Proposed Knowledge Units for Programming Languages
for Curriculum 2001

The Programming Language Knowledge Area Focus Group was formed less than two weeks before this report was due, so the report presented here is preliminary. We have had extensive discussion of the topics included here, but wish to present our ideas to a larger group of programming languages experts to get feedback on our ideas. We began with the knowledge units of CC '91, but made extensive changes to update the material and change the balance of material.

Contributing members of this knowledge area focus group are Kim Bruce (Williams College), Benjamin Goldberg (NYU), Chris Haynes (Indiana U.), Gary Leavens (Iowa State U.), and John Mitchell (Stanford U.).

The main changes of this report from CC '91 are

1. Shifting logic programming from core to an intermediate or advanced topic (we have not yet included a KU for this, however, as we have only focussed on those topics having core material).

2. Significantly cutting back the material on automata, regular expressions, and context-free grammars to the material most needed for programming languages. We anticipate that some of the material omitted here will be picked up in the algorithms [AL] or foundations [FO] KU's.

3. Increasing the attention to modules and information hiding.

4. Including more detail in most knowledge units, esp. those involving object-oriented languages.

5. Rearranging and reordering KU's to increase their coherence.

The changes we have made resulted in a decrease of roughly 11 hours from the KU's specified in CC '91.

We have included mainly core and intermediate level topics in the KU's. A few advanced topics occur, but we made no attempt to be complete in these (for instance we do not yet have the intermediate / advanced KU's necessary to support a compiler course). We did label the sections of each KU that belong in each category. The following is a short listing of the KU topics:

The numbers after each KU titles are the number of hours devoted to the KU. If there is only a single number then all topics are at the core level. If there are multiple numbers then the first represents core hours, the second represents intermediate, and the last (if present) represents advanced hours. We were inconsistent in listing intermediate and advanced topics (and in fact weeded out most advanced topics). Most remaining are there because they were felt by at least one member of the committee to be a candidate for moving to a stronger requirement.

We included justification for most of the KU's, but because of a lack of time, were not able to include them for all KU's. We will add these later. We also hope to have the benefit of comments from a wider group by the time we prepare the next version of this report.

The three processes of theory, abstraction, and design are well represented here. PL3 (formal languages) and PL9 (formal semantics) provide the strongest representation of theory in the curriculum, though aspects of theory also show up in discussions of type checking in PL5. Abstraction is very well represented in these KU's as programming languages provide abstractions for controlling computations and the representation of information. PL2 (Virtual machines), PL5 (types), PL6 (Control of Execution), PL7 (Declarations and Modules), as well as sections of PL10 (Functional Paradigm), PL11 (Object-oriented Paradigm) all present a heavy dose of abstraction. Design shows up in examination of trade-offs in choosing language constructs as well as PL4 (Language Translation Systems), PL8 (Run-time Storage Management), and PL12 (Distributed and Parallel Programming Constructs). Design also shows up in discussions of various programming language paradigms.

The knowledge units presented here do not have any explicit requirements for mathematics and physical sciences, though we expect that discrete mathematics will be important for the prerequisites of many topics. We have not yet prepared model courses with these KU's. We have not yet completely fixed the lists of prerequisites and requisites, so many will be revised later.

As a last thought before presenting the programming language knowledge units: We note that examination of the use of programming languages over the last 30 to 40 years has made it absolutely clear that trends in programming language usage change dramatically over time. Mainstream languages have moved from FORTRAN and COBOL in the 60's to PL/I, Pascal and C in the '70's (and beyond for the last two) to Smalltalk and C++ in the '80's (and beyond) to Java in the '90's - and that is ignoring large programming subcultures using languages like LISP/Scheme, APL, PROLOG, ML, Visual Basic, Perl, etc. Clearly no programmer can expect to use the same language or even the same language family/paradigm during her career. An understanding of the core concepts of programming languages and different programming language paradigms will better enable programmers to keep up with language changes that will occur over their careers.

A brief historical survey of major early developments in programming languages, beginning with the evolution of procedural high-level languages. An overview of contemporary programming paradigms and their related languages, including procedural, object-oriented, functional, logic, and parallel programming. Language families and trends.

Core Lecture Topics: (One and a half hours minimum)

1. Early languages; FORTRAN, ALGOL, COBOL, LISP, BASIC.
2. The evolution of procedural languages (the ALGOL 60, PL/1, ALGOL 68, Pascal, C, Euclid, Modula-2, Ada83, and Ada95 chain of development)
3. Imperative, algorithmic
1. Procedural, structured paradigm and languages (Pascal, C, Modula-2, and Ada83)
2. Object-oriented paradigm and languages: (Simula, Smalltalk, C++, Java, Eiffel, Modula-3, Oberon, CLOS, Dylan)
4. Mostly-functional, algorithmic, higher-order paradigm and higher-order languages with eager evaluation (Common Lisp, Scheme, ML, APL)
5. Purely-functional, algorithmic paradigm: (Miranda, Haskell, Clean),
6. Declarative (non-algorithmic) Languages: Logic programming languages (e.g., Prolog)

Intermediate Lecture Topics (half hour minimum)

1. Parallel programming paradigms: (CSP, Occam, Turing Plus, SR, Emerald, Java threads, Linda, Ada, Orca)
2. Scripting paradigm (UNIX Shell, Perl, Tcl, Python, Visual BASIC)

Prerequisites: PF

Actual vs. virtual computers. The understanding of programming languages in terms of the corresponding virtual machines (regardless of the actual architecture on which they run). Language translation understood conceptually as an implementation on a virtual machine, followed by a sequence of translations to simpler core languages through a hierarchy of virtual computers.

1. What is a virtual machine? (examples: Java Virtual Machine, lambda calculus, etc.)
2. Hierarchy of virtual machines presented to the user through the program, the translator, the operating system, etc.

Prerequisites:

Application of regular expressions and context free languages as formal descriptions of language syntax and their use in programming language analysis.

1. Overview of regular expressions, context-free grammars (and syntax diagrams), and their use in specifying and implementing programming languages.
2. Context-free grammars and parse-trees, ambiguous grammars.

1. Applications of regular expressions in lexical analysis.

Prerequisites: AL5

An overview of the language translation process, encompassing the range from compilers to interpreters. The focus is on the architecture of compilers.

1. Comparison of pure interpreters vs. compilers; operation and use
2. Architecture of a compiler (lexical analysis phase, parsing, symbol table, code generation, optimization)

1. Parsing: concrete and abstract syntax, abstract syntax trees
2. Code generation by tree walking
3. Optimization techniques

1. Application of regular expressions in table-driven lexical scanners
2. Application of cfg's in table-driven and recursive descent parsing

Suggested Laboratories:

1. (open) develop a simple parser (e.g., recursive descent) for arithmetic expression that returns an expression tree.
2. (closed) Use a compiler-generator tool to specify and run a finite state automaton that will accept a small part of the lexical grammar of some programming language.
3. Design and exercise a table-driven parser for a simple context-free language.

Prerequisites: AL6, AR3, PL2, PL3

Models and descriptions of data. Elementary and structured data types. Type checking and type inference. Polymorphism. User-defined and abstract data types.

1. Data type as set of values with set of operations
1. Elementary data types: Booleans, characters, integers, floating-point numbers.
2. Structured data types
1. product types: arrays, strings, records (structs in C/C++)
2. coproduct types: unions, variant records,
3. algebraic types (as in ML, Miranda, Haskell)
4. recursive types: representation by pointers or references
5. arrow types: function and procedure types
6. parameterized types
2. Type checking
1. Goals
1. detect errors; preserve intended meaning of program operations
2. representation independence
2. Static vs. Dynamic type systems
1. dynamic strong type checking in Smalltalk and Lisp/Scheme
2. tradeoff between flexibility and catching errors early
3. Basic type-checking (without polymorphism)
1. explicit type checking with explicit type declarations
2. type inference
3. User-defined types
1. type abbreviations (like typedef in C/C++, type in ML)
2. ADT's and preview of encapsulation via modules
3. type equality: structural type equivalence (as in ML) vs. name equivalence (as in Java)
4. Parametric polymorphism (Generics)
1. intuition and applications: polymorphic operations on lists, other data structures
2. comparison of implicit (ML, Scheme) and explicit (Ada generics, C++ templates) polymorphism
3. comparison with ad hoc polymorphism (typecase, instanceof in Java), static overloading (as in Ada83, Haskell), and dispatch in OO languages (and multiple dispatch in CLOS, Cecil)
5. Subtype polymorphism
1. structural subtyping rules for records, variants, functions, objects.
2. type casts (downcast vs. upcast and safety)

1. Type-checking algorithms
1. explicit algorithm & implicit algorithm w/ parametric polymorphism (Hindley/Milner, as in ML)
2. algorithm for checking subtyping in an explicit language

Suggested Laboratories:

1. (closed) Find a seeded type error in a dynamically-typed language.
2. (open) Develop the same program (e.g., an interpreter) in a dynamically typed language (e.g., Scheme) and in a statically typed language (e.g., ML). Compare the development efforts and the resulting code.
3. (open) Implement some generic collection ADT (e.g., set[T], bag[T], etc.) using a recursive representation (e.g., linked lists). Student gains experience with language support for structured types, recursive types, ADT's, specifications and polymorphism.

Prerequisites: PF2, PF3, PF5, PL2

Flow of control associated with evaluating expressions and executing statements. User-defined expressions and statements.

1. Expressions, order of evaluation of sub-expressions
1. Reasons for underspecifying evaluation order: reordering can improve efficiency, allow parallelism
2. side effects and possible non-termination prevent reordering
3. conditional expressions: some subexpressions are not evaluated; strictness
4. functions as abstraction of expressions
2. Statements
1. assignment, sequencing (S1;S2), function/procedure calls, goto
2. conditional and case/switch, loops (while-do, do-until), break and continue
3. procedures as abstractions of statements
4. iterators as abstraction of loop structure over data structures
3. Exceptions and exception handling
1. try-statements in Ada and Java
2. termination model vs. resumption model

1. parallel composition (S1||S2)
2. Functions delay evaluation
1. closures: lambda in Scheme, fun in ML, blocks in Smalltalk
2. lazy languages and user-defined control constructs (contrast Haskell and Smalltalk)

Prerequisites: PL2

Methods of sharing and restricting access to information in programming languages.

1. Declarations
1. binding and allocation: aliases, constants vs. variables
2. visibility of declarations, static vs. dynamic scope
3. lifetimes (impact of garbage collection. and closures)
2. Parameterization mechanisms;
1. parameter-passing: reference, copy (value, result, and value-result), name, sharing (as in Java) and correspondence to declaration forms.
2. type parameterization: generics or templates (as in Ada, C++), implicit polymorphism (as in ML, Haskell, and Scheme) [overlap w/PL5.4 to be resolved]
3. Mechanisms for sharing and restricting visibility of declarations (blocks in ALGOL-like languages, modules in Ada and ML, classes and subclasses in OO languages, packages in Java)
4. Use of modules to enforce information hiding for data abstractions and code reuse in libraries
1. information hiding and abstraction boundaries
2. separation of interface and implementation; existential type binding
3. aliasing and how it may violate information hiding
4. separate compilation and linking (interface vs. implementation)
5. information hiding vs. inheritance (protected in C++ and Java)

Suggested Laboratories:

1. (closed) Exercise the same program in languages with dynamic and static scoping, and/or with different parameter mechanisms. Explain the different effects.
2. (open) Write a large program, in teams, that uses several modules.

Prerequisites: PL2, PL5

Allocation, recovery, and reuse of storage during program execution.

1. Static allocation (as in Fortran or C static)
2. Stack-based allocation and its relationship with recursion
3. Heap-based allocation
4. Garbage collection - include benefits and problems of each technique
1. Explicit allocation/deallocation (as in C, C++)
2. Reference counting
3. Overview of garbage collection algorithms (mark and sweep and/or copying)

Prerequisites: PF4, PF5, PL2

Use of formal and informal models to describe programming language semantics.

1. Informal semantics (e.g., the ALGOL 60 or Scheme reports)
2. Formal semantics
1. kinds of formal semantics: operational (natural, SOS), axiomatic (Hoare logics), denotational (Domains, functions)
2. formal operational semantics of some small language (like PCF ...).
3. Benefits of formal semantics

1. Denotational Semantics.
1. Domains, fixed points
2. Denotational semantics of some language features, comparison to their operational semantics
2. Axiomatic Semantics
1. Hoare triples
2. Weakest pre-conditions

Suggested Laboratories:

1. (open) Given a semantics of a simple language (e.g., PCF), write an interpreter which implements the semantics.

Prerequisites: PL2, PL3, PL6

The functional programming paradigm. Advantages and disadvantages. Recursion over recursive data structures. Functions as data. Amortized complexity.

1. Overview and motivation
1. problems with reasoning about assignment in presence of aliasing vs. referential transparency when there is no mutation
2. need for copying when have mutation vs. sharing when no mutation
2. Recursion over lists, natural numbers, trees, and generalization to other recursively-defined data (using some language like Scheme, ML, Miranda, or Haskell)
3. Pragmatics: debugging by divide and conquer; persistency of data structures (the old version is still available when the new version is produced).
4. Amortized efficiency for functional data structures (e.g., amortized queues) and comparison to imperative data structures
5. Closures, and uses of functions as data (e.g., infinite sets, streams)

Suggested Laboratories:

1. (open) Write a denotational or operational-style interpreter for a small programming language. Students may also modify such an interpreter to experiment with choices in parameter-passing and scoping.
2. (open) See the programming exercises in Abelson and Sussman's book...

Prerequisites: PF4, PF5, PL2

The Object-Oriented (OO) paradigm. Advantages and disadvantages. Types, classes and objects; subtyping and inheritance. Type checking.

1. Overview and motivation
1. problems with change in stepwise refinement method
2. difficulty of code reuse
3. evolution of programs and the need to reflect incremental changes in the program structure
4. terms: ADT, type, class, object (instance), method, object's instance protocol (method interface), self/this, super
2. Mechanisms for defining classes and instances in some OO language (e.g., Smalltalk, Java, C++, Eiffel) and for defining interfaces in Java.
3. Object creation and initialization.
4. Inheritance and dynamic dispatch
1. single vs. multiple dispatch (as in CLOS, Dylan)
2. dynamic dispatch of methods, method overriding, and method inheritance (examples of method ping-ponging)
5. Sketch of run-time representation of objects and method tables, how it enables method dispatch.
6. Distinction between subtyping and inheritance

1. Advanced OO type problems
1. Need for sophisticated parametric polymorphism (e.g., F-bounded or equivalent)
2. Problems with binary methods

Suggested Laboratories:

1. (open) Write an interpreter for a small programming language, or a Turing machine, in an OO language, using the interpreter or visitor pattern.

Prerequisites: PF6, PL2, PL5.

Description of alternative realizations of parallel and distributed programming constructs.