Transcript PPT

CS2403 Programming Languages
Preliminaries
Chung-Ta King
Department of Computer Science
National Tsing Hua University
(Slides are adopted from Concepts of Programming Languages, R.W. Sebesta;
Modern Programming Languages: A Practical Introduction, A.B. Webber)
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
Input
an algorithm that
 Takes input
 Performs some calculations on
Program
the input
 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
code
…
Machine
code 6
Imperative Language and Arch.

Example: a factorial function in C
int fact(int n) {
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
CPU to do operations
sofar
n
int fact(int n) {
int sofar = 1;
while (n>0) sofar *= n--;
return sofar; }
Program counter
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
temp = v[k];
High Level Language
Program
v[k] = v[k+1];
Compiler
v[k+1] = temp;
lw
$15, 0($2)
lw
$16, 4($2)
sw$16, 0($2)
sw$15, 4($2)
Assembly Language
Program
Assembler
Machine Language
Program
Machine
Interpretation
Control Signal
Specification
0000
1010
1100
0101
1001
1111
0110
1000
1100
0101
1010
0000
0110
1000
1111
1001
1010
0000
0101
1100
1111
1001
1000
0110
0101
1100
0000
1010
1000
0110
1001
1111
All imperative!
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 =
if x <= 0
then 1
else x * fact(x-1);
Input
Input
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).
grandparent(vern,jake).
goal:
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
Logic Language
Imperative
Language
Functional
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