Building-in a Lisp Interpreter

The file Lisp.pro contains a very simple Lisp interpreter, written in Strawberry Prolog. The version of Lisp interpreted is purely functional. It is similar to Lispkit Lisp, that is described in the book of P. Henderson Functional Programming. Application and Implementation .

The interpreter is invoked through the eval predicate, i. e.

eval(Expression,Value)

succeeds if Expression is instantiated to a Lisp expression and its value is Value .

This interpreter allows Strawberry Prolog programmers to mix functional components into their programs.

Syntax of Lisp expressions:

variable ::= Strawberry Prolog atom.
number ::= Strawberry Prolog number.
constant ::= quote( Strawberry Prolog Term ) .
atomic_expression ::= [] | number | constant | variable.
unary_operation ::= car | cdr | atom | number | null .
binary_operation ::= eq | leq | add | sub | mul | div | md | cons .
variable_list ::= [] | nonempty_variable_list
nonempty_variable_list ::= variable | nonempty_variable_list, variable
expression_list ::= expression | expression_list, expression
expression ::= atomic_expression
| unary_operation( expression )
| binary_operation ( expression , expression )
| list( expression_list )
| if_expression
| do_expression
| lambda_expression
| let_expression
| letrec_expression
| variable( expression_list )
| [ expression_list ] .
if_expression ::= if( expression , expression , expression ) .
do_expression ::= do( expression_list )
lambda_expression ::= lambda( variable_list , expression ) .
let_expression ::= let( expression , association_list ) .
letrec_expression ::= letrec( expression , association_list ) .
association_list ::= association | association_list, association.
association ::= [ variable , expression ] .

Example:

?- eval(letrec(fact(7),
[fact,lambda([x],
if(eq(x,0),
1,
mul(x,fact(sub(x,1)))
)
)]),
Value), write(Value).
causes Strawberry Prolog to write 5040 , which is the value of 7! .

Structure of the program lisp.pro :

The eval predicate is defined in terms of two other predicates: l_expr and compute. The l_expr predicate checks whether the expression given to eval is a syntactically correct Lisp program. If it is, the compute predicate evaluates it.

The compute predicate contains clauses that correspond to the different Lisp constructs implemented. It also refers to compute_list, compute_ass_list and compute_arg_list that deal with lists of (variable names and) expressions that have to be evaluated. The basic steps in computing Lisp expressions are accomplished by the value and local_value predicates, that access variable values, and by the apply_un and apply_bin predicates, that implement built-in operations.

The reserved_word, binary and unary predicates define the lists of atoms that cannot be used as variable names in Lisp programs submitted to the interpreter. These lists contain a little more built-in Lisp function names than those implemented. If you wish to implement the functions in Strawberry Prolog, just edit the lisp.pro file. If you prefer to define them in the Lisp program fragments that you submit to eval, you will need to remove their names from the lists.