--> ap/xxxxx


Stripped down Chaitin (atmegascheme#6)

compiles only for the ATmega128

ATmega8: /usr/libexec/gcc/avr/ld: region text is full (lisp2.out section .text)

test with added serial support for prompt

Started on mini Scheme interpreter for the memory deficient (2007.01.03:1 atmegascheme#5 tech_notes#334)

ATmega8 platform, using free software tools, and based on Steele and Sussman's Design of Lisp-based Processors, and Abelson and Sussman's


;;SECTION 5.4.1
  (test (op self-evaluating?) (reg exp))
  (branch (label ev-self-eval))
  (test (op variable?) (reg exp))
  (branch (label ev-variable))
  (test (op quoted?) (reg exp))
  (branch (label ev-quoted))
  (test (op assignment?) (reg exp))
  (branch (label ev-assignment))
  (test (op definition?) (reg exp))
  (branch (label ev-definition))
  (test (op if?) (reg exp))
  (branch (label ev-if))
  (test (op lambda?) (reg exp))
  (branch (label ev-lambda))
  (test (op begin?) (reg exp))
  (branch (label ev-begin))
  (test (op application?) (reg exp))
  (branch (label ev-application))
  (goto (label unknown-expression-type))

also a pinch of Chaitin's C Lisp interpreter...


in contrast Steele and Sussman make use of a 3 bit type field (plus 8 bits for the address) for 7 types (thus 256x 11 bit words)

#define CONSTANTL 0
#define CONSTANTS 1
#define VAREF 2
#define CC 3
#define PROC 4
#define COND 5
#define PROCEDURE 6
#define QUOTE 7

further storage notes (Steel/Sussman):

The method we use for implementing CAR, CDR and CONS is the usual one of using two consecutive words of memory to hold a list cell, the first being the cdr and the second the car, where each word of memory can hold a type field and an address field. The address part of the pointer is in turn the address within the linear memory of the record pointed to.

Abelson and Sussman use two vectors: the_cars and the_cdrs


We can use vectors to implement the basic pair structures required for a list-structured memory. Let us imagine that computer memory is divided into two vectors: the-cars and the-cdrs. We will represent list structure as follows: A pointer to a pair is an index into the two vectors. The car of the pair is the entry in the-cars with the designated index, and the cdr of the pair is the entry in the-cdrs with the designated index. We also need a representation for objects other than pairs (such as numbers and symbols) and a way to distinguish one kind of data from another. There are many methods of accomplishing this, but they all reduce to using typed pointers, that is, to extending the notion of “pointer” to include information on data type.7 The data type enables the system to distinguish a pointer to a pair (which consists of the “pair” data type and an index into the memory vectors) from pointers to other kinds of data (which consist of some other data type and whatever is being used to represent data of that type). Two data objects are considered to be the same (eq?) if their pointers are identical.


The reader maintains a table, traditionally called the obarray, of all the symbols it has ever encountered. When the reader encounters a character string and is about to construct a symbol, it checks the obarray to see if it has ever before seen the same character string. If it has not, it uses the characters to construct a new symbol (a typed pointer to a new character sequence) and enters this pointer in the obarray. If the reader has seen the string before, it returns the symbol pointer stored in the obarray. This process of replacing character strings by unique pointers is called interning symbols.

cons as:

 (op vector-set!) (reg the-cars) (reg free) (reg <reg2>))
 (op vector-set!) (reg the-cdrs) (reg free) (reg <reg3>))
(assign <reg1> (reg free))
(assign free (op +) (reg free) (const 1))

further instruction summary:

A controller instruction in our register-machine language has one of
the following forms, where each <inputi> is either (reg
<register-name>) or (const <constant-value>).

These instructions were introduced in section 5.1.1:

(assign <register-name> (reg <register-name>))

(assign <register-name> (const <constant-value>))

(assign <register-name> (op <operation-name>) <input1> ... <inputn>)

(perform (op <operation-name>) <input1> ... <inputn>)

(test (op <operation-name>) <input1> ... <inputn>)

(branch (label <label-name>))

(goto (label <label-name>))

The use of registers to hold labels was introduced in section 5.1.3:

(assign <register-name> (label <label-name>))

(goto (reg <register-name>))

Instructions to use the stack were introduced in section 5.1.4:

(save <register-name>)