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, tested with Scryer Prolog:

?- 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)).% CPU time: 3.122s 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)).% CPU time: 0.014s 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)).% CPU time: 0.017s 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: