# Lispy cons

This unit implements cons as used in Lisp. This concept is mostly used in
[comp/lisp] but can be quite useful in other situations. It is notably used for
ASTs in [comp/c] and [comp/oberon] and as a way to describe ACPI's namespace in
[emul/aml].

The idea is that we have garbage collected pairs of values (called "car" and
"cdr"). Each element of those pairs can reference another cons. We have a memory
pool of a static size allocated to hold these cons and when we run out of space
to create a new cons, we free unreferenced cons to create some space. If we
can't free any space, we're out of memory.

## Designed for short term

The GC that this unit implements is small and low-tech and can stay that way
because it manages a relatively small number of cons (the CONSCNT constant).

This pool is designed for temporary values that aren't held onto for too long.
If you need to hold onto a cons, leak it (see below) in order to relieve
pressure onto the GCed pool.

## Top level references

To perform garbage collection, one has to keep track of the cons reference. We
have 3 possible sources of references:

1. Parameter stack
2. Return stack
3. "consref"

The underlying idea is that we have this pool of a specific size and at a
specific address. If any number in PS or RS corresponds to this range and is
divisible by 8 (pair of 32-bit numbers), we consider it a cons reference. Sure,
there can be false positives, but these will be rather rare and of little
consequence (we hold onto some memory longer than we should).

"consref" is the same as a regular value, except that they are iterable. The
garbage collector can go through all those values and add these to the garbage
collection "keep list".

## The keep list

Parallel to the cons pool is the keep list, which is 1/64th of its size. It's a
bit field that indicates which slots are used. When we want to create a new
cons, we check into this list for the first 0 we can find. That indicates where
our new cons will live.

We happily use slots as long as they exist. When we don't have space anymore,
we do garbage collection. That is, we set the whole keep list to 0, then we go
through all top level references and recursively mark elements in the list.

Once we've done that, if we still have no 0 left, we're really out of memory.

## Leaking cons

As written above, if you need to hold onto a cons (and the cons it points to),
you should leak it to permanent memory. The "leak" word copies the target cons
from the GCed pool to permanent memory and yields a pointer to that copied cons.
If the target value is not a cons or is not in the GC, "leak" is a noop.

The leaking of cons is done through an internal arena [mem/arena] rather than
directly through regular memory allocation. The goal of this is twofold. First,
arena allows us to check whether a given address is a cons, which is done
through "iscons?". If it's not a GC cons, then we check whether the specified
number is an address within any of the leak arena buffers.

Second, using an arena allows us to avoid corrupting compiled code in the same
way [comp/mem] does. A piece of compilation code that might need to leak cons
will want to call "ensureleakspace" first.

Note that leaking a cons that has references to it is problematic because those
references aren't updated. It doesn't break those references because the leaked
object will stay in the GC pool, but it will split the references. If a change
happens to cons on any side of the split, the other side will stay with the old
version of the data. Not only that, but leaked cons aren't checked in the GC
process, which means that referencing a GCed cons in a leaked cons will not hold
it "alive".

Therefore, it's usually a bad idea to leak a cons that is going to mutate.
Generally, you leak when you're done mutating it or you're sure you're not going
to mix it with GCed cons.

## Lists and pairs

There are of course a myriad of types of structures you can organize cons into,
but at the fundamental level, there are two types: lists and pairs.

A list is a cons where cdr is either 0 or another list (the check whether a
cons is a list is recursive).

A pair is a cons that is not a list. In terms of representation, we show lists
as "(1 2 3)" (a set of 4 cons) and a pair as "(1 . 2)". Can a construct
theoretically have something that could be represented as "(1 . 2 . 3)"? No.
That would be something that Lisp would create with "(cons 1 (cons 2 3))", so
it's "possible", but that would in fact be represented as "(1 . (2 . 3))".

The keen eyes among you will notice a bit of a problem with this representation:
pairs where the second element is 0 can't exists. "(cons 42 54)" is "(42 . 54)"
alright, but "(cons 42 0)" cannot be represented as "(42 . 0)", even if that is
its semantic significance. In representations, such pairs will show as "(42)".
In the code, this changes nothing because that "false list" can still be used
semantically as a pair (watch out for places where you use "islist?" though...),
but if you inspect your data, you might be surprised by this. But not if you
expect it after you've read that paragraph.

## Warning about dynamic structures

As shown in the paragraph above, relying on "islist?" outside of the printing
context will usually be a bad idea because of the semantic ambiguity of 0.

But you must also be careful about "iscons?"! That word only checks that the
supplied address is in the cons pool range. If you supply it with an arbitrary
literal, you *could* be unlucky and have it falsely yield true.

In [comp/lisp], we do use "iscons?" to process cons in a dynamic manner, but we
can do so because 100% of the input data is pointers (rawlists are cons of
strings). Pointer to non-cons are never in the cons pool. In this context, this
works. But once the rawlist is "cooked", arbitrary literals end up in the mix
and from then on, all processing on those cons must be done in "static" mode.
Lists can still have variable length, this works, but we can't have pairs where
lists are expected, this will break horribly when the wrong literal is in the
input.

## API

### Constants

CONSCNT  $1000. Number of cons in the GCed pool.

### Structures

struct Cons { uint car cdr ; }

car  First element of the cons
cdr  Second element of the cons

### Words

isgccons? ( a -- f ) *A*
  Yield whether address "a" is a GCed cons. This excludes leaked cons.

  This word is "memory safe", that is, it can safely be called with any "a"
  input value because that memory address is never accessed.

iscons? ( a -- f )
  Yield whether address "a" is a cons. This includes leaked cons.

  Like "isgccons?", this word is "memory safe".

iscons# ( a -- )
  Abort with error if "a" is not a cons.

islist? ( a -- f )
  Yields whether "a" is a list. If "a" is not a cons, yield 0 too.

cons ( car cdr -- cons )
  Find a free slot in the pool, mark it as used, set "car" and "cdr" as its
  values and yield the address of that new cons.

  If no free slot exist, launch the garbage collection mechanism. If there's
  still no free slot, abort with "out of memory".

carcdr ( cons -- car cdr )
cdrcar ( cons -- cdr car )
  Unwrap "cons" as a PS pair. Aborts if "cons" is not a cons.

?carcdr ( a -- car cdr 1 OR a 0 )
?cdrcar ( a -- cdr car 1 OR a 0 )
  Call "carcdr/cdrcar" only if "a" is a cons.

?single ( a -- x 1 OR a 0 )
  If "a" is not a cons *or* if it's a cons that contains a single element,
  unwrap that element as "x" and yield f=1. Otherwise, f=0.

single# ( a -- x )
  Unwrap "a" with "?single" and abort with error if that fails.

tail ( list -- cons-or-0 )
  Yield the tail element of the specified list, that is, the last cons where
  its "car" is the last value of the list and its cdr is 0.

  Yields 0 if "list" is empty.

append ( cons-or-0 car -- cons )
  Create a new cons with "car" and have "cons" link to it. Yield the newly
  created tail.

  If "cons" is 0, yield (car 0).

length ( list -- n )
  Yield the number of elements in a list.

leak ( a -- a )
  If "cons" is a GCed cons, copy it outside the cons pool, in the leak arena as
  described in "Leaking cons" above.

  Otherwise, this word is a noop. This includes leaked cons. This is an
  important caveat. This means that if, through mutation, you've ended up with
  a GCed cons underneath your leaked cons (this has to be a result of post-leak
  mutation), your leak will be incomplete.

  This word properly handles circular references, that is, it will not enter an
  infinite loop and the last reference of the circle will properly point to the
  leaked cons.

  The breaking of the circular loop is done by temporarily setting the cons
  that's about to be leaked with n"LEAK" in its car and a pointer to the leaked
  cons in cdr. When "leak" encounters a cons with a n"LEAK" car, it knows it has
  to stop and it yields the saved address. Once leaking is complete, the
  original cons' values are restored.

ensureleakspace ( -- )
  Call "ensurenext" [mem/arena] on the leak arena.

conscnt ( -- n )
  Yield the number of cons slots currently used in the pool.

.cons ( cons -- )
  Print "cons" contents, wrapping it in parens like a list, as long as "cdr" is
  a cons. If a cons is encountered as "car", we recursively begin the printing
  of a new cons.
