Archive for December, 2007

Scheme-like procedures

Monday, December 31st, 2007

Scheme procedures, like closures, carry a defining environment with them, preventing unexpected bindings. Unlike the funarg closure, it always carries the function definition. This provides static scoping of atoms for a given function definition.

Scheme does not define a data structure for a procedure, so I used the following structure: (proc <env> <args> <body>). And then I added the ability to directly apply a procedure…

  (
    (eq? (car fn) (quote proc))
    (eval
      (car(cdr(cdr(cdr fn))))
      (mkenv (car(cdr(cdr fn))) args (car(cdr fn)))
    )
  )

And then, to satisfy the static scoping requirement of Scheme, I use the Scheme definition of a lambda expression as an eval expression that evaluates to a procedure.

  (
    (eq? (car form) (quote lambda))
    (cons
      (quote proc)
      (cons
        env
        (cdr form)
      )
    )
  )

One unfortunate result of the procedure data structure is the creation of a circular list. Performing a def followed by set! to bind the procedure to the variable puts the procedure in the procedure’s embedded environment a-list. The base system’s display will recurse infinitely trying to display the procedure definition.

Not having a malleable display function, I hacked up an atom containing the environment as a component of its print name. As the built-in display assumes an atom’s print name contains only characters, it will display garbage characters.

In eval, we atomize the environment…

  (
    (eq? (car form) (quote lambda))
    (cons
      (quote proc)
      (cons
        (cons (car(quote car)) env)
        (cdr form)
      )
    )
  )

In apply, we peel off the atom mark before giving it to mkenv…

  (
    (eq? (car fn) (quote proc))
    (eval
      (car(cdr(cdr(cdr fn))))
      (mkenv (car(cdr(cdr fn))) args (cdr  (car(cdr fn))))
    )
  )

Since set! does not create a new binding, the old quoting def (in next-m-state)…

  (
    (eq? (car i-state) (quote def))
    (make-m-state
      (cdr (get-i-list m-state))
      (quote ())
      (add-to-env
        (make-binding
          (car(cdr i-state))
          (car(cdr(cdr i-state)))
        )
        (get-m-env m-state)
      )
    )
  )

is replaced by an evaluating define…

  (
    (eq? (car i-state) (quote define))
    (make-m-state
      (cdr (get-i-list m-state))
      (quote ())
      (add-to-env
        (make-binding
          (car(cdr i-state))
          (eval (car(cdr(cdr i-state))) (get-m-env m-state))
        )
        (get-m-env m-state)
      )
    )
  )

Evaluation of a lambda expression freezes the lexical environment of that procedure. Subsequent procedure definitions using define will not be added to this captured environment.

Recursion is created by using define with a temporary value, followed by a set! expression containing the recursive lambda expression. For mutually recursive procedures at the top level, it is easiest to define all procedure names before using set! expressions. That’s easy in a script, but inconvenient in an interactive environment.

Posted in Lisp/Scheme | No Comments »

One implementation of set!

Wednesday, December 19th, 2007

And now for set!. This version is, of course, heavily influenced by the current implementation of the environment as an association list. We search for the most recent binding of a variable, and directly alter the binding.

Because the value of the variable in set! must not be retrieved, set! is evaluated in eval…

  ((eq? (car form) (quote set!))    (change-binding
                                      (assoc (car (cdr form)) env)
                                      (eval (car (cdr (cdr form))) env)
                                    )

The function assoc can return the empty list. As we don’t want to mutate the empty list, we check for the empty list…

change-binding =
  (lambda (binding val)
    (cond
      ((null? binding) (quote ()))
      (#t              (set-cdr! binding val))
    )
  )

In this version, set! returns the new binding. However, Scheme does not specify the resulting value of set!.

Posted in Lisp/Scheme | No Comments »

A software state machine

Sunday, December 9th, 2007

First we restate our new m-state binding as (m-state . <m-state>).

The heart of our state machine is the creation of the next <m-state>…

  (next-m-state
    (cdr m-state-binding)
    (get-i-state (make-o-state (cdr m-state-binding)))
  )

where the <m-state> is (<m-result> . <m-env>).

We can view each new i-state as either data to be processed, or an instruction to be followed. If the i-state sequence has a pattern, we can store the pattern as part of the environment. Then get-i-state pulls the next data or instruction, the i-state, out of the stored environment, rather than from the external world.

The <m-env> is a collection of values that the evaluator can retrieve by name. The i-state is not part of the <m-env>. For the moment, we will also treat the i-state sequence, the <i-list>, as separate from the <m-env>.

My original state machine is influenced by experience with Verilog and VHDL, hardware description languages that define inputs and outputs as connections. In the hardware world, outputs change in response to input changes. There is no such thing as “no input” or “no output”. Many software people have stumbled when entering this world of programmable logic, because of Verilog’s and VHDL’s extreme resemblance to conventional programming languages. This is due to their original purposes as simulation languages, as opposed to their current second use as hardware design languages.

In the software world, input and output are data transactions, modelled as data transmissions from sources (inputs) and to destinations (outputs).

Conventional software treats the processor, a state machine, as self-contained, receiving and sending data to and from devices that do the actual interaction with the external world. Thus, in our new model, make-o-state is no longer necessary, and get-i-state means “get instruction” rather than “get input”. Our new state machine is a “software” Lisp state machine, swlsm. The loop itself is simpler:

swlsm =
  (lambda (m-state-binding)
    (loop
      (set-cdr! m-state-binding
        (next-m-state
          (cdr m-state-binding)
          (get-i-state (cdr m-state-binding))
        )
      )
    )
  )

but next-m-state becomes more complex, as it needs to supply a new <i-list>:

next-m-state =
  (lambda (m-state i-state)
    (cond
      (
        (eq? (car i-state) (quote ...))
        (make-m-state (cdr (get-i-list m-state)) ...)
      )
      ...
    )
  )

make-m-state =
  (lambda (i-list result env)
    (cons i-list (cons result (cons env nil)))
  )
get-i-list =
  (lambda (m-state)
    (car m-state)
  )
get-m-result =
  (lambda (m-state)
    (car (cdr m-state))
  )
get-m-env =
  (lambda (m-state)
    (car (cdr (cdr m-state)))
  )

get-i-state =
  (lambda (m-state)
    (car (get-i-list m-state))
  )

Because swlsm expects to receive an m-state containing an <i-list>, the primary input reader is no longer within the state machine loop. There isn’t yet a way to detect an end-of-file condition on the primary input. As a result, we need to wrap up the sequence of S-expressions into a single list. If needed, we can still code yet another REPL layer.

While updating and testing the state machine, I forgot to add an (exit) at the end of a test sequence. As the new state machine receives the entire sequence of S-expressions before processing it, we can now detect an end of sequence condition, and exit the session accordingly.

get-i-state =
  (lambda (m-state)
    (cond
      (
        (eq? (get-i-list m-state) (quote ()))
        (exit)
      )
      (
        #t
        (car (get-i-list m-state))
      )
    )
  )

Posted in Lisp/Scheme, State Machines | No Comments »