State machine representation
Dave Roberts
interested in is communications protocols, so I figured that I'd try some
practice projects in that area. Being that I have a hardware engineering
background and protocols are often designed in terms of state machines, I
tend to write reactive, event-driven state machine systems frequently.
So, in the course of my practice, a natural question came up: What's the
"best" way to represent a state machine in CL, and why? Obviously, the
question is loaded and there is no right answer. I'm looking for
experienced opinions here. The various possible solutions I have toyed with
include:
1. Just represent state machines simply with an integer or symbol state
variable and a case or cond form which switches on the current state. The
forms associated with any case/cond clause then determine the next state.
2. Represent each state with a different function, bound at top-level. The
state machine can then be represented as a list or structure, with those
functions operating on it.
3. Represent the state machine with a closure. Basically:
(defun make-state-machine ....
(let ((statevar1)
(statevar2)
(current-state))
(flet ((state1 (input) ...)
(state2 (input) ...))
(setq current-state state1)
(lambda (input) (funcall current-state input)))))
This is sort of "object-oriented" in the sense that the enclosure
encapsulates the total state and outsiders can't get into it without the
state machine itself exposing the state.
4. Finally, you could obviously do this with full CLOS objects, with the
machine being an object and states being represented by either additiona
CLOS objects or by a combination of variables and functions.
So, a question for all the Lisp Wizards: What is your favorite technique for
state machines.
Thanks,
-- Dave
Kenny Tilton
Dave Roberts wrote:
> So I'm learning CL and trying to write various programs. One thing that I'm
> interested in is communications protocols, so I figured that I'd try some
> practice projects in that area. Being that I have a hardware engineering
> background and protocols are often designed in terms of state machines, I
> tend to write reactive, event-driven state machine systems frequently.
>
> So, in the course of my practice, a natural question came up: What's the
> "best" way to represent a state machine in CL, and why? Obviously, the
> question is loaded and there is no right answer. I'm looking for
> experienced opinions here. The various possible solutions I have toyed with
> include:
>
> 1. Just represent state machines simply with an integer or symbol state
> variable and a case or cond form which switches on the current state. The
> forms associated with any case/cond clause then determine the next state.
That's what I have done with some simple machines. Symbols definitely,
for readability, plus numbers would not work with CASE.
>
> 2. Represent each state with a different function, bound at top-level. The
> state machine can then be represented as a list or structure, with those
> functions operating on it.
>
> 3. Represent the state machine with a closure. Basically:
> (defun make-state-machine ....
> (let ((statevar1)
> (statevar2)
> (current-state))
> (flet ((state1 (input) ...)
> (state2 (input) ...))
> (setq current-state state1)
> (lambda (input) (funcall current-state input)))))
Not bad.
kt
Jens Axel Søgaard
> So, a question for all the Lisp Wizards: What is your favorite technique for
> state machines.
I hope you will find Shriram Krishnamurthi's "The Swine before the Perl"
interesting.
--
Jens Axel Søgaard
Matthew Danish
> That's what I have done with some simple machines. Symbols definitely,
> for readability, plus numbers would not work with CASE.
Not true; numbers do work with CASE, since CASE compares as if with EQL.
If the equality operator is not specified (as with CASE), then EQL is
the default, according to the definition of /same/ in the glossary. The
Hyperspec even has an example of CASE on numbers.
--
; Matthew Danish <mda...@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
Gareth McCaughan
> 1. Just represent state machines simply with an integer or symbol state
> variable and a case or cond form which switches on the current state. The
> forms associated with any case/cond clause then determine the next state.
>
> 2. Represent each state with a different function, bound at top-level. The
> state machine can then be represented as a list or structure, with those
> functions operating on it.
I'm not sure I understand what you mean by this one.
> 3. Represent the state machine with a closure. Basically:
> (defun make-state-machine ....
> (let ((statevar1)
> (statevar2)
> (current-state))
> (flet ((state1 (input) ...)
> (state2 (input) ...))
> (setq current-state state1)
> (lambda (input) (funcall current-state input)))))
>
> This is sort of "object-oriented" in the sense that the enclosure
> encapsulates the total state and outsiders can't get into it without the
> state machine itself exposing the state.
>
> 4. Finally, you could obviously do this with full CLOS objects, with the
> machine being an object and states being represented by either additiona
> CLOS objects or by a combination of variables and functions.
>
> So, a question for all the Lisp Wizards: What is your favorite technique for
> state machines.
If your Lisp implementation does full tail-call optimization,
then you can modify #3 so that each state calls the next
directly (without the external driver you evidently have).
You could put everything into a tagbody, represent states
by tags, and use GO to change state. Very low-level, but then
a state machine is a pretty low-level construct. Again, this
assumes that each state is responsible for reading input or
whatever else it needs to do.
Another way of using CLOS is to represent the state by a
symbol and make what happens in each state be defined by
a method with an EQL specializer.
(defmethod process ((state (eql 'waiting-for-packet)) input)
...)
(defmethod process ((state (eql 'in-data-packet)) input)
...)
One advantage of this is that if there's some common stuff that
each state needs to do, you can say
(defmethod process (state input)
...)
and then use CALL-NEXT-METHOD, or some sort of non-standard
method combination.
--
Gareth McCaughan
.sig under construc
Paolo Amoroso
> So I'm learning CL and trying to write various programs. One thing that I'm
> interested in is communications protocols, so I figured that I'd try some
You may check Etiquette:
Project page
http://sourceforge.net/projects/etiquette
Quickstart guide
http://sourceforge.net/docman/display_doc.php?docid=17729&group_id=8411
Paolo
--
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Edi Weitz
> Quickstart guide
> http://sourceforge.net/docman/display_doc.php?docid=17729&group_id=8411
<http://sourceforge.net/docman/display_doc.php?docid=17729&group_id=84118>
Edi.
Kenny Tilton
Matthew Danish wrote:
> On Sun, Feb 01, 2004 at 09:07:01AM +0000, Kenny Tilton wrote:
>
>>That's what I have done with some simple machines. Symbols definitely,
>>for readability, plus numbers would not work with CASE.
>
>
> Not true; numbers do work with CASE, since CASE compares as if with EQL.
Oops. I forgot that the problem is if the key is not a literal since the
key is not evaluated, so if the OP wanted to use defconstant to set up
symbolic forms for the states (using literals would be madness) then
they would have to use #.FSM-INITIAL and #.FSM-BUILDING-INTEGER.
kt
--
http://tilton-technology.com
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
Paul Tarvydas
programming construct, you need to consider:
a) entry code - code that is executed when a state is entered
b) exit code - code that is executed when you leave a state
c) transition code - code that is executed when a particular state-to-state
transition is taken
d) hierarchical states - (a la Harel Statecharts) state machines nested
inside of parent states, where transitions into and out of the parent state
are "inherited" by the nested states - for example an "error" or "reset"
transition out of a parent state causes all nested machines to execute
their exit code, deepest first.
The protocol for performing a "step" of a state machine, triggered by an
incoming reactive event is:
1) exit current state
2) determine which particular transition is to be taken, then execute its
transition code
3) enter next state.
(Suitably augmented by considerations for hierarchical states).
None of the suggestions, thus far, have addressed these issues. For example
"go" is insufficient for performing a transition (since it must perform the
above protocol). Symbols / case #'s are insufficient because a sate
transition has a least 3 parts.
If I wanted debug-ability, I would implement state machines using defstructs
or clos objects along with a state-walking engine (which would have
state-single-stepping built into it).
If I wanted performance, I would implement a state compiler using lisp
macros (e.g. define defmachine and defstate macros) that unroll the control
flow within a machine into the hoary combination of case's, go's and
name-manglings necessary to efficiently encode the above logic.
In a language other than lisp, the state compiler would generally be
"outside of" the language, i.e. a separate compiler program which emits
source code in the target language and then is compiled again by the
target-language compiler.
This demonstrates one of the features of CL - due to a combination of its
regular syntax and its macros, CL has a compiler-compiler (think "Antlr" or
"YACC") built into the language. [And, just to over-do the analogy, lisp
comes pre-LEX'ed - "symbols" are "tokens". "LEX" is built into CL via the
reader.]
Great physicists solve a problem by inventing a notation to describe the
problem, first. Good lispers do the same.
pt
Dave Roberts
> You may check Etiquette:
>
> Project page
> http://sourceforge.net/projects/etiquette
Yes, I actually found etiquette prior to your message and was checking it
out. I was interested that they used CLOS for most of it. That was actually
one of the things that prompted my question.
-- Dave
Dave Roberts
> Dave Roberts <ld...@re-move.droberts.com> writes:
>> 2. Represent each state with a different function, bound at top-level.
>> The state machine can then be represented as a list or structure, with
>> those functions operating on it.
>
> I'm not sure I understand what you mean by this one.
I basically mean what I wrote for number 3, below, but without the closure.
That is, you could just represent states by functions stored in a top-level
variable:
(defun state1 (params) ...)
(defun state2 (params) ...)
(setq current-state #'state1)
Right?
Then you state machine driver simply becomes:
(funcall current-state params)
In each state, they (setq current-state ...) however they need to in order
to move to the next state.
>> 3. Represent the state machine with a closure. Basically:
>> (defun make-state-machine ....
>> (let ((statevar1)
>> (statevar2)
>> (current-state))
>> (flet ((state1 (input) ...)
>> (state2 (input) ...))
>> (setq current-state state1)
>> (lambda (input) (funcall current-state input)))))
>>
>> This is sort of "object-oriented" in the sense that the enclosure
>> encapsulates the total state and outsiders can't get into it without the
>> state machine itself exposing the state.
>>
>> 4. Finally, you could obviously do this with full CLOS objects, with the
>> machine being an object and states being represented by either additiona
>> CLOS objects or by a combination of variables and functions.
>>
>> So, a question for all the Lisp Wizards: What is your favorite technique
>> for state machines.
>
> If your Lisp implementation does full tail-call optimization,
> then you can modify #3 so that each state calls the next
> directly (without the external driver you evidently have).
Doesn't CL require this? I know that Scheme does.
> You could put everything into a tagbody, represent states
> by tags, and use GO to change state. Very low-level, but then
> a state machine is a pretty low-level construct. Again, this
> assumes that each state is responsible for reading input or
> whatever else it needs to do.
Interesting. That would work well and is a technique I hadn't thought of
(this is one of the things that I love about Lisp). The downside here is
that it basically consumes the thread during the complete running of the
state machine. I was thinking about something that was more reactive and
event-driven. Also, how efficient is tagbody for large numbers of tags? I
don't know how it's implemented. Worst case, it could be just a linear
search of an association list or something.
> Another way of using CLOS is to represent the state by a
> symbol and make what happens in each state be defined by
> a method with an EQL specializer.
Yea, this is pretty elegant. I assume that this is worse for performance
however, as the more complex you get with your dispatching, the more CLOS
has to work to figure out which method to use, right? I mean, nothing is
free. It's more elegant that simply putting a huge (cond ...) form
somewhere from a maintenance point of view, but basically CLOS has to
execute the functional equivalent of that (cond...) in order to dispatch.
One of the things I like about first-class functions is that you can store
them in variables and simply bypass all the dispatch logic. Very fast, no?
> (defmethod process ((state (eql 'waiting-for-packet)) input)
> ...)
>
> (defmethod process ((state (eql 'in-data-packet)) input)
> ...)
>
> One advantage of this is that if there's some common stuff that
> each state needs to do, you can say
>
> (defmethod process (state input)
> ...)
>
> and then use CALL-NEXT-METHOD, or some sort of non-standard
> method combination.
Yes. Definitely, of the approaches I looked at, CLOS was the most flexible.
(I have just dipped my toes into CLOS, but it seems like it's a whole other
world there, huge in size, scope, and power. My plan is to get a reasonable
grounding of the basics of "vanilla" CL and then dive into CLOS.)
Thanks for your reply.
-- Dave
Dave Roberts
> In any language, if you want to use state machines as a *serious*
> programming construct, you need to consider:
>
> a) entry code - code that is executed when a state is entered
>
> b) exit code - code that is executed when you leave a state
>
> c) transition code - code that is executed when a particular
> state-to-state transition is taken
>
> d) hierarchical states - (a la Harel Statecharts) state machines nested
> inside of parent states, where transitions into and out of the parent
> state are "inherited" by the nested states - for example an "error" or
> "reset" transition out of a parent state causes all nested machines to
> execute their exit code, deepest first.
>
> The protocol for performing a "step" of a state machine, triggered by an
> incoming reactive event is:
>
> 1) exit current state
>
> 2) determine which particular transition is to be taken, then execute its
> transition code
>
> 3) enter next state.
>
> (Suitably augmented by considerations for hierarchical states).
Right. My plan was to play around with some simple protocol state machines
and then develop a more general macro "language" that implements more fully
general state machines. I figured this would be a good exercise to learn
both the basics of CL and then make my way into non-trivial macros.
> None of the suggestions, thus far, have addressed these issues. For
> example "go" is insufficient for performing a transition (since it must
> perform the
> above protocol). Symbols / case #'s are insufficient because a sate
> transition has a least 3 parts.
Depends on how complex your state machines are. If you have a hardware
background, you understand the difference between Mealy and Moore state
machines. Moore state machines associates actions to the entry of states
themselves, while Mealy assigns them to the transitions between states.
Moore state machines are more simply and work well for small problems, but
can lead to state explosion if the machine logic is really complex. The
things you describe above are all nice generalizations of Mealy machines
and further increase flexibility and reduce state explosion. They're nice,
but they aren't *required* to make state machines work.
> If I wanted debug-ability, I would implement state machines using
> defstructs or clos objects along with a state-walking engine (which would
> have state-single-stepping built into it).
Right. That was one of the things I was looking at.
> If I wanted performance, I would implement a state compiler using lisp
> macros (e.g. define defmachine and defstate macros) that unroll the
> control flow within a machine into the hoary combination of case's, go's
> and name-manglings necessary to efficiently encode the above logic.
That was step 2 of my plan. ;-)
> In a language other than lisp, the state compiler would generally be
> "outside of" the language, i.e. a separate compiler program which emits
> source code in the target language and then is compiled again by the
> target-language compiler.
>
> This demonstrates one of the features of CL - due to a combination of its
> regular syntax and its macros, CL has a compiler-compiler (think "Antlr"
> or
> "YACC") built into the language. [And, just to over-do the analogy, lisp
> comes pre-LEX'ed - "symbols" are "tokens". "LEX" is built into CL via the
> reader.]
Yes, exactly. That's one of the reasons for the exercise from my side. I
want to understand this machinery and flexibility in greater detail. I have
done the reading, now I want to flex my mental muscles.
> Great physicists solve a problem by inventing a notation to describe the
> problem, first. Good lispers do the same.
Yes, exactly. That's precisely what I want to do. I have written state
machines in lots of different languages over the years. In some, the amount
of baggage you need to write to get a maintainable system is large, and the
more maintainable the system is, the slower it typically operates. My goal
is to learn about how I could implement the system in low-level constructs,
then develop a macro language on top of those ideas that allows simple,
maintainable expression, but transformation down to the efficient
representations.
Anyway, this is just a self-imposed exercise for myself to get me to work
through the details. Thanks for the discussion. Your input is spot on.
-- Dave
Dave Roberts
Excellent, I'll have a look. Actually, just about all the various
presentations at that conference look interesting. Thanks for the link.
-- Dave
Dave Roberts
>> 1. Just represent state machines simply with an integer or symbol state
>> variable and a case or cond form which switches on the current state. The
>> forms associated with any case/cond clause then determine the next state.
>
> That's what I have done with some simple machines. Symbols definitely,
> for readability, plus numbers would not work with CASE.
Right. Doesn't seem like it scales as well, however. Lots of top-level
namespace pollution. Probably the most simple way to get it done, however.
For simple programs, this seems like what I would use if I didn't have a
macro language built up to define state machines nicely (my eventual goal).
>> 2. Represent each state with a different function, bound at top-level.
>> The state machine can then be represented as a list or structure, with
>> those functions operating on it.
>>
>> 3. Represent the state machine with a closure. Basically:
>> (defun make-state-machine ....
>> (let ((statevar1)
>> (statevar2)
>> (current-state))
>> (flet ((state1 (input) ...)
>> (state2 (input) ...))
>> (setq current-state state1)
>> (lambda (input) (funcall current-state input)))))
>
> Not bad.
Thanks, I'm learning. I sense that closures are powerful constructs, but I'm
sort of struggling for how/when to use them. Typically, it seems like you
can always get something done another way, and so I struggle with when to
use that tool.
-- Dave
Dave Roberts
> Oops. I forgot that the problem is if the key is not a literal since the
> key is not evaluated, so if the OP wanted to use defconstant to set up
> symbolic forms for the states (using literals would be madness) then
> they would have to use #.FSM-INITIAL and #.FSM-BUILDING-INTEGER.
This seems like one of the areas where CL sort of botched this up. I keep
encountering lots of places I need #', and by implication #. (like in
apply, funcall, etc.). Scheme seems to have gotten this right. It's simple
philosophy that symbols just evaluate to one thing really helps. You just
use "define" and then things evaluate correctly.
As a question, is there some hidden power that CL's system provides, or is
it largely a waste of time? I'm sure somebody could create a contrived
example of where I might want it, but does it really come up all that
often? Most of the example code I have read doesn't make use of the power
that might be there, so I'm seriously questioning it.
-- Dave
Matthew Danish
I'm not sure why you connect #' and #. as they are completely different
constructions. #'foo becomes (FUNCTION foo) and #.foo means ``evaluate
foo at read-time.'' Since CASE expects all of the keys to be statically
determinable, you need to use #. to sneak in the value of a variable
(and then only at read-time).
As for #'foo, I suggest that you read my 3 recent posts in the ``Lisp's
future'' thread, as they address your question asked by someone else.
Dave Roberts
> I'm not sure why you connect #' and #. as they are completely different
> constructions. #'foo becomes (FUNCTION foo) and #.foo means ``evaluate
> foo at read-time.'' Since CASE expects all of the keys to be statically
> determinable, you need to use #. to sneak in the value of a variable
> (and then only at read-time).
Okay, my mistake. I have only had to deal with #' so far. I assumed that #.
was for retrieving the values of constants. I understand what it does now
and I can see the value of that.
> As for #'foo, I suggest that you read my 3 recent posts in the ``Lisp's
> future'' thread, as they address your question asked by someone else.
Great. I'll take a look.
Thanks,
-- Dave
Erik Naggum
| This seems like one of the areas where CL sort of botched this up.
Why do you need to make this kind of comment?
--
Erik Naggum | Oslo, Norway 2004-032
Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.
Erann Gat
<ld...@re-move.droberts.com> wrote:
> Kenny Tilton wrote:
>
> > Oops. I forgot that the problem is if the key is not a literal since the
> > key is not evaluated, so if the OP wanted to use defconstant to set up
> > symbolic forms for the states (using literals would be madness) then
> > they would have to use #.FSM-INITIAL and #.FSM-BUILDING-INTEGER.
>
> This seems like one of the areas where CL sort of botched this up. I keep
> encountering lots of places I need #', and by implication #. (like in
> apply, funcall, etc.). Scheme seems to have gotten this right. It's simple
> philosophy that symbols just evaluate to one thing really helps. You just
> use "define" and then things evaluate correctly.
There are good reasons why CL does it the way it does, but you will find
that people around here will be reluctant to explain them to you if you
open by proclaiming that "CL sort of botched this up".
E.
Dave Roberts
> * Dave Roberts
> | This seems like one of the areas where CL sort of botched this up.
>
> Why do you need to make this kind of comment?
Sorry, just making an observation. I wasn't trying to provoke, if that's
what you're implying. Specifically, I was comparing CL's way of handling
functions bound to symbols with that of Scheme, which honestly does seem
cleaner, in my not so educated opinion. There are many places where this
sort of crops up. In general, Scheme seems more clean and streamlined
("regular" ?). CL seems to have a few more peculiarities earned from more
years of doing more serious large-scale programming (now I'll offend the
Scheme guys by implying that Scheme hasn't done anything serious--again,
that's not what I'm saying).
Anyway, there are typically a couple of reasons for peculiarities like this
in a language. They are:
1. The language just sort of evolved, and this is one of the places where
that shows. We couldn't go back and clean up every last nit of syntactic
irregularity, because that would break too much code.
2. There is a very good reason that this works the way it is. You're just
missing it, Mr. Roberts, because you're a newbie. Again, if this is the
case, please educate me. It's easier to tolerate certain irregularities if
there is a good reason for them.
Anyway, I was not trying to offend. If you believe there is a lot of
advantage in CL's way of doing things, please share. I want to understand
if there is something I may have missed.
-- Dave
Bulent Murtezaoglu
DR> [...] Again, if this is the case, please educate me. It's
DR> easier to tolerate certain irregularities if there is a good
DR> reason for them. [...]
I don't know if anyone pointed this out but here's a good reference
for you to read:
http://www.nhplace.com/kent/Papers/Technical-Issues.html
cheers,
BM
Matthew Danish
The ideas of a variable bound to a value and a symbol bound to a value
are separate. Symbols are only bound to values incidentally through the
SYMBOL-VALUE slot of the symbol object. Lexical variables, for example,
have nothing to do with the values contained in symbols. The only
relation lexical variables have to symbols is that symbols name
variables. And generally compiled code discards that relationship.
The other thing: there is nothing preventing a variable from being bound
to a function object. You can do:
(let ((a (lambda (x) x)))
(funcall a 1))
And feel somewhat Scheme-y.
CL also has a namespace for variables that are to be bound exclusively
to functions. In the above example, the symbol A names a variable bound
to a function. In the following example, the symbol A names a function
variable bound to a function:
(flet ((a (x) x))
(a 1))
By default, in the arguments of a function call, CL expects that symbols
will name ordinary variables. If you want a symbol to name the function
variable in the alternate namespace, then you use #'A.
(let ((a (lambda (x) x))) ; ordinary variable binding declaration
(flet ((a (x) x)) ; function variable binding declaration
(foo a) ; A names the ordinary variable
(foo #'a))) ; #'A names the function variable
Dave Roberts
> As for #'foo, I suggest that you read my 3 recent posts in the ``Lisp's
> future'' thread, as they address your question asked by someone else.
Okay, so I just read those. Thanks! That helped a lot. The summary, from my
side is, I just wasn't seeing the larger issues. Your posts and Pascal
Costanza's really helped me see why this actually makes sense and isn't
just a random wart.
If it helps, understand that my earliest introduction to Lisp was via Scheme
in 1989 or so. I still have a fondness for the clean syntax of Scheme. Like
I said in my post to Erik Naggum, there are two reasons for things like
this in a language: either they are warts left behind as evolution grinds
through language design (think about large parts of C++, for instance) and
you want to keep compatibility with old code, or there are really good
reasons for it and I as the original poster just wasn't seeing it. In this
case, it was the latter.
Your post showed why there are larger issues to consider. In fact, I can
plainly see that while Scheme's simplistic treatment of this issue works
better for teaching and general programming usage, it would suffer
tremendously when trying to "program in the large" for sizable projects.
Anyway, thanks. That helped. A lot. ;-)
- Dave
Dave Roberts
Okay, fair enough. I wasn't trying to be inflamitory, as I replied to Erik
Naggum. I was just expressing an (incorrect, as I now find out)
observation.
Anyway, please educate me. I want to learn. I read Matthew Danish's posts
and some by Pascal Costanza. I'm now reading a Gabriel & Pitman article
that Pascal pointed to in one of his other posts
(http://www.dreamsongs.com/Separation.html), which seems to explain a lot
of it (though I'm still reading through it as I write this).
So, in summary, I apologize for stepping in somebody's oatmeal. I'm just
working through probably all the standard newbie issues. When I see
something like I saw, my own tendency is to say, "This looks goofy." Please
feel free to reply, "Dave, you're a clueless newbie. Here's why it's really
smart, not goofy: ..."
-- Dave
Harald Hanche-Olsen
| Gareth McCaughan wrote:
|
| > If your Lisp implementation does full tail-call optimization,
| > then you can modify #3 so that each state calls the next
| > directly (without the external driver you evidently have).
|
| Doesn't CL require this?
No, among other reasons because it makes debugging harder. Search for
old messages on this newsgroup for details. Kent Pitman, in
particular, has written at length on this topic.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- Debating gives most of us much more psychological satisfaction
than thinking does: but it deprives us of whatever chance there is
of getting closer to the truth. -- C.P. Snow
Harald Hanche-Olsen
| Specifically, I was comparing CL's way of handling functions bound
| to symbols with that of Scheme, which honestly does seem cleaner, in
| my not so educated opinion.
I suggest you go back and search this newsgroup for discussions on the
single name space issue. Once more, I can recommend Kent Pitman's
articles. (I have no idea how hard they will be to find using the
standard search engines, but it's worth the effort. And I am sure we
wouldn't care to rehash the whole discussion all over again. We could
use some artificial intelligence scanning the newsgroup and indexing
stuff by topic, not just by words and phrases.)
| In general, Scheme seems more clean and streamlined ("regular" ?).
Ah, but to borrow a metaphor from Neal Stephenson's Cryptonomicon, so
does a drill made for the home user when compared to one made for the
professional builder. The latter may look ugly, but it is totally
reliable and gets the job done with a minimum of fuzz. And the
ugliness just fades away as you begin to appreciate the tool for what
it can do.
Erik Naggum
| Specifically, I was comparing CL's way of handling functions bound to
| symbols with that of Scheme, which honestly does seem cleaner, in my
| not so educated opinion.
So the first language you learned is better than the next language you
set out to learn? That attitude is the reason people never learn to
speak anything but their first language well.
I just commented on this phenomenon over in misc.metric-system, in
<2004-032-8...@naggum.no>. It certainly applies here, too.
| Anyway, I was not trying to offend. If you believe there is a lot of
| advantage in CL's way of doing things, please share. I want to
| understand if there is something I may have missed.
What you have missed is that languages are the products of evolution.
Just learn the language at hand. Do not compare it to anything else,
or you will continue to write and think in whatever you compare with.
Have you ever tried to compare a potential girlfriend with your first?
The urge to compare may be human, but if so, it ranks up there with
errare humanum est -- you expend effort not to make mistakes precisely
because it is so human. There is no way to avoid offending people if
you keep comparing them to other people all the time. Languages are
the products of people and all those who use them are people. Imagine
someone who compares you to some other bloke all the time if you have
a hard time with the metaphors I have used, and you should be able to
realize that the act of comparing is the fundamental insult. Not only
does comparing with something else prevent you from appreciating what
something is on its own merits, you will naturally resist comparisons
that make it evident that it is superior to what you compare it with.
If you wish to speak Common Lisp with a strong Scheme accent, you are
well on your way. I cannot imagine why anyone would /want/ to speak
with a strong accent, but then again, I have been known to be hostile
to people who use their dialects outside of their home town and have
this incredibly annoying urge to tell me where they grew up instead of
anything worth hearing about. While this bizarre ritual is somehow a
human right in the eyes of those who do it, the computer will not be
impressed with your heritage, will not consider you a honorary member
of its tribe because you exhibit the same regionally accepted speech
impediments, and will not congratulate you on how well you speak a
foreign language despite the rather annoying and obvious flaws. So my
advice to you, and this is pretty strongly felt because I believe that
the first thing you learn is an irrelevant accident of timing which
must not prevent you from learning new things that accidentally arrive
within your sensory experiences later, is that you completely forget
everything you learned from Scheme and start afresh with Common Lisp
in its own right, on its own merits.
Otherwise, I may want to compare you to all the other people who have
never learned Common Lisp because they were stuck in Compareville.
Dave Roberts
> Just a few pre-emptive clarifications:
>
> The ideas of a variable bound to a value and a symbol bound to a value
> are separate. Symbols are only bound to values incidentally through the
> SYMBOL-VALUE slot of the symbol object. Lexical variables, for example,
> have nothing to do with the values contained in symbols. The only
> relation lexical variables have to symbols is that symbols name
> variables. And generally compiled code discards that relationship.
Matt, first let me say that your posts are really helping me work through.
That said, I don't think I understand the above paragraph. Part of it is
that I'm struggling with the various CL terminology for "cell," "object,"
"symbol," "variable," and "binding." I'm coming from a C->C++->Java sort of
background and so that's clouding my thinking. What may help me is to sort
of describe a simplistic implementation of this in C terms, so I can make
the translation. I have bits and pieces of it, and just when I think I'm
making some headway, I read something like the paragraph above that shows
that I don't yet have it. ;-)
> The other thing: there is nothing preventing a variable from being bound
> to a function object. You can do:
>
> (let ((a (lambda (x) x)))
> (funcall a 1))
>
> And feel somewhat Scheme-y.
Yes, and this is one thing that confuses me. So what is happening in this
case? By my probably incorrect notion of what's happening under the hood,
the LET form is creating a new local symbol(?) named "a," and then binding
the value portion(?) of that symbol to the lamba expression object. Is that
right? So what's a variable as opposed to a symbol/binding?
> CL also has a namespace for variables that are to be bound exclusively
> to functions. In the above example, the symbol A names a variable bound
> to a function. In the following example, the symbol A names a function
> variable bound to a function:
>
> (flet ((a (x) x))
> (a 1))
So is the best way to think about this as two different variables, one
capable of holding functions and the other values, or is it better to think
of a single named symbol ("A"), that has pointers/references, one to a
value and the other to and object. In other words, a symbol is implemented
as a structure with these things along with a reference to a property list
and all the other things that a symbol has.
> By default, in the arguments of a function call, CL expects that symbols
> will name ordinary variables. If you want a symbol to name the function
> variable in the alternate namespace, then you use #'A.
>
> (let ((a (lambda (x) x))) ; ordinary variable binding declaration
> (flet ((a (x) x)) ; function variable binding declaration
> (foo a) ; A names the ordinary variable
> (foo #'a))) ; #'A names the function variable
So this brings up a good question: If these are implemented as the same
symbol with two "slots" (not to be confused with CLOS slots), then it seems
like this would cause problems. If these are really two separate symbols in
two separate namespaces (like if I was doing name mangling internally or
something to value-A and function-A), that would seem to be better. The
binding for "function-A" would go away as the FLET form was exited, while
that would still leave "value-A" around until the LET form exited. If these
are the same symbol, "A," with just two slots, I'm not sure how it would be
handled when the FLET form went out of scope and yet I was still in the LET
scope.
-- Dave
Dave Roberts
> I don't know if anyone pointed this out but here's a good reference
> for you to read:
>
> http://www.nhplace.com/kent/Papers/Technical-Issues.html
I think I found a reference that Pascal Costanza provided to the same paper
on Gabriel's site, rather than Pitman's
(http://www.dreamsongs.com/Separation.html).
Thanks,
-- Dave
Dave Roberts
> + Dave Roberts <ld...@re-move.droberts.com>:
>
> | Gareth McCaughan wrote:
> |
> | > If your Lisp implementation does full tail-call optimization,
> | > then you can modify #3 so that each state calls the next
> | > directly (without the external driver you evidently have).
> |
> | Doesn't CL require this?
>
> No, among other reasons because it makes debugging harder. Search for
> old messages on this newsgroup for details. Kent Pitman, in
> particular, has written at length on this topic.
>
So what does the CL spec say on it, specifically? Is it implementation
dependent? Suggested? Encouraged?
What do most implementations do?
-- Dave
Erik Naggum
| What may help me is to sort of describe a simplistic implementation of
| this in C terms, so I can make the translation.
Do you want to become good at translating between the mind-sets of
different languages or do you want to write programs in Common Lisp?