Hi Andy Jost <Andrew.Jost@synopsys.com>
I’m trying to understand the implementation of typeclasses in Curry so that I can implement them in my compiler. Is there some documentation describing how dictionaries are implemented, including the naming conventions used?
there's a bit of documentation in the MCC implementation inside the DictTrans module here: https://hub.darcs.net/wlux/type-classes/browse/DictTrans.lhs It seems that the pakcs and KiCS2 implementations are at least inspired from that implementation.
One problem I face is knowing how to choose default instances. For example, the program “main = 1 + 1” translates to the following FlatCurry:
program "test" import "Prelude" function "test.main" 1 lhs_vars [1] Node "Prelude.apply" ( Node "Prelude.apply" ( Node "Prelude.+" ( var 1 ) , Node "Prelude.apply" ( Node "Prelude.fromInt" ( var 1 ) , int 1 ) ) , Node "Prelude.apply" ( Node "Prelude.fromInt" ( var 1 ) , int 1 ) )
Function “main” expects an implicit argument that is an instance of Prelude.Num. This is because no type declaration was specified, so its type is “Num a => a”. If I were to declare main as having a concrete type such as Int or Float, then it would take no arguments.
KiCS2 and PAKCS can run this program, so they must somehow choose a default instance. How is this done?
I’m especially bothered that the FlatCurry appears to be missing crucial information – i.e., the fact that “main” expects a Num instance is not mentioned in the FlatCurry. How do other Curry implementations know to pass a Num dictionary and how is the default instance chosen?
Please note that strictly speaking main is not a program but an initial goal. When you evaluate a goal the compiler really generates a program from the initial goal that you've provided to it and it uses the goal's type to determine how to do that. If the type of the goal is something like IO t, the program would simply execute the IO action denoted by the goal, otherwise the compiler generates a program that effectively runs some elaborate variant of the expression (AllSolutions.getAllValues main >>= mapIO_ print) for your main function. Incidentally, Haskell purposefully restricts the main function of a program to have type IO t. Given that the compiler is involved creating a program from your initial goal it is always clear that your main function is an overloaded function, so the FlatCurry translation is not missing any information. And the strategy above also explains how the dictionary to be passed to be main function is determined: It's the standard defaulting rule for ambiguous types inherited from Haskell. An ambiguous type is a type (C1 tv1, ..., Cn tvn) => ty where one or more of the type variables tv1, ... tvn do not appear in the type ty. And the rules here are that if one of the type classes C1, ... Cn is Frac or a subclass, the type is defaulted to Float (Double in Haskell, but Curry has eschewed the distinction between single and double precision floats). Otherwise, if it is Num or a subclass the corresponding type would be defaulted to Integer. If neither is the case you'll get an ambiguous type error when attempting to evaluate the goal. So applying this to your main function, the compiler would create a program that attempts to execute the IO action AllSolutions.getAllValues main >>= mapIO_ print, whose type would be the ambiguous type Num a => IO (). Since a appears in a Num a constraint, the type variable a then gets defaulted to Integer. The default types may be changed with a default declaration (at least in Haskell and for MCC; not sure if those are available in packs or kics) but it is not clear how those would apply to the initial goal. But then, it would be the compiler's business to figure that out anyway. Hope this helps, Wolfgang