Latest update Mar 6, 2023
One or (preferrably) two persons, level of ambition accordingly. It is an advantage (but not an absolute prerequisite) if at least one person knows some compiler theory.
In this project you will design a small functional language and implement an interpreter for it. The language should have at least the following features:
The language does not have to be higher order.
You are allowed to give the language lisp-like syntax, which means all functions and operators, with their arguments, are written with prefix notation and enclosed in parentheses. For instance, you will then write (+ x y) for x + y. This simplifies the parsing considerably.
The language need not be typechecked (although it is a bonus if it is). The interpreter should implement a read-eval-print loop, where expressions are read and evaluated; very much like fsi. New definitions should also be possible to add at the interpreter prompt.
You should write some test functions and evaluate. They should involve recursion. A good example is the factorial function.
It is important that your report contains a decent "user manual" for your interpreter (unless it is very self-explanatory), so it becomes easy for us to test it.
Hints: You will need to parse the input text, and translate it into a syntax tree representing the expression to be evaluated. Each node will contain a token, which represents an "atomic unit" in the language. You will need tokens for: operators, identifiers, constants, conditional. The parsing will do two things: (1) identify tokens, and (2) build the syntax tree. Due to the simple syntax, you can start building a new branch in the syntax tree as soon as you encounter a left parenthesis; you then record the operator/function token, and then recursively parse the sub-trees for the arguments. When you encounter the matching right parenthesis, you return the branch of the tree.
The syntax tree for the expression is then evaluated. So you will need a
function evaluating such trees, returning the resulting value.
You will also need a symbol table, where the declaration of functions to be called are looked up during the evaluation of the syntax tree. When you make a definition of a new function, an entry for it should be added to the symbol table. The symbol table needs to hold the function names as well as some representation of the formal arguments. You must also have some mechanism to substitute actual arguments for formal arguments when a function call is being made.
This is what a definition of the factorial function could look like in the language:
(define fac (x) (if (== x 0) 1 (* x (fac (- x 1)))))
Here is an example of an expression that could be typed in, and which the interpreter should evaluate:
(+ (* (fac 5) 3) 17)
(The correct answer is 377.)