4 ms·

Changing eval to an interface method would work, but wouldn't get quite the same effect. The way I see it, there's a two-dimensional problem here: one dimensio

Changing eval to an interface method would work, but wouldn't get quite the same effect. The way I see it, there's a two-dimensional problem here: one dimension is the different cases for the type (I, B, Add, Mul, Eq), and the other dimension is the different operations you want to perform (eval, typecheck, optimize, etc.). Each operation handles each case, so you have n*m pieces of code, but you're stuck with a (pretty much) one-dimensional text file, so as a programmer, you have to choose how to slice it, and I think different problems make more sense sliced in different ways. Sum types are nice because they let you put all the cases for an algorithm in the same place, which often makes the algorithm easier to understand. That said, maybe Go's flexibility in method ordering (the fact that you can declare method anywhere, not just next to the struct they act on) makes this a non-issue. You could define your different case types at the top of the file, then put all of your eval method together, all your typecheck methods together, etc. It wouldn't be as easy to work with as pattern matching, but it's certainly better than having the different pieces scattered everywhere. Another thing to consider is extensibility, particularly if you're writing a library or plugin system or something like that. If you use an interface to declare "an expression is something that knows how to be evaluated, typechecked, and optimized", then someone using your code as a library could add another expression case without a lot of trouble, but they would have no (safe) way to add an operation. With typical sum types, you have the opposite constraint: "an expression is either I, B, Add, Mul, or Eq", so a library user can safely add additional operations, but they couldn't add additional expression cases. I think that making both dimensions extensible is a fundamentally hard problem: for example, if plugin 1 wanted to add a new case and plugin 2 wanted to add a new operation, who would be responsible for handling the new operation in the new case? So as a library author, you have to choose which dimension is fixed and which dimension is extensible, and sum types are the way to keep the list of cases fixed.

twic 12y ago
This is called the "expression problem": http://c2.com/cgi/wiki?ExpressionProblem http://c2.com/cgi/wiki?ExpressionProblem http://homepages.inf.ed.ac.uk/wadler/papers/expression/expression.txt http://homepages.inf.ed.ac.uk/wadler/papers/expression/expre...
colin_mccabe 12y ago
I apologize if this sounds dismissive, but I think you are still not quite looking at this from a Golang point of view. If you want to group all the Eval methods together for multiple types, please do! This ain't Java. You don't have to use one file per type, unless it makes sense to do that. As you said, Go gives you flexibility in method ordering. Another thing to consider is extensibility, particularly if you're writing a library or plugin system or something like that. If you use an interface to declare "an expression is something that knows how to be evaluated, typechecked, and optimized", then someone using your code as a library could add another expression case without a lot of trouble, but they would have no (safe) way to add an operation. So, there's a few ways to do this. One is to have your external module use an external function with a case switch, like you did. Another way is to create a new interface for your new operation. Then, your plugin library could create wrapper types for the basic types, and implement the new interface for them. Go makes wrapper types pretty easy to create through the anonymous struct member mechanism. I think that making both dimensions extensible is a fundamentally hard problem: for example, if plugin 1 wanted to add a new case and plugin 2 wanted to add a new operation, who would be responsible for handling the new operation in the new case? So as a library author, you have to choose which dimension is fixed and which dimension is extensible, and sum types are the way to keep the list of cases fixed. Maybe I'm missing something, but this doesn't seem that hard in Go. Plugin 1 can add a new type which implements whatever interfaces it wants to. Plugin 2 can add a new interface which other people can implement, or not, as they choose. Once you get away from the idea of type hierarchies, this stops being difficult. I agree that there are some cool things in SML, OCaml, and other languages that Go doesn't have (like algebraic pattern matching and currying), but there are other things it does have which can be very helpful. Right tool for the job, and all that.
- alangpierce 12y ago
  Thanks for the thoughts. I've worked with Go enough that I know pretty much all of the language features, but not enough to be comfortable with idiomatic programming, so it's nice to see a more experienced perspective. Maybe I'm missing something, but this doesn't seem that hard in Go. Plugin 1 can add a new type which implements whatever interfaces it wants to. Plugin 2 can add a new interface which other people can implement, or not, as they choose. Once you get away from the idea of type hierarchies, this stops being difficult. Yeah, it's not so hard if you allow operations to be optional, but I think there are some cases where you can't get away with that. As a more concrete example, let's say we're writing a flexible compiler and we're hoping to provide two extension points: * People should be able to add support for additional architectures. They do this by writing a new function (or something conceptually equivalent) that takes a syntax tree and outputs a list of instructions in some particular instruction set. * People should be able to extend the language by adding new syntactic elements (new cases for a syntax tree node). If one plugin adds do-while loops and a completely separate plugin adds ARM support, there won't be any code for compiling do-while loops to ARM, so the compiler would simply be broken for that case (there's no acceptable "default behavior"). But I think that's a fundamentally hard problem that can't be solved with any language feature. But if we assume that only one plugin is allowed (or that plugins have a strict ordering), then I think either of the solutions you mentioned (type switch or wrapper types) sound pretty reasonable, and they're more flexible than sum types because sum types would force the syntax tree format to always stay the same. Still, I don't think any of these solutions is perfect. For example, when using wrappers, the Sum, Mul, and Eq cases would still point at the non-wrapped types, so I think you'd have to do a bunch of conversions. With the type-switch (but only for plugins) approach, the built-in x86 code generator would be implemented in a completely different way from the ARM code generator plugin, which seems weird to me. Also, neither of your approaches has a way to enforce at compile time that every case was handled/wrapped.

twic 12y ago

This is called the "expression problem": http://c2.com/cgi/wiki?ExpressionProblem http://c2.com/cgi/wiki?ExpressionProblem http://homepages.inf.ed.ac.uk/wadler/papers/expression/expression.txt http://homepages.inf.ed.ac.uk/wadler/papers/expression/expre...

colin_mccabe 12y ago

I apologize if this sounds dismissive, but I think you are still not quite looking at this from a Golang point of view. If you want to group all the Eval methods together for multiple types, please do! This ain't Java. You don't have to use one file per type, unless it makes sense to do that. As you said, Go gives you flexibility in method ordering. Another thing to consider is extensibility, particularly if you're writing a library or plugin system or something like that. If you use an interface to declare "an expression is something that knows how to be evaluated, typechecked, and optimized", then someone using your code as a library could add another expression case without a lot of trouble, but they would have no (safe) way to add an operation. So, there's a few ways to do this. One is to have your external module use an external function with a case switch, like you did. Another way is to create a new interface for your new operation. Then, your plugin library could create wrapper types for the basic types, and implement the new interface for them. Go makes wrapper types pretty easy to create through the anonymous struct member mechanism. I think that making both dimensions extensible is a fundamentally hard problem: for example, if plugin 1 wanted to add a new case and plugin 2 wanted to add a new operation, who would be responsible for handling the new operation in the new case? So as a library author, you have to choose which dimension is fixed and which dimension is extensible, and sum types are the way to keep the list of cases fixed. Maybe I'm missing something, but this doesn't seem that hard in Go. Plugin 1 can add a new type which implements whatever interfaces it wants to. Plugin 2 can add a new interface which other people can implement, or not, as they choose. Once you get away from the idea of type hierarchies, this stops being difficult. I agree that there are some cool things in SML, OCaml, and other languages that Go doesn't have (like algebraic pattern matching and currying), but there are other things it does have which can be very helpful. Right tool for the job, and all that.

alangpierce 12y ago
Thanks for the thoughts. I've worked with Go enough that I know pretty much all of the language features, but not enough to be comfortable with idiomatic programming, so it's nice to see a more experienced perspective. Maybe I'm missing something, but this doesn't seem that hard in Go. Plugin 1 can add a new type which implements whatever interfaces it wants to. Plugin 2 can add a new interface which other people can implement, or not, as they choose. Once you get away from the idea of type hierarchies, this stops being difficult. Yeah, it's not so hard if you allow operations to be optional, but I think there are some cases where you can't get away with that. As a more concrete example, let's say we're writing a flexible compiler and we're hoping to provide two extension points: * People should be able to add support for additional architectures. They do this by writing a new function (or something conceptually equivalent) that takes a syntax tree and outputs a list of instructions in some particular instruction set. * People should be able to extend the language by adding new syntactic elements (new cases for a syntax tree node). If one plugin adds do-while loops and a completely separate plugin adds ARM support, there won't be any code for compiling do-while loops to ARM, so the compiler would simply be broken for that case (there's no acceptable "default behavior"). But I think that's a fundamentally hard problem that can't be solved with any language feature. But if we assume that only one plugin is allowed (or that plugins have a strict ordering), then I think either of the solutions you mentioned (type switch or wrapper types) sound pretty reasonable, and they're more flexible than sum types because sum types would force the syntax tree format to always stay the same. Still, I don't think any of these solutions is perfect. For example, when using wrappers, the Sum, Mul, and Eq cases would still point at the non-wrapped types, so I think you'd have to do a bunch of conversions. With the type-switch (but only for plugins) approach, the built-in x86 code generator would be implemented in a completely different way from the ARM code generator plugin, which seems weird to me. Also, neither of your approaches has a way to enforce at compile time that every case was handled/wrapped.