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:
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:
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.