···@jaguNET.com (Bob) writes:
> Does anyone have any sample code for constructing a simple binary tree
> using lisp?
Binary trees are unfortunately not possible in Lisp because conses
only have two elements, and you need three (left, right, value) to
implement most kinds of binary tree. This is why Lisp is so slow and
C++ is so fast. Your best approach is to implement a version of Lisp
which has 3-element cons cells, this is what most people do.
--tim
Tim Bradshaw <···@tfeb.org> writes:
> > Does anyone have any sample code for constructing a simple binary tree
> > using lisp?
>
> Binary trees are unfortunately not possible in Lisp because conses
> only have two elements, and you need three (left, right, value) to
> implement most kinds of binary tree. This is why Lisp is so slow and
> C++ is so fast. Your best approach is to implement a version of Lisp
> which has 3-element cons cells, this is what most people do.
Yes, this is a most grave problem with Common Lisp indeed, which has
really hindered the acceptance of Common Lisp for quite some time.
It has prevented me from using Common Lisp for any projects,
because every time I try to convince my boss to use Common Lisp
instead of Perl and Visual Basic, he quite clearly turns me down with
the words: "Look son, we be doin' many binary trees in here! Lisp no
got binary trees, only got unary trees. Unary trees no good says
Larry Wall, Lisp no good, Perl ruleZ!"... Very sad...
But there is hope on the horizon: Are you going to push for the
introduction of 3-element conses to Common Lisp in NCITS/J13?
Maybe then I'll be able to use Common Lisp...
--
Pierre Mai <····@acm.org> http://home.pages.de/~trillian/
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
In article <··············@orion.dent.isdn.cs.tu-berlin.de>, ····@acm.org
(Pierre R. Mai) wrote:
>Tim Bradshaw <···@tfeb.org> writes:
>
>> > Does anyone have any sample code for constructing a simple binary tree
>> > using lisp?
>>
>> Binary trees are unfortunately not possible in Lisp because conses
>> only have two elements, and you need three (left, right, value) to
>> implement most kinds of binary tree. This is why Lisp is so slow and
>> C++ is so fast. Your best approach is to implement a version of Lisp
>> which has 3-element cons cells, this is what most people do.
>
>Yes, this is a most grave problem with Common Lisp indeed, which has
>really hindered the acceptance of Common Lisp for quite some time.
>It has prevented me from using Common Lisp for any projects,
>because every time I try to convince my boss to use Common Lisp
>instead of Perl and Visual Basic, he quite clearly turns me down with
>the words: "Look son, we be doin' many binary trees in here! Lisp no
>got binary trees, only got unary trees. Unary trees no good says
>Larry Wall, Lisp no good, Perl ruleZ!"... Very sad...
>
>But there is hope on the horizon: Are you going to push for the
>introduction of 3-element conses to Common Lisp in NCITS/J13?
And here I thought it was because all lisps are interpreted that
the language has been withering on the vine for lo these many years.
paul
Paul Wallich (··@panix.com) wrote:
: In article <··············@orion.dent.isdn.cs.tu-berlin.de>, ····@acm.org
: (Pierre R. Mai) wrote:
: >Tim Bradshaw <···@tfeb.org> writes:
: >
: >> > Does anyone have any sample code for constructing a simple binary tree
: >> > using lisp?
: >>
: >> Binary trees are unfortunately not possible in Lisp because conses
: >> only have two elements, and you need three (left, right, value) to
: >> implement most kinds of binary tree. This is why Lisp is so slow and
: >> C++ is so fast. Your best approach is to implement a version of Lisp
: >> which has 3-element cons cells, this is what most people do.
: >
: >Yes, this is a most grave problem with Common Lisp indeed, which has
: >really hindered the acceptance of Common Lisp for quite some time.
: >It has prevented me from using Common Lisp for any projects,
: And here I thought it was because all lisps are interpreted that
: the language has been withering on the vine for lo these many years.
Oh no -- this simply isn't true. Everyone knows the real reason
lisp isn't used is that all variables are dynamically scoped.
--
Brent Ellingson (········@badlands.NoDak.edu)
"It is amazing how complete is the delusion that beauty is goodness."
-- Leo Tolstoy
Brent A Ellingson wrote in message <············@node2.nodak.edu>...
>Paul Wallich (··@panix.com) wrote:
>: In article <··············@orion.dent.isdn.cs.tu-berlin.de>, ····@acm.org
>: (Pierre R. Mai) wrote:
>: >Yes, this is a most grave problem with Common Lisp indeed, which has
>: >really hindered the acceptance of Common Lisp for quite some time.
>: >It has prevented me from using Common Lisp for any projects,
>
>: And here I thought it was because all lisps are interpreted that
>: the language has been withering on the vine for lo these many years.
>
>Oh no -- this simply isn't true. Everyone knows the real reason
>lisp isn't used is that all variables are dynamically scoped.
NO! It's because all garbage collected systems are SLOOOOOWWWW!!!!
Oh yeah, except Java's...
* Pierre R Mai wrote:
> But there is hope on the horizon: Are you going to push for the
> introduction of 3-element conses to Common Lisp in NCITS/J13?
But we already have 1-lisps and 2-lisps, I think three is several too
many. Binary trees are just an efficiency hack in any case, Real Men
Use Lists for all that stuff.
--tim
In article <···············@tfeb.org>,
Tim Bradshaw <···@tfeb.org> wrote:
> ···@jaguNET.com (Bob) writes:
>
> > Does anyone have any sample code for constructing a simple binary tree
> > using lisp?
(cons (cons 10 20) (cons 30 40)
results in a binary tree whose left branch contains a binary tree
whose left branch = 10 and right branch = 20, etc.
>
> Binary trees are unfortunately not possible in Lisp because conses
> only have two elements, and you need three (left, right, value) to
> implement most kinds of binary tree. This is why Lisp is so slow and
> C++ is so fast. Your best approach is to implement a version of Lisp
> which has 3-element cons cells, this is what most people do.
>
I have to assume Tim's response is a joke (I hope so). In case it
confuses anyone, I want to respond seriously.
All lists are stored in lisp as binary trees, in fact the binary tree
is the most primitive data structure in lisp. The cons cell is the node.
Because of this, most good lisp systems can usually perform binary
tree manipulations much faster than you could do them in C/C++.
As well, most of the functions for manipulating them, including input and
output functions, are built in as language operators. One of the reasons
performance is so good in lisp is that allocation of a node is done
with CONS, and the garbage collector is used to free nodes. In C/C++,
even if you write your own allocators, you probably cannot get better
performance for allocation/deallocation than a fast lisp system
provides.
When I need to implement binary trees in C/C++, I write an embedded lisp
system (or at least part of one) to manage them efficiently.
Roger Corman
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
·····@corman.net wrote:
>
> In article <···············@tfeb.org>,
> Tim Bradshaw <···@tfeb.org> wrote:
> > Binary trees are unfortunately not possible in Lisp because conses
> > only have two elements, and you need three (left, right, value) to
> > implement most kinds of binary tree. This is why Lisp is so slow and
> > C++ is so fast. Your best approach is to implement a version of Lisp
> > which has 3-element cons cells, this is what most people do.
>
> ... One of the reasons
> performance is so good in lisp is that allocation of a node is done
> with CONS, and the garbage collector is used to free nodes. In C/C++,
> even if you write your own allocators, you probably cannot get better
> performance for allocation/deallocation than a fast lisp system
> provides.
But everybody knows the real reason you can't do anything real with lisp
that storage is so inefficient. After all, a list represented as cons
cells requires two memory words per element in most implementations.
For that reason, I will be proposing to J13 that the CAR attribute of
the CONS cell be deprecated, then eliminated. Not only will this reduce
storage requirements for typical applications by nearly one half, it will
also eliminate the need for many of the accessor functions CAR, CADR,
etc., their SETFs, RPLACA, and a whole mess of other ancillary operators.
The full proposal is nearly ready, except I'm stuck on a truly elegant
way to recast MAPCAR as MAPCDR.
Stay tuned for developments.
Maybe tim's suggestion from a few months ago could help here.
He suggested to replace all cons cells with vectors, which are indeed
simplier and faster than all this cons'ing overhead.
you get rid of the obvious inherent problems in lisp, the recursive
definition of lists. the performance and stack-exhausting problems with
such recursive list handling will be overcome.
not to talk about the complexity of recursion. this is not readable and
understandable anymore by the everday programmer, and programmers only
want to do their jobs right, right? there's no need to talk philosophy
and praise the LAMBDA god.
VECTORS could also be more efficiently garbage collected, because it
doesn't lead to that much fragmentation and granulation as the one-cell
mess with conses. VM systems as Win32 could be tuned by at least factor
two by using vectors instead of conses internally.
vectors also should be strongly typed. this would finally enable the
elimination of this memory wasting type tag in every memory cell. why
carrying along a type indicator in every single variable when the
compiler is clever enough to know what kind of type every variable is?
just look at C++ and the clever vtable trick. this is all what is needed
for run-time type information.
so instead of just depricating CAR the simple VECTOR functions should
replace CAR, CDR and CONS. wasn't it fortran, the mother of all
high-level languages? fortran IS efficient. you know why.
"Steven M. Haflich" <···@franz.com> wrote:
>But everybody knows the real reason you can't do anything real with lisp
>that storage is so inefficient. After all, a list represented as cons
>cells requires two memory words per element in most implementations.
>
>For that reason, I will be proposing to J13 that the CAR attribute of
>the CONS cell be deprecated, then eliminated. Not only will this reduce
>storage requirements for typical applications by nearly one half, it will
>also eliminate the need for many of the accessor functions CAR, CADR,
>etc., their SETFs, RPLACA, and a whole mess of other ancillary operators.
>The full proposal is nearly ready, except I'm stuck on a truly elegant
>way to recast MAPCAR as MAPCDR.
>
>Stay tuned for developments.
---
Reini Urban
http://xarch.tu-graz.ac.at/autocad/news/faq/autolisp.html
"Steven M. Haflich" <···@franz.com> writes:
> But everybody knows the real reason you can't do anything real with lisp
> that storage is so inefficient. After all, a list represented as cons
> cells requires two memory words per element in most implementations.
>
> For that reason, I will be proposing to J13 that the CAR attribute of
> the CONS cell be deprecated, then eliminated. Not only will this reduce
> storage requirements for typical applications by nearly one half, it will
> also eliminate the need for many of the accessor functions CAR, CADR,
> etc., their SETFs, RPLACA, and a whole mess of other ancillary operators.
No, No, No! I thought we had agreed to propose the idea where the CAR and
CDR get encoded into the same slot using an XOR. We really can't afford
to make such an incompatible change; those of us who don't need CARs
would never hear the end of it from those who do.
> The full proposal is nearly ready, except I'm stuck on a truly elegant
> way to recast MAPCAR as MAPCDR.
But that becomes easy with the XOR approach; in fact, a whole compatibility
package could be put together for those who don't want to lose CAR, CADR,
MAPCAR, etc., whose functionalities simply wrap their CDR counterparts
with an extra XOR to extract the CARs.
Sorry for posting this answer 9 days too late.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
In article <·················@franz.com>,
"Steven M. Haflich" <···@franz.com> wrote:
(...)
> For that reason, I will be proposing to J13 that the CAR attribute of
> the CONS cell be deprecated, then eliminated. Not only will this reduce
> storage requirements for typical applications by nearly one half
(...)
Me too!
And after your proposal is passed I am going to propose that
cdr-coding becomes mandatory for every conforming implementation
(and for the non-conforming too), and that an error is signalled
if a non-cdr-coded cons is passed to any of the cons manipulating
functions that remain. Thus we do away with most of the other
half as well.
Now, as to the other proposal of xoring the car and the cdr, I
*disagree*. You don't have a basis with xor only. On the other
hand, if you replace xor by nand, it would be a completely
different matter, and fully acceptable.
I also say sometimes that the good computer is the switched-off
computer.
On the 359th day before the calends of April, i.e. that many
days too early, not 9 days too late...
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
This has become a very funny thread--for experienced lispers.
I only hope some people don't take it seriously.
As for my (serious) comments about binary trees, I understand
the issue people have wanting to store a data item and two
branches at a node. A binary tree which only has data at leaves,
not at branches, can get by with two slots per node. This is
to me the classic binary tree. If you want nodes to hold three
things (data plus 2 branches) I would think of this as a
ternary (is that the right word?) tree i.e. to binary as
three is to two. In college I was taught that all trees of any
degree could be easily converted to a binary tree.
To use cons cells, you have to put two cons cells at each branch
such that each branch looks like this:
(data left-branch . right-branch)
Roger Corman
---------------
"Steven M. Haflich" wrote:
>
> ·····@corman.net wrote:
> >
> > In article <···············@tfeb.org>,
> > Tim Bradshaw <···@tfeb.org> wrote:
> > > Binary trees are unfortunately not possible in Lisp because conses
> > > only have two elements, and you need three (left, right, value) to
> > > implement most kinds of binary tree. This is why Lisp is so slow and
> > > C++ is so fast. Your best approach is to implement a version of Lisp
> > > which has 3-element cons cells, this is what most people do.
> >
> > ... One of the reasons
> > performance is so good in lisp is that allocation of a node is done
> > with CONS, and the garbage collector is used to free nodes. In C/C++,
> > even if you write your own allocators, you probably cannot get better
> > performance for allocation/deallocation than a fast lisp system
> > provides.
>
> But everybody knows the real reason you can't do anything real with lisp
> that storage is so inefficient. After all, a list represented as cons
> cells requires two memory words per element in most implementations.
>
> For that reason, I will be proposing to J13 that the CAR attribute of
> the CONS cell be deprecated, then eliminated. Not only will this reduce
> storage requirements for typical applications by nearly one half, it will
> also eliminate the need for many of the accessor functions CAR, CADR,
> etc., their SETFs, RPLACA, and a whole mess of other ancillary operators.
> The full proposal is nearly ready, except I'm stuck on a truly elegant
> way to recast MAPCAR as MAPCDR.
>
> Stay tuned for developments.
Hold on... it seems clear to me that you are missing the point, which is
the real source of the severe overhead associated with a cons cell, all
of which can be attributed to garbage collection schemes. If LISP had
built-in (malloc ..) and (free ..) operations, then not only would
confusion about the "recursive heap sorting progressive mind-controlling
garbage collector" be eliminated, but you could reduce the cons overhead
dramatically. LISP programs would also be more portable to operating
systems that do not include the garbage collector, but do support
malloc() and free() in their standard C library.
CU
Dobes
·····@corman.net writes:
> In article <···············@tfeb.org>,
> Tim Bradshaw <···@tfeb.org> wrote:
> > ···@jaguNET.com (Bob) writes:
> >
> > > Does anyone have any sample code for constructing a simple binary tree
> > > using lisp?
> (cons (cons 10 20) (cons 30 40)
> results in a binary tree whose left branch contains a binary tree
> whose left branch = 10 and right branch = 20, etc.
> >
> > Binary trees are unfortunately not possible in Lisp because conses
> > only have two elements, and you need three (left, right, value) to
> > implement most kinds of binary tree. This is why Lisp is so slow and
> > C++ is so fast. Your best approach is to implement a version of Lisp
> > which has 3-element cons cells, this is what most people do.
> >
> I have to assume Tim's response is a joke (I hope so). In case it
> confuses anyone, I want to respond seriously.
>
> All lists are stored in lisp as binary trees, in fact the binary tree
> is the most primitive data structure in lisp. The cons cell is the
> node.
if binary trees are made of cons cells, what do you call those trees
that employ something like
(defstruct node (datum left right))
where every node has data and not just the leaves? you know the kind
you'd use to convert infix to prefix and employ in binary searches.
i am just looking for the proper terminology here.
--
johan kullstam