Alice Project

The Promise structure

________ Synopsis ____________________________________________________

    signature PROMISE
    structure Promise : PROMISE

The Promise structure provides operations to create and eliminate futures through explicit handles, so-called promises. The polymorphic function

      promise ()

creates a new promise p and an associated future. The future can then be extracted with the function

      future p

The future is eliminated by applying fulfill (p, v), which globally replaces it with the value v. That value may again be a future. A promise may not be fulfilled more than once.

Note: Promises may be thought of as single-assignment references that allow dereferencing prior to assignment, yielding a future. The operations promise, future and fulfill correspond to ref, ! and :=, respectively.

See the end of the page for some examples of programming with promises.

See also: Future, Ref

________ Import ______________________________________________________

Imported implicitly.

________ Interface ___________________________________________________

    signature PROMISE =
	type 'a promise
	type 'a t = 'a promise

	exception Promise

	val promise :     unit -> 'a promise
	val future :      'a promise -> 'a

	val fulfill :     'a promise * 'a -> unit
	val fail :        'a promise * exn -> unit

	val isFulfilled : 'a promise * 'a -> unit

________ Description _________________________________________________

type 'a promise
type t = promise

The type of promises of values of type 'a.

exception Promise

Raised on multiple attempts to fulfill the same promise.

promise ()

Creates a new promise and an associated future. Returns the promise.

future p

Returns the future associated with p. If p has already been fulfilled with value v, that value is returned.

fulfill (p, v)

Replaces the future associated with p with the value v. If v is the future itself, the exception Future.Cyclic is raised instead. If p has already been fulfilled or failed, the exception Promise is raised.

fail (p, ex)

Requests the exception ex and fails the future associated with the promise p with ex. If p has already been fulfilled or failed, the exception Promise is raised. Equivalent to

        (Future.await ex; fulfill (p, spawn raise ex))
isFulfilled p

Returns true if p has already been fulfilled or failed, false otherwise. Note that a result of true does not necessarily imply that future p is determined, since p may have been fulfilled with another future.

________ Examples ____________________________________________________

Promises can be utilized to write a tail-recursive version of append:

    fun append (l1, l2)       = let val p = promise() in append'(l1, l2, p); future p end
    and append'( [],   l2, p) = fulfill(p, l2)
      | append'(x::l1, l2, p) = let val p' = promise() in fulfill(p, x::future p'); append'(l1, l2, p') end

Channels can be implemented easily using promises and references:

    type 'a chan = 'a list promise ref * 'a list ref

    fun chan () =
	    val p = promise ()
	    (ref p, ref (future p))

    fun put ((putr, getr), x) =
            val p = promise ()
            fulfill ( (putr, p), x :: future p)

    fun get (putr, getr) =
            val p  = promise ()
	    val xs = (getr, future p)
            fulfill (p, tl xs); hd xs

    fun close (putr, getr) = fulfill (!putr, nil)

last modified 2007/Mar/30 17:10