CSC 533: Organization of Programming Languages
Spring 2005
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: readability, writability, reliability, ...
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, 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
parameters: 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 specifies dynamic binding (implemented using pointer)
advanced OOP
generic types via templates, multiple inheritance (avoid ambiguities with ::)
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, Random, ArrayList, Stack, HashMap
Java execution models: applications vs. applets
primitive vs. reference types
primitive: stack-dynamic (type bound statically, address bound dynamically)
passed by-value, can generalize with wrapper classes
reference: heap-dynamic, must allocate using new (inherits from Object)
passed by-value, but similar to by-reference (since a pointer)
general-purpose, (pure) object-oriented programming language
similar to C++, can inherit data fields/methods, override, 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, abstract classes, interfaces
JavaScript
retained syntactic similarity to C++/Java, diff features due to diff design goals
interpreted (code embedded in HTML), dynamic variables, typeless functions
useful objects provided, rudimentary facility for defining new classes
user security is important, code security isn't
LISP/Scheme
functional programming (LISP) developed out of AI movement in mid-50's
closer to human reasoning (symbolic, list-oriented, transparent memory mgmt)
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 new function using define, can nest functions using static scoping
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 functions with state & methods