Re: eval in bash vs macro in lisp

"Rob Thorpe" <robert.thorpe@xxxxxxxxxxxx> writes:

Weiguang Shi wrote:
In article <1156791222.123136.15280@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
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.
.

Relevant Pages

  • Re: The empty list and the end of a list
    ... takes a list (tree) as input and returns a list of all atoms. ... The embedded NIL differs from the ending NIL in its syntactic ... (atom (list tree)) ... NIL atoms, rather than flattening them as if they denoted empty lists, ...
    (comp.lang.lisp)
  • Re: ASDF-newbie: How to determine whether ASDF is *already* installed on my ISP?
    ... ;This is not as strict as an AVL tree, so it gets somewhat more unbalanced, ... use NIL as val in all cases. ... ;Are we looking at the very top level of a MBBT object here? ... (defun mbbt-is-tree (mbbt) ...
    (comp.lang.lisp)
  • Re: The empty list and the end of a list
    ... takes a list (tree) as input and returns a list of all atoms. ... The embedded NIL differs from the ending NIL in its syntactic ... NIL atoms, rather than flattening them as if they denoted empty lists, ... (atom (list tree)) ...
    (comp.lang.lisp)
  • Re: request comments: simple c program builder in lisp
    ... break for lists with over 2047 items. ... Do you think you would ever want to concatenate more that 2048 elements in ... CFILE:CLEANABLE NIL)) ... (defun last-substr-pos-re (sub str) ...
    (comp.lang.lisp)
  • Re: trouble learning LISP
    ... (A B NIL C NIL D E F NIL NIL ...) ... (defun flatten (tree) ... (cond ((atom tree) ... You are mixing two different data types: lists and cons cells. ...
    (comp.lang.lisp)