Re: Polymorphic recursion 9Was Re: [Caml-list] Doubly-linked list)

[John Max Skaller <skaller@ozemail.com.au>]

Diego Olivier Fernandez Pons wrote:

> John Max Skaller a écrit :
> 
> 
>>I'm confused. I think you mean *type inference* is difficult
>>if you want polymorphic recursion?
>>
> 
> I'am confused too. We do want type inference, do we not ? And
> polymorphic recursion makes type inference undecidable. 


I thought type inference was already of such worst case
complexity that it is effectively equivalent to undecidable :-)
In practice, this is rarely a problem I believe.

In any case, I'd rather more generality than a guarrantee of
type inference: annotating function arguments when necessary
isn't that onerous is it?

> - Haskell allows full polymorphic recursion but requires providing
> explicitly a type signature (in fact, in Haskell you always provide
> type annotations even if it is not required)


Felix requires annotation too, because it also provides overloading
(and therefore it is often necessary). This definitely
makes function signatures more difficult to write, but it
allows more intuitive calling.

Felix is lower order (less emphasis on higher order things)
than Ocaml, so it is surprising that these higher order things
are actually *easier* to support in the compiler
(bottom up deduction is efficient, but it gets quite nasty
with overloading added in .. sometimes return types
have to be declared too)

It seems the advantages of full inference lessen both
as one tries for a lower order language (like Felix)
or a higher order language (like Haskell): inference
is maximally useful 'in between'. Most Ocaml programs
do live 'in between', but there is another fact:
annotating functions 'in between' is not much of a burden.

So we gain most advantage from type inference for

a small class of functions whose types are moderately
complex: those of less complexity are easy to annotate,
and those of more complexity cannot be easily annotated
OR computed.

I wonder if it is possible to find out how popular
this class of functions is in actual usage?

Can we see some cases where inference provides

a definitive advantage? [I have seen some before ..
they certainly exist]


-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850


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