To execute Lisp code with

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

Therefore, here is a bit

The code is also available from a public git repository: https://github.com/triska/lisprolog

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.

More about Prolog: