Thanks in advance, and apologies for any errors or anything confusing about my post.
I am getting errors with the tree traversal examples in section 3.4.6 of " Concepts, Techniques, and Models of Computer Programming ". I am using Oz / mozart2-2.0.0-alpha.0 (+build.4091-slitaz-1.01.ova).
I am entering the below procedures and functions exactly as they are in the book (two versions of the book, with slightly different code) and getting errors when I try to execute. I've tried fixing them myself, but cannot get anywhere so far. I'll give the code, execution statements, errors, and a test tree declaration (which seems to be valid as I can execute {LookUp}, {Insert} and {Delete} on it without issue) below. I'll include more notes as I think necessary, below..
So, my question is what is wrong with these bits of code or how I am using them or with my trees? I included a function and three procedures all giving the same issue to be complete (and maybe help troubleshooting), but I think the solution is the same for all.
Tree declaration is last, below.
THE CODE -->
%All of the below errors occur upon execution, not on definition of the proc or function
% version: VanRoyHaridi2003-book.pdf
% section 3.4.6 - "Trees","Tree Traversal", "Depth-first traversal
% p.159 (Adobe Reader p. 202 of 939)
declare
proc {DFS T}
case T
of leaf then skip
[] tree(Key Val L R) then
{DFS L}
{Browse Key#Val}
{DFS R}
end
end
{DFS S}
/*
%******************** Error: conditional failed *****************
%**
%** Missing else clause
%**
%** Matching: tree(key:250 left:tree(key:125 left:tree(key:60 left:tree(key:30 left:leaf right:leaf value:pyramid) right:tree(key:90 left:leaf right:leaf value:cube) value:sphere) right:tree(key:185 left:tree(key:155 left:leaf right:leaf value:wave) right:tree(key:215 left:leaf right:leaf value:plane) value:shadow) value:shape) right:tree(key:375 left:tree(key:315 left:tree(key:285 left:leaf right:leaf value:boing) right:tree(key:345 left:leaf right:leaf value:ring) value:tap) right:tree(key:435 left:tree(key:405 left:leaf right:leaf value:whoosh) right:tree(key:465 left:leaf right:leaf value:ping) value:boom) value:sounds) value:treetop)
%** in file "/mnt/host_folder/trees - traversals", line 39
%**
%** Call Stack:
%** procedure 'DFS' in file "/mnt/host_folder/trees - traversals", line 33, column 1, PC = -1279897415
%**--------------------------------------------------------------
*/
% version: CTMchapters1-3.pdf, "Tree Traversal" p.155 (Adobe Read p. 181 of 226)
% section 3.4.6.2, "Tree Traversal"
declare
proc {DFS T}
case T
of leaf then skip
[] tree(Key Val L R) then
{Browse Key#Val}
{DFS L}
{DFS R}
end
end
{DFS S}
% {DFS T} version two had the same error as the 1st version
% I know they are trivially different, but included it anyway... sorry
% Same page as {DFS T} in CTMchapters1-3.pdf (only).
declare
proc {DFSAccLoop T S1 ?Sn}
case T
of leaf then Sn=S1
[] tree(Key Val L R) then S2 S3 in
S2=Key#Val|S1
{DFSAccLoop L S2 S3}
{DFSAccLoop L S3 Sn}
end
end
fun {DFSAcc T} {Reverse {DFSAccLoop S nil $}} end
{Browse {DFSAcc S}}
/*
%******************** Error: conditional failed *****************
%**
%** Missing else clause
%**
%** Matching: tree(key:250 left:tree(key:125 left:tree(key:60 left:tree(key:30 left:leaf right:leaf value:pyramid) right:tree(key:90 left:leaf right:leaf value:cube) value:sphere) right:tree(key:185 left:tree(key:155 left:leaf right:leaf value:wave) right:tree(key:215 left:leaf right:leaf value:plane) value:shadow) value:shape) right:tree(key:375 left:tree(key:315 left:tree(key:285 left:leaf right:leaf value:boing) right:tree(key:345 left:leaf right:leaf value:ring) value:tap) right:tree(key:435 left:tree(key:405 left:leaf right:leaf value:whoosh) right:tree(key:465 left:leaf right:leaf value:ping) value:boom) value:sounds) value:treetop)
%** in file "/mnt/host_folder/trees - traversals", line 67
%**
%** Call Stack:
%** procedure 'DFSAccLoop' in file "/mnt/host_folder/trees - traversals", line 61, column 1, PC = -1239512161
%** procedure 'DFSAcc' in file "/mnt/host_folder/trees - traversals", line 70, column 1, PC = -1239496575
%** toplevel abstraction in line 1, column 0, PC = -1238883005
%**--------------------------------------------------------------
*/
% One of the versions of {LookUp X T} gives the same error.
% version: CTMchapters1-3.pdf, "Tree Traversal" p.152 (Adobe Read p. 178 of 226)
% section 3.4.6.2, "Storing information in trees"
declare
fun {Lookup X T}
case T
of leaf then notfound
[] tree(Y V T1 T2) then
if X<Y then {Lookup X T1}
elseif X>Y then {Lookup X T2}
else found(V) end
end
end
/*
%******************** Error: conditional failed *****************
%**
%** Missing else clause
%**
%** Matching: tree(key:horse left:tree(key:dog left:tree(key:cat left:leaf right:leaf value:chat) right:tree(key:elephant left:leaf right:leaf value:elephant) value:chien) right:tree(key:mouse left:tree(key:monkey left:leaf right:leaf value:singe) right:tree(key:tiger left:leaf right:leaf value:tigre) value:souris) value:cheval)
%** in file "/mnt/host_folder/Lookup Insert Delete", line 37
%**
%** Call Stack:
%** procedure 'Lookup' in file "/mnt/host_folder/Lookup Insert Delete", line 31, column 1, PC = -1241765194
%** toplevel abstraction in line 1, column 0, PC = -1241110606
%**--------------------------------------------------------------
*/
% the case version works, so I was suprised when the traversals using case are not working for me.
declare
fun {Lookup K T}
case T of leaf then notfound
[] tree(key:X value:V left:T1 right:T2) andthen X==K then found(V)
[] tree(key:X value:V left:T1 right:T2) andthen X<K then {Lookup K T2}
[] tree(key:X value:V left:T1 right:T2) andthen X>K then {Lookup K T1}
end
end
% There are two test trees here
declare
S=tree(key:250 value:treetop
left:tree(key:125 value:dash
left:tree(key:60 value:sphere
left:tree(key:30 value:pyramid left:leaf right:leaf)
right:tree(key:90 value:cube left:leaf right:leaf))
right:tree(key:185 value:shadow
left:tree(key:155 value:wave left:leaf right:leaf)
right:tree(key:215 value:plane left:leaf right:leaf)))
right:tree(key:375 value:hum
left:tree(key:315 value:tap
left:tree(key:285 value:boing left:leaf right:leaf)
right:tree(key:345 value:ring left:leaf right:leaf))
right:tree(key:435 value:boom
left:tree(key:405 value:whoosh left:leaf right:leaf)
right:tree(key:465 value:ping left:leaf right:leaf))))
T=tree(key:horse value:cheval
left:tree(key:dog value:chien
left:tree(key:cat value:chat left:leaf right:leaf)
right:tree(key:elephant value:elephant left:leaf right:leaf))
right:tree(key:mouse value:souris
left:tree(key:monkey value:singe left:leaf right:leaf)
right:tree(key:tiger value:tigre left:leaf right:leaf)))
{Browse S}
{Browse T}
Looking at your first program: your declaration of tree is wrong, as you can see the compiler cannot match your tree with any of the clauses defined in the case structure, for example for the first program you are trying to match something in this form (simplified form of your declaration):
S=tree(key:250 value:treetop left:leaf right:leaf)
with this clauses:
of leaf then skip
[] tree(Key Val L R)
S can't match neither with leaf nor with the second, as Key can't match with key:250 so the compiler gives you that error.
You can declare your tree as:
S = tree(250 treetop tree(120 foo leaf leaf) tree(100 foo2 leaf leaf))
You can fix now accordingly to this the other programs..