Virtual Time#

Previously called LogicalTime. (See that article for historic notes.)

A proposed replacement: the onidle combinator.

From the Orc Reference Manual:

Virtual time provides the ability to order events in an Orc execution. As an expression is executed, the Orc runtime tracks the "current" virtual time. A Vawait site call waits for a particular point in time. Through use of Vawait, one can set up temporal dependencies among Orc expressions.

Simulations in Orc can make use of virtual time to simulate time passage without the unproductive delays caused by real time waits. Certain algorithms can be succinctly expressed using virtual time. (See the shortest path example.)

An Orc virtual clock is created with four parameters, conceptually:

  • A set of points of time (for example, the integers)
  • Equality and total ordering relations over this set (for example, = and <)
  • Optionally, a parent clock
  • The scope (part of the program) over which it applies

(In an actual Orc program, only the total ordering relation is given as an actual argument to a Vclock call. The other parameters are implicit.)

During execution. a virtual clock tracks:

  • The current time
  • A priority queue of pending Vawait calls, in order of their awaited time, as given by the clock's total ordering relation.

When Vawait is called with a time value greater than the current time, that call is enqueued, and does not return until that time. Virtual time advances when all execution in the clock's scope becomes quiescent, defined below. Upon quiescence in a clock's scope, the clock's current time is updated to the least time among its waiters, and all Vawait calls for that time return.

Quiescence#

An expression is quiescent when all execution in the expression is either blocked on variables, blocked on certain site calls, halted, or killed. In other words, quiescence means no progress can be made in the expression without certain kinds of unblocking. Most site calls are not considered quiescent while they are invoked, however a few are; most notably Vawait when it is called with a future time value argument. Other not-quiescent-while-invoked sites are documented in their entry in the Standard Library chapter. Child virtual clocks are not quiescent until all execution in their scope has halted. So, a child clock whose scope is quiescent but not halted is non-quiescent from the viewpoint of the parent clock.

Note that expressions blocked on variables are quiescent. This normally is the intuitive behavior: for example, x <x< Q() is quiescent if the call to Q is. However, if the right side of a pruning combinator is not in the clock's scope, then blocking on a variable bound by the pruning combinator will be quiescent. This might be surprising: Suppose val x = F is followed by Vclock(IntegerTimeOrder) >> x. The virtual clock scope x will be quiescent if executed before F has published and x has a bound value. To avoid this, use the Orc join idiom. Before calling Vclock, join all potentially-unbound variables used inside the clock scope, like so: (x, y, z) >> Vclock(IntegerTimeOrder) >> x + y + z.

Vclock#

Executing Vclock(timeComparator) >> e executes the expression e with a virtual clock that has time values ordered by timeComparator. A time comparator operates on a particular time value type, for example integers. A time comparator is a site that takes two arguments, each of the time value type, and returns the value -1, 0, or 1 to indicate the first argument is less than, equal to, or greater than, respectively, the second argument. Note that in the current version of Orc, the site must be a Java site; it cannot be defined in Orc. (This limitation may be removed in a future Orc release.) The time value type of a clock is implicitly defined by the type of arguments that the given time comparator site accepts. The initial value of a virtual clock is established by the first Vawait call in the clock's scope that publishes.

The scope over which a virtual clock is effective is the right side of the pruning combinator in Vclock(timeComparator) >> e. A Vclock call can only be used on the left side of a sequential combinator; use in any other context will be marked by the compiler as an error. When the expression e publishes, the publication, as usual, is a publication of the sequential combinator expression. If the Vclock call is in the scope of another virtual clock, that clock is considered the parent clock of this clock.

Vawait#

Executing Vawait(t) waits quiescently until the the current (innermost) virtual clock advances to time t. There may be more than one Vawait call awaiting a given time value. All such calls will publish at the same time. Exactly one call, selected arbitrarily, will publish true, and the others (if any) will publish false. If Vawait(t) is called when the current virtual time is already t, the call immediately publishes false, without becoming quiescent. If the current virtual time is greater than t, the call halts silently. If the current virtual clock does not have defined time—that is, Vawait has not been called yet in the scope of this clock—then the Vawait behaves as if its argument is a future time value. If Vawait is called outside of the scope of any virtual clock, the call halts silently.

Vtime#

The Vtime site publishes the current value of the current (innermost) virtual clock. If the clock has not had a value set by a Vawait call, or Vtime is calls outside of the scope of any virtual clock, Vtime halts silently.

Example#

def Vwait(t :: Integer) = Vawait(t + (Vtime() :!: Integer))

Vclock(IntegerTimeOrder) >> Vawait(0) >> (
type Node = Integer
type Distance = Integer

def path(source :: Node,
     sink :: Node,
     cell :: lambda(Node) :: Cell[List[Node]],
     succ :: lambda(Node) :: (Node,Distance)
     ) :: List[Node] =
  def run(n :: Node, p :: List[Node]) :: Bot =
    cell(n).write(p) >>
    succ(n) >(m,d)>
    Vwait(d) >>
    run(m,m:p)
  run(source, [source])
  ; reverse(cell(sink).read())

-- A small test graph
val source = 0
val sink = 3

def mkcell() = Cell[List[Node]]()

val cell0 = mkcell()
val cell1 = mkcell()
val cell2 = mkcell()
val cell3 = mkcell()

def cell(Node) :: Cell[List[Node]]
def cell(0) = cell0
def cell(1) = cell1
def cell(2) = cell2
def cell(3) = cell3

def succ(Node) :: (Node,Distance)
def succ(0) = (1,2) | (2,6) | (3,9)
def succ(1) = (3,7)
def succ(2) = (3,2)
def succ(3) = stop

path(source, sink, cell, succ)
)

{-
OUTPUT:
[0, 2, 3]
-}

Add new attachment

Only authorized users are allowed to upload new attachments.
« This page (revision-2) was last changed on 04-Jul-2016 19:53 by John Thywissen