Lisp Front-End to JavaScript Engine

This page features Lisp-to-Javascript translator and runtime library and contains various interactive "pads" to experiment with the system.

Use the code in the text area as-is, or modify it, or replace it. Press "read lisp" to see the result of reading the code in, "lisp -> JS" to see the result of conversion of it to JavaScript, "eval lisp" to execute it.
;; classic recursive definition of factorial (defun fact (n) (if (<= n 1) n (* n (fact (- n 1))))) (out (fact 7)) ;; tower of hanoi (defun do_hanoi (height from to temp) (if (<= height 0) nil (do_hanoi (- height 1) from temp to) (out (+ "move " from " --> " to)) (do_hanoi (- height 1) temp to from))) (defun hanoi (height) (do_hanoi height 1 3 2)) (hanoi 4) ;; any form can be used as an expression (+ 5 (progn 1 2 3) (if 1 2 3) (let ((x 1)) (if x x x))) ;; coding closures in lisp even better than coding them in Javascript: ;; if for no other reason then because there are no 'return's: (defvar myf ((lambda (done) (lambda () (if done 'done (out "first time!") (setq done t)))))) (myf) (myf)

now, why we need all this lisp functionality: list processing.
;; example of a combinatorial traversal with lists: ;; a generative grammar. input syntax: ;; (a b c ...) sequence ;; (+ a b c ...) alternatives: a or b or c or ... ;; (* a b c ...) optional alternatives: nothing or a or b or c or ... (defun ggen (list path) (if list (let* ((item (car list))) (if (consp item) (if (eq (car item) '+) (mapcar (lambda (elt) (ggen (cons elt (cdr list)) path)) (cdr item)) (if (eq (car item) '*) (mapcar (lambda (elt) (ggen (cons elt (cdr list)) path)) (cons nil (cdr item))) (ggen (append item (cdr list)) path))) (if item (ggen (cdr list) (cons item path)) (ggen (cdr list) path)))) (out (. (list2arr (reverse path)) (join " "))))) (out "simple example:") (ggen '(a "b" (c d) e f (* g1 g2))) (out "more compex:") (ggen '(a "b" (c d) e f (+ g1 (g2a g2b) g3) i h (* k1 k2 (+ k31 k32)) x y z)) (out "rumsfeldisms:") (ggen '(we (+ know (do not know)) there are (+ known unknown) (+ knowns unknowns) and there are (+ unknown known) (+ unknowns knowns))) ;; printing lists out - tests for long or circular lists (set_print_bounds 5 5) ;; set print bounds very low, for tests (out '(1 2 3 4 5)) (out '(1 2 3 4 5 6)) (let ((x (cons 1 1))) (setq x.cdr x) (out x)) (let ((x (cons 1 1))) (setq x.car x) (out x)) (set_print_bounds) ;; restore the default bounds 'done

note that lisp functionality remains very much the same if JS is used directly, and JS's expressiveness is very much similar to lisp. Thus, one can do list processing using JS code invoking list library functions car, cdr, list, append, mapcar, consp, lispt, etc and also possibly using x.car, x.cdr, new Cons, x.constructor == Cons where appropriate for efficiency.
// classic recursive definition of factorial function fact (a) { if (a <= 1) return a; else return a * fact(a - 1); } out(fact(7)); // tower of hanoi function do_hanoi (height, from, to, temp) { if (height > 0) { do_hanoi(height - 1, from, temp, to); out("move " + from + " --> " + to); do_hanoi(height - 1, temp, to, from); } } function hanoi (height) { do_hanoi(height, 1, 3, 2); } hanoi(4); function ggen (list, path) { if (list) { var item = car(list); if (consp(item)) { if (car(item) == "+") mapcar(function (elt) {ggen(cons(elt, cdr(list)), path)}, cdr(item)); else if (car(item) == "*") mapcar(function (elt) {ggen(cons(elt, cdr(list)), path)}, cons(undefined, cdr(item))); else ggen(append(item, cdr(list)), path); } else if (item) ggen(cdr(list), cons(item, path)); else ggen(cdr(list), path); } else out(list2arr(reverse(path)).join(" ")); } out ("simple example:"); ggen(read("(a b (c d) e f (+ g1 g2))")); out("more compex:") ggen(read("(a b (c d) e f (+ g1 (g2a g2b) g3) i h (* k1 k2 (+ k31 k32)) x y z)")); out("rumsfeldisms:"); ggen(read("(we (+ know (do not know)) (* (that there are (+ rumsfelds clowns ((+ known unknown) (+ knowns unknowns) and there are (+ unknown known) (+ unknowns knowns))))))"));

However there is one area where lisp syntax wins big. It is lisp's ability to process code as plain S-Exprs. Lisp macros showcase this synergy between lisp's list processing and code manipulation like nothing else.

Adding the ingredients enabling macros - &rest in argument lists, the backquote and its comma and @ syntax, the defmacro facility, the macroexpand function - was not very difficult. The result is a smmall and fast yet capable macro system. A few examples are on the following pad:
(defmacro ax2bxc (a b c) ;; define a polynomial function `(lambda (x) (+ (* ,a x x) (* ,b x) ,c))) ;; compute and show y = 2x^2 + 3x + 1 where x in {1 2 3 4 5 6 7 8} (out "polynom: " (mapcar (ax2bxc 2 3 1) '(1 2 3 4 5 6 7 8))) (defmacro when (test &rest body) `(if ,test (progn ,@body) nil)) (when t (setq txt (+ "hello" ", " "world" "!")) (out txt)) (defmacro unless (test &rest body) `(if ,test nil ,@body)) (defun seque (n i max) (unless (> n max) (cons n (seque (+ n i) i max)))) (out (seque 6 2 30)) (defmacro arithmetic-if (test neg_form zero_form pos_form) (let* ((temp (gensym "$AIF"))) `(let ((,temp ,test)) (if (< ,temp 0) ,neg_form (if (eq ,temp 0) ,zero_form ,pos_form))))) (defun test (n) (arithmetic-if n "<<<" "~~~" ">>>")) (out (mapcar test '( -2 -1 0 1 2))) ;; truly useful macro - temporarily change the value of some var (defmacro having (vname val &rest body) (let ((tmp (gensym "$T$"))) ;; temp var to remember the old value `(let ((,tmp ,vname)) (setq ,vname ,val) ,@body (setq ,vname ,tmp) ;; value restored here ))) (setq xyz 0) ;; xyz is some global variable (defun show_xyz () (out "xyz: " xyz)) (having xyz 5 (list 1 2 3 4) (show_xyz) (cons 1 2) (having xyz 7 (list 1 2 3 4) (show_xyz) (cons 1 2))) (show_xyz) ;; more compex stuff (defmacro defseque (name op) `(defun ,name (n i max) (unless (> n max) (cons n (,name (,op n i) i max))))) (defseque seqmul *) (out (seqmul 1 3 81)) (defun grow_flip (n incr) (if (> n 0) (- 0 n incr) (+ (- 0 n) incr))) (defseque seq_galt grow_flip) (out (seq_galt 3 7 50)) ;; or, with a lambda passed in: (defseque seq_galt2 (lambda (n incr) (if (> n 0) (+ -n -incr) (+ -n incr)))) (seq_galt2 0 5 20) ;; arbitrary block in expression context (defmacro ex (&rest code) `((lambda () ,@code))) (out "use macro ex: " (+ 1 (ex (cons 1 2) (if t 2 3)) 4)) ;; cond is a built-in macro, but here we show its definition (defmacro cond (&rest body) (let* ((build (lambda (code) (if code (let ((test (car (car code))) (yes (cdr (car code))) (no (build (cdr code)))) `(if ,test (progn ,@yes) ,no)))))) (build body))) (defun tf (n) (cond ((= n 1) 10) ((= n 2) 20) ((= n 3) 30) (t 40))) (out "use cond: " (mapcar tf '(1 2 3 4))) 'done

Some answers regards what this project is and is not

This system utilizes classical Lisp S-expressions (a.k.a. S-Exprs) composed from pairs known as CONS cells. However, this is not a definition of an abstract Lisp machine nor a particular Lisp dialect nor an environment that defines the semantics of Lisp code evaluation. Instead this is a S-Expr-based front-end to the host JavaScript environment. The semantics of ECMAScript/JavaScript as defined in ECMA-262 is the key to understanding the flavor of this Lisp system. See here for details.

Considering the above, it is pretty clear that this project is not expected to run some existing Lisp or Scheme code "as is". Some porting is required; many primitives may be missing, some behave differently.

In a nutshell, this project implements a flavor of lisp featuring the following.

Scoping rules are implied by the workings of execution contexts from section 10 of ECMA-262. For instance, lisp closures are lexical (with the smallest lexical scope being a JS function definition), clean and are pretty efficient in comparison to the rest of the JS runtime.

Cons cells are represented as JavaScript objects with 2 properties, car and cdr. Nil is translated to JavaScript undefined. Defun is translated to JavaScript function definition, and due to that, has scope of the corresponding active context. Define and defvar is translated to JavaScript var statement and also has scope of the corresponding active context. Left-hand side of assignment may contain arbitrarily expressions as part of property access expressions.

Atoms in lisp is everything between blanks and list delimiters. and in this system atoms can be used creatively. Specifically, it is possible to intentionally write expressions having complex JavaScript expressions as atoms, One example is a.b.c. Another, contrived one is a.b.c.d-x+y+z[?1:2][++p*q--/*r*/]. Casing is preserved, so (qUote x 1) translates to qUote(x,1).

Symbols have historically played an important role in traditional Lisp systems, providing "objects" with identity and properties and an ability to reify as variables. We've reduced this to two aspects: symbols appearing in translated code can map to JavaScript identifiers or expressions; Symbols (or any atoms) appearing inside of quoted expressions map to JavaScript strings.

Using the System

There are 3 main ways this system can be used.

One is to experiment and have fun with S-expressions, JavaScript and their mix, as demonstrated by the interactive pads seen above on this page.

Take a look at the source of this HTML page. The lisp system is initialized with a script include tag. After that, global object Lisp contains the lisp functions and the translator as its properties. The lisp functions are then exported to become available as toplevel definitions with Lisp.use_package(). One can skip this step, using Lisp as name qualifier, which sometimes can be more appropriate.

The code that drive the interactive pads is not part of the lisp system. Yet the code shows some handy ways to invoke the translator and perhaps is reusable as well.

The second way of using the system is to code Web2.0, AJAX-ian apps in lisp using macros to capture various web code patterns, expanding it into production JavaScript code to be be consequently embedded/included into HTML pages.

The third one is to maintain code in lisp format, perhaps on the server, having that transparently expanded to JavaScript or perhaps into complex HTML content on demand. One example is given below.

HTML with embedded Lisp code

Use what is provided by default, or insert some other HTML code into the textarea below. HTML may contain any elements including JavaScript code. The page can contain Lisp code between and markers as shown below. Lisp code will be translated to JavaScript when buttons are pressed,

<html> <head> <lisp> (defun fact (n) (if (<= n 1) n (* n (fact (- n 1))))) </lisp> </head> <body> Math code that runs on this page was coded as lisp and translated to Javascript. <h3> Recursion </h3><hr> <lisp> (defun show_fact (n) (document.write (+ "factorial of " n " is " (fact n) "<br>"))) (show_fact 1) (show_fact 5) (show_fact 10) (show_fact 15) </lisp> <hr> </body> </html>

Source

Anyone can obtain and use the sources non-commercial purpose.
The core of the system: lisp.js)
The library of advanced control primitives and functions: lisp-lib.js)

Advanced functions and primitives are optional

The code from lisp-lib.js can be loaded independently from lisp.js by need. The interactive pad below has button "Load Lib" that does that.

Runtime Performance estimate: Classic BROWSE benchmark

BROWSE is one of the list-processing benchmarks from the classic Gabriels Lisp benchmark suite. It extensively manipulates AI-like data structures perfroming symbolic pattern matching on lists stored in symbol properties. Back in late 1980s, BROWSE was a non-trivial load even for most advanced, stare-of-the-art compiling and optimizing Lisp systems running on the best hardware of that time. Only supercomputers ran it in a matter of seconds. Most workstations and mainframes ran it in 2-3 mins. You can test the perfromance of your late 00s "workstation" righ now:

;;; BROWSE -- Benchmark to create and browse through an AI-like data base
;;; of units.

;;; First, define some auxiliary macros and functionality

(defmacro time (form) 
  (let* ((start (gensym "$TMS"))) 
    `(let* ((,start (new Date)))
       ,form
       (+ "  time, ms: "  (new String (- (new Date) ,start))))))

(defmacro cond (&rest body)
  (let* ((build (lambda (code) 
                  (if code
                      (let ((test (car (car code)))
                            (yes (cdr (car code)))
                            (no (build (cdr code))))
                        `(if ,test (progn ,@yes)
                           ,no))))))

(build body)))

(defmacro 1- (x) `(- ,x 1))
(defmacro push (elt list) `(set ,list (cons ,elt ,list)))
(defmacro put (obj prop val) `(set (aref ,obj ,prop) ,val))
(defmacro get (obj prop) `(aref ,obj ,prop))

(defmacro rplacd (expr val)  `(setf (. ,expr cdr) ,val))
(defmacro null (val)  `(= ,val nil))
(defmacro atom (val)  `(not (consp ,val)))
(defun copy_tree (x)
  (if (not (consp x))
      x
    (cons (copy_tree (car x))
          (copy_tree (cdr x)))))

;;; Now, BROWSE's original functionality

(defvar browse_rand 21)
(defmacro browse_char1 (x) `(. ,x (charAt 0)))

;;; n is # of symbols
;;; m is maximum amount of stuff on the plist
;;; npats is the number of basic patterns on the unit
;;; ipats is the instantiated copies of the patterns
(defun browse_init (n m npats ipats)
  (setq browse_rand 21)
  (let ((ipats ( copy_tree ipats)))
    (do ((p ipats (cdr p)))
        ((null (cdr p)) (set p.cdr ipats)))     
    (do ((n n  (1- n))
         (i m (cond ((= i 0) m)
                    (t  (1- i))))
         (name (gensym) (gensym))
         (a ()))
        ((= n 0) a)
        (push name a)
        (do ((i i  (1- i)))
            ((= i 0))
            (setf (get name (gensym)) nil))
        (setf (get name 'pattern)
              (do ((i npats  (1- i))
                   (ipats ipats (cdr ipats))
                   (a ()))
                  ((= i 0) a)
                  (push (car ipats) a)))
        (do ((j  (- m i)  (1- j)))
            ((= j 0))
            (setf (get name (gensym)) nil)))))

(defun browse_random ()
  (setq browse_rand (%  (* browse_rand 17) 251)))

(defun browse_randomize (l)
  (do ((a ()))
      ((null l) a)
      (let ((n (% (browse_random)  (list_length l))))
        (cond ((= n 0)
               (push (car l) a)
               (setq l (cdr l)))
              (t 
               (do ((n n  (1- n))
                    (x l (cdr x)))
                   ((= n 1)
                    (push (car (cdr x)) a)
                    (rplacd x x.cdr.cdr))
                   ))))))

(defun match (pat dat alist)
  (cond ((null pat)
         (null dat))
        ((null dat) ())
        ((or (eq (car pat) '?)
             (eq (car pat)
                 (car dat)))
         (match (cdr pat) (cdr dat) alist))
        ((eq (car pat) '*)
         (or (match (cdr pat) dat alist)
             (match (cdr pat) (cdr dat) alist)
             (match pat (cdr dat) alist)))
        (t (cond ((atom (car pat))
                  ;;replace eq by 'eql for char   
                  (cond ((eql (browse_char1 (car pat))
                              "?")
                         (let ((val (assoc (car pat) alist)))
                           (cond (val (match (cons (cdr val)
                                                   (cdr pat))
                                             dat alist))
                                 (t (match (cdr pat)
                                           (cdr dat)
                                           (cons (cons (car pat)
                                                       (car dat))
                                                 alist))))))
                        ((eql (browse_char1 (car pat)) "*")
                         (let ((val (assoc (car pat) alist)))
                           (cond (val (match (append (cdr val)
                                                     (cdr pat))
                                             dat alist))
                                 (t 
                                  (do ((l () (nconc l (cons (car d) nil)))
                                       (e (cons () dat) (cdr e))
                                       (d dat (cdr d)))
                                      ((null e) ())
                                      (cond ((match (cdr pat) d
                                                    (cons (cons (car pat) l)
                                                          alist))
                                             (return t))))))))))
                 (t (and 
                     (not (atom (car dat)))
                     (match (car pat)
                            (car dat) alist)
                     (match (cdr pat)
                            (cdr dat) alist)))))))

(defun browse ()
  (investigate 
   (browse_randomize 
    (browse_init 
     100 10 4 
     '((a a a b b b b a a a a a b b a a a)
       (a a b b b b a a (a a)(b b))
       (a a a b (b a) b a b a))))
   '((*a ?b *b ?b a *a a *b *a)
     (*a *b *b *a (*a) (*b))
     (? ? * (b a) * ? ?))))

(defun investigate (units pats)
  (do ((units units (cdr units)))
      ((null units))
      (do ((pats pats (cdr pats)))
          ((null pats))
          (do ((p (get (car units) 'pattern)
                  (cdr p)))
              ((null p))
              (match (car pats) (car p) ())))))

(defun testbrowse ()
  (time (browse)))

(testbrowse)

If your computer is not hopelesly obsolete, your measure is likely under 1 min. This means you ran this AI benchmark translated to javascript, interpreted, with CAR and CDR implemented as JS properties, inside your favaorite web browser, and it was FASTER than on Lisp workstations or mainframes avaialble only to top AI researhers 20 years ago. Wow.

P.S. This article could have a subtitle: "CONScript: ECMAScript serves Lisp". CONS, from "construct", is classical Lisp function creating the most fundamental Lisp object, a cons pair, a building block of Lisp lists. One can use the library of cons-related Lisp functions such as mapcar, maplist and append directly in Javascript code. CONScript (puns intended) is a system drafting ECMAScript engine to serve as lisp runtime. Macros are why it's fun.

Author: Dmitry Nizhegorodov (dmitrynizh@hotmail.com). My other projects and articles