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?
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?
-Andy
Zeige Antworten nach Diskussionsstrang
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
Hi Wolfgang,
Thank you very much for the detailed reply, especially for so clearly describing the rules for defaulting type variables.
One thing I could have made clearer is that I'm writing a compiler, so the parts you refer to as the "compiler's business" are also my business. This means I really do need to transform the goal, inspect its type, and, if necessary, supply dictionaries for defaulted type variables.
To do this, my system needs the ability to perform type queries. I dug around the PAKCS implementation to see how it does so and found that it just calls the frontend to generate interface (.icurry) files and then parses those. I should be able to follow a similar approach.
-Andy
-----Original Message----- From: Wolfgang Lux wolfgang.lux@gmail.com Sent: Saturday, May 18, 2019 7:26 AM To: Andy Jost Andrew.Jost@synopsys.com Cc: curry@lists.RWTH-Aachen.DE Subject: Re: [curry] Choosing default instances in Curry
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://urldefense.proofpoint.com/v2/url?u=https-3A__hub.darcs.net_wlux_type... 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
Hi Andy,
the good news (maybe for you as a compiler writer) is that PAKCS does not know very much about type classes. Since type classes are added as dictionaries by the front end, the FlatCurry code compiled by PAKCS has a structure identical to the previous code, i.e., when type classes had been added, no change was necessary in the compiler itself.
The only changes have been done in the interactive REPL to hide the details of type classes to the user. Thus, if the top-level expression to be evaluated has some type class context, an explicit concrete type annotation is added (Float in case of Fractional, Int in case of Num or Integral).
And you are right: in order to get the type of the main expression, PAKCS calls the front end and reads the resulting FlatCurry file.
More details about the implementation of type classes are in Finn Teegen's master thesis (written in German). Maybe Finn can send some comments (currently, he is on a business trip).
Best regards,
Michael
On 5/18/19 10:24 PM, Andy Jost wrote:
Hi Wolfgang,
Thank you very much for the detailed reply, especially for so clearly describing the rules for defaulting type variables.
One thing I could have made clearer is that I'm writing a compiler, so the parts you refer to as the "compiler's business" are also my business. This means I really do need to transform the goal, inspect its type, and, if necessary, supply dictionaries for defaulted type variables.
To do this, my system needs the ability to perform type queries. I dug around the PAKCS implementation to see how it does so and found that it just calls the frontend to generate interface (.icurry) files and then parses those. I should be able to follow a similar approach.
-Andy
-----Original Message----- From: Wolfgang Lux wolfgang.lux@gmail.com Sent: Saturday, May 18, 2019 7:26 AM To: Andy Jost Andrew.Jost@synopsys.com Cc: curry@lists.RWTH-Aachen.DE Subject: Re: [curry] Choosing default instances in Curry
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://urldefense.proofpoint.com/v2/url?u=https-3A__hub.darcs.net_wlux_type... 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
curry mailing list -- curry@lists.rwth-aachen.de To unsubscribe send an email to curry-leave@lists.rwth-aachen.de https://lists.rwth-aachen.de/postorius/lists/curry.lists.rwth-aachen.de
Hi Andy,
I guess, there is not much for me to add. Although the front end does support defaulting analogous to Haskell, the REPLs of both PAKCS and KiCS2 implement their own defaulting mechanism because, among other things because of the printing of free variables. I don't know how the MCC uses defaulting for its REPL, it might be worth a look.
Regards, Finn
On 20/05/19 18:44, Michael Hanus wrote:
Hi Andy,
the good news (maybe for you as a compiler writer) is that PAKCS does not know very much about type classes. Since type classes are added as dictionaries by the front end, the FlatCurry code compiled by PAKCS has a structure identical to the previous code, i.e., when type classes had been added, no change was necessary in the compiler itself.
The only changes have been done in the interactive REPL to hide the details of type classes to the user. Thus, if the top-level expression to be evaluated has some type class context, an explicit concrete type annotation is added (Float in case of Fractional, Int in case of Num or Integral).
And you are right: in order to get the type of the main expression, PAKCS calls the front end and reads the resulting FlatCurry file.
More details about the implementation of type classes are in Finn Teegen's master thesis (written in German). Maybe Finn can send some comments (currently, he is on a business trip).
Best regards,
Michael
On 5/18/19 10:24 PM, Andy Jost wrote:
Hi Wolfgang,
Thank you very much for the detailed reply, especially for so clearly describing the rules for defaulting type variables.
One thing I could have made clearer is that I'm writing a compiler, so the parts you refer to as the "compiler's business" are also my business. This means I really do need to transform the goal, inspect its type, and, if necessary, supply dictionaries for defaulted type variables.
To do this, my system needs the ability to perform type queries. I dug around the PAKCS implementation to see how it does so and found that it just calls the frontend to generate interface (.icurry) files and then parses those. I should be able to follow a similar approach.
-Andy
-----Original Message----- From: Wolfgang Lux wolfgang.lux@gmail.com Sent: Saturday, May 18, 2019 7:26 AM To: Andy Jost Andrew.Jost@synopsys.com Cc: curry@lists.RWTH-Aachen.DE Subject: Re: [curry] Choosing default instances in Curry
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://urldefense.proofpoint.com/v2/url?u=https-3A__hub.darcs.net_wlux_type... 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
curry mailing list -- curry@lists.rwth-aachen.de To unsubscribe send an email to curry-leave@lists.rwth-aachen.de https://lists.rwth-aachen.de/postorius/lists/curry.lists.rwth-aachen.de
curry mailing list -- curry@lists.rwth-aachen.de To unsubscribe send an email to curry-leave@lists.rwth-aachen.de https://lists.rwth-aachen.de/postorius/lists/curry.lists.rwth-aachen.de
Am 27.05.2019 um 17:53 schrieb Finn Teegen fte@informatik.uni-kiel.de:
Hi Andy,
I guess, there is not much for me to add. Although the front end does support defaulting analogous to Haskell, the REPLs of both PAKCS and KiCS2 implement their own defaulting mechanism because, among other things because of the printing of free variables. I don't know how the MCC uses defaulting for its REPL, it might be worth a look.
All defaulting in MCC is done by the type checker. And since MCC implements a value restriction for reasons of type soundness, the types of all free variables as well as the type of the goal itself are forced to be monomorphic. So there won't be any overloaded type remaining to be resolved at runtime.
Wolfgang
-
Andy Jost -
Finn Teegen -
Michael Hanus -
Wolfgang Lux