Lisprolog - Interpreter for a simple Lisp, written in Prolog
To execute Lisp code with Prolog, we have at least
2 options:
- "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
instructions.
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.
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 this method.
Therefore, here is a bit beyond this simplistic
approach: lisprolog.pl
The code is also available from a public git
repository: https://github.com/triska/lisprolog
These 165 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
natural form.
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
Haskell's monads.
A few example queries and their results, tested with
Scryer Prolog:
Append:
?- run(" \
\
(defun append (x y) \
(if x \
(cons (car x) (append (cdr x) y)) \
y)) \
\
(append '(a b) '(3 4 5)) \
\
", Vs).
Vs = [append,[a,b,3,4,5]].
Fibonacci, naive version:
?- time(run(" \
\
(defun fib (n) \
(if (= 0 n) \
0 \
(if (= 1 n) \
1 \
(+ (fib (- n 1)) (fib (- n 2)))))) \
(fib 24) \
\
", Vs)).
% CPU time: 3.122s
Vs = [fib,46368].
Fibonacci, accumulating version:
?- time(run(" \
\
(defun fib (n) \
(if (= 0 n) 0 (fib1 0 1 1 n))) \
\
(defun fib1 (f1 f2 i to) \
(if (= i to) \
f2 \
(fib1 f2 (+ f1 f2) (+ i 1) to))) \
\
(fib 250) \
\
", Vs)).
% CPU time: 0.014s
Vs = [fib,fib1,7896325826131730509282738943634332893686268675876375].
Fibonacci, iterative version:
?- time(run(" \
\
(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))) \
(car f)) \
\
(fib 350) \
\
", Vs)).
% CPU time: 0.017s
Vs = [fib,6254449428820551641549772190170184190608177514674331726439961915653414425].
Higher-order programming and eval:
?- run(" \
\
(defun map (f xs) \
(if 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
Prolog macros.
More about Prolog:
The Power of Prolog
Main page