This project contains implementation of languages introduced in Types and Programming Languages in Rust.

• Chapter 4: Arithmetic Expressions
• Chapter 7: Untyped Lambda Calculus
• Chapter 10: Simple Types
• Chapter 11: Simple Extensions
• Chapter 17: Subtyping

To be added...

This project is just for personal study, so user-friendliness is not in consideration. Since lexing and parsing are not the main interests of this book, only terms and evaluation functions for them are implemented, while lexers and parsers are not. This means the only way to construct the AST is to code it by hand. Reading from an external text file is not supported.

Each module (except util) in this crate contains a language. Terms are defined as enum Term, and the evaluation rules for them are defined as fn eval(t: &Rc<Term>) -> Rc<Term>.

Each module contains a test function which demonstrates the construction of AST of this languages, which could serve as a reference.

This project implement interpreters that are usually done with pure functional languages, like OCaml or Haskell. The implementation details on how to map these features to Rust are discussed in this section.

Typically, functional languages support garbage collection to prevent programmers from caring about memory management issues. However, this is not the case for Rust, which enforces strict disciplines on the lifetime of objects. Rc, the reference counting facility provided by the standard library is used throughout the project. Parent AST nodes hold Rc<Term>s to children, and evaluation function eval receives &Rc<Term> as parameter and returns Rc as result. Forwarding existing Terms and creating new instances of Terms all work without pain. An abbreviated rc is provided in util to save typing the longer Rc::new.

It is fortunate that Rust supports algebraic data type enum and match expression, which are commonly seen in functional languages. This makes pattern matching, a commonly seen feature in language interpreters, convenient. When matching enums, their associated values can be extracted to perform further evaluation. However, as Rc is used as pointer to child nodes, nested enum matching is not possible, so nested match expressions for associated values are used.