Archive for June, 2008

Scheme procedures with variable number of arguments

Monday, June 30th, 2008

The pcall procedure has been rewritten to a cleaner form. Some repetitive expressions are now evaluated only once as a procedure argument, avoiding the use of set!. Some raw implementation details are still visible, as I don’t yet want to define or use a lot of procedures…

    (pcall
      (lambda (x)
        (evapply (car x) (cdr x))
      )
    )

    (evapply
      (lambda (def args)
        (cond
          ( (eq? (first def) prim-mark)   (prim-call (second def) args) )
          ( (eq? (first def) proc-mark)   (proc-call (cdr(cdr(cdr def))) (second def) (third def) args) )
          ( #t                            '***undefined*** )
        )
      )
    )

    (proc-call
      (lambda (body env formals args)
        (evseq '***undefined*** body (append (pair formals args) env))
      )
    )

    (prim-call
      (lambda (id args)
        (cond
          ( (eq? id 'car)             (car  (first args)) )
          ( (eq? id 'cdr)             (cdr  (first args)) )
          ( (eq? id 'cons)            (cons (first args) (second args)) )
          ; -- etc. --
          ( #t                        '***undefined*** )
        )
      )
    )

I am still thinking about tail call optimization, and realizing the need to abstract/encapsulate the whole argument binding process. So pair becomes bind-args, and the binding of arguments and the extension of an environment becomes a combined function. However, instead of calling it pairlis, I call it add-args.

It turns out that adding the feature of variable number of procedure arguments is easy. One extra test in bind-args is all that’s needed to handle both Scheme syntaxes for this feature. In case you’re not familiar with Scheme syntax, the two syntaxes are…

; z (which can be any identifier) receives the tail of the evaluated argument list
( lambda z <body> )  ; no required arguments
( lambda ( <sequence of identifiers> . z ) <body> ) ; the arguments before "." are required

After looking at my assembly code, it looks like it can be added to the base interpreter without a lot of hassle. So here is the little Scheme code with renamed procedures and the handling of variable length argument lists. (Well, almost. Due to the implementation of (car ′()) and (cdr ′()), required arguments are not enforced anywhere.)…

    (proc-call
      (lambda (body env formals args)
        (evseq '***undefined*** body (add-args formals args env))
      )
    )

    (add-args
      (lambda (formals args env)
        (append (bind-args formals args) env)
      )
    )

    (bind-args
      (lambda (x y)
        (cond
          ( (null? x)    '() )
          ( (symbol? x)  (cons (cons x y) '()) )
          ( #t           (cons (cons (car x) (car y)) (bind-args (cdr x) (cdr y))) )
        )
      )
    )

After letrec; map and for-each

Saturday, June 28th, 2008

The letrec expression is now implemented in the base interpreter. That, plus sequential expressions in cond and lambda, makes Lisp an actual pleasure to work with.

The letrec expression places declaration and definition together in one location, rather than two. This removes pain from the task of adding procedures, and we can discard the ugly hack of mutating argument variables. As an aside, I’ve been peeking at Guy Steele’s call/cc Eval and just noticed that he uses rplacd, the traditional name of set-cdr!, to implement letrec.

Sequential expressions make it easy to add debugging expressions. Sometimes I want to splice and dice the arguments to make sure I’m doing it correctly. The REPL, by itself, just isn’t sufficient for the task. For example, my expressions might work correctly, but only if I receive the correct data. There’s currently no breakout facility, so it’s nice to be able to inspect arguments and display trace markers, without creating wrapper procedures or wrapper expressions.

A little experimentation with basic versions of map and for-each (only functions with one argument are accepted) reminded me of a design flaw. Unlike eval, the base interpreter is not designed to pass built-in procedures as arguments.

Scheme doesn’t care which order the elements of the list argument for map are selected. It can be processed either left-to-right or right-to-left. The for-each procedure uses sequenced expressions to force left-to-right processing of the list elements…

    (map
      (lambda (f x)
        (cond
          ( (null? x) '() )
          ( #t        (cons (f (car x)) (map f (cdr x))) )
        )
      )
    )

    (for-each
      (lambda (f x)
        (cond
          ( (null? x) '() )
          ( #t        (f (car x)) (for-each f (cdr x)) )
        )
      )
    )

Under the base interpreter, a wrapper procedure is needed to evaluate a built-in primitive…

  (letrec
    (
      ( displayx (lambda (x) (display x)) )
    )

    ( for-each displayx '(a b c d) )
  )

As this is a simple workaround, the goal is to build a compiler before fixing the flaw. (Functionality before repairs – does that sound familiar?) The higher level eval procedure, with the support environment named init-env, already fixes the flaw. So if performance is not a problem, that can be used until the compiler can be created for the little Lisp/Scheme. Since the two interpreters share the same data structure for procedures, it just requires adding bindings to init-env to make the map and for-each procedures available to eval.

Defining with letrec

Friday, June 27th, 2008

The letrec expression provides a more elegant syntax for naming recursive functions than the set! expression. The define expression is better, but it has nonuniform usage, depending on whether it is evaluated at the top level or not. Because the “internal” define semantics references letrec (Rev 6 changes this to letrec*, which has sequencing semantics), letrec is defined first.

When letrec is later implemented in the base interpreter, we won’t need this separated declaration code segment…

  (lambda (repl eval ev
           evsyntax evcond evletrec evletvar evletexp evletbind
           evset lookup bound-value
           pcall pair append evlist evseq make-proc
           first second third
           prim-mark proc-mark prim-syntax-mark init-env
           symbol? constant?)

Except for left-to-right sequencing and procedure application, much of the Lisp/Scheme code reflects the assembly language code. At the assembly language level, left-to-right sequencing is done by rewriting (mutation). The tougher bugs were due to forgetting to make copies of procedure elements before mutating.

I mention the similarity to the assembly language code because some of the existing code could be described more concisely using the Scheme map procedure. I am still at the “human compiler” stage and, at the moment, I’m more confident in translating explicit recursion to assembly code than in translating map usage.

Given a list of initializations x to create, we can extract a list of variables to define…

    (set! evletvar
      (lambda (x)
        (cond
          ( (eq? x '()) '() )
          ( #t          (cons
                          (cons (car(car x)) '())
                          (evletvar (cdr x))
                        )
          )
        )
      )
    )

We add the variables to the environment before we evaluate any initialization expressions. We also split up the letrec expression…

    (set! evsyntax
      (lambda (syn-def x env)
        (cond
          (
            (eq? (first syn-def) prim-syntax-mark)
            (cond
              ( (eq? (second syn-def) 'quote)     (second x) )
              ( (eq? (second syn-def) 'cond)      (evcond (cdr x) env) )
              ( (eq? (second syn-def) 'set!)      (evset
                                                    (lookup (second x) env)
                                                    (ev (third x) env)
                                                  )
              )
              ( (eq? (second syn-def) 'letrec)    (evletrec
                                                    (second x)
                                                    (cdr(cdr x))
                                                    (append (evletvar (second x)) env)
                                                  )
              )
              ( (eq? (second syn-def) 'lambda)    (make-proc x env) )
              ( #t                                '***undefined*** )
            )
          )
          ( #t  (pcall (evlist x env)) )
        )
      )
    )

Then we evaluate the initializing expressions and bind them with set-cdr! (another very low level detail)…

    (set! evletrec
      (lambda (bindings seq env)
        (evletbind env (evletexp bindings env))
        (evseq '***undefined*** seq env)
      )
    )

    (set! evletexp
      (lambda (bindings env)
        (cond
          ( (eq? bindings '()) '() )
          ( #t                 (cons
                                 (ev (second (car bindings)) env)
                                 (evletexp (cdr bindings) env)
                               )
          )
        )
      )
    )

    (set! evletbind
      (lambda (flist arglist)
        (cond
          ( (eq? arglist '()) '() )
          ( #t                (set-cdr! (car flist) (car arglist))
                              (evletbind (cdr flist) (cdr arglist))
          )
        )
      )
    )

Adding back file I/O

Wednesday, June 25th, 2008

To make the little Scheme language more useful, I’m adding back byte-by-byte file I/O. To keep things simple in the absence of arithmetic, only one input file and one output file can be open simultaneously. The procedures are called open-input, open-output, read-octet, write-octet, close-input, and close-output. The console I/O, implemented with read and display, remains a separate set of I/O ports.

To generate arbitrary bytes, integer->octet is implemented. The inverse conversion, octet->integer is also implemented.

No code is listed here for adding the new procedures, as it simply involves expanding init-env and pcall in a straightforward fashion.

However, we will show the code for handling constants. Just as in full Scheme and Common Lisp, we don’t want to require the quoting of numbers. More implementation details of the base interpreter revealed…

    (set! constant?
      (lambda (x)
        (cond
          ( (eq? (car x) (car #t))                    #t )  ; boolean?
          ( (eq? (car x) (car  1))                    #t )  ; number?
          ( (eq? (car x) (car(cdr 'car)))             #t )  ; octet-string?
          ( (eq? (car x) (car (integer->octet 65)))   #t )  ; octet?
          ( #t                                        #f )
        )
      )
    )

    (set! ev
      (lambda (x env)
        (cond
          ( (constant? x)              x )
          ( (symbol? x)                (bound-value (lookup x env)) )
          ( (symbol? (car x))          (evsyntax (cdr (lookup (car x) env)) x env) )
          ( #t                         (pcall (evlist x env)) )
        )
      )
    )

Scheme assignment, new evaluation of primitives

Sunday, June 22nd, 2008

We round out our basic Scheme implementation with assignments. In order to implement set!, we will add set-cdr! to our interpreter. set-car! will also be added for symmetry. Strangely enough, Scheme does not define a set-pair! procedure.

In addition to providing named procedures and recursion, the set! expression will allow the introduction of list circularities, including a circularity via the environment of a procedure object. For this reason, the display procedure in the base interpreter refuses to display a procedure object. We can prevent display from rendering our procedures by using the same marker. One more implementation detail of the base interpreter revealed…

    (set! proc-mark (car (lambda (x) x)))

We need to modify our lookup procedure to return bindings instead of just values…

    (set! lookup
      (lambda (v env)
        (cond
          ( (eq? env '())           '***undefined*** )
          ( (eq? v (car (car env))) (car env) )
          ( #t                      (lookup v (cdr env)) )
        )
      )
    )

    (set! bound-value
      (lambda (binding)
        (cond
          ( (eq? binding '***undefined***) '***undefined*** )
          ( #t (cdr binding) )
        )
      )
    )

    (set! ev
      (lambda (x env)
        (cond
          ( (eq? x #t)                 #t )
          ( (eq? x #f)                 #f )
          ( (symbol? x)                (bound-value (lookup x env)) )
          ( (eq? (first x) 'quote)     (second x) )
          ( (eq? (first x) 'cond)      (evcond (cdr x) env) )
          ( (eq? (first x) 'lambda)    (make-proc x env) )
          ( (eq? (first x) 'car)       (car  (ev (second x) env)) )
          ( (eq? (first x) 'cdr)       (cdr  (ev (second x) env)) )
          ( (eq? (first x) 'cons)      (cons (ev (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'eq?)       (eq?  (ev (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'read)      (read) )
          ( (eq? (first x) 'display)   (display (ev (second x) env)) )
          ( (eq? (first x) 'set-car!)  (set-car! (ev (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'set-cdr!)  (set-cdr! (ev (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'exit)      (exit) )
          ( #t                         (pcall (evlist x env)) )
        )
      )
    )

With lookup returning a binding, the binding can be mutated with set-cdr!. Because the pair holding the binding is shared, mutating it will cause the change to be seen at all visible levels, as expected. R5RS does not define if the expression argument is evaluated when the set! variable argument is unbound. The following always evaluates the expression argument…

    (set! evset
      (lambda (binding x)
        (cond
          ( (eq? binding '***undefined***) '***undefined*** )
          ( #t                             (set-cdr! binding x) '***undefined*** )
        )
      )
    )

    (set! ev
      (lambda (x env)
        (cond
          ( (eq? x #t)                 #t )
          ( (eq? x #f)                 #f )
          ( (symbol? x)                (bound-value (lookup x env)) )
          ( (eq? (first x) 'quote)     (second x) )
          ( (eq? (first x) 'cond)      (evcond (cdr x) env) )
          ( (eq? (first x) 'set!)      (evset (lookup (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'lambda)    (make-proc x env) )
          ( (eq? (first x) 'car)       (car  (ev (second x) env)) )
          ( (eq? (first x) 'cdr)       (cdr  (ev (second x) env)) )
          ( (eq? (first x) 'cons)      (cons (ev (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'eq?)       (eq?  (ev (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'read)      (read) )
          ( (eq? (first x) 'display)   (display (ev (second x) env)) )
          ( (eq? (first x) 'set-car!)  (set-car! (ev (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'set-cdr!)  (set-cdr! (ev (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'exit)      (exit) )
          ( #t                         (pcall (evlist x env)) )
        )
      )
    )

Most of the functionality of the base interpreter is now implemented. Numbers, strings, and octets are not yet implemented in the high level interpreter. As we are implementing the high level read using the base interpreter’s read, unsigned numbers can be inputted to the system. Strings and octets cannot be inputted, but they can be extracted from symbols.

Next, the primitives are defined in a way that allows redefinition. This feature is not available from the base interpreter. The base interpreter will give higher priority to the built-in procedures. Redefinition would allow us to replace a primitive with a richer version.

First, the primitive procedure definitions are put into an initial environment…

    (set! prim-mark 'prim-mark)

    (set! init-env
      '(
        (car       prim-mark  car)
        (cdr       prim-mark  cdr)
        (cons      prim-mark  cons)
        (eq?       prim-mark  eq?)
        (read      prim-mark  read)
        (display   prim-mark  display)
        (set-car!  prim-mark  set-car!)
        (set-cdr!  prim-mark  set-cdr!)
        (exit      prim-mark  exit)
       )
    )

    (set! repl
      (lambda ()
        (display (eval (read) init-env))
        (repl)
      )
    )

Because the arguments are evaluated by evlist and the environment that evlist uses is not needed by the procedure body, the evaluation of primitives is simplified when we move the evaluation to pcall.

    (set! pcall
      (lambda (x)
        (cond
          (
            (eq? (first (first x)) prim-mark)
            (cond
              ( (eq? (second (first x)) 'car)       (car  (second x)) )
              ( (eq? (second (first x)) 'cdr)       (cdr  (second x)) )
              ( (eq? (second (first x)) 'cons)      (cons (second x) (third x)) )
              ( (eq? (second (first x)) 'eq?)       (eq?  (second x) (third x)) )
              ( (eq? (second (first x)) 'read)      (read) )
              ( (eq? (second (first x)) 'display)   (display (second x)) )
              ( (eq? (second (first x)) 'set-car!)  (set-car! (second x) (third x)) )
              ( (eq? (second (first x)) 'set-cdr!)  (set-cdr! (second x) (third x)) )
              ( (eq? (second (first x)) 'exit)      (exit) )
              ( #t                                  '***undefined*** )
            )
          )
          (
            (eq? (first (car x)) proc-mark)
            (evseq
              '***undefined***
              (cdr(cdr(cdr (car x))))
              (append (pair (third (car x)) (cdr x)) (second (car x)))
            )
          )
          ( #t  '***undefined*** )
        )
      )
    )

    (set! ev
      (lambda (x env)
        (cond
          ( (eq? x #t)                 #t )
          ( (eq? x #f)                 #f )
          ( (symbol? x)                (bound-value (lookup x env)) )
          ( (eq? (first x) 'quote)     (second x) )
          ( (eq? (first x) 'cond)      (evcond (cdr x) env) )
          ( (eq? (first x) 'set!)      (evset (lookup (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'lambda)    (make-proc x env) )
          ( #t                         (pcall (evlist x env)) )
        )
      )
    )

Similarly, we can make the syntax keywords potentially redefinable. We don’t yet have a way to define new syntax expressions yet, but we can still separate them for future modification. Syntax expressions always start with an identifier, the keyword. The new code is a bit inefficient, as a lookup is done twice if the symbol in the first position is not a syntax keyword…

    (set! prim-syntax-mark 'prim-syntax-mark)

    (set! init-env
      '(
        (quote     prim-syntax-mark  quote)
        (cond      prim-syntax-mark  cond)
        (set!      prim-syntax-mark  set!)
        (lambda    prim-syntax-mark  lambda)

        (car       prim-mark  car)
        (cdr       prim-mark  cdr)
        (cons      prim-mark  cons)
        (eq?       prim-mark  eq?)
        (read      prim-mark  read)
        (display   prim-mark  display)
        (set-car!  prim-mark  set-car!)
        (set-cdr!  prim-mark  set-cdr!)
        (exit      prim-mark  exit)
       )
    )

    (set! evsyntax
      (lambda (syn-def x env)
        (cond
          (
            (eq? (first syn-def) prim-syntax-mark)
            (cond
              ( (eq? (second syn-def) 'quote)     (second x) )
              ( (eq? (second syn-def) 'cond)      (evcond (cdr x) env) )
              ( (eq? (second syn-def) 'set!)      (evset (lookup (second x) env) (ev (third x) env)) )
              ( (eq? (second syn-def) 'lambda)    (make-proc x env) )
              ( #t                                '***undefined*** )
            )
          )
          ( #t  (pcall (evlist x env)) )
        )
      )
    )

    (set! ev
      (lambda (x env)
        (cond
          ( (eq? x #t)                 #t )
          ( (eq? x #f)                 #f )
          ( (symbol? x)                (bound-value (lookup x env)) )
          ( (symbol? (car x))          (evsyntax (cdr (lookup (car x) env)) x env) )
          ( #t                         (pcall (evlist x env)) )
        )
      )
    )

Scheme conditional

Saturday, June 21st, 2008

The basic Scheme conditional is if. However, the original Lisp cond is implemented as part of the basic repertoire, and if is not implemented at all. The original cond expression is extended to allow expression sequences after the test. Here, the left-to-right evaluation of the test expressions is handled by the left-to-right evaluation of cond in the base interpreter (a feature we have been using from the beginning)…

    (set! evcond
      (lambda (x env)
        (cond
          ( (eq? x '())            '***undefined*** )
          ( (ev (car (car x)) env) (evseq '***undefined*** (cdr (car x)) env) )
          ( #t                     (evcond (cdr x) env) )
        )
      )
    )

    (set! ev
      (lambda (x env)
        (cond
          ( (eq? x #t)              #t )
          ( (eq? x #f)              #f )
          ( (symbol? x)             (lookup x env) )
          ( (eq? (first x) 'quote)  (second x) )
          ( (eq? (first x) 'cond)   (evcond (cdr x) env) )
          ( (eq? (first x) 'lambda) (make-proc x env) )
          ( (eq? (first x) 'car)    (car  (ev (second x) env)) )
          ( (eq? (first x) 'cdr)    (cdr  (ev (second x) env)) )
          ( (eq? (first x) 'cons)   (cons (ev (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'eq?)    (eq?  (ev (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'read)   (read) )
          ( (eq? (first x) 'display)(display (ev (second x) env)) )
          ( (eq? (first x) 'exit)   (exit) )
          ( #t                      (pcall (evlist x env)) )
        )
      )
    )

Next, assignments.

Lexically scoped lambda

Friday, June 20th, 2008

In Scheme, lambda expressions are evaluated, resulting in a procedure, known more widely in the Lisp world as a closure. The closure captures the environment that is in effect at lambda evaluation time. The environment is basically a table of variable bindings, and the first set of variables will be the ones represented by procedure argument names. The captured environment is used later to provide “lexical” scoping of variables.

The little evaluator is extended to pass along the current environment to all subexpressions, and a data structure for lambda procedures is created…

    (set! proc-mark 'proc-mark)

    (set! make-proc
      (lambda (form env)
        (cons proc-mark (cons env (cdr form)))
      )
    )

    (set! ev
      (lambda (x env)
        (cond
          ( (eq? x #t)              #t )
          ( (eq? x #f)              #f )
          ( (eq? (first x) 'quote)  (second x) )
          ( (eq? (first x) 'lambda) (make-proc x env) )
          ( (eq? (first x) 'car)    (car  (ev (second x) env)) )
          ( (eq? (first x) 'cdr)    (cdr  (ev (second x) env)) )
          ( (eq? (first x) 'cons)   (cons (ev (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'eq?)    (eq?  (ev (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'exit)   (exit) )
          ( #t                      '***undefined*** )
        )
      )
    )

    (set! eval
      (lambda (x env)
        (ev x env)
      )
    )

A procedure call is an elaborate affair: 1) the arguments must be evaluated, 2) the argument values must paired up with the “formal” arguments, 3) the pairings must be added somehow to the procedure environment, and 4) the body of the procedure must be evaluated.

We can, of course, use a recursive procedure to evaluate the procedure expression and the argument expressions. With lambda expressions evaluating to a procedure, this is a little cleaner than the original Lisp evaluator…

    (set! evlist
      (lambda (x env)
        (cond
          ( (eq? x '()) '() )
          ( #t          (cons (ev (car x) env) (evlist (cdr x) env)) )
        )
      )
    )

    (set! pcall
      (lambda (x)
        x
      )
    )

    (set! ev
      (lambda (x env)
        (cond
          ( (eq? x #t)              #t )
          ( (eq? x #f)              #f )
          ( (eq? (first x) 'quote)  (second x) )
          ( (eq? (first x) 'lambda) (make-proc x env) )
          ( (eq? (first x) 'car)    (car  (ev (second x) env)) )
          ( (eq? (first x) 'cdr)    (cdr  (ev (second x) env)) )
          ( (eq? (first x) 'cons)   (cons (ev (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'eq?)    (eq?  (ev (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'exit)   (exit) )
          ( #t                      (pcall (evlist x env)) )
        )
      )
    )

We check to make sure we have a procedure object. If we have a procedure object, we can extract the list of formal arguments from it and pair them up with the argument values. Another recursive procedure to pair things up…

    (set! pair
      (lambda (x y)
        (cond
          ( (eq? x '())  '() )
          ( #t           (cons (cons (car x) (car y)) (pair (cdr x) (cdr y))) )
        )
      )
    )

    (set! pcall
      (lambda (x)
        (cond
          ( (eq? (first (car x)) proc-mark) (pair (third (car x)) (cdr x)) )
          ( #t                              '***undefined*** )
        )
      )
    )

Next, the name-value pairs are used to create bindings in the procedure’s environment. For lexical scoping, the procedure’s captured environment is the procedure’s starting environment. For now, the environment is a singly linked list of (name . value) pairs. The list of name-value pairs are prepended to the environment. Yet another recursive procedure…

    (set! append
      (lambda (x y)
        (cond
          ( (eq? x '()) y )
          ( #t          (cons (car x) (append (cdr x) y)) )
        )
      )
    )

    (set! pcall
      (lambda (x)
        (cond
          ( (eq? (first (car x)) proc-mark) (append (pair (third (car x)) (cdr x)) (second (car x))) )
          ( #t                              '***undefined*** )
        )
      )
    )

Arguments can be evaluated in any order. But to enforce the left-to-right evaluation of the procedure body’s expression sequence, we use the “eager” evaluation rule – the arguments must all be evaluated before the procedure body is evaluated. Scheme requires at least one expression in the body, so the no-expression case is treated as undefined…

    (set! evseq
      (lambda (x seq env)
        (cond
          ( (eq? seq '()) x )
          ( #t            (evseq (ev (car seq) env) (cdr seq) env) )
        )
      )
    )

    (set! pcall
      (lambda (x)
        (cond
          (
            (eq? (first (car x)) proc-mark)
            (evseq
              '***undefined***
              (cdr(cdr(cdr (car x))))
              (append (pair (third (car x)) (cdr x)) (second (car x)))
            )
          )
          ( #t  '***undefined*** )
        )
      )
    )

All that’s needed now is to look up the variable bindings. The linear search and the prepending of argument bindings provides hiding (or shadowing) of variables with the same name in an outer scope. Because symbol? was not defined in the base interpreter, an implementation detail of symbols is revealed. The read and display procedures were added for debugging…

    (set! lookup
      (lambda (v env)
        (cond
          ( (eq? env '())           '***undefined*** )
          ( (eq? v (car (car env))) (cdr (car env)) )
          ( #t                      (lookup v (cdr env)) )
        )
      )
    )

    (set! symbol?
      (lambda (x)
        (eq? (car x) (car 'car))
      )
    )

    (set! ev
      (lambda (x env)
        (cond
          ( (eq? x #t)              #t )
          ( (eq? x #f)              #f )
          ( (symbol? x)             (lookup x env) )
          ( (eq? (first x) 'quote)  (second x) )
          ( (eq? (first x) 'lambda) (make-proc x env) )
          ( (eq? (first x) 'car)    (car  (ev (second x) env)) )
          ( (eq? (first x) 'cdr)    (cdr  (ev (second x) env)) )
          ( (eq? (first x) 'cons)   (cons (ev (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'eq?)    (eq?  (ev (second x) env) (ev (third x) env)) )
          ( (eq? (first x) 'read)   (read) )
          ( (eq? (first x) 'display)(display (ev (second x) env)) )
          ( (eq? (first x) 'exit)   (exit) )
          ( #t                      (pcall (evlist x env)) )
        )
      )
    )

Next, conditional expressions.

First set of Scheme procedures

Wednesday, June 18th, 2008

The evaluator is expanded to provide several basic procedures. The model is tgmoaf (the great mother of all functions). A slight variation of it, called ev, is defined. The primary aspect of this variation is the removal of some abstractions. It uses recursion to evaluate subexpressions in a straightforward fashion. The quote syntax is also provided to allow working with all kinds of data.

    (set! ev
      (lambda (x)
        (cond
          ( (eq? x #t)          #t )
          ( (eq? x #f)          #f )
          ( (eq? (car x) 'quote)(car(cdr x)) )
          ( (eq? (car x) 'car)  (car  (ev (car(cdr x)))) )
          ( (eq? (car x) 'cdr)  (cdr  (ev (car(cdr x)))) )
          ( (eq? (car x) 'cons) (cons (ev (car(cdr x))) (ev (car(cdr(cdr x))))) )
          ( (eq? (car x) 'eq?)  (eq?  (ev (car(cdr x))) (ev (car(cdr(cdr x))))) )
          ( (eq? (car x) 'exit) (exit) )
          ( #t                  '***undefined*** )
        )
      )
    )

    (set! eval
      (lambda (x env)
        (ev x)
      )
    )

Some abstractions can be added back. The function and argument extractions can be factored out, resulting in a new version of ev

    (set! first  (lambda (x) (car x)))
    (set! second (lambda (x) (car (cdr x))))
    (set! third  (lambda (x) (car (cdr (cdr x)))))

    (set! ev
      (lambda (x)
        (cond
          ( (eq? x #t)             #t )
          ( (eq? x #f)             #f )
          ( (eq? (first x) 'quote) (second x) )
          ( (eq? (first x) 'car)   (car  (ev (second x))) )
          ( (eq? (first x) 'cdr)   (cdr  (ev (second x))) )
          ( (eq? (first x) 'cons)  (cons (ev (second x)) (ev (third x))) )
          ( (eq? (first x) 'eq?)   (eq?  (ev (second x)) (ev (third x))) )
          ( (eq? (first x) 'exit)  (exit) )
          ( #t                     '***undefined*** )
        )
      )
    )

Next, the procedure call is fleshed out.

Starting another high level evaluator

Tuesday, June 17th, 2008

With set! and lambda working (in that order), the test can be pulled out and put into a lambda expression…

(
  (lambda (repl test)

    (set! test
      (lambda (x)
        (cond
          ((eq? (car x) 'quit) (exit))
        )
      )
    )

    (set! repl
      (lambda (f)
        (set! f (read))
        (test f)
        (display f)
        (repl '())
      )
    )

    (repl '())

  ) '() '()
)

The cond expression can be modified so that test returns a value…

(
  (lambda (repl test)

    (set! test
      (lambda (x)
        (cond
          ((eq? (car x) 'quit) (exit))
          (#t                  x)
        )
      )
    )

    (set! repl
      (lambda (f)
        (set! f (read))
        (set! f (test f))
        (display f)
        (repl '())
      )
    )

    (repl '())

  ) '() '()
)

This can be written more concisely as…

(
  (lambda (repl test)

    (set! test
      (lambda (x)
        (cond
          ((eq? (car x) 'quit) (exit))
          (#t                  x)
        )
      )
    )

    (set! repl
      (lambda ()
        (display (test (read)))
        (repl)
      )
    )

    (repl)

  ) '() '()
)

If the test procedure is replaced by an expression evaluator, we will have a REPL that is familiar to Lisp enthusiasts. The evolution sequence that was presented is a bottom-up debugging sequence, rather than the preferred top-down development sequence presented in much computing (including Lisp) literature. The sequence was guided by the goal of recreating the known architecture of a REPL.

The canonical evaluator is named eval, and has an environment argument as well as the expression (or form) argument. As a starting point, test is renamed to eval, and a second argument is added. So the REPL looks more like…

(
  (lambda (repl eval)

    (set! eval
      (lambda (x env)
        (cond
          ((eq? (car x) 'quit) (exit))
          (#t                  x)
        )
      )
    )

    (set! repl
      (lambda ()
        (display (eval (read) '()))
        (repl)
      )
    )

    (repl)

  ) '() '()
)

Next, we add some standard procedures.

Baby steps with a tiny Scheme

Friday, June 13th, 2008

With a small interpreter in hand, the system starts with a simple echo “computation”…

(display (read))

Before it can be repeated, it’s encased by a lambda expression. It can┬áthen be invoked…

(
  (lambda ()
    (display (read))
  )
)

Since the tiny Scheme does not have let or define, the following code abuses the lambda expression to gain access to an intermediate value…

(
  (lambda (f)
    (set! f (read))
    (display f)
  ) '()
)

The intermediate value can then be tested…

(
  (lambda (f)
    (set! f (read))
    (cond
      ((eq? (car f) 'quit) (exit))
    )
    (display f)
  ) '()
)

Some more lambda abuse results in naming the function, followed by its invocation by name…

(
  (lambda (repl)

    (set! repl
      (lambda (f)
        (set! f (read))
        (cond
          ((eq? (car f) 'quit) (exit))
        )
        (display f)
      )
    )

    (repl '())
  ) '()
)

And then a “loop” is created by using a recursive tail call…

(
  (lambda (repl)

    (set! repl
      (lambda (f)
        (set! f (read))
        (cond
          ((eq? (car f) 'quit) (exit))
        )
        (display f)
        (repl '())
      )
    )

    (repl '())
  ) '()
)

Next, we build an evaluator.