> (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 in the 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/writ/lisp_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.lang.lisp/browse_frm/thread/ee9519b32b4ef5d5
Xah
∑ http://xahlee.org/
☄
I hasten to add, that in my previous post, i said that:
«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.»
actually, lang such as perl, php, python, javascript, you can actually
have a nested list where the non-leaf nodes also holds arbitrary data.
All you have to do, is to consider that the first element of a list as
the non-leaf nodes (i.e. lisp's “head”).
In langs such as perl etc, assuming 1st element of list as non-leaf
node is not a problem. But in lang with a purely nested syntax, by
assuming the 1st element of list as non-leaf node, i think it
necessarily introduces a more complex model of interpretation if you
still want a isomorphism between the syntax, tree, and list datatype.
Xah
∑ http://xahlee.org/
☄
-------------------------------------------
> (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 in the 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/writ/lisp_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.lang.lisp/browse_frm/thread/ee9519b32b4ef5d5
Xah
∑ http://xahlee.org/
☄
In article
<····································@n33g2000pri.googlegroups.com>,
·······@gmail.com" <······@gmail.com> wrote:
> I hasten to add, that in my previous post, i said that:
>
> «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.»
>
> actually, lang such as perl, php, python, javascript, you can actually
> have a nested list where the non-leaf nodes also holds arbitrary data.
> All you have to do, is to consider that the first element of a list as
> the non-leaf nodes (i.e. lisp's “head”).
>
> In langs such as perl etc, assuming 1st element of list as non-leaf
> node is not a problem. But in lang with a purely nested syntax, by
> assuming the 1st element of list as non-leaf node, i think it
> necessarily introduces a more complex model of interpretation if you
> still want a isomorphism between the syntax, tree, and list datatype.
>
> Xah
> ∑ http://xahlee.org/
>
> ?
>
> -------------------------------------------
>
> > (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.
>
I think I'll help you invest a bit into your Lisp education. Read carefully.
Get your favorite Lisp system (I would recommend a Common Lisp
system like CLISP) and try things out yourself. I'll write sometimes
nice postings, this is one. ;-)
You can have every view you want. Just use your definition of leaves
and trees and map it to Lisp's lists and conses. I'm doing the
same. That's part of the flexibility of Lisp that
it leaves you the task to interpret what are the parts of a list.
Before people were using 'real' data structures' lists were
used for all kinds of data. An example
(:type :family
:name "schmidt"
:members ((:type :person :name "klaus" :age 12)
(:type :person :name "sophie" :age 15)))
Data is presented as 'property lists'. There is no type 'property list'.
It is just a convention that a property list is a list of key and value
pairs.
CL-USER 41 > (defvar *family* '(:type :family
:name "schmidt"
:members ((:type :person :name "klaus" :age 12)
(:type :person :name "sophie" :age 15))))
*FAMILY*
So now you can get the name:
CL-USER 44 > (getf *family* :name)
"schmidt"
Or the members:
CL-USER 45 > (getf *family* :members)
((:TYPE :PERSON :NAME "klaus" :AGE 12) (:TYPE :PERSON :NAME "sophie" :AGE 15))
Or you can loop over all members and collect the ages and so on.
CL-USER 46 > (loop for member in (getf *family* :members) collect (getf member :age))
(12 15)
So we get a list of the age values.
These are property lists. Then there are assoc lists and more.
Assoc lists are also not a Lisp data type, but a convention
how to put data into lists and get data out of lists:
(defparameter *family-1* '((:type . :family)
(:name . "Schmidt")
(:members . (((:type . :person)
(:name . "klaus")
(:age . 12))
((:type . :person)
(:name . "sophie")
(:age . 15))))))
Above shows that one can use a list of conses.
CL-USER 106 > (assoc :name *family-1*)
(:NAME . "Schmidt")
With ASSOC one can search for elements.
CL-USER 107 > (cdr (assoc :members *family-1*))
(((:TYPE . :PERSON) (:NAME . "klaus") (:AGE . 12)) ((:TYPE . :PERSON) (:NAME . "sophie") (:AGE . 15)))
CDR gives us the data.
For example we want a list of the names of the family members:
CL-USER 108 > (mapcar (lambda (person) (cdr (assoc :name person)))
(cdr (assoc :members *family-1*)))
("klaus" "sophie")
What ever your problem with Lisp lists is, it does not matter, since
one is perfectly able to write all kinds of interesting list manipulation
code in Lisp. Your cons-phobia does not change this. Last time
you came up with some Mathematica function I gave you a nice
implementation in Common Lisp in a few lines. Lisp (and especially
Common Lisp) has all kinds of useful list manipulation functionality
built in. They might not look what you expect. So, I recommend
'unlearning'. Unlearn what you know. Empty your head and start fresh.
Take a problem and try to implement it. The many lines of beautiful
Emacs Lisp code (I really think that a lot of Emacs code is extremely
well written) show that one can be productive with a relatively simple Lisp
dialect.
> 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))
CL-USER 47 > (read)
(list (list 1 3) (list 5 7))
(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}.
Sure, what ever. You can define it like you want.
Common Lisp lets you define your own interpretation of lists:
CL-USER 57 > (defstruct (computer (:type list) :named) brand cpu disks)
COMPUTER
CL-USER 58 > (defstruct (disk (:type list) :named) brand size)
DISK
CL-USER 61 > (make-computer :brand 'symbolics
:cpu 'ivory
:disks (list (make-disk :brand 'seagate :size '4gb)
(make-disk :brand 'seagate :size '4gb)))
(COMPUTER SYMBOLICS IVORY ((DISK SEAGATE 4GB) (DISK SEAGATE 4GB)))
CL-USER 63 > (computer-brand *)
SYMBOLICS
CL-USER 64 > (computer-disks **)
((DISK SEAGATE 4GB) (DISK SEAGATE 4GB))
Later in the Lisp history, structures and objects have been added.
So data like above is no longer put in lists, but structures or
objects. For structures the code does not change much:
CL-USER 89 > (defstruct computer brand cpu disks)
COMPUTER
CL-USER 90 > (defstruct disk brand size)
DISK
CL-USER 91 > (make-computer :brand 'symbolics
:cpu 'ivory
:disks (list (make-disk :brand 'seagate :size '4gb)
(make-disk :brand 'seagate :size '4gb)))
#S(COMPUTER :BRAND SYMBOLICS :CPU IVORY :DISKS (#S(DISK :BRAND SEAGATE :SIZE 4GB) #S(DISK :BRAND SEAGATE :SIZE 4GB)))
CL-USER 92 > (computer-brand *)
SYMBOLICS
CL-USER 93 > (computer-disks **)
(#S(DISK :BRAND SEAGATE :SIZE 4GB) #S(DISK :BRAND SEAGATE :SIZE 4GB))
> 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
You confuse syntax of expressions with syntax of Lisp programs.
One of the first things you need to learn when using Lisp
that the Lisp syntax is based on s-expressions.
>
> '(1 2 3)
> (quote 1 2 3)
> (list 1 2 3)
That's already wrong:
'(1 2 3) is a shorthand notation for (quote (1 2 3)) and not (quote 1 2 3).
Let's first READ the data:
CL-USER 81 > (read)
'(1 2 3) ; input
(QUOTE (1 2 3)) ; result
You can see that I wrote a quote sign above and it got read.
Lisp then prints it as (QUOTE (1 2 3)) .
Let's try the next one:
CL-USER 82 > (read)
(quote (1 2 3))
(QUOTE (1 2 3))
Above I get back what I entered.
CL-USER 83 > (read)
(list 1 2 3)
(LIST 1 2 3)
Again the reader just reads the form.
Now above were all forms in the programming language Lisp.
Let's just read the canonical list:
CL-USER 84 > (read)
(1 2 3)
(1 2 3)
That's all. A list as input and the list as output.
So why are there (quote (1 2 3)) and (list 1 2 3) ?
Both QUOTE and LIST are part of the programming language (let's say
Common Lisp, but it's true for most other forms of Lisp, like Emacs Lisp
or others).
QUOTE comes into play if you want to evaluate lists as programs.
QUOTE just tells the Lisp system to not evaluate what it encloses
and just treat it as data.
So:
(quote (1 2 3)) evaluated is just (1 2 3)
CL-USER 87 > (quote (1 2 3))
(1 2 3)
So, now to LIST. LIST is a function that returns its arguments in a list.
CL-USER 88 > (list 1 2 3)
(1 2 3)
Both have nothing to do with the syntax of s-expressions. Both are
part of the programming language Lisp.
To see the difference:
(quote 1 2 3) is a valid s-expression.
(quote 1 2 3) is not a valid Lisp expression.
CL-USER 109 > (read)
(quote 1 2 3)
(QUOTE 1 2 3)
CL-USER 110 > (QUOTE 1 2 3)
Error: The call (QUOTE 1 2 3) does not match definition (QUOTE SYSTEM::OBJECT).
1 (continue) Return a value from the call to QUOTE.
2 Try calling another function instead of QUOTE with the same arguments.
3 Try calling QUOTE with a new argument list.
4 (abort) Return to level 0.
5 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other options
So there is a price to pay that Lisp programs use s-expressions:
data and programs look similar. It's powerful but takes a bit
to master.
So, does that help with your cons-phobia?
--
http://lispm.dyndns.org/
On Aug 7, 12:12 pm, Rainer Joswig <······@lisp.de> wrote:
«You can have every view you want. Just use your definition of leaves
and trees and map it to Lisp's lists and conses.»
The major point i was trying to show, is the isomorphism between the
pure nested syntax and the tree data structure. The term “isomorphism”
is used here in some strict math sense, to mean there's a one-to-one
correspondence.
I think you missed the point completely.
Rainer wrote:
«What ever your problem with Lisp lists is, it does not matter, since
one is perfectly able to write all kinds of interesting list
manipulation code in Lisp.»
When you write in a dimissive way, you better take care to not convey
that you didn't read the originally carefully.
By your post, it seems to me you simply missed the point, and went on
with lisp fanaticism. You can see such fanatical defense in just about
any language forum every week, where the major value in these post are
just “how to do or think about problem XYZ in my language”.
Is there some means to measure my above claim? Perhaps, ask a outsider
(a non-lisp programer) to read our posts. I dare say, he'll find much
valuable general-purpose programing language information and more
valid argument, in my posts in this thread.
Rainer wrote:
«Last time you came up with some Mathematica function I gave you a
nice implementation in Common Lisp in a few lines.»
Yes. I meanted to answer to it because it is a very quality post.
Sorry about that.
spent 5 min now but I couldn't locate the post. I thought it's in this
thread:
http://groups.google.com/group/comp.lang.lisp/browse_frm/thread/4d92a412499a9bfd/
but didn't see it.
well, i wanted to reply and tell you that your code is simply wrong.
i.e. producting incorrect result. But that is difficult to do. I don't
know Common Lisp, don't have any CL installed, and your code is quite
complex.
[spend like 1 hour writing several more paragraphs that wondered
off... but i better stop here now.]
I'll read your post more carefully later to winnow any tech insight i
might get for CL technicalities. If i find something and worthy
comment, i'll post.
PS
> > '(1 2 3)
> > (quote 1 2 3)
> > (list 1 2 3)
>
> That's already wrong:
those are not intented to be equivalent.
Post elisp code Rainer. No political connotation here, but elisp code
is simply more communicative to me, and hopefully is trivial for old
lisp hat as you.
Xah
∑ http://xahlee.org/
☄