D.5 How to Use Camille in a Programming Languages Course

D.5.1 Module 0: Front End (Scanner and Parser)

The first place to start is with the front end of the interpreter, which contains the scanner (i.e., lexical analyzer) and parser (i.e., syntactic analyzer). The scanner and parser for Camille were developed using Python Lex-Yacc (PLY v3.11)—a scanner/parser generator for Python—and have been tested in Python 3.8.5. For the details of PLY, see http://www.dabeaz.com/ply/. The use of a scanner/parser generator facilitates an incremental development approach, which leads to a malleable interpreter/language. Thus, the following components can be given directly to students as is:

D.5.2 Chapter 10 Module: Introduction (Local Binding and Conditionals)

Given the parser, students typically begin by implementing only primitive operations, with the exception of array manipulations (Figure D.1; 1.x_INTRODUCTION_Chapter10_Conditionals/simpleinterpreter). Then, students develop an evaluate_expr function that accepts an expression and an environment as argument, evaluates the passed expression in the passed environment, and returns the result. This function, which is at the heart of any interpreter, constitutes a large conditional structure based on the type of expression passed (e.g., a variable reference or function definition).

Adding a support for a new concept or feature to the language typically involves adding a new grammar rule (in camilleparse.py)and/or primitive (in camillelib.py), adding a new field to the abstract-syntax representation of an expression (in camilleinterpreter.py), and adding a new case to the evaluate_expr function (in camilleinterpreter.py)—a theme running through Chapter 3 of Essentials of Programming Languages (Friedman, Wand, and Haynes 2001). All of the explorable concepts in the purview of interpreter building for this language are shown in Table D.1. Note that not all implementation options are available for use with the nameless environment.

Table D.1 Configuration Options in Camille (Perugini and Watkin 2018)

Therefore, students start by adding support for conditional evaluation and local binding. Support for local binding requires a lookup environment, which leads to the possibility of testing a variety of representations for that environment, as long as it adheres to the well-defined interface used by evaluate_expr. From there, students add support for non-recursive functions, which raises the issue of how to represent a function and there are a host of options from which to choose.

In what follows, each directory corresponds to the different (progressive) version of the interpreter:

Each individual interpreter directory contains its own README.md describing the highlights of the particular version of the interpreter in that the directory.

D.5.3 Configuring the Language

Table D.1 enumerates the configuration options available in Camille for aspects of the design of the interpreter (e.g., choice of representation of referencing environment) as well as for the semantics of implemented concepts (e.g., choice of parameter-passing mechanism). As we vary the latter, we get a different version of the language (Table D.2).

Table D.2 Design Choices and Implemented Concepts in Progressive Versions of Camille. The symbol ⇓ indicates that the concept is supported through its implementation in the defining language (here, Python). The Python keyword included in each cell, where applicable, indicates which Python construct is used to implement the feature in Camille. The symbol ↑ indicates that the concept is implemented manually. The Camille keyword included in each cell, where applicable, indicates the syntactic construct through which the concept is operationalized. (Key: ASR = abstract-syntax representation; CLS = closure; and LOLR = list-of-list representation. Cells in boldface font highlight the enhancements across the versions.) Reproduced from Perugini, S., and J. L.Watkin. 2018. “ChAmElEoN: A Customizable Language for Teaching Programming Languages.” Journal of Computing Sciences in Colleges 34(1): 44–51.

The configuration file (i.e., camilleconfig.py) allows the user to switch between different representations of closure (e.g., Camille closure, abstract syntax, or Python closure) and the environment structure (e.g., closure, list of lists, or abstract syntax), as well as modify the verbosity of output from the interpreter. These parameters can be adjusted by setting __closure_switch__, __env_switch__, and __debug_mode__, respectively, to the appropriate value. The detailed_debug flag is intended to be used to debug the interpreter, while the simple_debug flag is intended to be used in normal operation (i.e., running and debugging Camille programs). [The nameless environments are available for use with neither the interpreter supporting dynamic scoping nor any of the interpreters in Chapter 12 (i.e., 3.x_ADVANCED_Chapter12_ParameterPassing and 4.x_IMPERATIVE_Chapter12_ParameterPassing). Furthermore, not all environment representations are available with all implementation options. For instance, all of the interpreters in Chapter 12 use exclusively the named ASR environment.]

At this point, students can also explore implementing dynamic scoping as an alternative to the default static scoping. This amounts to little more than storing the calling environment, rather than the lexically enclosing environment, in the representation of the function. This is configured through the configuration file identified previously.

D.5.4 Chapter 11 Module: Intermediate (Functions and Closures)

Next, students implement recursive functions, which require a modified environment. At this point, students have implemented Camille version 2.1—a language supporting only (pure) functional programming—and explored the use of multiple configuration options for both aspects of the design of the interpreter and the semantics of implemented concepts (Table D.2).

D.5.5 Chapter 12 Modules: Advanced (Parameter Passing, Including Lazy Evaluation) and Imperative (Statements and Sequential Evaluation)

Next, students start slowly to morph Camille, through its interpreter, into a language with imperative programming features by adding provisions for side effect (e.g., through variable assignment). Variable assignment requires a modification of the representation of the environment. Now, the environment must store references to expressed values, rather than the expressed values themselves. This raises the issue of implicit versus explicit dereferencing, and naturally leads to exploring a variety of parameter-passing mechanisms (e.g., pass-by-reference or pass-by-name/lazy evaluation). Finally, students close the loop on the imperative approach by eliminating the need to use recursion for repetition by instrumenting the language, through its interpreter, to support sequential execution of statements. This involves adding support for statement blocks, while loops, and I/O operations. Since this module involves modifications to the environment, we exclusively use the named ASR environment in this module to simplify matters.