Union/Sum Types

Showing 1-34 of 34 messages
Union/Sum Types Kevin Ballard 9/7/11 1:14 PM
I've seen some mention of union types in the past on this list, but has there ever been a serious proposal to add them to Go? Sum types are one of my favorite bits about Haskell that I don't often see in other languages, and it seems like Go could benefit from having them. For example, the "xml" package right now has a type Token which is defined as interface{} but in fact is only intended to hold values of the types StartElement, EndElement, CharData, Comment, ProcInst, or Directive. This sort of thing really should be checked by the compiler, but the lack of union types in Go means it can't.

As a side note, union types are even more powerful once generics come into the picture, but I believe they're plenty useful on their own seeing as generics are still an undecided subject.
Re: [go-nuts] Union/Sum Types Evan Shaw 9/7/11 1:28 PM
On Thu, Sep 8, 2011 at 8:14 AM, Kevin Ballard <kbal...@gmail.com> wrote:
> I've seen some mention of union types in the past on this list, but has
> there ever been a serious proposal to add them to Go?

It's been implied that there was a serious proposal inside Google that
wasn't made public. See:
https://groups.google.com/d/msg/golang-nuts/-94Fmnz9L6k/4BUxp-JqZFUJ

That post also says why it hasn't been accepted.

Though it might be an oversight, the feature does still appear on the
roadmap, so maybe it's not completely out of the question:
http://golang.org/doc/devel/roadmap.html

- Evan

Re: [go-nuts] Union/Sum Types Kevin Ballard 9/7/11 1:33 PM
While I personally would rather like having an error when a case is missing in a switch, I do recognize that it's probably not something that would be put into the language. However, I still feel that union types add more expressivity to the type system and would be a valuable enhancement. According to the thread you linked, go/ast seemed like the only place where it would be used, but as I mentioned it would also be useful in the xml package. And in a script I wrote recently I ended up having to do the same think the xml package does, e.g. using an interface{} to hold one value of a small set of types, and I would have loved to be able to use a union{} instead. Why rely on documentation for something the compiler should be able to test for you?

-Kevin

On Wed, Sep 7, 2011 at 1:24 PM, Kyle Lemons <kev...@google.com> wrote:
There have been a few (one is here) over time.  I think in general the utility isn't seen to be particularly high, and some of the potential "safety" features (errors when missing a case in a switch) are seen as more hindrance than help.
~K
Re: [go-nuts] Union/Sum Types Russ Cox 9/7/11 1:59 PM
http://tip.goneat.org/doc/go_faq.html#unions
Re: [go-nuts] Union/Sum Types Kevin Ballard 9/7/11 2:14 PM
http://tip.goneat.org/doc/go_faq.html#variant_types is the more interesting entry, as I wasn't suggesting untagged unions. Is this to be considered a "final answer", or is it still open for consideration? I recognize that there are questions to be answered with variant types, but I also think they're a very useful language feature. Yes, interface{} can accomplish the same things as variant types, but only by removing compiler support for type-checking. It's also less efficient than a proper tagged union implementation.

In some ways, Go is actually less powerful than a traditional OOP language with regards to compile-time checking. For example, if I want to implement a binary tree using an OOP language, I could choose to do so by having an abstract Tree superclass with Node and Leaf subclasses, and each Node will then hold 2 Trees. But the equivalent construct in Go would end up having Node and Leaf structs, and Node would hold 2 interface{}'s as there's no way to specify that it only holds a Node or a Leaf. Yes, there are other ways to represent homogenous trees in Go that work around this issue (e.g. by using a slice for children, or by having a Leaf be a Node with nil values for its children, etc.), but any heterogenous tree will have to use interface{} and lose any compile-time niceties. This is precisely the issue I ran into when writing my script the other day, and it's also the issue the xml (and I assume go/ast) package has.

Variant types are also a good stepping stone to full ADTs, and are also very useful once generics come into play. I'd actually love to have full ADTs (especially because Go doesn't even have compile-time-checked enums), but I thought variant/union/sum types were a simpler suggestion.

-Kevin

On Wed, Sep 7, 2011 at 1:59 PM, Russ Cox <r...@golang.org> wrote:
http://tip.goneat.org/doc/go_faq.html#unions



--
Kevin Ballard
http://kevin.sb.org
kbal...@gmail.com
Re: [go-nuts] Union/Sum Types Russ Cox 9/7/11 3:02 PM
I think the FAQ answer speaks for itself.
You are arguing that there are benefits to having variant types,
which we understand, but you are ignoring the costs to having
both variant types and interface types: they interfere in
destructive ways.

Russ

Re: [go-nuts] Union/Sum Types Kevin Ballard 9/7/11 3:48 PM
The FAQ lists only a single issue where variant types interact with interfaces; namely, what happens if an element of a variant type was itself an interface. I'm not really sure why that's an issue though. The simple solution is to say you can't do that (after all, an interface can't contain an interface, so why should a union?). Using an interface{} value should suffice for that for the time being. And if, sometime in the future, Go decides to adopt full-fledged ADTs then the issue of distinguishing multiple interface-typed members becomes trivial, as each one would be paired with its own constructor.

interface{} is great when you want to handle dynamic types. Variant types are great when you want to handle a limited set of static types. I don't see why the two have to conflict.

Re: [go-nuts] Union/Sum Types r 9/7/11 3:58 PM
The answer is no.  The FAQ need not and should not contain an exhaustive counterargument.

Interfaces and arithmetic types interact in confusing ways. Go will not be improved by adding arithmetic types.

-rob

Re: [go-nuts] Union/Sum Types Steven Blenkinsop 9/7/11 8:04 PM
On Wed, Sep 7, 2011 at 6:58 PM, Rob 'Commander' Pike <r...@google.com> wrote:
The answer is no.

That just means we need to ask a better question :)
 
The FAQ need not and should not contain an exhaustive counterargument.

The FAQ need not, but an argument alluded to but never specified begets scepticism.
 
Interfaces and arithmetic types interact in confusing ways.

I don't see how this could be categorically true. There must be some constraints on the circumstances that would create the confusion that could inform a good design. But since I don't know what the confusion is, I can't come up with what these constraints would be.

On Wed, Sep 7, 2011 at 6:48 PM, Kevin Ballard <kbal...@gmail.com> wrote:

The simple solution is to say you can't do that (after all, an interface can't contain an interface, so why should a union?).

It makes sense that the dynamic type of a union would never be an interface or union type, same as with an interface, but you could still allow an interface or union type as an element type. The set of types assignable to the union type would be the set of types assignable to any of its element types, and it would just take on the dynamic type of any union or interface values assigned to it. It all makes sense if you think of converting to a union type as the inverse of a type switch without a default clause. Just list the types from the type switch in the union, and you guarantee that all values of the union type can be handled by that type switch. The element types need not be disjoint any more than the cases of a type switch need to be.
Re: [go-nuts] Union/Sum Types Russ Cox 9/7/11 8:28 PM
We don't have the time to engage in lengthy
design discussions about every language feature
we considered and declined, but this should give
a flavor of the complications.

What does

type RW union {
    io.Reader
    io.Writer
}

mean?  Or is it disallowed?
(That would be pretty unfortunate.)

What happens if you have

    var r io.Reader = os.Stdin  // an *os.File
    var rw RW = r

Can you say rw.(io.Writer) and successfully
pull out the *os.File (which is after all both).

What is the zero value of a union?
Why is that okay?

And so on and so on.  It gets complicated very fast.

Russ

Re: [go-nuts] Union/Sum Types Steven Blenkinsop 9/7/11 8:40 PM
On Wed, Sep 7, 2011 at 11:28 PM, Russ Cox <r...@golang.org> wrote:
We don't have the time to engage in lengthy
design discussions about every language feature
we considered and declined, but this should give
a flavor of the complications.

What does

type RW union {
   io.Reader
   io.Writer
}
 
mean?  Or is it disallowed?

The union of all types that implement either Read or Write or both. The union type has an empty method set.
 
What happens if you have

   var r io.Reader = os.Stdin  // an *os.File
   var rw RW = r
Can you say rw.(io.Writer) and successfully
pull out the *os.File (which is after all both).

You should be able to do rw.(*os.File) or rw.(io.ReadWriter) or rw.(io.Writer), just assert to whatever type you want, as long as it is a type that is assignable to one of the element types of the union. You could do rw.(io.Writer).(*os.File) if you want to, but there wouldn't be much point.
 
What is the zero value of a union?

nil

Why is that okay?

For the same reason that a nil interface is okay. As long as Go doesn't support some form of non-nil predicate or equivalent, there's no point worrying about restricting nil in a new case when there are already a million cases (hyperbolically speaking) where nil is potentially incorrect but not statically disallowable.
 
And so on and so on.  It gets complicated very fast.

None of these questions seem to be complicated given the union type I was suggesting.

Re: [go-nuts] Union/Sum Types Russ Cox 9/7/11 8:55 PM
I am going to mute this thread and stop replying after this post.
I just don't have time, sorry.

On Wed, Sep 7, 2011 at 23:40, Steven Blenkinsop <stev...@gmail.com> wrote:
> You should be able to do rw.(*os.File) or rw.(io.ReadWriter) or
> rw.(io.Writer), just assert to whatever type you want, as long as it is a
> type that is assignable to one of the element types of the union. You could
> do rw.(io.Writer).(*os.File) if you want to, but there wouldn't be much
> point.

This is too surprising.  It means that if someone
puts in an io.Writer and then does a type switch,
the io.Reader case fires.  So the tagged union is
in reality not very tagged.  This essentially violates
the definition of a variant type.

>> What is the zero value of a union?
> nil

This is another serious problem.  A common reason
someone might want unions is that you want to write
a function that accepts either string or []byte, so you
write

type MyInput union { string; []byte }
func F(MyInput)

and then someone writes F(nil) and gets a nil MyInput
instead of a nil []byte.  Now instead of two cases
there are three everywhere.  It basically kills this
case as a motivating example.

At this point the weird corner cases are eating away
at the benefits of the hypothetical union types enough
that it's not clear that they're necessary.  In the few
cases where you really care, you can write a dummy
interface { IsFoo() }, without any language changes.

Russ

Re: [go-nuts] Union/Sum Types Steven Blenkinsop 9/7/11 10:23 PM
On Wed, Sep 7, 2011 at 11:55 PM, Russ Cox <r...@golang.org> wrote:
I am going to mute this thread and stop replying after this post.
I just don't have time, sorry.

That's fine. This is golang-nuts after all.
 
On Wed, Sep 7, 2011 at 23:40, Steven Blenkinsop <stev...@gmail.com> wrote:
> You should be able to do rw.(*os.File) or rw.(io.ReadWriter) or
> rw.(io.Writer), just assert to whatever type you want, as long as it is a
> type that is assignable to one of the element types of the union. You could
> do rw.(io.Writer).(*os.File) if you want to, but there wouldn't be much
> point.

This is too surprising.  It means that if someone
puts in an io.Writer and then does a type switch,
the io.Reader case fires.  So the tagged union is
in reality not very tagged.  This essentially violates
the definition of a variant type.

That's because it isn't a tagged/disjoint union or variant. All this union guarantees is that you have a Read or Write method, which isn't particularly useful. Interfaces have the exact same "surprising" behaviour, so anyone who understands interfaces shouldn't have trouble with this. Maybe a more useful union for your purpose here would be:

type (
        ROrW   union  { Reader; Writer }
        Reader struct { io.Reader }
        Writer struct { io.Writer }
)

This union is disjoint, unlike the original. The use case for an interface union element type is for something like:

type String union { string; []byte; fmt.Stringer }

>> What is the zero value of a union?
> nil

This is another serious problem.  A common reason
someone might want unions is that you want to write
a function that accepts either string or []byte, so you
write

type MyInput union { string; []byte }
func F(MyInput)

and then someone writes F(nil) and gets a nil MyInput
instead of a nil []byte.  Now instead of two cases
there are three everywhere.  It basically kills this
case as a motivating example.

type MyInput union { []byte; []int }
F(nil)

What type is nil? Nil already has to be handled by convention throughout the language. I would like to see a way to statically enforce non-nil, but I think that's a separate issue. In this case, the solution is just to handle nil as well as []byte(nil) and "", or else just use the common convention in Go of not allowing nil. The single case is a lot easier to manage than all the potential cases.

Sure, you could make it so that you can't handle the zero value for MyInput unless you add nil to the union, but this would have a poison in the well effect, so I don't think its a good way to deal with the issue.

At this point the weird corner cases are eating away
at the benefits of the hypothetical union types enough
that it's not clear that they're necessary.  In the few
cases where you really care, you can write a dummy
interface { IsFoo() }, without any language changes.

True, to an extent. Except that dummy methods can be promoted if the type is embedded, which breaks the bounding on the types. Plus, while you can get the compiler to reject user mistakes, it doesn't help the library maintainer at all, since the intent has to be communicated separately, and this has to be maintained separately. It also means you can't use built-in types in your "union".

To me, the key appeal is of union types is to complement the type switch. Interfaces are great for statically ensuring you can call methods, but they aren't a good match for a type switch.
Re: [go-nuts] Union/Sum Types Han-Wen Nienhuys 9/8/11 7:39 AM
On Wed, Sep 7, 2011 at 7:58 PM, Rob 'Commander' Pike <r...@google.com> wrote:
> The answer is no.  The FAQ need not and should not contain an exhaustive counterargument.
>
> Interfaces and arithmetic types interact in confusing ways.

Have you considered making the variant type be an extension of interfaces?

  // An interface{} that can only be instantiated from either a Leaf
or Node object.
  type LeafNode interface {
    *Leaf, *Node
  }

This would cause conversions to LeafNode to only be allowed if the
source is either *Leaf or *Node. That gives some guarantee that values
you unpack in a function are of the type you put in originally.


--
Han-Wen Nienhuys
Google Engineering Belo Horizonte
han...@google.com

Re: [go-nuts] Union/Sum Types Steven Blenkinsop 9/8/11 5:25 PM
On Thu, Sep 8, 2011 at 10:39 AM, Han-Wen Nienhuys <han...@google.com> wrote:
On Wed, Sep 7, 2011 at 7:58 PM, Rob 'Commander' Pike <r...@google.com> wrote:
> The answer is no.  The FAQ need not and should not contain an exhaustive counterargument.
>
> Interfaces and arithmetic types interact in confusing ways.

Have you considered making the variant type be an extension of interfaces?

 // An interface{} that can only be instantiated from either a Leaf
or Node object.
 type LeafNode interface {
   *Leaf, *Node
 }

This would cause conversions to LeafNode to only be allowed if the
source is either *Leaf or *Node. That gives some guarantee that values
you unpack in a function are of the type you put in originally.

This wouldn't work. Currently, type LeafNode interface { Leaf; Node } means that a LeafNode is the intersection of Leaf and Node (which means it has the union of the constraints, i.e. method sets). Making type LeafNode interface { *Leaf; *Node } be the union of *Leaf and *Node would be inconsistent behaviour.
Re: Union/Sum Types 9/9/11 7:23 AM
On Sep 8, 5:55 am, Russ Cox <r...@golang.org> wrote:
> I am going to mute this thread and stop replying after this post.

We will see ...

> I just don't have time, sorry.
>
> On Wed, Sep 7, 2011 at 23:40, Steven Blenkinsop <steven...@gmail.com> wrote:
> > You should be able to do rw.(*os.File) or rw.(io.ReadWriter) or
> > rw.(io.Writer), just assert to whatever type you want, as long as it is a
> > type that is assignable to one of the element types of the union. You could
> > do rw.(io.Writer).(*os.File) if you want to, but there wouldn't be much
> > point.
>
> This is too surprising.  It means that if someone
> puts in an io.Writer and then does a type switch,
> the io.Reader case fires.

That is not surprising. It isn't surprising because, in this respect,
Go is an unsafe language. This, I think, was obvious from the very
beginning (year 2009, when Go specification was published).
Re: [go-nuts] Re: Union/Sum Types Rich Wareham 9/9/11 7:37 AM
On Fri, Sep 09, 2011 at 07:23:09AM -0700, ⚛ wrote:
> On Sep 8, 5:55 am, Russ Cox <r...@golang.org> wrote:
> > I am going to mute this thread and stop replying after this post.
>
> We will see ...

It might be the residual fear of the  playground in me, but I'm half
expecting an ASCII art "Russ Cox smells of [something appropriately
smelly that rhymes with grit]" to appear in this thread from you now :).

--
Dr Rich Wareham

Re: Union/Sum Types j...@webmaster.ms 9/9/11 9:00 AM
It is only question of the syntax confusion.
I think, Han-Wen wanted to say that variant types can be equal to
interface{} with some compile-time constraints.

type LeafNode *Leaf | *Node  // let's define it more like they look in
ML and Haskell in order not to confuse

that would mean
type LeafNode interface {}

var ln LeafNode
a := ln.(*Leaf) // ok
b := ln.(*Node) // ok
b := ln.(int) // <----------------- error in compile time, not in
runtime

PoC can be done as a preprocessor.

On Sep 9, 4:25 am, Steven Blenkinsop <steven...@gmail.com> wrote:
> On Thu, Sep 8, 2011 at 10:39 AM, Han-Wen Nienhuys <han...@google.com> wrote:
> > On Wed, Sep 7, 2011 at 7:58 PM, Rob 'Commander' Pike <r...@google.com> wrote:
> > > The answer is no.  The FAQ need not and should not contain an exhaustive
> > counterargument.
>
> > > Interfaces and arithmetic types interact in confusing ways.
>
> > Have you considered making the variant type be an extension of interfaces?
>
> >  // An interface{} that can only be instantiated from either a Leaf
> > or Node object.
> >  type LeafNode interface {
> >    *Leaf, *Node
> >  }
>
> > This would cause conversions to LeafNode to only be allowed if the
> > source is either *Leaf or *Node. That gives some guarantee that values
> > you unpack in a function are of the type you put in originally.
>
> This wouldn't work. Currently, type LeafNode interface { Leaf; Node } means
> that a LeafNode is the *intersection* of Leaf and Node (which means it has
> the union of the constraints, i.e. method sets). Making type LeafNode
> interface { *Leaf; *Node } be the *union* of *Leaf and *Node would be
> inconsistent behaviour.
Re: Union/Sum Types j...@webmaster.ms 9/9/11 9:07 AM
On Sep 9, 8:00 pm, "j...@webmaster.ms" <j...@webmaster.ms> wrote:
> It is only question of the syntax confusion.
> I think, Han-Wen wanted to say that variant types can be equal to
> interface{} with some compile-time constraints.
>
> type LeafNode *Leaf | *Node  // let's define it more like they look in
> ML and Haskell in order not to confuse
>
> that would mean
> type LeafNode interface {}
>
> var ln LeafNode
> a := ln.(*Leaf) // ok
> b := ln.(*Node) // ok
> c := ln.(int) // <----------------- error in compile time, not in
> runtime

And the same on assignment:
ln = &Leaf{} // ok
ln = &Node{} // ok
ln = 42 // <---- compile time error
Re: [go-nuts] Re: Union/Sum Types Han-Wen Nienhuys 9/9/11 9:09 AM
On Fri, Sep 9, 2011 at 1:00 PM, j...@webmaster.ms <j...@webmaster.ms> wrote:
> It is only question of the syntax confusion.
> I think, Han-Wen wanted to say that variant types can be equal to
> interface{} with some compile-time constraints.
>
> type LeafNode *Leaf | *Node  // let's define it more like they look in
> ML and Haskell in order not to confuse
>
> that would mean
> type LeafNode interface {}
>
> var ln LeafNode
> a := ln.(*Leaf) // ok
> b := ln.(*Node) // ok
> b := ln.(int) // <----------------- error in compile time, not in
> runtime

Right. There could also be an error if one of the types is missing
from a type switch that uses the interface type,

 var ln LeafNode
 switch ln.(type) {
  case *Leaf:
    log.Println("leaf")
 }  // compile time error: missing case for *Node.

> On Sep 9, 4:25 am, Steven Blenkinsop <steven...@gmail.com> wrote:
>> On Thu, Sep 8, 2011 at 10:39 AM, Han-Wen Nienhuys <han...@google.com> wrote:
>> > On Wed, Sep 7, 2011 at 7:58 PM, Rob 'Commander' Pike <r...@google.com> wrote:
>> > > The answer is no.  The FAQ need not and should not contain an exhaustive
>> > counterargument.
>>
>> > > Interfaces and arithmetic types interact in confusing ways.
>>
>> > Have you considered making the variant type be an extension of interfaces?
>>
>> >  // An interface{} that can only be instantiated from either a Leaf
>> > or Node object.
>> >  type LeafNode interface {
>> >    *Leaf, *Node
>> >  }
>>
>> > This would cause conversions to LeafNode to only be allowed if the
>> > source is either *Leaf or *Node. That gives some guarantee that values
>> > you unpack in a function are of the type you put in originally.
>>
>> This wouldn't work. Currently, type LeafNode interface { Leaf; Node } means
>> that a LeafNode is the *intersection* of Leaf and Node (which means it has
>> the union of the constraints, i.e. method sets). Making type LeafNode
>> interface { *Leaf; *Node } be the *union* of *Leaf and *Node would be
>> inconsistent behaviour.
>

--

Han-Wen Nienhuys
Google Engineering Belo Horizonte
han...@google.com

Re: [go-nuts] Re: Union/Sum Types Kyle Lemons 9/9/11 10:57 AM
On Fri, Sep 9, 2011 at 1:00 PM, j...@webmaster.ms <j...@webmaster.ms> wrote:
> It is only question of the syntax confusion.
> I think, Han-Wen wanted to say that variant types can be equal to
> interface{} with some compile-time constraints.
>
> type LeafNode *Leaf | *Node  // let's define it more like they look in
> ML and Haskell in order not to confuse
>
> that would mean
> type LeafNode interface {}
>
> var ln LeafNode
> a := ln.(*Leaf) // ok
> b := ln.(*Node) // ok
> b := ln.(int) // <----------------- error in compile time, not in
> runtime

Right. There could also be an error if one of the types is missing
from a type switch that uses the interface type,

 var ln LeafNode
 switch ln.(type) {
 case *Leaf:
   log.Println("leaf")
 }  // compile time error: missing case for *Node.

Perhaps this is something that could be handled by govet, possibly with a properly formatted annotation in the type comment.
~K 
Re: Union/Sum Types 9/9/11 11:00 AM
On Sep 9, 4:23 pm, ⚛ <0xe2.0x9a.0...@gmail.com> wrote:
> On Sep 8, 5:55 am, Russ Cox <r...@golang.org> wrote:
> > On Wed, Sep 7, 2011 at 23:40, Steven Blenkinsop <steven...@gmail.com> wrote:
> > > You should be able to do rw.(*os.File) or rw.(io.ReadWriter) or
> > > rw.(io.Writer), just assert to whatever type you want, as long as it is a
> > > type that is assignable to one of the element types of the union. You could
> > > do rw.(io.Writer).(*os.File) if you want to, but there wouldn't be much
> > > point.
>
> > This is too surprising.  It means that if someone
> > puts in an io.Writer and then does a type switch,
> > the io.Reader case fires.
>
> That is not surprising. It isn't surprising because, in this respect,
> Go is an unsafe language. This, I think, was obvious from the very
> beginning (year 2009, when Go specification was published).

Ah. It turned out that I misread the paragraph of text starting with
"This is too ..." written by Russ. My misinterpretation was caused, I
guess, by an inconsistency in the paragraph. I don't understand - how
could a type switch convert an io.Writer into an io.Reader? That's
impossible.

Is somebody able to decipher the paragraph and explain what the
following sentence means: "...if someone puts in an io.Writer and then
does a type switch, the io.Reader case fires".

Thanks.
Re: [go-nuts] Re: Union/Sum Types Kyle Lemons 9/9/11 11:16 AM
Ah. It turned out that I misread the paragraph of text starting with
"This is too ..." written by Russ. My misinterpretation was caused, I
guess, by an inconsistency in the paragraph. I don't understand - how
could a type switch convert an io.Writer into an io.Reader? That's
impossible.

That's kinda the point... it isn't impossible, and that's confusing.

type RW union io.Reader or io.Writer 
var rw RW

file, _ := os.Create("/tmp/foo") // file is *os.File
writer := io.Writer(file) // writer is io.Writer backed by an *os.File

switch rw = writer; rw { // rw is a union backed by an *os.File
  case io.Reader: panic("What?!") // *os.File is an io.Reader
  case io.Writer: ...
}
Re: [go-nuts] Re: Union/Sum Types Andy Balholm 9/9/11 8:38 PM
It is already possible to convert a Writer to a Reader with a type switch (although having union types makes it more likely). The following (perfectly valid) program will panic, just like the hypothetical program above:

package main

import (
"fmt"
"os"
"io"
)

func main() {
file, _ := os.Create("/tmp/foo") // file is *os.File
writer := io.Writer(file)        // writer is io.Writer backed by an *os.File

switch x := writer.(type) {
case io.Reader:
panic("What?!")
default:
fmt.Println("It's not a reader.")
}
}

Re: Union/Sum Types 9/9/11 11:44 PM
Thanks for explaining it.
Re: [go-nuts] Union/Sum Types Eleanor McHugh 9/10/11 3:02 AM
On 8 Sep 2011, at 04:28, Russ Cox wrote:
> We don't have the time to engage in lengthy
> design discussions about every language feature
> we considered and declined, but this should give
> a flavor of the complications.
>
> What does
>
> type RW union {
>    io.Reader
>    io.Writer
> }
>
> mean?  Or is it disallowed?
> (That would be pretty unfortunate.)

Firstly don't call it a union as that's incorrect: a Variant is a subset of interface{} which can contain any one of the specified types at a given time, not a type which is the union of all the specified types (i.e. let's ditch the C terminology because it confuses matters).

type RW variant {
  io.Reader
  io.Writer
}

> What happens if you have
>
>    var r io.Reader = os.Stdin  // an *os.File
>    var rw RW = r
>
> Can you say rw.(io.Writer) and successfully pull out the *os.File (which is after all both).

The language spec already specifies the order in which a type switch will compare cases and I cannot see a reason why a type assertion wouldn't return the correct type either.
The more interesting question is whether or not a variant should be allowed to possess its own method set because clearly it cannot be relied upon to expose a consistent method set for its contained items. Personally I think it should as this would allow much of the manual type checking associated with its use to be factored out in one place, however that would make variants and interfaces asymmetric. The spec would also have to explicitly forbid type embedding for variant types, so they'd asymmetric to the normal type system as well.

> What is the zero value of a union?
> Why is that okay?

The obvious answer is nil as that has unique type properties, but that runs counter to the point of a variant type. Perhaps this is the one place in the language where the zero value should be considered explicitly erroneous, so a variant type can be declared without specifying content but any attempt to read from it or invoke methods on it until a value has been assigned will generate a panic.

> And so on and so on.  It gets complicated very fast.

Yes, and no. However a robust variant type with its own method set could lead to more succinct code without damaging readability or maintainability so the experiment is certainly worth considering.


Ellie

Eleanor McHugh
Games With Brains
http://feyeleanor.tel
----
if _, ok := reality.(Reasonable); !ok { panic(reality) }

Re: Union/Sum Types j...@webmaster.ms 9/10/11 7:15 AM


On Sep 9, 9:57 pm, Kyle Lemons <kev...@google.com> wrote:
> > On Fri, Sep 9, 2011 at 1:00 PM, j...@webmaster.ms <j...@webmaster.ms> wrote:
> > > It is only question of the syntax confusion.
> > > I think, Han-Wen wanted to say that variant types can be equal to
> > > interface{} with some compile-time constraints.
>
> > > type LeafNode *Leaf | *Node  // let's define it more like they look in
> > > ML and Haskell in order not to confuse
>
> > > that would mean
> > > type LeafNode interface {}
>
> > > var ln LeafNode
> > > a := ln.(*Leaf) // ok
> > > b := ln.(*Node) // ok
> > > b := ln.(int) // <----------------- error in compile time, not in
> > > runtime
>
> > Right. There could also be an error if one of the types is missing
> > from a type switch that uses the interface type,
>
> >  var ln LeafNode
> >  switch ln.(type) {
> >  case *Leaf:
> >    log.Println("leaf")
> >  }  // compile time error: missing case for *Node.
>
> Perhaps this is something that could be handled by govet, possibly with a
> properly formatted annotation in the type comment.

I do not think it would be easy to adapt govet for this.
At least there is one case where a runtime check is required:

var a interface{} = ....
b := a.(LeafNode)

becames:

if _, ok := a.(*Leaf); !ok {
  if _, ok := a.(*Node); !ok {
    panic("interface conversion")
  }
}
b := a

Re: [go-nuts] Union/Sum Types Steven Blenkinsop 9/10/11 9:04 AM
On Sat, Sep 10, 2011 at 6:02 AM, Eleanor McHugh <ele...@games-with-brains.com> wrote:
Firstly don't call it a union as that's incorrect: a Variant is a subset of interface{} which can contain any one of the specified types at a given time, not a type which is the union of all the specified types (i.e. let's ditch the C terminology because it confuses matters).

Union isn't terminology, it's set theory terminology, which is directly applicable to type systems. The C use is actually a union of the members, rather than a union of the types which is what we're talking about. That brings up the question, what kind of union would actually be useful in Go? You're saying a variant, but I'm not sure that would best match Go's type system or type switch syntax.
 
> What is the zero value of a union?
> Why is that okay?

The obvious answer is nil as that has unique type properties, but that runs counter to the point of a variant type.

It may run counter to the point of a variant type, but for a union type, that would be a valid property. I don't think the use case in Go is the same as in languages that have variants. They wouldn't be used to construct option types, considering the presence of nil. Pointers and interfaces make static assurances that they refer to the right thing... unless they're nil. I don't see how a union type would be any different.
 
Perhaps this is the one place in the language where the zero value should be considered explicitly erroneous, so a variant type can be declared without specifying content but any attempt to read from it or invoke methods on it until a value has been assigned will generate a panic.

The problem with what you're suggesting is that it has a "poison in the well" effect, so it doesn't compose well, especially when you consider that it could be via non-exported fields of a struct. There are ways of solving this problem that would work throughout the entire language if that were seen as worthwhile, but this isn't the way to go about it.
Category Types (was Re: [go-nuts] Union/Sum Types) Eleanor McHugh 9/11/11 6:26 AM
On 10 Sep 2011, at 17:04, Steven Blenkinsop wrote:
> On Sat, Sep 10, 2011 at 6:02 AM, Eleanor McHugh <ele...@games-with-brains.com> wrote:
> > Firstly don't call it a union as that's incorrect: a Variant is a subset of interface{} which can contain
> > any one of the specified types at a given time, not a type which is the union of all the specified types
> > (i.e. let's ditch the C terminology because it confuses matters).
>
> Union isn't C terminology, it's set theory terminology, which is directly applicable to type systems. The C use is actually a union of the members, rather than a union of the types which is what we're talking about.

I was actually referring to the code example when I wrote those words, as it looked essentially identical to a union in C. Further there was no suggestion that the union type should also possess its own method set, further supports the implied equivalence - especially to the bulk of programmers who either don't have a background in type theory, or like myself possess only a lazy, hazy recollection of it.

> That brings up the question, what kind of union would actually be useful in Go?

If the purpose of our enquiry is to introduce a union without already having a reason for its existence then certainly this is a good question. However there is a very compelling reason for some kind of union type: to facilitate generic programming.

> You're saying a variant,

In hindsight I'd prefer to call it a category as its three key features:

1. can be described in terms of a singular choice between a set of existing valid types;
2. possesses a method set which expresses homomorphic structure for the types it categorises;
3. doesn't support type embedding so represents a fundamental type;

combined strike me as analogous to a category with formally defined functors. At the same time it's a fully fledged concrete type which can implement interfaces in its own right without ambiguity, and where the contained type can be asserted as required.

This makes it a useful black box for building generic behaviour including solving the underlying problems which caused me to postulate a structural template type some months ago without any of the deficits identified in the subsequent discussion.

> but I'm not sure that would best match Go's type system or type switch syntax.


The internal representation probably wouldn't be much different to that used for interfaces, so similar mechanisms for type assertion etc. should apply with the main weirdness being the introduction of category{} which is equivalent to struct{} - however as the latter is already a valid type I'm not sure this would be a problem in practice.

What syntactic changes can you see the introduction of such a type requiring?


Ellie

Eleanor McHugh
Games With Brains
http://feyeleanor.tel
----
if _, ok := reality.(Reasonable); !ok { panic(reality) }

Category Types (was Re: [go-nuts] Union/Sum Types) Steven Blenkinsop 9/12/11 8:38 PM
On Sun, Sep 11, 2011 at 9:26 AM, Eleanor McHugh <ele...@games-with-brains.com> wrote:
>
> > That brings up the question, what kind of union would actually be useful in Go?
>
> If the purpose of our enquiry is to introduce a union without already having a reason for its existence then certainly this is a good question. However there is a very compelling reason for some kind of union type: to facilitate generic programming.

That's a good focus. One of the main issues facing a generics implementation in Go is that interfaces are an insufficient type constraint for many generic algorithms to be useful. For example, you can't do anything with built-in types, since these don't have methods.

 
>
> > You're saying a variant,
>
> In hindsight I'd prefer to call it a category as its three key features:
>
> 1. can be described in terms of a singular choice between a set of existing valid types;

If you're going to do this, you might as well move to explicit tags rather than using types as the tags, which means you end up with variants again (basically).

type Stringer interface { String() string }
type Cat2 category { A; B }
type Cat3 category { A; B; C }
// A and B implement Stringer, C does not

The only way to get a Stringer or a Cat2 from a Cat3 is to fully decompose into the individual types (objects), then assign to some commonly visible variable(s) the result, or repeat the code in each object case. You could create a separate syntax from type assertion for the singular type resolution, but then you'd essentially have two type assertions with slightly different semantics. So you'd have to move away from using the types themselves as the tags. Of course, maybe I'm missing something (see down).

 
> 2. possesses a method set which expresses homomorphic structure for the types it categorises;
>
> 3. doesn't support type embedding so represents a fundamental type;
>
> combined strike me as analogous to a category with formally defined functors. At the same time it's a fully fledged concrete type which can implement interfaces in its own right without ambiguity, and where the contained type can be asserted as required.

Can you please elaborate on this a bit? I'm not up on category theory (though I'm interested). Explain the way you'd specify it, which is a good test for whether its something even worth thinking about. Math is good for inspiration, but bad for getting programmers to use something. Chances are, I've missed something very fundamentally elegant which negates my concerns.

My spidey sense is telling me this might be a good idea for an experimental functional language...
Re: Category Types (was Re: [go-nuts] Union/Sum Types) Eleanor McHugh 9/13/11 5:50 PM
On 13 Sep 2011, at 04:38, Steven Blenkinsop wrote:
> On Sun, Sep 11, 2011 at 9:26 AM, Eleanor McHugh <ele...@games-with-brains.com> wrote:
> >
> > > That brings up the question, what kind of union would actually be useful in Go?
> >
> > If the purpose of our enquiry is to introduce a union without already having a reason for its existence then certainly this is a good question. However there is a very compelling reason for some kind of union type: to facilitate generic programming.
>
> That's a good focus. One of the main issues facing a generics implementation in Go is that interfaces are an insufficient type constraint for many generic algorithms to be useful. For example, you can't do anything with built-in types, since these don't have methods.

I've proposed a couple of ways around that over the last two years, but unfortunately they've all had (or been perceived to have) defects which were either considered incompatible with Go or didn't mesh with how other languages handle generics.

> > > You're saying a variant,
> >
> > In hindsight I'd prefer to call it a category as its three key features:
> >
> > 1. can be described in terms of a singular choice between a set of existing valid types;
>
> If you're going to do this, you might as well move to explicit tags rather than using types as the tags, which means you end up with variants again (basically).
>
> type Stringer interface { String() string }
> type Cat2 category { A; B }
> type Cat3 category { A; B; C }
> // A and B implement Stringer, C does not
>
> The only way to get a Stringer or a Cat2 from a Cat3 is to fully decompose into the individual types (objects), then assign to some commonly visible variable(s) the result, or repeat the code in each object case. You could create a separate syntax from type assertion for the singular type resolution, but then you'd essentially have two type assertions with slightly different semantics. So you'd have to move away from using the types themselves as the tags. Of course, maybe I'm missing something (see down).

A simple type assertion of the category would be identical to any other type assertion:

c := new(Cat3)
...
...
if c, ok := c.(Stringer); ok {
  ...
}
...
...
switch c := c.(type) {
case A:            // handle type A
case B:            // handle type B
case Stringer:  // handle type Stringer
}

>  > 2. possesses a method set which expresses homomorphic structure for the types it categorises;

However for the behaviours common to the category a simple method call hides the complexity.

> > 3. doesn't support type embedding so represents a fundamental type;
> >
> > combined strike me as analogous to a category with formally defined functors. At the same time it's a fully fledged concrete type which can implement interfaces in its own right without ambiguity, and where the contained type can be asserted as required.
>
> Can you please elaborate on this a bit? I'm not up on category theory (though I'm interested). Explain the way you'd specify it, which is a good test for whether its something even worth thinking about. Math is good for inspiration, but bad for getting programmers to use something. Chances are, I've missed something very fundamentally elegant which negates my concerns.

Disclaimer: I'm not an expert on category theory :)

A category can be considered equivalent to a type, or to a group of types which are isomorphic (i.e. possess similarity of structure) when considered purely in terms of their common functors (homomorphic - or structure-preserving - functions). There's a strong similarity to interfaces in that these identify structural isomorphs based on similarity of method set, however where an interface is inferred based upon the homomorphisms which characterise it, a category would provide a mechanism whereby such homomorphisms could be implemented for a fixed set of types.

Syntactically this would look like this:

type A category {
        B
        C
}

type Action interface {
        DoSomething()
}

func (a A) DoSomething() {
        switch a := a.(type) {
        case B:                        a.DoSomethingInB()
        case C:                        a.DoComethingInC()
        }
}

func UseCategory(i interface{}) {
        if i, ok := i.(Action); ok {
                i.DoSomething()
        }
        if i, ok := i.(A); ok {
                i.DoSomething()
        }
}

> My spidey sense is telling me this might be a good idea for an experimental functional language...

Probably, but as category theory has roots in topology and structure it's probably applicable to any language.


Ellie

Eleanor McHugh
Games With Brains
http://feyeleanor.tel
----
raise ArgumentError unless @reality.responds_to? :reason

Re: [go-nuts] Union/Sum Types Kevin Ballard 9/19/11 2:55 PM
I just wanted to point out that the change to path/filepath.Walk() in the new weekly would have benefited from union types. Currently the WalkFunc is typed as

type WalkFunc func(path string, info *os.FileInfo, err os.Error) os.Error

and it uses a special constant SkipDir as a return value that indicates the directory should be skipped. But this is slightly confusing and is a mild abuse of the type system; it would have been a lot nicer if we could have represented this as

type WalkValue int
const (
    SkipDir WalkValue = iota
)
type WalkFunc func(path string, info *os.FileInfo, err os.Error) union { os.Error, WalkValue }

Granted, this would be even better with ADTs.

-Kevin

--
Kevin Ballard
http://kevin.sb.org
kbal...@gmail.com
Re: [go-nuts] Union/Sum Types Paul Borman 9/19/11 3:35 PM
I am not going to suggest changing Walk, but if you dislike the dual purpose of os.Error it could have returned (skipdir bool, err os.Error).  No need for a union.
Re: [go-nuts] Union/Sum Types r 9/19/11 3:44 PM

On Sep 19, 2011, at 3:35 PM, Paul Borman wrote:

> I am not going to suggest changing Walk, but if you dislike the dual purpose of os.Error it could have returned (skipdir bool, err os.Error).  No need for a union.

The signature was complicated enough I already, and I decided that for the very (extremely) rare case of skipping a directory's contents, it was worth not mucking up the signature further.

-rob


More topics »