Concepts of Programming Languages
Lecture 1 - Introduction
Patrick Donnelly
Montana State University
Spring 2014
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 1 / 46
Textbook
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 2 / 46
Administrivia
Website:
http://nisl.cs.montana.edu/~pdonnelly/CSCI305/
Reading:
Chapter 1
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 3 / 46
A good programming language is a conceptual universe
for thinking about programming.
A. Perlis
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 4 / 46
Reasons for Studying Programming Languages
Increased ability to express ideas
Improved background for choosing appropriate languages
Increased ability to learn new languages
Better understanding of significance of implementation
Better use of languages that are already known
Overall advancement of computing
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 5 / 46
Principles
Programming languages have four properties:
Syntax
Names
Types
Semantics
For any language:
Its designers must define these properties
Its programmers must master these properties
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 6 / 46
Syntax
Definition
The syntax of a programming language is a precise description of all
its grammatically correct programs.
When studying syntax, we ask questions like:
What is the grammar for the language?
What is the basic vocabulary?
How are syntax errors detected?
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 7 / 46
Names
Various kinds of entities in a program have names:
variables
types
functions
parameters
classes
objects
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 8 / 46
Names
Various kinds of entities in a program have names:
variables
types
functions
parameters
classes
objects
Named entities are bound in a running program to:
Scope
Visibility
Type
Lifetime
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 8 / 46
Types
Definition
A type is a collection of values and a collection of operations on those
values.
Simple types: Structured types
numbers Strings,
characters lists,
booleans, . . . etc. trees,
hash tables, . . . etc..
Definition
A language’s type system can help to:
Determine legal operations
Detect type errors
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 9 / 46
Semantics
Definition
The meaning of a program is called its semantics.
In studying semantics, we ask questions like:
When a program is running, what happens to the values of the
variables?
What does each statement mean?
What underlying model governs run-time behavior, such as
function call?
How are objects allocated to memory at run-time?
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 10 / 46
Paradigms
Definition
A programming paradigm is a pattern of problem-solving thought that
underlies a particular genre of programs and languages.
There are four main programming paradigms:
Imperative
Object-oriented
Functional
Logic
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 11 / 46
Imperative Paradigm
Follows the classic von Neumann-Eckert model:
Program and data are indistinguishable in memory
Program = a sequence of commands
State = values of all variables when program runs
Large programs use procedural abstraction
Example imperative languages:
Cobol
Fortran
C
Ada
Perl
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 12 / 46
The von Neumann-Eckert Model
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 13 / 46
Object-oriented (OO) Paradigm
An OO Program is a collection of objects that interact by passing
messages that transform the state.
When studying OO, we learn about:
Sending Messages
Inheritance
Polymorphism
Example OO languages:
Smalltalk
Java
C++
C#
Python
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 14 / 46
Functional Paradigm
Functional programming models a computation as a collection of
mathematical functions.
Input = domain
Output = range
Functional languages are characterized by:
Functional composition
Recursion
Example functional languages:
Lisp
Scheme
ML
Haskell
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 15 / 46
Logic Paradigm
Logic programming declares what outcome the program should
accomplish, rather than how it should be accomplished.
When studying logic programming we see:
Programs as sets of constraints on a problem
Programs that achieve all possible solutions
Programs that are nondeterministic
Example logic programming languages:
Datalog
Prolog
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 16 / 46
Special Topics
Concurrency:
e.g., Client-server programs
Correctness:
How can we prove that a program does what it is
supposed to do under all circumstances?
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 17 / 46
On Language Design
Design Constraints:
Computer architecture
Technical setting
Standards
Legacy systems
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 18 / 46
On Language Design
Design Constraints:
Computer architecture
Technical setting
Standards
Legacy systems
Outcomes and Goals:
1 How does a programming language emerge and become
successful?
2 What key characteristics make an ideal programming language?
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 18 / 46
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 19 / 46
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 20 / 46
Language Design Trade-Offs
Reliability vs. cost of execution
Example: Java demands all references to array elements be
checked for proper indexing, which leads to increased execution
costs
Readability vs. writability
Example: APL provides many powerful operators (and a large
number of new symbols), allowing complex computations to be
written in a compact program but at the cost of poor readability
Writability (flexibility) vs. reliability
Example: C++ pointers are powerful and very flexible but are
unreliable
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 21 / 46
Compilation
Compiler – translate high-level program (source language) into
machine code (machine language)
Programs are translated into machine language; includes JIT
systems
Slow translation, fast execution
Use: Large commercial applications
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 22 / 46
Compilation
Compiler – translate high-level program (source language) into
machine code (machine language)
Programs are translated into machine language; includes JIT
systems
Slow translation, fast execution
Use: Large commercial applications
Example compiled languages:
Fortran, Cobol, C, C++
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 22 / 46
Compilation
Compilation process has several phases:
lexical analysis: converts characters in the source program into
lexical units
syntax analysis: transforms lexical units into parse trees which
represent the syntactic structure of program
semantics analysis: generate intermediate code
code generation: machine code is generated
Load module (executable image): the user and system code
together
Linking and loading: the process of collecting system program units
and linking them to a user program
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 23 / 46
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 24 / 46
Von Neumann Bottleneck
Connection speed between a computer’s memory and its processor
determines the speed of a computer
Program instructions often can be executed much faster than the
speed of the connection; the connection speed thus results in a
bottleneck
Known as the von Neumann bottleneck; it is the primary limiting
factor in the speed of computers
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 25 / 46
Pure Interpretation
Interpreter – executes instructions on a virtual machine
Programs are interpreted by another program known as an
interpreter
No translation
Easier implementation of programs (run-time errors can easily and
immediately be displayed)
Slower execution (10 to 100 times slower than compiled programs)
Often requires more space
Now rare for traditional high-level languages but recent comeback
with some Web scripting languages (e.g., JavaScript, PHP)
Use: Small programs or when efficiency is not an issue
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 26 / 46
Pure Interpretation
Interpreter – executes instructions on a virtual machine
Programs are interpreted by another program known as an
interpreter
No translation
Easier implementation of programs (run-time errors can easily and
immediately be displayed)
Slower execution (10 to 100 times slower than compiled programs)
Often requires more space
Now rare for traditional high-level languages but recent comeback
with some Web scripting languages (e.g., JavaScript, PHP)
Use: Small programs or when efficiency is not an issue
Example interpreted languages:
Scheme, Haskell, Python
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 26 / 46
The Interpreting Process
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 27 / 46
Hybrid Implementation Systems
A compromise between compilers and pure interpreters
A high-level language program is translated to an intermediate
language that allows easy interpretation
Faster than pure interpretation
Use: Small and medium systems when efficiency is not the first
concern
Example Hybrid compilation/interpretation
The Java Virtual Machine (JVM)
Perl programs are partially compiled to detect errors before
interpretation
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 28 / 46
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 29 / 46
Just-in-Time Implementation Systems
Initially translate programs to an intermediate language
Then compile the intermediate language of the subprograms into
machine code when they are called
Machine code version is kept for subsequent calls
JIT systems are widely used for Java programs
.NET languages are implemented with a JIT system
In essence, JIT systems are delayed compilers
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 30 / 46
Preprocessors
Preprocessor macros (instructions) are commonly used to specify that
code from another file is to be included
A preprocessor processes a program immediately before the program
is compiled to expand embedded preprocessor macros
A well-known example: C preprocessor expands #include,
#define, and similar macros
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 31 / 46
Characteristics of a Successful Language
Simplicity and readability
Clarity about binding
Reliability
Support
Abstraction
Orthogonality
Efficient implementation
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 32 / 46
Characteristics of a Successful Language
Simplicity and readability
Clarity about binding
Reliability
Support
Abstraction
Orthogonality
Efficient implementation
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 33 / 46
Simplicity and Readability
Small instruction set:
e.g., Java vs Scheme
Simple syntax:
e.g., C/C++/Java vs Python
Benefits:
Ease of learning
Ease of programming
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 34 / 46
Characteristics of a Successful Language
Simplicity and readability
Clarity about binding
Reliability
Support
Abstraction
Orthogonality
Efficient implementation
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 35 / 46
Clarity about Binding
A language element is bound to a property at the time that property is
defined for it.
Definition
A binding is the association between an object and a property of that
object.
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 36 / 46
Clarity about Binding
A language element is bound to a property at the time that property is
defined for it.
Definition
A binding is the association between an object and a property of that
object.
Examples
a variable and its type
a variable and its value
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 36 / 46
Clarity about Binding
A language element is bound to a property at the time that property is
defined for it.
Definition
A binding is the association between an object and a property of that
object.
Examples
a variable and its type
a variable and its value
Early binding takes place at compile-time.
Late binding takes place at run time
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 36 / 46
Characteristics of a Successful Language
Simplicity and readability
Clarity about binding
Reliability
Support
Abstraction
Orthogonality
Efficient implementation
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 37 / 46
Reliability
A language is reliable if:
Program behavior is the same on different platforms
e.g., early versions of Fortran
Type errors are detected
e.g., C vs Haskell
Semantic errors are properly trapped
e.g., C vs C++
Memory leaks are prevented
e.g., C vs Java
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 38 / 46
Characteristics of a Successful Language
Simplicity and readability
Clarity about binding
Reliability
Support
Abstraction
Orthogonality
Efficient implementation
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 39 / 46
Language Support
Accessible (public domain) compilers/interpreters
Good texts and tutorials
Wide community of users
Integrated with development environments (IDEs)
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 40 / 46
Characteristics of a Successful Language
Simplicity and readability
Clarity about binding
Reliability
Support
Abstraction
Orthogonality
Efficient implementation
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 41 / 46
Abstraction in Programming
Data:
Programmer-defined types/classes
Class libraries
Procedural:
Programmer-defined functions
Standard function libraries
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 42 / 46
Characteristics of a Successful Language
Simplicity and readability
Clarity about binding
Reliability
Support
Abstraction
Orthogonality
Efficient implementation
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 43 / 46
Orthogonality
Definition
A language is orthogonal if its features are built upon a small,
mutually independent set of primitive operations.
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 44 / 46
Orthogonality
Definition
A language is orthogonal if its features are built upon a small,
mutually independent set of primitive operations.
Fewer exceptional rules = conceptual simplicity
Example
restricting types of arguments to a function
Tradeoffs with efficiency
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 44 / 46
Characteristics of a Successful Language
Simplicity and readability
Clarity about binding
Reliability
Support
Abstraction
Orthogonality
Efficient implementation
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 45 / 46
Efficient Implementation
Embedded systems
Real-time responsiveness (e.g., navigation)
Failures of early Ada implementations
Web applications
Responsiveness to users (e.g., Google search)
Corporate database applications
Efficient search and updating
AI applications
Modeling human behaviors
Patrick Donnelly (Montana State University) Concepts of Programming Languages Spring 2014 46 / 46
