3 ms·

What I usually find is that in the case where I have a Golang function that needs to return either a foo or a bar, I can just return a tuple of (foo, bar) and h

What I usually find is that in the case where I have a Golang function that needs to return either a foo or a bar, I can just return a tuple of (foo, bar) and have one of them be nil. Yes, you miss out on the compiler enforcing the fact that one is nil, but that hasn't been a big problem for me in practice. The same goes with passing a "foo or bar" to a channel.. I just send a struct where one field is nil. It works very well in practice. It would be interesting to see a discussion of why Golang didn't implement sum types. I suspect that part of it is efficiency... right now, the sizes of Go structs are known at compile time. With a sum type, you would either have to give that up, or pad to the size of the largest possible value. This is similar to unions in C, where the size is dictated by the size of the largest element. I think that in the case he gives, of an expression tree, using interfaces like he did is the right way to go. I would only say, that "eval" should be a method in the interface, to eliminate the clunky case statement based on the value type. This would also allow him to get rid of the isExpr method and write the code in a more idiomatic way, I think...

aikah 12y ago
well it's a hack to make up for the lack of go expressiveness. Period. Go needs static polymorphism AND generics.it doesnt need to look like Haskell.
alangpierce 12y ago
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.
  - 12y ago
kibwen 12y ago
> It would be interesting to see a discussion of why Golang > didn't implement sum types. The discussion is alluded to in the FAQ: http://golang.org/doc/faq#variant_types http://golang.org/doc/faq#variant_types "We considered adding variant types to Go, but after discussion decided to leave them out because they overlap in confusing ways with interfaces. What would happen if the elements of a variant type were themselves interfaces? " I would be interested to read the original discussion, if it was carried out via publicly accessible mailing lists. > I suspect that part of it is efficiency... right now, > the sizes of Go structs are known at compile time. I don't think this would warrant much concern. To use your own example, emulating sum types via a tuple of `(foo, bar)` where both `foo` and `bar` are nil-able implies that they are interfaces (or pointers), which (AFAICT) means that the return type of your function is always going to be the size of two pointers at runtime (16 bytes on a 64-bit platform). If you replaced that with an actual sum type, the runtime representation would consist of a single pointer and a tag, which would be between 9 and 16 bytes (depending on padding and alignment), so even in the worst case it's no more wasteful than the tuple approach. Additionally, using tuples here, every time that you add another potential variant (i.e. `(foo, bar, baz, qux)`) you inflate the size of the return type by another eight bytes, whereas the sum type scales gracefully without getting larger. And if you're worried about a sum type where one of the variants is some huge struct, then you're free to store a pointer to an instance of that struct instead, in which case your runtime size is, again, no worse than 16 bytes (assuming all the other variants aren't huge structs as well), and it's not like this introduces any greater runtime efficiency than the tuple approach given that interfaces already (again, AFAICT) demand a pointer indirection. (I'm not an expert on Go though, I could be wrong! Corrections welcome!)
- colin_mccabe 12y ago
  Hi kibwen, I think it's pretty clear that you can minimize the size of either a sum type or a non-sum type by using pointers rather than values, as you pointed out. But, obviously, Go supports returning values, not just pointers. In that case, Go will have to allocate space for the maximum-sized component of the value type, which could be arbitrarily large. This is a non-obvious fact unless you're a language implementor, or just really interested in the implementation. This somewhat violates the concept that the performance costs of code should be clear. This is less of an issue in languages like Java that do not have value types. When everything is a pointer, all of the elements of the sum type have the same size (or at least, a size less than 8 bytes, in the case of primitives). This may not be the only, or even the best reason for not implementing them, but it's still something to consider. It's true that sum types can be more space-efficient than using nullable struct members like my example did. But this mainly seems like an issue when you have more than two types in the sum type, which seems to come up very rarely. The difference between returning two 8-byte pointers and returning a type tag and an 8-byte pointer is not a big deal on a 64-bit machine. You are using 2 64-bit registers in any case. Maybe there's cases I haven't thought of, but at first glance, the efficiency argument for sum types seems very weak. [Variant types are] alluded to in the FAQ: Thanks! I didn't see that before. Interesting.

aikah 12y ago

well it's a hack to make up for the lack of go expressiveness. Period. Go needs static polymorphism AND generics.it doesnt need to look like Haskell.

alangpierce 12y ago

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.
- 12y ago

kibwen 12y ago

> It would be interesting to see a discussion of why Golang > didn't implement sum types. The discussion is alluded to in the FAQ: http://golang.org/doc/faq#variant_types http://golang.org/doc/faq#variant_types "We considered adding variant types to Go, but after discussion decided to leave them out because they overlap in confusing ways with interfaces. What would happen if the elements of a variant type were themselves interfaces? " I would be interested to read the original discussion, if it was carried out via publicly accessible mailing lists. > I suspect that part of it is efficiency... right now, > the sizes of Go structs are known at compile time. I don't think this would warrant much concern. To use your own example, emulating sum types via a tuple of `(foo, bar)` where both `foo` and `bar` are nil-able implies that they are interfaces (or pointers), which (AFAICT) means that the return type of your function is always going to be the size of two pointers at runtime (16 bytes on a 64-bit platform). If you replaced that with an actual sum type, the runtime representation would consist of a single pointer and a tag, which would be between 9 and 16 bytes (depending on padding and alignment), so even in the worst case it's no more wasteful than the tuple approach. Additionally, using tuples here, every time that you add another potential variant (i.e. `(foo, bar, baz, qux)`) you inflate the size of the return type by another eight bytes, whereas the sum type scales gracefully without getting larger. And if you're worried about a sum type where one of the variants is some huge struct, then you're free to store a pointer to an instance of that struct instead, in which case your runtime size is, again, no worse than 16 bytes (assuming all the other variants aren't huge structs as well), and it's not like this introduces any greater runtime efficiency than the tuple approach given that interfaces already (again, AFAICT) demand a pointer indirection. (I'm not an expert on Go though, I could be wrong! Corrections welcome!)

colin_mccabe 12y ago
Hi kibwen, I think it's pretty clear that you can minimize the size of either a sum type or a non-sum type by using pointers rather than values, as you pointed out. But, obviously, Go supports returning values, not just pointers. In that case, Go will have to allocate space for the maximum-sized component of the value type, which could be arbitrarily large. This is a non-obvious fact unless you're a language implementor, or just really interested in the implementation. This somewhat violates the concept that the performance costs of code should be clear. This is less of an issue in languages like Java that do not have value types. When everything is a pointer, all of the elements of the sum type have the same size (or at least, a size less than 8 bytes, in the case of primitives). This may not be the only, or even the best reason for not implementing them, but it's still something to consider. It's true that sum types can be more space-efficient than using nullable struct members like my example did. But this mainly seems like an issue when you have more than two types in the sum type, which seems to come up very rarely. The difference between returning two 8-byte pointers and returning a type tag and an 8-byte pointer is not a big deal on a 64-bit machine. You are using 2 64-bit registers in any case. Maybe there's cases I haven't thought of, but at first glance, the efficiency argument for sum types seems very weak. [Variant types are] alluded to in the FAQ: Thanks! I didn't see that before. Interesting.