Lisprolog - Interpreter for a simple Lisp, written in Prolog
To execute simple Lisp code
in Prolog, we have at least
A combination of these approaches is typically used in books that
illustrate how to implement a simple "Prolog" engine in Lisp:
First, these engines typically assume a representation of Prolog
programs that is convenient from a Lisp perspective, and can't
even parse a single proper Prolog term. Instead, as in
Option 1, they require you to manually translate
Prolog programs to Lisp forms before the execution even starts.
This is not sufficient though, because Prolog supports features
like backtracking that Lisp doesn't. Therefore,
they also need to implement an interpreter for
"Prolog" code, as in Option 2.
- "Lisp in Prolog in zero lines": Manually translate each Lisp
function to a Prolog predicate, i.e., rewrite
the Lisp code to Prolog code and then use a Prolog system to
execute the Prolog code. This is possible and easy since a
function is a special case of a relation, and functional
programming is a restricted form of logic programming. We can
readily translate each Lisp function
with N arguments to a Prolog predicate
with N+1 arguments, where the additional argument
is used to relate the original
function's return value to its arguments.
- Write a Prolog program that parses Lisp code in its
natural form, and then interprets the Lisp program based
on its abstract syntax tree or virtual machine
If you allow manual rewriting before the interpretation even
starts, implementing a simple "Lisp" in Prolog is even easier than
the converse, because functions are a special case of relations.
Therefore, once we have manually translated Lisp functions to
Prolog predicates as explained above, we could
delegate the execution directly to the underlying
Prolog engine. This is a very simple approach and
needs zero additional lines of Prolog code: The
existing Prolog engine handles everything. One downside of this
approach is that we give up control over the execution, and thus
we cannot modify any of its aspects if we use
Therefore, here is a bit beyond this simplistic
These 160 lines of Prolog code implement Option 2:
They give you an interpreter for a simple
Lisp, including a parser to let you write Lisp code in its
Internally, Prolog Definite Clause
Grammars are used for parsing Lisp code, and
semicontext notation is
used for implicitly threading through certain arguments.
This Prolog feature is very similar to
A few example queries and their results:
(defun append (x y)
(cons (car x) (append (cdr x) y))
(append '(a b) '(3 4 5))", Vs).
Vs = [append, [a, b, 3, 4, 5]].
Fibonacci, naive version:
(defun fib (n)
(if (= 0 n)
(if (= 1 n)
(+ (fib (- n 1)) (fib (- n 2))))))
(fib 24)", Vs)).
% 14,255,802 inferences, 3.71 CPU in 3.87 seconds (96% CPU, 3842534 Lips)
Vs = [fib, 46368].
Fibonacci, accumulating version:
(defun fib (n)
(if (= 0 n) 0 (fib1 0 1 1 n)))
(defun fib1 (f1 f2 i to)
(if (= i to)
(fib1 f2 (+ f1 f2) (+ i 1) to)))
(fib 250)", Vs)).
% 39,882 inferences, 0.010 CPU in 0.013 seconds (80% CPU, 3988200 Lips)
Vs = [fib, fib1, 7896325826131730509282738943634332893686268675876375].
Fibonacci, iterative version:
(defun fib (n)
(setq f (cons 0 1))
(setq i 0)
(while (< i n)
(setq f (cons (cdr f) (+ (car f) (cdr f))))
(setq i (+ i 1)))
(fib 350)", Vs)).
% 34,233 inferences, 0.010 CPU in 0.010 seconds (98% CPU, 3423300 Lips)
Vs = [fib, 6254449428820551641549772190170184190608177514674331726439961915653414425].
Higher-order programming and eval:
(defun map (f xs)
(cons (eval (list f (car xs))) (map f (cdr xs)))
(defun plus1 (x) (+ 1 x))
(map 'plus1 '(1 2 3))", Vs).
Vs = [map, plus1, [2, 3, 4]].
If you are interested in interpreters, check
out A Couple of Meta-interpreters in
Prolog: You can write a meta-interpreter
for pure Prolog in
at most 4 lines
of code! Contrast this with the rather complex
meta-interpreters for Lisp.
For more interpreters written in declarative languages, check out Thinking in States.
If you are interested in Lisp, you may also like
More about Prolog