Overview of Topics

Use this as a checklist of topics covered in class

□ Programming languages types

            □ General: Functional, imperative, object-oriented, other (dataflow, visual, ...)

                        □ Purity vs. convenience: E.g. assignment as expression, ternary if

            □ Special-purpose: SQL, process control, graphics, gaming, ...

□ Criteria for judging a good programming language

            □ Semantic fit to problem domain

            □ Chapter 1 criteria

□ History of programming languages

People: 1 John Backus & team, 2 Grace Murray Hopper & team, 3 John McCarthy, 4 John Kemeny & Thomas Kurtz, 5 Nikolas Wirth, 6 Ken Iverson, 7 Ralph Griswold, 8 Ken Thompson & Dennis Ritchie, 9 Bjarne Stroustrup, 10 James Gosling, 11 Larry Wall

Languages: 1 Fortran, 2 Cobol, 3 Lisp, 4 Basic, 5 Algol and Pascal and Modula, 6 APL, 7 Snobol and Icon, 8 C, 9 C++, 10 Java, 11 Perl

□ Compiler theory, general

□ Syntax

            □ Tokens, lexemes

            □ Recognition, generation, derivations

            □ Chomsky Hierarchy of Grammars

□ FSG, FA, and regular expressions; CSG, BNF, EBNF and parse trees; PDA and LBA; Turing Machines

            □ Parsing

                        □ Top down parsers, e.g. recursive descent as an LL parser

                        □ Bottom up (shift-reduce parsers), e.g. LR table parsing

            □ Ambiguous grammars

□ Semantics

            □ Static semantics, e.g. attribute grammars

            □ Dynamic semantics to prove program correctness

                        □ Operational

                        □ Axiomatic

□ Assertions: Preconditions, postconditions, loop invariants, weakest preconditions

                        □ Denotational

                                    □ E.g. short-circuit evaluation

                                    □ E.g. scope of index in a loop

□ Translation

            □ Preprocess, compile, link, load, execute

            □ Interpret

            □ Eager vs. lazy evaluation

□ Learning Perl

□ Learning C++

□ Terms to know

            □ side effects, operator overloading, orthogonality, aliasing, object-based vs. object-oriented

□ Binding times and lifetime

            □ Times: Language definition time, compile time, link time, load time, run time

□ Memory management: garbage collection and memory leakage, dereferencing and dangling pointers; eager vs. lazy heap management

□ Scoping

            □ Dynamic vs. static scoping

            □ Local vs. non-local (misnamed global) scoping

□ Types

            □ Strong vs. weak

            □ Type compatibility: name, structural

            □ Subtyping

            □ Union types (free unions, discriminated unions)

            □ User-defined typing (typedef, objects as types)

            □ Type conversions: explicit, implicit (promotion), coercion

□ Data structures

            □ Persistent data structures

            □ Heap management

                        □ new, malloc; delete, dispose, free

            □ Whole-data structure operations (e.g. APL)

□ Arrays

            □ Implementations

                        □ As objects (Java), hence "jagged" permitted

□ Associative arrays, as hashes (Perl, Javascript, possibly PHP), hence "jagged" permitted

                        □ Scientific arrays, as adjacent memory (Fortran), hence data parallelism is easy

            □ Column-major order (Fortran) vs. row-major order (all other languages)

            □ Slices

            □ Subscript binding (static, fixed stack-dynamic, fixed heap-dynamic, heap dynamic)

□ Variables and constants

            □ Descriptors, esp. string descriptors

            □ r-values vs. l-values

            □ implicit vs. explicit declarations

            □ static vs. stack-dynamic vs. implicit heap-dynamic vs. explicit heap-dynamic

            □ Named constants

            □ Anonymous variables

□ Control structures

            □ break labelName, continue

            □ assertions (§14.4.7, but anticipated by Konrad Zuse in 1945)

□ Functional abstraction: Subprograms

            □ Semantic models of parameter passing methods: in, out, in-out (Chapter 9)

                        □ Pass by value, by result, by value-result, by reference, by name

            □ Implementation of the above (Chap. 10): activation records, displays, deep vs. shallow access

            □ Subprograms as parameters

            □ Generics

□ Data abstraction

            □ Records (struct)

            □ Enumerations

            □ Assemblies, namespaces, packages.

□ Object-based programming: C++, Java, Ada95, C#, JavaScript

            □ Paper by Peter Wegner, 1989, contrasting object-based with object-oriented programming.

□ Polymorphism, virtual methods, single inheritance vs. multiple inheritance, private vs. public vs. package vs. protected scope, friend functions in C++, static binding (for final, private, or static methods).

            □ Which subclasses are subtypes? (§§ 12.3.2 and 12.5.2)

□ Functional programming

            □ Examples: Scheme, ML, others (Derive, Haskell)

            □ Functions as first class entities; defining mapcar (§15.5.11.2)

            □ The read-eval-print loop

□ Constraint programming: Logic programming languages

            □ Predicate calculus extends propositional calculus

            □ Resolution theorem proving for Horn clauses, via unification

            □ Declarative vs. procedural (with tracing) semantics

            □ Prolog as an example of a logic programming language

            □ Pattern matching with backtracking as another model of parameter passing

            □ The negation problem and the closed world assumption

            □ Applications of Prolog: database access, expert systems, natural language processing

□ Concurrency (parallelism)

            □ Event handling, exceptions, and errors

            □ Multthreading vs. coroutines: resume

            □ Dijkstra's guarded statements: if, while

            □ Physical vs. logical concurrency

□ Journal theme issue on concurrency: “Make way for multiprocessors,” ACM Queue, Vol. 3, No. 7, Sept. 2005.

[Much omitted here, some of which is a part of CSC 416 Operating Systems, and other parts of which make for good projects.]