Subject: Re: Lisp and trees
From: Erik Naggum <>
Date: Thu, 22 Nov 2001 03:47:39 GMT
Newsgroups: comp.lang.lisp
Message-ID: <>

* Jeff Sandys
| Lisp *IS* a binary tree.  It's basic memory structure is a  cons cell of
| two pointers (car and cdr) to other cons cells.

* Erik Naggum
> What utter nonsense.  

* Jeff Sandys
| Erik, when you use this expression you imply to me that you believe  that
| the above statement is absolutely untrue.

  When you decide to highlight "is" that way, it means that Lisp can be
  nothing else and that something else cannot be Lisp.   _That_ is the
  utter nonsense.  If someone says "all X are Y", and somebody denies this,
  they are _not_ saying "no X is Y" (or "all X are not Y"), and they are
  _not_ denying that "some X are Y", but some people react as if they were
  entitled to say "all" because their evidence suggests "some", and hence
  go nuts because they think you contradict their evidence that "some" is
  true.  Elementary logic is not as optional as some people think it is.
> First, a binary tree has two pointers and at least one value.

| A binary tree is a structure of nodes, each with two, and only two
| branches.  Each branch connects to another node or terminates at a leaf
| (value).

  You carefully avoid mentioning what other information a node must have to
  be useful.  Not to beat you over the head with either Knuth or Leiserson,
  et al, this is what Winston & Horn has to say about binary trees:

        A _binary tree_ can be defined recursively either as a leaf, or as
        a node with two attached binary trees.  Such a binary tree can be
        represented using atoms for the leaves and three-element lists for
        the nodes.  The first element of each list is an atom representing
        a node, and the other two elements are the subtrees attached to the

  Abelseon, et al, agree with this representation.  This is quite different
  from a simple cons cell.  Usually, a binary tree also includes a parent.

> Third, there is no particular memory structure that merits "basic" in
> Common Lisp.

| Except that the heritage of Lisp [...]

  "Heritage" and "basic" are not even related concepts.  Why bring it up?

| And Erik, you have challenged me to unlearn Lisp 1.5, throw out Winston
| and Horn, and forget that I ever learned Scheme.

  What utter nonsense.  If what you got out of thse good books is that
  bunch of utter nonsense, you should simply re-read them.  Pull yourself
  together and just accept that you were mistaken.  The only useful thing
  you can about having been wrong is to figure out what is right.
  Defending what is clearly wrong is counter-productive.  Defending
  yourself because you were wrong about something is just plain stupid.

  Norway is now run by a priest from the fundamentalist Christian People's
  Party, the fifth largest party representing one eighth of the electorate.
  Carrying a Swiss Army pocket knife in Oslo, Norway, is a criminal offense.