!Concurrent GC

We briefly discussed David's three line mark-and-sweep solution.

def start(x) = x.write() >> each(Succ(x)) >y> start(y)
def finish(y) = x.read() >> x.clear() ; Free(x)
def gc() = each(roots) >r> start(r) ; each(nodes) >n> finish(n) >> stop ; signal

Nodes with written cells are black, unwritten are white. This is a simplified version of the actual algorithm. The 
real algorithm also requires that the mutator not allow edges from black (reachable) nodes to white (unreachable) 

Jay would prefer not to allow the .clear (reset) method on cells. Here is an alternate version without
the reset:

def start(x) = atomic(if(x.read()) >> x.write(false)) >> each(Succ(x)) >y> start(y)
def finish(y) = if(x.read()) then Free(x) else x.write(true)
def gc() = each(roots) >r> start(r) ; each(nodes) >n> finish(n) >> stop ; signal

The atomic section is not necessary for correctness, but a race between the read and the write may result in
repeated work, as another thread starts a node that may be about to be colored black. Assuming that the scheduling
is fair, the algorithm will still terminate without atomic.


A region encloses an expression, giving it some sort of implicit dynamic object. A simulation region
has a logical timer, an atomic region has a transaction, etc. Given an expression e, (region e) is also
an expression; this means that regions can be nested to any depth.

Within a region, there are usually operations that observe or change the current dynamic object. While
we could add these specifically as new syntax, it seems easier to add them as sites which operate on
the most enclosing region.

!Real Time Regions

The simplest region to consider is a real-time region. Since real time advances simultaneously in
any part of a program, a real-time region simply sets a new zero point; the region's object is a relative
timer, which starts at 0, and advances at the same rate as any other real timer.

A real-time region has two operations. Rtimer(t) waits for t units of time. Rclock() returns the amount
of time that has passed since this real-time region began to execute.

As a simple test of real timers, Jay proposes implementing a clock synchronization algorithm.

!Logical Time Regions

In addition to real-time regions, there are also logical time regions, which we have been writing as
(sim e). The dynamic object of such a region is a new logical timer.

A logical time region also has two operations. Ltimer(t) waits for t units of logical time. Lclock() returns
the amount of logical time that has passed since this logical time region began to execute.
Jay has proposed three axions for logical time:
Common ("immediate") operations (add, multiply, etc) do not advance the logical timer. All other calls (uncommon/"non-immediate" operations) take an unknown amount of logical time.
Logical time is non-decreasing.
The logical timer eventually advances. 
 In order to satisfy property #3, we must require two properties of the execution:

All immediate operations eventually return a value or halt.
It is not possible to do an infinite amount of computation in zero logical time.

!Nested Logical Timers

Since regions can be nested, a new logical time region may be executed within the context of another logical timer.
What happens?

Our consensus for now is that the execution of the nested region takes zero logical time in the timeline of the parent region.
The question we still have to answer is: what happens when a site interacts with two different logical time regions?