Type-safe tagged unions in the D programming language
deadalnix.me
deadalnix.me
For one, even in C, most uses of unions fall into two kinds. There are unions that emulate sub-typing and unions that have a manually implemented tag system. Basically, C programmers have to work around the language's deficiencies manually and hope to avoid errors--nothing surprising, I suppose.
More importantly, tagged unions simply make more sense. They are the mathematical dual of structs, which means that having both exposes a natural symmetry in language design. And, just like in physics, symmetry almost always means you're on the right track!
And, of course, once you have tagged unions and structs, you've added algebraic data types to your language. Now just throw in pattern matching and you have a basic system that is both safer and more expressive than the common alternatives. What's not to like?
This is one of the many reasons I'm very excited about Rust and not excited at all about Go.
If you have a tagged union consisting of the elements Foo(int), Bar(char) and Baz(int,string) then to consume such a thing you have to specify what to do with a Foo, what to do with a Bar and what to do with a Baz. You can specify this by giving a struct with a function that consumes Foos, a function that consumes Bars and a function that consumes Bazs. In ML syntax we have:
type Qux = Foo of int | Bar of char | Baz of int * string
type QuxDual = Consumer of (int -> result) *
(char -> result) *
(char * string -> result)
You can see that because of these `result` types duality is not particularly nice in languages based on functions. It's nicer in languages based on processes or continuations, because they have a direct notion of a consumer of something. A consumer of an int is an `int -> result` function but in languages based on processes we can directly take a process that takes an int as an input or a continuation C(int). So in those kind of languages we don't have extra result types hanging around.
For types, this is defined exclusively based on the functions it has. Roughly speaking, the product of two types A and B is the "simplest" structure that has a function to A and a function to B--that is, if you imagine a nice diagram, there is an arrow from A × B to A and an arrow from A × B to B. For structs, these two functions are just field accesses.
The notion of "simplest" here essentially just means that given any other object C with these criteria--that is, a function to A and a function to B--there has to also exist a function C to A × B. I'm skipping some details, but you should get the general gist.
The notion of duality just means taking the above diagram and flipping all the arrows. So the co-product of two types A and B is the "simplest" type A + B that has a function from A to A + B and a function from B to A + B. These functions correspond to tagging elements from A or B as appropriate.
For logical AND, the dual is logical OR. For getting the least upper bound, the dual is getting the greatest lower bound. And, following that same logic, for structs the dual is tagged unions.
I hope that made sense. This is the sort of thing that's much easier to describe interactively with a whiteboard instead of trying to just use ASCII--it practically begs me to draw some diagrams, but my ASCII art is simply not up to par :(.
func(T, ...)
as
t.func(...)
where t is an instance of some type T. This may seem trivial, but it allows for functions to be added to a class or type which is out of your control.
For example, the function to convert a 'string' to a C-style zero terminated string is:
toStringz(string s).
calling the function as s.toStringz() has a much more natural feel, and allows for a much more modular approach than "throw everything in the class", since it can just simply be added on as a uniform function in another module (toStringz is a library feature on the concrete string type). This even works on basic types:
(5.0).sqrt();
!!
I really wish more languages had really simple tagged type support. Sometimes I don't need full on inheritance, things like packet formats would benefit greatly from a dead simple minimal implementation.
[0] http://dconf.org/schedule/index.html [1] http://www.youtube.com/watch?v=e2F2pqeMLuw
D is a failed language design (among countless others) if you ask me. I remember originally it was meant to be a "cleaned up, modernized C++ replacement" but these days it seems to lack any coherent concept.
Rust certainly runs circles around it if you want a "cleaned up, modernized C++ replacement" and thus already has much more momentum than - by now old - D.
Is there any reason to assume that D can still manage to break out of its "obscure enthusiast language" position? That is not a rhetorical question, I am genuinely curious.
But I agree that Rust gives me more hope. Rust's treatment of memory seems like it's obviously the best way to do manual but safe memory management.
I agree that Rust is gaining momentum and it's memory-handling approach is definitely the one I prefer, however, I still like D way to do things.
1. Easy to read and understand code 2. Provably correct 3. Industrial quality
I've been a regular here for 4 years!
D is relatively conservative in terms of features, but it is more broad and complex. D as a language is not minimal, although that is en vogue today. For example, does Rust address SIMD/Vector Extensions [0], Contracts [1], Inline assembly [2]?
Rust is more of a experimental variant of C (or ML) with respect to parallelism and concurrency. Rust is more minimalistic, because it solves problems with general mechanisms instead of special syntax. For example, instead of special syntax for unittests in D [3], in Rust you use the general attribute mechanism in Rust [4].
I do not want to judge them against each other. D is the solid language, which I hope replaces C++ as soon as possible. As a C/C++ programmer you feel at home in D relatively fast. On the other hand, Rust is an interesting language, which might show us a better way to program multicore computers. Learning Rust stretches your mind, instead.
[0] http://dlang.org/simd.html [1] http://dlang.org/dbc.html [2] http://dlang.org/iasm.html [3] http://dlang.org/unittest.html [4] http://static.rust-lang.org/doc/rust.html#attributes
https://mail.mozilla.org/pipermail/rust-dev/2013-April/00342...
There also seems to be some work on SIMD extensions -
You can make tagged unions type safe if you eliminate storage that is interpreted in more than one way. You can do it by requiring immutability, introducing indirection, or by copying the type-variant part. Unless I'm missing something (very possible), this technique doesn't seem to do any of those things, so I don't see how it can be sound.