cond revisited

[Thomas Lindgren]

The current proposal for cond has a variable binding
rule I have found unsatisfying:

in the following pseudo-code

cond Expr1 -> Body1; Rest end

this is translated basically into a nested case:

case Exprs1 of
   true -> Body1;
   false -> <rest of code>
end

But this means the bindings made in Exprs1 are seen
not only in Body but also in Rest (ie, all subsequent
clauses). I find this unintuitive, so I would like to
propose a translation of cond into case which avoids
this problem*. Here we go.

Assume that we have

cond Exprs -> Body; Rest_clauses end

1. We first compute the variables exported from Exprs
into Body (and afterwards) as X1,...,Xn.

2. We then take advantage of a property of fun:s, that
they do not export variable bindings at all. So we
can write

(fun() -> Exprs end)()

which evaluates Exprs without exporting any variable
bindings. Note that the extra (fun ..)() call easily
can be removed at compile time, so there is no extra
cost.

If we were content with not exporting variables from
Exprs to Body at all, we could stop with that. But
Richard Carlsson has convinced me that this was not
enough. If we DID stop, we would simply get

   case (fun() -> Exprs end)() of 
      true -> Body; 
      ... 
   end

but to get the variable bindings out, we need to do a
bit more.

3. Since we want X1,...,Xn to be visible in Body, we
then ensure that they are passed correctly.

Let CondGuard be the code:

(fun() ->
   case Exprs of
      true -> {true, X1,...,Xn};
      false -> false
   end)()

The above expression is then wrapped in the following:

case CondGuard of
   {true, X1,....,Xn} -> Body;
   false -> <code for Rest_clauses>
end

This ensures that the variables X1,...,Xn are seen
only in Body. The final clause of the cond can look
like

case ...
  ...
  false -> exit(cond_clause)
end

That's all. The translation is a bit more involved
than the one currently used, and the compiler will
have to work a bit harder. But note that this can
compile to *quite efficient* code after some
simplifications have been done.

A barebones example:

cond
   X = f(A), Y = g(B), X =< Y -> h(X,Y);
   X = f(A,B), Y = g(A,B), X > Y -> i(X,Y)
end

becomes (omitting begin ... end pairs)

case (fun() -> case X = f(A), Y = g(B), X =< Y of
                   true -> {true,X,Y};
                   false -> false
     )() of
   {true, X, Y} -> h(X,Y);
   false ->
      case (fun() -> 
             case X = f(A,B), Y = g(A,B), X > Y of
                true ->
                   {true, X, Y};
                false ->
                   false
             end)() of
         {true, X, Y} -> i(X,Y);
         false -> exit(cond_clause)
      end
end

which can quickly be simplified by beta reduction and
case-of-case optimization into

case X1 = f(A), Y1 = g(B), X1 =< Y1 of
   true ->
     {true, X, Y} = {true, X1, Y1}, h(X,Y);
   false ->
      case X2 = f(A,B), Y2 = g(A,B), X2 > Y2 of
         true ->
            {true, X, Y} = {true, X2, Y2}, i(X,Y);
         false ->
            exit(cond_clause)
      end
end

The compiler then simplifies the matching of
{true,...} and eliminates the copies. You end up with
basically the case-statement you would have written by
hand. And there you are.

Best,
Thomas



	
		
__________________________________ 
Yahoo! Mail - PC Magazine Editors' Choice 2005 
http://mail.yahoo.com