Project 1: Untyped arithmetic expressions

Due: 09/09 at 11:59pm
Points: 30

A good way to be sure that you understand the semantics of a programming language is to implement it! We’ll write an interpreter for NB, the simple language of untyped arithmetic expressions from TAPL Chapter 3.

nb> if iszero (pred (succ 0)) then true else false
true

0. Getting started

Visit this GitHub Classroom link to create a Git repository for you. Clone the repository to the computer you plan to work on.

The repository contains the following files (among others):

solution/
  nb.darwin   Reference implementation (MacOS)
  nb.linux    Reference implementation (Linux)
sample/
  syntax.py   Python module for parsing and formatting terms
  id.py       Example read-eval-print loop
  syntax.scm  Same, for Scheme
  id.scm
  syntax.ml   Same, for OCaml
  id.ml
test/
  test.sh     Test script
  nb.input    Test cases
submit/       Please place your code here

Try running the reference implementation and have a look at the test cases to see how it works.

1. Syntax

Grammar

The syntax of NB is as in TAPL:

t ::= true
      false
      if t then t else t
      0
      succ t
      pred t
      iszero t

Parser

Since the focus of this class is on semantics, not syntax, we provide code for parsing. If you want to use a language not listed here, contact the instructor and we will try to provide code in your language.

Note that the provided parsers handle additional syntax that is not shown above, but will be introduced in later projects.

Python 3: syntax.py

syntax.parse_term(s) converts string s to an abstract syntax tree (AST) made out of lists and strings. For example, if the input string is s = "if iszero (pred (succ 0)) then true else false", then
```
syntax.parse_term(s) = ["if", ["iszero", ["pred", ["succ", "zero"]]], "true", "false"]
```
syntax.format_term(t) converts AST t to a string:
```
syntax.format_term(syntax.parse_term(s)) = s
```
syntax.read_lines(prompt) implements a simple read-eval-print loop (REPL), returning a generator over lines of input. See id.py for example usage.

Scheme: syntax.scm

(parse-term s) converts string s to an AST, made of lists and symbols:
```
(parse-term s) = (if (iszero (pred (succ zero))) true false)
```
(format-term t) converts AST t to a string.
(read-lines prompt f) implements a simple REPL, calling function f on each line; see id.scm for example usage.

OCaml: syntax.ml

Syntax.parse_term s converts string s to an AST:

Syntax.parse_term s = If (IsZero (Pred (Succ Zero)), True, False)

Syntax.format_term t converts AST t to a string.
Syntax.read_lines prompt f implements a simple REPL, calling function f on each line; see id.ml for example usage.

2. Semantics

Write a function named eval_term (or something similar) that takes a term and returns its value, if it exists; otherwise, it raises an exception with an appropriate error message.

You can base it on either the small-step semantics in Figures 3-1 and 3-2 (pages 34 and 41) or the big-step semantics in Exercise 3.5.17 (page 43) and the notes. (I recommend the big-step semantics.)

3. Read-eval-print loop

Your interpreter should be named submit/nb. It should read lines from stdin, each containing exactly one term. For each term, it should evaluate it and write a single line to stdout, which is either the resulting value or an error message, which must begin with the string error:. The provided syntax modules have example code for you to use.

Run test/test.sh nb to test your interpreter. It compare the output of your interpreter with the reference implementation on a variety of NB expressions. (For terms that are supposed to result in errors, the test script only checks that you printed out a string starting with error:) If it finds any differences, it prints them out and says Some tests failed. If there are no differences, it says All tests passed!

Submission

To submit your code, please:

Push your work to GitHub.
Create a release in GitHub by clicking on “Releases” on the right-hand side, then “Create a new release” or “Draft a new release”.
Fill in “Tag version” and “Release title” with pp1 if you’re submitting the whole assignment, pp1-1 if you’re submitting part 1, pp1-2 if you’re submitting part 2, etc.
Finally, click “Publish Release”.

If you submit the same part more than once, we will grade the latest release for that part.

Rubric

Part	Points
Booleans	8
numbers	12
REPL	10
Total	30