Re: expect module

[Kohtala Marko <Marko.Kohtala@ntc.nokia.com>]

Gary Houston <ghouston@easynet.co.uk>
> True.  I had a vague idea of rewriting part of it in C.  Adding a
> per-line mode may be a good idea too.  Perhaps implementing
> expect-strings directly instead of as a front-end to a more general
> expect would help.

If you are after speed, I think it would be better to implement a
regexp library based on a more generic nondeterministic FSM to
deterministic FSM transformer. Then you advance the deterministic FSM
on each character you receive. If both machines were scheme data
structures, then this same transformer could be used for many other
things as well.

I am sorry if this is already thought over or shot down or even
implemented. I do not follow these scheme things very closely so just
let me know what I am ignorant of.

Maybe the machine could be made so that for each state, there is an
alist of event to next state and a list of "actions" in this
state. Maybe we could have the events equal by eq?. The compiler could
just concatenate the lists of different states for the states of the
deterministic FSM, and also have the actions stay equal by eq? no
matter what lists thay are on. The transformer could ignore any
further structure on the events and actions so that the one advancing
the machine can perform the actions whatever they are.

Maybe something like

(define (nd-to-d starts epsilon statecombine)
        ;; evaluate to deterministic machine. STARTS is a list of states
        ;; in the machine initial state. EPSILON is the epsilon transition
        ;; which may be taken without any event. STATECOMBINE is a function
        ;; taking one argument which is a list of actions of ND in
        ;; this state of deterministic machine. It returns the action for
        ;; deterministic machine.
...
)

(define d (nd-to-d
           (letrec ((state1 `(((epsilon . ,state2)
                               (event1 . ,state3))
                              a)
                    (state2 `(((event2 . ,state3))
                              b))
                    (state3 `(()
                              quit))))
            (list state1))
           'epsilon
	   (lambda (x) x)))
d
=> (letrec ((dstate1 `(((event1 . ,dstate2) (event2 . ,dstate2))
                       a b))
            (dstate2 `(() quit)))
        dstate1)

(define (d-advance d event func)
	;; Return state of D which is the result of EVENT.
	;; Call FUNC with action of resulting state.
	;; In case of syntax error, return #f.
...
)

For expect, the ND machine actions could be cons cells having
precedence and the action. The statecombine would then choose the
highest precedence action if there would be more than one action to
choose from.

For a compiler, the actions could be shift or reduce actions and
statecombine would thrown exceptions in case of conflicts.

Of course, expect would also need something to compile and combine the
regexp strings and attach the actions into the resulting state
machine.

It is somewhat big task, but the result would be very useful and
faster in the runtime for expect.

-- 
Marko Kohtala - Marko.Kohtala@ntc.nokia.com, Marko.Kohtala@hut.fi