tk's bits

Until recently, I had been running a software state machine which implemented a next-m-state function that took two arguments: m-state and i-state.

The i-state had not been an input state for quite some time. It is an instruction state, but it is redundant since it is pulled out of m-state.

So next-m-state was redone to accept only one argument, the m-state. The state machine becomes (slightly hacked because the base system does not have set!)…

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

The first stage extracts the instruction list and the environment…

next-m-state =
  (lambda (m-state)
    (execute (get-i-list m-state) (get-m-env m-state))
  )

The second stage checks for the existence of instructions. If there is at least one instruction, the first instruction is split from the rest of the instruction list…

execute =
  (lambda (i-list env)
    (cond
      ((null? i-list) (exit))
      (#t             (exec1 (car i-list) (cdr i-list) env)
    )
  )

Finally, the instruction (also called a command, listed here as cmd) is executed…

exec1 =
  (lambda (cmd next-i-list env)
    (cond
      ((eq? (car cmd) (quote define)) (make-m-state
                                        next-i-list
                                        (quote ())
                                        (add-to-env
                                          (make-binding
                                            (car(cdr cmd))
                                            (eval (car(cdr(cdr cmd))) env)
                                          )
                                          env
                                        )
                                      )
      )
      (#t                             (make-m-state
                                        next-i-list
                                        (eval cmd env)
                                        env
                                      )
      )
    )
  )

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))
      )
    )
  )

Since a set-cell! procedure doesn’t exist, we will create a pair ((quote m-state) . m-state) that allows us to update the m-state value with just a set-cdr!

That allows us to write a new state machine

lsm =
  (lambda (m-state-binding)
    (loop
      (set-cdr! m-state-binding
        (next-m-state
          (cdr m-state-binding)
          (get-i-state (make-o-state (cdr m-state-binding)))
        )
      )
    )
  )

Since I can tell you that loop is implemented with a simple jump instruction, and conventional stack balancing is involved, it’s clear to conventional programmers that the stack starts at the same level at the beginning of each iteration.

I just discovered Richard Gabriel’s Patterns of Software Usage. This collection of Gabriel’s essays compels me to give some reasoning for the abstractions I’ve implemented. I’ve logged a number of abstractions without giving reasons for implementing them.

The abstractions for adding local (argument) bindings were originally based on the ones in J. Allen’s Anatomy of Lisp. It’s a bit different because it’s based on my perceived need to delete local bindings when optimizing tail calls.

The abstractions for global bindings are roughly parallels to the abstractions for local bindings.

The abstractions for the m-state are based on my experience with HDL’s (Hardware Description Languages). I’ve used both mainstream languages, namely, Verilog and VHDL. The primary idiom for sequential logic is the finite state machine. The feeding of the output state to the input procedure is a recognition that in a real world application, the output can affect the external world before the application reacts to it. The functions correspond to the components of a state machine description: current input, next state logic,  updating of state (via a state register), and generating output from the current state.

We abstract the m-state by defining functions for creating it and for extracting information from it.

next-m-state =
  (lambda (m-state i-state)
    (cond
      ((eq (car i-state) (quote def))  (make-m-state
                                         (quote ())
                                         (add-to-env
                                           (make-binding
                                             (car (cdr i-state))
                                             (car (cdr (cdr i-state)))
                                           )
                                           (get-m-env m-state)
                                         )
                                       )
      )
      (t                               (make-m-state
                                         (eval i-state (get-m-env m-state))
                                         (get-m-env m-state)
                                       )
      )
    )
  )

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

make-o-state =
  (lambda (m-state)
    (print (get-m-result m-state))
  )

The LSM gives us one model of a state machine in functional form. We will use it to define “global” functions in an applicative (eager evaluation) functional style.

The global environment is part of the m-state. Adding named functions to it is done by creating a binding and making a new global environment, which is passed to the next state to become the new global environment. An LSM level command (def <name> <expression>) is recognized by the generator for the next m-state. The def command binds <name> to the unevaluated <expression>, and adds the binding to the global environment. The result value is the empty list.

next-m-state =
  (lambda (m-state i-state)
    (cond
      ((eq (car i-state) (quote def))  (cons
                                         (quote ())
                                         (add-to-env
                                           (make-binding
                                             (car (cdr i-state))
                                             (car (cdr (cdr i-state)))
                                           )
                                           (cdr m-state)
                                         )
                                       )
      )
      (t                               (cons
                                         (eval i-state (cdr m-state))
                                         (cdr m-state)
                                       )
      )
    )
  )

add-to-env =
  (lambda (binding env)
    (cons binding env)
  )

make-binding =
  (lambda (var value)
    (cons var value)
  )

The following script will test that a globally defined variable can be evaluated as a variable, or as a function if it is bound to a function definition…

(def f1 (lambda (a b) (cons a b)))
f1
(f1 (quote (x y z)) (quote (a b c)))

My base (assembly language) system still requires that nonprimitive function definitions be named in the a-list used as an argument to eval0. When the LSM interpreter is invoked, the remaining input is interpreted under the environment set by the LSM interpreter, rather than the environment of the base system. The LSM interpreter promotes the mixing of evaluation and persistent definition, whereas the base system promotes the separation of evaluation and persistent definition.

My original implementation of REPL looks like the following…

repl =
  (lambda (x)
    (repl (print (eval (read) (quote ()))))
  )

We can abstract this a little bit by noting that it represents the creation of an output based on an input.

repl =
  (lambda (x)
    (repl (make-o-state (get-i-state)))
  )
get-i-state =
  (lambda ()
    (read)
  )
make-o-state =
  (lambda (i-state)
    (print (eval i-state (quote ())))
  )

Here, I am introducing the notion of state, so we might as well look at a state machine. A state machine models an environment that has a machine state. At each sampling of the input state, the machine state is combined with the input state to generate the next machine state. The generation of the next machine state S_i+1, given the current machine state S_i and input state x_i, can be specified as a transformation function t…

S_i+1 = t(S_i, x_i)

Useful state machines also have an output function based on the machine state.

y_i = f(S_i)

The complexity of the state changes is the complexity of the transformation function t.

The state machine has an initial state S₀ and the first input state is x₀.

We can add a next machine state generator and make the o-state a function of the next m-state…

repl =
  (lambda (x)
    (repl (make-o-state (next-m-state m-state (get-i-state))))
  )
next-m-state =
  (lambda (m-state i-state)
    (eval i-state m-state)
  )
make-o-state =
  (lambda (m-state)
    (print m-state)
  )

The above code shows the intent of using eval to create a new m-state. It also shows that the m-state is intended to be the environment for eval. We need to show that the m-state includes both the eval environment and the result of eval. For this purpose, the m-state is implemented as (result . env).

next-m-state =
  (lambda (m-state i-state)
    (cons (eval i-state (cdr m-state)) (cdr m-state))
  )
make-o-state =
  (lambda (m-state)
    (print (car m-state))
  )

To show that the o-state can potentially affect the external world, we make it an argument of the i-state sampler…

repl =
  (lambda (o-state)
    (repl (make-o-state (next-m-state m-state (get-i-state o-state))))
  )
get-i-state =
  (lambda (o-state)
    (read)
  )

Now we just need to show that the o-state is not the next machine state…

repl =
  (lambda (m-state)
    (repl (next-m-state m-state (get-i-state (make-o-state m-state))))
  )

As REPL is no longer the same function, we will rename the new function as the Lisp state machine, or LSM…

lsm =
  (lambda (m-state)
    (lsm (next-m-state m-state (get-i-state (make-o-state m-state))))
  )