alice
library
manual.
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.