Lisp CPU

This is the architecture for a Lisp CPU, which should fit in a small FPGA, like the one used in the Spartan-3 Starter Kit. With "Lisp CPU" I mean that the core evaluates a binary form of s-expressions without compiling it to a lower machine code level, like described in Design of LISP-Based Processors or, SCHEME: A Dielectric LISP or, Finite Memories Considered Harmful or, LAMBDA: The Ultimate Opcode. My goal is not a full featured Common Lisp implementation, but a Lisp dialect which is good enough for writing applications like games, without the need to do all the low-level handlings like in C. While the application logic will be written in Lisp, special hardware functions and performance critical tasks, like sound generation, will be implemented in hardware and available with primitive Lisp functions.

Pointers and values

Every value and pointer is saved in a word, with some extra bits for the type information.

Type Meaning of the word without the type bits
fixnum fixnum
symbol pointer to a symbol structure
list pointer to a list structure
primitive the identifier of a primitive function
array pointer to an array
function pointer to a function
nil the word is not used

Structures

symbol structure: 3 words with type information:

list structure: 2 words with type information:

array structure: first fixnum specifies the size, followed by the typed values or pointers.

function structure: two list pointers: first list is a list of symbols for the parameters, second list is the function body.

Lisp Primitives

+ - < > <= >= /= = * set quote setq defun progn if cons car cdr nil

set-led number : sets the LED bit-pattern (8 bits)

get-led : gets the LED bit-pattern (8 bits)

while condition body : a loop: if the evaluation of condition is not nil, body will be evaluated (implicit progn) and then it starts again with checking condition, until it is nil.

defun : the standard defun, but with dynamic scope and without special lambda list details, like default parameters, keyword arguments etc. All symbols are global and when a function is called, the function arguments are prepended in the value slot of the symbol and removed on function return.

Building a CPU in Lisp

(progn
  (set (quote test) 0)
  (while (< test 10)
    (set-led test)
    (set (quote test) (+ test 1))))

This program can be transformed into the binary s-epression representation and evaluated with lispcpu.lisp.txt.

Building a CPU in Verilog

It's more difficult than I thought to built a Lisp CPU. Perhaps the Verilog language is not so good, because some nice standard language featuers (forever-loop etc.) are missing in the Xilinx-Tools. But it is possible, the code looks only a bit more complicated. For learning how to built a CPU at all and how to implement RAM, ROM, program counter and an evaluator, I started with a simple CPU, which will be enhanced to the Lisp CPU:

module LispCPU(clk, led, segment, digit);
	input clk; 

	// disable LEDs and 7 segment display
	output [7:0] led;
	output [7:0] segment;
	output [8:0] digit;
	assign segment[7:0] = 0;
	assign digit[8:0] = 'hff;

	// prescaler
	reg [32:0] devide = 0;

	reg [7:0] rLed = 0;
	assign led = rLed;

	`define INIT 1
	`define EVALUATE 2
 
	reg [15:0] ram [0:255];  // 256 words ram
	reg [7:0] pc = 0;  // program counter
	reg [7:0] currentState = `INIT;
	reg [7:0] nextState = `INIT;
	reg [15:0] cmd;
	reg [15:0] accu;

	reg slowClock;

	`define CMD_LED_ON 1
	`define CMD_LED_OFF 2
	`define CMD_LOAD_NEXT_TO_ACCU 3
	`define CMD_WAIT_UNTIL_ACCU_IS_ZERO 4
	`define CMD_JUMP_TO_ZERO 5

	always @(posedge clk) begin 
		if (devide == 0) begin
			devide <= 5000000;
			slowClock <= ~slowClock;
		end else devide <= devide - 1;
	end
 
	always @(posedge slowClock) begin 
		currentState = nextState;
		case (currentState)
			`INIT: begin
				pc = 0;      ram[pc] = `CMD_LED_ON;
				pc = pc + 1; ram[pc] = `CMD_LOAD_NEXT_TO_ACCU;
				pc = pc + 1; ram[pc] = 'h03;  // 3 to accu
				pc = pc + 1; ram[pc] = `CMD_WAIT_UNTIL_ACCU_IS_ZERO;
				pc = pc + 1; ram[pc] = `CMD_LED_OFF;
				pc = pc + 1; ram[pc] = `CMD_LOAD_NEXT_TO_ACCU;
				pc = pc + 1; ram[pc] = 'h09;  // 9 to accu
				pc = pc + 1; ram[pc] = `CMD_WAIT_UNTIL_ACCU_IS_ZERO;
				pc = pc + 1; ram[pc] = `CMD_JUMP_TO_ZERO;
				pc = 0;
				nextState = `EVALUATE;
			end
			`EVALUATE: begin
				cmd = ram[pc];
				pc = pc + 1;
				case (cmd)
					`CMD_LED_ON: rLed = 1;
					`CMD_LED_OFF: rLed = 0;
					`CMD_LOAD_NEXT_TO_ACCU: begin
						accu = ram[pc];
						pc = pc + 1;
					end
					`CMD_WAIT_UNTIL_ACCU_IS_ZERO: begin
						if (accu != 0) begin
							pc = pc - 1;
							accu = accu - 1;
						end
					end
					`CMD_JUMP_TO_ZERO: pc = 0;
				endcase
			end
		endcase
	end

	always @(negedge slowClock) begin 
		currentState <= nextState;
	end

endmodule

Next Things TODO