Lisp on c64

Compact bytecode. No "string" representation of code. Listing a program pretty-prints the bytecode. One-line repl input to build up the program. Saves bytecode to disk.

Eval

Take list. Look for op. For each arg (if args) eval each and put result on stack. After all eval'd the stack should have args. Call op that pops all off stack and pushes result on stack. Separate call stack? Call stack contains pointer to return point in code. Otherwise return point pushed on stack before args. If function

binding

Each function is executed with a scope. This is a symbol lookup table. Calling the function takes the args and copies them to names in the scope. When eval'ing the function symbols are looked up in the scope. By default a function is associated to the current scope. The bind keyword is used to make a new scope and associate it with the function eval.

Stackless eval

Eval without recursion in C (eval is a loop). The loop is while the stack has items.

Take the operator from the start of the list and push it onto the stack. Then traverse the remaining list in reverse, pushing each item onto the stack. The goal is (probably) to turn each non-atom item into an atom of some form. Then continue the loop.

By the time the operator is reached the items should all be atoms. The operator then pulls all the args from the stack, runs the code and replaces itself on the stack with the return value. This return value replaces the list head item.

lisp

A cons is a linked list of cons cells. If the "data" points to the head of a cons (as opposed to a string symbol) it is a list. The "car" returns the "data" pointer and "cdr" returns the "next" pointer.

If a list expression begins with a symbol it is a "special form" and means essentially a function call of some form. If the list expression begins with another list it's a lambda expression (anonymous function call). The "quote" special form always has a list as it's "cdr".

eval redux

A recursive eval does a depth first search of a tree (until "cond" or "if" where it switches to breadth first). The "C stack" stores the state of this traversal. A queue traversal does exactly the same thing except the queue replaces the stack. What would be a recursive eval becomes a push of the expression pointer onto the eval queue. Consumption of the queue only occurs when atoms are encountered.

If the evaluator determines an expression needs evaluation it pushes the expression pointer on the queue and continues.

When a function call is encountered it must be curried to a function that accepts zero arguments. If more than zero arguments the first argument is eval'd and when done generates a new function.

If arguments push function call on call stack. Push all argument expressions onto value stack in right-to-left order and continue. If value stack contains atom pop function from call stack and apply the atom to the function as first argument. If remaining args in function push new curried function back onto call stack and continue. When function has no more arguments then run it. In this way the "stack frame" is stored as a curried function.

This is elegant but inefficient as each stack frame is a copy of the entire function being evaluated. Lighter way is to create a stack frame to hold a list of evaluated arguments and the function pointer. A function call expression generates this stack frame and pushes all arguments onto the values stack. As long as the stack frame has unapplied slots any evaluation of an expression has it's return value pushed into the stack frame. When the stack frame is full the function is evaluated in full which may or may not result in further function calls and additional stack frames. Actually a stack frame is really an environment. So there is an expression stack and and an environment stack. When an atom is pulled from the expression stack it is stored in the environment on the top of the environment stack.

When function encountered push function pointer on value stack. Then push right-to-left argument expressions. Then continue. When expression is evaluated the result is pushed onto the current environment. When a function pointer is evaluated the arguments are pulled from the environment stack and given names in a new environment (binding). The function body is then pushed on the value stack along with the environment. The renaming step could be skipped and the values set directly in the environment by name.

LOS Z80

32k mem, 32768 bytes, 4 bytes per cons is 8192 cons cells. Requires 2048 bytes of bit flags for in use cells. Or 8192 bytes of ref count ints.

8k rom, 8k ref count, 16k strings, 32k of cons cells. If address less than 32k it's a ref to a string.

New cons: find free in ref count table. Multiply by 4 and add 32k to get cons address. The car is a two byte address. If greater than 32k it is a list, otherwise if greater than 16k it's a string. The cdr is always an address into upper 32k.

The stack is at top of mem, but no "call" is ever made. The stack only ever has 4 byte cons cells in it.