raould <raould@[EMAIL PROTECTED]
> writes:
> Not that you need such a hack since there seems to have been a slew of
> folks coming up with extentions to HM that play nice. But I was
> wondering if one could approximate
>
> /* horrible pseudocode */
> id x = x : 'a -> 'a.
> foo i:int s:string = Pair(id i, id s) : int -> string ->
> Pair(int,string).
>
> in regular old non-System-F supporting HM systems by generating (sorta
> like C++ template expansion) a new version of id for every type it is
> applied to in foo. Sort of a macro expansion.
That is basically how the MLTon compiler implements polymorphism.
Note that the restrictions of the Hindley-Milner type system (in
particular, absense of polymorphically recursive functions) ensures
that there will only be a finite number of instances of any function.
This can be quite large, though. Also, you lose separate compilation,
as you can't compile a polymorphic function until you know which
instances it is applied to. The best you can do is to type-check the
function and, possibly, generate some type-agnostic intermediate code
that makes compilation to specific types faster.
C++ templates support polymorphic recursion, so template instantiation
can be (and sometimes is) infinite. Hence, an arbitrary limit on the
number of instances is typically imposed by a C++ compiler. C++ has
the added disadvantage that you can't even type-check a template until
it is instantiated (and then only for this specific instance).
Most functional language compilers don't do this kind of multiple
instantiation but instead exploit that polymorphic functions don't
need to access the polymorphic data so, as long as the size of the
polymorphic data is the same, the same code can work on any type.
Hence, the compilers ensure that all data has the same size (typically
one machine word), storing larger data in the heap and just keep a
pointer to it in a register or stack slot. Hence, you need only one
copy of each polymorphic function and you can compile this in advance
without knowing which future instances it will be applied to. The
disadvantage is that you need to store more things in the heap.
For simple and fast compilers and small code, I would chose the latter
implementation, but for fast generated code I would choose specialised
instantiations like MLTon.
Torben
|
