Lisra
Synopsis
A Lisp interpreter in Rascal.
Description
Writing a Lisp interpreter is a classical challenge. Popular word has that all large applications evolve until they include a Lisp interpreter. (A variant says the same about including an email client in every large application).
We will closely follow and reuse parts of Peter Norvig's excellent page on Lispy, a Lisp interpreter written in Python. The Lisp variant to be implemented is the following subset of the Scheme language:
| Form | Syntax | Semantics and Example |
|---|---|---|
| variable reference | ||
| var | ||
| A symbol is interpreted as a variable name; | ||
| its value is the variable's | ||
value. Example: x | ||
| constant literal | ||
| number | ||
A number evaluates to itself. Example: 12 | ||
| quotation | ||
(quote exp) | ||
| Return the exp literally; do not evaluate it. Example: | ||
(quote (a b c)) =>; (a b c) | ||
| conditional | ||
(if _test conseq alt_) | ||
| Evaluate test; if true, | ||
| evaluate and return conseq; otherwise evaluate and return | ||
| alt. Example: (if (< 10 20) (+ 1 1) (+ 3 3)) => 2 | ||
| assignment | ||
(set! _var exp_) | ||
| Evaluate exp and assign that value to | ||
| var, which must have been previously defined (with a | ||
define or as a parameter to an enclosing procedure). | ||
Example: (set! x2 (* x x)) | ||
| definition | ||
(define var exp) | ||
| Define a new variable in the innermost environment and give it | ||
| the value of evaluating the expression exp. | ||
Examples: (define r 3) or (define square (lambda (x) (* x x))) | ||
| procedure | ||
(lambda (_var..._) exp) | ||
| Create a procedure | ||
| with parameter(s) named var... and the expression as the body. | ||
Example: (lambda (r) (* r r)) | ||
| sequencing | ||
(begin _exp..._) | ||
| Evaluate each of the expressions in left-to-right order, and return the final value. | ||
| Example: `(begin (set! x 1) (set! x (+ x 1)) (* x 2)) => 4 | ||
| procedure call | ||
(_proc exp..._) | ||
| If proc is | ||
anything other than one of the symbols if, set!, define, | ||
lambda, begin, or quote then it is treated as a procedure. It is | ||
| evaluated using the same rules defined here. All the expressions | ||
| are evaluated as well, and then the procedure is called with the list | ||
| of expressions as arguments. | ||
| Example: <`(square 12) => 144 |
In this table, var must be a symbol--an identifier such as x or square--and number must be an integer number, while the other italicized words can be any expression. The notation exp... means zero or more repetitions of exp.
A Lisp interpreter consists of the following parts:
- A parser that reads a Lisp program in text form and converts it to a runtime representation that is suitable for the interpreter.
- The interpreter itself that executes the program in runtime representation and computes its outcome.
- A pretty printer that converts the outcome in internal representation back to text.
- Finally, an interactive console is needed that interact with the user.
We discuss all these aspects: