_images/PL.jpg

Welcome!

Welcome to Foundations of Programming Languages by Kent D. Lee. This text, available from Springer, covers material on the design and implementation of programming languages, focusing on the three paradigms of prorgramming: imperative, functional, and logic programming.

Concepts covered in the text include syntax specification, lexical analysis, parsing, abstract syntax, compilation, disassembly, interpretation, functional programming, logic programming, type inference, and type inference rules. The text covers several programming languages including assembly language programming, C++, Standard ML, and Prolog.

This text uses and extends the CoCo Virtual Machine. CoCo is based on the Python Virtual Machine version 3.2. CoCo, and its Python disassember, were written to illustrate assembly language programming on a virtual machine. The text both uses CoCo so students can learn about assembly language programming, and extends CoCo so students can learn about virtual machine implementations. The CoCo website describes the CoCo virtual machine and the Github website http://github.com/kentdlee/CoCo provides the source code for CoCo.

In addition, this text uses CoCo as a target language for implementing a compiler of Standard ML. The code for this project is available on Github at http://github.com/kentdlee/MLComp. The text extends the MLComp compiler to compile a robust subset of Standard ML.

The final chapter of this text covers type inference in Standard ML and provides the description and partial implementation of the Standard ML type inference system written in Prolog. This code is included in the MLComp Github project. The text extends the type checker to cover a more complete subset of the language.

Solutions to CoCo and MLComp can be provided to instructors of qualified universities or colleges. These solutions cover chapters 4, 6, and 8 of the text. In addition, solutions to exercises from chapters 1, 2, 3, 5 and 7 can be provided to teachers upon request. Teachers must provide proof that they are teaching at a university or college.

This website provides access to figures and example code from the text as well as practice problems, review questions, and exercises.

Errata

Chapter 3

  • Section 3.6 - Unfortunately, all the line numbers are wrong in this section for figure 3.7. Please refer to this version of the figure to find the correct line numbers.

Chapter 8

  • The test28.sml program helped me determine there was a slight error in the function application type inference rule and two declaration rules. Here are the correct type inference rules. They are also corrected in the chapter 8 material of this website.

ValDec

\frac{pat:\alpha\Rightarrow\varepsilon_{pat},~~\varepsilon\vdash e:close(\alpha)}{\varepsilon\vdash val~pat=e\Rightarrow\varepsilon_{pat}}

ValRecDec

\frac{[id:\alpha]\oplus\varepsilon\vdash e:\alpha}{\varepsilon\vdash val~rec~id=e\Rightarrow[id:close(\alpha)]}

FunApp

\frac{\varepsilon\vdash e_1 : \alpha\rightarrow\beta, ~~ \alpha'\rightarrow\beta':inst(\alpha\rightarrow\beta),~~ \varepsilon\vdash e_2 : \alpha_{e2}, ~~ \alpha' : inst(\alpha_{e2})}
     {\varepsilon\vdash e_1 e_2 : \beta'}

  • Correspondingly, figure 8.11 is also incorrect since the FunApp type inference rule changed. It is corrected and appears correct in chapter 8 of this website.

Contents