[mercury-users] literature polymorphic recursive calls

[Tom Schrijvers]

On Tue, 21 Jun 2005, Ralph Becket wrote:

> Tom Schrijvers, Tuesday, 21 June 2005:
> > > Hi Tom,
> > >      My memory is fading, but I think the book on Clean called "Functional
> > > Programming and Parallel Graph Rewriting", which is (was?) available at the
> > > Clean web site, has a discussion of the type checking algorithm of Clean
> > > which includes a discussion of Hindley-Milner vs Milner-Mycroft, if that's
> > > what you mean. Perhaps that's relevant?
> >
> > Thanks a lot, Brian! This seems like a very good starting point for my
> > purpose.
>
> I'm curious: I thought the only difference between HM and MM was that
> the latter also had rules for predicates and logical connectives?

What I got from the above document is that the basic type system of H. B.
Curry cannot deal with recursive definitions (recursive calls).  The type
inference algorithm has to be iterated until recursive call types are
instances of the definition types, but this may be infinite in some cases.
The solution of Hindley-Milner is to require recursive calls to have
exactly the same type as the definition (monomorphic recursive calls). The
Mycroft approach is to require explicit type annotations to resolve
recursive definitions. Both approaches can be combined of course: use
annotation if it is available and otherwise assume monomorphic recursive
calls. Both solution only do one iteration. I guess Mercury takes a third
approach: it does multiple iterations to handle some non-problematic
recursive definitions. What happens if the limit is reached? I should try
it :)

Tom

--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------