[TYPES] A question about the literature on monomorphisation

[Kalani Thielen]

I think that the print copy has this section that isn’t anywhere online.  I can’t verify at the moment though, because I gave my print copy to a friend.

Our PL at Morgan Stanley is https://github.com/Morgan-Stanley/hobbes/ <https://github.com/Morgan-Stanley/hobbes/>, basically an eager variant of Haskell with structural types (and a few other features useful in our area).  We monomorphise code to avoid penalties for polymorphism/overloading (we are very sensitive to pre-trade latency).

The approach here (and IIRC the same way Mark Jones described it) is to say that only monomorphic constraints can be satisfied, and that satisfied constraints are eliminated by rewriting qualified expressions into equivalent expressions without qualification (e.g. show(42) :: Show int => [char] — rewrites to —> showInt(42) :: [char]).  That winds up being an API for user code to define new ways to resolve constraints (e.g. network RPC, where connections are made and protocols negotiated at “compile time”).

It looks a little different than your example, and there’s more going on than just monomorphisation, but the kind of nested polymorphism you describe gets “flattened out” and we generate hidden type classes (e.g. List<A> { List<B> map(A->B) } would be in a subclass from List<A> { String toString() } to add the additional type variable).  On the back end we wind up with a lot of tiny type classes with long parameter lists.

HTH, sorry if I’ve taken a tangent.  :)



> On Mar 30, 2020, at 10:36 AM, Philip Wadler <wadler at inf.ed.ac.uk> wrote:
> 
> Thanks. I downloaded a copy of Mark's thesis from here:
>     https://www.cs.ox.ac.uk/files/3432/PRG106.pdf <https://www.cs.ox.ac.uk/files/3432/PRG106.pdf>
> 
> It refers to the "monomorphism restriction" a few times, but I cannot find a reference to "monomorphisation". Can you say which sections you had in mind?
> 
> If you have an example of monomorphisation for the Morgan Stanley PL you mention that is similar to the example in my original question, I would love to see it. Is your PL described publicly anywhere?
> 
> Cheers, -- P
> 
> .   \ Philip Wadler, Professor of Theoretical Computer Science,
> .   /\ School of Informatics, University of Edinburgh
> .  /  \ and Senior Research Fellow, IOHK
> . http://homepages.inf.ed.ac.uk/wadler/ <http://homepages.inf.ed.ac.uk/wadler/>
> 
> 
> 
> On Thu, 26 Mar 2020 at 18:22, Kalani Thielen <kthielen at gmail.com <mailto:kthielen at gmail.com>> wrote:
> Mark Jones’s dissertation on qualified types has a useful section on monomorphisation near the end.  In that context it was to eliminate type constraints (e.g. type classes) by rewriting, so resolving overloading and monomorphising at the same time.  Polymorphic definitions without qualifications and nested definitions can be handled the same way if you don’t mind generating hidden constraints/classes.  This is the route we took at Morgan Stanley for a PL we use internally.
> 
> HTH
> 
> 
>> On Mar 26, 2020, at 2:10 PM, Philip Wadler <wadler at inf.ed.ac.uk <mailto:wadler at inf.ed.ac.uk>> wrote:
>> 
>> The bookkeeping required to formalise monomorphisation of instances
>> and methods is not too difficult, but not trivial---it took us several
>> tries to formalise it for a different language.
>> 
>> The question is, where has this been described in the literature?
>> Below is a list of the references we have found on monomorphisation,
>> but none of them seems to cover the specific problem of
>> monomorphisation of generic methods within generic interfaces, as
>> described above, even though that combination occurs in several
>> languages.  Have we missed any relevant literature?
> 
> The University of Edinburgh is a charitable body, registered in
> Scotland, with registration number SC005336.