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.
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
.
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.
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.
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.
{- Shortest path through a directed graph, using a virtual clock -} 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] -}
Related Reference Topics
Related Tutorial Sections