Re: Iteration in lisp
- From: lisp1.3.CalRobert@xxxxxxxxxxxxxxx (Robert Maas, http://tinyurl.com/uh3t)
- Date: Thu, 01 May 2008 02:37:46 -0700
From: "John Thingstad" <jpth...@xxxxxxxxx>
Maybe I am bit dim but to me the obvious implementation of a
state machine is just a tagbody and goto.
If you're never going to change it mid-run, and if you don't need
to include any instrumentation of a general nature about the
process, such as a trace of state changes, then clearly that's the
simplest way to go.
But if you need to change the state-transition-matrix in the middle
of a run and *not* have to re-start from the top, then you need
something that has an explicit state variable and a single toplevel
loop and either table-driven or separate-functions for defining the
new state that follows any given state. The table can simply be
modified mid-run to show a new next-state, while a separate
function can be re-defined (in Lisp, not so easy in other
langugages) at any time to return the new-state value differently
from the previous definition.
If you wish to make it more explicit you could:[rest o details snipped]
(defmacro state-machine (&body body)
`(tagbody ,@body))
(defmacro change-state (state)
`(go ,state))
If you want an easy way to recompile a new tagbody containing a new
state-change matrix, but you will be re-starting from the top
rather than picking up where you left off, this sounds optimal in
regard to simplicity.
The class version is a waste of memory, too slow and too much work.
I'm not sure what you mean by "class version". Perhaps that's some
part of the thread I haven't seen yet.
The recursive version has a unclear execution model if it uses
dynamic variables etc..
I agree. But I can't think of any good reason to include dynamic
variables. More normally I envision a single global state-object
which contains all the embedded data about the current overall
state, which includes the basic state (modeled by the finite-state
machine) plus all the auxiliary data that is being computed by the
machine. For example, a SGML or XML parser might be modeled as a
finite-state machine (for parse mode: toplevel, inside tag, inside
attribute, inside numeric value, inside string, inside white space
between attributes, inside character/unicode entity, etc.) plus
auxiliary stacks (for emulating recursion into sub-expressions i.e.
text bounded by nested opening/closing tag pairs).
Dispatch just adds overhead with no added clarity.
Dispatch within single loop allows instrumentation to be placed in
just one spot within the loop rather than duplicated once per each
state. Compare these:
(setq state (cons 'state1 (make-auxilary-record ...)))
(loop (trace-state state) (one-step state))
(setq aux (make-auxilary-record ...))
(tagbody state1 (trace-state1 aux)
(...handcoded-conditional... (go state2) ... (go state4))
state2 (trace-state2 aux)
(...handcoded-conditional... (go state3) ... (go state4))
state3 (trace-state3 aux)
(...handcoded-conditional... (go state1) ... (go state5))
state4 (trace-state4 aux)
(...handcoded-conditional... (go state1) ... (go state3))
state5 (trace-state5 aux)
(...handcoded-conditional... (go state2) ... (go state5)))
See how much messier it is to duplicate the tracing for each state?
Seems to me people go to almost extreme lengths to avoid goto
even when it is the right abstraction.
I'm not one of those people. You should say that "some" people go
to almost extreme lengths ...
I like to instrument my code, and if I'm doing a whole lot of
things that are almost identical in some ways then I like to write
that identical stuff in just one place instead of many, assuming I
anticipate the potential duplication in advance of course. I make
liberal use of goto in my code when first developing it one line at
a time, and the goto remains until and unless I can refactor the
code to use some higher-level construct to replace it nicely.
One use for goto that never disappears is a common return point.
Typically I have two ways to exit, one when it finds what it's
looking for, and one where it exhausts the search space without
finding what it's looking for. If I want to return multiple values,
only one of which is different depending on success or failure,
then SETQ of the key difference variable then GO to a common
(return (values ...)) seems the best pattern to me. On the other
hand if I return a different number of values depending on how the
loop was exited, then I write (return (values ...)) individually at
each exit-from-loop point instead of using any GO there.
A continuation mechanism could be used if you need to exit and
resume the machine from another point in the program (like the one
in the library cl-cont).
Or pass the (rawstate . auxinfo) as parameter to the dispatch loop,
then when needing to temporarily exit just throw the current
machine state to achieve non-local immediate exit from the loop,
and then pass it as parameter next time the dispatch loop is called
from some other place in the higher-level application. One use for
this I can see is if the state transition matrix is being built
incrementally, with some cases not yet programmed, one case of the
function to compute next state might discover the next state can't
yet be determined, so it throws the previous state just before that
trouble, and the high-level program fixes the problem by changing
the state-handler for that particular old state to correctly
determine the new state, then on re-start it runs fine to next
state. (This is an alternative to fixing the problem from *inside*
the dynamic context, such as from inside a breakpoint, whereby the
dispatch loop never needs to re-start picking up where it left
off.) I guess you had some other useful application in mind, but I
presume my methodology would work for your application too.
.
- Prev by Date: Re: Parallel Common-Lisp with at least 64 processors?
- Next by Date: load .emacs error
- Previous by thread: Re: Iteration in lisp
- Next by thread: Re: Iteration in lisp
- Index(es):
Relevant Pages
|
Loading
