Rosetta Lisp is a set of Lisp-1 implementations that share the VM instruction set, built-in functions, and the bootstrapping code.

• Introduction article (Japanese)

Currently there are 6 implementations available. Each of them is implemented in different languages.

• ocalisp in OCaml (Reference implementation)
• scalisp in Scala 3
• golisp in Go
• fslisp in F#
• kokalisp in Koka 3
• idrlisp in Idris 1 (Out of date)
• wonderlisp in Rosetta Lisp itself

The design of the Rosetta Lisp implementation is heavily inspired by SECD machine. Every S-expression is macro-expanded and then compiled into a code, a sequence of instructions. Rosetta Lisp implementations share an extremely simple, small instruction set that targeting an SECD-like virtual machine.

Rosetta Lisp VM consists of four states:

• [S]tack - a list of values
• [E]nvironment - an abstract representation of a collection of key-value pairs
• [C]ode - a list of instructions
• [D]ump - a list of pairs of Environment and Code

Push a value on top of S.

(define (ldc value)
  (lambda (S E C D k)
    (k (cons value S) E C D)))

Find a binding for name from E and push the value on top of S.

(define (ldv name)
  (lambda (S E C D k)
    (k (cons (find-env name E) S) E C D)))

Make a function capturing E and push it on top of S.

(define (ldf pattern code)
  (lambda (S E C D k)
    (k (cons (make-function-closure pattern code E) S) E C D)))

Make a macro capturing E and push it on top of S.

(define (ldm pattern code)
  (lambda (S E C D k)
    (k (cons (make-macro-closure pattern code E) S) E C D)))

Find a built-in function named name and push it on top of S.

(define (ldb name)
  (lambda (S E C D k)
    (k (cons (find-builtin-function name) S) E C D)))

Pop a value from S, set C to then-code if the value is #f, set C to else-code otherwise. Set E to a new environment derived from E. Push the previous E and C on top of D.

(define (sel then-code else-code)
  (lambda ((s . S) E C D k)
    (k S
       (new-env E)
       (if s then-code else-code)
       (cons (cons E C) D))))

Pop a pair of Environment and Code from D and set E and C to it.

(define (leave)
  (lambda (S E C ((e . c) . D) k)
    (k S e c D)))

Pop argc values as function arguments from S, pop a function from S, call the function with the arguments.

(define (app argc)
  (lambda ((argN argN-1 ... arg1 f . S) E C D k)
    (apply-function f (list arg1 .. argN) S E C D k)))

apply-function is defined for built-in functions and function closures obtained by ldf. apply-function on function closures is defined as follows:

(define (apply-function (FUNCTION-CLOSURE pattern code env)
                        args
                        S E C D k)
  (k S
     (bind-args-with-pattern args pattern (new-env env))
     code
     (cons (cons E C) D)))

Pop a value from S.

(define (pop)
  (lambda ((s . S) E C D k)
    (k S E C D)))

Pop a value, create a binding from name to the value on E.

(define (def name)
  (lambda ((s . S) E C D k)
    (k S (env-define name s E) C D)))

Pop a value, update a binding from name to the value on E.

(define (set name)
  (lambda ((s . S) E C D k)
    (k S (env-set name s E) C D)))

All literals and quoted expressions are compiled into ldc:

; compiling 123
[0 entry]
  ldc 123

All unquoted symbols are compiled into ldv:

; compiling foo
[0 entry]
  ldv foo

Lists are compiled into a sequence of element evaluations and an app.

; compiling (compare a b)
[0 entry]
  ldv compare
  ldv a
  ldv b
  app 2

; compiling (+ foo (* bar baz) 111)
[0 entry]
  ldv +
  ldv foo
  ldv *
  ldv bar
  ldv baz
  app 2
  ldc 111
  app 3

All other instructions are produced by Syntax. Applications of Syntax are not compiled into an usual app.

(builtin cons) produces a ldb.

[0 entry]
  ldb hello

(if a b c) produces a sel and two branch codes terminated by a leave.

[0 entry]
  ldv a
  sel [1 then] [2 else]
[1 then]
  ldv b
  leave
[2 else]
  ldv c
  leave

(begin a b c) produces a sequence of evaluations and pops.

[0 entry]
  ldv a
  pop
  ldv b
  pop
  ldv c

(fun (x y) y) produces a ldf, (macro (x y) x) produces a ldm. Body of functions are terminated by a leave but macros are not.

[0 entry]
  ldf [1 fun (x y)]
[1 fun (x y)]
  ldv y
  leave

[0 entry]
  ldm [1 macro (x y)]
[1 macro (x y)]
  ldv x

(def x 123) produces a def, (set! x 123) produces a set. Both of them also produce a ldc () to adjust stack size.

[0 entry]
  ldc 123
  def x
  ldc ()

[0 entry]
  ldc 123
  set x
  ldc ()

(quote x) is also one of Syntax that produces a ldc.

All other functionalities are injected as built-in functions. Every implementation provides the same built-in function set. By doing this, Every implementation can use the same bootstrapping code to get frequently used functions and macros.

To reduce the size of required built-in functions, there are a lot of functions and macros that are defined in the bootstrapping code instead of in host languages. It's not optimal in terms of performance, but it makes easy to add another Rosetta Lisp implementation.

In the following documentation, result<a> means a result cons cell.

• If car is #t, the result a is set to cdr.
• If car is #f, the failure error information str is set to cdr.

NOTE: quote is a syntax, quasiquote and unquote are implemented on boot.lisp.

String encoding is not specified, but is expected to be ASCII compatible through these operators. This requirement is usually satisfied by using a Unicode scalar sequence or byte sequence.

vec is a type for minimal support of mutable/fixed-length sequential data.

There are test suites for the functionalities of the parser, the compiler, and the VM. Rosetta Lisp's bootstrapping code includes unit tests for each built-in function, as comments.

(def cons (builtin cons))
;! > (cons 1)
;! fail
;! > (cons 1 2)
;! (1 . 2)
;! > (cons 1 2 3)
;! fail

Since it's troublesome to parse these comments, there is a unified, easy-to-parse test file available. This test file is generated by ./gentest.