I don't understand LISP macro well but happen to do bash programming
often.
Given some parameters, I can use ``eval'' to create functions on the fly.
Are there some similarities between the two, in concept? What are the
major differences?
Thank you.
Wei
Weiguang Shi wrote:
> I don't understand LISP macro well but happen to do bash programming
> often.
>
> Given some parameters, I can use ``eval'' to create functions on the fly.
>
> Are there some similarities between the two, in concept? What are the
> major differences?
Lisp has an EVAL function, so you should compare that instead.
Macros are a way of scripting the compiler: essentially, the abstract
syntax tree is passed through custom transformation functions which are
matched to the syntax tree nodes according to the operator symbol.
The most fundamental difference between Lisp eval and shell eval is
that the shell eval works with a string which is tokenized from
scratch. The input to Lisp eval is a data structure representing code.
Therefore, the Lisp eval is probably far more efficient as well as
robust (doesn't suffer from silly whitespace and quoting problems).
That is to say, when you insert variable pieces into a shell string
that is going to be put through eval, you have to be careful. The
interpolated pieces could expand to the wrong tokens, or syntax which
is interpreted the wrong way. E.g.
x=\$
y=ls
eval ${x}y # expands to $y, which expands to ls.
< file listing>
x=\"
y=ls
eval ${x}y
-bash: unexpected EOF while looking for matching `"'
-bash: syntax error: unexpected end of file
This blows up because ${x} expands to the " character, and so ${x}y
expands to "ls, which is re-tokenized from scratch.
There is no way for this type of error to happen in Lisp eval. To
create a read syntax error, you would have to pass the string to the
reader, e.g.
[5]> (read-from-string "\"unmatched")
*** - READ: input stream #<INPUT STRING-INPUT-STREAM> ends within a
string
As you can see, the layers are separated. You can use the reader
without involving the evaluator, or evaluate data as code that was
produced without involving the reader.
Weiguang Shi <·····@nestow.cs.ualberta.ca> writes:
> I don't understand LISP macro well but happen to do bash programming
> often.
>
> Given some parameters, I can use ``eval'' to create functions on the fly.
>
> Are there some similarities between the two, in concept? What are the
> major differences?
Indeed there are some similarities.
Macros are functions used to generate code.
$ m () {
local name=$1
local op=$2
eval "$name () {
expr \$1 '$op' \$2
}"
}
$ m add \+
$ m mul \*
$ add 1 2
3
$ mul 2 3
6
$
CL-USER> (defmacro m (name op)
`(defun ,name (a b) (,op a b)))
M
CL-USER> (m add +)
ADD
CL-USER> (m mul *)
MUL
CL-USER> (add 1 2)
3
CL-USER> (mul 2 3)
6
CL-USER>
There is an "eval" hidden behind each macro.
We could write it as a function if we wanted to be more similar to
what happens in bash:
(defun m (name op) ; don't do that in lisp!
(eval `(defun ,name (a b) (,op a b)))) ; use a macro rather!
but we'd have to call it quoting the arguments:
(m 'add '+)
(like we have to do in bash: m mul \*
--
__Pascal Bourguignon__
Weiguang Shi <·····@nestow.cs.ualberta.ca> writes:
> Thank you! I could only suspect.
>
> So although I don't understand LISP macros, I can still grok it.
Off-topic note: The verb "to grok" comes from Heinlein's fascinating
novel _A Stranger in a Strange Land_, and roughly means to have such
an intimate understanding of as to be nearly one with it. If you
don't understand something, you cannot grok it.
But back to the topic itself, macros can't be fairly analogized to any
other language that I know of, because they allow you to add syntactic
features to the language. I try explaining this by implementing a
'for' loop in Common Lisp using a macro. Common Lisp does not have
such a feature, so adding it with a macro is a substantial change to
the syntax of the language.
In C, you write:
for (i = 0; i < 10; i++) {
printf("i = %d\n", i);
}
In Lisp, this would look like:
(for (i 0) (< i 10) (incf i)
(format t "i = ~D~%" i))
If you type that into your Lisp, you will get an error or two. Those
errors will include the fact that there's no such function I and the
fact that there's no such function FOR.
Let's add it to the language:
(defmacro for (init continue next &body body)
(unless (consp init)
(error "Syntax error - init form must be a list"))
(let ((looplabel (gensym))
(var (first init))
(initval (second init)))
(unless (symbolp var)
(error "Syntax error - variable must be a symbol"))
`(prog ((,var ,initval))
,looplabel
,@body
,next
(when ,continue
(go ,looplabel)))))
Now try that example form again, and it will print out what you'd
expect. Lisp did not have this syntax beforehand and it does now.
You can't do that in bash. Just because macros can do one thing that
you can do with eval in bash doesn't mean that eval in bash can do
other things that macros can. The same applies to most of the "ooh,
macros are for *this*!" revelations that people have early on. I
started out thinking that they were just for writing functions that
didn't evaluate their arguments until they were ready to. And they
can, indeed, do just that. My point is this: don't limit your
understanding of macros to the first thing you find that they can do.
In article <··············@hermes.theari.com>, Ari Johnson wrote:
> Weiguang Shi <·····@nestow.cs.ualberta.ca> writes:
>
>> Thank you! I could only suspect.
>>
>> So although I don't understand LISP macros, I can still grok it.
>
> Off-topic note: The verb "to grok" comes from Heinlein's fascinating
> novel _A Stranger in a Strange Land_, and roughly means to have such
> an intimate understanding of as to be nearly one with it. If you
> don't understand something, you cannot grok it.
I understand what the word means. I meant it and don't think that's
impossible. But that's off-topic.
>
> But back to the topic itself, macros can't be fairly analogized to any
> other language that I know of, because they allow you to add syntactic
> features to the language. I try explaining this by implementing a
> 'for' loop in Common Lisp using a macro. Common Lisp does not have
> such a feature, so adding it with a macro is a substantial change to
> the syntax of the language.
>
> In C, you write:
> for (i = 0; i < 10; i++) {
> printf("i = %d\n", i);
> }
>
> In Lisp, this would look like:
> (for (i 0) (< i 10) (incf i)
> (format t "i = ~D~%" i))
>
> If you type that into your Lisp, you will get an error or two. Those
> errors will include the fact that there's no such function I and the
> fact that there's no such function FOR.
>
> Let's add it to the language:
>
> (defmacro for (init continue next &body body)
> (unless (consp init)
> (error "Syntax error - init form must be a list"))
> (let ((looplabel (gensym))
> (var (first init))
> (initval (second init)))
> (unless (symbolp var)
> (error "Syntax error - variable must be a symbol"))
> `(prog ((,var ,initval))
> ,looplabel
> ,@body
> ,next
> (when ,continue
> (go ,looplabel)))))
>
> Now try that example form again, and it will print out what you'd
> expect. Lisp did not have this syntax beforehand and it does now.
> You can't do that in bash.
One can certainly create a function with a name and parameter
sequence, call it ``new'' syntax, and inside the function evaluate
them into a sequence meaningful in the original bash syntax. After
all, they (the ``new'' syntaxes) are just functions, either in lisp or
bash, are they not? I completely fail to see how macro excels here.
> Just because macros can do one thing that you can do with eval in
> bash doesn't mean that eval in bash can do other things that macros
> can. The same applies to most of the "ooh, macros are for *this*!"
> revelations that people have early on. I started out thinking that
> they were just for writing functions that didn't evaluate their
> arguments until they were ready to. And they can, indeed, do just
> that. My point is this: don't limit your understanding of macros to
> the first thing you find that they can do.
It's a good point and thanks.
Wei
Weiguang Shi <·····@nestow.cs.ualberta.ca> writes:
> One can certainly create a function with a name and parameter
> sequence, call it ``new'' syntax, and inside the function evaluate
> them into a sequence meaningful in the original bash syntax. After
> all, they (the ``new'' syntaxes) are just functions, either in lisp or
> bash, are they not? I completely fail to see how macro excels here.
In that case, this would be a very good exercise for you as you learn
Lisp. Implement the 'for' loop syntax I demonstrated above as a
function.
Weiguang Shi wrote:
> In article <··············@hermes.theari.com>, Ari Johnson wrote:
> > Weiguang Shi <·····@nestow.cs.ualberta.ca> writes:
> >
> >> Thank you! I could only suspect.
> >>
> >> So although I don't understand LISP macros, I can still grok it.
> >
> > Off-topic note: The verb "to grok" comes from Heinlein's fascinating
> > novel _A Stranger in a Strange Land_, and roughly means to have such
> > an intimate understanding of as to be nearly one with it. If you
> > don't understand something, you cannot grok it.
> I understand what the word means. I meant it and don't think that's
> impossible. But that's off-topic.
>
> >
> > But back to the topic itself, macros can't be fairly analogized to any
> > other language that I know of, because they allow you to add syntactic
> > features to the language. I try explaining this by implementing a
> > 'for' loop in Common Lisp using a macro. Common Lisp does not have
> > such a feature, so adding it with a macro is a substantial change to
> > the syntax of the language.
> >
> > In C, you write:
> > for (i = 0; i < 10; i++) {
> > printf("i = %d\n", i);
> > }
> >
> > In Lisp, this would look like:
> > (for (i 0) (< i 10) (incf i)
> > (format t "i = ~D~%" i))
> >
> > If you type that into your Lisp, you will get an error or two. Those
> > errors will include the fact that there's no such function I and the
> > fact that there's no such function FOR.
> >
> > Let's add it to the language:
> >
> > (defmacro for (init continue next &body body)
> > (unless (consp init)
> > (error "Syntax error - init form must be a list"))
> > (let ((looplabel (gensym))
> > (var (first init))
> > (initval (second init)))
> > (unless (symbolp var)
> > (error "Syntax error - variable must be a symbol"))
> > `(prog ((,var ,initval))
> > ,looplabel
> > ,@body
> > ,next
> > (when ,continue
> > (go ,looplabel)))))
> >
> > Now try that example form again, and it will print out what you'd
> > expect. Lisp did not have this syntax beforehand and it does now.
> > You can't do that in bash.
>
> One can certainly create a function with a name and parameter
> sequence, call it ``new'' syntax, and inside the function evaluate
> them into a sequence meaningful in the original bash syntax. After
> all, they (the ``new'' syntaxes) are just functions, either in lisp or
> bash, are they not? I completely fail to see how macro excels here.
No. In Lisp, compound forms (i.e. forms which are lists as opposed to
atoms like X, 42 or "abc") come in three flavors: special forms
(essentially, built-in syntax with evaluation rules specific to that
syntax), function call forms (with a uniform evaluation syntax that
applies to all functions) and macros. Macros look like special forms;
i.e. they are the way by which new user-defined syntax can be
introduced which looks indistinguishable from some special form.
The POSIX shell command language has "special forms" also, for instance
case expr in
pattern ) ... ;;
pattern ) ... ;;
* ) ... ;;
esac
for x in words
do
command
command
...
done
If the POSIX language was programmable, you would be able to write your
own forms like this.
Note that "for" cannot be written as a bash function, because the
function has no way to inspect what follows the for clause. You have to
be able to hunt down the "do" and the "done". If for were a function
in the above example, it would be given the arguments "x" "in" and
"words". It would then return, and the shell would then consider "do"
to be the next command. (Maybe you could hack something together using
separate functions. The "for" function could record something on a
hidden stack-like structure, and the "do" and "done" commands could
arrange for looping somehow. No idea how "done" would handle the
backward branch to the "do").
A macro in Lisp is a code-transforming function that is running inside
the Lisp interpreter or compiler to implement a new syntactic
recognizer. The macro is identified by the symbol in the first position
of the list form. The entire form is then handed off to the
corresponding function, which produces some other form that is then
subsituted in place of that form. The macro call happens at the time
the source code is processed, not when it is evaluated. In some modes,
the two may be close together, such as in interactive evaluation of
forms from a listener. The programmer types in a macro calling
expression, the macro function is called to expand it, and right after
that, the results of macroexpansion are evaluated. But in general, the
two processes need not even take place in the same image.
Macro-expansion can be done on a build machine, and evaluation of the
results on the target machine.
The shell language is sometimes used with a macro processor, but an
external one. For instance, the GNU Autoconf system uses the m4 macro
expander to generate scripts and makefiles. A "configure.in" written in
the macro language is converted to "configure" which is a shell script.
The output of the macro expander is raw text which has to be tokenized,
because the shell doesn't have a data-structure based language that
could be targetted by an integrated macro processor.
In article <························@74g2000cwt.googlegroups.com>,
Kaz Kylheku wrote:
>
> Weiguang Shi wrote:
>> In article <··············@hermes.theari.com>, Ari Johnson wrote:
>> > Weiguang Shi <·····@nestow.cs.ualberta.ca> writes:
>> >
>> >> Thank you! I could only suspect.
>> >>
>> >> So although I don't understand LISP macros, I can still grok it.
>> >
>> > Off-topic note: The verb "to grok" comes from Heinlein's fascinating
>> > novel _A Stranger in a Strange Land_, and roughly means to have such
>> > an intimate understanding of as to be nearly one with it. If you
>> > don't understand something, you cannot grok it.
>> I understand what the word means. I meant it and don't think that's
>> impossible. But that's off-topic.
>>
>> >
>> > But back to the topic itself, macros can't be fairly analogized to any
>> > other language that I know of, because they allow you to add syntactic
>> > features to the language. I try explaining this by implementing a
>> > 'for' loop in Common Lisp using a macro. Common Lisp does not have
>> > such a feature, so adding it with a macro is a substantial change to
>> > the syntax of the language.
>> >
>> > In C, you write:
>> > for (i = 0; i < 10; i++) {
>> > printf("i = %d\n", i);
>> > }
>> >
>> > In Lisp, this would look like:
>> > (for (i 0) (< i 10) (incf i)
>> > (format t "i = ~D~%" i))
>> >
>> > If you type that into your Lisp, you will get an error or two. Those
>> > errors will include the fact that there's no such function I and the
>> > fact that there's no such function FOR.
>> >
>> > Let's add it to the language:
>> >
>> > (defmacro for (init continue next &body body)
>> > (unless (consp init)
>> > (error "Syntax error - init form must be a list"))
>> > (let ((looplabel (gensym))
>> > (var (first init))
>> > (initval (second init)))
>> > (unless (symbolp var)
>> > (error "Syntax error - variable must be a symbol"))
>> > `(prog ((,var ,initval))
>> > ,looplabel
>> > ,@body
>> > ,next
>> > (when ,continue
>> > (go ,looplabel)))))
>> >
>> > Now try that example form again, and it will print out what you'd
>> > expect. Lisp did not have this syntax beforehand and it does now.
>> > You can't do that in bash.
>>
>> One can certainly create a function with a name and parameter
>> sequence, call it ``new'' syntax, and inside the function evaluate
>> them into a sequence meaningful in the original bash syntax. After
>> all, they (the ``new'' syntaxes) are just functions, either in lisp or
>> bash, are they not? I completely fail to see how macro excels here.
>
> No. In Lisp, compound forms (i.e. forms which are lists as opposed to
> atoms like X, 42 or "abc") come in three flavors: special forms
> (essentially, built-in syntax with evaluation rules specific to that
> syntax), function call forms (with a uniform evaluation syntax that
> applies to all functions) and macros. Macros look like special forms;
> i.e. they are the way by which new user-defined syntax can be
> introduced which looks indistinguishable from some special form.
>
> The POSIX shell command language has "special forms" also, for instance
>
> case expr in
> pattern ) ... ;;
> pattern ) ... ;;
> * ) ... ;;
> esac
>
> for x in words
> do
> command
> command
> ...
> done
>
> If the POSIX language was programmable, you would be able to write your
> own forms like this.
>
> Note that "for" cannot be written as a bash function, because the
> function has no way to inspect what follows the for clause. You have to
> be able to hunt down the "do" and the "done". If for were a function
> in the above example, it would be given the arguments "x" "in" and
> "words". It would then return, and the shell would then consider "do"
> to be the next command. (Maybe you could hack something together using
> separate functions. The "for" function could record something on a
> hidden stack-like structure, and the "do" and "done" commands could
> arrange for looping somehow. No idea how "done" would handle the
> backward branch to the "do").
>
> A macro in Lisp is a code-transforming function that is running inside
> the Lisp interpreter or compiler to implement a new syntactic
> recognizer. The macro is identified by the symbol in the first position
> of the list form. The entire form is then handed off to the
> corresponding function, which produces some other form that is then
> subsituted in place of that form. The macro call happens at the time
> the source code is processed, not when it is evaluated. In some modes,
> the two may be close together, such as in interactive evaluation of
> forms from a listener. The programmer types in a macro calling
> expression, the macro function is called to expand it, and right after
> that, the results of macroexpansion are evaluated. But in general, the
> two processes need not even take place in the same image.
> Macro-expansion can be done on a build machine, and evaluation of the
> results on the target machine.
>
> The shell language is sometimes used with a macro processor, but an
> external one. For instance, the GNU Autoconf system uses the m4 macro
> expander to generate scripts and makefiles. A "configure.in" written in
> the macro language is converted to "configure" which is a shell script.
> The output of the macro expander is raw text which has to be tokenized,
> because the shell doesn't have a data-structure based language that
> could be targetted by an integrated macro processor.
>
Thanks. This makes more sense to me. So, details aside, the
fundamental feature that makes LISP's macro unique and in-imitable is
LISP's using the same representation for both code and data.
Wei
Weiguang Shi wrote:
> Thanks. This makes more sense to me. So, details aside, the
> fundamental feature that makes LISP's macro unique and in-imitable is
> LISP's using the same representation for both code and data.
No, because a language whose only interface to itself is raw source
code text also uses the same representation for code and data: the
character string. Well, of course not /all/ data in that language is a
character string. But then not all data in Lisp is a nested list with
atoms, either. Plus, you do other things with strings than representing
program source, and you do other things with nested lists than
representing program source.
The fundamental feature of the Lisp macro system is rather that the
source and target language for a macro is structured data representing
a syntax tree, rather than a raw character string or close-to-raw token
sequence.
It's also a nice feature that the structured data has a very
straightforward two-way correspondence to a minimalistic printed
notation, which alone suffices as a way to write programs.
The combination of these two features is inimitable in the sense that
to get both of them, you basically reinvent Lisp.
In article <························@b28g2000cwb.googlegroups.com>,
Kaz Kylheku wrote:
> Weiguang Shi wrote:
>> Thanks. This makes more sense to me. So, details aside, the
>> fundamental feature that makes LISP's macro unique and in-imitable is
>> LISP's using the same representation for both code and data.
>
> No, because a language whose only interface to itself is raw source
> code text also uses the same representation for code and data: the
> character string. Well, of course not /all/ data in that language is a
> character string. But then not all data in Lisp is a nested list with
> atoms, either. Plus, you do other things with strings than representing
> program source, and you do other things with nested lists than
> representing program source.
>
> The fundamental feature of the Lisp macro system is rather that the
> source and target language for a macro is structured data representing
> a syntax tree, rather than a raw character string or close-to-raw token
> sequence.
Is this ``structured data'' a list?
Wei
Weiguang Shi wrote:
> In article <························@b28g2000cwb.googlegroups.com>,
> Kaz Kylheku wrote:
> > Weiguang Shi wrote:
> >> Thanks. This makes more sense to me. So, details aside, the
> >> fundamental feature that makes LISP's macro unique and in-imitable is
> >> LISP's using the same representation for both code and data.
> >
> > No, because a language whose only interface to itself is raw source
> > code text also uses the same representation for code and data: the
> > character string. Well, of course not /all/ data in that language is a
> > character string. But then not all data in Lisp is a nested list with
> > atoms, either. Plus, you do other things with strings than representing
> > program source, and you do other things with nested lists than
> > representing program source.
> >
> > The fundamental feature of the Lisp macro system is rather that the
> > source and target language for a macro is structured data representing
> > a syntax tree, rather than a raw character string or close-to-raw token
> > sequence.
> Is this ``structured data'' a list?
Well, it's really a tree. If I write:-
(defun foo (x) (bar x) nil)
Then the function "read" will build a list the list contains symbols
not their values. The first element is the symbol "defun", the second
is "foo". The third is a list itself, containing x. The fourth another
sublist containing bar and x. The last two elements are nil, since nil
is used to end lists. The whole thing is a tree formed from pairs.
It is this tree that is transformed by macros. Transforming a tree is
often easier than rewriting strings, which is the way macros are
implemented in many other languages. For example is C it is wrong to
write #define SQUARE x * x because the x given the macro may be
something strange and affect the order of evaluation of the *. Instead
you must use #define SQUARE (x) * (x), which still isn't perfect since
boths x's could be functions that shouldn't be evaluated twice. These
problems are much easier if the program is a tree.
One nice example of macros is what you can do with defun itself. You
can create your own macro that defines functions, even replace the
standard defun if you like. You can for example create a new exception
handling system inside functions defined with your macro, or add a way
to embed the unit tests for a function into it's body.
Another example is object systems. If you don't like the default CLOS
object system you can write a whole new one in Lisp by using macro and
functions, without altering the compiler. The normal CLOS object
system is often implemented using many macros itself.
You could do either of these things in bash, by reading in the script
and performing string matching on it, then evaling it. The problem is
it would be much more difficult, you would have to write most of a bash
parser.
Weiguang Shi wrote:
> In article <·······················@i42g2000cwa.googlegroups.com>,
> Kaz Kylheku wrote:
> > Weiguang Shi wrote:
> >> Rob Thorpe wrote:
> >> > Well, it's really a tree. If I write:-
> >> >
> >> > (defun foo (x) (bar x) nil)
> >> >
> >> > Then the function "read" will build a list the list contains symbols
> >> > not their values. The first element is the symbol "defun", the second
> >> > is "foo". The third is a list itself, containing x. The fourth another
> >> > sublist containing bar and x. The last two elements are nil, since nil
> >> > is used to end lists. The whole thing is a tree formed from pairs.
> >>
> >> It's not obvious to me how this becomes a tree but guess I need to
> >> read&program more in LISP. Thanks!.
> >
> > http://www.cambridge.org/resources/0521612357/3218_Ch3AddlTextTreeToBrackets.pdf
> >
> Thanks. So it's like this
>
> list
> |
> +-------+-------+------------+------------+
> | | | | |
> defun foo list list nil
> | |
> x +----+----+
> | |
> bar x
Almost, in lisp it's like this:-
|
|
+-------+------+------------+---------------+--nil
| | | | |
defun foo +--nil | nil
| +-----+--nil
x | |
bar x
Each "+" is called a cons cell. It consists of two links. The 'car' is
the first link all of these in my drawing go downwards. The second is
the 'cdr' element, all these in my drawing go to the left. A list is
well-behaved, a 'proper' list if it ends with "nil" as the last cdr.
The above tree is slightly more complex than yours, but the fact that
nil always ends a list makes it somewhat easier to write code to
process it.
You don't have to worry about this much when using macros, but it's
useful to be aware of it. And it's useful when writing normal code to
manipulate lists.
"Rob Thorpe" <·············@antenova.com> writes:
> Weiguang Shi wrote:
>> In article <·······················@i42g2000cwa.googlegroups.com>,
>> Kaz Kylheku wrote:
>> > Weiguang Shi wrote:
>> >> Rob Thorpe wrote:
>> >> > Well, it's really a tree. If I write:-
>> >> >
>> >> > (defun foo (x) (bar x) nil)
>> >> >
>> >> > Then the function "read" will build a list the list contains symbols
>> >> > not their values. The first element is the symbol "defun", the second
>> >> > is "foo". The third is a list itself, containing x. The fourth another
>> >> > sublist containing bar and x. The last two elements are nil, since nil
>> >> > is used to end lists. The whole thing is a tree formed from pairs.
>> >>
>> >> It's not obvious to me how this becomes a tree but guess I need to
>> >> read&program more in LISP. Thanks!.
>> >
>> > http://www.cambridge.org/resources/0521612357/3218_Ch3AddlTextTreeToBrackets.pdf
>> >
>> Thanks. So it's like this
>>
>> list
>> |
>> +-------+-------+------------+------------+
>> | | | | |
>> defun foo list list nil
>> | |
>> x +----+----+
>> | |
>> bar x
>
> Almost, in lisp it's like this:-
> |
> |
> +-------+------+------------+---------------+--nil
> | | | | |
> defun foo +--nil | nil
> | +-----+--nil
> x | |
> bar x
>
> Each "+" is called a cons cell. It consists of two links. The 'car' is
> the first link all of these in my drawing go downwards. The second is
> the 'cdr' element, all these in my drawing go to the left. A list is
> well-behaved, a 'proper' list if it ends with "nil" as the last cdr.
>
> The above tree is slightly more complex than yours, but the fact that
> nil always ends a list makes it somewhat easier to write code to
> process it.
>
> You don't have to worry about this much when using macros, but it's
> useful to be aware of it. And it's useful when writing normal code to
> manipulate lists.
Actually, both trees are "correct". Only they don't work at the same
level of abstraction. Note that Rob tree is a binary tree, where each
node only contain a left child and a right child (car and cdr). The
nodes are not labelled, only the leaves are atoms. It may be better
draw as:
|
+
/ \
/ \
defun +
/ \
/ \
foo +
/ \
/ \
+ +
/ \ ...
/ \
x nil
This can written in lisp as :
(DEFUN . (FOO . ((X . ()) . ((BAR . (X . ())) . (() . ())))))
Weiguang's tree is a n-ary tree of an higher level of abstraction,
where heac list contains the label of the node, and the children.
(label child1 ... childn)
We have only three nodes:
- one labelled defun, with four children: FOO (X) (BAR X) NIL
- one labelled X, with no child.
- one labelled BAR, with one child X
(DEFUN FOO (X) (BAR X) NIL)
You can explicit these data structures:
(defun make-bintree (left right) (cons left right))
(defun bintree-left (tree) (car tree))
(defun bintree-right (tree) (cdr tree))
or:
(defun make-ntree (label &rest children) (cons label children))
(defun ntree-label (tree) (car tree))
(defun ntree-children (tree) (cdr tree))
Now, the funny thing, is that these two levels of abstraction directly
collapse to the identical data structure:
(equal '(DEFUN . (FOO . ((X . ()) . ((BAR . (X . ())) . (() . ())))))
'(DEFUN FOO (X) (BAR X) NIL))
--> T
Now, one could argue that given the structure of a lisp program,
Weiguang's tree is better to conceptualize lisp programs.
PS: Here is how I draw my cons cells ;-)
[31]> (com.informatimago.common-lisp.cons-to-ascii:draw-list
'(defun foo (x) (bar x) nil) :title "(DEFUN FOO (X) (BAR X) NIL))")
+-----------------------------------------------------------+
| (DEFUN FOO (X) (BAR X) NIL)) |
| |
| +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ |
| | * | * |-->| * | * |-->| * | * |-->| * | * |-->|NIL|NIL| |
| +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ |
| | | | | |
| v v v v |
| +-------+ +-----+ +---+---+ +---+---+ +---+---+ |
| | DEFUN | | FOO | | * |NIL| | * | * |-->| * |NIL| |
| +-------+ +-----+ +---+---+ +---+---+ +---+---+ |
| | | | |
| v v v |
| +---+ +-----+ +---+ |
| | X | | BAR | | X | |
| +---+ +-----+ +---+ |
+-----------------------------------------------------------+
--
__Pascal Bourguignon__ http://www.informatimago.com/
THIS IS A 100% MATTER PRODUCT: In the unlikely event that this
merchandise should contact antimatter in any form, a catastrophic
explosion will result.
Weiguang Shi wrote:
> In article <·······················@i42g2000cwa.googlegroups.com>,
> Kaz Kylheku wrote:
> > Weiguang Shi wrote:
> >> Rob Thorpe wrote:
> >> > Well, it's really a tree. If I write:-
> >> >
> >> > (defun foo (x) (bar x) nil)
> >> >
> >> > Then the function "read" will build a list the list contains symbols
> >> > not their values. The first element is the symbol "defun", the second
> >> > is "foo". The third is a list itself, containing x. The fourth another
> >> > sublist containing bar and x. The last two elements are nil, since nil
> >> > is used to end lists. The whole thing is a tree formed from pairs.
> >>
> >> It's not obvious to me how this becomes a tree but guess I need to
> >> read&program more in LISP. Thanks!.
> >
> > http://www.cambridge.org/resources/0521612357/3218_Ch3AddlTextTreeToBrackets.pdf
> >
> Thanks. So it's like this
>
> list
> |
> +-------+-------+------------+------------+
> | | | | |
> defun foo list list nil
> | |
> x +----+----+
> | |
> bar x
That's correct; it's how one might visualize the syntax tree.
At a lower level, this N-ary tree is really made of binary conses. So
the horizontal parts are really sideways trees:
Each "list" is just a pointer to the leftmost "+" which is a cons. Each
"+" is a cons cell, each downward "|" is a CAR field, and each
"---..--" is the CDR pointing left. A cons that has no left pointer in
the diagram has a CDR field containing NIL. I.e. these two are the same
+
|
X
+---- NIL
|
X
However, you usually don't have to take these lower-level details into
account when reasoning about syntax. You don't think of it as a binary
tree made of CAR/CDR pointers. The elements of a list are seen as the
children of an N-ary tree, all on the same level.
You can drop the "list" placeholders to create a simplified picture:
+-------+-------+------------+------------+
| | | | |
defun foo + +----+ nil
| | |
x bar x
The nice thing about this picture is that you can see the N-ary tree,
but also the binary one if you just rotate it 45 degrees to the right.
From: Duane Rettig
Subject: Re: eval in bash vs macro in lisp
Date:
Message-ID: <o0r6z3plt6.fsf@franz.com>
Ari Johnson <·········@gmail.com> writes:
[ ... ]
> If you type that into your Lisp, you will get an error or two. Those
> errors will include the fact that there's no such function I ...
[ ... ]
> Now try that example form again, and it will print out what you'd
> expect. Lisp did not have this syntax beforehand and it does now.
Excellent point and beautifully put, and likely to get lost on someone
who doesn't catch its implication.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182