Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

State machine representation

1,147 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