« Recovery Domains: An Organizing Principle for Recoverable Operating Systems

» The Tao of Parallelism in Algorithms


The almost LISP

LISP with a LISP

(aka Lots of Insipid Stupid Brackets)

LISB is an implementation of LISP in maude written by Steve Lauterburg and Andrew Lenharth. LISP is an interesting language with which to expirement with more interesting internal representations in maude. Because of the regular use of data as code and code as data, either one has to convert between two representations quickly, or operate quickly on one unified representation. Many language implementations in maude use two representations: one for data in memory and one for code. LISB uses a unified representation.

The biggest challenge in using a representation that requires extensive use of the store for all computations is having acceptable performance. We feel that LISB reaches this.

Cool things about LISB

Code as Data as Code

Unlike many maude implementations of languages, LISB treats data and code identically. Which is to say, a program is parsed into memory as lists of lists and atoms and numbers. The execution environment is thus designed to execute code out of memory. This allows one to easily support the construction and modification of code by the user. This is different from many other implementations of languages in maude as they tend to interpret the syntax of the language. LISB interprets code from memory. If one looks at support for functions, one finds many other implementations directly store program text as part of a closure. LISB just stores a pointer to the code in memory.

The Macro System

A major feature of LISP is the macro system. LISB supports macros as LISP does. Actually, LISB allows richer semantics than LISP in that it allows anonymous macros and first class macros (though this is little supported and would go away if LISB ever aquired a bytecode compiler). A macro allows one to write a function that takes its arguments unevaluated (they are just things in memory after all) and construct code to be executed in the macro's stead. To help with debugging, LISB provides the macroexpand function that allows one to acquire the code that is the result of an expantion of a macro.

['defmacro 'my-cadr [x] [list $ car [list $ cdr x]]]
[print ['macroexpand $ ['my-cadr [a b c]]]]
[print ['my-cadr $ [a b c]]]

Eval and Quote

Keeping to the code is just data tradition, the eval function exists to allow one to execute a chunk of data (usually a list). Quote allows one to treat the expression following the quote as a chunk of data.

  [defun 'create-addr [x y] [list $ '+ x y]]
  [defun 'create-rec [f x] 
    [if [null x]
            [funcall f [car x] ['create-rec f [cdr x]]]
        [print ['create-rec #$ 'create-addr $[1 2 3 4]]]
        [print [eval ['create-rec #$ 'create-addr $[1 2 3 4]]]]


A set of accessors are provided to allow destructive updates of lists with setf and friends. Accessors are generallized such that using a function that applies an accessor as the last operation as the arguement to an updating function (such as setf) works correctly.

[setf a $ [1 2 3 4]]
[print a]
[setf [car [cdr [cdr a]]] {"3rd"}]
[defun 'cadr [x] [car [cdr x]]]
[setf ['cadr a] {"2nd"}]
[print a]

A useful set of primitives

A representative bunch of builtin functions are provided for testing, conditionals, list manipulation, etc.

TODO: List them

Mixed Standard Library

The initialization of the environment is such that it is trivial to define builtin functions in LISP and have them predefined when user code is executed. For example, the following is part of the initialization code and predefines some "builtin" functions.

--- atom function
-> [defun atom [x] [not [consp x]]]
-> discard

--- list function
-> [defun list [&rest x] x]
-> discard

--- cadr accessor
-> [defun cadr [x] [car [cdr x]]]
-> discard

Lambda-List keywords (aka &rest)

To demonstrate support for Lambda-list keywords, support is provided for &rest. &rest is a modifier before the last argument in a function specifying that all remaining arguments should be put in a list and that list should be bound to the last argument. Thus variable argument functions are supported.

[defun 'some-null-element-p ['lists]
    [cond [[null 'lists] nil]
          [[null [car 'lists]] t]
          [t ['some-null-element-p [cdr 'lists]]]]]

  [defun 'single-list-mapcar ['func 'arg-list]
    [if [null 'arg-list]
      [cons [funcall 'func [car 'arg-list]]
            ['single-list-mapcar 'func [cdr 'arg-list]]]]]

  [defun 'my-mapcar ['func &rest 'arg-lists]
    [if ['some-null-element-p 'arg-lists]
        [cons [apply 'func ['single-list-mapcar #$ first 'arg-lists]]
              [apply #$ 'my-mapcar
                     'func ['single-list-mapcar #$ rest 'arg-lists]]]]]

  [defun 'plus [x y] ['+ x y]]
  [print ['my-mapcar #$ 'plus $ [1 2 3 4] $[4 3 2 2]]]

Potential enhancements


Long executions of LISB would benefit from a GC, especially due to the excessive use of cons cells.

Maude performance tuning

Performance was sped up 63x by simply making minor adjustments to how some equations performed matching and the structure of the global state. It is estimated that another 50% speed up could be obtained by more work.

Message passing concurency

Because if one can do it, one should do it!

More Builtins and Types

Currently, enough builtin functions and predicates exist to write interesting programs (and because of the macro system, you can certainly write most yourself). However, a larger standard library would be nice. Also, support for floating point and vectors would round out the programming arsinal nicely.


So having input functions (that do anything other than really dumb things) is really hard in maude. Ideally you could write you own read-eval-loop in LISB. Then you could have a LISP interpreter written in LISB. And that would be cool.


LISB is available for download. Don't forget the examples.