SWE315 Programming Languages
Preliminaries
YPU
Fall 2017
Damascus
Programming Language
⧫ A programming language is an artificial
language designed to express computations or
algorithms that can be performed by a
computer -- Wikipedia
⧫ A program is computer coding of
an algorithm that Input
⚫ Takes input
⚫ Performs some calculations on
the input Program
⚫ Generates output
Output
1
Outline
⧫ Three models of programming languages
⧫ A brief history
⚫ Programming design methodologies in perspective
(Sec. 1.4.2)
⧫ Language evaluation criteria (Sec. 1.3)
⚫ Language design trade-offs (Sec. 1.6)
⧫ Implementation methods (Sec. 1.7)
2
Models of Programming Languages
Programming is like …
3
1st View: Imperative & Procedural
⧫ Computers take commands and do operations
⧫ Thus, programming is like …
issuing procedural commands to the computer
⚫ Example: a factorial function in C
int fact(int n) {
int sofar = 1;
while (n>0) sofar *= n--;
return sofar;
}
⧫ Since almost all computers today use the von
Neumann architecture → PL mimic the arch.
4
The von Neumann Architecture
Program counter
(Fig. 1.1) 5
The von Neumann Architecture
⧫ Key features:
⚫ Data and programs stored in memory
⚫ Instructions and data are piped from memory to CPU
⚫ Fetch-execute-cycle for each machine instruction
initialize the program counter (PC)
repeat forever
fetch the instruction pointed by PC
increment the counter
decode the instruction
add A,B,C 0100 1001
execute the instruction sub C,D,E 0110 1010
end repeat br LOOP 1011 0110
… …
Assembly Machine
code code 6
Imperative Language and Arch.
⧫ Example: a factorial function in C
int fact(int n) { sofar
int sofar = 1; n
while (n>0) sofar *= n--; int fact(int n) {
return sofar; int sofar = 1;
while (n>0) sofar *= n--;
} return sofar; }
⚫ Indicates that data n,
sofar, and program code
are stored in memory
⚫ Program code instructs Program counter
CPU to do operations
7
Imperative Languages and Arch.
⧫ Imperative languages, e.g., C, C++, Java, which
dominate programming, mimic von Neumann
architecture
⚫ Variables → memory cells
⚫ Assignment statements → data piping between
memory and CPU
⚫ Operations and expressions → CPU executions
⚫ Explicit control of execution flows → prog. counter
⧫ Allow efficient mapping between language and
hardware for good execution performance, but
limited by von Neumann bottleneck
8
Layers of Abstraction/Translation
High Level Language temp = v[k];
Program
v[k] = v[k+1];
Compiler v[k+1] = temp;
Assembly Language lw $15, 0($2)
Program lw $16, 4($2)
Assembler
sw$16, 0($2)
sw$15, 4($2)
Machine Language 0000 1001 1100 0110 1010 1111 0101 1000
Program 1010 1111 0101 1000 0000 1001 1100 0110
1100 0110 1010 1111 0101 1000 0000 1001
0101 1000 0000 1001 1100 0110 1010 1111
Machine
Interpretation All imperative!
Control Signal
Specification ALUOP[0:3] <= InstReg[9:11] & MASK
9
2nd View: Functional
⧫ Programming is like …
solving mathematical functions, e.g.,
z = f(y, g(h(x)))
⚫ A program, and its subprograms, are just
implementations of mathematical functions
⚫ Example: a factorial function in ML
fun fact x = Input Input
if x <= 0
then 1
else x * fact(x-1); Program Function
Output Output 10
Another Functional Language: LISP
⧫ Example: a factorial function in Lisp
(defun fact (x)
(if (<= x 0) 1 (* x (fact (- x 1)))))
⚫ Computations by applying functions to parameters
⚫ No concept of variables (storage) or assignment
◼ Single-valued variables: no assignment, not storage
⚫ Control via recursion and conditional expressions
◼ Branches → conditional expressions
◼ Iterations → recursion
⚫ Dynamically allocated linked lists
⧫ 2nd-oldest general-purpose PL still in use (1958)
11
3rd View: Logic
⧫ Programming is like …
logic induction
⚫ Program expressed as rules in formal logic
⚫ Execution by rule resolution
⚫ Example: relationship among people
fact: mother(joanne,jake).
father(vern,joanne).
rule: grandparent(X,Z) :- parent(X,Y),
parent(Y,Z).
goal: grandparent(vern,jake).
12
Logic Programming
⧫ Non-procedural
⚫ Only supply relevant facts (predicate calculus) and
inference rules (resolutions)
⚫ System then infer the truth of given queries/goals
⧫ Highly inefficient, small application areas
(database, AI)
⚫ Example: a factorial function in Prolog
fact(X,1) :- X =:= 1.
fact(X,Fact) :-
X > 1, NewX is X - 1,
fact(NewX,NF),
Fact is X * NF.
13
Summary: Language Categories
Imperative Functional
Logic Language
Language Language
Memory
ALU Control
von Neumann Architecture
14
Summary: Language Categories
⧫ Imperative
⚫ Variables, assignment statements, and iteration
⚫ Include languages that support object-oriented
programming, scripting languages, visual languages
⚫ Ex.: C, Java, Perl, JavaScript, Visual BASIC .NET
⧫ Functional
⚫ Computing by applying functions to given parameters
⚫ Ex.: LISP, Scheme, ML
⧫ Logic
⚫ Rule-based (rules are specified in no particular order)
⚫ Ex.: Prolog
15
Outline
⧫ Three models of programming languages
⧫ A brief history
⚫ Programming design methodologies in perspective
(Sec. 1.4.2)
⧫ Language evaluation criteria (Sec. 1.3)
⚫ Language design trade-offs (Sec. 1.6)
⧫ Implementation methods (Sec. 1.7)
16
Programming Design Methodology
⧫ 1950s and early 1960s: simple applications;
worry about machine efficiency (FORTRAN)
⧫ Late 1960s: people efficiency important;
readability, better control structures (ALGOL)
⚫ Structured programming, free format lexical
⚫ Top-down design and step-wise refinement
⧫ Late 1970s: process-oriented to data-oriented
⚫ Data abstraction
⧫ Middle 1980s: object-oriented programming
⚫ Data abstraction + inheritance + dynamic binding
17
Genealogy
of
Common
Languages
(Fig. 2.1)
18
Outline
⧫ Three models of programming languages
⧫ A brief history
⚫ Programming design methodologies in perspective
(Sec. 1.4.2)
⧫ Language evaluation criteria (Sec. 1.3)
⚫ Language design trade-offs (Sec. 1.6)
⧫ Implementation methods (Sec. 1.7)
19
What Make a Good PL?
Language evaluation criteria:
⧫ Readability: the ease with which programs can
be read and understood
⧫ Writability: the ease with which a language
can be used to create programs
⧫ Reliability: a program performs to its
specifications under all conditions
⧫ Cost
20
Features Related to Readability
⧫ Overall simplicity: lang. is more readable if
⚫ Fewer features and basic constructs
◼ Readability problems occur whenever program’s author
uses a subset different from that familiar to reader
⚫ Fewer feature multiplicity (i.e., doing the same
operation with different ways)
⚫ Minimal operator overloading
⧫ Orthogonality
⚫ A relatively small set of primitive constructs can be
combined in a relatively small number of ways
⚫ Every combination is legal, independent of context
➔ Few exceptions, irregularities
21
Features Related to Readability
⧫ Control statements
⚫ Sufficient control statements for structured prog.
→ can read program from top to bottom w/o jump
⧫ Data types and structures
⚫ Adequate facilities for defining data type & structure
⧫ Syntax considerations
⚫ Identifier forms: flexible composition
⚫ Special words and methods of forming compound
statements
⚫ Form and meaning: self-descriptive constructs,
meaningful keywords
22
Writability
⧫ Simplicity and orthogonality
⚫ But, too orthogonal may cause errors undetected
⧫ Support for abstraction
⚫ Ability to define and use complex structures or
operations in ways that allow details to be ignored
⚫ Abstraction in process (e.g. subprogram), data
⧫ Expressivity
⚫ A set of relatively convenient ways of specifying
operations
⚫ Example: the inclusion of for statement in many
modern languages
23
Reliability
⧫ Type checking
⚫ Testing for type errors, e.g. subprogram parameters
⧫ Exception handling
⚫ Intercept run-time errors & take corrective measures
⧫ Aliasing
⚫ Presence of two or more distinct referencing methods
for the same memory location
⧫ Readability and writability
⚫ A language that does not support “natural” ways of
expressing an algorithm will necessarily use
“unnatural” approaches, and hence reduced reliability
24
Cost
⧫ Training programmers to use language
⧫ Writing programs (closeness to particular
applications)
⧫ Compiling programs
⧫ Executing programs: run-time type checking
⧫ Language implementation system: availability of
free compilers
⧫ Reliability: poor reliability leads to high costs
⧫ Maintaining programs
25
Others
⧫ Portability
⚫ The ease with which programs can be moved from
one implementation to another
⧫ Generality
⚫ The applicability to a wide range of applications
⧫ Well-definedness
⚫ The completeness and precision of the language’s
official definition
⧫ Power efficiency?
26
Language Design Trade-Offs
⧫ Reliability vs. cost of execution
⚫ e.g., Java demands all references to array elements
be checked for proper indexing but that leads to
increased execution costs
⧫ Readability vs. writability
⚫ e.g., 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
⚫ e.g., C++ pointers are powerful and very flexible but
not reliably used
27
Outline
⧫ Three models of programming languages
⧫ A brief history
⚫ Programming design methodologies in perspective
(Sec. 1.4.2)
⧫ Language evaluation criteria (Sec. 1.3)
⚫ Language design trade-offs (Sec. 1.6)
⧫ Implementation methods (Sec. 1.7)
28
Implementations of PL
⧫ It is important to understand how features and
constructs of a programming language, e.g.,
subroutine calls, are implemented
⚫ Implementation of a PL construct means its
realization in a lower-level language, e.g. assembly
→ mapping/translation from a high-level language to
a low-level language
⚫ Why the need to know implementations?
Understand whether a construct may be implemented
efficiently, know different implementation methods
and their tradeoffs, etc.
29
Implementation by Compilation
⧫ Translate a high-level program into equivalent
machine code automatically by another program
(compiler)
⧫ 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 syntactic structure of program
⚫ Semantics analysis: generate intermediate code
⚫ Code generation: machine code is generated
⚫ Link and load
30
Compilation
Process
(Fig. 1.3)
31
Implementation by Interpretation
⧫ Program interpreted by another program
(interpreter) without translation
⚫ Interpreter acts a simulator or virtual machine
⧫ Easier implementation of programs (run-time
errors can easily and immediately displayed)
⧫ Slower execution (10 to 100 times slower than
compiled programs)
⧫ Often requires more space
⧫ Popular with some Web scripting languages
(e.g., JavaScript)
32
Hybrid Implementation Systems
⧫ A high-level language program is translated to
an intermediate language that allows easy
interpretation
⚫ Faster than pure interpretation
33
Summary
⧫ Most important criteria for evaluating
programming languages include:
⚫ Readability, writability, reliability, cost
⧫ Major influences on language design have been
application domains, machine architecture and
software development methodologies
⧫ The major methods of implementing
programming languages are: compilation, pure
interpretation, and hybrid implementation
34
