"Lisp in Dart" "Lisp in Go" Japanese

A Lisp interpreter in TypeScript

February 8 - August 29, 2016 (鈴)

1. Introduction

I ported the Lisp interpreter of 1,200 lines in Dart language [dartlang.org], lisp.dart, ("A fast Lisp interpreter in Dart"), to TypeScript language [typescriptlang.org] with target version ES5 (ECMAScript 5). It is a small yet real Lisp with macros and backquotations based on the tradition, and also with automatic tail-call optimization. The result runs both in the current major web browsers which support ES5 (including Internet Explorer 11 and Safari 9) and Node.js [nodejs.org] on the console.

For the reader's convenience, I have compiled the resulting lisp.ts into JavaScript with the TypeScript compiler tsc and embedded it in this page. Write some Lisp program in the text area below and press Evaluate button. Any output of print and an evaluation result will be displayed. To wipe out the results, press Wipe button.

If you want to try it quickly, press Example button. A program which calculates a Fibonacci number will be written to the text area. Press Evaluate button. The result 55 of (fib 10) will be displayed. Rewrite it to (fib 20) and press Evaluate button; 6765 will be added. Besides, remove the two parentheses and the number and Evaluate the fib itself; you will see an image of closure where if has been expanded into the special form cond and the formal argument n has been compiled into a offset value in the frame.

The interpreter does not communicate with any servers; it runs alone offline once read onto the browser. I have made an archive of simpler example with the source lisp.ts as lisp-*-*-*.tar.bz2 above. Use it freely. I put it under the MIT/X11 license.

               



  



2. Inner Representations of Data

For the Lisp interpreter in TypeScript, I used basically the same inner representations of data as in lisp.dart in Dart. Data types of the implementing language (TypeScript) are used as they are as possible to represent data types of the implemented language (Lisp).

Lisp Expression Inner Representation
numbers 1, 2.3 number
strings "abc", "hello!\n" string
t true
nil null
symbols x, + Sym (user-defined)
keywords lambda, cond Keyword (extends Sym)
lists (x 1 "2"), (y . 3) Cell (user-defined)

In the Dart VM, numbers are represented by int or double; int represents arbitrary-precision integers; int and double can be mixed freely. In this Lisp interpreter, regrettably, numbers are represented only by 64-bit floating-point numbers of JavaScript. It is a big limitation for the specification of Lisp. That is why I named it "Nukata Lisp Light" in *version* (see §4).

Below is the definition of Cell class:

// Lisp cons cell
class Cell {
    constructor(public car: any,
                public cdr: any) {}
    toString(): string { return "(" + this.car + " . " + this.cdr + ")" }

    // Length as a list
    get length(): number { return foldl(0, this, (i, e) => i + 1) }
}

where foldl function is defined as follows.

// foldl(x, (a b c), fn) => fn(fn(fn(x, a), b), c)
function foldl(x: any, j: Cell, fn: (x, y)=>any) {
    while (j !== null) {
        x = fn(x, j.car);
        j = j.cdr;
    }
    return x;
}
Compare them with those of lisp.dart in Dart.
/// Cons cell
class Cell {
  var car;
  var cdr;

  Cell(this.car, this.cdr);
  @override String toString() => "($car . $cdr)";

  /// Length as a list
  int get length => foldl(0, this, (i, e) => i + 1);
}
/// foldl(x, (a b c), fn) => fn(fn(fn(x, a), b), c)
foldl(x, Cell j, fn(y, z)) {
  while (j != null) {
    x = fn(x, j.car);
    j = j.cdr;
  }
  return x;
}

The length property of Cell class is used in a built-in Lisp function, length, which is defined at the constructor of Interp class as follows.

        this.def("length", 1, (a: any[]) =>
                 (a[0] === null ? 0 : a[0].length));

The length function operates not only on Cell class but also on string type which has the length property as well.
(length '(a b c d)) evaluates to 4 and (length "abcd") also evaluates to 4.

Let's try them right now with the text area and Evaluate button in §1.

3. Points of the Porting

The porting from Dart to TypeScript was largely monotonous.

The hardest difficulty in it was to define user-defined exception classes. Systematic handling of exceptions is the pillar of the structure of programs.

Indeed, you can define a derived class from Error of JavaScript in TypeScript 1.7. However, with target version ES5, the derivation from Error is almost only in appearance. Calling super(message) from the constructor does not have effects; information about the exception raised will not propagete.

Thus, I defined the following base class which sets up information about the exception manually, and derived EvalException and FormatException from it for the Lisp interpreter.

// Base class of user-defined exceptions
class Exception extends Error {
   constructor(message: string)  {
       super();
       // XXX super(..) has no effects for Error; set it up manually.

       // Capture the stack trace if it runs on Node.js.
       let capture = Error["captureStackTrace"];
       if (capture !== undefined)
           capture(this, this.constructor);

       this.message = message;

       // If Function#name in ES6 is available,
       // set the class name at runtime to this.name;
       // otherwise set a fixed name to it.
       let name = this.constructor["name"];
       this.name = (name !== undefined) ? name : "Exception";
    }
}

I ported the Dart predicate identical, which returns true if two arguments are identical, in the same way as the polyfill of Object.is() in ES6 (ECMAScript 6) for non-ES6 browsers found at Object.is() - MDN [mozilla.org].

// Return true if two arguments are identical. (cf. Object#if in ES6)
function identical(x: any, y: any): boolean {
    if (x === y)
        return x !== 0 || 1 / x === 1 / y;
    else
        return x !== x && y !== y;
}

It is disappointing that TypeScript has no such feature like assert statement in Dart. I defined the following function as a temporary expedient.

// A substitution of assert statement
// XXX You must supply message to display what has failed.
// XXX Costs to call this remains even if you empty the function body.
function assert(x: boolean, message?: string): void {
    if (! x)
        throw new Error("Assertion Failure: " + (message || ""));
}

4. Running both in Browsers and Node.js

At the head of the program, two functions to output a sring and to terminate the process are declared as two variables so that the interpreter may run both in browsers and Node.js.

var write: (s: string) => void; // Output string s (a new line on \n char).
var exit: (n: number) => void;  // Terminate the process with exit code n.

At the constructor of Interp class, these write and exit are used as follows to define some built-in Lisp functions.

        this.def("prin1", 1, (a: any[]) => {
            write(str(a[0], true));
            return a[0];
        });
        this.def("princ", 1, (a: any[]) => {
            write(str(a[0], false));
            return a[0];
        });
        this.def("terpri", 0, (a: any[]) => {
            write("\n");
            return true;
        });
        this.def("exit", 1, (a: any[]) => exit(a[0]));

At the tail of the program, if process and require are defined, write and exit are set from process and a main procedure runs, assuming it is in Node.js. If any names of script files are given as the command line arguments, it does require("fs") and reads the files.

// Provisional functions and main procedure for Node.js (not used on browsers)

declare var process: any;
declare function require(name: string);
if (typeof process !== "undefined" && typeof require !== "undefined") {
    write = (s: string) => process.stdout.write(s);
    exit = process.exit;

    // Run interactively in UTF-8 for no argument or any "-" argument.
    // Run each as a script file in UTF-8 in order for other arguments.
    // XXX An exp must be written in one line when running interactively.
    let argv = process.argv;
    if (argv.length <= 2)
        argv = [undefined, undefined, "-"];
    let stdin = undefined;
    let fs = undefined;
    let interp = new Interp();
    run(interp, prelude);
    for (let i = 2; i < argv.length; i++) {
        let fileName = argv[i];
        if (fileName == "-") {
            if (stdin === undefined) {
                stdin = process.openStdin();
                stdin.setEncoding("utf8");
                write("> ");
                stdin.on("data", (input: string) => {
                    try {
                        let r = run(interp, input);
                        write(str(r));
                    } catch (ex) {
                        if (ex instanceof EvalException)
                            write("\n" + ex);
                        else
                            throw ex;
                    }
                    write("\n> ");
                });
                stdin.on("end", () => {
                    write("Goodbye\n");
                });
            }
        } else {
            fs = fs || require("fs");
            let text = fs.readFileSync(fileName, "utf8");
            run(interp, text);
        }
    }
}

The following is an example of running the program with TypeScript 1.7.5 and Node.js v4.2.6 on OS X 10.10.5.

01:~/tmp$ tsc -t ES5 lisp.ts
01:~/tmp$ node lisp.js
> (dump)
("dotimes" "dolist" "while" "nconc" "last" "nreverse" "_nreverse" "assoc" "assq"
 "member" "memq" "listp" "or" "mapcar" "and" "append" "_append" "letrec" "let" "
when" "if" "equal" "/=" "<=" ">=" ">" "setcdr" "setcar" "null" "=" "identity" "p
rint" "consp" "not" "cdddr" "cddar" "cdadr" "cdaar" "caddr" "cadar" "caadr" "caa
ar" "cddr" "cdar" "cadr" "caar" "defun" "defmacro" "*version*" "dump" "exit" "ap
ply" "symbol-name" "intern" "make-symbol" "gensym" "*gensym-counter*" "terpri" "
princ" "prin1" "truncate" "/" "-" "*" "+" "mod" "%" "<" "eql" "numberp" "stringp
" "length" "rplacd" "rplaca" "list" "eq" "atom" "cons" "cdr" "car")
> *version*
(1.2 "TypeScript" "Nukata Lisp Light")
> (+ 5 6)
11
> (+ 7

EvalException: syntax error: ")" expected: EOF at 2
>  
As the last example shows, an expression must be written in one line when running interactively. This inconvenience can be removed by using async/await with target version ES6. See "TypeScript の Async/Await と非同期入力" ("TypeScript no Async/Await to Hidōki-Nyūryoku", Async/Await and Asynchronous Input in TypeScript).

To run lisp.js, compiled from lisp.ts, in browsers, use an HTML file like the following:

<html>
  <head>
    ....
    <style type="text/css">
      ....
      span.warn { color: red }
      textarea { font-family: monospace }
      pre { white-space: pre-wrap; width: 49em;
            overflow: auto; background-color: #F8F8FF }
    </style>
    <script type="text/javascript" src="lisp.js"></script>
  </head>
  <body>
    ....
    <p>
    <textarea id="r_area" rows="15" cols="80"></textarea>

    <p>
    <button onclick="r_eval()" >Evaluate</button>
    &nbsp; &nbsp; &nbsp; &nbsp;
    <button onclick="w_clear()" >Wipe</button>
    &nbsp; &nbsp; &nbsp; &nbsp;
    <button onclick="r_example()" >Example</button>

    <p>
    <pre id="w_area" style="height: 10em"></pre>

    <script type="text/javascript">
      var r_area = document.getElementById("r_area");
      var w_area = document.getElementById("w_area");
      var interp = new Interp();
      run(interp, prelude);

      function r_example() {
         r_area.value =
         "(defun fib (n)\n" +
         "  (if (<= n 1)\n" +
         "      n\n" +
         "    (+ (fib (- n 1))\n" +
         "       (fib (- n 2)))))\n\n" +
         "(fib 10) ; => 55";
      }

      function w_clear() {
         w_area.innerHTML = '';
      }

      function write(s) {
         var t = w_area.innerHTML;
         w_area.innerHTML = t + s;
      }

      function exit(n) {
         write('<span class="warn">' +
               'exit(n) is not implemented.' +
               '</span>\n');
         return null;
      }

      function r_eval() {
         var s = r_area.value;
         try {
            var r = run(interp, s);
         } catch (ex) {
            write('<span class="warn">' +
                  safe_string(ex) +
                  '</span>\n\n');
            return;
         }
         write(safe_string(str(r)) + '\n\n');
      }

      function safe_string(s) {
         s = s + "";
         s = s.replace(/&/g, "&amp;");
         s = s.replace(/</g, "&lt;");
         s = s.replace(/>/g, "&gt;");
         return s;
      }
    </script>
  </body>
</html>

The string s = r_area.value read from the text area r_area will be given to the Lisp interpreter interp to be executed with r = run(interp, s). The string representation str(r) of the result r as a Lisp expression will be added to w_area.innerHTML, the content of the pre element to write.

This page you are reading now is roughly the same as the above.

5. Conclusion

I ported the Lisp of 1,200 lines in Dart to TypeScript with target version ES5 as the Lisp of 1,390 lines. It runs on ECMAScript 5, which is widely popular as the JavaScript on browsers.

The two implementations of Lisp will be useful as the so-called Rosetta stone for comparison and two-way porting between Dart and TypeScript. I have ported the Lisp in Dart also to Go language [golang.org]. It is the Lisp of 1,631 lines described in "Go 言語による Lisp インタープリタ" ("Go gengo ni yoru Lisp intāpurita", A Lisp Interpreter in Go, 2015). Except for the handling of numbers, the three implements the same specification of Lisp.

There is an earlier attempt to implement Lisp in TypeScript. It is the pioneering TypeLisp [github.com] of 416 lines described in "[LSP42] CofeeScriptとTypeScriptとDart" ("[LSP42] CoffeeScript to TypeScript to Dart", (Lisp in) CoffeeScript, TypeScript and Dart, 2014). Compared with it, a key feature of the present implementation (the Lisp in 1,390 lines) is its use of the type and class system of TypeScript and the exception handling of JavaScript, besides the size of specification.

However, a preliminary test shows that the Lisp in Dart runs mostly the fastest, followed by TypeLisp, and the present implementation runs roughly in a half of the speed of them. I guess the reason of the slowness as follows:

  1. Like the Lisp in Dart, it resolves any reference to a formal argument of a user-defined Lisp function in advance and turns the reference at runtime into a simple reference to an array. However, unlike in Dart, arrays in JavaScript is slow in a naïve implementation at least; the resolution may have the contrary effect.
  2. Unlike the Dart VM which implements classes inherently, JavaScript may not operate effectively on codes compiled from classes in TypeScript.

It will be useful to establish the practice of TypeScript programming to look into the realities and the reasons. However, in any way, it runs so quite lightly for a Lisp on scripting language as to expect some Web applications in Lisp will be possible.

Let's try some Lisp programs mentioned in "6. Simple Speed Comparison - A fast Lisp interpreter in Dart" and others by pasting those programs to the text area and pressing Evaluate button in §1. You would see them run quite lightly, depending on machines and browsers.

It will be an interesting attempt to add the interfaces to implement Web applications to this Lisp in practice.

As shown in §2 and §4, it is easy to add built-in functions to this Lisp. You can use data types in JavaScript also in the built-in functions as they are.

Copyright (c) 2016 OKI Software Co., Ltd.