On 21-Dec-1999, Gabor Greif <[EMAIL PROTECTED]> wrote:
> Some recent papers from Ross Paterson and Richard Bird [1] examine nested
> types and programming techniques associated with them. They use the
> extended typing discipline of Hugs with rank-2 polymorphism.
>
> My first question is where I can find documentation on implementing rank-2
> polymorphism. How is it done in Hugs and GHC?
I don't know exactly how it is done in Hugs and GHC.
But I imagine that code generation would be fairly straight-forward.
For higher-order terms with universally quantified polymorphic types,
the compiler would just pass the dictionaries for any type class
parameters when invoking the closure, rather than storing them
in the closure when it is created (as is done for ordinary
monomorphic higher-order terms).
> My understanding is that with nested datatypes an unbound number of
> distinct datatypes can be present even in a single value as opposed to
> regular datatypes where one value can be composed only of a limited number
> of types.
>
> I am asking because I have an experimental translation scheme in place that
> transforms regular polynomial datatypes into C++ (templated) types. This
> breaks down when nested datatypes arise, because an unbounded number of
> template instantiations have to be created.
Actually I think it should not be the nested data types themselves
that cause the problem. Rather, it is functions using polymorphic
recursion -- which you will of course need if you are to do anything
useful with your nested data types -- that are problematic.
The reason that the nested data types themselves should not cause a problem
is that declaring a pointer to a template class, e.g.
Foo<T> *p;
does not cause that template class Foo<T> to be instantiated.
So you could for example translate the nested data type
data Foo t = Foo (Foo (Pair t))
into
template <class T>
struct Foo {
Foo< Pair<T> > *arg;
};
You can create instances of this type
Foo <int> foo;
and this will not cause infinite template expansion -- yet.
It's only when you try to translate a function
that uses polymorphic recursion, e.g.
bar :: Foo t -> Int
bar (Foo x) = bar x
into C++ that you run into trouble:
template <class T>
int bar(Foo<T> bar_arg) {
return bar(*bar_arg.arg);
}
If bar ever instantiated, e.g. because somewhere else
there is a call to it, then the recursive call to bar() here
causes infinite template expansion.
(This is perhaps a silly example, because of course execution of
the function bar() will never terminate. But the result here is
that we're getting an error at link time, even if bar() is never
invoked at runtime. And there are other examples, slightly more
complicated, which do terminate but which exhibit the same
problem.)
Note that the same problem arises with functions that use
polymorphic recursion even if they don't make use of nested
types:
baz :: t -> Int
baz x = bar [x]
Here a simple translation of this into C++ will give you
something like this
template <class T> struct List {
T head;
List<T> *tail;
};
template <class T>
List<T> cons(T h, List<T>* t) {
List<T> l = { h, t };
return l;
}
template <class T>
int baz(T x) {
baz(cons(x, NULL));
}
and again we get infinite template expansion, resulting in an
error at link time, if there is any other call to baz().
> Since I intend to explore this
> translation too, I have to modify my target model.
>
> One way to pursue is to put (a reference to) the run-time representation of
> the nested type into (memory layout of) the value, and let the rank-2
> functions operate on the run-time representation of the type. Since this is
> not needed with values of regular type, this technique would put additional
> overhead on them, even if the generality of nested datatypes is not used in
> the function.
I suggest that rather than putting a representation of the nested type
into the value, instead pass a representation of the argument type as
an extra argument to any polymorphic recursive functions.
In other words, for polymorphic recursive functions, adopt the
standard dictionary passing approach that Hugs and ghc use.
You may also have to do the same for any polymorphic functions
called from functions using polymorphic recursion.
The only time that you need to put a representation of the type into
the value, rather than just passing it as an argument, is if you want to
handle *existential* types.
Anyway, here's some references. I hope they are helpful.
Cheers,
Fergus.
References
----------
[1]
@inproceedings{mpj94c,
author = {Mark Jones},
title = {Dictionary-free Overloading by Partial Evaluation},
booktitle = {ACM SIGPLAN Workshop on Partial Evaluation and
Semantics-Based Program Manipulation},
year = {1994},
month = {June},
publisher = {ACM SIGPLAN}
}
[2]
@inproceedings{peterson,
author = {John Peterson and Mark Jones},
title = {Implementing Type Classes},
booktitle = {Proceedings of ACM SIGPLAN Symposium on Programming
Language Design and Implementation},
year = {1993},
month = {June},
publisher = {ACM SIGPLAN}
}
[3] Type classes in Mercury. David Jeffery, Fergus Henderson and Zoltan Somogyi.
To appear in Proceedings of the 1999 Australian Computer Science conference.
Available on request. Earlier tech report version available via
<http://www.cs.mu.oz.au/mercury/information/papers.html>.
[4] Run time type information in Mercury.
Tyson Dowd, Zoltan Somogyi, Fergus Henderson, Thomas Conway and David Jeffery.
Proceedings of the International Conference on the Principles and Practice of
Declarative Programming, Paris, France, September/October 1999,
Lecture Notes in Computer Science, Springer-Verlag.
Available via <http://www.cs.mu.oz.au/mercury/information/papers.html>.
--
Fergus Henderson <[EMAIL PROTECTED]> | "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit"
PGP: finger [EMAIL PROTECTED] | -- the last words of T. S. Garp.
