Lisprolog - Interpreter for a simple Lisp, written in Prolog



To execute simple Lisp code in Prolog, we have at least 2 options:
  1. "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.
  2. 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

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

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

% 14,255,802 inferences, 3.71 CPU in 3.87 seconds (96% CPU, 3842534 Lips)
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)).

% 39,882 inferences, 0.010 CPU in 0.013 seconds (80% CPU, 3988200 Lips)
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)).

% 34,233 inferences, 0.010 CPU in 0.010 seconds (98% CPU, 3423300 Lips)
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


Main page