As we need to create new names as targets for assembly language jump instructions, we might as well rename the existing names into new names. When renaming (alpha conversion), new names can be derived from the original names for debugging, or can be completely new to accommodate target languages, such as assembly language or C.

We still need a symbol table to hold the mappings of original names to new names. An a-list will do the job as a linear search table. Using the base interpreter’s symbol table would have been easier if I had added a primitive function for “interning” symbols. In Scheme, the string->symbol procedure would provide the service.

In my latest version, I wanted to keep the internal representation of strings flexible. So the string->symbol procedure is not built in. I have added a string->quasisymbol procedure, where I defined quasisymbol to mean an uninterned symbol.

It was not hard to add a string object type and write string equality and append functions. Unfortunately, the reader and writer do not know any syntax for inputting and outputting strings, and they are not currently extendable at the Scheme level. Therefore, output can be through a nonstandard procedure, or the hack of converting a string to an uninterned symbol. The writer doesn’t care if a symbol is interned or not – if the value object has a symbol type, it will display what it assumes is a print name.

I opted to rename symbols by adding a prefix. The prefix would be the new name that conforms with target language syntax. By restricting the characters that can be used in the prefix, we can free up a character as a prefix terminator. With the current mini-Scheme, all bound variables will be defined before they are used. With lexical scoping, we can use the inherent stacking of recursion to manage the symbol table. Free variables don’t fare well in the stack processing – they just get a prefix that marks them as free variables. They don’t go into the symbol table, and a second pass is used to give them unique prefixes.

In the following code, the unlisted gen-name-string procedure will create a new name in string format.

(letrec
  ( ; ...

    ;;; must be able to handle improper list
    (rename-and-add
      (lambda (x e)
        (if (null? x)
          e
          (if (not (pair? x))
            (cons
              (list x (make-new-name x))
              e)
            (cons
              (list (car x) (make-new-name (car x)))
              (rename-and-add (cdr x) e))))))

    (make-new-name
      (lambda (x)
        (string->quasisymbol
          (string-append
            (gen-name-string)
            (string #\-)
            (symbol->string x)))))

    (get-new-name
      (lambda (x e)
        (if (assq x e)
          ; get stored new-name
          (car (cdr (assq x e)))
          ; else create a temporary name for free variable
          (string->quasisymbol
            (string-append
              (string #\f #\-)
              (symbol->string x))))))

    ; ...
  )
  ( ... ))

With the above definition of symbol table routines, we just need to find all the places where names need to be defined and changed.

(letrec
  ( ; ...

      (initial-environment
      (lambda ()
        (list
          (list (quote apply)    (make-new-name (quote apply)))
          (list (quote car)      (make-new-name (quote car)))
          (list (quote cdr)      (make-new-name (quote cdr)))
          (list (quote cons)     (make-new-name (quote cons)))
          (list (quote set-cdr!) (make-new-name (quote set-cdr!)))
          (list (quote eq?)      (make-new-name (quote eq?)))
          (list (quote symbol?)  (make-new-name (quote symbol?)))
          (list (quote pair?)    (make-new-name (quote pair?)))
          (list (quote exit)     (make-new-name (quote exit)))
          (list (quote display)  (make-new-name (quote display)))
          (list (quote read)     (make-new-name (quote read)))
          (list (quote write)    (make-new-name (quote write)))
          (list (quote newline)  (make-new-name (quote newline))))))

    (compile-set!
      (lambda (x e)
        (append
          (compile-expr (car (cdr (cdr x))) e)
          (list
            (list (quote store) (get-new-name (car (cdr x)) e))))))

    (compile-lambda
      (lambda (x e)
        (compile-lambda-1 x (rename-the-formals (car (cdr x)) e))))

    (rename-the-formals
      (lambda (f-list e)
        (rename-and-add f-list e)))

    (compile-formals
      (lambda (x e)
        ; added null case here, so that bind-rest-arg
        ;   with a null name is not generated
        (if (null? x)
          (quote ())
          (if (not (pair? x))
            (list
              (list (quote bind-rest-arg) (get-new-name x e)))
            (cons
              (list (quote bind-arg) (get-new-name (car x) e))
              (compile-formals (cdr x) e))))))

    (compile-value
      (lambda (x e)
        (if (symbol? x)
          ; for symbols
          (list
            (list (quote add-arg) (get-new-name x e)))
          ; for literals and quote expressions
          (list
            (list (quote add-arg) x)))))

    ; ...
  )
  ( ... ))

(letrec
  ((compile
    (lambda (x e)
      (compile-expr x e)))

   (compile-expr
     (lambda (x e)
       (if (null? x)
         (list (quote ***empty-combination***))
         (if (not (pair? x))
           (compile-value x e)
           (if (eq? (car x) (quote quote))
               (compile-value x e)
               (if (eq? (car x) (quote lambda))
                   (compile-lambda x e)
                   (compile-combination x e)))))))

   (compile-lambda
     (lambda (x e)
       (append
         (list
           (quote (bind-args)))
         (compile-expr (car (cdr (cdr x))) e)
         (list
           (quote (return))))))

   (compile-combination
     (lambda (x e)
       (append
         (list
           (quote (push-arglist)))
         (compile-args (cdr x) e)
         (list
           (quote (pop-arglist))
           (list (quote call) (car x))))))

    ; ...
  )
  (...))

Scheme’s lexical scoping of nested lambda expressions is practically the same as lexical scoping in traditional “block structured” languages such as Algol or Pascal. To avoid ambiguity, we will replace the traditional term “procedure” with “routine” in the following description.

If we look at recursion, there will be several bindings for each variable, one for each invocation of a recursive routine. A routine embedded in the recursive routine must receive the correct set of bindings for the “global” or free variables.

The correct set of bindings is captured when a routine reference is created. For some languages, this only occurred when a routine was called or passed as a parameter. When passed as a parameter, the routine reference for an “inner” routine would be placed in a procedure descriptor, which also contained a reference to the desired variable bindings (or in conventional terms, storage). The procedure descriptor is fundamentally a representation of a closure or a funarg.

We change the code to create a procedure descriptor for a lambda expression. We add the begin-proc instruction which jumps to the corresponding end-proc instruction.

The following implementation also places argument allocation within the procedure code, rather than in the argument list code. The binding of arguments can be implemented with store instructions.

We also extend argument evaluation to include the expression in the operator/function position. The function of the pop-arglist instruction is combined with the call instruction, making a new instruction call-indirect, which will use the procedure descriptor that was added to the “argument list”. We rename push-arglist to create-arglist, as we are no longer revealing the implementation to be a stack.

(letrec
  ( ; ...
    (compile-lambda
      (lambda (x e)
        (append
          (list
            (quote (make-proc-descriptor))
            (quote (begin-proc))
            (quote (allocate-args))
            (quote (bind-args)))
          (compile-expr (car (cdr (cdr x))) e)
          (list
            (quote (return))
            (quote (end-proc))))))

    (compile-combination
      (lambda (x e)
        (append
          (list
            (quote (create-arglist)))
          (compile-args x e)
          (list
            (quote (call-indirect))))))

   ; ...
  )
  (...))

We expand the bind-args instruction by explicitly naming the arguments. We also handle the “&rest” argument, and rename the allocate-args instruction to create-local-env. The create-local-env instruction will create storage for arguments and a link to the “local” environment associated with the previous lexical scope. The procedure descriptor will provide the local environment being linked to.

(letrec
  ( ; ...
    (compile-lambda
      (lambda (x e)
        (append
          (list
            (quote (make-proc-descriptor))
            (quote (begin-proc))
            (quote (create-local-env)))
          (compile-formals (car (cdr x)) e)
          (compile-expr (car (cdr (cdr x))) e)
          (list
            (quote (return))
            (quote (end-proc))))))

    (compile-formals
      (lambda (x e)
        (if (not (pair? x))
          (list
            (list (quote bind-rest-arg) x))
          (cons
            (list (quote bind-arg) (car x))
            (compile-formals (cdr x) e)))))

   ; ...
  )
  (...))

The set! expression is fairly straightforward.

(letrec
  ( ;...

   (compile-expr
     (lambda (x e)
       (if (null? x)
         (list (quote ***empty-combination***))
         (if (not (pair? x))
           (compile-value x e)
           (if (eq? (car x) (quote quote))
               (compile-value x e)
               (if (eq? (car x) (quote lambda))
                   (compile-lambda x e)
                   (if (eq? (car x) (quote set!))
                     (compile-set! x e)
                     (compile-combination x e))))))))

    (compile-set!
      (lambda (x e)
        (append
          (compile-expr (car (cdr (cdr x))) e)
          (list
            (list (quote store) (car (cdr x)))))))

   ; ...
  )
  (...))

(letrec
  ((compile
     (lambda (x e)
       (if (null? x)
         (quote ***empty-combination***)
         (if (pair? x)
           (if (eq? (car x) (quote quote))
             (compile-value x e)
             (compile-combination x e))
           (compile-value x e)))))
   (compile-value
     (lambda (x e)
       (list (list (quote load) x))))
   (compile-combination
     (lambda (x e)
       (append
         (compile-args (cdr x) e)
         (list (list (quote call) (car x))))))
   (compile-args
     (lambda (x e)
       (if (null? x)
         (quote ())
         (append (compile (car x) e) (compile-args (cdr x) e)))))
  )
  (...))

In addition, if we plan to later adopt the Scheme convention of converting to CPS, values can only be specified in argument lists. If we also plan on continuing to use linked lists to pass arguments, we can evaluate arguments in right-to-left order. (It’s more efficient to add to the head of a list, than to the tail of a list.) Right-to-left order also fits in with typical C calling conventions when stacks grow from higher addresses towards lower addresses.

(letrec
  ((compile
     (lambda (x e)
       (if (null? x)
         (quote ***empty-combination***)
         (if (pair? x)
           (if (eq? (car x) (quote quote))
             (compile-value x e)
             (compile-combination x e))
           (compile-value x e)))))
   (compile-value
     (lambda (x e)
       (list (list (quote add-arg) x))))
   (compile-combination
     (lambda (x e)
       (append
         (list (quote (push-arglist)))
         (append    ; - splice -
           (compile-args (cdr x) e)
           (list
             (quote (pop-arglist))
             (list (quote call) (car x)))))))
   (compile-args
     (lambda (x e)
       (if (null? x)
         (quote ())
         (append     ; - right-to-left order -
           (compile-args (cdr x) e)
           (compile (car x) e)))))
  )
  (...))

We’ve now added the presence of a stack of argument lists. This is one way to get “proper tail calls”. The pop-arglist instruction moves the argument list from stack space to heap space, so neither the caller nor the callee need to schedule deallocation for the arguments. If we stay with the argument list as a linked list, the instruction add-args will simply cons the value argument and the list at the top of the argument stack, and then replace the list at the top of the stack with the new list.

If the expression is the body of a top-level lambda expression, we just need to add argument binding and a return instruction. Because the argument list is no longer on a stack (i.e., the stack is already balanced), we can, at a later time, optimize the two-instruction sequence, call-return, to a jump instruction.

(letrec
   ((compile-body
      (lambda (x e)
        (append
          (list (quote (bind-args)))
          (append    ; -splice-
            (compile-expr x e)
            (list (quote (return)))))))
    (compile-expr
      (lambda (x e)
        (if (null? x)
          (list (quote ***empty-combination***))
          (if (pair? x)
            (if (eq? (car x) (quote quote))
                (compile-value x e)
                (compile-combination x e))
            (compile-value x e)))))
    (compile-value
      (lambda (x e)
        (list (list (quote add-arg) x))))
    (compile-combination
      (lambda (x e)
        (append
          (list (quote (push-arglist)))
          (append    ; -splice-
            (compile-args (cdr x) e)
            (list
              (quote (pop-arglist))
              (list (quote call) (car x)))))))
    (compile-args
      (lambda (x e)
        (if (null? x)
          (quote ())
          (append
            (compile-args (cdr x) e)
            (compile-expr (car x) e)))))
  )
  (...))

At least three items are left to deal with: closures (especially, for the case of nested lambda expressions), conditionals, and assignments.

The first pass here builds something familiar. Compilation of a variable or constant consists of mapping a bare variable or constant to a “load value” instruction. A list (representing a combination) will, at first, be mapped to a “call” instruction.

(letrec
  ((compile
     (lambda (x e)
       (if (null? x)
         (quote ***empty-combination***)
         (if (pair? x)
           (list (quote call) x)
           (list (quote load) x)))))
  )
  (...))

When the expression x is a combination, (car x) is the function name, which we use in the actual “call” instruction. We actually want to call the function AFTER the arguments are evaluated:

(letrec
  ((compile
     (lambda (x e)
       (if (null? x)
         (quote ***empty-combination***)
         (if (pair? x)
           (cons
             (compile-args (cdr x) e)
             (list (list (quote call) (car x))))
           (list (quote load) x)))))
   (compile-args
     (lambda (x e)
       (list (quote load-arglist) x))))
  )
  (...))

We then recurse to compile the argument list.

(letrec
  ((compile
     (lambda (x e)
       (if (null? x)
         (quote ***empty-combination***)
         (if (pair? x)
           (cons
             (compile-args (cdr x) e)
             (list (list (quote call) (car x))))
           (list (quote load) x)))))
   (compile-args
     (lambda (x e)
       (if (null? x)
         (quote ())
         (cons (compile (car x) e) (compile-args (cdr x) e)))))
  )
  (...))

At which point, a little rearranging of list levels is required to create the “flat” structure of an assembly language.

(letrec
  ((compile
     (lambda (x e)
       (if (null? x)
         (quote ***empty-combination***)
         (if (pair? x)
           (append
             (compile-args (cdr x) e)
             (list (list (quote call) (car x))))
           (list (list (quote load) x))))))
   (compile-args
     (lambda (x e)
       (if (null? x)
         (quote ())
         (append (compile (car x) e) (compile-args (cdr x) e)))))
  )
  (...))

We just need to add quoted values:

(letrec
  ((compile
     (lambda (x e)
       (if (null? x)
         (quote ***empty-combination***)
         (if (pair? x)
           (if (eq? (car x) (quote quote))
             (list (list (quote load) x))
             (append
               (compile-args (cdr x) e)
               (list (list (quote call) (car x)))))
           (list (list (quote load) x))))))
   (compile-args
     (lambda (x e)
       (if (null? x)
         (quote ())
         (append (compile (car x) e) (compile-args (cdr x) e)))))
  )
  (...))

The generated code is good for a stack-based computer, with a control stack separate from the data stack. As Scheme requires more than stack capabilities, we will need to modify this a little.

The apply procedure, as implemented, knows of only two types of procedures, the machine/native code procedures that provide the foundation for the Scheme system, and the S-expression procedure, for which we can define a traditional S-expression evaluator/interpreter.

The eval procedure, as implemented, is an S-expression interpreter. It cannot interpret executable code in any other form.

The apply procedure is the interpreter selector. In this role, the procedure provides the necessary data marshalling services — making this the natural place to include a foreign function interface (FFI). The ultimate interpreter is the hardware that is called the processor, CPU, and other synonymous names.

Just recently I modified a Scheme version of eval to go further — it performs a code transformation (macro expansion) before proceeding with interpretation. Because of the code transformation step, it’s clear that eval is not necessarily the interpreter — the code transformation could actually include a compilation to native code or to pseudo-code. The Anatomy of Lisp pointedly demonstrates this by providing more than one version of S-expression interpreters, each with a different set of formal arguments, and then providing definitions of eval that call each version of the “real” interpreter.

One of the happy results of this version is that it doesn’t matter if the interpreted code is in CPS or not. Not even for the machine language procedures, the m-proc. The trick is that apply does not stack a return address — that is done by the recursive argument evaluation performed by the eval interpreter. Thus a return from an m-proc will usually return to where the interpreter is inserting the return value into an argument list. The ultimate return point is the REPL. To “tail call’ back into the Scheme system, the m-proc merely needs to provide the appropriate apply arguments and then jump to the machine coded apply routine.

To enable growth of the system, I added a save procedure to create an image file, and provided an option to load an image on startup. To retain definitions, I added a procedure to place a name-value binding in the “top level” environment.

The %digit-multiply-add primitive is provided for radix and internal representation independence. It has four arguments. The first two digits are the multiplier and multiplicand digits. The third digit is used to provide the carry from a previous multiply-and-add, and the fourth digit can be used to provide a digit from the product being accummulated.

Multiplication is simpler than subtraction – with the choice of sign+magnitude representation, there is no need to convert the magnitude to or from complemented form.

Because it was simpler to do, and easier to verify, the current added procedures, listed below, do not use the fourth argument (it’s always 0). A partial product is created by multiplying one operand by a single digit from the other operand. Each partial product is added to an accummulated product, and the result is passed on to the next partial product step (function application). To align the partial products properly, we add a least significant 0 digit to the current multidigit operand and pass it on to the next step as the new multidigit operand.

    (multiply
      (lambda (x y)
        (cond
          ( (number? x)
            (cond
              ( (number? y) (mpy-num x y) )
              ( #t          '***undefined*** )  ))
          ( #t '***undefined*** )  )))

    (mpy-num
      (lambda (x y)
        (%list->number (mpy-num1 (%number->list x) (%number->list y)))))

    (mpy-num1
      (lambda (x y)
        (cond
          ( (eq? (car x) #\0)     (list #\0) )
          ( (eq? (car y) #\0)     (list #\0) )
          ( (eq? (car x) (car y)) (cons #\+ (mpy-magnitude (cdr x) (cdr y))) )
          ( #t                    (cons #\- (mpy-magnitude (cdr x) (cdr y))) ))))

    (mpy-magnitude
      (lambda (x y)
        (mpy-mag1 x y)))

    (mpy-mag1
      (lambda (x y)
        (cond
          ( (null? x) (list digit0) )
          ( #t
            (mpy-mag2
              (cdr x)
              (cons digit0 y)
              (mpy-mag3 (car x) y digit0) )))))

    (mpy-mag2
      (lambda (x y partial)
        (cond
          ( (null? x) partial )
          ( #t
            (mpy-mag2
              (cdr x)
              (cons digit0 y)
              (add-magnitude
                (mpy-mag3 (car x) y digit0)
                partial))  ))))

    (mpy-mag3
      (lambda (d y carry)
        (cond
          ( (null? y) (list carry) )
          ( #t
            (cons
              (car (%digit-multiply-add d (car y) carry digit0))
              (mpy-mag3
                d
                (cdr y)
                (car(cdr
                  (%digit-multiply-add d (car y) carry digit0))))) ))))

One major constraint in the following code is that equivalent digits must be equal in the eq? sense.

(letrec
    ((digit0 (%digit0))
    (digit1 (car(cdr (%digit-sum
                       (%digit-complement (%digit0))
                       (%digit-complement (%digit0))
                       (%digit0)))))
    (max-digit (%digit-complement (%digit0)))

    (add
      (lambda (x y)
        (cond
          ((number? x)
            (cond
              ((number? y) (add-num x y))
              ( #t '***undefined***)))
          (#t '***undefined***))))

    (subtract
      (lambda (x y)
        (cond
          ((number? x)
            (cond
              ((number? y) (sub-num x y))
              (#t '***undefined***)))
          (#t '***undefined***))))

    (negate
      (lambda (x)
        (cond
           ((number? x)
             (%list->number (negate-list (%number->list x))))
           (#t '***undefined***))))

    (add-num
      (lambda (x y)
        (%list->number (add-num1 (%number->list x) (%number->list y)))))

    (sub-num
      (lambda (x y)
        (%list->number (add-num1 (%number->list x) (negate-list (%number->list y))))))

    (negate-list
      (lambda (x)
        (cond
          ((eq? (car x) #\0) x)
          ((eq? (car x) #\+) (cons #\- (cdr x)))
          ((eq? (car x) #\-) (cons #\+ (cdr x)))
          (#t '***undefined***))))

    (add-num1
      (lambda (x y)
        (cond
          ((eq? (car x) #\0) y)
          ((eq? (car y) #\0) x)
          ((eq? (car x) (car y)) (cons (car x) (add-magnitude (cdr x) (cdr y))))
          ((eq? (car x) #\+) (adjust-mag1 (sub-magnitude (cdr x) (cdr y))))
          ((eq? (car x) #\-) (adjust-mag1 (sub-magnitude (cdr y) (cdr x))))
          (#t '***undefined***))))

    (add-magnitude
      (lambda (x y)
        (add-mag1 x y)))

    (sub-magnitude
      (lambda (x y)
        (sub-mag1 x y)))

    (add-mag1
      (lambda (x y)
        (cond
          ((null? x)
            (cond
              ((null? y) '())
              (#t (add-mag2 (%digit-sum digit0 (car y)  digit0) (cdr x) (cdr y)))))
          ((null? y) (add-mag2 (%digit-sum (car x) digit0  digit0) (cdr x) (cdr y)))
          (#t (add-mag2 (%digit-sum (car x) (car y) digit0) (cdr x) (cdr y))))))

    (add-mag2
      (lambda (d-sum x y)
        (cond
          ((null? x)
            (cond
              ((null? y)
                (cond
                  ((eq? (car(cdr d-sum)) digit0) (list (car d-sum)))
                  (#t d-sum)))
              (#t (add-next d-sum (list digit0) y))))
          ((null? y) (add-next d-sum x (list digit0)))
          (#t (add-next d-sum x y)))))

    (add-next
      (lambda (d-sum x y)
        (cons
          (car d-sum)
          (add-mag2
            (%digit-sum (car x) (car y) (car(cdr d-sum)))
            (cdr x)
            (cdr y)))))

    (adjust-mag1
      (lambda (x)
        (cond
          ((neg-mag? x) (cons #\- (trim-mag1 (recomplement x))))
          (#t (check-zero (cons #\+ (trim-mag1 x)))))))

    (check-zero
      (lambda (x)
        (cond
          ((null? (cdr x)) '(#\0))
          (#t x))))

    (trim-mag1
      (lambda (x)
        (reverse (behead-zero (cdr (reverse x))))))

    (behead-zero
      (lambda (x)
        (cond
          ((eq? (car x) digit0) (behead-zero (cdr x)))
          (#t x))))

    (neg-mag?
      (lambda (x)
        (cond
          ((null? (cdr x)) (eq? (car x) max-digit))
          (#t (neg-mag? (cdr x))))))

    (recomplement
      (lambda (x)
        (sub-mag1 '() x)))

    (sub-mag1
      (lambda (x y)
        (cond
          ((null? x)
            (cond
              ((null? y) (list digit0))
              (#t (sub-mag2
                    (%digit-sum digit0  (%digit-complement (car y)) digit1)
                    (list digit0)
                    (cdr y)))))
          ((null? y) (sub-mag2
                       (%digit-sum (car x) (%digit-complement digit0) digit1)
                       (cdr x)
                       (list digit0)))
          (#t (sub-mag2
                (%digit-sum (car x) (%digit-complement (car y)) digit1)
                (cdr x)
                (cdr y))))))

    (sub-mag2
      (lambda (d-sum x y)
        (cond
          ((null? x)
            (cond
              ((null? y) (list
                           (car d-sum)
                           (car (%digit-sum digit0 max-digit (car(cdr d-sum))))))
              (#t (sub-next d-sum (list digit0) y))))
          ((null? y) (sub-next d-sum x (list digit0)))
          (#t (sub-next d-sum x y)))))

    (sub-next
      (lambda (d-sum x y)
        (cons
          (car d-sum)
          (sub-mag2
            (%digit-sum (car x) (%digit-complement (car y)) (car(cdr d-sum)))
            (cdr x)
            (cdr y))))))
  ; ...
)

The “soft” format is a list. The first item is the sign in character form, and the rest of the list are the digits in little-endian order.

With the new procedures, I revisited the add and subtract code, and altered it to put conversion to and from the internal format at the same application (i.e., call or invoke) level.

I also added two procedures, %digit-sum and %digit-complement, to highlight the fact that the radix used for “hard” encoding does not affect the general algorithm at all. Although I am using decimal now, the radix could be (decimal) 4 294 967 296, which is what would be expected from a 32-bit implementation.

The add-digit procedure %digit-sum began as a two argument function. With digits as operands and a list as output, adding three numbers (to include the carry) was a bit ugly. The solution was to redefine %digit-sum as a three argument function.

The %digit-sum procedure replaces a Scheme conditional tree. The internal routine eliminates a lot of argument list cons-ing. The only cons-ing needed is for producing the return value. Arithmetic is used to create the sum, speeding it up even more. As a result, I am expecting the new arithmetic to be competitive with the floating-point arithmetic of some old versions of Basic running on their original (slow) microprocessors. The up side: big-num capability. The down-side: fractions are not yet implemented.

The %digit-complement is the (radix – 1) complement. In my decimal radix system, that would be the nine’s complement. If I had used a binary radix, it would have been the one’s complement.

That leaves three items that were not implemented in assembly language: digit0, digit1, and max-digit (replacement for digit9). The updated algorithm is derived from using digit0 and digit1 as the carry digits, and digit0 and max-digit as the “sign extension” digits. Only digit0 needs to be implemented, with the others derived from digit0.

As a result, I went back to the working base interpreter, and implemented some type predicates and some data conversion procedures in assembly language. Two tables are used to expand the library of primitive procedures. One is the dispatch table, which is indexed by number, so that there are no external names hard-bound to the primitives. The second table is the initialization table that binds names to symbol locations and dispatch indexes. This makes it easy to add new primitives.

Rather than treating characters and octets (aka bytes) as separate data types, I have gone to Unix mode and equated them. This also means that octet strings and text strings are synonymous.

This is counter to the growing use of Unicode. The problem with Unicode is that a valid Unicode-encoded text is a structured data type, rather than a simple sequence of same-sized data.

The base display procedure was changed to output octets as byte values directly to the console display, rather than a number in text form. The base read procedure was changed to input string and character literals.

The purpose of adding type predicates such as symbol?, number?, and char? is to divorce the high level Scheme code from the underlying data structures that are hard-coded by the assembly language code. This allows one to avoid exposing the built-in data structures, eliminating ugly low level manipulations such as the use of (car ’symbol) to get the anonymous type mark associated with symbols.

The data conversion procedures are added for the same purpose. You can build up the symbols from integer values with these procedures:

• integer->char
• list->string
• string->symbol

and break down symbol names with inverse procedures – all without exposing the ugly details of an inefficient implementation.

The divorce also allows creating code which is easier to port to other Scheme systems. Most Schemes will be far more efficient than the version I have created.