CSC 533: Organization of Programming Languages
Fall 2000
Final Exam Review
Programming Paradigms
procedural/imperative programming (e.g., C)
basic concept: machine state (memory cells/variables)
program by specifying a sequence of statements that alter the state
object-based programming (e.g., JavaScript)
basic concept: abstract data types
program by specifying complex types that interact via message passing
object-oriented programming (e.g., C++, Java)
basic concept: abstract data types + inheritance + dynamic (late) binding
program by defining hierarchies of interacting objects
functional programming (e.g., LISP/Scheme)
basic concept: functional transformation
program by defining and applying transformations to data
General Language Issues
language evaluation criteria
reliability, clarity/simplicity, orthogonality, speed, portability, ...
syntax & semantics
BNF grammar, parse trees, ambiguity, EBNF, precedence & associativity
operational, axiomatic, & denotational semantics
variables & binding
variable attributes, type/address/value binding, scope & lifetime
static vs. dynamic binding, stack-based memory management, activation records
data types
primitive types: integer, floating-point (& other numbers), boolean, character
pointer: indirect addressing, dynamic memory management
heap fragmentation & compaction, garbage collection vs. reference counts
complex types: string, enumeration, subrange, array/vector, record/struct
expressions & control structures
sub-expression evaluation order, compound statements, loops & branching
subprograms
parameter passing: by-value, by-result, by-value-result, by-reference, by-name
overloading functions/operators, templates
abstract data types (requires encapsulation + info hiding)
Modula-2: opaque vs. transparent types
C++ & Java protection modes: public, protected, private, package-only (Java)
OOP in C++
hybrid OOP language, combines procedural code with objects
can inherit data fields & member functions, override or add features
scope resolution operator can specify member functions from parent class
virtual member function specifies dynamic binding (implemented using pointer)
advanced OOP
generic types via templates
abstract base class: specifies form & properties of a derived class
multiple inheritance: ambiguities must be avoided using ::
OOP in Java
design goals: simple, object-oriented, secure, arch. neutral, portable, ...
based on C++ syntax, but removed many confusing/redundant features
name resolution at link time, automatic memory reclamation, ...
extensive libraries: Math, String, Array, Vector, Stack, HashTable, Random
Java execution models: applications vs. applets
primitive vs. reference types
primitive: semi-dynamic (type bound statically, address bound dynamically)
passed by-value, can generalize with wrapper classes
reference: explicit dynamic, must allocate using new (inherits from Object)
passed by-value, but behaves more like by-reference (since a pointer)
general-purpose, (pure) object-oriented programming language
similar to C++, can inherit data fields & methods, override methods, add features
can specify methods from parent class by specifying super
all methods are dynamically bound by default (can override with static)
advanced OOP
generic types via inheritance (e.g., vector of Objects)
abstract base class vs. interface
no multiple inheritance, but multiple interfaces OK
JavaScript
designed as scripting language for Web browsers
generates dynamic output in a page
controls events in the page (button clicks, text entered, form submit, ...)
retained syntactic similarity to C++/Java, diff features due to diff design goals
scripting languages --> interpreted by browser, code embedded in HTML
applications are quick & dirty --> variables are dynamic for flexibility,
don't have to declare variables, no type for functions
applications are small --> useful objects provided, rudimentary facility
for defining new classes, no info hiding or inheritance
user security is important, code security isn't --> can't access client
files, can't hide source code
LISP/Scheme
functional programming developed out of AI movement in mid-50's
closer to human reasoning (symbolic, list-oriented, transparent memory mgmt)
LISP (LISt Processing Language) developed by McCarthy at MIT, 1959
based on lambda-calculus of Alonzo Church ==> Turing complete
simple & orthogonal: only 2 kinds of data objects (atoms & lists)
all computation performed by applying functions to inputs
function definitions & function calls also represented as lists
Scheme developed at MIT, mid-70's: clean, simple subset of LISP
static scoping, first-class functions, efficient tail-recursion
syntax
S-expressions: atoms (numbers, characters, strings, booleans, symbols)
lists -- non-contiguous, dynamic, represented as dotted pair
functional expressions: S-expressions that represent function calls
memory management
types associated with values, not variables
all data dynamically allocated, reclaimed via garbage collection
makes extensive use of structure sharing
primitive functions
arithmetic: +, -, *, /, quotient, remainder, max, min, abs, =, <, <=
symbolic: car, cdr, cons, list, list-ref, length, member, reverse, append
predicates: zero?, positive?, odd?, even?, number?, list?, null?, equal?
boolean: and, or, not
higher-order: map, apply
user-defined functions
create nameless function with lambda expression, give name using define
can nest functions, static scoping hides inner functions
control
to evaluate functional expr: evaluate each arg, apply function to values
conditionals: if-expression, cond-expression (both considered special forms)
repetition via recursion: Scheme must perform tail-recursion optimization
structuring data
association list w/ assoc, trees via nested lists
non-functional features
I/O (read, read-char, display, load, ...), sequencing (begin),
destructive assignment (define, set!), environment definition (let)
OOP in Scheme
can define OOP objects as lambda expressions with state & methods