Re: [Caml-list] [ANN] The Missing Library

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

On Mon, 2004-05-03 at 10:02, Marcin 'Qrczak' Kowalczyk wrote:
> W liście z czw, 29-04-2004, godz. 03:31 +1000, skaller napisał:
> 
> > I have quite a lot of 'multi-pass' phases in my Felix compiler
> > where i build temporary data structures in between.
> > 
> > I'd love to glue some of these together to eliminate building
> > whole data structures.
> 
> I'm not sure it's worth the trouble.

Neither am I, even given an easy way to do it.

>  There are two issues of compiler
> phases: organization and efficiency.
> 
> Concerning the organization, my opinion is that we do want to separate
> it into several small phases, so each pass becomes easier to manage.

How small though?

> Trying to do too much at once sometimes requires to recompute the same
> thing several times, because there is no convenient intermediate form
> to store it for reuse,

Oh, this is a perfect description of my horrible lookup algorithm!

Originally, it was decoupled, but it didn't work.
I've had to glue the whole thing together in a single operation
because everything is so mutually recursive.

For example: typing a function return value requires
binding all the return statement expressions, which
requires lookup, which requires binding all the
function names in the expression, which requires
overloading which requires binding the signatures
of all the candidate functions.. one of which could
be the original function you're trying to find
the type of, and if it's that one you need to find
its return types .. woops! That was the original problem :)

i would like to augment the system so calls of the form:

	f x y z

allow overloading on all arguments: at present you can
only overload on the first one. Seems easy .. just
extended application of the unification algorithm.
Only it requires determining the return type of f,
and not just the parameter type. The parameter type
must be specified .. the return type does not.

So I'd have to recursively calculate the return type.
which is already problematic (see above) .. which might
create yet another cycle if doing that called the overload
resolution routine again with the same arguments ..

I'm scared to even try it [There are 4 distinct entry points
to the algorithm, and 4 distinct 'exclusion' lists marking
them to prevent infinite recursion .. its never clear to me 
which list to reset and which one to push a new fixpoint onto,
nor is it clear what to do when a cycle is detected..

>  Also, lazy structures with some smart inversion of
> control flow typically introduce an overhead of creating many closures
> and calling many functions through pointers.

At one stage I rewrote the 'token filter' part of Vyper using
Ocaml streams. About 3 times slower I think.

>                                    | C coder which splits functions into
>                                    | fragments between calls (needed
>                                    | because of tail calls), 

Interested in how you handle tail calls in C.
In theory this is easy, using goto. Unfortunately
it requires generating a single massive function,
and gcc is too much of a toy compiler to really trust with that.

> The slowest part is currently the pretty printer.

The slowest part of Felix is the lookup algorithm
because of the really heavy (exponential time) recursion
and lack of proper memoisation.

-- 
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