ADTs and Interfaces

[thwd]

At yesterday's Go 1.6 release party, an interesting discussion took place:

We were talking about Go's type system and I argued that algebraic data types (ADTs) would, in my opinion, be the missing vector in a fully orthogonal type system for Go. In short, my argument was that while we have an product type (struct), we don't have a sum type. I also contrasted our type 'language' with a regular one and again, while we have sequence (structs) and repetition (slices), we lack alternation. One of the attendees referred me to the FAQ, where ADTs are disqualified because their coexistence with interfaces is hard.

That got me thinking: aren't interfaces our sum type? Given static, AOT compilation, and implicit interface implementation. If I wanted to express "A or B" (where A and B are types), I just need to have A and B implement one method in common, which no other type implements (a dummy, unexported one). For types defined outside of my package, I'm out of luck, though.

So on to my question: what interferes with a way to express "type C is A or B" directly in the language if we implemented for C to be the interface with all of the common methods between A and B, plus a compile-time check that ensures that no other type that also happens to implement the same methods can be converted to C?

Insights welcome.

[Jan Mercl]

On Thu, Feb 18, 2016 at 11:33 AM thwd <sedevel...@gmail.com> wrote:

> Insights welcome. 

For example, recently: https://www.reddit.com/r/golang/comments/46bd5h/ama_we_are_the_go_contributors_ask_us_anything/d03t6ji

--

-j

[thwd]

Thank you for this link, Jan. I hadn't seen it.

What do you think of the idea of sum types *being* interfaces, as opposed to being something of their own?

[Jesper Louis Andersen]

On Thu, Feb 18, 2016 at 1:21 PM, thwd <sedevel...@gmail.com> wrote:

What do you think of the idea of sum types *being* interfaces, as opposed to being something of their own?

An interface is a pair of an underlying value and it's method set. This means the value has a type and the method set is operating (implicitly) on that type.

In the type theory literature, the name for such a beast is an existential type.

There is an interesting cooperation between these existential types (using the 'exists' quantifier) and parametric types (using the 'forall' quantifier), which the following post on Stack Overflow explains pretty well:

http://stackoverflow.com/questions/292274/what-is-an-existential-type

When you give me an existential/interface, I only know which method set is valid, nothing else about the underlying type. In turn, I get an enormous amount of abstraction power which can be seen in the generality of interfaces such as Reader and Writer. Things start composing in ways you cannot have without existentials.

Likewise, when you give me a universal/parametric-polymorphic, you know I have no way of manipulating it. In turn, I get an enormous amount of abstraction power which can be seen in the generality of interfaces such as Map<K, V>, List<A>, and so on. Things start composing in ways you cannot have without universals.

Go have existentials, but no universals.

Standard ML have universals, but no existentials.

In a way, the two notions are duals of each other. And they both come with some overhead for an implementation since you have to eventually box universals and follow a pointer for an existential.

Sum types, on the other hand, are completely different and orthogonal to the above, and I don't think I would characterize interfaces as sums, since the existential notion fits far better to the idea.

--

J.

[Donovan Hide]

Not really related to the existential questions raised here, but related to the AMA question and answers on variant/sum types. Recently I've been working with Go on implementing XDR data structure encoders and decoders and also DTLS message encoders and decoders (which are very XDR-like). It's a little frustrating when you compare Go interfaces with how well Rust handles these scenarios (nested variant types within parent variant types) with its enum type:

https://doc.rust-lang.org/book/enums.html

As a concrete example you can see how you end up hacking such features into a Go codec library:

https://github.com/davecgh/go-xdr/pull/6/files

The result is you end up having structs with redundant fields for all the different types, or alternatively you have to write custom encoders and decoders for each struct which have knowledge of the nested arms in the wire format and generally treat them as separate structs or anonymous or empty interfaces. 

I'd be very happy if some consideration was given to adding something like variant types to Go 2! I think it would help add a lot of automatic type safety to some very common Internet protocol standards. 

[thwd]

On Thursday, February 18, 2016 at 1:54:01 PM UTC+1, Jesper Louis Andersen wrote:

Sum types, on the other hand, are completely different and orthogonal to the above, and I don't think I would characterize interfaces as sums, since the existential notion fits far better to the idea.

I think I understood.

- Isn't then a tagged union a way to implement existential types?

- And as interfaces are conceptually a type-value pair, aren't they basically a glorified tagged union?

If the answer to both answers is yes, then that reinforces the notion that interfaces are sum types.

[Manlio Perillo]

From a practical point of view, and as far as I know, you can implement sum types (discriminate unions) using interfaces.

However since the compiler does not know the actual types that will take part in the union, it can not allocate memory for them in advance.

Current implementation stores the interface value in a pointer; this means that when you do

var x interface{}

x = 10

the compiler will need to allocate memory to store the value. Memory allocation is not cheap.

So, for me, variant types are the missing piece to keep memory allocation under full programmer control.

Example:

type Foo union {

  int

  float64

  Bar

  interface{}

}

An union is a POD (Plain Old Data, no methods).

Manlio 

[Jan Mercl]

On Thu, Feb 18, 2016 at 3:04 PM Manlio Perillo <manlio....@gmail.com> wrote:

> type Foo union {
>         int
>         float64
>         Bar
>         interface{}
> }

How would, for example, the precise GC handle non-tagged unions with fields of different pointer types?

--

-j

[Aram Hăvărneanu]

On Thu, Feb 18, 2016 at 1:52 PM, Jesper Louis Andersen
<jesper.lou...@gmail.com> wrote:
> In a way, the two notions are duals of each other.

Yes, I they are exact duals. And because they are duals, it's
impossible to implement both while maintaining orthogonality. Most
elements in the Universal x Parametric space project over both.

This is a very powerful abstract argument why generics in Go will
never work well, one which I wish were understood by more people.

--
Aram Hăvărneanu

[Robert Johnstone]

There are some differences.  For example, sum types have a limited and pre-defined set of possible concrete types (A, B, or C), whereas an interface type has an open membership.  As you noticed (and has been mentioned by the Go developers), there is a lot of overlap between the interfaces and sum types, but I would not confuse them.

[thwd]

On Thursday, February 18, 2016 at 3:34:05 PM UTC+1, Robert Johnstone wrote:

There are some differences.  For example, sum types have a limited and pre-defined set of possible concrete types (A, B, or C), whereas an interface type has an open membership.

If we consider that Go is compiled ahead of time, the open membership is more of a automatically calculated finite set of possible members. My question is rather if there is any case in which the more general interface type cannot be restricted to behave as a sum type. Or, in other words, if an implementation of sum types using/being interfaces would not be possible in some case.

[Manlio Perillo]

I don't know the internal of the GC, so I don't have an answer.

However I have some additional notes about this:

https://www.reddit.com/r/golang/comments/46bd5h/ama_we_are_the_go_contributors_ask_us_anything/d043ukb

The first issue is the zero value for an union type.

The zero value of an union is similar to the zero value of s struct.

I'm not sure to understand the issue, so it is possible that I'm missing something.

The second issue is intefaction between union and interfaces.

As an example:

type Example union {

    io.Reader

    io.ReaderAt

}

When you want to store a *bytes.Reader, it is up to you to decide how it should be stored

var x Example

x.Reader =buf

or

x := Example{Reader: buf)

Once you set a value in an union, accessing other fields will panic.

When you have a zero value of an union, you can access every fields and they will return the zero value for the field type. 

Manlio

[thwd]

Guys, I don't want to be rude but this question is about how sum types could be implemented in terms of interfaces. Not about a separate sum type and how it would theoretically interact with interfaces.

Maybe open a different thread for this?

[Jesper Louis Andersen]

On Thu, Feb 18, 2016 at 3:26 PM, Aram Hăvărneanu <ara...@mgk.ro> wrote:

This is a very powerful abstract argument why generics in Go will
never work well, one which I wish were understood by more people.

There are examples of type systems which merges the two concepts and does so relatively well. Haskell is one example of a real language existing today which does it. The type theory of keeping such a mixing safe is, however, somewhat complicated. Lots of type features are very easy to understand in isolation. But mix them and the complexities shows up.

A good argument, however, is that not all features are desired in a language just because you can add them. As an example, a universal value enjoys the extremely important concept of parametricity (due to Reynolds). A function which isn't allowed to scrutinize the type but only pass it along has to, by definition, treat all such types the same. The reasoning about such a function is much stronger because it is limited what it can do. It's dual, ad-hoc polymorphism, is more powerful from an implementation point of view because you can recognize certain optimizations as a programmer. But now your general reasoning is out of the question.

As an aside, both existentials and universals have an overhead. I much prefer a slightly slower program for having them in a language, but I do recognize the interesting outcome of Go, having eliminated universals. From a research-perspective, the question is how far can you get in programs without that feature, and can you use other features to stand in for the missing universals.

--

J.

[Manlio Perillo]

Il giorno giovedì 18 febbraio 2016 16:04:24 UTC+1, thwd ha scritto:

Guys, I don't want to be rude but this question is about how sum types could be implemented in terms of interfaces.

They can not be implemented using interfaces, but only with a separate type know to the compiler.

> [...]

Regards  Manlio

[Jesper Louis Andersen]

On Thu, Feb 18, 2016 at 2:42 PM, thwd <sedevel...@gmail.com> wrote:

I think I understood.

- Isn't then a tagged union a way to implement existential types?

- And as interfaces are conceptually a type-value pair, aren't they basically a glorified tagged union?

If the answer to both answers is yes, then that reinforces the notion that interfaces are sum types.

Most type-theory and semanticist nerds try to remove themselves from particular implementations of the logic and just say "this thing works logically". Implementations will always map the concept of the logic to a particular machine, and the machine which is currently popular is a quasi Havard/Neumann machine[0]. "It is an implementation detail".

If the tag is globally unique in the program, then you can use the tag in a lookup table to find the appropriate method set to execute. Many implementations of sum-types reuse the tags however and let them overlap, relying on guarantees given by the type system to keep them apart. This helps separate compilation as you can compile distinct modules without worrying too much about tag overlapping. In such an implementation, you need to refer to the method set, much like you would in the current Go implementation.

Sum types are more defined by what they do *not* have:

* If I have two sum types A and B, I cannot seamlessly replace one with the other in the program. They are different types. In contrast, the union of existentials is "global" in the sense that if I say I require a Reader, I don't care at all if it is an A or B. Or anything else in the future the programmer might cook up. The fact that you can augment the program after-the-fact tiptoes into the functional-programming problem called "The expression problem".

* A sum type has no method set. If I'm passed something which is a Reader, I'm guaranteed there is a Read method baked into the value itself. A sum type is just a type, so I would need to know in what module there were an eventual Read method and then call foo.Read to get at it. Note how this tightly couples the 'foo' module into your code all of a sudden. To rid yourself of this you need parameterized modules, called "functors" in Ocaml/StandardML[1].

* A sum type can often be either transparent or opaque in different scopes of the program. When the type is transparent, that scope is allowed to match/deconstruct/dissect its contents. When the type is opaque it is abstract and can only be passed on. Programming with sum-types in-the-large has to rely on such imposed forced abstraction in order to make sure values modularize well. Arbitrarily breaking abstraction barriers tend to breed tight coupling in your programs.

One thing to look out for in a lot of programming language theory is that some concepts ends up "embedding" themselves in other concepts. I.e., you can perhaps recast one idea in the language of another idea. Recognizing these embeddings are great when you are trying to prove your semantics enjoys a certain property because you can then prove the property for the more general case and argue that the special case is just an embedding. It may be you've found such an embedding of sum-types in interfaces, but you would have to prove it first. Usually the devil is in the details.

This is also why the concept of a Monad is so alluring to the semanticist. It embeds *any* side effect, so once you have a proof that the monadic construction enjoys your property, you can seamlessly add exceptions, state, continuations, concurrency, transactional memory, and a whole lot of other effects to your programming language. At no proof-theoretic cost! You get it almost for free. Yet, the practical me is somewhat more hesitant when it comes to actually programming with said monads, as is done in Haskell.

[0] Quasi here because of Tomasulo's algorithm, among other things. You can only self-modify under the presence of appropriate barriers.

[1] As always, recognize that the word functor is heavily overloaded. It means different things in C++, Prolog, Haskell, ML and Math though some of the notions coincide in either form, spirit or definition.

--

J.

[Rob Pike]

Mr Andersen: A long-overdue "thank you" for your careful, patient, and very informative messages to this list over the years.

-rob

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Donovan Hide]

It has been enjoyable to read Jesper's detailed answers with reference to ML-like implementations of ADT's, but I'm still not really left the wiser as to why it is impossible to have variant types in Go :-)

I was intrigued to read about how Rust uses a flat memory layout to implement enums:

http://smallcultfollowing.com/babysteps/blog/2015/05/05/where-rusts-enum-shines/

Although maybe this is not defined by a spec:

https://www.reddit.com/r/rust/comments/1lpmrx/storing_structsenums_of_structs_more_compactly_in/cc1jbku

If Go had variant types where each instance has padding to make them all of equal length to the longest possible defined variant type of that set, would that not make it easier to access the fields of each type with a simple compile-time table? As for the question of nested interface fields, could there not be some restrictions applied for a variant type, so that it can't have a nested interface field?

I'm no language design expert. I enjoy Go and love interfaces as they are. However, using Go for working with over the wire protocols (TLS/DTLS/XDR) which were designed with discriminated unions in mind can be very frustrating. Here's a particularly gnarly example of an over-the-wire protocol that is horrendous to map to Go types:

https://github.com/stellar/stellar-core/blob/master/src/xdr/Stellar-transaction.x

Another variant type use case was trying to implement Phil Bagwell's HAMT data structure in Go, where the overhead of using an interface{} to represent either a bitmap/pointer or a key/value pair was too large to make it worth while. There's always unsafe, but then we're back to C!

Another use case is passing both error messages and non-error message over the same channel.

This isn't the generics debate all over again, it's just a request for some serious consideration to be given to variant types for Go 2.0.

[Russ Cox]

Not well. A concurrent GC is the real problem. If the implementation of union were a discriminator word followed by different kinds of memory based on the discriminator, a concurrent GC would need some way to read that whole piece of memory atomically, so that it got a consistent snapshot. Otherwise, even GC'ing a race-free single-goroutine program, the GC might misinterpret a float64 as an interface{} and crash the machine.

Interfaces used to have the property that the second word might or might not be a pointer based on the first word, and they caused exactly the same trouble for the GC. The solution is that now the second word is always a pointer. The alternative was that every interface assignment use a double-word atomic store, which was too much.

If this kind of 'union' existed in Go, those considerations suggest it would need to be represented as a fixed 'type+ptr' pair, so that what might be in the union at a memory level would be *int, *float64, *Bar, or *interface{}. And then the motivation, namely control over memory layout, is gone.

This is one of the many reasons Go does not have unions.

Russ

[Russ Cox]

On Thu, Feb 18, 2016 at 5:32 AM, thwd <sedevel...@gmail.com> wrote:

That got me thinking: aren't interfaces our sum type? Given static, AOT compilation, and implicit interface implementation. If I wanted to express "A or B" (where A and B are types), I just need to have A and B implement one method in common, which no other type implements (a dummy, unexported one).

This is a common pattern. You can see it in the standard library in the go/ast and go/constant packages, for example. However, note that this is really a "best effort" check to help you avoid mistakes, not a strong guarantee.

What you actually get from doing this is not "A or B" but "A or B or nil or some type T that embeds an A or B". The nil is annoying but the embedding part eliminates any appearance of a guarantee. But for most uses the best effort check is really the goal. There are plenty of other ways to break Go programs.

Russ

[Donovan Hide]

How would, for example, the precise GC handle non-tagged unions with fields of different pointer types?

Not well. A concurrent GC is the real problem. If the implementation of union were a discriminator word followed by different kinds of memory based on the discriminator, a concurrent GC would need some way to read that whole piece of memory atomically, so that it got a consistent snapshot. Otherwise, even GC'ing a race-free single-goroutine program, the GC might misinterpret a float64 as an interface{} and crash the machine.

I guess immutability would solve that problem, in the same way as "final" in Java and "readonly" in C# do for class fields. 

[Aram Hăvărneanu]

On Thu, Feb 18, 2016 at 4:11 PM, Jesper Louis Andersen
<jesper.lou...@gmail.com> wrote:
> There are examples of type systems which merges the two concepts
> and does so relatively well. Haskell is one example of a real
> language existing today which does it. The type theory of keeping
> such a mixing safe is, however, somewhat complicated. Lots of type
> features are very easy to understand in isolation. But mix them and
> the complexities shows up.

Yes, I think code has some complementary properties (like in quantum
mechanics) when it comes to expressing "existential" or "universal"
qualities, which leads to some sort of uncertainity principle-like
inequality that must translate into some other property of the code.

For Go, which lives in an "existential" universe, this translates
to sometimes awkward, but *explicit* code written by the programmer.

For language which have both, this translates to intricate *implicit*
interactions between the features of the language, which the
programmer must understand in order to write correct code.

--
Aram Hăvărneanu

[thwd]

Hi Russ, thank you for your thoughts.

Suppose there was a mechanism (syntactic or otherwise) to define an interface "X" in terms of arbitrary other types "Y" and "Z".

 - We state that the types "Y" and "Z" (and *only these* types) implement "X". Regardless of their method sets.

 - We define the method set of "X" to be the intersection of the method sets of "Y" and "Z".

 - We disallow embedding of exported interfaces with unexported methods.

Such a feature could potentially eliminate the need for nil in the language. I have to prove it but I think it's doable.

If I was to propose this formally (for a future version of Go), do you think it would stand a chance of actually being considered and reviewed?

[Jan Mercl]

On Fri, Feb 19, 2016 at 1:37 PM thwd <sedevel...@gmail.com> wrote:

> Such a feature could potentially eliminate the need for nil in the language. I have to prove it but I think it's doable.

What would be the zero value of pointer types?

--

-j

[thwd]

It wouldn't exist! :) You'd be able to use option types [1] to express the absence of a value for the pointer.

https://en.wikipedia.org/wiki/Option_type

[thwd]

Just to be perfectly clear, I mean a non-parametric option. E.g. (*Foo or Nothing) where Nothing is something like struct{}.

[Jan Mercl]

On Fri, Feb 19, 2016 at 2:24 PM thwd <sedevel...@gmail.com> wrote:

> It wouldn't exist! :) You'd be able to use option types [1] to express the absence of a value for the pointer.

So the declaration like

        var p *int

or

        type node struct {

                i int

                next *node

        }

would not be allowed?

--

-j

[thwd]

As you know,

    var p *int

is an implicit way to write

    p := (*int)(nil)

If we rule out nil as a value then you have two possibilities:

 - Give "p" an actual value i.e. point at something.

 - Make "p" of type "*int or Nothing" and let it be Nothing until you assign something else to it.

This makes the cases where p might be "absent/nothing/nil" explicit.

Second example: type node { ... } is perfectly valid, but field "next" is guaranteed to point at something. If there might be no next, then you make "next" of type "*node or Nothing".

This is common in functional languages and oh so nice. In the same vein as Go forces you to think about errors, option types make you think about the case where a value might be absent.

[Axel Wagner]

Hey,

> If we consider that Go is compiled ahead of time, the open membership is
> more of a automatically calculated finite set of possible members.

The compilation model in go is per-package. Thus the compiler doesn't
know about types in other packages (in general. There's of course
whole-program analysis, but that's expensive). So as long as other
packages might be able to implement your type, the compiler needs to
treat it as open.

> My question is rather if there is any case in which the more general interface
> type cannot be restricted to behave as a sum type. Or, in other words, if
> an implementation of sum types using/being interfaces would not be possible
> in some case.

An interface is defined by it's method set. A struct embedding another
type will get all methods of that type promoted. Corollary: Given *any*
interface I, the definition type S struct { I } will give you an
implementation of I. As S can come from above, as per the previous
paragraph, the compiler can't treat interfaces ever as closed sets.


That's the fundamental issue. Of course you can use interfaces as sum
types *in practice*. In practice, it's completely valid to define an
interface with an unexported method (thus making the only possible
implementation in a different package by embedding) and just doing a
table-flip and panic if anyone ever attempts that (which, in practice,
will never occur). That's indeed the general advise when people want
ADT-like behavior. But you negate most of the advantages of both
interfaces and ADT in the process (for example you still need a default
branch on every type switch, to create a runtime-panic, as the compiler
can't do the check for you).

So when people ask for ADT they usually ask for types that are *defined*
to be closed, so that a) they can elide the "this is an invalid value"
case in their switches and b) the compiler complains when destructuring
non-exhaustively (this is the "instead of foo, error we should be able
to return sum{ foo, error } to enforce correct error
checking"-argument). It would be a strict addition to the utility of the
type-system (but the reasons why it's not added are also well-known).

Best,

Axel

[Manlio Perillo]

Il giorno venerdì 19 febbraio 2016 03:10:41 UTC+1, Russ Cox ha scritto:

On Thu, Feb 18, 2016 at 9:09 AM, Jan Mercl <0xj...@gmail.com> wrote:

On Thu, Feb 18, 2016 at 3:04 PM Manlio Perillo <manlio....@gmail.com> wrote:

> type Foo union {
>         int
>         float64
>         Bar
>         interface{}
> }

How would, for example, the precise GC handle non-tagged unions with fields of different pointer types?

Not well. A concurrent GC is the real problem. If the implementation of union were a discriminator word followed by different kinds of memory based on the discriminator, a concurrent GC would need some way to read that whole piece of memory atomically, so that it got a consistent snapshot. Otherwise, even GC'ing a race-free single-goroutine program, the GC might misinterpret a float64 as an interface{} and crash the machine.

Thanks, Russ.

Is this a solvable problem with a "better" GC, or does this means that GC and low level system language are not compatible?

> [...]

Manlio

[Ian Lance Taylor]

I'm not sure I understand your question. Are you saying that a
language that does not support an untagged union of a pointer type
with a non-pointer type is not a low level system language? I'm not
sure I accept that implied claim. In any case, I think that such a
language could not be compatible with precise concurrent GC, though it
would be compatible with conservative and/or stop-the-world GC.

Ian

[Ian Lance Taylor]

On Fri, Feb 19, 2016 at 6:09 AM, thwd <sedevel...@gmail.com> wrote:
> As you know,
> var p *int
> is an implicit way to write
> p := (*int)(nil)
>
> If we rule out nil as a value then you have two possibilities:
> - Give "p" an actual value i.e. point at something.
> - Make "p" of type "*int or Nothing" and let it be Nothing until you assign
> something else to it.
>
> This makes the cases where p might be "absent/nothing/nil" explicit.
>
> Second example: type node { ... } is perfectly valid, but field "next" is
> guaranteed to point at something. If there might be no next, then you make
> "next" of type "*node or Nothing".
>
> This is common in functional languages and oh so nice. In the same vein as
> Go forces you to think about errors, option types make you think about the
> case where a value might be absent.

That is a fine language, but it's not Go. That kind of change is
extremely unlikely to go into any future version of Go.

Ian

[Ian Lance Taylor]

On Fri, Feb 19, 2016 at 4:37 AM, thwd <sedevel...@gmail.com> wrote:
>
> Suppose there was a mechanism (syntactic or otherwise) to define an
> interface "X" in terms of arbitrary other types "Y" and "Z".
> - We state that the types "Y" and "Z" (and *only these* types) implement
> "X". Regardless of their method sets.
> - We define the method set of "X" to be the intersection of the method sets
> of "Y" and "Z".
> - We disallow embedding of exported interfaces with unexported methods.
>
> Such a feature could potentially eliminate the need for nil in the language.
> I have to prove it but I think it's doable.
>
> If I was to propose this formally (for a future version of Go), do you think
> it would stand a chance of actually being considered and reviewed?

Any proposal will be considered and reviewed, but it has to bring
benefits that outweigh the costs. We all agree that sum types bring
benefits. The questions center around the costs.

Ian