Alice Project

The Future structure

________ Synopsis ____________________________________________________

    signature FUTURE
    structure Future : FUTURE

The Future structure provides operations to create and inspect futures. A future is a place-holder for the undetermined result of a computation. Once the computation terminates with a result value, the future is eliminated by globally replacing it with that value. That value may be a future on its own. If the associated computation terminates with an exception, the future is failed. A failed future carries the corresponding exception and reraises it on every attempt to access it. Whenever a future is requested by a concurrent computation, i.e. it tries to access its value, that computation automatically synchronizes on the future by blocking until it becomes determined or failed.

There are three basic kinds of futures:

For more background, see the overview of futures. See the end of the page for some examples of programming with futures.

Limitation: Handling of failed futures currently deviates from the specification for some border cases, due to compatibility issues.

See also: Promise, Thread, Alt

________ Import ______________________________________________________

Imported implicitly.

________ Interface ___________________________________________________

    signature FUTURE =
	datatype status = FUTURE | FAILED | DETERMINED

	exception Cyclic

	val concur :       (unit -> 'a) -> 'a
	val byneed :       (unit -> 'a) -> 'a
	val alarm :        Time.time -> unit

	val await :        'a -> 'a
	val awaitEither :  'a * 'b -> ('a,'b) alt

	val status :       'a -> status
	val isFuture :     'a -> bool
	val isFailed :     'a -> bool
	val isDetermined : 'a -> bool
	val isLazy :       'a -> bool

        functor Concur (signature S functor F () : S) : S
        functor ByNeed (signature S functor F () : S) : S

________ Description _________________________________________________

datatype status = FUTURE | FAILED | DETERMINED

A type describing the status of a value. Every value is either determined, a future, or a failed future.

exception Cyclic

Raised if the computation associated with a future returns the future itself as its result.

concur f

Creates a new thread that evaluates f () and immediately returns a future of the result. When the application has been evaluated, the future is replaced by the result. If the application terminates with an exception ex, the future is failed with exception ex. If the application terminates returning the future itself, the future is failed with exception Cyclic. Equivalent to spawn f().

Note that raising an exception synchronizes on the exception value, so that no cycle can occur if the computation tries to raise its own future as an exception. It rather blocks forever.

byneed f

Returns a lazy future of the computation f (). As soon as a thread requests the future, the computation is intiated in a new thread. Evaluation proceeds similar to concur. Equivalent to lazy f().

alarm t

Creates a future that is determined to () after the time period t. In conjunction with awaitEither, this function can be used to program timeouts. Raises Overflow if t is larger than the longest possible time period that can be handled by the system. Equivalent to spawn Thread.sleep t.

await v

Explicitly request the value v, returning the value. If v is not a future, the function returns immediately. If v is failed with exception ex, await will reraise ex.

awaitEither (v1, v2)

Blocks until at least one of the two arguments is determined or failed. It then returns the respective argument wrapped into an alternative. Unlike await, this function never raises an exception, even if one of the arguments is failed. Further inspection using await or isFailed is required to find out whether that argument is failed.

status v

Returns the current status of the value v, without accessing the value.

Note: Use of this reflective function and its respective abbreviations below is discouraged, as it breaks monotonicity of futures, and thus referential transparency.

isFuture v
isFailed v
isDetermined v

Verify the status of the value v. Equivalent to:

        isFuture x = (status v = FUTURE)
        isFailed x = (status v = FAILED)
        isDetermined x = (status v = DETERMINED)
isLazy v

Returns true if v is a lazy future that has not yet been requested, false otherwise. Does not request v by itself.

Concur (signature S = SIG functor F () = MOD)
ByNeed (signature S = SIG functor F () = MOD)

Polymorphic functors evaluating a module expression MOD concurrently or lazily. The following equivalences hold:

        Concur (signature S = SIG functor F () = MOD) = spawn MOD : SIG
        ByNeed (signature S = SIG functor F () = MOD) = lazy MOD : SIG

________ Examples ____________________________________________________

The following function generates an infinite list of integers:

	fun enum n = lazy n :: enum (n+1)

Here is lazy variant of map that can deal with infinite lists:

	fun mapl f   []    = nil
	  | mapl f (x::xs) = lazy f x :: mapl f xs

However, this version is still strict in the first cons of the list. A fully lazy version is:

	fun mapl f xs = lazy (case xs
	                        of  []   => nil
	                         | x::xs => f x :: mapl f xs)

which is equivalent to the more readable formulation using syntactic sugar

	fun lazy mapl f   []    = nil
	       | mapl f (x::xs) = f x :: mapl f xs

The following function waits for a given amount of time for the result of a computation (passed as a future) to become available. It returns SOME v if a valid result is available within the time limit, NONE otherwise.

	fun timeout (x : 'a, t : Time.time) : 'a option =
	    case awaitEither (x, alarm t)
	     of FST x => SOME x
	      | SND _ => NONE

See also Promise for additional examples.

last modified 2007/Mar/30 17:10