Okay, the flame retardant suit is on... ;-)
So I have been going through the exercise of figure out how to represent
state machines in CL. I came up with a solution and then decided to try my
hand at putting together a macro to make the syntax easier. I now fully
understand why Paul Graham is always going on about macros. Really cool.
I'd love it if people would please give me some helpful criticism of my code
and coding style. This is my first CL code, so please be constructive and
gentle. I want to learn, not get told I'm an idiot. I already know that I'm
an idiot, at least when it comes to CL, so tell me something I don't know.
If I'm missing a more efficient or "normal" way to do something, please
point it out to me and show me how you would have done it differently in
order to create more readable, maintainable, or efficient code (in that
order, I guess).
Okay, first here is the general syntax. A state machine basically looks
like:
(defsm <machine-name> (<input vars>) <start state name>
(<state name> ( <test> <next-state-name> <forms...>)
( <test> <next-state-name> <forms...>))
(<state name> ( <test> <next-state-name> <forms...>)
( <test> <next-state-name> <forms...>)))
The following macro basically converts this to a generator function that
returns a closure representing the new machine. The closure contains a LET
holding the current state, followed by a LABELS form for each of the
individual states which get converted to functions. Each state function
takes input parameters equivalent to the variable name specified at the
start of the macro. The body of each state function is then a COND form
that evaluates the tests. If a test is true, the machine sets the next
state accordingly and then executes the various forms that are associated
with the transition. There is a LAMBDA function that gets returned to pass
the input parameters on to the current state.
(defmacro defsm (smname inputs init-state &rest states)
(labels ((cond-arm (transition)
`(,(car transition)
(setq current-state #',(cadr transition))
,@(cddr transition)))
(per-state (state)
(list (car state)
(if (consp inputs)
inputs
(list inputs))
`(cond ,@(mapcar #'cond-arm (cdr state))))))
`(defun ,(intern (string-upcase (concatenate
'string
"MAKE-"
(symbol-name smname))))
() ;; no parameters to the resulting function
(let ((current-state))
(labels ,(mapcar #'per-state states)
(setq current-state #',init-state)
(lambda ,(if (consp inputs)
inputs
(list inputs))
(funcall current-state ,@inputs)))))))
You can use this as part of another closure to build up a self-contained
state machine with supporting state variables and helper functions. The
following is the start to a SMTP server state machine, for instance. Don't
critique the protocol implementation right now; I'm typing in error codes
and such completely from memory, and haven't gone back and checked the RFC
yet; there may be bugs protocol-wise.
(let (socket
esmtp)
(labels ((crlf ()
(write-char #\Return socket)
(write-char #\Linefeed socket))
(output (string)
(write-string string socket)
(crlf))
(output-extensions (remote-name)
(output "220-OK")
(output "220 8BITMIME"))
(smtp-commandp (input name)
(equalp input name))
(commandp (input name)
(eq input name)))
(defsm smtp-server (sm-command param) start
(start ((commandp sm-command 'newsession)
await-helo
(setq socket param)
(output "220 server ready")))
(await-helo ((and (commandp sm-command 'smtp-input)
(smtp-commandp param "EHLO"))
await-mail
(setq esmtp t)
(output-extensions "droberts.com"))
((and (commandp sm-command 'smtp-input)
(smtp-commandp param "HELO"))
await-mail
(setq esmtp nil)
(output "220 OK"))
(t
await-helo
(output "550 ERROR")))
(await-mail (t await-mail))))) ;; This would obviously continue
You can then create an instance of the state machine thusly:
(setq mm (make-smtp-server))
And then drive it like this, for testing. Obviously, in a real system, this
would be hooked up to a better event mechanism.
(funcall mm 'newsession *standard-output*)
(funcall mm 'smtp-input "EHLO")
So, please comment. Would you write something this way? If not, how would
you do it? Please note also that right now I'm restricting myself to avoid
CLOS. I have a hunch that when I finally get in and learn CLOS, I would do
this totally differently, but I want to force myself to learn basic CL
right now, using this as an exercise.
-- Dave
In article <························@attbi_s01>, Dave Roberts
<·············@re-move.droberts.com> wrote:
> This is my first CL code, so please be constructive and
> gentle. I want to learn, not get told I'm an idiot.
I think this is a very respectable effort. Actually, it's quite
impressive for your first time out.
> Would you write something this way?
No. My code would be worse :-)
E.
Erann Gat wrote:
> In article <························@attbi_s01>, Dave Roberts
> <·············@re-move.droberts.com> wrote:
>
>> This is my first CL code, so please be constructive and
>> gentle. I want to learn, not get told I'm an idiot.
>
> I think this is a very respectable effort. Actually, it's quite
> impressive for your first time out.
Thank you.
>> Would you write something this way?
>
> No. My code would be worse :-)
I doubt it. I have read some of your papers. ;-) But thanks for the
encouragement. I need it.
-- Dave
This is very good! Just a couple of obvious comments:
-- You want to use a gensym for the closure var. Consider the case:
(defsm smtp-server (sm-command param) start
(start ((commandp sm-command 'newsession)
await-helo
(setq socket param)
;how am I to know current-state is bad to use here?
(setq current-state 'foo)
(output "220 server ready")))
;etc etc
)
-- Ditto for internal function names. The user of the macro cannot know
that if he cannot have his own functions use the same names as the states of
his state-machine if he will use them as action forms in a defsm.
I probably would have written this in a similar way. Alternatively I might
have generated a 'case' or a 'tagbody' from the macro, instead of labels.
cheers,
BM
Bulent Murtezaoglu wrote:
>
> This is very good! Just a couple of obvious comments:
>
> -- You want to use a gensym for the closure var. Consider the case:
Yes, agreed. I knew that my posting would probably bring out somebody saying
that this was exposing some form of capture. That was my next pass through
the code. I need to go read-up on GENSYM a bit.
> -- Ditto for internal function names. The user of the macro cannot know
> that if he cannot have his own functions use the same names as the states
> of his state-machine if he will use them as action forms in a defsm.
Hmmm... so basically, you're saying that I should convert whatever state
names the user gives me into GENSYM'd ones? How is the best way to go about
that? Temporary assoc list kept in the macro?
> I probably would have written this in a similar way. Alternatively I
> might have generated a 'case' or a 'tagbody' from the macro, instead of
> labels.
I looked at CASE and thought it seemed a bit more inefficient. It seemed
faster to dispatch directly to a function rather than go through all the
testing that CASE implies. TAGBODY seems to work well for machines that are
self-contained and "run to completion" in a single call (something like a
regular expression matcher or something). TAGBODY seemed less of a match
when you want to fully exit the machine to go do something else for a while
and then come back with another input. Are those impressions correct?
-- Dave
Dave Roberts <·············@re-move.droberts.com> writes:
> Bulent Murtezaoglu wrote:
>
> > I probably would have written this in a similar way. Alternatively I
> > might have generated a 'case' or a 'tagbody' from the macro, instead of
> > labels.
>
> I looked at CASE and thought it seemed a bit more inefficient. It seemed
> faster to dispatch directly to a function rather than go through all the
> testing that CASE implies. TAGBODY seems to work well for machines that are
> self-contained and "run to completion" in a single call (something like a
> regular expression matcher or something). TAGBODY seemed less of a match
> when you want to fully exit the machine to go do something else for a while
> and then come back with another input. Are those impressions correct?
But your state machines don't have any facility to yeild, either. In
the best case scenario, the compiler will generate approximately the
same code for your LABELS as it would have for a TAGBODY. Either way,
you'll need to either yeild or multiplex somehow.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Thomas F. Burdick wrote:
> But your state machines don't have any facility to yeild, either. In
> the best case scenario, the compiler will generate approximately the
> same code for your LABELS as it would have for a TAGBODY. Either way,
> you'll need to either yeild or multiplex somehow.
Sure they do. They just return. Each call to the machine moves it forward
one transition and then it exits back to the caller. Effectively, it's
self-yielding. ;-)
In terms of TAGBODY, I think the implementation there would have been plenty
efficient. I figured that CASE would have been less efficient because of
the comparisons. The issue with TAGBODY is that I would have had to have
each state call out of the machine to get more events (yield). This works
great if the main thread can be "in" the state machine for a long time, but
it doesn't work for things like servers. Like I cobbled together an SMTP
server as my example. Imagine having a few hundred of these all receiving
mail simultaneously from different sites. If you have true OS-level
threading, you could devote a thread to each and do it all with TAGBODY. If
you don't have that, you need some Unix-select-like mechanism that gets an
event on possibly hundreds of sockets, then dispatches that event to the
correct machine, which turns the crank forward on notch, and returns the
event dispatch loop for another go.
-- Dave
>>>>> "DR" == Dave Roberts <·············@re-move.droberts.com> writes:
[...]
DR> Hmmm... so basically, you're saying that I should convert
DR> whatever state names the user gives me into GENSYM'd ones? How
DR> is the best way to go about that? Temporary assoc list kept in
DR> the macro? [...]
You shouldn't need to do that. You have those symbols at macroexpansion
time so you can generate labels then. The expansion itself need not be
different (except you'd have gensyms instead of names). Hmm, you
probably are not asking this. What does 'kept in the macro' mean? The
expander? If so, yes, you could do that. Don't worry about efficiency
in the expander code, just use what's intuitive and easy for you. W/o
working the thing out, I think one could just collect the gensyms and
the corresponding actions in lists while walking through the arguments
and construct the appropriate forms in a second pass, or do it all in
one pass. But I might be wrong. In any event, the expander only needs
to be comprehensible -- not efficient or clever in an obscure way.
I think you are correct on the alternatives.
cheers,
BM
Bulent Murtezaoglu wrote:
>>>>>> "DR" == Dave Roberts <·············@re-move.droberts.com> writes:
> [...]
> DR> Hmmm... so basically, you're saying that I should convert
> DR> whatever state names the user gives me into GENSYM'd ones? How
> DR> is the best way to go about that? Temporary assoc list kept in
> DR> the macro? [...]
>
> You shouldn't need to do that. You have those symbols at macroexpansion
> time so you can generate labels then. The expansion itself need not be
> different (except you'd have gensyms instead of names). Hmm, you
> probably are not asking this. What does 'kept in the macro' mean? The
> expander? If so, yes, you could do that. Don't worry about efficiency
> in the expander code, just use what's intuitive and easy for you. W/o
> working the thing out, I think one could just collect the gensyms and
> the corresponding actions in lists while walking through the arguments
> and construct the appropriate forms in a second pass, or do it all in
> one pass. But I might be wrong. In any event, the expander only needs
> to be comprehensible -- not efficient or clever in an obscure way.
Yes, I was thinking in the expander code. Basically, I need a mapping table
that takes all the symbols the user gives me and converts them to GENSYM'd
ones, then I need to replace the user-supplied symbols both when I generate
the function names in the LABELS form, and also when I change to a new
state using (SETQ CURRENT-STATE ...).
Yes, I wasn't worrying about efficiency in the expander. That's why I
suggested an assoc list rather than a hashtable or something.
> I think you are correct on the alternatives.
Okay, cool. That means I'm starting to actually learn this stuff.
Thanks,
-- Dave
Dave Roberts <·············@re-move.droberts.com> writes:
> I need to go read-up on GENSYM a bit.
After you did, also read up on WITH-UNIQUE-NAMES and/or WITH-GENSYMS
(they are mostly identical). They make dealing with GENSYM in most
cases where you'd use it easier/more readable. The spec, and a
reference implementation, of WITH-UNIQUE-NAMES is available from
<http://www.cliki.net/with-unique-names>. IIRC, WITH-GENSYMS is from
Graham's On Lisp, if so this book (full text available online, in case
you didn't know) probably contains potentially helpfull discussion.
But do understand GENSYM and why/when you'd want to use it first
(shouldn't take long, it isn't really hard, and you seem to do well in
that regard anyway).
On 09 Feb 2004 00:38:20 +0100, Henrik Motakef <············@henrik-motakef.de> wrote:
> Dave Roberts <·············@re-move.droberts.com> writes:
>
>> I need to go read-up on GENSYM a bit.
>
> After you did, also read up on WITH-UNIQUE-NAMES and/or WITH-GENSYMS
> (they are mostly identical). They make dealing with GENSYM in most
> cases where you'd use it easier/more readable. The spec, and a
> reference implementation, of WITH-UNIQUE-NAMES is available from
> <http://www.cliki.net/with-unique-names>. IIRC, WITH-GENSYMS is from
> Graham's On Lisp, if so this book (full text available online, in
> case you didn't know) probably contains potentially helpfull
> discussion.
>
> But do understand GENSYM and why/when you'd want to use it first
> (shouldn't take long, it isn't really hard, and you seem to do well
> in that regard anyway).
While you're at it you might also want to look at REBINDING:
<·················································@ljosa.com>
Edi.
Dave Roberts <·············@re-move.droberts.com> writes:
> I looked at CASE and thought it seemed a bit more inefficient. It seemed
> faster to dispatch directly to a function rather than go through all the
> testing that CASE implies. TAGBODY seems to work well for machines that are
> self-contained and "run to completion" in a single call (something like a
> regular expression matcher or something). TAGBODY seemed less of a match
> when you want to fully exit the machine to go do something else for a while
> and then come back with another input. Are those impressions correct?
For a case on a symbol, it may be harder to generate a O(1) selection
mechanism (meaning that may be not all compilers do it), but for
integers, it's easy to compile a case into an array lookup.
So you could number the states and use (case state-num ((0) ...) ((1) ...) ...)
But if you don't plan to use more than a few states (such as when
implementing SMTP), I'd see no use in working harder on this... Put it
in perspective, even if a function call is 100 times slower than an
array dispatch, at >1GHz cycles, it does not represent more than 0.01
bit transmission time on a 1Mb/s link...
--
__Pascal_Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he doesn't
want merely because you think it would be good for him.--Robert Heinlein
http://www.theadvocates.org/
Pascal Bourguignon wrote:
> But if you don't plan to use more than a few states (such as when
> implementing SMTP), I'd see no use in working harder on this... Put it
> in perspective, even if a function call is 100 times slower than an
> array dispatch, at >1GHz cycles, it does not represent more than 0.01
> bit transmission time on a 1Mb/s link...
I agree fully. I was just looking for an efficient, general solution. In the
case of something like a server protocol, just about anything works fine
from a performance perspective. Remember, this is just an exercise to help
me learn. I certainly could have used CASE in the sample code I started to
write without any performance issues whatsoever.
-- Dave
Dave Roberts <·············@re-move.droberts.com> writes:
> (defsm <machine-name> (<input vars>) <start state name>
> (<state name> ( <test> <next-state-name> <forms...>)
> ( <test> <next-state-name> <forms...>))
> (<state name> ( <test> <next-state-name> <forms...>)
> ( <test> <next-state-name> <forms...>)))
Two suggestions regarding syntax: First, use long names, like
define-state-machine.
Second, I often find it beneficial to use the following pattern for
declarative syntax:
(define-foo name (options*) definitions*)
Note that this is the pattern of defclass, defun, etc. In this case it
might look like
(define-state-machine <name>
(:inputs (<inputs>) :initial-state <initial-state>)
<state-declarations>)
This is much more readable, IMHO. Another advantage is that you can
extend this syntax with new options without breaking old forms. And,
some lisp editors will indent/color/whatever forms like define-foo
according to this pattern.
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld <······@cs.uit.no> writes:
> (define-foo name (options*) definitions*)
>
> Note that this is the pattern of defclass, defun, etc.
Uhm, not defclass, of course. But many others.
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld wrote:
> Two suggestions regarding syntax: First, use long names, like
> define-state-machine.
Any particular reason, or just a preference thing? I'm assuming this would
be about readability. I was going for something that looked a little
"defun"-like.
> (define-state-machine <name>
> (:inputs (<inputs>) :initial-state <initial-state>)
> <state-declarations>)
>
> This is much more readable, IMHO. Another advantage is that you can
> extend this syntax with new options without breaking old forms. And,
> some lisp editors will indent/color/whatever forms like define-foo
> according to this pattern.
I actually thought about doing this, but I haven't gotten around to really
exploring key parameters yet. ;-) Good suggestion, though. I see how this
would help readability.
-- Dave
Dave Roberts <·············@re-move.droberts.com> writes:
> Any particular reason, or just a preference thing? I'm assuming this
> would be about readability. I was going for something that looked a
> little "defun"-like.
Of course it's about readability, which btw is very important. Defun
is a name loaded with history and a central part of the langugage,
either of which any operator you'll ever design is not.
--
Frode Vatvedt Fjeld
Dave Roberts <·············@re-move.droberts.com> writes:
> Okay, the flame retardant suit is on... ;-)
After posting here for a while you develop a leathery skin. It may
not impress the women so much, but it's a lot like the `super armor'
in a first-person shooter --- the projectiles simply bounce off.
> I'd love it if people would please give me some helpful criticism of my code
> and coding style. This is my first CL code, so please be constructive and
> gentle. I want to learn, not get told I'm an idiot. I already know that I'm
> an idiot, at least when it comes to CL, so tell me something I don't know.
Posting code is the number one way to get constructive criticism here.
> (defmacro defsm (smname inputs init-state &rest states)
> (labels ((cond-arm (transition)
> `(,(car transition)
> (setq current-state #',(cadr transition))
> ,@(cddr transition)))
> (per-state (state)
> (list (car state)
> (if (consp inputs)
> inputs
> (list inputs))
> `(cond ,@(mapcar #'cond-arm (cdr state))))))
> `(defun ,(intern (string-upcase (concatenate
> 'string
> "MAKE-"
> (symbol-name smname))))
> () ;; no parameters to the resulting function
> (let ((current-state))
> (labels ,(mapcar #'per-state states)
> (setq current-state #',init-state)
> (lambda ,(if (consp inputs)
> inputs
> (list inputs))
> (funcall current-state ,@inputs)))))))
This is quite good for a first time!
Others have made suggestions, so I won't repeat them here. I'll just
add my own.
I'd suggest that rather than constructing a `MAKE-' symbol from the
state machine name, you just use what the user provides. It may look
slightly funny to you, but there are issues with calling INTERN that
you can avoid by simply not using it. Consider these:
(define-state-machine |SomeCamelCaseName| ...)
resulting make function won't have same case.
(define-state-machine sequence ...)
resulting make function has symbol clash.
(define-state-machine my-package:sequence ...)
resulting make function *still* has symbol clash.
(define-state-machine foo ...)
;; But someone changed the readtable case.
(MAKE-FOO ...)
(define-state-machine foo ...)
;; but the *package* has changed
(other-package:make-foo ...)
If you supply the literal name as an argument, none of the above
problems will be encountered.
--
~jrm
Joe Marshall wrote:
> I'd suggest that rather than constructing a `MAKE-' symbol from the
> state machine name, you just use what the user provides. It may look
> slightly funny to you, but there are issues with calling INTERN that
> you can avoid by simply not using it. Consider these:
Okay, interesting. You're probably right in terms of style, but help me
through the following questions so I understand the issues for other
contexts. In particular, how do DEFSTRUCT and similar functions deal with
these issues? That was sort of the model I was going for.
>
> (define-state-machine |SomeCamelCaseName| ...)
> resulting make function won't have same case.
Ah, right. Hmmmm... would I avoid that just by not calling STRING-UPCASE, or
is the issue bigger than that?
>
> (define-state-machine sequence ...)
> resulting make function has symbol clash.
Hmmm... again, how does DEFSTRUCT deal with that?
>
> (define-state-machine my-package:sequence ...)
> resulting make function *still* has symbol clash.
I'm probably not understanding exactly how INTERN works, but can you explain
this one to me? I thought that INTERN with no package parameter interns it
into the current package, which shouldn't conflict, no?
>
> (define-state-machine foo ...)
> ;; But someone changed the readtable case.
> (MAKE-FOO ...)
Isn't this a problem in any case? If the user changes the readtable case,
doesn't that throw pretty much everything off-kilter anyway?
> (define-state-machine foo ...)
> ;; but the *package* has changed
> (other-package:make-foo ...)
I'm not yet familiar enough with packages to understand this one. Must do
further reading... ;-)
> If you supply the literal name as an argument, none of the above
> problems will be encountered.
Okay, cool.
-- Dave
Dave Roberts <·············@re-move.droberts.com> writes:
> Joe Marshall wrote:
>
>> I'd suggest that rather than constructing a `MAKE-' symbol from the
>> state machine name, you just use what the user provides. It may look
>> slightly funny to you, but there are issues with calling INTERN that
>> you can avoid by simply not using it. Consider these:
>
> Okay, interesting. You're probably right in terms of style, but help me
> through the following questions so I understand the issues for other
> contexts. In particular, how do DEFSTRUCT and similar functions deal with
> these issues? That was sort of the model I was going for.
DEFSTRUCT and similar functions have the same sort of issues.
>> (define-state-machine |SomeCamelCaseName| ...)
>> resulting make function won't have same case.
>
> Ah, right. Hmmmm... would I avoid that just by not calling STRING-UPCASE, or
> is the issue bigger than that?
Let me go through the steps and show you the places it goes wrong.
We'll assume that you have loaded the macro and are now going to
compile some code that uses the macro.
The first part of the process is reading the code. When read
encounters a token that it determines should be symbol, it calls
INTERN after accumulating the token. READ will generally *not* intern
the exact sequence of characters it is given. The unescaped
constituent characters are translated according to the READTABLE-CASE
slot in the readtable in use (which will be in *READTABLE*). Section
23.1.2.1 of the hyperspec gives these examples:
READTABLE-CASE Input Symbol-name
-------------------------------------
:UPCASE ZEBRA ZEBRA
:UPCASE Zebra ZEBRA
:UPCASE zebra ZEBRA
:DOWNCASE ZEBRA zebra
:DOWNCASE Zebra zebra
:DOWNCASE zebra zebra
:PRESERVE ZEBRA ZEBRA
:PRESERVE Zebra Zebra
:PRESERVE zebra zebra
:INVERT ZEBRA zebra
:INVERT Zebra Zebra
:INVERT zebra ZEBRA
When you are given an arbitrary symbol, it is not possible to
determine what the value of the readtable case was at the time the
symbol was read. When the user types
(define-state-machine foo ...)
He'll expect to be able to type (make-foo ...) later on.
The reader will intern both the symbol FOO and MAKE-FOO, but it will
do it according to the readtable. You cannot assume that it will intern
the token "make-foo" as "MAKE-FOO".
>> (define-state-machine sequence ...)
>> resulting make function has symbol clash.
>
> Hmmm... again, how does DEFSTRUCT deal with that?
It doesn't. (defstruct sequence x y) is not recommended.
>> (define-state-machine my-package:sequence ...)
>> resulting make function *still* has symbol clash.
>
> I'm probably not understanding exactly how INTERN works, but can you explain
> this one to me? I thought that INTERN with no package parameter interns it
> into the current package, which shouldn't conflict, no?
That is correct. But remember that the current package when the code
is read in may *not* be the current package when you expand the macro.
In the case I just mentioned, the symbol my-package:sequence has the
symbol name of "SEQUENCE", it just happens to be in "MY-PACKAGE"
rather than in "COMMON-LISP". When you
(INTERN (concatenate 'string "MAKE-" (symbol-name machine)))
This will intern into the current value of *PACKAGE* regardless of
where the original symbol is interned.
>> (define-state-machine foo ...)
>> ;; But someone changed the readtable case.
>> (MAKE-FOO ...)
>
> Isn't this a problem in any case? If the user changes the readtable case,
> doesn't that throw pretty much everything off-kilter anyway?
It does, but you'd expect it to do so *consistently*.
>> If you supply the literal name as an argument, none of the above
>> problems will be encountered.
You *could* also do something like this:
(intern (concatenate 'string (symbol-name '#:make-) (symbol-name users-symbol))
(symbol-package users-symbol))
But it is so much simpler and straightforward to let the user specify
*exactly* the name he wants.
--
~jrm
Joe Marshall wrote:
> DEFSTRUCT and similar functions have the same sort of issues.
So that explains a lot.
Thanks for the whole post. It was very helpful. I still need to read through
packages a few more times. I'm not quite sure I understand the fine points
of what you said regarding that, but the rest makes sense.
-- Dave
Joe Marshall wrote:
> DEFSTRUCT and similar functions have the same sort of issues.
So that explains a lot.
Thanks for the whole post. It was very helpful. I still need to read through
packages a few more times. I'm not quite sure I understand the fine points
of what you said regarding that, but the rest makes sense.
-- Dave
DAVE WROTE:
> [.....]
> I still need to read through packages a few more times.
> [.....]
If you are newbie (and idiot) try this:
[http://www.flownet.com/gat/packages.pdf]
("The Complete Idiot's Guide to Common Lisp Packages" by Erann Gat)
regards, szymon.
On 2004-02-08, Dave Roberts <·············@re-move.droberts.com> wrote:
|
| The following macro basically converts this to a generator function that
| returns a closure representing the new machine.
| ...
| (defmacro defsm (smname inputs init-state &rest states)
| (labels ((cond-arm (transition)
| `(,(car transition)
| (setq current-state #',(cadr transition))
| ,@(cddr transition)))
| (per-state (state)
| (list (car state)
| (if (consp inputs)
| inputs
| (list inputs))
| `(cond ,@(mapcar #'cond-arm (cdr state))))))
| `(defun ,(intern (string-upcase (concatenate
| 'string
| "MAKE-"
| (symbol-name smname))))
| () ;; no parameters to the resulting function
| (let ((current-state))
| (labels ,(mapcar #'per-state states)
| (setq current-state #',init-state)
| (lambda ,(if (consp inputs)
| inputs
| (list inputs))
| (funcall current-state ,@inputs)))))))
To avoid polluting the function namespace, I would instead use a
hashtable and have a function MAKE-STATE-MACHINE to create new state
machines, like so:
(defparameter *state-machines* (make-hash-table))
(defmacro define-state-machine (smname (init-state inputs) &body states)
(labels (...) ; as above
(setf (gethash smname *state-machines*)
(compile nil `(let (current-state)
(labels ,(mapcar #'per-state states)
(setq current-state #',init-state)
(lambda ,(if (consp inputs) inputs (list inputs))
(funcall current-state ,@inputs))))))))
(defun make-state-machine (smname)
(or (gethash smname *state-machines*)
(error "Unknown state machine ~a" smname)))
(define-state-machine smtp-server (...) ...)
(setq mm (make-state-machine 'smtp-server)) ; etc.
This would also avoid the problems with constructing your own symbols
behind the scenes that Joe Marshall pointed out in his post.
--
Cliff Crawford *** ·····@cornell.edu
"The perfection of art is to conceal art." -- Quintilian
Cliff Crawford <·····@cornell.edu> writes:
> To avoid polluting the function namespace, I would instead use a
> hashtable and have a function MAKE-STATE-MACHINE to create new state
> machines, like so:
I concur that MAKE-STATE-MACHINE would be stylistically better, but
I'd use the symbol's property list. Eg:
(defun make-state-machine (smname)
(assert (functionp (get smname 'state-machine))
((get smname 'state-machine))
"No state machine defined for ~S" smname)
(funcall (get smname 'state-machine)))
That way if you unintern the state machine's naming symbol, the state
machine disappears with it.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Cliff Crawford wrote:
> To avoid polluting the function namespace, I would instead use a
> hashtable and have a function MAKE-STATE-MACHINE to create new state
> machines, like so:
Given packages and such, is that really a big concern?
>
> (defparameter *state-machines* (make-hash-table))
>
> (defmacro define-state-machine (smname (init-state inputs) &body states)
> (labels (...) ; as above
> (setf (gethash smname *state-machines*)
> (compile nil `(let (current-state)
> (labels ,(mapcar #'per-state states)
> (setq current-state #',init-state)
> (lambda ,(if (consp inputs) inputs (list inputs))
> (funcall current-state ,@inputs))))))))
Hmmmm... now why did you call COMPILE in there? Isn't the result of the
macro about to be compiled anyway?
> (defun make-state-machine (smname)
> (or (gethash smname *state-machines*)
> (error "Unknown state machine ~a" smname)))
>
> (define-state-machine smtp-server (...) ...)
> (setq mm (make-state-machine 'smtp-server)) ; etc.
>
> This would also avoid the problems with constructing your own symbols
> behind the scenes that Joe Marshall pointed out in his post.
This basically creates a sub-namespace just for state machines. Again, the
question I would have is, isn't this sort of thing what the package system
is supposed to help solve? If so, why doesn't it solve the issue in this
particular case?
-- Dave
On 2004-02-08, Dave Roberts <·············@re-move.droberts.com> wrote:
| >
| > (defparameter *state-machines* (make-hash-table))
| >
| > (defmacro define-state-machine (smname (init-state inputs) &body states)
| > (labels (...) ; as above
| > (setf (gethash smname *state-machines*)
| > (compile nil `(let (current-state)
| > (labels ,(mapcar #'per-state states)
| > (setq current-state #',init-state)
| > (lambda ,(if (consp inputs) inputs (list inputs))
| > (funcall current-state ,@inputs))))))))
|
| Hmmmm... now why did you call COMPILE in there? Isn't the result of the
| macro about to be compiled anyway?
Because as I was typing it, at the same time I was thinking about how
you could implement it as a higher-order function instead, and got
confused....I knew I should've tested it before posting :) The setf
should be replaced with:
`(setf (gethash ,smname *state-machines*)
(let (current-state)
...))
| This basically creates a sub-namespace just for state machines. Again, the
| question I would have is, isn't this sort of thing what the package system
| is supposed to help solve? If so, why doesn't it solve the issue in this
| particular case?
I'm not really sure how the package system would help you, unless you
use a seperate package for state machines. It's more of a style
question, I think; using MAKE-STATE-MACHINE gives you a consistent
interface for constructing new state machines. In practice, however,
it probably doesn't matter if you create new functions for each state
machine you define, since you're probably not going to be defining
lots and lots of different state machines in a single application, so
the "pollution" would be minimal in that case.
--
Cliff Crawford *** ·····@cornell.edu
"The perfection of art is to conceal art." -- Quintilian
I took another shot at this, given some of the feedback. How's this for a
second try? In particular:
1. The function to create the state machine is named what the user created
it as.
2. I have used GENSYM to hopefully avoid capture. This is done for both the
CURRENT-STATE variable as well as all the user-named state functions. The
state names are added to an association list when they are required.
As a question, I was struggling a bit with form of STATE-NAME-TRANSITION,
the lexical function in the macro generator. What is a good way to
basically do the Lisp equivalent of this (in C/Java)
ret = assoc(statename, states-map);
if (ret == nil) {
ret = newassoc(statename, gensym());
addassoc(ret, states-map);
}
return ret;
I basically cobbled it together with a LET binding and an UNLESS form, but
it "felt" kludgy (particularly the random LET binding). What Lisp idiom
should I have used? The alternative would have been to use an IF form and
retrieve the assoc twice: (if (assoc statename states-map) (assoc statename
states-map) (progn ...code to install the new mapping...))
(defmacro define-state-machine (smname inputs init-state &rest states)
(let ((current-state (gensym))
(states-map nil))
(labels ((state-name-translation (statename)
(let ((ret (assoc statename states-map)))
(unless ret
(setq ret (cons statename (gensym)))
(push ret states-map))
(cdr ret)))
(cond-arm (transition)
`(,(car transition)
(setq ,current-state
#',(state-name-translation (cadr transition)))
,@(cddr transition)))
(per-state (state)
(list (state-name-translation (car state))
(if (consp inputs)
inputs
(list inputs))
`(cond ,@(mapcar #'cond-arm (cdr state))))))
`(defun ,smname
() ;; no parameters to the resulting function
(let ((,current-state))
(labels ,(mapcar #'per-state states)
(setq ,current-state #',(state-name-translation init-state))
(lambda ,(if (consp inputs)
inputs
(list inputs))
(funcall ,current-state ,@inputs))))))))
-- Dave
I should add, one thing I was not able to do was figure out the interaction
of &key and &rest parameters and thus was not able to take Frode Vatvedt
Fjeld's suggestion to make the input parameters and starting state
keywords. If somebody can show me how to do that, it would help. I actually
tried to grok both CLHS and CLtL on this point, but just ended up confused.
I think I understand how to use &key without &rest, but combining them
makes my head hurt. ;-)
-- Dave
Dave Roberts <·············@re-move.droberts.com> wrote in message news:<·······················@attbi_s51>...
> I should add, one thing I was not able to do was figure out the interaction
> of &key and &rest parameters and thus was not able to take Frode Vatvedt
> Fjeld's suggestion to make the input parameters and starting state
> keywords. If somebody can show me how to do that, it would help. I actually
> tried to grok both CLHS and CLtL on this point, but just ended up confused.
> I think I understand how to use &key without &rest, but combining them
> makes my head hurt. ;-)
"We can safely combine &rest and &key parameters though the behavior
may be a bit surprising initially."
http://www.gigamonkeys.com/book/functions.html
Erm, I hope Peter views this as free advertising for his book in
progress...
···········@yahoo.com (Tayssir John Gabbour) writes:
> Dave Roberts <·············@re-move.droberts.com> wrote in message news:<·······················@attbi_s51>...
> > I should add, one thing I was not able to do was figure out the interaction
> > of &key and &rest parameters and thus was not able to take Frode Vatvedt
> > Fjeld's suggestion to make the input parameters and starting state
> > keywords. If somebody can show me how to do that, it would help. I actually
> > tried to grok both CLHS and CLtL on this point, but just ended up confused.
> > I think I understand how to use &key without &rest, but combining them
> > makes my head hurt. ;-)
>
> "We can safely combine &rest and &key parameters though the behavior
> may be a bit surprising initially."
> http://www.gigamonkeys.com/book/functions.html
>
> Erm, I hope Peter views this as free advertising for his book in
> progress...
Yup. That's cool. BTW, there may be a few new chapters there since
last time I mentioned it. At least one. Feedback is, as always,
welcome and appreciated.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Dave Roberts <·············@re-move.droberts.com> writes:
> I should add, one thing I was not able to do was figure out the
> interaction of &key and &rest parameters [..]
I don't think you want to use &rest at all, because this goes against
the ability to extend the options. (The &rest parameter "uses up" all
the remaining positions indiscriminately.) Do for example something
like this
(defmacro define-state-machine (name (&key initial-state inputs)
&rest state-definitions)
....)
which results in syntax like
(define-state-machine foo (:inputs (a b c) :initial-state start)
(start ..)
...)
What is left for you to decide, is if any of the options are so
important and intuitive that they should be required arguments rather
than keywords. However I'd advise you to be quite cautious with this.
&rest in combination with &key is generally only used when you need to
forward all keyword arguments you receive, while looking at some of
them. Something like
(defun my-wrapper (x &key y z &rest all-keys &allow-other-keys)
(warn "yz: ~S~S" y z)
(apply #'wrapped-function x all-keys))
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld <······@cs.uit.no> writes:
> &rest in combination with &key is generally only used when you need to
> forward all keyword arguments you receive, while looking at some of
> them. Something like
> (defun my-wrapper (x &key y z &rest all-keys &allow-other-keys)
Though &rest must precede &key (in conforming programs), right?
--
Lars Brinkhoff, Services for Unix, Linux, GCC, HTTP
Brinkhoff Consulting http://www.brinkhoff.se/
Dave Roberts <·············@re-move.droberts.com> writes:
> I should add, one thing I was not able to do was figure out the interaction
> of &key and &rest parameters and thus was not able to take Frode Vatvedt
> Fjeld's suggestion to make the input parameters and starting state
> keywords. If somebody can show me how to do that, it would help. I actually
> tried to grok both CLHS and CLtL on this point, but just ended up confused.
> I think I understand how to use &key without &rest, but combining them
> makes my head hurt. ;-)
Think of it this way: The &rest argument gets everything after the
optionals and required. *After* this happens, the keyword arguments
are processed one at a time by poking around in the &rest argument for
the appropriate values.
--
~jrm
A few other questions I had when developing this code:
1. One of the nice things about the Lisp debugger is that it allows you to
hit an error, figure out what is up, traverse up and down the stack frames,
redefine something to correct the error, and then restart. Does the use of
lexical function definitions cause problems with this. For instance, if I
hit a problem in one of the definitions of my states, how would I redefine
a lexical function in a LABELS form in the debugger and restart? If this is
hard/impossible, does this argue more for using top-level functions,
accepting the resulting top-level name pollution?
2. Now that I switched to convert all the function names corresponding to
states to GENSYM'd symbols, this complicates debugging. While I avoid
variable capture, I can no longer tell which state the machine is in when
it blows up from a stack trace. Given this, would you risk variable capture
to get cleaner debugging, or just leave it with GENSYM'd symbols? Is there
any way to get both? Yes, I know that I could probably leave the assoc list
that the generator uses hanging around as some sort of debugging aid, but
it seems like a real pain to do hand conversions in the debugger when
you're striving for clarity of thought.
Thoughts?
-- Dave
On Mon, 09 Feb 2004 03:45:39 GMT
Dave Roberts <·············@re-move.droberts.com> wrote:
> 2. Now that I switched to convert all the function names corresponding
> to states to GENSYM'd symbols, this complicates debugging. While I
> avoid variable capture, I can no longer tell which state the machine
> is in when it blows up from a stack trace. Given this, would you risk
> variable capture to get cleaner debugging, or just leave it with
> GENSYM'd symbols? Is there any way to get both? Yes, I know that I
> could probably leave the assoc list that the generator uses hanging
> around as some sort of debugging aid, but it seems like a real pain to
> do hand conversions in the debugger when you're striving for clarity
> of thought.
[1]> (gensym)
#:G344
[2]> (gensym "foo")
#:|foo345|
Darius wrote:
> On Mon, 09 Feb 2004 03:45:39 GMT
> Dave Roberts <·············@re-move.droberts.com> wrote:
>
>> 2. Now that I switched to convert all the function names corresponding
>> to states to GENSYM'd symbols, this complicates debugging. While I
>> avoid variable capture, I can no longer tell which state the machine
>> is in when it blows up from a stack trace. Given this, would you risk
>> variable capture to get cleaner debugging, or just leave it with
>> GENSYM'd symbols? Is there any way to get both? Yes, I know that I
>> could probably leave the assoc list that the generator uses hanging
>> around as some sort of debugging aid, but it seems like a real pain to
>> do hand conversions in the debugger when you're striving for clarity
>> of thought.
>
> [1]> (gensym)
> #:G344
> [2]> (gensym "foo")
> #:|foo345|
Nice! Here's the new version and it solves exactly that point. Thanks.
(defmacro define-state-machine (smname inputs init-state &rest states)
(let ((current-state (gensym "current-state"))
(states-map nil))
(labels ((state-name-translation (statename)
(let ((ret (assoc statename states-map)))
(unless ret
(setq ret (cons
statename
(gensym
(symbol-name statename))))
(push ret states-map))
(cdr ret)))
(cond-arm (transition)
`(,(car transition)
(setq ,current-state
#',(state-name-translation (cadr transition)))
,@(cddr transition)))
(per-state (state)
(list (state-name-translation (car state))
(if (consp inputs)
inputs
(list inputs))
`(cond ,@(mapcar #'cond-arm (cdr state))))))
`(defun ,smname
() ;; no parameters to the resulting function
(let ((,current-state))
(labels ,(mapcar #'per-state states)
(setq ,current-state #',(state-name-translation init-state))
(lambda ,(if (consp inputs)
inputs
(list inputs))
(funcall ,current-state ,@inputs))))))))
Dave Roberts <·············@re-move.droberts.com> writes:
> [..] Thoughts?
Yes; don't be so afraid of "polluting" the top-level function
name-space. There is a balance to be found between using/defining
symbols indiscriminately and setting up hash-table name-spaces for
everything.
In your case, when you have such a clear concept as a state that maps
1:1 to top-level functions, give them names in the top-level
namespace. This how the lisp environment expects you to name
functions, and interacting with your system becomes much easier this
way.
I think the following is a good rule of thumb: Don't intern names that
are part of the syntax' primary functionality. Do intern names that
you just want to make available through the reader for
introspection/debugging/re-definition (i.e. interactive development)
purposes.
By this rule, defstruct is a bad design, because the reader and
constructor function-names that defstruct creats are certainly part of
that macro's primary functionality. The names should be mentioned
explicitly in the syntax, as is the case with the better-designed
defclass. In your state-machine case, however, the purpose (I suppose)
for interning the state function names would be to enable developers
to say e.g. (trace state-foo), (compile 'state-foo), or even
(defun state-foo (&rest args)
(break "oh no, entered state foo with ~S" args))
For such use, the package issues are not really that important. Create
names something like this:
(with-standard-io-syntax
(intern (format nil "~A-~A" 'state state-name)
(symbol-package state-name)))
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld <······@cs.uit.no> writes:
> Dave Roberts <·············@re-move.droberts.com> writes:
>
> > [..] Thoughts?
>
> Yes; don't be so afraid of "polluting" the top-level function
> name-space. There is a balance to be found between using/defining
> symbols indiscriminately and setting up hash-table name-spaces for
> everything.
I agree with this to an extent. Don't be afraid of defining things on
symbols that the macro's user types in. As long as the macro itself
doesn't do any INTERNing of weird strings, ie, as long as the user
came up with the name, you're fine.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Dave Roberts <·············@re-move.droberts.com> writes:
> A few other questions I had when developing this code:
>
> 1. One of the nice things about the Lisp debugger is that it allows you to
> hit an error, figure out what is up, traverse up and down the stack frames,
> redefine something to correct the error, and then restart. Does the use of
> lexical function definitions cause problems with this?
Not necessarily, but quite likely. It depends on the implementation.
> 2. Now that I switched to convert all the function names corresponding to
> states to GENSYM'd symbols, this complicates debugging. While I avoid
> variable capture, I can no longer tell which state the machine is in when
> it blows up from a stack trace. Given this, would you risk variable capture
> to get cleaner debugging, or just leave it with GENSYM'd symbols? Is there
> any way to get both?
Yes, use a named gensym: (gensym "FOO-") => #:FOO-21524
--
~jrm