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/

Add new attachment

Only authorized users are allowed to upload new attachments.
« This page (revision-2) was last changed on 22-Feb-2009 13:23 by AdrianQuark