Re: [Caml-list] looping recursion

[skaller <skaller@users.sourceforge.net>]

On Wed, 2004-07-28 at 10:38, John Prevost wrote:

> 
> exception Boom2 of int
> 
> let rec loop2 x =
>   try
>     if x < 100 then loop2 (x + x) else raise (Boom2 0)
>   with Boom2 y -> raise (Boom2 (y + 1))
> 
> let use_loop2 x = try loop2 x with Boom2 y -> y
> 
> In this second example, use_loop2 is using the exceptions in loop2 to
> calculate the result.  (Admittedly, this is a bizarre little setup.)

I'm actually doing something like this (unfortunately)
in the Felix compiler.

Basically, Felix has overloading and requires the function
argument type to be specified, but the return type is deduced
bottom up by actually examining the function's return statement
argument type.

Unfortunately, this situation is complicated by the fact
a function can call itself. However, we cant just plug in
a type variable for the function's return type, calculate
the result, and then unify to eliminate the variable,
as Ocaml could, because in Felix functions can be overloaded.
So to calculate in function f, what the type of f(a) is,
we again have to do overload resolution. Having done that
we need the return type of the function .. but we can't
calculate it because that's what we're already in the middle
of doing, and we'd get an infinite loop.

you might think a type variable could be introduced here,
and eliminated when we pop back, but that isn't so.
The problem is we might have in f:

   return g (f a);

and now, the recursion isn't tail, and we have to have
a definite type for f a, in order to calculate which g
is called, in order to calculate the type of f.

So I just throw an exception and ignore that return statement.
Such recursions (in the client Felix code) usually 
have conditionals wrapped around them and one branch 
had better give a result: otherwise
the client must specify the return type.

[I suspect in terminating code this cannot be needed but
I'm not sure]

the actual algorithm unifies the specified return
type (if given) with all the types of return
statements (which don't lead to infinite recursion).

I have tried to localise exception handling in my
code but this is one case where I couldn't figure
out how to do so. It is of course vital that
the exception handlers stack up here, so the exceptions
propagate far enough but no further.

[The code is extremely messy and I'm not even sure it 
gives the correct result when it does succeed :]

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners