TRS Chapter #07 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
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 7.5
fun {BitXORo X Y R}
choice
X=0 Y=0 R=0
[] X=1 Y=0 R=1
[] X=0 Y=1 R=1
[] X=1 Y=1 R=0
end
end
% 7.6
{Browse 6#
{SolveAll
fun {$} S X Y in
_ = {BitXORo X Y 0}
[X Y] = S
end}}
% 7.8
{Browse 8#
{SolveAll
fun {$} S X Y in
_ = {BitXORo X Y 1}
[X Y] = S
end}}
% 7.9
{Browse 9#
{SolveAll
fun {$} S X Y R in
_ = {BitXORo X Y R}
[X Y R] = S
end}}
% 7.10
fun {BitANDo X Y R}
choice
X=0 Y=0 R=0
[] X=1 Y=0 R=0
[] X=0 Y=1 R=0
[] X=1 Y=1 R=1
end
end
% 7.11
{Browse 11#
{SolveAll
fun {$} S X Y in
_ = {BitANDo X Y 1}
[X Y] = S
end}}
% 7.12
%% Need to get "all" search working for translation of first TRS implementation
fun {HalfAddero X Y R C}
choice
X=0 Y=0 R=0 C=0
[] X=1 Y=0 R=1 C=0
[] X=0 Y=1 R=1 C=0
[] X=1 Y=1 R=0 C=1
end
end
{Browse 12#
{SolveAll
fun {$} R in
_ = {HalfAddero 1 1 R 1}
R
end}}
% 7.13
{Browse 13#
{SolveAll
fun {$} S X Y R C in
_ = {HalfAddero X Y R C}
[X Y R C] = S
end}}
% 7.15
fun {FullAddero B X Y R C} W XY WZ in
_ = {HalfAddero X Y W XY}
_ = {HalfAddero W B R WZ}
{BitXORo XY WZ C}
end
{Browse 15#
{SolveAll
fun {$} S R C in
_ = {FullAddero 0 1 1 R C}
[R C] = S
end}}
fun {FullAddero2 B X Y R C}
choice
B=0 X=0 Y=0 R=0 C=0
[] B=1 X=0 Y=0 R=1 C=0
[] B=0 X=1 Y=0 R=1 C=0
[] B=1 X=1 Y=0 R=0 C=1
[] B=0 X=0 Y=1 R=1 C=0
[] B=1 X=0 Y=1 R=0 C=1
[] B=0 X=1 Y=1 R=0 C=1
[] B=1 X=1 Y=1 R=1 C=1
end
end
% 7.16
{Browse 16#
{SolveAll
fun {$} S R C in
_ = {FullAddero 1 1 1 R C}
[R C] = S
end}}
% 7.17
{Browse 17#
{SolveAll
fun {$} S B X Y R C in
_ = {FullAddero B X Y R C}
[B X Y R C] = S
end}}
% 7.43
fun {BuildNum N}
if N == 0 then
nil
elseif {IsEven N} == true then
0|{BuildNum (N div 2)}
else
1|{BuildNum ((N - 1) div 2)}
end
end
% 7.40
{Browse 40#{BuildNum 0}}
% 7.41
{Browse 41#{BuildNum 36}}
% 7.42
{Browse 42#{BuildNum 19}}
% 7.44
fun {BuildNum2 N}
if {IsOdd N} == true then
1|{BuildNum2 ((N - 1) div 2)}
elseif {IsEven N} == true then
0|{BuildNum2 (N div 2)}
else
nil
end
end
% 7.80
fun {Poso N} A D in
A|D = N
end
{Browse 80#
{SolveAll
fun {$} Q in
_ = {Poso [0 1 1]}
true = Q
end}}
% 7.81
{Browse 81#
{SolveAll
fun {$} Q in
_ = {Poso [1]}
true = Q
end}}
% 7.82
{Browse 82#
{SolveAll
fun {$} Q in
_ = {Poso nil}
true = Q
end}}
% 7.83
{Browse 83#
{SolveAll
fun {$} Q in
_ = {Poso Q}
Q
end}}
% 7.86
proc {GT1o N} A AD DD in
A|AD|DD = N
end
{Browse 86#
{SolveAll
fun {$} Q in
{GT1o [0 1 1]}
true = Q
end}}
% 7.87
{Browse 87#
{SolveAll
fun {$} Q in
{GT1o [0 1]}
true = Q
end}}
% 7.88
{Browse 88#
{SolveAll
fun {$} Q in
{GT1o [1]}
true = Q
end}}
% 7.89
{Browse 89#
{SolveAll
fun {$} Q in
{GT1o nil}
true = Q
end}}
% 7.90
{Browse 90#
{SolveAll
fun {$} R in
{GT1o R}
R
end}}
% Translation of 7.97 - 7.133 is not completed
% %% 7.118
% fun {GenAddero D N M R} A B C E X Y Z in
% choice
% A|X=N
% [] B|Y=M {Poso Y}
% [] C|Z=R {Poso Z}
% []
% (alli ???
% _{FullAddero D A B C E}
% _{Addero E X Y Z}
% end
% end
%
% fun {Addero D N M R}
% choice
% D=0 M=nil R=N
% [] D=0 N=nil R=M {Poso M}
% [] D=1 M=nil {Addero 0 N [1] R}
% [] D=1 N=nil {Addero 0 [1] M R}
% [] A C in N=[1] M=[1] [A C]=R {FullAddero D 1 1 A C}
% [] N=[1] {GenAddero D N M R}
% [] M=[1] {GT1o N} {GT1o R} {Addero D [1] N R}
% [] {GT1o N} {GenAddero D N M R}
% end
% end
%
% %% 7.97
% {Browse 97#
% {SolveN 3
% fun {$} S X Y R in
% _ = {Addero 0 X Y R}
% [X Y R] = S
% end}}
%
% %% 7.101
% {Browse 101#
% {SolveN 22
% fun {$} S X Y R in
% _ = {Addero 0 X Y R}
% [X Y R] = S
% end}}
%
% %% 7.120
% {Browse 120#
% {SolveAll
% fun {$} S in
% {GenAddero 1 [0 1 1] [1 1] S}
% end}}
%
% %% 7.126
% {Browse 126#
% {SolveAll
% fun {$} S X Y in
% _ = {Addero 0 X Y [1 0 1]}
% [X Y] = S
% end}}
%
% %% 7.128
% fun {Pluso N M K}
% {Addero 0 N M K}
% end
%
% %% 7.129
% {Browse 129#
% {SolveAll
% fun {$} S X Y in
% _ = {Pluso X Y [1 0 1]}
% [X Y] = S
% end}}
%
% %% 7.130
% fun {Minuso N M K}
% {Addero 0 M K N}
% end
%
% %% 7.131
% {Browse 131#
% {SolveAll
% fun {$} Q in
% _ = {Minuso [0 0 0 1] [1 0 1] Q}
% Q
% end}}
%
% %% 7.132
% {Browse 131#
% {SolveAll
% fun {$} Q in
% _ = {Minuso [0 0 1] [0 1 1] Q}
% Q
% end}}
%
% %% 7.133
% {Browse 133#
% {SolveAll
% fun {$} Q in
% _ = {Minuso [0 1 1] [0 0 0 1] Q}
% Q
% end}}
|