In the early days of Ada, some thought was given to using block statements with
locally declared exceptions to simulate Zahn's construct (discussed startimg on
page 275 of the Knuth article). This construct provides not only for
multilevel exit from within any construct, but also for different actions to be
performed upon exit from the construct, depending on the point from which the
construct was exited.
The following is an Ada paraphrase of Knuth's Example 5b (from page 276 of the
Computing Surveys article):
declare
Left_Leaf_Hit, Right_Leaf_Hit: exception;
begin
loop
if X < Node.Data then
if Node.Left_Child = null then
raise Left_Leaf_Hit;
else
Node = Node.Left_Child;
end if;
else
if Node.Right_Child = null then
raise Right_Leaf_Hit;
else
Node = Node.Right_Child;
end if;
end if;
end loop;
exception
when Left_Leaf_Hit =>
Node.Left_Leaf := new Tree_Node'(X, null, null);
when Right_Leaf_Hit =>
Node.Right_Leaf := new Tree_Node'(X, null, null);
end;
For this idiom to have become practical, compilers would have had to recognize
that,for exceptions declared and handled locally, a raise statement can be
translated into a branch rather than a call on a run-time stack-unwinding
routine. (In Ada 95, we have to worry about finalization for any inner blocks
we are exiting. Even in Ada 83 we would have to wait for termination of all
tasks dependent on inner blocks we are exiting, so a compiler would have to
make sure there could be no such tasks before turning the run-time call into a
branch to the handler.)
In Ada, this particular example does not make a particularly compelling case
for Zahn's construct, since we could also write
loop
if X < Node.Data then
if Node.Left_Child = null then
Node.Left_Leaf := new Tree_Node'(X, null, null);
exit;
else
Node = Node.Left_Child;
end if;
else
if Node.Right_Child = null then
Node.Right_Leaf := new Tree_Node'(X, null, null);
exit;
else
Node = Node.Right_Child;
end if;
end if;
end loop;
(Knuth himself points out, in Example 5c, that different exit actions,
depending on the point from which you exit, can be moved to the point of
exit.) The relevant point here is that exceptions can be used to exit from
arbitrary deeply nested constructs, but the code is likely to be
disconcertingly inefficient unless the compiler has an eye out for this pattern.
-- Norman
|