Extra stuff (Programming Languages)
From Spivey's Corner
There's only time for so much stuff in a lecture course, and there is always more that can be said. Here are notes on several topics that will be covered in The Book.
Contents |
Background
Some more gentle starting material:
[000] Just enough Haskell: curried functions, case expressions, lambda expressions, the type (), local definitions introduced by let or where, algebraic types, type synonyms, user-defined infix operators.
Haskell features we won't use. Formatting rules for Haskell code. The abstract data type of finite mappings.
[00] Defunctionalization (d17n) as a change of representation and as a whole-program transformation.
[0] Simple expressions with local definitions: abstract syntax, recursive evaluator, environments.
Infrastructure
The infrastructure for definitional interpreters, including libraries for building lexers and parsers.
Implementation of mappings
Implementation of the ADT of mappings, used for environments, memories and substitutions in our interpreters. Favourite data structures for this would be randomised binary search trees (but maybe not in Haskell, unless we make the random number a hash of the key – a sweet idea), or 2-3 trees – see my old Compilers notes.
Abstract machines
A development of an abstract machine (like Henderson's version of the SECD machine) for Fun.
Implementations of Fun
A meta-circular interpreter – Fun in Fun. Source code: Gzipped tar format, Windows ZIP format.
Other implementations exist, written in OCaml and Java. The GeomLab dialect has an implementation that uses postfix code and a bootstrapped compiler written in Fun.
Prolegomena
A chapter outlining the foundation for reasoning about Haskell programs generally, and definitional interpreters specifically.
These Prolegomena are destined for the use, not of pupils, but of future teachers, and even the latter should not expect that they will be serviceable for the systematic exposition of a ready-made science, but merely for the discovery of the science itself.
[Immanuel Kant, Prolegomena to Any Future Metaphysics, 1783, tr. Paul Carus]
Styles of semantics
Denotational, Operational, Axiomatic: styles of semantics.
Bits and pieces
| Programming Languages |
| Syllabus |
| Outline |
| Problems |
| Labs |
| Software |
| FAQ |
