!!! Virtual Time

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

A proposed replacement: the [onidle] combinator.

[From the Orc Reference Manual|https://orc.csres.utexas.edu/documentation/html/refmanual/ref.time.virtual.html]:

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(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)

[0, 2, 3]