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

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

On Mon, 2004-05-03 at 18:58, Marcin 'Qrczak' Kowalczyk wrote:

> (The primary example is C++ where evaluation of constant expressions
> can influence parsing of further parts, with name resolution and type
> checking and template instantiation sitting between so they are also all
> mutually recursive. I have no idea how to sanely organize a C++
> compiler.)

Neither did any of the C++ compiler writers for at least 15 years.

> Hmm. This probably depends on the language. Mine doesn't have anything
> which requires far "phase lookahead". 

Felix is statically typed, everything is recursive,
recursive types are supported, it has generics,
overloading by selecting the most specialised 
function (like C++). Whilst a function parameter
must be annotated with a type, the return type
doesn't need to be given (usually:). 

Also 'typeof(e)' is allowed.. including for
function parameter types ...

To solve this algebraically I think I'd need
meta-sums: the type of an overload 

	f: int -> 'a
	f: long -> 'b

would be something like:

	int of 'a | long of 'b

so that

	f x

would be typed:

	typematch typeof(x) with 
	| int 'a -> 'a
	| long 'b -> ;b


I actually support such type terms as well as lambda abstractions.
>From the std library:

  typedef fun dom(t:TYPE):TYPE = 
    typematch t with
    | ?a -> _ => a
    endmatch
  ;

Note that dom isn't a total function, and so this isn't
entirely parametric polymophism: the construction clearly
allows for partial specialisations .. :)

However the overload resolution doesn't use this stuff
(I'm not sure how to do all the reductions).

Anyhow there is a central 'bottleneck', lookup,
where all the nesting and recursion is unravelled.
Thereafter everything is flat and fully bound,
and much easier to work with..

.. data flow analysis will be a breeze by comparison :D

> The only troublesome part wrt. the order was possible recursion among
> definitions in a block. All definitions are potentially mutually
> recursive,

Same in Felix

>  and using a name before its definition has been executed, in
> any other way than attaching it to a closure, is an error, by necessity
> sometimes detected only at runtime.

In Felix this can't be a problem for functions, only for
variables. Unlike Ocaml, 

	fun f ...

declares a class, whilst

	let f x = ..

in Ocaml constructs a value. Ocaml's f is a closure immediately,
Felix's is just a C++ class. The class gets instantiated
on use, so direct calls are never a problem. Neither is intermodule
recursion. uninitialised variables are possible though: 
I just blame the programmer :D

> The duplication was getting ugly. 

I know the feeling, except in my case 'multiplication' would
be more precise than mere 'duplicaton' :)

> So my solution was to analyze each sequence of definitions in two
> mini-phases, with an explicit representation between them. 

Right. Hence your comment in a previous email: you've got
an intermediate representation (ugly) but it's localised
enough to be sensible in some way, for example linear.

> > Interested in how you handle tail calls in C.
> 
> The portable variant uses the well-known trampoline style, where each C
> function returns a pointer to the next function to jump into. The stack
> is managed explicitly. 

That's what Felix does for procedures (except I'm using heap
store for stack frames). I can now convert tail procedure calls
into gotos. But I do no such thing for functions, they just
run on the stack (even though their stack frames are heap allocated,
the return addresses are not).

> But for x86 I process the assembler output of gcc
> and convert code which returns an address (marked with a comment in asm)
> with a jump. This increased performance by about 30%.

Ah. Inline asm tricks  .. been thinking of that. 

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