At first it might seem mysterious how a programming language could be implemented. But, after this chapter, hopefully some of that mystery has been revealed. Implementation of a programming language is just a matter of the same studious application of syntax, dynamic semantics, and static semantics that we’ve studied throughout this book. It also relies heavily on CS theory of the kind studied in discrete mathematics or theory of computation courses.
9.7.1. Terms and Concepts#
abstract syntax tree
Backus-Naur Form (BNF)
call by name
call by value
Hindley–Milner (HM) type inference algorithm
preliminary type variable
weak type variable
9.7.2. Further Reading#
Types and Programming Languages by Benjamin C. Pierce, chapters 1-14, 22.
Modern Compiler Implementation (in Java or ML) by Andrew W. Appel, chapters 1-5.
Automata and Computability by Dexter C. Kozen, chapters 1-27.
Real World OCaml has a chapter on the OCaml frontend.
This webpage documents some of the internals of the OCaml type checker and inferencer.
Our treatment of type inference is based on Pierce.