fringe definition
jrwats
(all the leaves) of a tree. However, all the implementations I've
seen iterate through *all* the nodes. So I either do not have the
definition of fringe correct, or LISPers have a different defintion or
something else - I don't know what. In my view here is a binary tree
with 4 as the root node, 2 as it's left child, 6 as it's right and so
on:
(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.
Below are 2 implementations:
#1 fringe implementation from http://home.pipeline.com/~hbaker1/Iterator.html:
(defun fringe (x &optional (c nil)) ; fringe of
tree x.
(if (atom x) (cons x c) (fringel x c)))
(defun fringel (xl c) ; fringe of list of
trees xl.
(if (null xl) c (fringe (car xl) (fringel (cdr xl) c))))
(fringe bin-tree) = (4 2 1 3 6 5 7)
#2 from http://www.dreamsongs.com/10ideas.html
(defun leaves (tree)
(cond ((atom tree) (list tree))
(t (append (leaves (car tree))
(leaves (cdr tree))))))
(leaves bin-tree) = (4 2 1 3 nil 6 5 7 nil nil)
gotta love the nils
...Finally here is my view of what the fringe implementation should
be:
(defun left-child (node)
(cond ((or (atom node) (null node)) nil)
((cadr node))))
(defun right-child (node)
(cond ((or (atom node) (null node)) nil)
((caddr node))))
(defun is-leaf (node)
(or (not (left-child node))
(not (right-child node))))
(defun get-fringe (tree)
(cond ((is-leaf tree) (list tree))
(t (append (get-fringe (left-child tree))
(get-fringe (right-child tree)))))
(get-fringe bin-tree) = (1 3 5 7)
So what is going on?
Rainer Joswig
<d6105697-9bd7-4e55...@i24g2000prf.googlegroups.com>,
jrwats <jrw...@gmail.com> wrote:
Is that homework?
See this:
CL-USER 17 > (sdraw:sdraw '(4 (2 1 3) (6 5 7)))
[*|*]--->[*|*]--------------------------->[*|*]--->NIL
| | |
v v v
4 [*|*]--->[*|*]--->[*|*]--->NIL [*|*]--->[*|*]--->[*|*]--->NIL
| | | | | |
v v v v v v
2 1 3 6 5 7
What you see is that (4 (2 1 3) (6 5 7)) is a binary
tree made of conses, numbers and nils.
(4 . ((2 . (1 . (3 . nil))) . ((6 . (5 . (7 . nil))) . nil)))
has the same cons structure as (4 (2 1 3) (6 5 7))
CL-USER 19 > (equal '(4 . ((2 . (1 . (3 . nil))) . ((6 . (5 . (7 . nil))) . nil)))
'(4 (2 1 3) (6 5 7)))
T
left-child = CAR
right-child = CDR
is-leaf = ATOM
Your tree definition is different - that's all.
Tim Bradshaw
>
> So what is going on?
They are using different notions of what a tree is than you. For
instance the Gabriel one is walking over the cons tree and
accumulating its leaves. That's a completely different thing than
your tree.
So, basically you need to understand the data structures involved, not
just assume that because the function has a particular name it will do
what you think it should.
Pascal J. Bourguignon
> So I've seen many people implement functions that return the fringe
> (all the leaves) of a tree. However, all the implementations I've
> seen iterate through *all* the nodes. So I either do not have the
> definition of fringe correct, or LISPers have a different defintion or
> something else - I don't know what. In my view here is a binary tree
> with 4 as the root node, 2 as it's left child, 6 as it's right and so
> on:
>
> (setf bin-tree '(4 (2 1 3) (6 5 7)))
Ho! La! Not so fast!
Have a look at:
http://groups.google.com/group/comp.lang.lisp/msg/0c66e597e08be90d
> Thus in my view the only fringe nodes (leaves) are 1, 3, 5, and 7.
You didn't give us enough information yet to know that.
> Below are 2 implementations:
> #1 fringe implementation from http://home.pipeline.com/~hbaker1/Iterator.html:
> (defun fringe (x &optional (c nil)) ; fringe of
> tree x.
> (if (atom x) (cons x c) (fringel x c)))
>
> (defun fringel (xl c) ; fringe of list of
> trees xl.
> (if (null xl) c (fringe (car xl) (fringel (cdr xl) c))))
>
> (fringe bin-tree) = (4 2 1 3 6 5 7)
There is some implied tree representation at work here.
Exercise left to the reader: explicit the tree representation.
> #2 from http://www.dreamsongs.com/10ideas.html
> (defun leaves (tree)
> (cond ((atom tree) (list tree))
> (t (append (leaves (car tree))
> (leaves (cdr tree))))))
>
> (leaves bin-tree) = (4 2 1 3 nil 6 5 7 nil nil)
> gotta love the nils
There is some other implied tree representation at work here.
Exercise left to the reader: explicit this other tree representation.
> ...Finally here is my view of what the fringe implementation should
> be:
> (defun left-child (node)
> (cond ((or (atom node) (null node)) nil)
> ((cadr node))))
>
> (defun right-child (node)
> (cond ((or (atom node) (null node)) nil)
> ((caddr node))))
>
> (defun is-leaf (node)
> (or (not (left-child node))
> (not (right-child node))))
That's good, you're defining a tree represention. It would be nicer
if you gave the corresponding make-tree-node and make-tree-leaf constructors.
(defun make-tree-node (label left-subtree right-subtree)
(list label left-subtree right-subtree))
(defun make-tree-leaf (label) (list label nil nil))
> (defun get-fringe (tree)
> (cond ((is-leaf tree) (list tree))
> (t (append (get-fringe (left-child tree))
> (get-fringe (right-child tree)))))
>
> (get-fringe bin-tree) = (1 3 5 7)
>
> So what is going on?
(get-fringe (make-tree-node 4 (make-tree-node 2 (make-tree-leaf 1) (make-tree-leaf 3))
(make-tree-node 6 (make-tree-leaf 5) (make-tree-leaf 7))))
--> ((1 NIL NIL) (3 NIL NIL) (5 NIL NIL) (7 NIL NIL))
Notice that: (make-tree-leaf 1) --> (1 NIL NIL)
Perhaps you meant something else for a leaf?
;-)
--
__Pascal Bourguignon__ http://www.informatimago.com/
This is a signature virus. Add me to your signature and help me to live.
xah...@gmail.com
> So I've seen many people implement functions that return the fringe
> (all the leaves) of a tree. However, all the implementations I've
> seen iterate through *all* the nodes. So I either do not have the
> definition of fringe correct, or LISPers have a different defintion or
> something else - I don't know what. In my view here is a binary tree
> with 4 as the root node, 2 as it's left child, 6 as it's right and so
> on:
>
> (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.
You are correct.
The reason you see lispers define otherwise is because lisp's cons
business really screwed up its lists.
For a detailed explanation:
Fundamental Problems of Lisp
http://xahlee.org/UnixResource_dir/writ/lisp_problems.html
Trees and Indexes
http://xahlee.org/tree/a-trees_indexes.html
(10 years old article)
For several more articles about trees, see:
http://xahlee.org/tree/tree.html
however, most of these are 10 years old and not maintained.
I see some lisp regulars here have tried to give you answers. In
general, they'll tell you how you misunderstood tree, or how you
should understand data structure, etc. Basically, any of their general
remarks about trees are garbage. Trust me. I'm a tree expert.
Xah
∑ http://xahlee.org/
☄
Tim Bradshaw
> Fundamental Problems of Lisphttp://xahlee.org/UnixResource_dir/writ/lisp_problems.html
What Xah means is "Lisp doesn't actually have lists: it has conses and
a little bit of syntax which makes certain kinds of trees of conses
print and read prettily.
Somehow this upsets him deeply: I guess if it had been called CONSP
rather than LISP this would have all been OK.
Don Geddis
> For several more articles about trees, see:
> Trust me. I'm a tree expert.
I've got some Monterey Pines in my backyard, but I hear that they require
a lot of water. Do you think my landscaping would be more drought-resistant
if I planted Stone Pines instead?
-- Don
(Everybody else on c.l.l: yes, yes, I know. Why respond at all? I think I
have a sickness. I just can't resist sometimes. Much apologies to the
community. I'm working on my problem. Just ignore, just ignore, just
ignore...)
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ d...@geddis.org
"The prince wants your daughter for his wife."
"Well, tell him his wife can't have her." -- Blackadder III
Tamas K Papp
> (Everybody else on c.l.l: yes, yes, I know. Why respond at all? I
> think I have a sickness. I just can't resist sometimes. Much apologies
> to the community. I'm working on my problem. Just ignore, just ignore,
> just ignore...)
I don't mind if someone occasionally quotes 1-3 lines from the guy for
amusement :-) I don't see his rants otherwise, which is a relief.
Tamas
xah...@gmail.com
> On Aug 5, 4:38 pm, "xah...@gmail.com" <xah...@gmail.com> wrote:
>
> > Fundamental Problems of Lisp http://xahlee.org/UnixResource_dir/writ/lisp_problems.html
>
> a little bit of syntax which makes certain kinds of trees of conses
> print and read prettily.
>
> Somehow this upsets him deeply: I guess if it had been called CONSP
> rather than LISP this would have all been OK.
It's not a naming problem.
The lisp's cons is a fundamental problem in the language today.
http://xahlee.org/UnixResource_dir/writ/lisp_problems.html
“Lisp's cons is perhaps the greatest fuck up in the history of
computer languages.” —Xah Lee
-----------------------------------
Now, a little speculation.
We might wonder, why lisp has the cons problem and was never
addressed?
I guess at the time, 1960s, the very fact that you could have a
concept like a list in a lang and manipulate it as a unit, is
extremely advaced at the time. The list, being built up by hardware
cons, is just something that has to be done.
having data as a single manipulatable object (list) didn't really
become popular until the 1990s. (notably by Perl, and others) And
today, it is THE most important feature of highlevel languages (perl,
python, php, javascript... of the ones i know of).
the lisp's cons, as a underlying primitive that builds lists, even
though a bit cumbersome, but works just fine when list structure are
simple. Even today, with all the perl, python, php, javascript etc
langs that deal with lists, vast majority of list usage is just simple
flat list, sometimes 2 level of nesting (list of list, list of hash,
hash of list). 3 levels of listing is seldomly used unless it's
dealing with 3d matrices. Greater than 3 level is almost never seen.
Systematic manipulation and exploitation of nested list, such as
mapping to leafs, to particular level, transposition by permutation on
level, etc is hardly even to be seen. (except Mathematica, APL)
So, in general, when you just deal with simple lists, the deficiency
in lisp's doesn't really suface.
-----------------
Today, with lisp manipulation ubiquitous. The lisp's cons business
becomes more apparent and painful.
Xah
∑ http://xahlee.org/
☄
George Neuner
wrote:
>So I've seen many people implement functions that return the fringe
>(all the leaves) of a tree. However, all the implementations I've
>seen iterate through *all* the nodes. So I either do not have the
>definition of fringe correct, or LISPers have a different defintion or
>something else - I don't know what. In my view here is a binary tree
>with 4 as the root node, 2 as it's left child, 6 as it's right and so
>on:
>
>(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.
>:
>So what is going on?
What you have is not a binary tree, but a nested list built from
Lisp's cons cells. Conses have only 2 fields and so they cannot hold
key data and 2 child pointers necessary to create a proper binary
tree. You can create more appropriate tree nodes using structures or
CLOS objects or even vectors.
If you want to stay with conses, you can approximate a binary tree by
storing key data in the car and a (single) downward link to children
in the CDR using a nil to signify no children ... something like as
follows:
(4 . ((2 . ((1 . ()) . (3 . ()))) . (6 . ((5 . ()) . (7 . ())))))
4 . *
|
* . *
/ \
2. * 6 . *
/ \
* . * * . *
/ | | \
/ | | \
1 . - 3 . - 5 . - 7 . -
It's fairly simple to build and use such a tree programmatically, but
it is somewhat convoluted to enter data manually.
George
John Thingstad
<gneu...@comcast.net>:
>
> It's fairly simple to build and use such a tree programmatically, but
> it is somewhat convoluted to enter data manually.
>
> George
Not really you just use (defstruct (bintree (:type list))...
--------------
John Thingstad
xah...@gmail.com
> 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/
☄
xah...@gmail.com
«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/
☄
-------------------------------------------
Tim Bradshaw
> “Lisp's cons is perhaps the greatest fuck up in the history of
> computer languages.” —Xah Lee
Really the question we need the answer to here: if we bate you some
more, will you burst? Because obviously, if you will, it will be
worth it, but otherwise it's just yet another tedious waste of time.
Rainer Joswig
<729da8ac-d9b8-4d85...@n33g2000pri.googlegroups.com>,
"xah...@gmail.com" <xah...@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?
xah...@gmail.com
«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/
☄
xah...@gmail.com
burst? as in starting to swear? or making a ridiculously exaggerated
claim?
Recently i kinda started a conversational styled posting manner. There
are good and bad points... but anyway i don't feel comfy in reply to
one liners or myself being on-liners...
Write more Tim, with more thoughts please. So we can avoid on-liner
slipslop exchanges.
Xah
∑ http://xahlee.org/
☄