<< Prev | - Up - | Next >> |
Rule: only stateful datastructures created inside the search space can be modified during search. It is possible to access global datastructures from within the search space, as this example demonstrates:
declare
C={NewCell 1}
proc {Pred1 X} X={Access C} end
{ExploreAll Pred1}
but it is not possible to modify a global data-structure. The following example:
declare
C={NewCell 1}
proc {Pred2 X} {Assign C 2} X={Access C} end
{ExploreAll Pred2}
raises an exception because the search predicate Pred2
attempts to modify the global cell C
. If you need to modify stateful datastructures inside your search predicate, this is only possible if these datastrutures are also created inside the search predicate, i. e. inside the search space:
declare
proc {Pred3 X}
C={NewCell 1}
in
{Assign C 2}
X={Access C}
end
{ExploreAll Pred3}
What is wrong about the following example? How should it be written instead?
declare
D={NewDictionary}
D.left := left(foo)
proc {Pred4 X}
D.left = left(X)
D.right := right(X)
end
{ExploreAll Pred4}
Rule: a search predicate should not refer to global free variables. All identifiers within the search predicate must either be locally introduced, or, if they are not, refer to variables that were bound before the time the search is performed.
This is really just a variation on the previous rule: a unbound variable is a form of stateful datastructure: it can be assigned (bound) once. Therefore it too must be created by the search redicate. For example, the following code blocks:
declare
Y
proc {Pred6 X} Y=f(X) end
{ExploreAll Pred6}
In the Explorer, this is displayed by a yellow star. How should his code be written so that it doesn't block?
In previous exercises (see Section 10.7), we considered a ground representation of terms:
term ::= var | f(term
...term)
Write a function MakeEncapsulatedTerm
which takes a ground representation of a term and returns an encapsulated term. Make sure that it works properly with respect to search. In particular, it should work with the following example:
declare
P1={ToEncapsulatedTerm f(1 g(1 2))}
P2={ToEncapsulatedTerm f(h(2 1) g(2 1))}
{ExploreAll proc {$ T} {P1 T} {P2 T} end}
Write a functional procedure UnifyAllSubSequences
which inputs a list of terms [T1 ... Tn]
encoded as unary predicates and outputs a chart with n+1
positions. This chart contains an edge from position i to position j if and only if the conjunction of X=Ti,...,X=Tj
is satisfiable for some fresh variable X
. An edge between i and j should carry a solved form of this conjunction in terms of a predicate for X
.
For instance, your procedure UnifyAllSubSequences
should be able to deal with the following input list Ts
:
declare
proc{T1 X} Y in X=f(Y _ Y) end
proc{T2 X} X=f(a _ _) end
proc{T3 X} X=f(_ b _) end
proc{T4 X} Y in X=f(_ Y Y) end
proc{T5 X} X=f(_ _ c) end
Ts = [T1 T2 T3 T4 T5]
<< Prev | - Up - | Next >> |