tk's bits

Up to now, instructions that yielded values performed binding, known in other languages as assignment. The instruction BSETQ is introduced to provide simple “copy” binding, which is actually an act of aliasing. It is similar to SETQ, but the current binding method (which places the latest binding at the head of an association list) will yield a different behavior if scope is introduced.

The new instruction replaces the use of an ugly, slow method of creating an alias, which has been

(bcons x nil tmp)
(bcar tmp x-alias)

Instead of being located after the operand atom (in the manner of other instructions), the BSETQ result atom precedes the operand, to make it similar to SETQ. The next anticipated update will allow the use of function calls in BSETQ and IFGO. The binding versions of the functions can then disappear, removing the inconsistency in positioning the result atoms.

Because IFGO is so functionally primitive, it takes quite a bit of work to create subroutine calls. Recursive calls need a stack, and the following code is required to implement a call and return that are usable for recursion:

(bcdr return-point exit)
(bcons exit exit-stack exit-stack)
(ifgo t subr1)
(label return-point)
(label nop)

(label ret)
(bcar exit-stack exit)
(bcdr exit-stack exit-stack)
(ifgo t exit)

Although only one copy of the return code was needed, the call code required generating label names for the return points. We can eliminate the labelling requirement by implementing the equivalent of machine language call instructions that automatically record a return point. I defined a BCALL instruction having two operands. The first operand is the “destination” label atom bound to an instruction list. The second operand is a result atom which is bound to the current instruction list “tail.” The result atom is bound before the destination instructions were executed.

With the new instruction, the call is reduced to one instruction, and the stacking code for recursion is moved to the beginning of the called subroutine, a major refactoring. The exit code remains the same.

(bcall subr1 exit)

(label subr1)
(bcons exit exit-stack exit-stack)

Converting the PRINTB and READB routines to list form and executing them from the second level interpreter is extremely slow. The slow speed of the name search is made worse by the large number of nondestructive rebindings occurring at two levels.

Small test programs on a 1.8 GHz machine is slow but tolerable. But the processor was very bogged down when running a program that read itself in list form and then outputted it back in list form. I had to add console display code, so that progress of the read routine could be seen. It’s highly probable that a faster read routine can be written at the higher level.

With the ability to read and display lists, it’s time to write an interpreter.

With another level of interpreting, it isn’t necessary to hack a binding. Label bindings are created by scanning over the loaded list for label instructions, to create the initial association list. The association list is then handed over to the interpreter contained in the same source file as the list reader.

For my first re-rendering of the interpreter, no predefined bindings are defined, other than the label bindings. There are still the atom-to-print-name bindings that are not accessible to the interpreted code, but accessible to the PRINTB routine used for debugging the interpreter.

So now, I have a system written in quadruple form, loaded by the boot loader, that can load and execute programs in list form. It’s not Lisp yet, but it is a list processing machine capable of reading and writing elementary Lisp syntax.

With the ability to create GC-safe code, we start to implement what we really want.

Once again, I started with a print routine. I recreated, somewhat, the PRINTD subroutine using the new symbolic interpreter code. Then I modified it to accept a different association list of print names. After that, I modified it to create Lisp syntax which is lighter weight than the fully dotted S-expression of PRINTD.

Because there is no arithmetic and no access to address values, anonymous atoms are simply printed as “?”.

WRITEF closes its file when it’s done. However, the Windows CONOUT$ file allows piecemeal I/O to a console display, so the basic algorithm for the new routine, PRINTB, did not change. There is one slight drawback – the CONOUT$ text cannot be redirected to a file from the command line. However, it is possible to copy text from the Command Prompt window.

Of course, I want a corresponding read routine for entering data in list form.

The primary motivation for starting with an imperative Lisp is the parsing of the input. I have written one parser in functional style without global variables. It built the tree from an in-memory string text, and it was very tedious. The symbol table, input source code, parse stack, and the generated partial trees had to all be passed as arguments at each step.

All other parsers I have written (including the one I wrote for this bootstrap) were basically standard stream-oriented parsers that use imperative, sequential code.

The list input routine is in three phases: the first two phases are almost the same as the first two phases of the boot loader. The third phase takes the generated token list and performs a basic recursive descent parse on the list. The boot loader does not recognize a comma as white space, and it does not treat the brackets (parentheses) and period (dot) as single character tokens. The list input routine recognizes these extra nuances in the first phase.

The new list I/O routines are called READB and PRINTB, for bracketed expressions. The routines are asymmetric – the PRINTB routine will not write to a file. The association list for getting the print name of an atom is called NLIST, and the inverse list for selecting an atom from a print name is called SYMTAB.