TRS Chapter #06 Examples in Oz
%%%%%%%%%%%%%%%%%%%%%%%%%%% From CTM Chapter 9 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Lazy problem solving (Solve)
% This is the Solve operation, which returns a lazy list of solutions
% to a relational program. The list is ordered according to a
% depth-first traversal. Solve is written using the computation space
% operations of the Space module.
fun {Solve Script}
{SolStep {Space.new Script} nil}
end
fun {SolStep S Rest}
case {Space.ask S}
of failed then Rest
[] succeeded then {Space.merge S}|Rest
[] alternatives(N) then
{SolLoop S 1 N Rest}
end
end
fun lazy {SolLoop S I N Rest}
if I>N then Rest
elseif I==N then
{Space.commit S I}
{SolStep S Rest}
else Right C in
Right={SolLoop S I+1 N Rest}
C={Space.clone S}
{Space.commit C I}
{SolStep C Right}
end
end
fun {SolveOne F}
L = {Solve F}
in
if L==nil then nil else [L.1] end
end
fun {SolveAll F}
L = {Solve F}
proc {TouchAll L}
if L==nil then skip else {TouchAll L.2} end
end
in
{TouchAll L}
L
end
fun {SolveN N F}
L = {Solve F}
in
{List.take L N}
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Translation Notes:
%% 6.19-6.30: Need an Oz Breadth-First Solve that matches the behavior of condi
% 6.31-6.38: Need an Oz Solve that matches the behavior of all and alli
% 6.1
fun {Anyo G}
choice
{G}
[] {Anyo G}
end
end
% 6.4
fun {Nevero}
{Anyo fun {$} fail end}
end
% 6.5 (diverges)
%{Browse 5#
% {SolveOne
% fun {$} Q in
% _ = {Nevero}
% true = Q
% end}}
% 6.6
{Browse 6#
{SolveOne
fun {$} Q in
fail
{Nevero}
end}}
% 6.7
fun {Alwayso}
{Anyo fun {$} skip _ end}
end
{Browse 7#
{SolveOne
fun {$} Q in
_ = {Alwayso}
true = Q
end}}
% 6.9 (diverges)
%{Browse 9#
% {SolveAll
% fun {$} Q in
% _ = {Alwayso}
% true = Q
% end}}
% 6.10
{Browse 10#
{SolveN 5
fun {$} Q in
_ = {Alwayso}
true = Q
end}}
% 6.11
{Browse 11#
{SolveN 5
fun {$} Q in
true = Q
_ = {Alwayso}
Q
end}}
% 6.12
fun {Salo G}
choice
skip _
[] {G}
end
end
% 6.13
{Browse 13#
{SolveOne
fun {$} Q in
_ = {Salo Alwayso}
true = Q
end}}
% 6.14
{Browse 14#
{SolveOne
fun {$} Q in
_ = {Salo Nevero}
true = Q
end}}
% 6.15 (diverges)
%{Browse 15#
% {SolveAll
% fun {$} Q in
% _ = {Salo Nevero}
% true = Q
% end}}
% 6.16 (diverges)
%{Browse 16#
% {SolveOne
% fun {$} Q in
% _ = {Salo Nevero}
% fail
% true = Q
% end}}
% 6.17 (diverges)
%{Browse 17#
% {SolveOne
% fun {$} Q in
% _ = {Alwayso}
% fail
% true = Q
% end}}
% 6.18 (diverges)
%{Browse 18#
% {SolveOne
% fun {$} Q in
% _ =
% choice
% false = Q
% {Alwayso}
% [] {Anyo fun {$} true = Q end}
% end
% true = Q
% end}}
% Translation of 6.19 - 6.38 is not completed
% %% 6.19 (Note: condi is a breadth-first search)
% {Browse 19#
% {BFSolveOne
% fun {$} Q in
% _ =
% choice
% false = Q
% {Alwayso}
% [] true = Q
% end
% true = Q
% end}}
%
% %% 6.20 (diverges)
% %{Browse 20#
% % {BFSolveN 2
% % fun {$} Q in
% % _ =
% % choice
% % false = Q
% % {Alwayso}
% % [] true = Q
% % end
% % true = Q
% % end}}
%
% %% 6.21
% {Browse 21#
% {BFSolveN 5
% fun {$} Q in
% _ =
% choice
% false = Q
% {Alwayso}
% [] {Anyo fun {$} true = Q end}
% end
% true = Q
% end}}
%
% %% 6.24
% fun {Teacup}
% choice tea [] cup end
% end
% {Browse 24#
% {BFSolveN 5
% fun {$} R in
% choice
% {Teacup} = R
% [] false = R
% [] fail
% end
% end}}
%
% %% 6.25
% {Browse 25#
% {BFSolveN 5
% fun {$} Q in
% _ =
% choice
% false = Q
% {Alwayso}
% [] true = Q
% {Alwayso}
% [] fail
% end
% true = Q
% end}}
%
% %% 6.27 (diverges)
% %{Browse 27#
% % {SolveN 5
% % fun {$} Q in
% % _ =
% % choice
% % false = Q
% % {Alwayso}
% % [] true = Q
% % {Alwayso}
% % [] fail
% % end
% % true = Q
% % end}}
%
% %% 6.28
% {Browse 28#
% {SolveN 5
% fun {$} Q in
% _ =
% choice
% {Alwayso}
% [] {Nevero}
% end
% true = Q
% end}}
%
% %% 6.30 (diverges)
% {Browse 30#
% {BFSolveN 5
% fun {$} Q in
% _ =
% choice
% {Alwayso}
% [] {Nevero}
% end
% true = Q
% end}}
% %% 6.31
% {Browse 31#
% {AllSolveOne
% fun {$} Q in
% choice
% false = Q
% [] true = Q
% end
% _ = {Alwayso}
% true = Q
% end}}
%
% %% 6.32
% {Browse 32#
% {AllBFSolveOne
% fun {$} Q in
% choice
% false = Q
% [] true = Q
% end
% _ = {Alwayso}
% true = Q
% end}}
%
% %% 6.33
% {Browse 33#
% {AllBFSolveN 5
% fun {$} Q in
% choice
% false = Q
% [] true = Q
% end
% _ = {Alwayso}
% true = Q
% end}}
%
% %% 6.34
% {Browse 34#
% {AllBFSolveN 5
% fun {$} Q in
% choice
% true = Q
% [] false = Q
% end
% _ = {Alwayso}
% true = Q
% end}}
%
% %% 6.36
% {Browse 36#
% {AllSolveN 5
% fun {$} Q in
% choice
% _=_
% [] _={Nevero}
% end
% _ = {Alwayso}
% true = Q
% end}}
%
% %% 6.38 (diverges)
% {Browse 36#
% {AllBFSolveN 5
% fun {$} Q in
% choice
% _=_
% [] _={Nevero}
% end
% _ = {Alwayso}
% true = Q
% end}}
|