* [Caml-list] elegant subtyping? @ 2011-11-04 13:06 Markus Weißmann 2011-11-04 13:27 ` Matthias Puech 2011-11-04 13:43 ` Pietro Abate 0 siblings, 2 replies; 6+ messages in thread From: Markus Weißmann @ 2011-11-04 13:06 UTC (permalink / raw) To: caml-list Hello everyone, I'm writing on a compiler and want to subtype the "statements" that can occur in my code: At first I have an abstract syntax tree that can hold any statement of the language. From that I create a control flow graph that will only have non-control-flow statements (a true subset of the Ast-statements). Whats the best way to realize that? Basically I have: module Ast: type statement = Assign | Guard | Goto | Label module Cfg: type statement = Assign | Guard I see three -- not so elegant -- solutions to this: 1.) type-safe but imho quite ugly code: module Cfg: type statement = Assign | Guard module Ast: type statement = Base of Cfg.statement | Goto | Label 2.) use the same type for both and give up the safety that wrong types cannot show up in the Cfg 3.) use objects Did I miss the type-safe, elegant, module-based solution somehow? Or is 1.) as good as it gets? Best regards -Markus -- Markus Weißmann, M.Sc. Institut für Informatik Technische Universität München Raum 03.07.054, Boltzmannstr. 3, 85748 Garching Tel. +49 (89) 2 89-1 81 05 Fax +49 (89) 2 89-1 81 07 mailto:markus.weissmann@in.tum.de ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] elegant subtyping? 2011-11-04 13:06 [Caml-list] elegant subtyping? Markus Weißmann @ 2011-11-04 13:27 ` Matthias Puech 2011-11-04 13:43 ` Pietro Abate 1 sibling, 0 replies; 6+ messages in thread From: Matthias Puech @ 2011-11-04 13:27 UTC (permalink / raw) To: caml-list Isn't that exactly what polymorphic variants are for? http://caml.inria.fr/pub/docs/manual-ocaml/manual006.html#toc36 Cheers, -m Le 11/04/2011 02:06 PM, Markus Weißmann a écrit : > Hello everyone, > > I'm writing on a compiler and want to subtype the "statements" that can > occur in my code: > At first I have an abstract syntax tree that can hold any statement of the > language. From that I create a control flow graph that will only have > non-control-flow statements (a true subset of the Ast-statements). > Whats the best way to realize that? > > Basically I have: > > module Ast: type statement = Assign | Guard | Goto | Label > module Cfg: type statement = Assign | Guard > > > I see three -- not so elegant -- solutions to this: > > 1.) type-safe but imho quite ugly code: > module Cfg: type statement = Assign | Guard > module Ast: type statement = Base of Cfg.statement | Goto | Label > > 2.) use the same type for both and give up the safety that wrong types > cannot show up in the Cfg > > 3.) use objects > > Did I miss the type-safe, elegant, module-based solution somehow? Or is > 1.) as good as it gets? > > > Best regards > > -Markus > ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] elegant subtyping? 2011-11-04 13:06 [Caml-list] elegant subtyping? Markus Weißmann 2011-11-04 13:27 ` Matthias Puech @ 2011-11-04 13:43 ` Pietro Abate 2011-11-04 14:12 ` Gabriel Scherer 1 sibling, 1 reply; 6+ messages in thread From: Pietro Abate @ 2011-11-04 13:43 UTC (permalink / raw) To: caml-list hello, using polymorphic variants maybe ? # module Cfg = struct type statement = [ `Assign | `Guard ] end;; module Cfg : sig type statement = [ `Assign | `Guard ] end # module Ast = struct type statement = [ Cfg.statement | `Goto | `Label ] end;; module Ast : sig type statement = [ `Assign | `Goto | `Guard | `Label ] end p On Fri, Nov 04, 2011 at 02:06:23PM +0100, Markus Weißmann wrote: > Hello everyone, > > I'm writing on a compiler and want to subtype the "statements" that can > occur in my code: > At first I have an abstract syntax tree that can hold any statement of the > language. From that I create a control flow graph that will only have > non-control-flow statements (a true subset of the Ast-statements). > Whats the best way to realize that? > > Basically I have: > > module Ast: type statement = Assign | Guard | Goto | Label > module Cfg: type statement = Assign | Guard > > > I see three -- not so elegant -- solutions to this: > > 1.) type-safe but imho quite ugly code: > module Cfg: type statement = Assign | Guard > module Ast: type statement = Base of Cfg.statement | Goto | Label > > 2.) use the same type for both and give up the safety that wrong types > cannot show up in the Cfg > > 3.) use objects > > Did I miss the type-safe, elegant, module-based solution somehow? Or is > 1.) as good as it gets? > > > Best regards > > -Markus > > -- > Markus Weißmann, M.Sc. > Institut für Informatik > Technische Universität München > Raum 03.07.054, Boltzmannstr. 3, 85748 Garching > > Tel. +49 (89) 2 89-1 81 05 > Fax +49 (89) 2 89-1 81 07 > > mailto:markus.weissmann@in.tum.de > > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa-roc.inria.fr/wws/info/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs -- ---- http://en.wikipedia.org/wiki/Posting_style ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] elegant subtyping? 2011-11-04 13:43 ` Pietro Abate @ 2011-11-04 14:12 ` Gabriel Scherer 2011-11-04 14:50 ` Vincent Aravantinos 0 siblings, 1 reply; 6+ messages in thread From: Gabriel Scherer @ 2011-11-04 14:12 UTC (permalink / raw) To: Pietro Abate; +Cc: caml-list In theory, polymorphic variants are the right tool for the job : they allow to express exactly what is asked for -- even in presence of recursive datatypes, if carefully formulated using open recursion and fixpoint. See Jacques Garrigue paper "Code reuse through polymorphic variants" for an introduction and interesting examples : http://www.math.nagoya-u.ac.jp/~garrigue/papers/fose2000.html In practice, they come with the downside of being more difficult to use than closed variants. I personally keep using your solution (1) to preserve simplicity; that usually means a finite number of dumb-looking "| Ast.Assign -> Cfg.Assign" branches in each pattern matching, but nothing really problematic for code quality or maintenance. The problem with polymorphic variants is that they are so flexible that type inference cannot help you a lot with errors in polymorphic variants code. For example, if you mistype one constructor name, the compiler won't be able to flag an error, it will only infer a slightly different types with the usual constructors, plus the misspelled one. Errors will only be spotted later, when you try to combine the faulty code with a function with strict assumptions on the variants (closed pattern matching), with an unwieldy error message. My advice for polymorphic variant beginners is to massively use annotations to control type-checking : every time you take a polymorphic variant as input, or output one, the function should be annotated with a precise type for the variant part. This will shield you from most inference issues, and force you to build an expressive set of type definitions (as Pietro demonstrated) that can be composed and help reason about your program. On Fri, Nov 4, 2011 at 2:43 PM, Pietro Abate <Pietro.Abate@pps.jussieu.fr> wrote: > hello, > using polymorphic variants maybe ? > > # module Cfg = struct type statement = [ `Assign | `Guard ] end;; > module Cfg : sig type statement = [ `Assign | `Guard ] end > > # module Ast = struct type statement = [ Cfg.statement | `Goto | `Label ] end;; > module Ast : sig type statement = [ `Assign | `Goto | `Guard | `Label ] end > > p > > On Fri, Nov 04, 2011 at 02:06:23PM +0100, Markus Weißmann wrote: >> Hello everyone, >> >> I'm writing on a compiler and want to subtype the "statements" that can >> occur in my code: >> At first I have an abstract syntax tree that can hold any statement of the >> language. From that I create a control flow graph that will only have >> non-control-flow statements (a true subset of the Ast-statements). >> Whats the best way to realize that? >> >> Basically I have: >> >> module Ast: type statement = Assign | Guard | Goto | Label >> module Cfg: type statement = Assign | Guard >> >> >> I see three -- not so elegant -- solutions to this: >> >> 1.) type-safe but imho quite ugly code: >> module Cfg: type statement = Assign | Guard >> module Ast: type statement = Base of Cfg.statement | Goto | Label >> >> 2.) use the same type for both and give up the safety that wrong types >> cannot show up in the Cfg >> >> 3.) use objects >> >> Did I miss the type-safe, elegant, module-based solution somehow? Or is >> 1.) as good as it gets? >> >> >> Best regards >> >> -Markus >> >> -- >> Markus Weißmann, M.Sc. >> Institut für Informatik >> Technische Universität München >> Raum 03.07.054, Boltzmannstr. 3, 85748 Garching >> >> Tel. +49 (89) 2 89-1 81 05 >> Fax +49 (89) 2 89-1 81 07 >> >> mailto:markus.weissmann@in.tum.de >> >> >> -- >> Caml-list mailing list. Subscription management and archives: >> https://sympa-roc.inria.fr/wws/info/caml-list >> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners >> Bug reports: http://caml.inria.fr/bin/caml-bugs > > -- > ---- > http://en.wikipedia.org/wiki/Posting_style > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa-roc.inria.fr/wws/info/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > > ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] elegant subtyping? 2011-11-04 14:12 ` Gabriel Scherer @ 2011-11-04 14:50 ` Vincent Aravantinos 2011-11-06 22:08 ` "Markus W. Weißmann" 0 siblings, 1 reply; 6+ messages in thread From: Vincent Aravantinos @ 2011-11-04 14:50 UTC (permalink / raw) To: caml-list In the end, I think the choice of using polymorphic variants or not should not rely only on the types themselves but also mainly on the functions that you apply on them. More precisely: if there is no or very few common (simple) functions between Ast.statement and Cfg.statement functions, don't bother with polymorphic variants (you can still get rid of the copy pasting by defining your function only on one of the types, and then using translation to the other type to lift your function). On 11/04/2011 10:12 AM, Gabriel Scherer wrote: > In theory, polymorphic variants are the right tool for the job : they > allow to express exactly what is asked for -- even in presence of > recursive datatypes, if carefully formulated using open recursion and > fixpoint. See Jacques Garrigue paper "Code reuse through polymorphic > variants" for an introduction and interesting examples : > http://www.math.nagoya-u.ac.jp/~garrigue/papers/fose2000.html > > In practice, they come with the downside of being more difficult to > use than closed variants. I personally keep using your solution (1) to > preserve simplicity; that usually means a finite number of > dumb-looking "| Ast.Assign -> Cfg.Assign" branches in each pattern > matching, but nothing really problematic for code quality or > maintenance. > > The problem with polymorphic variants is that they are so flexible > that type inference cannot help you a lot with errors in polymorphic > variants code. For example, if you mistype one constructor name, the > compiler won't be able to flag an error, it will only infer a slightly > different types with the usual constructors, plus the misspelled one. > Errors will only be spotted later, when you try to combine the faulty > code with a function with strict assumptions on the variants (closed > pattern matching), with an unwieldy error message. > > My advice for polymorphic variant beginners is to massively use > annotations to control type-checking : every time you take a > polymorphic variant as input, or output one, the function should be > annotated with a precise type for the variant part. This will shield > you from most inference issues, and force you to build an expressive > set of type definitions (as Pietro demonstrated) that can be composed > and help reason about your program. > > > On Fri, Nov 4, 2011 at 2:43 PM, Pietro Abate > <Pietro.Abate@pps.jussieu.fr> wrote: >> hello, >> using polymorphic variants maybe ? >> >> # module Cfg = struct type statement = [ `Assign | `Guard ] end;; >> module Cfg : sig type statement = [ `Assign | `Guard ] end >> >> # module Ast = struct type statement = [ Cfg.statement | `Goto | `Label ] end;; >> module Ast : sig type statement = [ `Assign | `Goto | `Guard | `Label ] end >> >> p >> >> On Fri, Nov 04, 2011 at 02:06:23PM +0100, Markus Weißmann wrote: >>> Hello everyone, >>> >>> I'm writing on a compiler and want to subtype the "statements" that can >>> occur in my code: >>> At first I have an abstract syntax tree that can hold any statement of the >>> language. From that I create a control flow graph that will only have >>> non-control-flow statements (a true subset of the Ast-statements). >>> Whats the best way to realize that? >>> >>> Basically I have: >>> >>> module Ast: type statement = Assign | Guard | Goto | Label >>> module Cfg: type statement = Assign | Guard >>> >>> >>> I see three -- not so elegant -- solutions to this: >>> >>> 1.) type-safe but imho quite ugly code: >>> module Cfg: type statement = Assign | Guard >>> module Ast: type statement = Base of Cfg.statement | Goto | Label >>> >>> 2.) use the same type for both and give up the safety that wrong types >>> cannot show up in the Cfg >>> >>> 3.) use objects >>> >>> Did I miss the type-safe, elegant, module-based solution somehow? Or is >>> 1.) as good as it gets? >>> >>> >>> Best regards >>> >>> -Markus >>> >>> -- >>> Markus Weißmann, M.Sc. >>> Institut für Informatik >>> Technische Universität München >>> Raum 03.07.054, Boltzmannstr. 3, 85748 Garching >>> >>> Tel. +49 (89) 2 89-1 81 05 >>> Fax +49 (89) 2 89-1 81 07 >>> >>> mailto:markus.weissmann@in.tum.de >>> >>> >>> -- >>> Caml-list mailing list. Subscription management and archives: >>> https://sympa-roc.inria.fr/wws/info/caml-list >>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners >>> Bug reports: http://caml.inria.fr/bin/caml-bugs >> -- >> ---- >> http://en.wikipedia.org/wiki/Posting_style >> >> -- >> Caml-list mailing list. Subscription management and archives: >> https://sympa-roc.inria.fr/wws/info/caml-list >> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners >> Bug reports: http://caml.inria.fr/bin/caml-bugs >> >> > -- Vincent Aravantinos Postdoctoral Fellow, Concordia University, Hardware Verification Group http://users.encs.concordia.ca/~vincent ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] elegant subtyping? 2011-11-04 14:50 ` Vincent Aravantinos @ 2011-11-06 22:08 ` "Markus W. Weißmann" 0 siblings, 0 replies; 6+ messages in thread From: "Markus W. Weißmann" @ 2011-11-06 22:08 UTC (permalink / raw) To: caml-list Thanks a lot everyone for all the tips and info -- it's working like a charm! Best regards -Markus On 4 Nov 2011, at 15:50, Vincent Aravantinos wrote: > In the end, I think the choice of using polymorphic variants or not should not rely only on the types themselves but also mainly on the functions that you apply on them. More precisely: if there is no or very few common (simple) functions between Ast.statement and Cfg.statement functions, don't bother with polymorphic variants (you can still get rid of the copy pasting by defining your function only on one of the types, and then using translation to the other type to lift your function). > > On 11/04/2011 10:12 AM, Gabriel Scherer wrote: >> In theory, polymorphic variants are the right tool for the job : they >> allow to express exactly what is asked for -- even in presence of >> recursive datatypes, if carefully formulated using open recursion and >> fixpoint. See Jacques Garrigue paper "Code reuse through polymorphic >> variants" for an introduction and interesting examples : >> http://www.math.nagoya-u.ac.jp/~garrigue/papers/fose2000.html >> >> In practice, they come with the downside of being more difficult to >> use than closed variants. I personally keep using your solution (1) to >> preserve simplicity; that usually means a finite number of >> dumb-looking "| Ast.Assign -> Cfg.Assign" branches in each pattern >> matching, but nothing really problematic for code quality or >> maintenance. >> >> The problem with polymorphic variants is that they are so flexible >> that type inference cannot help you a lot with errors in polymorphic >> variants code. For example, if you mistype one constructor name, the >> compiler won't be able to flag an error, it will only infer a slightly >> different types with the usual constructors, plus the misspelled one. >> Errors will only be spotted later, when you try to combine the faulty >> code with a function with strict assumptions on the variants (closed >> pattern matching), with an unwieldy error message. >> >> My advice for polymorphic variant beginners is to massively use >> annotations to control type-checking : every time you take a >> polymorphic variant as input, or output one, the function should be >> annotated with a precise type for the variant part. This will shield >> you from most inference issues, and force you to build an expressive >> set of type definitions (as Pietro demonstrated) that can be composed >> and help reason about your program. >> >> >> On Fri, Nov 4, 2011 at 2:43 PM, Pietro Abate >> <Pietro.Abate@pps.jussieu.fr> wrote: >>> hello, >>> using polymorphic variants maybe ? >>> >>> # module Cfg = struct type statement = [ `Assign | `Guard ] end;; >>> module Cfg : sig type statement = [ `Assign | `Guard ] end >>> >>> # module Ast = struct type statement = [ Cfg.statement | `Goto | `Label ] end;; >>> module Ast : sig type statement = [ `Assign | `Goto | `Guard | `Label ] end >>> >>> p >>> >>> On Fri, Nov 04, 2011 at 02:06:23PM +0100, Markus Weißmann wrote: >>>> Hello everyone, >>>> >>>> I'm writing on a compiler and want to subtype the "statements" that can >>>> occur in my code: >>>> At first I have an abstract syntax tree that can hold any statement of the >>>> language. From that I create a control flow graph that will only have >>>> non-control-flow statements (a true subset of the Ast-statements). >>>> Whats the best way to realize that? >>>> >>>> Basically I have: >>>> >>>> module Ast: type statement = Assign | Guard | Goto | Label >>>> module Cfg: type statement = Assign | Guard >>>> >>>> >>>> I see three -- not so elegant -- solutions to this: >>>> >>>> 1.) type-safe but imho quite ugly code: >>>> module Cfg: type statement = Assign | Guard >>>> module Ast: type statement = Base of Cfg.statement | Goto | Label >>>> >>>> 2.) use the same type for both and give up the safety that wrong types >>>> cannot show up in the Cfg >>>> >>>> 3.) use objects >>>> >>>> Did I miss the type-safe, elegant, module-based solution somehow? Or is >>>> 1.) as good as it gets? >>>> >>>> >>>> Best regards >>>> >>>> -Markus >>>> >>>> -- >>>> Markus Weißmann, M.Sc. >>>> Institut für Informatik >>>> Technische Universität München >>>> Raum 03.07.054, Boltzmannstr. 3, 85748 Garching >>>> >>>> Tel. +49 (89) 2 89-1 81 05 >>>> Fax +49 (89) 2 89-1 81 07 >>>> >>>> mailto:markus.weissmann@in.tum.de >>>> >>>> >>>> -- >>>> Caml-list mailing list. Subscription management and archives: >>>> https://sympa-roc.inria.fr/wws/info/caml-list >>>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners >>>> Bug reports: http://caml.inria.fr/bin/caml-bugs >>> -- >>> ---- >>> http://en.wikipedia.org/wiki/Posting_style >>> >>> -- >>> Caml-list mailing list. Subscription management and archives: >>> https://sympa-roc.inria.fr/wws/info/caml-list >>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners >>> Bug reports: http://caml.inria.fr/bin/caml-bugs >>> >>> >> > > -- > Vincent Aravantinos > Postdoctoral Fellow, Concordia University, Hardware Verification Group > http://users.encs.concordia.ca/~vincent > > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa-roc.inria.fr/wws/info/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > -- Markus Weißmann, M.Sc. Technische Universität München Institut für Informatik Boltzmannstr. 3 D-85748 Garching Germany Tel. +49 (89) 2 89-1 81 05 Fax +49 (89) 2 89-1 81 07 http://wwwknoll.in.tum.de/ ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2011-11-06 22:08 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2011-11-04 13:06 [Caml-list] elegant subtyping? Markus Weißmann 2011-11-04 13:27 ` Matthias Puech 2011-11-04 13:43 ` Pietro Abate 2011-11-04 14:12 ` Gabriel Scherer 2011-11-04 14:50 ` Vincent Aravantinos 2011-11-06 22:08 ` "Markus W. Weißmann"
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).