Introduction to Programming
What is a Programming Language?
• Formally, a set of finite sequences of elements of
the alphabet
– E.g., abcd…
• It has a syntax and a semantics
– We will define these in great detail shortly
– Communicates only an algorithmic idea
• A programming language makes it easier and
efficient for people to communicate with
Principles of Language Design
• The major principles that underlie the design of
modern programming languages are
Type systems (semantics)
Memory Management
Exception Handling
• We treat these categories formally instead of just
comparing features of different languages to
– Apply more rigor (needed for example in writing a
– Understand future languages better (formalisms
• Tells us what constitutes a correctly written
– Vocabulary
– Alphabet
• Not unlike work with spoken languages
– Borrows from linguistic theory, grammar
– Most programming languages use a contextfree grammar
Type Systems and Semantics
• If the syntax is correct…
– What kind of values can we manipulate?
• Is a 32 bit value an integer, a float, 4 ASCII characters, etc.
– Semantics applies meaning to the data values
• What is the exact effect of a statement on the state
of computation?
– What happens next?
– These must all be defined somehow; we will use a
formal abstract definition for semantics
Memory Management
• Collection of techniques to map values and
data structures to memory
– Static vs. Dynamic memory
– Use of the heap
– Garbage collection and reclamation
• Numerous algorithms and strategies have
been designed to manage memory
Exception Handling
• An exception is an unexpected event
– Division by zero
– Overflow
– Illegal memory access
• How can these be trapped and handled?
• (will mostly skip this chapter in the class)
Tower of Babel of Programming
• What programming languages do you
already know or can think of the names?
Why so many languages?
Application domains
Levels of Languages
Different philosophies to solve problems
Language improvement
Application Domains
Scientific Computing
– Mathematical, Parallel, Historically FORTRAN
Management Information Systems
– Database, SQL
– COBOL for business systems
– Client/Server approach popular
Artificial Intelligence
– Intelligent behavior, deduction
– Roots of functional and logical programming
– Compilers, OS, network, etc.
– Typically low level languages, Assembly/C
– Overlap with other applications
– Client/Server, often interpreted
Programming Paradigms
• Paradigm: Model or mental framework for thinking about
– Procedural/Imperative
• Programs are a series of steps; assignments, loops, sequences, conditional
– Object-Oriented
• Collection of interacting objects; inheritance, polymorphism
– Functional
• Program is a collection of mathematical functions using functional
– Logic
• Program is a collection of logical declarations; states what the outcome
should be rather than how to accomplish the outcome
– Event-Driven
• Continuous loop responding to events
– Concurrent
• Collection of cooperating processes; issues for parallelism
Pragmatic Considerations
• Architecture constraints
– Stuck with the von Neumann
– Instruction set matches with
Imperative model
• Contextual constraints
– Relates back to application
area, levels of languages
– General purpose vs. special
– Compiled vs. interpreted
Virtual Machine
• This text uses the virtual machine model for a language called “Clite”
• Interpreter is Java, so Clite is really doubly-interpreted! (or Just-InTime Compiled)
• By doing so, we avoid details of mapping a language to a specific
machine architecture
• Standardization – process of defining a machineindependent definition to which all implementors
of the language must adhere
– Used to be bottom-up and standardization only took
place if a language was used enough
– Process is becoming top-down with larger companies
(e.g. Microsoft, Sun)
• Major standards organizations, ANSI, ISO, ECMA
– Slow process, e.g. ANSI/ISO C (1999)
Brief history of PL’s
FORmula TRANslation
– IBM 1957; John Backus
First high level language
Designed to support numerical computation
– Still used today in scientific computing
Code snippet
10 IF (NUMBER .LT. 0) GO TO 20
GO TO 10
20 …
Early versions used GOTO
A simple FORTRAN error resulted in errors for NASA’s Project Mercury suborbital flights (myth for Mariner Venus probe)
– DO 3 I = 1,3 was mistyped as DO 3 I = 1.3 which was accepted by the compiler as
assigning 1.3 to the variable DO3I
• Common Business Oriented Language
• Designed for business needs; payroll,
accounting, etc.
– Responsible for huge amounts of legacy code
• Designed to be English-Like to make it
‘easy to program’
• 1970 Nicklaus Wirth
• Designed to enforce good programming
techniques as a teaching language, easy to learn
– Taught in most schools/universities in the 80’s
• Not embraced as an industrial language; instead
they used C
– But offshoot language Delphi (Borland) is used
commonly and commercially today; competitor to
Microsoft’s Visual Basic
• 1970 – Dennis Ritchie, Bell Labs
• Originally designed to write UNIX
– Close to assembly, allows speed efficiencies
– Led to its popularity today, the basis for just
about every operating system (including
– One of the most popular choices when it comes
to real-time systems
• 1980 – Bjarne Stroustrup, Bell Labs
• Superset of C++
– Adds object-oriented programming on top of C
• Standardized by ANSI/ISO
– One of the most popular commercial languages
today, allows low-level access of C together
with OOP
• We’ll examine C++ in this class
• Relatively new language developed by Microsoft
– ECMA standard, on fast track for ISO standard
• Combines aspects of C++/Java/Visual Basic
Uses concept of virtual machine (CLI) - .NET
Easy integration with web services
Easy development of GUI via IDE
Cleans up some messiness of previous languages
• We will also examine C# in this class
• Named after Ada Lovelace
– Daughter of Lord Byron
– Mathematician, Scientist
• 1979 US Armed Services
– Intended as a common language for all government
– Powerful; OOP, Multiprocessing, structures for
efficiency and re-usability
• Criticized for being difficult to learn
• Don’t see much ADA around nowadays
• 1994 – James Gosling, Sun Microsystems
• Virtual machine
– Both interpreted and compiled
• Rise of the web has been attributed to its success
• No ISO/ECMA standard of Java
– Sun pulled out of the standards process in 1999 for
more control
– Does have “Java Community Process”
• 1958 – John McCarthy
• LISt Processing
– Based on Alonzo Church’s Lambda Calculus
• Computing with symbolic expressions rather than numbers
• List structure as the key data structure
• Composition of functions as a tool for forming more complex
• Sample
(defun list-of (n elt)
(if (zerop n)
(cons elt (list-of (- n 1) elt))))
• We’ll study Scheme, an offshoot of Lisp
• 1980’s Standard Meta Language
– Edinburgh Lab, Robin Milner
• Fully formal definition
Close to mathematics (sets, tuples, functions)
No declarations as in imperative languages
No side effects
Type of variables is computed by inference, depending
on context
• [1,4,5] = list of integers
• (1,1) is a tuple of integers
• fun square(x) = x*x;
• 1972 - Alan Colmeraurer
• PROgramming LOGic
– ISO standard 1995
• A Prolog program is a set of facts and a set of logical rules
speaks(mary, russian).
speaks(bob, english).
talkswith(P1,P2) :- speaks(P1,L),
speaks(P2,L), P1\=P2.
Program that defines people that speak Russian and that you talk to
someone that speaks the same language.
• Queries: speaks(mary,X). ; X=english, russian
Special Purpose Languages
• Languages designed for specific tasks
• Retrieval from relational databases
• Practical extraction and report language
• Processing strings, regular expressions
• Markup of hypertext
• When we get to PHP we will assume you know some HTML
Programming Language Qualities
• Simplicity and clarity
– How easy is it to write in the language?
– Different definitions; some minimize keystrokes
• Binding
– How are values bound to variables?
• Definition, compilation, runtime, early vs. late binding
• Orthogonality
– Do features combine in a predictable way? E.g. meaning of +
• Reliability
– Behave the same way each time it is run?
• Applicability
– How well does the language map to its applications?
• Abstraction
– Low or high level?
• Efficiency
– Practical and efficient on a von Neumann machine?
• There are lots of programming languages out there
– Different paradigms
– Different applications
– Different levels of computing
• There will probably continue to be even more
programming languages in the future
• By studying formal properties of programming
languages and a sampling of paradigms, you will
be well prepared to face these new languages