The Analytic Garden

Image generated by Claude.ai

The SECD machine is a virtual machine designed to be a target m platform for functional programming languages, in particular Lispkit Lisp. the SECD name comes from the four basic registers of the virtual machine: stack, environment, control, and dump. Three of the registers typically act as stacks: stack, control, and dump. The environment register usually contains an associative array.

The SECD machine was originally described by Peter Landin in "The Mechanical Evaluation of Expressions" in 1964. The version I am considering here is described in Peter Henderson's book Functional Programming Application and Implementation [1980]. It's out of print. You can find used copies for sale online.

Each cycle of the machine updates one or more of the registers. An SECD program is an encoding of a functional program into machine code/ In the SECD representation, each operation is represented as a number.

S-expressions

The SECD machine operates on three different types of objects: symbols, numbers, and lists, In this version of the SECD virtual machine, numbers will be integers. For purposes of input and output, SECD and Lispkit Lisp programs are formatted as s-expressions.

The grammar of s-expressions is

s-expression ::= atom | ( s-expression-list )
s-expression-list ::= s-expression | s-expression . s-expression | s-expression s-expression-list
atom ::= integer | string

There is a special symbol atom named "NIL" which represents the empty list. Examples of valid s-expressions are "cat", 42, ( A . B ), and ( a b c d ).

The latter example could be written (a . (b . (c . (d . NIL)))).

Each s-expression type is represented by a class.

/*
 * SExp.java
 *
 * author: Bill Thompson
 * license: GPL 3
 * copyright: 2026-01-27
 *
 * A class for S expressions.
 * 
 * Cons, SymbolAtom, and NumberAtom are subclasses.
 *
 */
package LispKit;

public class SExp {
    protected static final int EMPTY = -1;
	protected static final int CONS = 0;
	protected static final int INT = 1;
	protected static final int SYMBOL = 2;
	
	protected int _type;
	
	public SExp() {
		_type = EMPTY;
	}
	
	public boolean isNumber() {
		 return (_type == INT);
	 }
    
	 public boolean isSymbol() {
		 return (_type == SYMBOL );
	 }
    
	 public boolean isCons() {
		 return (_type == CONS);
	 }
    
	 public boolean isEmpty() {
		 return (_type == EMPTY);
	 }
	 
	 // NIL is a SymbolAtom
	 // NIL should be made a singleton.
	 public boolean isNIL() {
	 	if( _type == SYMBOL ) 
	 		return ((SymbolAtom) this).GetSymbol().equals( "NIL");
	 	else
	 		return false;	
	 }

	 // added car and cdr functions, so that calling them on a non-cons, returs NIL 
	 public SExp car() {
		return new SymbolAtom();
	 }

	  public SExp cdr() {
		return new SymbolAtom();
	 }
}

/*
 * SymbolAtopm.java 
 * author: Bill Thompson
 * license: GPL 3
 * copyright: 2026-01-27
 *
 * A class for holding symbols.
 *
 */
package LispKit;

public class SymbolAtom extends SExp {
	private final String _string;
	
	public SymbolAtom( String s ) {
		_type = SYMBOL;
		_string = s;
	}

	// NIL
	public SymbolAtom() {
		_type = SYMBOL;
		_string = "NIL";
	}
	
	public String GetSymbol() {
		return _string;
	}
}

/*
 * NumberAtom.java
 * author: Bill Thompson
 * license: GPL 3
 * copyright: 2026-01-27
 *
 * A class for holding integers.
 * This class could be changed to hold floats of BigNums.
 *
 */
package LispKit;

public class NumberAtom extends SExp {
	private final int _number;

	public NumberAtom( int n ) {
		_type = INT;
		_number = n;
	}
	
	public int GetInt() {
		return _number;
	}
}

/*
 * Cons.java
 * author: Bill Thompson
 * license: GPL 3
 * copyright: 2026-01-27
 *
 * A class for cons cells.
 * Cons are the glue holding Lisp functions together.
 *
 */
package LispKit;

public class Cons extends SExp {
	
	private SExp _car;
	private SExp _cdr;
	
	public Cons( SExp aCar, SExp aCdr ) {
		_type = CONS;
		_car = aCar;
		_cdr = aCdr;
	}
	
    @Override
	public SExp car() {
		return _car;
	}
	
    @Override
	public SExp cdr() {
		return _cdr;
	}
	
	public void SetCar( SExp aCar ) {
		_car = aCar;
	}
	
	public void SetCdr( SExp aCdr ) {
		_cdr = aCdr;
	}
}

The Cons class provided three functions that are important for manipulating s-expressions:

cons - construct a new s-expression
car - copy the first element of the cons.
cdr - return the rest of the cons.

The code provides classes for reading and writing s-expression. I won't list them here, they are long. The code is modeled on the methods described in Henderson's book. See GitHub for details.

The SECD Machine

Below are the SECD numeric opcode and the operations described as transitions of the registers. The the descriptions are based on Peter Henderson's book. The transition table was generated by ChatGPT, mostly based on https://pqnelson.github.io/org-notes/comp-sci/abstract-machines/secd.html.

Opcode	Mnemonic	Meaning (short)
0	NIL	push NIL / empty list
1	LD	load from environment
2	LDC	load constant
3	LDF	load function (closure)
4	AP	apply
5	RTN	return
6	DUM	push dummy env (for recursion)
7	RAP	recursive apply
8	SEL	conditional branch
9	JOIN	join after SEL
10	CAR	head
11	CDR	tail
12	ATOM	atom?
13	CONS	cons pair
14	EQ	equality
15	ADD	add
16	SUB	subtract
17	MUL	multiply
18	DIV	divide
19	REM	remainder
20	LEQ	≤ test
21	STOP	stop / (in LispKit) special behavior described in manual

==========================================================================

Below are the standard SECD small-step transition rules (Henderson-style) for a machine state ⟨s, e, c, d⟩, using Lisp list notation:

(a . s) means push a on stack s (top at the left).
(OP . c) means instruction OP followed by remaining control c.
A closure is the pair (c' . e') (code + environment).
T / F are the booleans (often represented as non-NIL / NIL in implementations).

These rules follow the common “Henderson SECD” presentation. (pqnelson.github.io)

S-expression operations

CONS
⟨(a b . s), e, (CONS . c), d⟩ → ⟨((a . b) . s), e, c, d⟩ (pqnelson.github.io)

CAR
⟨((a . b) . s), e, (CAR . c), d⟩ → ⟨(a . s), e, c, d⟩ (pqnelson.github.io)

CDR
⟨((a . b) . s), e, (CDR . c), d⟩ → ⟨(b . s), e, c, d⟩ (pqnelson.github.io)

ATOM
⟨(a . s), e, (ATOM . c), d⟩ → ⟨(t . s), e, c, d⟩
where t = T if a is an atom, else t = F. (pqnelson.github.io)

Arithmetic and predicates (all binary; pop a then b)

Each of these leaves e, c, d unchanged; it rewrites the stack top:

ADD: (a b . s) → ((b + a) . s)
SUB: (a b . s) → ((b − a) . s)
MUL: (a b . s) → ((b * a) . s)
DIV: (a b . s) → ((b / a) . s)
REM: (a b . s) → ((b % a) . s)
LEQ: (a b . s) → ((b <= a) . s) (boolean result)
EQ: (a b . s) → ((b = a) . s) (boolean result)

So, e.g.
⟨(a b . s), e, (ADD . c), d⟩ → ⟨((b + a) . s), e, c, d⟩, etc. (pqnelson.github.io)

Loading / closures

LD i
⟨s, e, (LD i . c), d⟩ → ⟨(x . s), e, c, d⟩
where x = locate(i, e). (pqnelson.github.io)

LDC n
⟨s, e, (LDC n . c), d⟩ → ⟨(n . s), e, c, d⟩ (pqnelson.github.io)

LDF c' (make closure)
⟨s, e, (LDF c' . c), d⟩ → ⟨((c' . e) . s), e, c, d⟩ (pqnelson.github.io)

Meta-level lookup (as typically defined)
If i = (b . n) is a pair of indices (frame, offset), then:
locate(b, n, e) = index(n, index(b, e)) where index is 0-based list indexing. (pqnelson.github.io)

Conditionals

SEL cT cF
⟨(x . s), e, (SEL cT cF . c), d⟩ → ⟨s, e, cX, (c . d)⟩
where cX = cT if x = T, else cX = cF. (pqnelson.github.io)

JOIN
⟨s, e, (JOIN), (c . d)⟩ → ⟨s, e, c, d⟩ (pqnelson.github.io)

Function application / return / recursion

Let a closure be (c' . e') and let v be the argument value list.

AP
⟨((c' . e') v . s), e, (AP . c), d⟩ → ⟨NIL, (v . e'), c', (s e c . d)⟩ (pqnelson.github.io)

(Interpretation: clear stack to NIL, extend closure env with argument list v, start executing c', and push caller context onto dump.)

RTN
⟨(x), e', (RTN), (s e c . d)⟩ → ⟨(x . s), e, c, d⟩ (pqnelson.github.io)

DUM (dummy environment for recursion setup)
⟨s, e, (DUM . c), d⟩ → ⟨s, (PENDING . e), c, d⟩ (pqnelson.github.io)

RAP (recursive apply; patch dummy frame)
⟨((c' . e') v . s), (PENDING . e), (RAP . c), d⟩ → ⟨NIL, rplaca(e', v), c', (s e c . d)⟩ (pqnelson.github.io)

Here rplaca is the meta-operation “replace the car of e' with v” (i.e., patch the dummy frame so the function can refer to itself). (pqnelson.github.io)

STOP

STOP halts execution. (Often “final state when C and D are empty”; presentations vary.) (pqnelson.github.io)

========================================================================

For example, the code sequence ( 2 A 21 ) loads the letter A from the control register and pushes it onto the stack.

The SECD class operated by means of switch statement which contains a routine for each op code. For example,

case 2 -> {  // LDC 
    Cons c2 = (Cons) c;
    Cons c3 = (Cons) c2.cdr();  // cdr(c)
    SExp c4 = c3.car();         //car(cdr(c)) 
     s = new Cons( c4, s);      // cons(car(cdr(c)), s)
     c = c3.cdr();              // c =  cdr(cdr(c))
}

I won't list them all here because the class is quite large. See GitHub for details.

Lispkit Lisp

Lispkit Lisp is a functional subset of Lisp. The version here is based on Henderson's book. I started development on a version in Java several years ago and recently got interested in Lisp again. I decided to finish the version. The Java version for the original was developed in an older release of Java, Java 11, I think. Therefore, this version doesn't use more recent features of the language.

Writing a version of SECD and Lispkit is a popular exercise. There are many versions of Lispkit and the SECD machine available on the web in a number of different languages: C, Python, Clojure, Java, and many more. This article describes one more.

Henderson's book describes the operation of Lispkit in an Algol like (C language like) pseudocode. One advantage of Java as implementation language is that it has built-in garbage collection. This feature simplifies programming.

This version of Lispkit is a compiled version, i.e. Lisp source is compiled into SECD s-expressions. The compiled code is executed on the SECD virtual machine.

The Lispkit compiler is written in Lisp.

( LETREC COMPILE
  ( COMPILE LAMBDA ( E )
    ( COMP E ( QUOTE NIL ) ( QUOTE ( 4 21 ) ) ) )
  ( COMP LAMBDA ( E N C )
    ( IF ( ATOM E )
        ( CONS ( QUOTE 1 ) ( CONS ( LOCATION E N ) C ) ) 
    ( IF ( EQ ( CAR E ) ( QUOTE QUOTE ) ) 
        ( CONS ( QUOTE 2 ) ( CONS ( CAR ( CDR E ) ) C ) ) 
    ( IF ( EQ ( CAR E ) ( QUOTE ADD ) ) 
        ( COMP ( CAR ( CDR E ) ) N ( COMP ( CAR ( CDR ( CDR E ) ) ) N ( CONS ( QUOTE 15 ) C ) ) ) 
    ( IF ( EQ ( CAR E ) ( QUOTE SUB ) )
        ( COMP ( CAR ( CDR E ) ) N ( COMP ( CAR ( CDR ( CDR E ) ) ) N ( CONS ( QUOTE 16 ) C ) ) ) 
    ( IF ( EQ ( CAR E ) ( QUOTE MUL ) )
        ( COMP ( CAR ( CDR E ) ) N ( COMP ( CAR ( CDR ( CDR E ) ) ) N ( CONS ( QUOTE 17 ) C ) ) ) 
    ( IF ( EQ ( CAR E ) ( QUOTE DIV ) )
        ( COMP ( CAR ( CDR E ) ) N ( COMP ( CAR ( CDR ( CDR E ) ) ) N ( CONS ( QUOTE 18 ) C ) ) ) 
    ( IF ( EQ ( CAR E ) ( QUOTE REM ) ) 
        ( COMP ( CAR ( CDR E ) ) N ( COMP ( CAR ( CDR ( CDR E ) ) ) N ( CONS ( QUOTE 19 ) C ) ) ) 
    ( IF ( EQ ( CAR E ) ( QUOTE LEQ ) )
        ( COMP ( CAR ( CDR E ) ) N ( COMP ( CAR ( CDR ( CDR E ) ) ) N ( CONS ( QUOTE 20 ) C ) ) ) 
    ( IF ( EQ ( CAR E ) ( QUOTE EQ ) )
        ( COMP ( CAR ( CDR E ) ) N ( COMP ( CAR ( CDR ( CDR E ) ) ) N ( CONS ( QUOTE 14 ) C ) ) ) 
    ( IF ( EQ ( CAR E ) ( QUOTE CAR ) )
        ( COMP ( CAR ( CDR E ) ) N ( CONS ( QUOTE 10 ) C ) )
    ( IF ( EQ ( CAR E ) ( QUOTE CDR ) )
        ( COMP ( CAR ( CDR E ) ) N ( CONS ( QUOTE 11 ) C ) )
    ( IF ( EQ ( CAR E ) ( QUOTE ATOM ) )
        ( COMP ( CAR ( CDR E ) ) N ( CONS ( QUOTE 12 ) C ) )
    ( IF ( EQ ( CAR E ) ( QUOTE CONS ) )
        ( COMP ( CAR ( CDR ( CDR E ) ) ) N ( COMP ( CAR ( CDR E ) ) N ( CONS ( QUOTE 13 ) C ) ) )
    ( IF ( EQ ( CAR E ) ( QUOTE IF ) )
        ( LET ( COMP ( CAR ( CDR E ) ) N ( CONS ( QUOTE 8 )
                                    ( CONS THENPT ( CONS ELSEPT C ) ) ) )
          ( THENPT COMP ( CAR ( CDR ( CDR E ) ) ) N ( QUOTE ( 9 ) ) )
          ( ELSEPT COMP ( CAR ( CDR ( CDR ( CDR E ) ) ) ) N ( QUOTE  ( 9 ) ) )   )
    ( IF ( EQ ( CAR E ) ( QUOTE LAMBDA ) ) 
        ( LET ( CONS ( QUOTE 3 ) ( CONS BODY C ) ) 
          ( BODY COMP ( CAR ( CDR ( CDR E ) ) ) ( CONS ( CAR ( CDR E ) ) N )
                                    ( QUOTE ( 5 ) ) )  )
    ( IF ( EQ ( CAR E ) ( QUOTE LET ) ) 
         ( LET  ( LET  ( COMPLIS ARGS N ( CONS ( QUOTE 3 )
                            ( CONS BODY ( CONS ( QUOTE 4 )  C ) ) ) )
                  ( BODY COMP ( CAR ( CDR E ) ) M ( QUOTE ( 5 ) ) ) )
            ( M CONS ( VARS ( CDR ( CDR E ) ) )  N )
            ( ARGS EXPRS ( CDR ( CDR E ) ) ) )
    ( IF ( EQ ( CAR E ) ( QUOTE LETREC ) )
         ( LET  ( LET  ( CONS ( QUOTE 6 ) ( COMPLIS ARGS M
                            ( CONS ( QUOTE 3 ) ( CONS BODY ( CONS ( QUOTE 7 ) C ) ) ) ) ) 
                  ( BODY COMP ( CAR ( CDR E ) ) M ( QUOTE ( 5 ) ) ) )
            ( M CONS ( VARS ( CDR ( CDR E ) ) ) N ) 
            ( ARGS EXPRS ( CDR ( CDR E ) ) ) )
    ( COMPLIS ( CDR E ) N ( COMP ( CAR E ) N ( CONS ( QUOTE 4 ) C ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )
  ( COMPLIS LAMBDA ( E N C )
    ( IF ( EQ E ( QUOTE NIL ) ) ( CONS ( QUOTE 2 ) ( CONS ( QUOTE NIL ) C ) )
        ( COMPLIS ( CDR E ) N ( COMP ( CAR E ) N ( CONS ( QUOTE 13 ) C ) ) ) ) )
  ( LOCATION LAMBDA ( E N )
    ( LETREC
      ( IF ( MEMBER E ( CAR N ) ) ( CONS ( QUOTE 0 ) ( POSN E ( CAR N ) ) )
          ( INCAR ( LOCATION E ( CDR N ) ) ) )
    ( MEMBER LAMBDA ( E N )
          ( IF ( EQ N ( QUOTE NIL ) ) ( QUOTE F )
          ( IF ( EQ E ( CAR N ) ) ( QUOTE T ) ( MEMBER E ( CDR N ) ) ) ) )
    ( POSN LAMBDA ( E N ) 
      ( IF ( EQ E ( CAR N ) ) ( QUOTE 0 ) ( ADD ( QUOTE 1 ) ( POSN E ( CDR N ) ) ) ) ) 
    ( INCAR LAMBDA ( L ) ( CONS ( ADD ( QUOTE 1 ) ( CAR L ) ) ( CDR L ) ) ) ) )
  ( VARS LAMBDA ( D )
    ( IF ( EQ D ( QUOTE NIL ) ) ( QUOTE NIL )
        ( CONS ( CAR ( CAR D ) )  ( VARS ( CDR D ) ) ) ) )
  ( EXPRS LAMBDA ( D )
    ( IF ( EQ D ( QUOTE NIL ) ) ( QUOTE NIL )
        ( CONS ( CDR ( CAR D ) ) ( EXPRS ( CDR D ) ) ) ) ) 
)

We have a chicken and egg problem. How can we compile the compiler to get started? Fortunately, Henderson's book provides a pre-compiled s-expression version of the Lisp code. You can type it from book. If you're lucky, you won't make too many mistakes. I downloaded it from here.

( 6 2 NIL 3 ( 1 ( 0 . 0 ) 2 NIL 14 8 ( 2 NIL 9 ) ( 2 NIL 1 ( 0 . 0 ) 11 13 1 ( 1 . 5 ) 4 1
( 0 . 0 ) 10 11 13 9 ) 5 ) 13 3 ( 1 ( 0 . 0 ) 2 NIL 14 8 ( 2 NIL 9 ) ( 2 NIL 1 ( 0 . 0 ) 11
13 1 ( 1 . 4 ) 4 1 ( 0 . 0 ) 10 10 13 9 ) 5 ) 13 3 ( 6 2 NIL 3 ( 1 ( 0 . 0 ) 11 2 1 1 ( 0
. 0 ) 10 15 13 5 ) 13 3 ( 1 ( 0 . 0 ) 1 ( 0 . 1 ) 10 14 8 ( 2 0 9 ) ( 2 1 2 NIL 1 ( 0 . 1 )
11 13 1 ( 0 . 0 ) 13 1 ( 1 . 1 ) 4 15 9 ) 5 ) 13 3 ( 1 ( 0 . 1 ) 2 NIL 14 8 ( 2 F 9 ) ( 1
( 0 . 0 ) 1 ( 0 . 1 ) 10 14 8 ( 2 T 9 ) ( 2 NIL 1 ( 0 . 1 ) 11 13 1 ( 0 . 0 ) 13 1 ( 1 . 0 )
4 9 ) 9 ) 5 ) 13 3 ( 2 NIL 1 ( 1 . 1 ) 10 13 1 ( 1 . 0 ) 13 1 ( 0 . 0 ) 4 8 ( 2 NIL 1 ( 1 .
1 ) 10 13 1 ( 1 . 0 ) 13 1 ( 0 . 1 ) 4 2 0 13 9 ) ( 2 NIL 2 NIL 1 ( 1 . 1 ) 11 13 1 ( 1 .
0 ) 13 1 ( 2 . 3 ) 4 13 1 ( 0 . 2 ) 4 9 ) 5 ) 7 5 ) 13 3 ( 1 ( 0 . 0 ) 2 NIL 14 8 ( 1 ( 0 .
2 ) 2 NIL 13 2 2 13 9 ) ( 2 NIL 2 NIL 1 ( 0 . 2 ) 2 13 13 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 )
10 13 1 ( 1 . 1 ) 4 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 13 1 ( 1 . 2 ) 4 9 ) 5 ) 13 3 ( 1 ( 0
. 0 ) 12 8 ( 1 ( 0 . 2 ) 2 NIL 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 13 1 ( 1 . 3 ) 4 13 2 1 13 9 )
( 1 ( 0 . 0 ) 10 2 QUOTE 14 8 ( 1 ( 0 . 2 ) 1 ( 0 . 0 ) 11 10 13 2 2 13 9 ) ( 1 ( 0 . 0 )
10 2 ADD 14 8 ( 2 NIL 2 NIL 1 ( 0 . 2 ) 2 15 13 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 11 10
13 1 ( 1 . 1 ) 4 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 10 13 1 ( 1 . 1 ) 4 9 ) ( 1 ( 0 . 0 ) 10
2 SUB 14 8 ( 2 NIL 2 NIL 1 ( 0 . 2 ) 2 16 13 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 11 10 13
1 ( 1 . 1 ) 4 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 10 13 1 ( 1 . 1 ) 4 9 ) ( 1 ( 0 . 0 ) 10 2
MUL 14 8 ( 2 NIL 2 NIL 1 ( 0 . 2 ) 2 17 13 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 11 10 13 1
( 1 . 1 ) 4 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 10 13 1 ( 1 . 1 ) 4 9 ) ( 1 ( 0 . 0 ) 10 2 DIV
14 8 ( 2 NIL 2 NIL 1 ( 0 . 2 ) 2 18 13 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 11 10 13 1 ( 1
. 1 ) 4 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 10 13 1 ( 1 . 1 ) 4 9 ) ( 1 ( 0 . 0 ) 10 2 REM 14
8 ( 2 NIL 2 NIL 1 ( 0 . 2 ) 2 19 13 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 11 10 13 1 ( 1 .
1 ) 4 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 10 13 1 ( 1 . 1 ) 4 9 ) ( 1 ( 0 . 0 ) 10 2 LEQ 14 8
( 2 NIL 2 NIL 1 ( 0 . 2 ) 2 20 13 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 11 10 13 1 ( 1 . 1 )
4 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 10 13 1 ( 1 . 1 ) 4 9 ) ( 1 ( 0 . 0 ) 10 2 EQ 14 8 ( 2
NIL 2 NIL 1 ( 0 . 2 ) 2 14 13 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 11 10 13 1 ( 1 . 1 ) 4
13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 10 13 1 ( 1 . 1 ) 4 9 ) ( 1 ( 0 . 0 ) 10 2 CAR 14 8 ( 2
NIL 1 ( 0 . 2 ) 2 10 13 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 10 13 1 ( 1 . 1 ) 4 9 ) ( 1 ( 0 .
0 ) 10 2 CDR 14 8 ( 2 NIL 1 ( 0 . 2 ) 2 11 13 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 10 13 1
( 1 . 1 ) 4 9 ) ( 1 ( 0 . 0 ) 10 2 ATOM 14 8 ( 2 NIL 1 ( 0 . 2 ) 2 12 13 13 1 ( 0 . 1 ) 13
1 ( 0 . 0 ) 11 10 13 1 ( 1 . 1 ) 4 9 ) ( 1 ( 0 . 0 ) 10 2 CONS 14 8 ( 2 NIL 2 NIL 1 ( 0 .
2 ) 2 13 13 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 10 13 1 ( 1 . 1 ) 4 13 1 ( 0 . 1 ) 13 1 ( 0
. 0 ) 11 11 10 13 1 ( 1 . 1 ) 4 9 ) ( 1 ( 0 . 0 ) 10 2 IF 14 8 ( 2 NIL 2 NIL 2 ( 9 ) 13 1
( 0 . 1 ) 13 1 ( 0 . 0 ) 11 11 11 10 13 1 ( 1 . 1 ) 4 13 2 NIL 2 ( 9 ) 13 1 ( 0 . 1 ) 13
1 ( 0 . 0 ) 11 11 10 13 1 ( 1 . 1 ) 4 13 3 ( 2 NIL 1 ( 1 . 2 ) 1 ( 0 . 1 ) 13 1 ( 0 . 0 )
13 2 8 13 13 1 ( 1 . 1 ) 13 1 ( 1 . 0 ) 11 10 13 1 ( 2 . 1 ) 4 5 ) 4 9 ) ( 1 ( 0 . 0 ) 10
2 LAMBDA 14 8 ( 2 NIL 2 NIL 2 ( 5 ) 13 1 ( 0 . 1 ) 1 ( 0 . 0 ) 11 10 13 13 1 ( 0 . 0 )
11 11 10 13 1 ( 1 . 1 ) 4 13 3 ( 1 ( 1 . 2 ) 1 ( 0 . 0 ) 13 2 3 13 5 ) 4 9 ) ( 1 ( 0 . 0 )
10 2 LET 14 8 ( 2 NIL 2 NIL 1 ( 0 . 0 ) 11 11 13 1 ( 1 . 5 ) 4 13 1 ( 0 . 1 ) 2 NIL 1
( 0 . 0 ) 11 11 13 1 ( 1 . 4 ) 4 13 13 3 ( 2 NIL 2 NIL 2 ( 5 ) 13 1 ( 0 . 0 ) 13 1 ( 1 .
0 ) 11 10 13 1 ( 2 . 1 ) 4 13 3 ( 2 NIL 1 ( 2 . 2 ) 2 4 13 1 ( 0 . 0 ) 13 2 3 13 13 1
( 2 . 1 ) 13 1 ( 1 . 1 ) 13 1 ( 3 . 2 ) 4 5 ) 4 5 ) 4 9 ) ( 1 ( 0 . 0 ) 10 2 LETREC 14 8 ( 2
NIL 2 NIL 1 ( 0 . 0 ) 11 11 13 1 ( 1 . 5 ) 4 13 1 ( 0 . 1 ) 2 NIL 1 ( 0 . 0 ) 11 11 13
1 ( 1 . 4 ) 4 13 13 3 ( 2 NIL 2 NIL 2 ( 5 ) 13 1 ( 0 . 0 ) 13 1 ( 1 . 0 ) 11 10 13 1 ( 2
. 1 ) 4 13 3 ( 2 NIL 1 ( 2 . 2 ) 2 7 13 1 ( 0 . 0 ) 13 2 3 13 13 1 ( 1 . 0 ) 13 1 ( 1 .
1 ) 13 1 ( 3 . 2 ) 4 2 6 13 5 ) 4 5 ) 4 9 ) ( 2 NIL 2 NIL 1 ( 0 . 2 ) 2 4 13 13 1 ( 0 .
1 ) 13 1 ( 0 . 0 ) 10 13 1 ( 1 . 1 ) 4 13 1 ( 0 . 1 ) 13 1 ( 0 . 0 ) 11 13 1 ( 1 . 2 ) 4
9 ) 9 ) 9 ) 9 ) 9 ) 9 ) 9 ) 9 ) 9 ) 9 ) 9 ) 9 ) 9 ) 9 ) 9 ) 9 ) 9 ) 5 ) 13 3 ( 2 NIL 2 ( 4 21 ) 13 2
NIL 13 1 ( 0 . 0 ) 13 1 ( 1 . 1 ) 4 5 ) 13 3 ( 1 ( 0 . 0 ) 5 ) 7 4 21 )

Lispkit loads the SECD version of compiler, and then reads a Lisp function either from the keyboard or a file. The function is passed as argument to the compiler and the compiler is executed by the SECD machine. This compile the Lisp code to SECD code. Next, the function arguments are read. They are passed as arguments to the compiled function code and the results are displayed as an s-expression.

/*
 * Lispkit.java
 *
 * author: Bill Thompson
 * license: GPL 3
 * copyright: 2026-01-27
 *
 * An SECD virtual machine for a functional version of Lisp
 * Based on Peter Henerson's book
 * Functional Programming Application and Implementation
 * ISBN 0-13-331579-7 
 *
 *  I don't implement garbage collection. Java takes care of that.
 */
package LispKit;

import java.io.*;

public class LispKit {
	/**
	 * Main class for the Lispkit System
	 */

	// compiler.secd is a compiled Lisp compiler for SECD from Henderson's book
	// the compiler.secd file is from https://github.com/carld/lispkit
	private static final String COMPILER_FILE = "compiler.secd";

	public static void main(String[] args) throws FileNotFoundException, IOException {
		String cwd = GetCwd();
	
		/**
		 * Load the compiler
		 * 
		 * Compiler file should be in same directory Lispkit class is run from
		 */
		SExp comp;
		try (FileInputStream f = new FileInputStream( cwd + COMPILER_FILE )) {
			SExpReader compReader = new SExpReader( f );
			comp = compReader.GetExp();
		}

		/**
		 * Read the Lisp function
		 * 
		 * If an arg is passed on commandline, it contains the Lisp function,
		 * otherwise read the function from the terminal.
		 */
		SExpReader s;
		if( args.length > 0 ) {
			try (FileInputStream f2 = new FileInputStream( args[0] )) {
				s = new SExpReader( f2 );
			}
		} 
		else {
			s = new SExpReader();
		}
		SExp fn = s.GetExp();

		// display the function
		SExpWriter w = new SExpWriter();
		w.PutSExp( fn );
		w.ForceLineOut(); 
		
		// compile the Lisp function
		SECD secd = new SECD();
		SExp fn2 = new Cons( fn, new SymbolAtom() );
		SExp compFn = secd.exec( comp, fn2 );

		// print the compled function
		w.PutSExp( compFn );
		w.ForceLineOut(); 

		/**
		 * Read the function arguments
		 * 
		 * If a second arg is passed on commandline, it contains the arguments for the Lisp function,
		 * otherwise read the arguments from the terminal.
		 */
		
		SExpReader s2;
		if( args.length > 1 ) {
			try (FileInputStream f3 = new FileInputStream( args[1] )) {
				s2 = new SExpReader( f3 );
			}
		} 
		else {
			s2 = new SExpReader();
		}
		// SExp fnArgs = s2.GetExpList();
		SExp fnArgs = s2.GetExp();
	
		// display the function arguments
		w.PutSExp( fnArgs );
		w.ForceLineOut(); 

		// execute the function
		secd = new SECD();
		SExp result = secd.exec( compFn, fnArgs );

		// disply results
		w.PutSExp( result );
		w.ForceLineOut(); 		
	}
	
	private static String GetCwd() {
		String cwd = System.getProperty( "user.dir" );
		String dir;
		
		if( ! cwd.endsWith( "/" ) )
			dir = cwd + "/";
		else
			dir = cwd;	
		
		return dir;
	}
}

Here's an example using the notorious Ackerman function for positive integers.. The function is not primitive recursive and its values grows very rapidly. The Lisp version is from here. Many other examples of Lispkit Lisp code can be found here.

\[A(0,n) = n + 1\]

\[A(m + 1,0) = A(m,1)\]

\[A(m + 1,n + 1) = A(m, A(m + 1))\]

( LETREC ACKERMANN
 ( ACKERMANN LAMBDA ( X Y )
  ( IF ( EQ X ( QUOTE 0 ) )
    ( ADD Y ( QUOTE 1 ) )
    ( IF ( EQ Y ( QUOTE 0 ) )
      ( ACKERMANN ( SUB X ( QUOTE 1 ) ) ( QUOTE 1 ) )
      ( ACKERMANN ( SUB X ( QUOTE 1 ) ) ( ACKERMANN X ( SUB Y ( QUOTE 1 ) ) ) ) ) ) ) )

Here are the results

// The input function
( LETREC ACKERMANN ( ACKERMANN LAMBDA ( X Y ) ( IF ( EQ X ( Q
UOTE 0 ) ) ( ADD Y ( QUOTE 1 ) ) ( IF ( EQ Y ( QUOTE 0 ) ) ( 
ACKERMANN ( SUB X ( QUOTE 1 ) ) ( QUOTE 1 ) ) ( ACKERMANN ( S
UB X ( QUOTE 1 ) ) ( ACKERMANN X ( SUB Y ( QUOTE 1 ) ) ) ) ) 
) ) )
// compiled output 
( 6 2 NIL 3 ( 1 ( 0 . 0 ) 2 0 14 8 ( 1 ( 0 . 1 ) 2 1 15 9 ) (
 1 ( 0 . 1 ) 2 0 14 8 ( 2 NIL 2 1 13 1 ( 0 . 0 ) 2 1 16 13 1 
( 1 . 0 ) 4 9 ) ( 2 NIL 2 NIL 1 ( 0 . 1 ) 2 1 16 13 1 ( 0 . 0
 ) 13 1 ( 1 . 0 ) 4 13 1 ( 0 . 0 ) 2 1 16 13 1 ( 1 . 0 ) 4 9 
) 9 ) 5 ) 13 3 ( 1 ( 0 . 0 ) 5 ) 7 4 21 ) 
// arguments
( 3 3 ) 
// result
61

This version of Lispkit doesn't have tail recursion, so if the arguments are slightly larger, the system hangs and eventually crashes.

You can see the full code on GitHub.

The Analytic Garden

SECD and Functional Lisp

S-expressions

The SECD Machine

Lispkit Lisp

Labels

Contributors

wfmu