9I. lisp-cells and cell functions
---------------------------------
yep. that's right. you thought LISP was fun, then try E now.
[or: the story about why E is a better LISP than LISP itself :-)]

Starting from v3, E has the cell datatype, almost identical to cells
in the LISP language. more technically, E has:

`Conservative Mark and Sweep Garbage-Collected Lisp-Cells'

basically this amounts to being able to allocate LISP-cells,
which are pairs of two values:

	x:=<a|b>

which is much like NEW [a,b]:LONG, only now E will automatically
deallocate the 8 bytes in question itself when it finds out it needs
memory and no pointers are pointing to the cell. In practise this
means that you can freely have functions create cells as temporaries,
without worrying about freeing them. And any LISP-programmer will
be able to explain to you that with cells you can build any
data-structure (most notably trees and lists). [note: this text
does not thorougly explain how to make full use of cells, since
dozens of LISP books have been written about this]

Selecting the values can easily be done using Car(x) and Cdr(x),
two LISP-functions which select head and tail (first and second)
element of the cell. if x is a PTR TO LONG, even x[0] and x[1]
are allowed.

One can also write lists of cells:

	<a,b,c>

(note the commas) as short for

	<a|<b|<c|NIL>>>

An alternative for selection with Car/Cdr is E's unification:

	x <=> <a,b|c>
	a+b+c

instead of:

	Car(x)+Car(Cdr(x))+Cdr(Cdr(x))

lisp-cell unification resembles E-list unification (see  4L ). for
example:

	x <=> <1,2|a>

equals:

	IF Car(x)=1
          IF Car(Cdr(x))=2
            a:=Cdr(Cdr(x))
            ...


A lisp-nil value is available "<>", which equals "NIL" and "0", but not
"[]".

some functions are available (note that Cons() is _only_ available
through <...>)

	h:=Car(c)	t:=Cdr(c)

get the head and the tail value of a cell c

	bool:=Cell(c)

gives a bool for whether or not c points at a cell, so Cell(<1>)=TRUE,
and Cell(3.14)=FALSE. This is not a fast function.

	n:=FreeCells()

tell you about the amount of free cells available. very slow function.
there should be no need to call this function other than curiosity.

	SetChunkSize(k)

Sets the chunksize to allocate for cells to k kilobyte. default is 128k.
This function can only be called once, and only before the first cons
(<..>) allocation takes place. Thereafter it has no effect.

In general, get a good book about lisp to understand more about
programming with cells.

One can write any LISP-functions in E, with exactly the same functionality:

PROC append(x,y) IS IF x THEN <Car(x)|append(Cdr(x),y)> ELSE y
PROC nrev(x) IS IF x THEN append(nrev(Cdr(x)),<Car(x)>) ELSE NIL
PROC sum(x) IS IF x THEN Car(x)+sum(Cdr(x)) ELSE 0

using a destructive implementation for functions like these is
also allowed.

techy stuff:
E's garbage collector implements a conservative mark and sweep algorithm
that was tested to be 5 to 25 times faster than several logical and
functional language implementations on the Amiga. Conservative
means that in case of doubt, the GC will not deallocate a cell. this
is necessary since in a typeless language such as E, the GC can
easily bump into a value that is not a valid pointer etc.

The GC allocates big chunks (default 128k), in which it allocates
cells. if out of cells, it will collect garbage by scanning the
stack and registers for pointers into the cellspace, and recursively
mark them. after that, all unmarked cells are reused, and if the
gain after a collection was only small, a new chunk is allocated
(if this fails, "NEW" is raised).

interaction with other E values:
- storing other values in cells is no problem whatsoever. objects,
  strings, floats, anything can be put into a cell without confusing
  the GC too much.
- storing cells in other values, for example a ptr to a cell in a
  dynamic object, is problematic, since the GC won't be able to find
  it there. a solution for this will be provided. However I think this
  case will seldom occur.
  ptrs to cells can safely be stored in global and local variables,
  even registers, and any stack datastructures.
  [and most importantly, in other cells!]

caveats:
- The GC currently can't collect cells that have a Car-list >1000
  long or so, i.e. <<<NIL:a>:b>:c>, but then 1000 instead of 3
  entries. this will hardly ever occur since lists like this
  are usually formed as Cdr-lists, which the GC can handle into
  infinity. (it will raise "STCK" if this fails")
- inline assembly code should never push stuff on the stack that
  is not LONG aligned. this was already necessary in v2.1b,
  but now is even more essential.

There's a trade off in chunk-size between time and space.
Allocating small chunks obviously is nice since you won't waste
any memory, however, when collecting garbage, the effort for
each pointer to trace is almost proportional to the number of
spaces. therefore:
- if speed is most important tune the chunkspacesize such that
  that only one space is needed. if the top cell-memory usage at a
  certain time is 50k, a chunkspace of 100k or 150k will give
  optimal performance.
- if memory usage is more important, in the example above a
  chunksize of 20k or 30k will be quite optimal for memory.
In general, time a heavy usage of your cell-algorithm with
different sizes to see what trade-off suits you best.