Project 1: Untyped arithmetic expressions

Due: 02/01 at 11:55pm
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

If you don’t have a GitLab account, please create one using your nd.edu email address.
Fork the PL Programming Project repository.
- Make your fork private (under Settings → General → Permissions → Project visibility).
- Add @dchiang and @nbotzer as Maintainers (under Settings → Members → Invite member). You can give us an expiration date of 2019/05/15 if you want.

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 (Guile)
  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.
On student0x.cse.nd.edu, Python 3 is installed at ~dchiang/Public/python/bin/python.

Scheme (Guile): 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!

Please submit your code by pushing to your private repository and creating a tag pp1.

Rubric

Part	Points
Booleans	8
numbers	12
REPL	10
Total	30