2020 February 7,
Carleton College, Joshua R. Davis,
In this tutorial, we're going to implement a simple programming language together. In any interpreted programming language, interpreting a statement is done in three steps, which coincidentally (?) correspond to the three kinds of machines in this course:
So I hope that this tutorial further illustrates the roles played by finite automata, push-down automata, and Turing machines in the wider world of computing.
You might implement an interpreter in some other course such as CS 251. This tutorial is much less ambitious than that work, in two ways. First, we are implementing our interpreter in Python, which is at least as capable as the language that we're implementing. So we make heavy use of Python's facilities. Second, I've already written the evaluator and the user interface, and the evaluator is the hardest part. See interpreter.py. You must write just the scanner and parser. If you write your code to specification, then it will work seamlessly with my code.
Our language has three data types. The first type is floating-point numbers. Numbers can be added, multiplied, and stored in variables, as the following transcript shows. (By the way, this language superficially resembles Lisp, but it is not Lisp.)
Desktop > python3 interpreter.py Welcome to So Super Language. Press Control-D to exit. :> 7 7.0 :> (+ 2 -4.1) -2.1 :> (set age 20) 20.0 :> (* age 2) 40.0 :> (* 15 40) (+ 100 7) age 600.0 107.0 20.0 :> ^D Desktop >
The second type is strings. They are delimited by single quotation marks ', and they cannot contain any 's. Strings can be concatenated, repeated, and stored in variables:
:> (+ 'computability' ' and complexity') 'computability and complexity' :> (set name 'Turing') 'Turing' :> (* 4 name) 'TuringTuringTuringTuring'
The strings 'TRUE' and 'FALSE' serve as the Booleans in this language.
:> (= (* 2 3) 7) 'FALSE' :> (< 'Zzz' 'dozing') 'TRUE' :> (set x -5) -5.0 :> (if (< x 0) (* -1 x) x) 5.0
The third type is functions. They can be defined by the user, applied to arguments, and stored in variables. Functions are first-class: They can be passed to other functions as arguments and returned from functions as output.
:> (set mult3 (fun (x) (* 3 x))) (fun (x) (* x 3)) :> (mult3 20) 60.0 :> (mult3 'CS254') 'CS254CS254CS254' :> ((fun (x) (+ 7 x)) 11) 18.0 :> (- 7 11) error: unknown: - :> (set - (fun (x y) (+ x (* -1 y)))) (fun (x y) (+ x (* -1 y))) :> (- 7 11) -4.0 :> (((fun (y) (fun (x) (* x y))) 7) 9) 63.0
We also want our interpreter to handle as many kinds of user error as is reasonable.
:> (+ 'python 'cobra') error: syntax: too many or too few ' :> (+ 3 ()) error: syntax: empty list () :> (+ 3 6 error: syntax: unclosed ( :> (+ 3 6)) error: syntax: too many ) :> (* (2 age)) 4) error: syntax: too many ) :> (* 'bad' 'example') error: *: usage (* <num> ... <num> <numOrStr>) :> ((fun (x y) (* x x y)) 3) error: function: incorrect number of arguments to (fun (x y) (* x x y))
Now that you have an idea of how the language should operate, let's get down to the details of your work.
The syntax of the language distinguishes five kinds of characters:
There are four kinds of token in our language:
Your first job is to write the scanner tokenList, based on the stub already present in interpreter.py. The function takes as input a string, representing a single line of user input. It returns a list of strings, namely all of the tokens in the user input, in order. For example, the string (* 11 val) 'so super' scans into the list of six tokens ["(", "*", "11", "val", ")", "'so super'"]. If an error occurs in scanning, then a helpful error message is printed and the Python object None is returned. Implement tokenList using a regular expression. (The core of my solution is a single line of Python, but I have a couple of additional lines to handle errors such as mismatched '.)
Once the scanning rules are out of the way, the rest of the language's syntax is extremely simple. Here's a context-free grammar that uses the concepts of atom and string literal introduced above:
The start variable is LIST. Intuitively, a list is a sequence of one or more expressions. An expression is either an atom, a string literal, or a list enclosed in parentheses.
The children of the root of the parse tree correspond to the expressions that the user types on the input line. Otherwise, the structure of the parse tree represents the nesting of the parentheses in each expression. For example, the input line (+ x 14) is parsed into this five-node tree:
ROOTNODE
|
BRANCHNODE
| | |
+ x 14
The input line ((fun (x) (* x x)) 3) (set y 'babatope') is parsed into this 15-node tree:
ROOTNODE
| |
BRANCHNODE BRANCHNODE
| | | | |
BRANCHNODE 3 set y 'babatope'
| | |
fun BR BRANCHNODE
| | | |
x * x x
The interpreter.py file already contains a TreeNode class, which implements a simple tree data structure. A node can have arbitrarily many children. A node can also store an arbitrary Python object as its data "payload". All of the leaf nodes in the parse tree have Python strings as their payloads; these strings are exactly the atoms and string literals from the token list. The branch nodes' payloads are ignored by the rest of the interpreter, so you may store whatever you like in them.
Your second job is to write the parser parseTree, based on the stub in interpreter.py. This parsing function takes as input a list of strings — the token list produced by tokenList. If the token list does not conform to the grammar, then the parser prints an informative error message and returns None. If the token list conforms to the grammar, then the parser returns a TreeNode representing the root of the parse tree.
The parser does not need to know or check any details of the semantics of the language, such as how many arguments a given function or keyword takes, or what their types should be. That check is performed later by the evaluator.
My solution uses iteration with a stack. The stack stores all of the nodes along the path from the root node to the node where I'm currently working. The node on the top of the stack is the node to which I'm currently attaching children. If you prefer, you can use recursion, which by our Recursion tutorial is equivalent to iteration with a stack.
Here's a tip: First write a parser that assumes a perfectly competent user. That is, the parser has no error handling. My solution is about 13 lines of code. Then introduce various error checks. They cause my solution to grow to about 30 lines of code.
I've already written the evaluator, so you don't need to know anything about the semantics of the language. However, knowing what the language is supposed to do may help you debug.
When an atom is evaluated, we first ask the underlying Python interpreter whether that atom can be interpreted as a floating-point number. If so, then that number is the atom's value. If not, then the atom is inferred to be a variable. When a variable is evaluated, its value is looked up in the environment (the set of variables and their assignments).
When a string literal is evaluated, it evaluates to itself.
When a compound expression (LIST) is evaluated, the head of the list must evaluate to a keyword or function. The remaining items in the list are inferred to be arguments to that keyword or function. A keyword is a string that the evaluator handles on a specific case-by-case basis:
If the head of a compound expression is a function, then the remaining expressions in the list are evaluated, and then the function is evaluated using those values as its arguments. The language comes with built-in functions +, *, =, and <. Here's an optional exercise for you: Implement the functions and, or, not, and <= in So Super Language (not Python).
Here's an example of an issue that is important to CS 251 but not CS 254. In the following code snippet, is the result of the final statement 7.0 or 9.0? The answer depends on exactly how values are stored in, and retrieved from, the environment. It is implicit in the evaluator that I've given you.
:> (set x 3) 3.0 :> (set f (fun (y) (+ x y))) (fun (y) (+ x y)) :> (f 4) 7.0 :> (set x 5) 5.0 :> (f 4)
This issue is called scope. Here's another interesting (and unfortunate) example.
:> (set - (fun (x y) (+ x (* -1 y)))) (fun (x y) (+ x (* -1 y))) :> (set factorial (fun (n) (if (= n 0) 1 (* n (factorial (- n 1)))))) (fun (n) (if (= n 0) 1 (* n (factorial (- n 1))))) :> (factorial 0) 1.0 :> (factorial 1)
To be clear, this language is not intended as a serious competitor to real programming languages. It is missing many features, including loops. It is definitely not as well designed as Lisp. Anyway, let's end on some happier examples.
:> (set curry (fun (f) (fun (x) (fun (y) (f x y))))) (fun (f) (fun (x) (fun (y) (f x y)))) :> (((curry *) 3) 5) 15.0 :> (set compose (fun (f g) (fun (x) (f (g x))))) (fun (f g) (fun (x) (f (g x)))) :> (set square (fun (x) (* x x))) (fun (x) (* x x)) :> (set increment (fun (x) (+ x 1))) (fun (x) (+ x 1)) :> ((compose square increment) 7) 64.0 :> ((compose increment square) 7) 50.0
Once you complete tokenList and parseTree, test the interpreter thoroughly. In particular, it should work on all of the example code given above. (The factorial example is not supposed to work well.)
Let me know if you find errors or bad behavior. I already know that the evaluator's error checking should be better. That is not your problem.