8.3. Expression States

A site call, from the site's perspective, has three possible outcomes: the site will definitely publish a value, the site knows that it will never publish a value, and the site does not know if it will ever publish a value. For example, a call to Ift(true) publishes a signal, Ift(false) never publishes, and c.get() on channel c that is currently empty may eventually publish or remain non-responsive, depending on whether a value is put in c in the future.

A site call, from the caller's perspective, is ready, blocked or halted. A call is ready if all its arguments have deflated to values, so that a call can be made. A call is blocked if either (1) the caller can not make the call because not all argument values are bound (since site calls are strict); this is an internally blocked call, or (2) the caller is waiting for the response after having called the site; this is an externally blocked call. A site call is halted if the caller has already received a response or the site has indicated that it will never send a response. A site call is killed if it is part of G in F <x< G and G publishes.

An internally blocked call becomes ready when all its arguments are bound to values. An internally blocked call halts if one of its arguments will never be bound because the expression that computes its value has halted or has been killed. A ready call becomes externally blocked once the call is made. A blocked call transitions to halted if it receives a response or if the called site can determine that it will never respond; a blocked call may remain blocked forever if the called site can not determine if if it will ever respond. Note that a halted call stays halted unless it is killed.

We extend these concepts to execution of an expression. At any moment, an expression has an associated set of site calls under consideration for execution; if the expression has begun additional executions, as in F >x> G, all the versions of G being executed contribute to this set; if the expression includes function calls, those calls initiate execution of the function bodies which are also expressions that contribute to this set; any variable x used as an expression on its own is equivalent to a site call Let(x). If some site call in this set is ready, the expression is ready; if all calls are blocked, the expression is blocked, and if all calls are halted the expression is halted.

8.3.1. Ready

A site call is ready if all its argument variables are bound to values, so that a call can be made. An expression is ready if some site call in its set of associated site calls is ready.

8.3.2. Blocked

A site call is blocked if (1) the call can not be made because some argument of the call is unbound, the call is then internally blocked, or (2) the caller is waiting for a response, the call is then externally blocked. An expression is blocked if its set of associated site calls are all blocked. All component expressions of a blocked expression are blocked. A blocked expression stays blocked unless (1) an internally blocked site call is made ready by the bindings of its arguments, or (2) it is halted, or (3) killed.

8.3.3. Halted

A site call is halted if (1) it was internally blocked and one of its arguments will never be bound because the expression that computes its value has been halted or killed, or (2) it was externally blocked and either a response has been received or an indication that there never will be a response. An expression is halted if the set of associated site calls have all halted. All component expressions of a halted expression are halted. A halted expression stays halted unless it is killed. A halted expression never makes site calls nor publishes any value.

8.3.4. Killed

Expression G is killed in F <x< G if G has published. All component expressions of a killed expression are killed. A killed expression stays killed. A killed expression never makes site calls nor publishes any value.

8.3.5. Helpful Sites

Sites that may indicate absence of response are called helpful (see Helpful Sites). Not all sites are helpful.

8.3.6. Examples

Parallel site calls; ready and blocked states

Let c be a channel. Consider expression G given by

c.get() | Rwait(1000)

The expression is ready because it can make both calls. After both calls have been made, the expression is blocked waiting for their responses. Suppose Rwait(1000) responds first. Then the expression stays blocked waiting for the response to c.get(). If a response is received, the expression halts; if c is empty and another caller closes c, then c.get() indicates that there will be no response, causing G to halt; otherwise, G stays blocked forever.

Pruning combinator; killed state

Consider the expression

F <x< G

where G from the previous example is

c.get() | Rwait(1000)

As we have shown, G will definitely publish. Then G is killed, and so are its sub-expressions.

Sequential and otherwise combinators

In the previous example let F be

x >> c.get() >> true ; false

In F <x< G, expression F is blocked until x is bound to a value. Since G eventually publishes, x will be bound eventually. Then the call c.get() is made in F. As we have discussed, this call (1) may receive a response, in which case true will be published, and the entire expression halts, (2) the call receives an indication that there will be no response (in case c is empty and it is closed) in which case x >> c.get() >> true halts silently, causing false to be published, or (3) the call remains blocked forever, causing F to remain blocked.

8.3.7. Related Links