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
Fork the PL Programming Project repository.
Make your fork private (under Settings → General → Permissions → Project visibility).
@nbotzeras 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.
The syntax of NB is as in TAPL:
t ::= true false if t then t else t 0 succ t pred t iszero t
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.
sto 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"]
tto 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.pyfor example usage.
student0x.cse.nd.edu, Python 3 is installed at
(parse-term s)converts string
sto an AST, made of lists and symbols:
(parse-term s) = (if (iszero (pred (succ zero))) true false)
(format-term t)converts AST
tto a string.
(read-lines prompt f)implements a simple REPL, calling function
fon each line; see
id.scmfor example usage.
Syntax.parse_term sconverts string
sto an AST:
Syntax.parse_term s = If (IsZero (Pred (Succ Zero)), True, False)
Syntax.format_term tconverts AST
tto a string.
Syntax.read_lines prompt fimplements a simple REPL, calling function
fon each line; see
id.mlfor example usage.
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.
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