Re: fringe definition

> (setf bin-tree '(4 (2 1 3) (6 5 7)))
> Thus in my view the only fringe nodes (leaves) are 1, 3, 5, and 7.

also note, when in a language where there's isomorphism between the
syntax and the nested list, there's a concept of head.

For example, in pseudo lisp:

(list (list 1 3) (list 5 7))

In this list, the 1,3,5,7 are leafs. Each having index
{1,1}, {1,2}, {2,1}, {2,2}.

Now, the three appearances of “list”, are non-leaf nodes inthe tree,
having indexes of: {0}, {1,0}, {2,0}. These positions are called Head
in Mathematica, and the notion of head also appear in lisp.

Now, consider this pseudo lisp:

(4 (2 1 3) (6 5 7))

which is closer to what you gave above. Now, the element at index {0}
is 4, and at {1,0} is 2, and at {2,0} is 6.

The whole expression itself, is still a tree or a nested list. In this
way, we can see that there is a isomorphism between the textual
representation of a tree, and what is actually considered a list
datatype in the lisp-like language.

So, suppose you invented a lisp language, so that there's no cons, but
the symbol “list” represent a list datatype (the implementation of the
language may actually just be linked list as cons). So, in this
language, the expression

(list (list 1 3) (list 5 7))

would represent a list datatype. However, the expression

(4 (2 1 3) (6 5 7))

would not be a list datatype, however, the expression's structure is
identical to the previous one, and still a tree. In this language,
when the head of a expression does not have a valid definition, such
as being a integer, it is simply left unevaluated.

So, in this lang, both

(list (list 1 3) (list 5 7))
and
(4 (2 1 3) (6 5 7))

are valid expressions, and of identical structure. The expression
itself represent a tree. The 2 expression can be easily transformed
into each other, by simply doing a replacement of the atom “list” to
one of integer, or vice versa. (e.g. replacing by pattern matching or
actually apply a function to the head positions)

Now, the thing about languages with a pure nested syntax is that, the
head itself can be a nested expression. For example, you can have

((f x) 1 2 3)

So, when you have a expression such as

(x (y 1 3) (z 5 7))

The indexes at
{0}, {1,0}, {2,0}, i.e. the x, y, z,
needs not to be atoms themselves. They can be arbitrary expressions
(tree).

So this means, in this language the head, or non-leaf nodes of a tree,
can hold data, not just the leafs.

In most lang that supports nested list, such as perl, php, python,
only the leaf nodes holds data. But as you can see the above, in this
lang with regular nested syntax, not only leaf nodes can hold data,
but any node, including non-leaf nodes (heads), can hold arbitrarily
nested data.

As a illustration to intermediat, in XML, the none-leaf nodes can hold
a limited amount of data, called its attributes.

I thought i just do some education for the lispers here.

--------------------------

Now, in lisp, because of the cons, combined with the fact that its
syntax is irregular, truely, fucked up all the beauty and power of
list processing.

The problem of the cons business is well known. For example, your
surprise at the various definition of leaf is just one Frequent
puzzle. The other thing about its irregular syntax, such as

'(1 2 3)
(quote 1 2 3)
(list 1 2 3)

adds more complexity to the cons problem. For example, if you read
again the above exposition about the isomorphism between the purely
nested uniform syntax, tree, and list datatype, and try to apply it to
Common Lisp, Emacs Lisp, or Scheme Lisp, you'll find all sort of
problems, and really see how lisp is crippled, in the sense that it
could have been far more consistent, simpler, powerful.

The above pseudo lisp lang explanation is based on my knowledge of
Mathematica. i.e. it is basically how Mathematica is.

Further readings:

• Trees
http://xahlee.org/tree/tree.html

• “The Concepts and Confusions of Prefix, Infix, Postfix and Fully
Functional Notations”
http://xahlee.org/UnixResource_dir/writ/notations.html

• Fundamental Problems of Lisp
http://xahlee.org/UnixResource_dir/w..._problems.html

This post is posted to comp.lang.lisp, comp.lang.functional .

The whole thread of this message can be seen at
http://groups.google.com/group/comp....9519b32b4ef5d5

Xah
∑ http://xahlee.org/

☄