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(2,desc) => let val c = Space.clone s in Space.commit(s, desc, 0); case searchOne s of NONE => (Space.commit(c, desc, 1); searchOne c) | SOME s => SOME s end
Given the money script, a solution can be searched by invoking
val s = Space.new() val moremoney = money s val SOME solution = searchOne s
The solution is itself again a space. You can use the functions from FD.Reflect together with the variables in moremoney to extract the actual values from the solution space.
More sophisticated search engines are provided by the structure Search.
import signature SPACE from "x-alice:/lib/gecode/SPACE-sig" import structure Space from "x-alice:/lib/gecode/Space"
signature SPACE = sig eqtype space type description exception InvalidSpace exception InvalidVar exception Description exception InternalException datatype status = BRANCH of int * description | FAILED | SOLVED val new : unit -> space val status : space -> status val commit : space * description * int -> unit val clone : space -> space val discard : space -> unit val alive : space -> bool val fail : space -> unit end
The type of computation spaces.
A branch description.
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.
returns a newly created space.
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 InvalidSpace if the space s has already been discarded.
returns a new space which is a copy of s.
Raises InvalidSpace if the space s has already been discarded.
commits to alternative i of s, using branching description d. The first alternative is 0.
Raises InvalidSpace if the space s has already been discarded, or Description if d is invalid for this space.
discards the space s, freeing up the memory it uses. Subsequent operations on this space will raise a runtime error.
tests whether the space s is still alive, i.e. whether it has not been discarded.
injects a failure into s.