Transcript Powerpoint slides by Dr. Smith

CSC 434
Programming
Languages
Fall 2001
Why Study P.L.’s?
Broader
point of view
Employability
Pick appropriate P.L. for the job
Design a new P.L.
Use in implementing a P.L.
Programming Paradigms
Imperative
Functional
Logic
Object
oriented
Distributed / parallel
Criteria for Evaluating
Programming Languages
Expressive
power
Simplicity and orthogonality
Implementation
Error detection and correction
Program correctness and standards
Expressive Power
 Writability
control structures
data structures
operators
modularity
 Readability
syntax !
maintenance
Simplicity and Orthogonality
Levels
of precedence (15 in C)
Not too many constructions, with all
combinations valid and no special cases
K++
++K
K += 1
K = K + 1
Implementation Issues
Cost and Efficiency
 Compiling
2 stages
faster execution
 Interpreting
1 stage
slower execution
The Stages of Compiling
Source program
Lexical phase
Tokens
Syntax phase
Parse tree
Semantic phase
Object program
Error Detection and Correction
 Type
checking
 Pointer problems
 Array subscripts out of range
 Run-time exceptions
…
Correctness and Standards
 BASIC
versus Ada for standards
 Program structure
 Formal proofs (predicate calculus)
invariants
pre-conditions and post-conditions
Evolution of P.L.’s (1 of 2)
– surprising success of 1st HLL
 Algol 60 – reasons it did not succeed, but
enormous influence, BNF
 COBOL – data processing, influence of DOD
 PL/1 – synthesis of Fortran and COBOL
 Basic – original simplicity, time-sharing, lack
of a standard
 Fortran
Evolution of P.L.’s (2 of 2)
– for teaching CS concepts, influence
of strong typing
 C – for systems programming, weak typing
 Ada – influence of DOD, rigorous standard
 Modula-2 – simpler alternative to Ada
 Others – Lisp, Prolog, C++, Java, …
 Pascal
See Appendix 1, pp. 329-345
Syntax and Semantics of P.L.’s
Backus Normal Form (BNF)
 Syntax
versus semantics
 BNF is a meta-language, first used for
Algol 60
 A grammar G defines a language L(G)
 The grammar G can be used:
to generate a valid sentence in L(G)
to recognize if a given sentence is valid
according to the rules of G
Elements of BNF Syntax
Consists
of rules, or productions
::= means ‘is defined to be’
| means ‘or’
Identifiers within ‘< >’ are syntactic
categories, or non-terminal symbols
Other symbols are terminal symbols
that represent themselves literally
Example of a BNF Grammar
<exp> ::= <exp> + <term>
| <exp> - <term>
| <term>
<term> ::= <term> * <factor>
| <term> / <factor>
| <factor>
<factor> ::= ( <exp> ) | <identifier>
Other Features of Syntax
grammars – the dangling else
 EBNF uses [ ] for optional items and { } for
zero or more repetitions
 Ambiguous
<integer> ::= [+|-] <unsigned integer>
<identifier> ::= <letter> { <letter> | <digit> }
 Syntax
diagrams a graphical form of EBNF
Semantics of P.L.’s – Harder!
 Operational
Semantics – uses a virtual
machine
 Denotational Semantics – manipulates
mathematical objects
 Axiomatic Semantics – uses predicate
calculus to prove properties of program
statements
Miscellaneous P.L. Syntax
 Special
words in a P.L.
keywords – meaning varies with context
reserved words – meaning is fixed
 Use of blanks (Fortran example)
 Comments
/* … */
// …
 Case sensitivity – why it might be avoided
Block Structure
 Nested
functions / procedures
 Scope of variables (inside out)
local variables
non-local variables
global variables
 Storage categories (lifetime)
static storage
automatic storage
dynamic storage
Bindings
name to its declaration – scope
 Binding declaration to its reference – lifetime
 Binding reference to its value – assignment
 Binding
 When
do bindings occur?
compile time? load time? run time?
 own variables in Algol 60, static in C
 Finding
value, given address is dereferencing
Static Scope and Dynamic Scope
 In
static scope a procedure is called in the
environment of its definition – can be
determined at compile time.
 In
dynamic scope a procedure is called in
the environment of its caller – must be
determined at run time.
 Hazards
of dynamic scope.
Static Scope and Dynamic Scope
PROGRAM Dynamic (input, output);
VAR x: integer;
PROCEDURE a;
BEGIN
… write (x);
…
END;
PROCEDURE b;
VAR x: real;
BEGIN
… x := 2.0;
… a; …
END;
BEGIN
…
x := 1;
…
b; … a; …
END.
Binding the Type
typing (static) is good – catch errors at
compile time – Pascal, Ada
 Strong

Implicit typing – e.g., first letter of variable name
in Fortran, $ suffix in Basic, …

Type inferencing – type determined at run time,
can change during execution – APL
Simple Data Types
Primitive Data Types (portability ??)
boolean (not in C)
integers
reals
complex (in Fortran)
 Enumerated Types
day = (Sun, Mon, Tues, Wed, Thurs, Fri, Sat);
 Subrange Types
work = Mon .. Fri;

Pointer Variables
TYPE integerpt = ^integer;
VAR p: integer;
pipoint, another: integerpt;
new (pipoint);
pipoint^ := 17;
another := pipoint;
Another is now an alias for pipoint. If we
deallocate using pipoint, the memory
block is gone, but another still refers to it
– a dangling reference – a severe source
of runtime errors.
Data Structures
 Arrays
 Records
 Sets
 Strings
 Dynamic
lists
stacks
queues
trees
graphs
– using pointers
Arrays
 Index
type and base type
 Array storage allocation – the dope vector
 Array sizes – static, semi-dynamic,
dynamic
 Cross-sections or slices
 Equivalence
structural equivalence
name equivalence
Name/Structural Equivalence
TYPE
first = ARRAY [1..10] OF integer;
second = ARRAY [1..10] OF integer;
VAR
a: first;
b: second;
c: ARRAY [1..10] OF integer;
d,e: ARRAY [1..10] OF integer;
f: first;
Records
use indexing – A[j,k] – homogeneous elements
Records use qualification – R.field – heterogeneous fields
 Arrays with records as elements
Records with arrays as fields
 Variant records – conserve memory
a fixed part
a tag field, or discriminant
a variant part
but variant part may not correspond to tag!
 Arrays
Records – An Example
TYPE
spouse = RECORD
name: ARRAY [1..10] OF CHAR;
age: INTEGER;
END;
employee = RECORD
name: ARRAY [1..20] OF CHAR;
bday: ARRAY [1..3] OF INTEGER;
wage: real;
status: char;
spice = ARRAY [1..n] OF spouse;
END;
Records – Another Example
TYPE
shape = (circle, triangle, rectangle);
colors = (red, green, blue);
figure = RECORD
filled: boolean;
color: colors;
CASE form: shape OF
circle: (diameter: real);
triangle: (leftside: integer;
riteside: integer;
angle: real);
rectangle: (side1: integer;
side2: integer);
END;
VAR myfigure: figure;
Sets & Strings
 Set
representations
the characteristic vector
union / intersection via OR / AND
 String representations
terminal characters
fixed-length strings
varying-length strings
count-delimited strings
indexed list of strings
linked list strings
Evaluating Expressions
 Overloading
 Short
 Type
of operators
circuit evaluation
conversions
mixed mode arithmetic
assignment
coercion of parameters
casts
Control Structures
 Sequential
Processing
do A, then B, then C, …
 Conditional Processing (branching or
selection)
if A is true, then do B, else do C
 Iterative Processing (looping or repetition)
while A is true, do B {and test A again}
 Exceptions
Issues with Iteration
 Is
lcv a floating point variable?
 Is lcv declared explicitly or implicitly?
 What is value of lcv when loop terminates?
 When is termination test done?
 Can lcv be changed inside the loop?
 Can the loop be exited from the middle?
Structuring Programs
 Procedures,
functions, subroutines, …
 Formal versus actual parameters
 Named parameters
 Default parameters
 Overloading of function names – signatures
 Independent versus separate compilation
Parameter Passing
 Principal
methods
call by value
call by value-result
call by reference
call by name
 Complications with aliasing
Parameter Passing
VAR element: integer;
a: ARRAY [1..2] OF integer;
PROCEDURE whichmode (x: ? MODE integer)
BEGIN
a[1] := 6;
element := 2;
x := x + 3;
END;
BEGIN
a[1] := 1; a[2] := 2; element := 1;
whichmode (a[element]);
…
Elements of OOP
– information hiding,
as with ADT’s – modules, packages,
classes, …
Inheritance
Polymorphism – as with overloading
Dynamic binding – method call can
invoke different actual methods,
determined at run time
Encapsulation
Java Abstract Classes
An
abstract method is one that has a
header but no body, so cannot be
implemented.
An
abstract class is one in which one
or more of the methods are abstract.
Java Interfaces
 Multiple
inheritance would be desirable, as
provided in C++, but has significant problems.
 Instead Java provides interfaces. An interface
contains just constants and abstract methods.
Since they are all abstract, they are not labeled
as such.
 A class can then inherit from a parent class, and
also implement several interfaces. To do so, the
class must provide bodies for each of the
abstract methods in the interfaces.
Java Exceptions
Throwable objects include:
– errors, from which there is no recovery
– unchecked exceptions, such as for
arithmetical errors, which need not be
(but can be!) caught and dealt with
– checked exceptions, which must be
caught, even if no action is provided
 Code that may cause one or more
exceptions is placed in a try block.
 Code for dealing with exceptions is placed
in catch blocks.

Parallel Architectures
 Single
Instruction, Multiple Data (SIMD)
 Multiple Instruction, Multiple Data
(MIMD) via shared memory
 Multiple Instruction, Multiple Data
(MIMD) via message passing
 Each
of these must deal with the issue of
coordinating the parallel activities.
Problems of Parallelism
Non-determinism
Deadlock
Starvation
Fairness
Termination
Load
Balancing
Solving the Preceding
Problems
 Semaphores
are low-level, using flags set by
the user – easy to use improperly.
 Monitors are procedures that take on all of
the responsibility of assigning critical
resources to other processes, in response to
their requests.
 Rendezvous is the use of message passing to
coordinate the allocation of resources and
tasks to be performed.
 Both monitors and rendezvous were
invented by Tony Hoare!
Java Threads (1 of 3)
 Java
provides concurrency, which may or
not be true parallelism on multiple
CPU’s, via threads.
 Threads can be in several states: created,
running, suspended, stopped, …
 Once a thread is created, one must
explicitly start it; it will then perform the
functionality of its run method.
 Threads can be created either by
extending the thread class, or by
implementing the runnable interface.
Java Threads (2 of 3)
 Java
restricts access by competing
threads to critical regions of code via the
synchronized reserved word.
 When a method of a Java object is
synchronized, the object becomes a
monitor.
 When an object is a monitor in Java, then
when a thread T is using one of the
monitor’s synchronized methods, no other
thread can use any of the monitor’s
synchronized methods until T relinquishes
the monitor.
Java Threads (3 of 3)
Synchronization
is still not adequate
to coordinate the activities of threads.
It just prevents threads from stepping
on each other.
To provide coordination, one must use
wait( ) and notify( ), as with the
Producer-Consumer problem.
Dijkstra’s Guarded IF
if
expr1 -> stmt1
[]
expr2 -> stmt2
[]
…
[]
exprn -> stmtn
fi
Dijkstra’s Guarded DO
do
expr1 -> stmt1
[]
expr2 -> stmt2
[]
…
[]
exprn -> stmtn
od
The Run-Time Stack
 As
one subprogram calls another, a run-time stack is
used to keep track of all the necessary information in a
LIFO manner.
 The run-time stack contains activation records, and
these are linked by both static and dynamic chains.
 The static chain enables a subprogram to find non-local
variables according to the static scoping of
subprograms.
 The dynamic chain provides for appropriate return from
one subprogram to its caller. Also, in the case of
dynamic scoping, the system must dynamically search
the records in the chain for the first occurrence of nonlocals.
Functional Languages
 With
imperative languages, one must know the
entire state of the system, as determined by
assignments to memory locations.
 With functional languages, there are no
assignments, just the return of function values, so
there is no need to reason about the system state to
be sure of the result of a computation.
– no side effects
– referential transparency (always same results)
Lisp and its Variants
 Invented
by McCarthy at MIT ~ 1960
 Early versions
– MACLISP
– InterLisp
– Franz Lisp
– …
 Now Common Lisp
 Also Scheme and ML
Basics of Lists and Lisp (1 of 2)
 A List
is a finite sequence (possibly empty) of
elements, each of which is either an atom or a List.
 The first element of a List L is (car L).
 The remaining elements of a List L are (cdr L).
 Example L = ((A B) C ((D)))
(car L) = (A B)
(cdr L) = (C ((D)))
 We can represent Lists by diagrams in two ways that
reflect its original implementation on a 36-bit
machine.
Basics of Lists and Lisp (2 of 2)
 In
our diagrams,
(car L) is always either an atom or a List
(cdr L) is always a List, possibly empty
 Data and functions in Lisp are Lists! For a
function, the first element is the function
name, and the remaining elements are the
arguments.
 cons is used to put Lists together. Thus (cons
x y) returns a List z such that (car z) is x and
(cdr z) is y. Note that y must be a List!
Evaluation in Lisp
 Lisp
always evaluates List elements.
 But evaluation is suppressed by ‘ or
quote, and by the special function setq.
 (setq x y) evaluates y and assigns its value
to the unevaluated argument x.
 So Lisp is NOT purely functional!
 On the other hand eval forces evaluation.
(setq x ‘(+ 2 3 4))
x is (+ 2 3 4)
(eval x) is 9
Lisp: list & append
 list
takes any number of arguments, and
builds a List containing each actual
argument as an element
 append takes any number of arguments
(they must be Lists), and builds a List
stringing together their elements
 examples
(list ‘(a) ‘(b (c))) is ((a) (b (c)))
(append ‘(a) ‘(b (c))) is (a b (c))
Lisp: and & or
 (and
( ) ( ) …) returns nil as soon as any
argument evaluates to nil, else the value
of the last argument
 (or
( ) ( ) …) returns value of the first
argument that evaluates to non-nil, else
returns nil
 Note
the short-circuit evaluation
Lisp: defun
(defun fn (v1 v2 … vn)(exp))
Lisp does not evaluate the List elements.
Rather it stores away an association of the
function name fn with the parameters v1 ….
vn and the Lisp expression exp. This
association is consulted whenever fn is
invoked.
Lisp: cond
(cond (pred1 exp1)
(pred2 exp2)
…
(predn expn))
Lisp evaluates each predj in turn. For the
first one that is true, it returns with the
value of the corresponding expj. If none
of the predj are true, cond returns nil.
member versus ismember
 (member
e L) returns nil if e not in L, else
returns L from point of first match
 (defun
ismember (e L)
(cond ((null L) nil)
((equal e (car L)) t)
(t (ismember e (cdr L))) ))
apply, funcall, & mapcar
(apply fn list) applies fn to list, returning a value
(apply ‘cons ‘(a (b c))) yields (a b c)
funcall is like apply, except that the arguments
to fn are not in a list
(funcall ‘cons ‘a ‘(b c)) yields (a b c)
(mapcar fn list) applies fn to each element of
list, returning a new list
(mapcar ‘square ‘(2 3 4 5)) yields (4 9 16 25)
PROLOG
 PROgramming
in LOGic
 About relationships among objects
 A non-procedural language
 Extremely simple syntax
 Historical origins
Univ. of Marseille
Japanese 5th generation initiative
Univ. of Edinburgh
Prolog Facts
 Relationship
or predicate first
 Objects in parentheses, comma between
 Period at end
 Example:
female (alice).
female (marsha).
male (peter).
mother (marsha, peter).
mother (marsha, alice).
Variables and Queries
 Variables
are capitalized
 To match query to clause in database, must have
same predicate with same arity
 Instantiation of variables with goal of satisfying a
query
 Uninstantiation and backtracking
 Anonymous variable
 Closed world assumption
 Reversible satisfaction
Prolog Rules and Conjunction
 Conclusion
in head (one predicate)
 Requirements in body (zero or more predicates)
 :- between conclusion and requirements
 Period at end
happy (billy) :- day (christmas).
good (Date) :- tall (Date), rich (Date).
Instantiation and Backtracking
married (ben, ann).
mother (ann, sue).
mother (ann, tom).
father (Man, Child) :- married (Man, Woman),
mother (Woman, Child).
parent (Person, Child) :- mother (Person, Child).
parent (Person, Child) :- father (Person, Child).
?- father (ben, Whom).
?- parent (Who, sue).
More Prolog
 Recursion
in Prolog
ancestor (A,D) :- parent (A,D).
ancestor (A,D) :- parent (A,X), ancestor (X,D).
 Watch out for left recursion!
 Prolog is good for:
working with databases
solving logic problems
processing natural language (Eliza)