11.6. state: General-purpose supplemental data structures.

General-purpose supplemental data structures.

11.6.1. Some

site Some[A](A) :: Option[A]

An optional value which is available. This site may also be used in a pattern.

Example:

-- Publishes: (3, 4)
Some((3,4)) >s> (
    s >Some((x,y))> (x,y)
  | s >None()> signal
)

11.6.2. None

site None[A]() :: Option[A]

An optional value which is not available. This site may also be used in a pattern.

11.6.3. Cell

site Cell[A]() :: Cell[A]

Create a write-once storage location.

Example:

-- Publishes: 5 5
val c = Cell()
  c.write(5) >> c.read()
| Rwait(1) >> ( c.write(10) ; c.read() )

cell[A].read() :: A

IndefiniteIdempotent

Read a value from the cell. If the cell does not yet have a value, block until it receives one. If a call to read blocks, it becomes quiescent.

cell[A].readD() :: A

DefiniteIdempotent

Read a value from the cell. If the cell does not yet have a value, halt silently.

cell[A].write(A) :: Signal

DefiniteIdempotent

Write a value to the cell. If the cell already has a value, halt silently.

11.6.4. Ref

site Ref[A]() :: Ref[A]

Create a rewritable storage location without an initial value.

Example:

val r = Ref()
Rwait(1000) >> r := 5 >> stop
| Println(r?) >>
  r := 10 >>
  Println(r?) >>
  stop

11.6.5. Ref

site Ref[A](A) :: Ref[A]

Create a rewritable storage location initialized to the provided value.

ref[A].read() :: A

Read the value of the ref. If the ref does not yet have a value, block until it receives one. If a call to read blocks, it becomes quiescent.

ref[A].readD() :: A

Read the value of the ref. If the ref does not yet have a value, halt silently.

ref[A].write(A) :: Signal

Write a value to the ref, then return a signal.

11.6.6. (?)

def (?)[A](Ref[A]) :: A

Get the value held by a reference. x? is equivalent to x.read().

Implementation. 

              
def (?)[A](Ref[A]) :: A
def (?)(r) = r.read()


            

11.6.7. (:=)

def (:=)[A](Ref[A], A) :: Signal

Set the value held by a reference. x := y is equivalent to x.write(y).

Implementation. 

              
def (:=)[A](Ref[A], A) :: Signal
def (:=)(r,v) = r.write(v)


            

11.6.8. swap

def swap[A](Ref[A], Ref[A]) :: Signal

Swap the values in two references, then return a signal.

Implementation. 

              
def swap[A](Ref[A], Ref[A]) :: Signal
def swap(r,s) = (r?,s?) >(rval,sval)> (r := sval, s := rval) >> signal



            

11.6.9. Semaphore

site Semaphore(Integer) :: Semaphore

Return a semaphore with the given initial value, which must be non-negative. The semaphore maintains the invariant that its value is always non-negative.

An example using a semaphore as a lock for a critical section:

-- Prints:
-- Entering critical section
-- Leaving critical section
val lock = Semaphore(1)
lock.acquire() >>
Println("Entering critical section") >>
Println("Leaving critical section") >>
lock.release()

semaphore.acquire() :: Signal

Indefinite

If the semaphore's value is greater than 0, decrement the semaphore and return a signal. If the semaphore's value is 0, block until it becomes greater than 0. If a call to acquire blocks, it becomes quiescent.

semaphore.acquireD() :: Signal

Definite

If the semaphore's value is greater than 0, decrement the semaphore and return a signal. If the semaphore's value is 0, halt silently.

semaphore.release() :: Signal

Definite

If any calls to acquire are blocked, allow the oldest such call to return. Otherwise, increment the value of the semaphore. This may increment the value beyond that with which the semaphore was constructed.

semaphore.snoop() :: Signal

Indefinite

If any calls to acquire are blocked, return a signal. Otherwise, block until some call to acquire blocks. If a call to snoop blocks, it becomes quiescent.

semaphore.snoopD() :: Signal

Definite

If any calls to acquire are blocked, return a signal. Otherwise, halt silently.

11.6.10. Channel

site Channel[A]() :: Channel[A]

Create a new asynchronous FIFO channel of unlimited size. A channel supports get, put and close operations.

A channel may be either empty or non-empty, and either open or closed. When empty and open, calls to get block. When empty and closed, calls to get halt silently. When closed, calls to put halt silently. In all other cases, calls return normally.

Example:

-- Publishes: 10
val b = Channel()
  Rwait(1000) >> b.put(10) >> stop
| b.get()

channel[A].get() :: A

Indefinite

Get an item from the channel. If the channel is open and no items are available, block until one becomes available. If the channel is closed and no items are available, halt silently. If a call to get blocks, it becomes quiescent.

channel[A].getD() :: A

Definite

Get an item from the channel. If no items are available, halt silently.

channel[A].put(A) :: Signal

Definite

Put an item in the channel. If the channel is closed, halt silently.

channel[A].close() :: Signal

IndefiniteIdempotent

Close the channel and block until it is empty. This has the effect of immediately causing any blocked calls to get to halt silently. In addition, any subsequent calls to put will halt silently, and once the channel becomes empty, any subsequent calls to get will halt silently. If a call to close blocks, it becomes quiescent.

When the channel is empty, return a signal.

channel[A].closeD() :: Signal

DefiniteIdempotent

Close the channel and return a signal immediately. This has the effect of immediately causing any blocked calls to get to halt silently. In addition, any subsequent calls to put will halt silently, and once the channel becomes empty, any subsequent calls to get will halt silently.

channel[A].isClosed() :: Boolean

Definite

If the channel is currently closed, return true, otherwise return false.

channel[A].getAll() :: List[A]

Definite

Get all of the items currently in the channel, emptying the channel and returning a list of the items in the order they were added. If there are no items in the channel, return an empty list.

11.6.11. BoundedChannel

site BoundedChannel[A](Integer) :: BoundedChannel[A]

Create a new asynchronous FIFO channel with the given number of slots. Putting an item into the channel fills a slot, and getting an item opens a slot. A channel with zero slots is equivalent to a synchronous channel.

A bounded channel may be empty, partly filled, or full, and either open or closed. When empty and open, calls to get block. When empty and closed, calls to get halt silently. When full and open, calls to put block. When closed, calls to put halt silently. In all other cases, calls return normally.

Example:

-- Publishes: "Put 1" "Got 1" "Put 2" "Got 2"
val c = BoundedChannel(1)
  c.put(1) >> "Put " + 1
| c.put(2) >> "Put " + 2
| Rwait(1000) >> (
    c.get() >n> "Got " + n
  | c.get() >n> "Got " + n
  )

boundedChannel[A].get() :: A

Indefinite

Get an item from the channel. If the channel is open and no items are available, block until one becomes available. If the channel is closed and no items are available, halt silently. If a call to get blocks, it becomes quiescent.

boundedChannel[A].getD() :: A

Definite

Get an item from the channel. If no items are available, halt silently.

boundedChannel[A].put(A) :: Signal

Indefinite

Put an item in the channel. If no slots are open, block until one becomes open. If the channel is closed, halt silently. If a call to put blocks, it becomes quiescent.

boundedChannel[A].putD(A) :: Signal

Definite

Put an item in the channel. If no slots are open, halt silently. If the channel is closed, halt silently.

boundedChannel[A].close() :: Signal

IndefiniteIdempotent

Close the channel and block until it is empty. This has the effect of immediately causing any blocked calls to get to halt silently. In addition, any subsequent calls to put will halt silently, and once the channel becomes empty, any subsequent calls to get will halt silently. Note that any blocked calls to put initiated prior to closing the channel may still be allowed to return as usual. If a call to close blocks, it becomes quiescent.

boundedChannel[A].closeD() :: Signal

DefiniteIdempotent

Close the channel and return a signal immediately. This has the effect of immediately causing any blocked calls to get to halt silently. In addition, any subsequent calls to put will halt silently, and once the channel becomes empty, any subsequent calls to get will halt silently. Note that any blocked calls to put initiated prior to closing the channel may still be allowed to return as usual.

boundedChannel[A].isClosed() :: Boolean

Definite

If the channel is currently closed, return true, otherwise return false.

boundedChannel[A].getOpen() :: Integer

Definite

Return the number of open slots in the channel. Because of concurrency this value may become out-of-date so it should only be used for debugging or statistical measurements.

boundedChannel[A].getBound() :: Integer

DefinitePure

Return the total number of slots (open or filled) in the channel.

boundedChannel[A].getAll() :: List[A]

Definite

Get all of the items currently in the channel or waiting to be added, emptying the channel and returning a list of the items in the order they were added. If there are no items in the channel or waiting to be added, return an empty list.

11.6.12. Array

site Array[A](Integer) :: Array[A]

Create a new native array of the given nonnegative size. The array is initialized to contain nulls.

The resulting array can be called directly with an index, as if its type were lambda (Integer) :: Ref[A]. In this case, it returns a Ref pointing to the element of the array specified by an index, counting from 0. Changes to the array are reflected immediately in the ref and visa versa.

Simple example:

-- Publishes: 3
val a = Array(1)
a(0) := 3 >>
a(0)?

More complex example:

-- Publishes: 0 1 2
val a = Array(3)
for(0, a.length?) >i>
a(i) := i >>
stop
; a(0)? | a(1)? | a(2)?

Array[A](Integer, String) :: Array[A]

Create a new primitive array of the given size with the given primitive type. The initial values in the array depend on the primitive type: for numeric types, it is 0; for booleans, false; for chars, the character with codepoint 0.

The element type of the array should be the appropriate wrapper type for the given primitive type, although a typechecker may not be able to verify this. This constructor is only necessary when interfacing with certain Java libraries; most programs will just use the Array(Integer) constructor.

array[A].length? :: Integer

DefinitePure

Return the size of the array.

11.6.13. ObservationSubject

site ObservationSubject[E]() :: ObservationSubject[E]

Returns a "subject" where notifications are sent to all observers. An ObservationSubject can be viewed as a multi-reader channel. Observers register for notifications by calling observe(). Each time put() is called, the value is enqueued at each current observer. Observers fetch enqueued values by calling get().

observationSubject.observe() :: {. get :: lambda[]() :: Integer, stream :: lambda[]() :: Integer, close :: lambda[]() :: Signal, isClosed :: lambda[]() :: Boolean .}

Indefinite

Create an observer. TODO: Write more OrcDoc for ref manual entry

observer.get() :: Integer

Indefinite

TODO: Write more OrcDoc for ref manual entry

observer.stream() :: Integer

Indefinite

TODO: Write more OrcDoc for ref manual entry

observer.close() :: Signal

IndefiniteIdempotent

TODO: Write more OrcDoc for ref manual entry

observer.isClosed() :: Boolean

Definite

TODO: Write more OrcDoc for ref manual entry

observationSubject.put(Integer) :: Signal

Definite

TODO: Write OrcDoc for ref manual entry

observationSubject.close() :: Signal

IndefiniteIdempotent

TODO: Write OrcDoc for ref manual entry

observationSubject.closeD() :: Signal

DefiniteIdempotent

TODO: Write OrcDoc for ref manual entry

observationSubject.isClosed() :: Boolean

Definite

TODO: Write OrcDoc for ref manual entry

Implementation. 

              
            

11.6.14. Table

def Table[A](Integer, lambda (Integer) :: A)(Integer) :: A

The call Table(n,f), where n is a natural number and f a total function over natural numbers, creates and returns a partial, pre-computed version of f restricted to the range (0, n-1). Table does not return a value until all calls to f have completed. Consequently, if f halts silently on any call, the call to Table will halt silently.

The user may also think of the call as returning an immutable array whose ith element is accessed by calling f(i).

This function provides a simple form of memoisation; we avoid recomputing the value of f(i) by internally storing the result in an array.

Example:

val a = Table(5, fib)
-- Publishes the 4th number of the fibonnaci sequence: 5
a(3)

Implementation. 

              
def Table[A](Integer, lambda (Integer) :: A) :: (lambda(Integer) :: A)
def Table(n, f) =
  val a = Array[A](n) :: Array[A]
  def fill(Integer, lambda (Integer) :: A) :: Signal
  def fill(i, f) =
    if i <: 0 then signal
    else ((a(i) := f(i)), fill(i-1, f)) >> signal
  fill(n-1, f) >> (lambda (i :: Integer) = a(i)?)



            

11.6.15. Counter

site Counter(Integer) :: Counter

Create a new counter initialized to the given value.

11.6.16. Counter

site Counter() :: Counter

Create a new counter initialized to zero.

counter.inc() :: Signal

Definite

Increment the counter.

counter.dec() :: Signal

Definite

If the counter is already at zero, halt silently. Otherwise, decrement the counter and return a signal.

counter.onZero() :: Signal

Indefinite

If the counter is at zero, return a signal. Otherwise, block until the counter reaches zero. If a call to onZero blocks, it becomes quiescent.

counter.value() :: Integer

Definite

Return the current value of the counter.

Example:

-- Publishes five signals
val c = Counter(5)
repeat(c.dec)

11.6.17. Dictionary

site Dictionary() :: Dictionary

Create a new dictionary (a mutable map from field names to values), initially empty. The first time a field of the dictionary is accessed (using a dot access), the dictionary creates and returns a new empty Ref which will also be returned on subsequent accesses of the same field. A dictionary differs from a record in that it is both mutable and dynamically extensible.

Example:

-- Prints: 1 2
val d = Dictionary()
  Println(d.one.read()) >>
  Println(d.two.read()) >>
  stop
| d.one.write(1) >>
  d.two.write(2) >>
  stop

Here is the same example rewritten using Orc's reference syntax to improve clarity:

-- Prints: 1 2
val d = Dictionary()
  Println(d.one?) >>
  Println(d.two?) >>
  stop
| d.one := 1 >>
  d.two := 2 >>
  stop

To create a multi-level dictionary, one must explicitly create sub-dictionaries for each field. For example:

-- Prints: 2
val d = Dictionary()
d.one := Dictionary() >>
d.one?.two := 2 >>
Println(d.one?.two?) >>
stop

Note that d.one.two is not valid: because d.one is a reference to a dictionary, and not simply a dictionary, a dereference step is needed before accessing a field, as in d.one? >x> x.two. For readers familiar with the C language, this is the same reason one must write s->field instead of s.field when s is a pointer to a struct.

11.6.18. fst

def fst[A,B]((A,B)) :: A

Return the first element of a pair.

Implementation. 

              
def fst[A,B]((A,B)) :: A
def fst((x,_)) = x


            

11.6.19. snd

def snd[A,B]((A,B)) :: B

Return the second element of a pair.

Implementation. 

              
def snd[A,B]((A,B)) :: B
def snd((_,y)) = y


            

11.6.20. Interval

site Interval[A](A, A) :: Interval[A]

Interval(a,b) returns an object representing the half-open interval [a,b).

interval[A].isEmpty() :: Boolean

Return true if this interval is empty.

interval[A].spans(A) :: Boolean

Return true if the interval spans the given point, false otherwise.

interval[A].intersects(Interval[A]) :: Boolean

Return true if the given interval has a non-empty intersection with this one, and false otherwise.

interval[A].intersect(Interval[A]) :: Interval[A]

Return the intersection of this interval with another. If the two intervals do not intersect, returns an empty interval.

interval[A].contiguous(Interval[A]) :: Boolean

Return true if the given interval is contiguous with this one (overlaps or abuts), and false otherwise.

interval[A].union(Interval[A]) :: Interval[A]

Return the union of this interval with another. Halts with an error if the two intervals are not contiguous.

11.6.21. Intervals

site Intervals[A]() :: Intervals[A]

Return an empty set of intervals. An Intervals object is iterable; iterating over the set returns disjoint intervals in increasing order.

intervals[A].isEmpty() :: Boolean

Return true if this set of intervals is empty.

intervals[A].spans(A) :: Boolean

Return true if this set of intervals spans the given point, and false otherwise.

intervals[A].intersect(Intervals[A]) :: Intervals[A]

Return the intersection of this set of intervals with another.

intervals[A].union(Interval[A]) :: Intervals[A]

Return the union of this set of intervals with the given interval. This method is most efficient when the given interval is before most of the intervals in the set.