The course is built around an investigation of what programming languages are, and the notion of programs as artefacts. Two key aspects of the study of programming languages are their semantics, and their syntax.

We will survey some of the fundamental principles of the semantics and computational behaviour of programs, including the lambda calculus, types and fixed-points. Rigorous proofs of properties of programs, such as are needed for safety-critical software, or for program transformations such as are carried out by optimising compilers, require a formal description of the 'meaning' and behaviour of programs. We will study two of the dominant approaches: denotational semantics and opertional semantics. In each case, standard proof techniques will be developed and applied.

The syntax of programming languages is routinely defined by well-understood means, in terms of formal grammars and their relation to certain classes of automata. We will investigate the algorithms underlying standard automata-bsed compiler generators and make practical use of them to construct simle translators.

Students who succeed in all aspects of this course will be able to:

• manipulate and generate lambda-terms, extending a system such as Church numerals; check and assign types to lambda terms.
• solve simple recursive equations by determining the limit of the Kleene fixpoint construction.
• design and extend operational and denotational definitions for basic programming language constructs.
• prove properties of programs by various formal means, including structural and fixpoint induction.
• demonstrate correspondences between grammars, languages and automata.
• use standard parser and lexer generator tools to construct and implement translations such as a very simple compiler.

Assignments (30%); Final Exam (70%)

Thirty one-hour lectures, three one-hour tutorials and seven two-hour laboratory sessions.

COMP2300 and COMP2600

Course offered in Semester 2 in alternate odd-numbered years.