On Fri, Apr 16, 2021 at 03:13:10PM -0500, polifemo wrote:
> OH! I think I'm getting it!
> for example, 'simul is '(\~ ("permute" ("shuffle" ("flood" ("G" NIL "gen"
> ...
> Something that confused me was that first symbol, '\~. It is not a valid
> picolisp symbol!
Correct. The special symbol \~ is new in pil21 and is only used as a marker
(e.g. for error checks). It is not absolutely necessary, and did not exist in
pil64.
> But now that I see that a namespace is a cons of a "short
> name namespace" and a "long name namespace", no symbol from either
> namespace would be a reasonable root for the tree. So that arbitrary symbol
> (\~) was chosen as the root. The cadr of 'simul are the short names, and
> there is no caddr because there are no long names!
Yes, though not the caddr but the cddr.
In summary, a namespace consists of 2 cells:
+------+-----+ +-------+-------+
| \~ | ---+---->| short | long |
+------+-----+ +-------+-------+
# Create empty namespace
: (symbols 'ap 'pico)
-> (pico)
ap: ap
-> (\~ NIL)
# Two cells
+------+-----+ +-----+-----+
| \~ | ---+---->| / | / |
+------+-----+ +-----+-----+
ap: (local) (abc def ghijklmo pqrstuvw)
ap: ap
-> (\~ (abc NIL def) ghijklmo NIL pqrstuvw)
ap: (car ap)
-> \~
ap: (cadr ap)
-> (abc NIL def)
$ap: (cddr ap)
-> (ghijklmo NIL pqrstuvw)
ap: (all 'ap)
-> (abc def ghijklmo pqrstuvw)
> One of the things that confused me was the way trees are represented. For
> example, given this tree:
>
> 9
> 8
> 7
> 6
> 5
> 4
> 3
> 2
> 1
>
> I would have represented it as a nested list in this way:
> (5 (2 (1 NIL NIL) (3 NIL (4 NIL NIL))) (7 (6 NIL NIL) (8 NIL (9 NIL NIL))))
> That is, each new branch is inside its own list. Intuitive, but quite
> wasteful, given that conses are memory in picolisp.
>
> But the picolisp way is:
> (5 (2 (1) 3 NIL 4) 7 (6) 8 NIL 9)
> this is hard for me to describe, but something like...
> Every second element is the left branch of the element before it, and every
> third element is the right branch of the element two places back.
If we look at it this way, it is very simple:
1. A tree node consists of either one or two cells. Leaf nodes need only one
cell.
2. The first cell of a node has the payload (value) in its CAR, and the
subtrees (or NIL for leaf nodes) in its CDR.
3. The second cell of a node holds the subtrees. The left one in the CAR and
the right one in the CDR.
As leaf nodes need only one cell, and half of the nodes in a (balanced) tree are
leaf nodes, such a tree occupies one and a half cells per node on the average.
☺/ A!ex
--
UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
