State machine representation

989 views
Skip to first unread message

Dave Roberts

unread,
Feb 1, 2004, 1:53:38 AM2/1/04
to
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.

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

unread,
Feb 1, 2004, 4:07:01 AM2/1/04
to

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

unread,
Feb 1, 2004, 6:04:52 AM2/1/04
to
Dave Roberts wrote:

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

<http://ll1.ai.mit.edu/>

--
Jens Axel Søgaard

Matthew Danish

unread,
Feb 1, 2004, 6:52:11 AM2/1/04
to
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.
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

unread,
Feb 1, 2004, 6:58:15 AM2/1/04
to
Dave Roberts <ld...@re-move.droberts.com> writes:

> 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

unread,
Feb 1, 2004, 7:38:41 AM2/1/04
to
Dave Roberts <ld...@re-move.droberts.com> writes:

> 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

unread,
Feb 1, 2004, 9:09:32 AM2/1/04
to

Kenny Tilton

unread,
Feb 1, 2004, 12:18:38 PM2/1/04
to

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

unread,
Feb 1, 2004, 12:46:40 PM2/1/04
to
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).

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

unread,
Feb 1, 2004, 1:08:42 PM2/1/04
to
Paolo Amoroso wrote:

> 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

unread,
Feb 1, 2004, 1:23:52 PM2/1/04
to
Gareth McCaughan wrote:

> 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

unread,
Feb 1, 2004, 1:36:37 PM2/1/04
to
Paul Tarvydas wrote:

> 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

unread,
Feb 1, 2004, 1:39:25 PM2/1/04
to
Jens Axel Søgaard wrote:

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

unread,
Feb 1, 2004, 1:44:19 PM2/1/04
to
Kenny Tilton wrote:

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

unread,
Feb 1, 2004, 1:48:43 PM2/1/04
to
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.

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

unread,
Feb 1, 2004, 2:14:57 PM2/1/04
to

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

unread,
Feb 1, 2004, 2:37:17 PM2/1/04
to
Matthew Danish wrote:

> 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

unread,
Feb 1, 2004, 2:42:28 PM2/1/04
to
* 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?

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

unread,
Feb 1, 2004, 3:18:53 PM2/1/04
to
In article <fSbTb.156975$sv6.865734@attbi_s52>, Dave Roberts
<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

unread,
Feb 1, 2004, 3:58:44 PM2/1/04
to
Erik Naggum wrote:

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

unread,
Feb 1, 2004, 4:10:09 PM2/1/04
to
>>>>> "DR" == Dave Roberts <ld...@re-move.droberts.com> writes:
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

unread,
Feb 1, 2004, 4:16:15 PM2/1/04
to
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.

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

unread,
Feb 1, 2004, 4:26:09 PM2/1/04
to
Matthew Danish wrote:

> 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

unread,
Feb 1, 2004, 4:38:35 PM2/1/04
to
Erann Gat wrote:

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

unread,
Feb 1, 2004, 4:24:24 PM2/1/04
to
+ 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.

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

unread,
Feb 1, 2004, 4:46:39 PM2/1/04
to
+ Dave Roberts <ld...@re-move.droberts.com>:

| 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

unread,
Feb 1, 2004, 4:53:15 PM2/1/04
to
* Dave Roberts

| 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

unread,
Feb 1, 2004, 4:54:46 PM2/1/04
to
Matthew Danish wrote:

> 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

unread,
Feb 1, 2004, 4:56:30 PM2/1/04
to
Bulent Murtezaoglu wrote:

> 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

unread,
Feb 1, 2004, 4:58:35 PM2/1/04
to
Harald Hanche-Olsen wrote:

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

unread,
Feb 1, 2004, 5:00:16 PM2/1/04
to
* Dave Roberts

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

Matthew Danish

unread,
Feb 1, 2004, 5:13:28 PM2/1/04
to
On Sun, Feb 01, 2004 at 09:54:46PM +0000, Dave Roberts wrote:
> > 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?

No; it is creating a new variable which is /named by/ the symbol A. The
variable is bound to the function. The symbol A is an entirely separate
object in its own right, and in this context it is only being used to
name the variable. Remember, Lisp programs are syntactically described
by Lisp data such as lists and symbols, etc.

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

It is two different variables. However, there is a confusing part:
symbols really do have SYMBOL-VALUE and SYMBOL-FUNCTION accessors. But
these have nothing to do with lexical variables (they are relevant to
special variables).


P.S. It is better not to think in C terms w/regard to this.

Dave Roberts

unread,
Feb 1, 2004, 5:22:57 PM2/1/04
to
Erik Naggum wrote:

> * Dave Roberts
> | 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.

No, not at all. Indeed, if this was true, I would not have progressed
through BASIC -> Assembly Language -> Pascal -> Forth -> C -> Fortran ->
bit of CL -> bit of Scheme -> C++ -> Java -> CL.

Comparisons between things are one way we check whether we understand
something. Rote learning is certainly possible, but I find it terribly
difficult. I do far better when I understand the "why" behind something,
even if it's just "no reason, that's just the way we did it." Further, I
think this is well supported by lots of research into memorization. The
more "hooks" you have between things you already know and the material you
are learning, the better you are able to retain the new information.
Without these hooks, your alternative is to simply keep repeating the
material until it eventually sets in. This can be quite a long process,
however.

Note that I'm not saying, "X is correct because I learned it first." It's
just natural to say, "Hmmm... Y does this differently than X, and X seems
cleaner, not because I learned it first, but just because it seems
cleaner." Without background as to why things are done the way they are, it
actually presents a barrier to learning. I would note that others were very
quick to suggest many other references that explain the issue to me, while
you seem to be suggesting that I'm wrong to even ask the question.

As a check, is that what you're really trying to tell me?

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

I think that is foolish. Certainly Lisp compares itself all the time with
other languages. Indeed, one reason that I'm learning Lisp is after reading
through some of Paul Graham's claims that Lisp is a "better" language than
others. Certainly, I should be allowed to weigh the evidence of such claims
by comparisons to other languages, right?

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

Fair enough, and I actually agree with some of that. The learning process
natually causes comparisons, however. I figured CL was "tough enough" to
handle a newbie asking questions, however. My goal is not to "speak CL with
a Scheme accent." My goal is to become proficient at CL (indeed, that was
what caused me to post my initial question about how to represent state
machines). The fact that Scheme is another lisp dialect that is somewhat
related in some of its ideas naturally causes one to see differences and
ask questions, however.

> Otherwise, I may want to compare you to all the other people who have
> never learned Common Lisp because they were stuck in Compareville.

Hmmm... Not sure what to say here. I'm making an honest effort to try to
learn and understand. If you don't or can't respect that, I suppose that's
your choice. I hope that others populating this group will be kind enough
to help me and not take the same attitude. Indeed, many have already been
so in precisely this thread.

-- Dave

Dave Roberts

unread,
Feb 1, 2004, 5:25:38 PM2/1/04
to
Harald Hanche-Olsen wrote:

> + Dave Roberts <ld...@re-move.droberts.com>:
>
> | 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.)

Yes, people have sent me the reference, which I appreciate, BTW. My goal
wasn't to inflame here, but it seems I have really stepped on some toes...
;-)

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

Yes, fair enough. Hence my questions about this. One very valid answer, as
I'm now finding out, is simply, "Dave, you're a clueless newbie. Here's why
we did it this way and it's actually better than the alternative: ..."

I think the Gabriel & Pitman paper probably goes into it all, but I'm still
answering posts here and haven't read more than the first couple of
paragraphs yet. ;-)

-- Dave

Erik Naggum

unread,
Feb 1, 2004, 5:37:32 PM2/1/04
to
* Erik Naggum

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

* Dave Roberts


| I think that is foolish.

OK. Goodbye, then.

Dave Roberts

unread,
Feb 1, 2004, 5:39:16 PM2/1/04
to
Matthew Danish wrote:

> On Sun, Feb 01, 2004 at 09:54:46PM +0000, Dave Roberts wrote:
>> > 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?
>
> No; it is creating a new variable which is /named by/ the symbol A. The
> variable is bound to the function. The symbol A is an entirely separate
> object in its own right, and in this context it is only being used to
> name the variable. Remember, Lisp programs are syntactically described
> by Lisp data such as lists and symbols, etc.

Okay, I think I'm getting there. Maybe an implementation example to clarify
a bit:

So a simplistic implementation of a variable might be:
struct variable {
lisp_object * value;
symbol * symbol;
}

Is that sort of right? So a symbol really is an atomic object (yea, I know,
that's probably when they call them atoms... ;-). The key point is, rather
than a symbol refering to a value, it's really that a variable refers to
both a value as well as the name of the variable, right?

So what's a binding versus variable? What I had previously in my head was
that a binding was sort of like what I just wrote above as a structure for
variable.

So if that's right, then additional quesitons are:

1. How does the system map between symbols and variables? Seems like it
would be inefficient to search through a set of variables to find one with
the same symbol name, rather than starting at the symbol name and following
pointers to the value.

2. How are function and value variables different?

>> 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.
>
> It is two different variables. However, there is a confusing part:
> symbols really do have SYMBOL-VALUE and SYMBOL-FUNCTION accessors. But
> these have nothing to do with lexical variables (they are relevant to
> special variables).
>
>
> P.S. It is better not to think in C terms w/regard to this.

I'm not really trying to think in terms of C, but really the implementation.
Put another way, I'm a hardware guy and I think in terms of bytes and
pointers and such. If you want to give an assembly-language definition,
that would help. I'm not going for a language comparison here with C, just
trying to understand the implementation, and C is an easy language to
describe that implementation (where C = "high level assembly language").

-- Dave


Joe Marshall

unread,
Feb 1, 2004, 5:39:55 PM2/1/04
to
Dave Roberts <ld...@re-move.droberts.com> writes:

> What may help me is to sort of describe a simplistic implementation
> of this in C terms, so I can make the translation.


First a bit of terminology.

A Lisp identifier can refer to a function or a variable (among other
things). The first identifier in a form refers to a function,
subsequent identifiers refer to variables unless some provision is
made. So in the expression

(foo bar baz)

FOO refers to a function, BAR and BAZ refer to variables.

The FUNCALL function takes its first argument and invokes it on the
remaining arguments. So in the form

(funcall foo bar baz)

FOO refers to a variable that will be invoked as a function upon BAR
and BAZ.

The FUNCTION form when used on an identifiers indicates that you wish
to refer to the function, not the variable. So in the form

(foo (function bar) baz)

FOO and BAR refer to functions (FOO will be invoked, BAR is just an
argument), baz will refer to a variable.


A variable reference reference may be `free', `bound', or `special'.
A function reference may be `free' or `bound'. In this expression:

(let ((x 22))
(foo x y))

FOO is a free function reference, X is a bound variable, and Y is a
free variable. In this expression:

(flet ((foo (a b) (+ a b)))
(foo 3 4))

FOO is a bound function.


Ok, so here are the rules:

Use FLET, LABELS, and MACROLET to bind functions.

Use LET, LAMBDA, and several other macros, to bind variables.

Free references to functions will use the value found in the function
cell of the appropriate symbol.

References to special variables will use the value found in the value
cell of the appropriate symbol.

Free references to variables will use the value found in the value
cell, but if that is what you want to do, you should declare the
variable special.

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

The variable A is being bound to a function object.

Thus the reference to A in the second line refers to that function.
FUNCALL invokes this function on the number 1.

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

No, the symbol `A' does not get involved here.

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

For binding, there are two different variables, one in each namespace,
both with the same name. Although variables can hold function
objects, there is no syntax by which you could put a non-function
object into a function binding.

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

A symbol does have these, but it is generally not involved when
binding values or functions.


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

Symbols aren't involved.

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

That's basically what happens.

--
~jrm

Joe Marshall

unread,
Feb 1, 2004, 5:41:14 PM2/1/04
to
Dave Roberts <ld...@re-move.droberts.com> writes:

>
> Doesn't CL require [full tail recursion optimization]?
>

No, but most implementations have a means by which you can enable it.


--
~jrm

Kenny Tilton

unread,
Feb 1, 2004, 5:38:48 PM2/1/04
to

Dave Roberts wrote:
> Yes, people have sent me the reference, which I appreciate, BTW. My goal
> wasn't to inflame here, but it seems I have really stepped on some toes...
> ;-)

It is pretty funny how you have managed to set off just about every land
mine in the joint in your first few questions. If you dig into Google
and read every thread we have seen on namespaces and tail recursion and
CL vs Scheme, when you finish in six months you will understand that...
well, you are lucky to be alive at this point.

:)

kenny

--
http://tilton-technology.com

Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film

Your Project Here! http://alu.cliki.net/Industry%20Application

Harald Hanche-Olsen

unread,
Feb 1, 2004, 5:33:24 PM2/1/04
to
+ Dave Roberts <ld...@re-move.droberts.com>:

| Matthew Danish wrote:
|
| > (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,"

No, actually the reader creates the symbol. The program is defined
not in terms of the text, but in terms of the data structures (conses,
symbols, and a number in this case) which results from the above
textual representation being read.

| and then binding the value portion(?) of that symbol to the lamba
| expression object.

The LET creates a new lexical variable. The name of that variable is
the symbol A, but no "value portion" of the symbol is affected by the
binding, unless the variable has been declared special (and even then,
the true story is a bit more complicated). In fact, the compiler will
allocate a location for the variable and make sure all accesses to A
within the scope refer to that location. There is no further
connection between the symbol and the value, except that the debugger
is informed so it can help you inspect the variable.

| Is that right? So what's a variable as opposed to a symbol/binding?

A variable in CL /is/ a binding. More precisely, it is a binding in a
particular name space, the "variable" one. A symbol is something
whose primary attribute is its identity. It is the thing being
bound.

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

A bit like the latter, but the references aren't really part of the
symbol at all. You may think of the name spaces as the abstract
objects that bind symbols to values.

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

No! The global value and function bindings may be part of the symbol
object, and though this is not a requirement, it probably doesn't hurt
to think of them that way. But lexical bindings are totally divorced
from their names at runtime, with the exception of information
available to the debugger, as I mentioned before.

| > (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.

Good observation. That is why they are not implemented that way.

Dave Roberts

unread,
Feb 1, 2004, 5:44:34 PM2/1/04
to
Erik Naggum wrote:

> * Dave Roberts
> | 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?
>

I think you're reading in here, per your other posting about avoiding
comparisons, to something I'm not trying to do. I'm specifically not asking
for how this compares to C in terms of language. I'm really asking how this
is implemented, simply with C as the syntax of choice for that presentation
since it's easy to understand. If you want to describe it in assembly
language, I'm fine with that, too.

Put another way, I'm really trying to ask, "What are 'bindings,'
'variables,' 'symbols,' etc., in terms of machine words, pointers, and byte
groupings representing objects?" If I can understand that, even if it's
just a naive implementation, that helps me understand the other terminology
better. Sorry, I'm carrying baggage from being a hardware engineer here.
Abstraction and abstract ideas are nice, but I find that my own personal
learning style is that I can't make them stick unless I anchor them to the
bits and bytes that really underly them. Once I have that, I find that I
can work very naturally and easily in the abstract system.

-- Dave

Thomas F. Burdick

unread,
Feb 1, 2004, 5:45:55 PM2/1/04
to
Dave Roberts <ld...@re-move.droberts.com> writes:

Most implementations support *some* sort of tail call elimination, but
it might be as simple as only self-calls. You can find out about your
particular implementation, but unless you plan on completely tying
your program to an implementation, you shouldn't count on it. A
better way is to abstract away the state-changing machinery with a
CHANGE-STATE macro, or something. You can have it expand to a
funcall, or to something like (throw 'main-loop 'next-state). If
you're talking about having big state machines, powering the whole app
(as opposed to little, one-off parsers or something), you definately
want to hide the mechanism behind nice high-level declarative macros.

For little one-off machines, I just use go-to. Specifically PROG,
which sets up some lexical variables, and gives you an implicit
TAGBODY. Using a loop with tests on a condition variable isn't any
clearer IMO, so I might as well lose the if-then-else ladder that
amounts to interpreting a TAGBODY.

--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'

Thomas F. Burdick

unread,
Feb 1, 2004, 5:50:45 PM2/1/04
to
Kenny Tilton <kti...@nyc.rr.com> writes:

> Dave Roberts wrote:
> > Yes, people have sent me the reference, which I appreciate, BTW. My goal
> > wasn't to inflame here, but it seems I have really stepped on some toes...
> > ;-)
>
> It is pretty funny how you have managed to set off just about every land
> mine in the joint in your first few questions. If you dig into Google
> and read every thread we have seen on namespaces and tail recursion and
> CL vs Scheme, when you finish in six months you will understand that...
> well, you are lucky to be alive at this point.
>
> :)

To head off the next one: continuations are a bad idea in an
industrial strength language like CL. They're not missing, their lack
is a feature. ;-)

Harald Hanche-Olsen

unread,
Feb 1, 2004, 5:47:42 PM2/1/04
to
+ Dave Roberts <ld...@re-move.droberts.com>:

| So what does the CL spec say on it [tail call optimization],


| specifically? Is it implementation dependent? Suggested? Encouraged?

Nothing much, apparently. You can get the spec for free, you know:
The Common Lisp HyperSpec, available from Xanalys' website or some
such place. Google for it. Then you don't have to ask what the spec
says, but can move on to the next level: "Where in the HyperSpec does
it talk about it?"

Dave Roberts

unread,
Feb 1, 2004, 5:57:31 PM2/1/04
to
Harald Hanche-Olsen wrote:

> + Dave Roberts <ld...@re-move.droberts.com>:
>
> | So what does the CL spec say on it [tail call optimization],
> | specifically? Is it implementation dependent? Suggested? Encouraged?
>
> Nothing much, apparently. You can get the spec for free, you know:
> The Common Lisp HyperSpec, available from Xanalys' website or some
> such place. Google for it. Then you don't have to ask what the spec
> says, but can move on to the next level: "Where in the HyperSpec does
> it talk about it?"
>

Right, exactly. I already have the spec. The hard part is now finding things
in it. For a function, that's easy. The index is good. I wasn't sure where
I'd dig this up, however, which is why I asked. Thanks for your help.

-- Dave

Harald Hanche-Olsen

unread,
Feb 1, 2004, 6:03:05 PM2/1/04
to
+ Dave Roberts <ld...@re-move.droberts.com>:

| I'm not really trying to think in terms of C, but really the
| implementation.

I think that is a mistake. CL provides a set of abstractions that are
best understood precisely as abstractions. If you get too involved in
how these abstractions are implemented, I think you will lose the very
essence of the language. I think this is what Erik was hinting at
when he suggested elsewhere that you should not compare CL with other
languages. If you try to think of one language in another language's
terms, you lose. "Real programmers write Fortran in any language."

(Boy, I have posted more responses to you than I usually post to this
newsgroup in a month. I'm really a lurker here. But now it really is
bedtime on my side of the globe, so it's time for me to fade back into
obscurity.)

Dave Roberts

unread,
Feb 1, 2004, 6:03:38 PM2/1/04
to
Thomas F. Burdick wrote:

> Most implementations support *some* sort of tail call elimination, but
> it might be as simple as only self-calls. You can find out about your
> particular implementation, but unless you plan on completely tying
> your program to an implementation, you shouldn't count on it. A
> better way is to abstract away the state-changing machinery with a
> CHANGE-STATE macro, or something. You can have it expand to a
> funcall, or to something like (throw 'main-loop 'next-state). If
> you're talking about having big state machines, powering the whole app
> (as opposed to little, one-off parsers or something), you definately
> want to hide the mechanism behind nice high-level declarative macros.

Yes, agreed. In fact, that's step 2 of my plan. First, I want to understand
the form those macros will expand to. Then I'm going to write the macros.
The whole thing is a large exercise to force me through the learning
process for a language this sophisticated.

> For little one-off machines, I just use go-to. Specifically PROG,
> which sets up some lexical variables, and gives you an implicit
> TAGBODY. Using a loop with tests on a condition variable isn't any
> clearer IMO, so I might as well lose the if-then-else ladder that
> amounts to interpreting a TAGBODY.

Right. For something that can consume a whole thread and whip through the
machine to completion, this style would seem to both be efficient and work
well. The trouble I'm going to have is that my machines are going to be
protocol-level entities, so I need something that won't block in the
machine to get more input. The machine really has to transition to the next
state, then exit so we can go back and do some non-blocking I/O to get the
next batch of input, then enter the machine again and drive it forward one
or more states. Part of the reason this is so is because you could have
multiple such state machines operating simultaneously, each handling a
differnet protocol conenction. The TAGBODY/GO approach seems very nice for
things like lexers, parsers, etc., that can run to completion and then
terminate.

-- Dave

Dave Roberts

unread,
Feb 1, 2004, 6:04:53 PM2/1/04
to
Kenny Tilton wrote:

>
>
> Dave Roberts wrote:
>> Yes, people have sent me the reference, which I appreciate, BTW. My goal
>> wasn't to inflame here, but it seems I have really stepped on some
>> toes... ;-)
>
> It is pretty funny how you have managed to set off just about every land
> mine in the joint in your first few questions. If you dig into Google
> and read every thread we have seen on namespaces and tail recursion and
> CL vs Scheme, when you finish in six months you will understand that...
> well, you are lucky to be alive at this point.
>
> :)
>
> kenny
>

Indeed. So it seems. ;-)

Well, I never was bashful...

Again, thanks to those who have been patient with me. I appreciate your
experience and wisdom.

-- Dave

Dave Roberts

unread,
Feb 1, 2004, 6:07:28 PM2/1/04
to
Thomas F. Burdick wrote:

> Kenny Tilton <kti...@nyc.rr.com> writes:
>
>> Dave Roberts wrote:
>> > Yes, people have sent me the reference, which I appreciate, BTW. My
>> > goal wasn't to inflame here, but it seems I have really stepped on some
>> > toes... ;-)
>>
>> It is pretty funny how you have managed to set off just about every land
>> mine in the joint in your first few questions. If you dig into Google
>> and read every thread we have seen on namespaces and tail recursion and
>> CL vs Scheme, when you finish in six months you will understand that...
>> well, you are lucky to be alive at this point.
>>
>> :)
>
> To head off the next one: continuations are a bad idea in an
> industrial strength language like CL. They're not missing, their lack
> is a feature. ;-)
>

Whew! Glad you said that... ;-)

Seriously, I actually have never understood continuations that well. They
always sort of make my head hurt. Even when they do come into focus every
now and then, they seem very inefficient. It would appear that a good Lisp
with threads would be far better. Yes, you may not be able to do some of
the fancy things that continuations allow, but they handle all the standard
cases pretty well, thank you.

Anyway, I won't ask that question. Anything else I should steer clear of?

-- Dave

Dave Roberts

unread,
Feb 1, 2004, 6:24:33 PM2/1/04
to
Joe Marshall wrote:

<a lot of good stuff...>


So the conclusion that I'm finally coming to is that I don't understand the
difference between a symbol and a variable. I had though previously that
they were basically the same thing.

So I had thought:

(setq foo 10)

and

(let ((foo 10))
...)

were basically creating the same sort of binding object, just that one was
at top-level and the other was local to the LET form. Your description of
all this leads me to believe that this is incorrect and there is something
fundamentally different about top-level vs. lexical bindings.

Now, there doesn't seem to be anything different between these
syntactically. I could just as easily write (+ foo 10), either at top-level
or in the LET scope. That suggests to me that they are the same in terms of
the implementation, but they just differ in scope.

For instance, say I'm in the LET form, I'm imagining the interpreter going
along, finding a reference to foo in (+ foo 10), and then searching for the
binding. It basically says, "Okay, I have this symbol in this list
representing the code of this function. Let's go find the binding for foo."
So it goes to the closest enclosing environment, in this case the one set
up by LET. It finds a binding there where the symbol foo is referenced, and
uses the value. Had it not found that binding there, it would have
progressed to the next greater environment, top-level. In that case, it
would have found a binding of foo there, set the SETQ form.

Is that right?

I'm reading the Gabriel/Pitman article and I got as far as the Notation and
Terminology section where they try to describe all this and I'm stopped,
rereading and rereading.

Specifically, I'm really struggling with the difference between symbol,
variable, binding, and lexical variable. I understand what an identifier
is.

-- Dave

Pascal Costanza

unread,
Feb 1, 2004, 6:28:04 PM2/1/04
to

Dave Roberts wrote:

> So, in summary, I apologize for stepping in somebody's oatmeal. I'm just
> working through probably all the standard newbie issues.

I have also been through this before not so long ago. You might want to
take a look at http://www.pascalcostanza.de/lisp/guide.html for a report
on what I have learned.

Another suggestion: Before getting into arguments with some regulars
here about off topic issues you might want to google for previous
discussions and flame wars to see whether it's worth your time.


Pascal

--
Tyler: "How's that working out for you?"
Jack: "Great."
Tyler: "Keep it up, then."

Pascal Costanza

unread,
Feb 1, 2004, 6:32:19 PM2/1/04
to

Dave Roberts wrote:

> Specifically, I'm really struggling with the difference between symbol,
> variable, binding, and lexical variable. I understand what an identifier
> is.

You may find http://www.flownet.com/gat/specials.pdf helpful.

David Golden

unread,
Feb 1, 2004, 7:03:56 PM2/1/04
to
Downloading or otherwise finding a copy of "Common Lisp: A Gentle
Introduction to Symbolic Computation" by David S. Touretzky might help you
learn lisp. http://www-2.cs.cmu.edu/~dst/LispBook/index.html

It may seem "too gentle" for the first few chapters, but it might be good to
read it without trying to compare lisp to other stuff.
Lisp is lisp, it's not the other stuff.

It won't break things down into "hardware primitives" exactly, but
does break things down into lisp primitives in a manner that comes
vaguely close. Oh, and Chapter 14, about basic lisp macros, uses a finite
state machine "little language" (lisp is a language for writing languages)
as a worked example.

Note that lisp *once* mapped fairly reasonably to certain hardware
primitives on certain hardware (it's where the funny names "car" and "cdr"
come from, for example), but nowadays, it's much better to think of it more
abstractly, particularly since back in those days, lisp really was "LISt
Processing" and not much else - now there's a whole load of other data
types that may or may not be built from lists in a particular
implementation.

It's kinda just *not* that lisp is "built up" from hardware primitives, but
rather lisp "is", and the hardware representation is an implementation
detail that the compiler handles for you. Lisp could be on a trinary
content-addressable-memory computer, and it would still be lisp.

Dave Roberts

unread,
Feb 1, 2004, 7:11:28 PM2/1/04
to
Harald Hanche-Olsen wrote:

> The LET creates a new lexical variable. The name of that variable is
> the symbol A, but no "value portion" of the symbol is affected by the
> binding, unless the variable has been declared special (and even then,
> the true story is a bit more complicated). In fact, the compiler will
> allocate a location for the variable and make sure all accesses to A
> within the scope refer to that location. There is no further
> connection between the symbol and the value, except that the debugger
> is informed so it can help you inspect the variable.

Okay, I think I get that. The issue that is now causing me trouble is the
different handlig of top-level versus lexical scopes. Can you give me
something on the different handling of a name (say "foo") when it is in a
lexical scope versus top-level.

>
> | Is that right? So what's a variable as opposed to a symbol/binding?
>
> A variable in CL /is/ a binding. More precisely, it is a binding in a
> particular name space, the "variable" one. A symbol is something
> whose primary attribute is its identity. It is the thing being
> bound.

Okay, so that makes sense now, I think.



> | 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.
>
> A bit like the latter, but the references aren't really part of the
> symbol at all. You may think of the name spaces as the abstract
> objects that bind symbols to values.

So now I'm getting confused again.

> | 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.
>
> No! The global value and function bindings may be part of the symbol
> object, and though this is not a requirement, it probably doesn't hurt
> to think of them that way. But lexical bindings are totally divorced
> from their names at runtime, with the exception of information
> available to the debugger, as I mentioned before.

Actually, I think it is hurting me to think of them that way. It sounds like
the programming model is that symbols are just interned strings. That's it.
Just a string of characters, with each one guaranteed to be unique such
that you can use a pointer to it rather than repeat the characters
everywhere. Then it sounds like there are two namespaces in the system, one
for values and the other for functions. These spaces seem logically
separate (two totally different sets of bindings). Then it seems like an
environment stores a set of bindings for values, and a set of bindings for
functions, again totally separate.

Now, the thing that I'm still struggling with is that it seems like symbols
are not simple interned strings in at least some of the literature I have
read. For instance, the Gabriel/Pitman article that I'm reading says in its
terminology definitions: "A symbol is a Lisp data structure that has a
value cell, a property list, a function cell (in Common Lisp), and so on."

> | > (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.
>
> Good observation. That is why they are not implemented that way.

Okay, so now I'm struggling with the Gabriel/Pitman quote above.

-- Dave

Gareth McCaughan

unread,
Feb 1, 2004, 8:14:15 PM2/1/04
to
Dave Roberts wrote:

> Gareth McCaughan wrote:
>
> > 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?

Right.

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

No, CL doesn't. Some implementations may do it, but I'm
not sure that any implementation *guarantees* to do it.
I don't actually know of any language with such a requirement
(either as standard or for all implementations) other than
Scheme, though it wouldn't surprise me to learn that there
are others.

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

The *compiler* may have to do a linear search, but I'd be
astonished if the compiled code had anything of the kind
left in it. Each GO will probably end up as a single jump
instruction.

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

Yes, it is likely to be faster than using EQL specializers
in CLOS.

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

CLOS is amazing. Your plan is a reasonable one.

--
Gareth McCaughan
.sig under construc

Dave Roberts

unread,
Feb 1, 2004, 8:26:14 PM2/1/04
to
Pascal Costanza wrote:

>
> Dave Roberts wrote:
>
>> So, in summary, I apologize for stepping in somebody's oatmeal. I'm just
>> working through probably all the standard newbie issues.
>
> I have also been through this before not so long ago. You might want to
> take a look at http://www.pascalcostanza.de/lisp/guide.html for a report
> on what I have learned.
>
> Another suggestion: Before getting into arguments with some regulars
> here about off topic issues you might want to google for previous
> discussions and flame wars to see whether it's worth your time.

Actually, Pascal, I did that a few weeks ago. In fact, it was one of the
documents that convinced me to spend the time to learn CL. ;-)

Thanks for putting it together. A very good overview of the language, its
benefits, and pointers to other documentation.

-- Dave

Dave Roberts

unread,
Feb 1, 2004, 8:28:30 PM2/1/04
to
Pascal Costanza wrote:

>
> Dave Roberts wrote:
>
>> Specifically, I'm really struggling with the difference between symbol,
>> variable, binding, and lexical variable. I understand what an identifier
>> is.
>
> You may find http://www.flownet.com/gat/specials.pdf helpful.

Thanks. This looks helpful. I like the title. It's just how I'm feeling
right about now... ;-)

-- Dave

Dave Roberts

unread,
Feb 1, 2004, 8:33:42 PM2/1/04
to
Harald Hanche-Olsen wrote:

> + Dave Roberts <ld...@re-move.droberts.com>:
>
> | I'm not really trying to think in terms of C, but really the
> | implementation.
>
> I think that is a mistake. CL provides a set of abstractions that are
> best understood precisely as abstractions. If you get too involved in
> how these abstractions are implemented, I think you will lose the very
> essence of the language. I think this is what Erik was hinting at
> when he suggested elsewhere that you should not compare CL with other
> languages. If you try to think of one language in another language's
> terms, you lose. "Real programmers write Fortran in any language."

Hmmm... I typically find this works out better for me. Again, I'm not
looking for specifically a C comparison versus CL, just a naive description
of how this *might* be implemented. That probably isn't descriptive of how
an efficient implementation works; that's fine, I just need to get hold of
the mental model for this. Again, if somebody feels it's easier to describe
the naive implementation in CL syntax, rather than C or something, I'm fine
with that. I just don't understand enough CL right now, being a newbie, so
I'm trying to cast the description in something I know better. But if CL
works better, that's fine.

Even if you just want to say: A symbol is basically a structure that
holds... blah, blah, blah, that would help.

> (Boy, I have posted more responses to you than I usually post to this
> newsgroup in a month. I'm really a lurker here. But now it really is
> bedtime on my side of the globe, so it's time for me to fade back into
> obscurity.)
>

Go to sleep. Thanks for the help. I appreciate it. ;-)

-- Dave

Dave Roberts

unread,
Feb 1, 2004, 8:39:54 PM2/1/04