[{TableOfContents}]

!!! Traces

Preliminaries:

* An Orc computation consists of sequences of ''events'' occurring in logical ''threads''.
* Threads form a tree, where each thread is connected to the thread which spawned it.


The following minimal events must be traced to deterministically replay a computation (assuming the scheduler is deterministic):

;root:The root of the thread tree.
;fork:A fork event. By convention, the "left" branch of the fork (as dictated by the syntax) is evaluated by the same thread, while the right branch is evaluated by a new thread.
;receive:A site call returning. The order in which site calls return (and the values they return) is the primary source of non-determinism in Orc computations.
;die:A token halting. If this occurs during a site call it must be recorded to distinguish halting from never returning.
;error:A token encountering an error (always followed by {{die}}). If this occurs during a site call it must be recorded to distinguish halting with an error from never returning.

A trace is a DAG of events:

* Edges are only allowed to point "back" in time, i.e. from an event to one which preceded it in time.
* Each non-{{root}} event has a logical {{parent}} edge which points to its immediate predecessor in time in the same or parent logical thread.
* The {{fork}} event is the only event which may have more than one incoming {{parent}} edge.
* Each non-{{root}} event has a {{thread}} edge pointing to the closest {{parent}} ancestor {{fork}} or {{root}} event. This serves as the thread identifier for events in the same logical thread.
* Each {{receive}} event has a logical {{after}} edge pointing to the {{receive}} event which preceded it in time. This serves to encode ''possible'' causal relationships between site calls in different threads; since we don't have any knowledge of site internals, we have to assume that all temporal relationships may reflect causal relationships.

A trace file contains a sequence of serialized events from the same trace.

Events are serialized into the trace file in the order in which they occur in time.  {{after}} and {{parent}} edges are represented implicitly by the serialization order; all other edges are explicitly represented by references to already-serialized events.

!!! Other Events

Pruning combinator:
;pull:Create a new future (always followed by {{fork}}).
;block:Block waiting for a future to receive a value (always followed by {{unblock}} or {{die}}). Has an edge to the corresponding {{pull}}.
;store:Store a value to a future.  Has an edge to the corresponding {{pull}}.
;unblock:Receive a value from a future.  Has an edge to the corresponding {{store}}.
;choke:Halt due to a value being stored to a future (always followed by {{die}}).  Has an edge to the corresponding {{store}}.
;useStored:Use a value already stored. Has an edge to the corresponding {{store}}.

Otherwise combinator: TODO

Closures:
;enter:Enter the scope of a closure. Helpful to track the environment of a thread.
;leave:Leave the scope of one or more closures. Helpful to track the environment of a thread.

External events:
;publish:Publish a value from the top-level Orc expression (always followed by {{die}}).
;print:Print to stdout.

!!! User Interface

The debugger will be text-based, for rapid development. The concepts should be straightforward to extend to a graphical debugger.


* The interface will consist of a thread list followed by a command prompt.
* The thread list will display a "primary" thread together with zero or more "secondary" threads, each with a unique number.
* The command prompt will be used to enter commands such as:
** select a primary thread
** hide a thread
** hide all secondary threads
** step forwards or backwards one event in the primary thread
** display contextual information about the primary thread's current event
** search for an event
* Each thread in the thread list will include the following information:
** The source location and line of code which includes the start of the expression the thread is evaluating
** The expression the thread is evaluating, elided if necessary to fit on a single line
** The state of the thread (blocked, running, or terminated)
* The primary thread will also display several lines of source code around the current expression, for context.
* Stepping involves simulating events from the primary event stream until the next (or previous) event for the primary thread is reached. Note that these events may include events in other threads, although such events will never change the primary thread directly.
* When any thread in the thread list forks, the new thread is appended to the thread list as a secondary thread.
* When any thread in the thread list terminates, it is removed from the thread list after the next forward step command.
* When stepping backwards past the point a secondary thread was created, it is removed from the thread list.
* When stepping backwards past the point the primary thread was created, it is replaced by the creating thread.
* Contextual information for the current event (accessible via the command line) includes:
** The value of any bound variable
** For any unbound variable (future), the event which originated the future
** For a blocked thread, the event which originated the future
** For a terminated thread, the event which terminated it
* To search for an event, the user enters a query and is presented with a list of matching events. The user chooses one and it is selected as the primary thread. This feature will almost certainly require indices in the trace file for efficient operation.

!! Resources and Related Work

The "Ford" module in CVS contains a working Prolog-like query language for traces and a not-really-working
textual replay debugger: http://code.google.com/p/orc/source/browse/#svn/trunk/Ford

OPIUM partly inspired the query language for navigating through traces: http://www.inria.fr/rrrt/rr-3257.html

The query language is also heavily based on linear temporal logic: http://en.wikipedia.org/wiki/Temporal_logic

The Omniscient Debugger is a good inspiration for UI, but isn't designed to deal with large numbers of
concurrent threads: http://www.lambdacs.com/debugger/

Hat (the Haskell Tracer) is Haskell's solution to the debugging problem. Haskell's lazy evaluation -- much like
Orc's concurrent evaluation -- means that terms are not evaluated in a predictable order, so to understand a
program's evaluation it's necessary to navigate directly from effects to causes.  Hat's user interface is not
optimal, but if you're not sure where to start, just creating an Orc clone of the Hat tool suite would be a good
goal for your project: http://www.haskell.org/hat/