To execute simple Lisp code in

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

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

Therefore, here is a bit

These

Internally, Prolog Definite Clause Grammars are used for parsing Lisp code, and semicontext notation is used for

A few example queries and their results:

?- 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]].

?- 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].

?- 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].

?- 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].

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

For more interpreters written in declarative languages, check out

If you are interested in Lisp, you may also like Prolog macros.