"circlisp" "Lisp in TypeScript" "Lisp in Go" Japanese

A fast Lisp interpreter in Dart

Written in Japanese: April 6, 2015 (鈴)
Translated to English: June 25, 2015

1. Introduction

In "Dart のイテレータと非同期処理" ("Dart no Iterēta to Hidōkishori"), I reviewed iterators and asynchronous operations of Dart, presenting a simple implementation of read function of Lisp as a non-trivial programming example. Here going forward with it, I present an entire implementation of Lisp interpreter.

The implementation is based on those of L2Lisp, ver. 7.2 and later, and has automatic avoidance of free symbol capture in macro expansion, tail call optimization (which also implies tail recursion optimization), and expansion of quasi-quotations, along with the other features. It runs far faster than those of L2Lisp in Ruby and Python, which are the same category as Dart in that they are scripting languages. Further, it shows almost the same performance as that of L2Lisp in Java. In the rest of this article, I sketch out the implementation and give a simple speed comparison.

I use Dark SDK 1.9.1 (distributed at Index of Downloads [dartlang.org]) and later as the Dart implementation.

2. Inner Representations of Lisp Expressions

The table below summarizes the inner representations of expressions to be read by the Lisp interpreter. As you see, bulit-in types of Dart represent their values also in Lisp if possible.

The Sym class is, however, user-defined to represent Lisp symbols because the bulit-in Symbol type of Dart represents only identifiers that are allowed by the Dart language. Some symbols such as lambda and cond are represented by Keyword in order to be treated specially as expression keywords. A list of Lisp is represented as a linked list of instances of the Cell class, which is defined to represent cons cells. An instance of Cell consists of two members, named car and cdr respectively by tradition. These classes are discussed in the next section in detail.

Lisp Expression Inner Representation
numbers 1, 2.3 num (int & double)
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)

The table below summarizes the inner representations of evaluated lambda expressions and other functions. Note that they are not the results of applications of such expressions. All of them are instances of user-defined classes.

A lambda expression is a list represented by Cell when it is read by the interpreter. When it is evaluated as a Lisp expression, an instance of Closure will be constructed as the result. In the construction of Closure, each lambda expression nested in the body of the lambda expression will be replaced by an instance of Lambda; each occurrence of formal parameter there will be replaced by an instance of Arg; and each macro and each quasi-quotation there will be expanded. In short, it is compiled to resolve the parameters, macros, etc. which occur in its body.

Lisp Expression Compiled Inner Representation
lambda expressions (lambda (...) ...) Closure (has Cell as its environment)
nested lambda expresions (lambda (...) ...) Lambda (has no environment)
macro expressions (macro (...) ...) Macro (has no environment)
built-in functions car, cons, +, ... BuiltInFunc

You can see string representations of instances of these classes in your interactive Lisp session as follows. When you define a function with (defun ...) in Lisp, the function body will be compiled to an instance of Closure. In a similar way, when you define a macro with (defmacro ...), the macro body will be compiled to an instance of Macro.

> (lambda (x) (+ x 1))
#<closure:1:nil:((+ #0:0:x 1))>
> (lambda (x) (lambda (y) (+ x y)))
#<closure:1:nil:(#<lambda:1:((+ #1:0:x #0:0:y))>)>
> (macro (x) `(+ ,x 1))
#<macro:1:((list '+ #0:0:x 1))>
> car
#<car:1>
> equal
#<closure:2:nil:((cond ((atom #0:0:x) (eql #0:0:x #0:1:y)) ((atom #0:1:y) nil) (
(equal (car #0:0:x) (car #0:1:y)) (equal (cdr #0:0:x) (cdr #0:1:y)))))>
> if
#<macro:-3:((cons 'cond (cons (list #0:0:test #0:1:then) (cond (#0:2:else (list 
(cons t #0:2:else)))))))>
>  

Look into the bodies of the compiled lambda expressions in the above example and you see every formal parameter replaced with some Arg instance of the string representation such as #0:0:x. Each Arg instance holds a static nesting level of the corresponding function call and an offset value within the call-frame in order to implement static scoping. For example, an Arg instance of the string representation #1:0:x represents a formal parameter of nesting level 1, offset 0, and symbolic name x.

A call-frame of a Lisp function is implemented with a list (an instance of the built-in List type of Dart) which contains the actual arguments. An environment is implemented with a Lisp list (a instance of user-defined Cell) which contains call-frames.

Most parameters are likely to be at level 0 and then refer to the head of the environment, i.e. a car of a Lisp list, as their call-frame. And each element of the frame can be accessed in constant time since the frame is a List of Dart. After all, given an environment, most parameters are likely to be accessed in constant time.

Apart from the environments described above, the global environment which holds functions and macros defined globally, for example, car, cons, +, let, and if, is implemented as the globals member of Map<Sym, Object> type within the Interp class which represents the core of the interpreter. The table below summarizes these three kinds of entities.

Component of Lambda Expression Compiled Inner Representation
a formal parameter in the body Arg (has a nesting level and an offset)
an environment Cell (has Lists of actual arguments)
the global environment Interp's globals member (is a Map<Sym, Object>)

Below is the definition of the Arg class. The methods setValue and getValue of Arg provide the relation between formal parameters occurring in the body and the environment.

/// A bound variable in a compiled lambda/macro expression
class Arg {
  final int level;
  final int offset;
  final Sym symbol;

  Arg(this.level, this.offset, this.symbol);
  @override String toString() => "#$level:$offset:$symbol";

  /// Set the value to the location corresponding to the variable in the environment.
  void setValue(x, Cell env) {
    for (int i = 0; i < level; i++)
      env = env.cdr;
    (env.car as List)[offset] = x;
  }

  /// Get the value from the location corresponding to the variable in the environment.
  getValue(Cell env) {
    for (int i = 0; i < level; i++)
      env = env.cdr;
    return (env.car as List)[offset];
  }
}
So far I have sketched the data structure of the Lisp interpreter. Since the algorithm for the interpreter would be determined roughly by the specification of the Lisp language, the above might suffice to build a skeleton of the interpreter. The follwing three sections describing the details of the interpreter are supplements to it, in a sense.

3. Lists, Symbols and Built-in Functions

The following is the definition of the Cell class, which represents lists of Lisp internally. The method toString is intended only for quick debugging. The Lisp interpreter uses the str function, which is not shown here, to display lists as its output.

/// 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);
}

The following is the definition of the foldl function, which is used in the length property to calculate the length of any list.

/// 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;
}
foldl was named after the function of the same name in Haskell. In order to allow foldl to be applied to null, which means nil in Lisp, it is not defined as a method of Cell.

The reason why length is defined as a member of Cell specifically is to define the built-in length function of Lisp

> (length "あいうえお")
5
> (length '(a i u e o))
5
>  

in the way to make use of duck typing which Dart has as a scripting language:

    def("length", 1, (List a) => (a[0] == null) ? 0 : a[0].length);
This is not a thing to be highly evaluated. Orthodoxly speaking, branching on type should be preferred. But it is the attraction of Dart that it can be loose in this way if favored.

where def is a method of the Interp class defined as follows; it constructs a Lisp symbol from the string parameter name and stores the BuiltInFunc instance to the globals member of the Interp class, using the constructed symbol as the key to the instance:

  /// Define a built-in function by giving a name, an arity, and a body.
  void def(String name, int carity, BuiltInFuncBody body) {
    globals[new Sym(name)] = new BuiltInFunc(name, carity, body);
  }
The second argument of the def medthod, carity, is a value that is made up from the arity of the function and whether the function has variable length arguments, i.e., &rest args. "Carity" is my coinage, but I have not decided yet what "c" of c + arity means: combined, composite, or calculated. It counts 1 as an arity for whole &rest args. Then, if the function has &rest args, the sign of the arity number is changed.
For example, the subtraction function - has carity -2, i.e., the length of the arguments is variable and the function takes 1 argument at least when no &rest args. The &rest args are passed as a Cell list.
    def("-", -2, (List a) {
      var x = a[0]; Cell y = a[1];
      return (y == null) ? -x : foldl(x, y, (i, j) => i - j);
    });
It can be used as follows:
> (- 7)
-7
> (- 7 8 9)
-10
>  

The following shows the definitions of some major built-in functions:

    def("car", 1, (List a) => (a[0] == null) ? null : (a[0] as Cell).car);
    def("cdr", 1, (List a) => (a[0] == null) ? null : (a[0] as Cell).cdr);
    def("cons", 2, (List a) => new Cell(a[0], a[1]));
    def("atom", 1, (List a) => (a[0] is Cell) ? null : true);
    def("eq", 2, (List a) => identical(a[0], a[1]) ? true : null);

The following is the definition of the Sym class, which represents Lisp symbols internally. The Sym constructor used in new Sym(name) in the above is a factory in fact. It stores the constructed symbol to the internal table in order to implement the intern operation of Lisp.

/// Lisp symbol
class Sym {
  final String name;

  /// Construct a symbol that is not interned.
  Sym.internal(this.name);

  @override String toString() => name;
  @override int get hashCode => name.hashCode; // ※ Key to Speed!

  /// The table of interned symbols
  static final Map<String, Sym> table = {};

  /// Construct an interned symbol; construct a Keyword if isKeyword holds.
  factory Sym(String name, [bool isKeyword=false]) {
    var result = table[name];
    assert(result == null || ! isKeyword);
    if (result == null) {
      result = isKeyword ? new Keyword.internal(name) : new Sym.internal(name);
      table[name] = result;
    }
    return result;
  }

  /// Is it interned?
  bool get isInterned => table.containsKey(name);
}

The Keyword class, which represents keywords such as lambda, quasiquote, quote, and setq, is derived from the Sym class. As you see from the definition of constructor of Sym above and that of Keyword below, once you construct a symbol with new Keyword("lambda") first, you will get the same Keyword instance even if you call new Symbol("lambda") later. Therefore, it is not necessary to look up any keyword table in the lexical analysis; this makes the operation to read Lisp expressions simple.

/// Expression keyword
class Keyword extends Sym {
  Keyword.internal(String name): super.internal(name);
  factory Keyword(String name) => new Sym(name, true);
}
If you comment out the line
  @override int get hashCode => name.hashCode; // ※ Key to Speed!
in the Sym class definition, the Lisp interpreter will lost speed a little. To watch what happens inside with the profiler, run the line
01:~/tmp$ dart --enable-vm-service lisp.dart some_time-consuming_lisp_script.l
with some time-consuming Lisp script, and open http://localhost:8181 with a Web browser on the same machine. You will see the "Native" takes a lot as follows. You can get the details through the link of "cpu profile". If you undo the commenting-out and profile it again, you will see the "Native" has gone.


Naturally you can use the default hashCode, because two Sym instances should be the same key to Map if and only if they are identical. But actually the hash table implemented inside the Dart 1.9.1 seems not to work so effectively then. Sorry I do not look into it further at present, but I will be glad if someone investigates it and feeds back to the implementers of Dart so that the override trick here may be unnecessary.

4. Expression Evaluation and Tail Call Optimization

The eval method of the Interp class evaluates a Lisp expression in a similar way with the method of the same name in L2Lisp ver. 9.2.

  /// Evaluate a Lisp expression in an environment.
  eval(x, Cell env) {
    try {
      for (;;) {
        if (x is Arg) {
          return x.getValue(env);
        } else if (x is Sym) {
          if (globals.containsKey(x))
            return globals[x];
          throw new EvalException("void variable", x);
        } else if (x is Cell) {
          var fn = x.car;
          Cell arg = cdrCell(x);
          if (fn is Keyword) {
            if (fn == quoteSym) {
              if (arg != null && arg.cdr == null)
                return arg.car;
              throw new EvalException("bad quote", x);
            } else if (fn == prognSym) {
              x = _evalProgN(arg, env);
            } else if (fn == condSym) {
              x = _evalCond(arg, env);
            } else if (fn == setqSym) {
              return _evalSetQ(arg, env);
            } else if (fn == lambdaSym) {
              return _compile(arg, env, Closure.make);
            } else if (fn == macroSym) {
              if (env != null)
                throw new EvalException("nested macro", x);
              return _compile(arg, null, Macro.make);
            } else if (fn == quasiquoteSym) {
              if (arg != null && arg.cdr == null)
                x = qqExpand(arg.car);
              else
                throw new EvalException("bad quasiquote", x);
            } else {
              throw new EvalException("bad keyword", fn);
            }
          } else {              // Application of a function
            // Expand fn = eval(fn, env) here on Sym for speed
            if (fn is Sym) {
                fn = globals[fn];
                if (fn == null)
                  throw new EvalException("undefined", x.car);
            } else {
              fn = eval(fn, env);
            }

            if (fn is Closure) {
              env = fn.makeEnv(this, arg, env);
              x = _evalProgN(fn.body, env);
            } else if (fn is Macro) {
              x = fn.expandWith(this, arg);
            } else if (fn is BuiltInFunc) {
              return fn.evalWith(this, arg, env);
            } else {
              throw new EvalException("not applicable", fn);
            }
          }
        } else if (x is Lambda) {
          return new Closure.from(x, env);
        } else {
          return x;             // Numbers, Strings, null etc.
        }
      }
    } on EvalException catch (ex) {
      if (ex.trace.length < 10)
        ex.trace.add(str(x));
      throw ex;
    }
  }

This methods implements tail call optimization.

To see how it implements the optimization, first, look at the branch of if (fn == prognSym), which covers an evaluation for any Lisp expression (progn E1 E2 ... En). The branch performs x = _evalProgN(arg, env).

            } else if (fn == prognSym) {
              x = _evalProgN(arg, env);
            } ...

As shown below, _evalProgN(arg, env) evaluates each element of arg, assumed to be a Lisp list (E1 E2 ... En), from E1 to En-1 in turn and returns the tail expression En, not evaluating it:

  /// (progn E1 E2.. En) => Evaluate E1, E2, .. except for En and return it.
  _evalProgN(Cell j, Cell env) {
    if (j == null)
      return null;
    for (;;) {
      var x = j.car;
      j = cdrCell(j);
      if (j == null)
        return x;               // The tail expression will be evaluated at the caller.
      eval(x, env);
    }
  }

where the function cdrCell is defined as follows:

/// Get cdr of list x as a Cell or null.
Cell cdrCell(Cell x) {
  var k = x.cdr;
  if (k is Cell)
    return k;
  else if (k == null)
    return null;
  else
    throw new EvalException("proper list expected", x);
}

Thus the tail of any progn expression in Lisp will be evaluated back in the same level of nesting as the progn expression itself. The same applies to any cond (conditional) expression.

Now look at the branch of if (fn is Closure), which covers any application of lambda expression ((lambda (A1 ... An) E1 ... Em) X1 ... Xn):

            if (fn is Closure) {
              env = fn.makeEnv(this, arg, env);
              x = _evalProgN(fn.body, env);
            } ...

First, this branch performs env = fn.makeEnv(this, arg, env) that builds a new environment from arg, assumed to be a list of actual arguments X1 ... Xn, upon the environment held by fn, a Closure instance, and replaces env with the new environment. The previous env is only used to evaluate the actual arguments in fn.makeEnv.

An environment held by a Closure instance is no other than the environment existed when the original lambda expression was evaluated and replaced with the Closure instance. Static scoping is implemented by discarding the current env and building a new one upon this environment.

Then, the body of the lambda expression fn.body is evaluated in the same way as a progn expression. In other words, the tail of the lambda expression will be evaluated back in the same level of nesting as the lambda expression itself.

Thus tail call optimization is implemented.

If such a lambda expression happens to be the body of some tail recursive function, its tail recursive call will be back to the same level of nesting of its first call. Thus tail recursion optimization is implemented.

5. Avoiding Free Symbol Capture Automatically in Macro Expansion

In Common Lisp, it is danger to use a free symbol within a macro definition body. The symbol is free if the macro definition does not create a binding for it. A trouble will occur when the macro is expanded in an expression that happens to contain a local variable of the same name as the symbol. The symbol within the macro will be confused with the local variable. It is likely to happen since the macro users do not necessarily know the detail of the macro definition.

I will show you an example based on the discussion of L2Lisp ver. 2.0. The following is an interactive session of GNU CLISP 2.48, an implementation of Common Lisp:

[1]> (setq x "poi")
"poi"
[2]> (defmacro m (n) `(setq x ,n))
M
[3]> ((lambda (x) (m 3) (print x))
      100)

3
3
[4]> x
"poi"
[5]>  

The above application of the lambda expression [3] gives the actual argument 100 to the formal parameter x. The parameter x is, however, reset to 3 because the expression (m 3) within the lambda expression is expanded to (setq x 3). The expression (print x) prints 3 and the result of the application is also 3. The global variable x which the macro m ought to have set remains the initial value "poi".

The book below discusses this problem of Common Lisp in the ninth chapter as the "自由なシンボルの捕捉" ("Jiyū na Shimboru no Hosoku", Free Symbol Capture). In Common Lisp, this defect (provided by the language specification in a sense) has been avoided traditionally by giving global variable names which begin and end with asterisks. As discussed in the section 9.8 of the book, however, there is no adequate way to avoid it for function names.

Nevertheless, this defect is largely harmless because Common Lisp separates the name space into one for functions and one for variables. In other words, it can be said that the existence of this defect has been justified the separation of name spaces which has made the semantics of the Common Lisp language complex unnecessarily.

On the other hand, the Lisp presented here has no such quirk. Any formal parameter in a lambda expression is valid only in the lexical scope of the body of the expression. Within alpha equivalence in lambda calculus, it can be renamed to any name as far as it does not conflict with others lexically in the scope. The name spaces for functions and variables are simply unified without the trouble.

The following session shows it:

> (setq x "poi")
"poi"
> (defmacro m (n) `(setq x ,n))
m
> ((lambda (x) (m 3) (print x))
   100)
100
100
> x
3
>  

It should be obvious why it goes so if you see the compiled macro expression and the compiled lambda expression:

> m
#<macro:1:((list 'setq 'x #0:0:n))>
> (lambda (x) (m 3) (print x))
#<closure:1:nil:((setq x 3) (print #0:0:x))>
>  

The Closure instance here has replaced the parameter x occurring in the expression body by the Arg instance #0:0:x before expanding the macro application (m 3) to (setq x 3).

To see how the replacement and expansion above are implemented, look at the branch in the eval method which is shown below and covers the compilation of any lambda expression:

            } else if (fn == lambdaSym) {
              return _compile(arg, env, Closure.make);
            } ...

where the _compile method is defined as follows:

 /// Compile a Lisp list (macro ...) or (lambda ...).
  DefinedFunc _compile(Cell arg, Cell env, FuncFactory make) {
    if (arg == null)
      throw new EvalException("arglist and body expected", arg);
    Map<Sym, Arg> table = {};
    bool hasRest = _makeArgTable(arg.car, table);
    int arity = table.length;
    Cell body = cdrCell(arg);
    body = _scanForArgs(body, table);
    body = _expandMacros(body, 20); // Expand macros statically up to 20 nestings.
    body = _compileInners(body);
    return make((hasRest) ? -arity : arity, body, env);
  }

This method operates as follows:

  1. _makeArgTable makes a table of Arg instances from the list of formal parameters.
  2. _scanForArgs replaces any parameters occurring in the body with the Arg instances by referring to the table.
  3. _expandMacros expands any macros and quasi-quotations in the body.
  4. _compileInners replaces any nesting lambda expressions with Lambda instances.
  5. The third argument make makes the target instance. Now it makes a closure instance because Closure.make is given as the actual argument. Below is the definition of the Closure class:
    /// Compiled Lambda Expresssion (Closure with Environment)
    class Closure extends DefinedFunc {
      /// The environment of the closure
      final Cell env;
    
      Closure(int carity, Cell body, this.env): super(carity, body);
      Closure.from(Lambda x, Cell env): this(x.carity, x.body, env);
      @override String toString() => "#<closure:$carity:${str(env)}:${str(body)}>";
    
      /// Make an environment to evaluate the body from the list of actual arguments.
      Cell makeEnv(Interp interp, Cell arg, Cell interpEnv) {
        List frame = makeFrame(arg);
        evalFrame(frame, interp, interpEnv);
        return new Cell(frame, env); // Prepend the frame to the closure's environment.
      }
    
      static DefinedFunc make(int carity, Cell body, Cell env) =>
        new Closure(carity, body, env);
    }
    

Thus, by replacing the formal parameters with Arg instances (based on alpha equivalence in lambda calculus) before expanding the macros and quasi-quotations, the capture is avoided automatically.

I think such an avoidance will be useful for Scheme, a popular language that also unifies name spaces for functions and variables, if you want to adopt traditional macros similar to those of Common Lisp for it. I explained the avoidance with L2Lisp in Pascal eight years ago. Now I wonder if there is such a dialect of Scheme actually exists.
By the way, as to another type of variable capture given in the ninth chapter of the book, "マクロ引数の捕捉" ("Makuro-Hikisū no Hosoku", Macro Argument Capture), it is as dangerous as in Common Lisp. But the danger can be avoided also as safely as in Common Lisp by using the gensym function. The following is such an example from the prelude string of the interpreter.
(defmacro dolist (spec &rest body) ; (dolist (name list [result]) body...)
  (let ((name (car spec))
        (list (gensym)))
    `(let (,name
           (,list ,(cadr spec)))
       (while ,list
         (setq ,name (car ,list))
         ,@body
         (setq ,list (cdr ,list)))
       ,@(if (cddr spec)
             `((setq ,name nil)
               ,(caddr spec))))))

This will be compiled as follows. Note also that the local variable list introduced by let is replaced with the Arg instance #0:1:list, which is distinguished from the built-in function list introduced by the expansion of quasi-quotations. (i.e., this serves also as an example of automatic avoidance of free symbol capture at the same time).

> dolist
#<macro:-2:((#<lambda:2:((cons 'let (cons (list #0:0:name (list #0:1:list (cadr 
#1:0:spec))) (cons (_append (cons 'while (cons #0:1:list (cons (list 'setq #0:0:
name (list 'car #0:1:list)) #1:1:body))) (list (list 'setq #0:1:list (list 'cdr 
#0:1:list)))) (cond ((cddr #1:0:spec) (list (list 'setq #0:0:name nil) (caddr #1
:0:spec))))))))> (car #0:0:spec) (gensym)))>
>  

Below is an example of its application.

> (dolist (e '(1 2 3 4 5 6 10)) (print e))
1
2
3
4
5
6
10
nil
>  

6. Simple Speed Comparison

I compared the speed of this Lisp in Dart with those of L2Lisp in Python, Ruby and Java by measuring each time to execute 8queens.l (from L2Lisp 7.3 §3) on a MacBook Pro (Retina, 13-inch, Early 2013) with 8GB RAM and Core i5 2.6GHz CPU running OS X 10.9.5. Compared implementations were as follows:

I measured the run time three times and took the shortest one for each. The results were 9.041[s] on Python, 4.678[s] on Ruby, 0.511[s] on Java, and 0.757[s] on Dart. Judging from the results, Dart can be classified as the same category of Java rather than that of so-called scripting languages.

A similar tendency was reported by "zick" in "リリカル☆Lisp開発日記 » [LSP42] ドキッ!LISPだらけの大運動会" [bugyo.tk] ("Lyrical Lisp Kaihatsu-Nikki [LSP42] Doki'! LISP-darake no Dai-Undōkai"). It reported that his implementation of Lisp in Dart survived the competition as one of the fastest two, being almost equal to that of Kotlin on Java VM, among his various implementations of Lisp of the same spefication in many languages.

So I replicated the benchmarks for Lisp used in the second and final rounds of the competition in the same environment, and with the same implementations, as the comparison on 8queens.l above. I got the more obvious results.

Both the benchmarks implement a Lisp evaluator in Lisp (and, the final round benchmark implements another Lisp evaluator on the evaluator) and calculates a Fibonacci number with it. To run them also in L2Lisp, I replaced the expression:

(setq #+nil (defun funcall (f x) (f x)))

at the beginning of the code with:

(defun funcall (f x) (f x))

The results of the second round benchmark were 0.668[s] for L2Lisp on Java, 0.729[s] for Lisp on Dart, 0.733[s] for DartLisp by "zick", 13.996[s] for L2Lisp on Ruby, 28.392[s] for L2Lisp on Python. I measured the run time three times and took the shortest one for each.


The results of the final round benchmark were 90.352[s] for L2Lisp on Java, 150.444[s] for Lisp on Dart, 192.289[s] for DartLisp by "zick". I measured the run time once for each.


The difference of speeds between zick's DartLisp and my Lisp may be explained by the difference whether it uses an association list or an array (List in Dart) for a call-frame of function, and whether it leaves the parameter symbols as they are or resolves them to the offsets in the frame, to be short, whether it takes linear time or constant time to access local variables. However, if it is so, such a way of implementation is not the conclusive factor of the speed, since both L2Lisp in Python and in Ruby also use an array (list in Python or Array in Ruby) for a call-frame and resolve the parameter symbols to the offset in the frame. Indeed they are important in comparisons on the same language, but the difference of performance between the language processors is overwhelming in comparisons on the different languages.

7. Conclusion

Lisp interpreters are complex enough as benchmark tests. Each of the results shown in the previous section can be considered as a rough index of performance each language will show for common problems, although the comparison is not much exact since those interpreters do not implement the strictly same specification of Lisp, albeit they share some architectures.

Judging from the results, Dart is extraordinarily fast among scripting languages such as Python and Ruby, and comparable to Java. There is no breakthrough in building Lisp interpreters other than those for L2Lisp in Python and Ruby, if any. The present speed of Lisp in Dart is a gift of the Dart VM. Dart on the Dart VM is promising as a general-purpose language that copes with both the productivity of scripting languages and the performance comparable to Java.

Lack of static validation is often pointed out as a difficulty in building large systems in a scripting language. Dart can overcome it by static typing even gradually. You can use dartanalyzer to verify the static validity of your program:
01:~/tmp$ dartanalyzer lisp.dart
Analyzing [lisp.dart]...
No issues found
01:~/tmp$  

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