10.2 Checkpoint

Thus far in this course of study of programming languages, we have explored:

• (Chapter 2) Language definition methods (i.e., grammars). We have also used these methods as a model to define data structures and implement functions that access them.

• (Chapter 5) Recursive, functional programming in λ-calculus and Scheme (and ML and Haskell in online Appendices B and C, respectively).

• (Chapter 6) Binding (as a general programming language concept) and (static and dynamic) scoping.

• (Chapter 8) Partial function application, currying, and higher-order functions as a way to create powerful and reusable programming abstractions.

• (Chapter 9) Data types and type systems:

  • definition (with class in Python; with define-datatype in Racket Scheme; with type and datatype in ML; and with type and data in Haskell)

  • pattern matching and pattern-directed invocation (with cases in Scheme, and built into ML and Haskell)

• (Chapter 9) Data abstraction and abstract data types:

  • the concepts of interface, implementation, and application

  • multiple representations (list, abstract syntax, and closure) for defining an implementation for organizing data structures in an interpreter, especially an environment

We now use these fundamentals to build (data-driven, environment-passing) interpreters, in the style of occurs-free? from Chapter 6, and concrete2abstract and abstract2concrete from Chapter 9 (Section 9.6 and Programming Exercise 9.6.2). We progressively add language concepts and features, including conditional evaluation, local binding, (recursive) functions, a variety of parameter-passing mechanisms, statements, and other concepts as we move through Chapters 10–12.

Camille is a programming language inspired by Friedman, Wand, and Haynes (2001), which is intended for learning the concepts and implementation of computer languages through the development of a series of interpreters for it written in Python (Perugini and Watkin 2018). In particular, in Chapters 10–12 we implement a variety of an environment-passing interpreters for Camille—in the tradition of Friedman, Wand, and Haynes (2001)—in Python.

There are multiple benefits of incrementally implementing language interpreters. First, we are confronted with one of the most fundamental truths of computing: “the interpreter for a computer language is just another program” (Friedman, Wand, and Haynes 2001, Foreword, p. vii, Hal Abelson). Second, once a language interpreter is established as just another program, we realize quickly that implementing a new concept, construct, or feature in a computer language involves adding code at particular points in that program. Third, we learn the causal relationship between a language and its interpreter. In other words, we realize that an interpreter for a language explicitly defines the semantics of the language that it interprets. The consequences of this realization are compelling: We can be mystified by the drastic changes we can effect in the semantics of implemented language by changing only a few lines of code in the interpreter—sometimes as little as one line (e.g., using dynamic scoping rather than static scoping, or using lazy evaluation as opposed to eager evaluation).

We use Python as the implementation language in the construction of these interpreters. Thus, an understanding of Python is requisite for the construction of interpreters in Python in Chapters 10–12. We refer readers to Appendix A for an introduction to the Python programming language.

Online Appendix D is a guide to getting started with Camille and includes details of its syntax and semantics, how to acquire access to the Camille Git repository necessary for using Camille, and the pedagogical approach to using the language. The Camille Git repository is available at https://bitbucket.org/camilleinterpreter/camille-interpreter-in-python-release/src/master/. Its structure and contents are described in online Appendix D and at https://bitbucket.org/camilleinterpreter/camille-interpreter-in-python-release/src/master/PAPER/paper.md. Online Appendix E provides the individual grammars for the progressive versions of Camille in one central location.