alice
library
manual.

Home
Tour
Language
Library
Tools
Site Map

The Space structure

^________ Synopsis ^{____________________________________________________}

    signature SPACE
    structure Space : SPACE

The Space structure provides access to first class computation spaces. First class computation spaces can be used to program inference engines for problem solving.

For example, simple depth-first one solution search can be done as follows.

    fun searchOne s =
	case Space.status s of
	     Space.FAILED          => NONE
	   | Space.SOLVED          => SOME s
	   | Space.BRANCH(desc) =>
		 let
		     val c = Space.clone s
		 in
		     Space.commit(s, 1, desc);
		     case searchOne s of
			  NONE   => (Space.commit(c, 2, desc); searchOne c)
			| SOME s => SOME s
		 end

Given the money script, a solution can be searched by invoking

    val s = Space.new()
    val solution = searchOne (money s)

More sophisticated search engines are provided by the structure Search.

^________ Import ^{______________________________________________________}

    import signature SPACE from "x-alice:/lib/gecode/SPACE-sig"
    import structure Space from "x-alice:/lib/gecode/Space"

^________ Interface ^{___________________________________________________}

    signature SPACE =
    sig
        eqtype space
        type description

	exception InvalidSpace
	exception InvalidVar
	exception Description

	datatype status = BRANCH of int * description | FAILED | SOLVED
	val new         : unit -> space
	val status      : space -> status
	val commit      : space * int * description -> unit
	val clone       : space -> space
	val discard     : space -> unit
	val alive       : space -> bool
	val fail        : space -> unit
    end

^________ Description ^{_________________________________________________}

eqtype space

The type of computation spaces.

type description

A branch description.

datatype status = BRANCH of int * description | FAILED | SOLVED

This datatype is used to communicate the state of a computation space. If the status is BRANCH(x,d), the x is the number of alternatives, and d is a branching description that can be used for commiting to an alternative.

new

returns a newly created space.

status s

runs propagation in s until it reaches a fixed point and then returns the status of s.

If s is failed, FAILED is returned.

If s is not failed and there are no active distributors in s waiting for choices, SOLVED is returned.

If s is not failed and there is at least one active distributor in s which is waiting for a choice, BRANCH(x, d) is returned, where x is the number of alternatives and d is an abstract description of the choice.

Raises a runtime error if the space s has already been discarded.

clone s

returns a new space which is a copy of s.

Raises a runtime error if the space s has already been discarded.

commit (s, d, i)

commits to alternative i of s, using branching description d.

Raises a runtime error if the space s has already been discarded, or description d is invalid for this space.

discard s

discards the space s, freeing up the memory it uses. Subsequent operations on this space will raise a runtime error.

alive s

tests whether the space s is still alive, i.e. whether it has not been discarded.

fail s

injects a failure into s.