Losing language features: some stories about disjoint unions
graydon2.dreamwidth.org
graydon2.dreamwidth.org
I'm not saying this was "right" in any sense, but it wasn't just foolish old timers not recognizing that a "better" solution was possible. When you grew up having every single bit of memory threaded by hand (and costing macroscopic amounts of money), you think about memory efficiency differently.
Presumably this was inspired by existing practices in the assembly-language programs.
Many early programming languages have followed the example of FORTRAN.
In October 1964, John McCarthy (which had not only been leading the development of the first LISP, but he had also been a major contributor to ALGOL) has proposed the keyword "union" and he had advocated for safer implementations of disjoint union types. The first such implementation has been in ALGOL 68, a few years later.
Unfortunately, the C language has taken the "union" keyword from ALGOL 68, but instead of implementing proper disjoint union types, the C "union" has been made essentially identical with the FORTRAN EQUIVALENCE from 1956.
The "variant record" of Pascal, was not really better, so that can also be counted as a failure to implement proper union types.
For a long time Pascal and C have been among the most popular programming languages, creating bad habits in the use of unions.
Accessing a value was more laconic in FORTRAN, because you omitted the union name and the "." that are required in C.
The fact that a union is considered a type in C allows the use of a typedef, which removes the need to repeat the definitions for multiple variables, but that is about the only help that you get in C.
Both in C and in FORTRAN you must know the current type of the stored value and there is no protection against using the wrong type. If the current type cannot be determined statically, you must manage manually another variable storing a type tag, in both languages.
Many word address machines, explicitly the PDP-7, it was only the instructions that changed, with ADD being one's complement and YAD being two's
Remember we only got B/C because the PDP-7 didn't have enough ram to implement FORTRAN.
Similar reasons C case switch falls through, the PDP-7 SAD instruction forced it. Then they abused that fall through to support lower case on the PDP-11, which would have been powerful enough for the type of union you are talking about.
Midas/Macro assembly is tangential related but it is really a side effect of word addressable, accumulator/index machines.
IIRC, Lisp is a good example for the difference between equality by value, reference, or even predicated equality.
If you want to think about just how limited the PDP-7 was look at the instructions
www.bitsavers.org/pdf/dec/pdp7/PDP7_Instruction_list.pdf
https://github.com/torvalds/linux/blob/89be9a83ccf1f88522317...
Edit: A bit of background: https://lwn.net/Articles/565097/
But not to worry, the unreadable mess of C unions is not going away. struct folio will eventually absorb all those fields, and more. The only difference is there's a single folio for a whole set of pages, so moving the data there will save a significant amount of memory.
https://github.com/torvalds/linux/blob/89be9a83ccf1f88522317...
I think Go + sum types could be good. Maybe. But, honestly, it's hard to say for sure. First-order effects are great: we have sum types and can use them to model problems. Second-order effects get muddy: We have sum types and they are the ideal solution for a bunch of problems, but without other features they're awkward to use. For example... now you can do a Result type... but if you want to return multiple values in a Result, you need a set/tuple type too. If you do that, is Go's multiple return values concept still a good idea? I could probably go on but hopefully this illustrates the point.
I think a lot of people don't acknowledge why Go is truly so successful. Well OK, first elephant in the room, it's obviously successful because it's backed by Google, a company who can and did throw immense resources at making the implementation and standard library pretty damn good as well as helping to push it, but that alone wouldn't have propelled it to where it is today (I mean, compare it to Dart.)
But beyond that, Go is successful because Go code is very simple to write and leaves the programmer with relatively few things to be concerned about, and yet in spite of that, Go code generally runs reasonably fast, uses relatively small amounts of memory and is generally not very crash-prone. (Some people would happily debate that, but I trust software like restic, esbuild, rclone and Syncthing every day without fail, among other smaller Go programs. I'm OK with making that assertion.)
If you put in the effort to make really good Rust code, the effort is not wasted, but it is a lot of effort when the stupid Go code often does the trick. Consider Discord's presence service: they switched from Go to Rust and massively cut costs and improved latency. Rust wins, Rust better? But... most services will never scale to the point where marginal improvements in latency, throughput or RAM are going to be worth a lot of man-hours worth of programming and ongoing maintenance. Usually throwing a couple more VMs at the problem is just going to be the path of lesser resistance. This was always the case when comparing lower-level to higher-level, but Go amplifies it because the performance gap isn't as big, but the complexity gap remains very large or maybe gets larger.
Is writing Rust code really that hard? No, not at all, it's more that writing good Go code is so relatively easy, the language is simple and the standard library is loaded with useful tools. Go's CLI flag parser is pretty unimpressive, but so many projects just need a very basic flag parser and it works totally fine for that, you just don't need to overthink it 99.99% of the time. Same for net/http, the built-in image and compression codecs, TLS stack, and more. Meanwhile, designing and maintaining good high-quality Rust crates is just relatively hard. You've got to worry about async vs sync, various cfg options like nostd and noalloc, and dealing with a lot of wrinkles in the language. Want to use a dyn trait? You'll need to make sure the trait doesn't have any functions with generic parameters or async; makes perfect sense, but adds tension; you want to avoid unnecessary runtime costs in the ideal case but still have the flexibility to use a dyn trait in other cases. Not to mention the borrow checker and how it interacts with a lot of these design choices. Go code is much dumber, but often times it's sufficient.
And that's the crux of it. Go is simple in a stupid way, rather than an elegant way, but it really makes the most of it. If you want to supplant Go at what it does best, trying to make a better programming language overall may be a bit misguided. It's probably not that hard to come up with a programming language design that is "better" than Go. What's hard, IMO, is coming up with a programming language where the cognitive load increase relative to Go is met with a pay-off that people using Go would consider genuinely worth it. Something like guaranteed data race safety is definitely good enough if it's something someone needs or at least strongly wants for a given use case. Sum types, on the other hand, are very nice thing to have that make modelling data easier and less error-prone, but not having them isn't exactly the end of the world... In Go, people sometimes emulate them with interfaces and type-switches, and it's not fantastic, but it's usually sufficient.
Ocaml probably could/should be more successful, but I'm not sure it competes with Go, I think they're in entirely different wheelhouses. Ocaml feels like it doesn't want to compete with Go, but then again, I only have relatively surface-level knowledge of Ocaml, so I can't really say for sure.
It's basically a fork of the Go lexer/parser that adds Result/Option/Tuple/Set... propagation operators (and more)
and it compiles down to Go code.
Most of the issues you discuss with Rust are not issues in OCaml, as OCaml has GC. The language is simpler, in that programs are concerned with fewer concepts (e.g. no lifetimes), but less expressive in that they cannot formally talk about these concepts (though see the Jane Street work to add in some Rust-like concerns: https://blog.janestreet.com/oxidizing-ocaml-locality/)
If comments on the web are anything to go by, being familiar to C and JS programmers is one of the main reasons for Go's success. I think it has plenty of its own specifics, it's not like e.g. C# which really did start as a straightforward Java clone, but OCaml has even more differences.
This does seem to be quite a conundrum. I don't think there's any argument regarding the merits of functional programming as a paradigm, but imperative just seems easier to wrap one's head around, and frankly most code is really boring and doesn't need to be able to do the super powerful things that functional programming can do with relative ease.
I feel like I'm playing with fire by saying this here, but I think it's true.
I think functional and imperative programming, in practice, tend to have different types of constraints, and there are different things that are easy to reason about in them, and encourage different reasoning methods and approaches, and ways of proving properties about them.
I think that for learning functional programming, being all-in on purely functional programming and never having side-effects or mutation, can be useful. But for practical programming, functional programming is not in itself a virtue just by itself. One should always consider the trade-offs of the specific case one is facing if one is not learning, as such. If a project has decided on a trade-off where purely functional programming is chosen, then maybe continuing with pure FP is fine; but even in such a case, a function that from outside is purely functional, but uses imperative programming internally, for instance for the sake of optimization, can make sense.
There are different advantages and disadvantages to having: pure FP; imperative programming; or different kinds of mixes of FP and imperative programming.
Overall, my approximate opinion is that it does not make sense to be dogmatic about functional programming, except when learning FP.
https://stackoverflow.com/questions/7717691/why-is-the-minim... is arguably a relevant example, though a proper in-place implementation in Haskell might be more fair for comparison. Though I am not certain whether Haskell's lazy evaluation would help or hinder analysis, Ocaml or SML might be better languages for implementing and analysing an in-place implementation variant.
Also, Hacker News is a censorship hole.
https://stackoverflow.com/a/7719971
You can see that the Haskell code is more verbose than the C code.
The kind of folks that dropped Python and Java for Go, would not have picked up OCaml even if it had a better concurrency story 10-15 years ago.
I has enough ML influence on it, as a simplified Scala, and also can compile to native in various ways.
On the other hand you will notice that the only thing Android team only cared about Go, was the Soong build syste, and parts of the GPU debugger.
Maybe, but once you have eg an Option or Either (a.k.a. Result) type, you typically really want to have some functions that work generically on all versions of them. (Though you could probably get away with using Go's version of void*, the empty interface, in a lot of cases?)
Just add first-class tuples to the language.
If we look behind the curtains, go functions somehow return tuples that are automatically unrolled into respective variables, sometimes. That's why if you have f(a, b, c){} and g() (b,c){} you can't do f(a, g()) currently.
It does not unroll it automatically for some reason here. The result remains in "tuple" form ?
I think it may leave some space to have tuples if needed.
In any case, I don't see it as technically infeasible.
It can be changed more easily than in other languages because everyone statically links, but it’s not trivial.
Like Perl's sigils? Or PHP's distinction between 'normal' variables with a $ and variables of function type which have no marking but are case insensitive?
type
StatusCodes = (Success, Ongoing, Done)
type
StatusCodes enumeration (Success, Ongoing, Done)
type StatusCodes int
const (
Success StatusCodes = iota
Ongoing
Done
) type Color interface {
isColor()
}
type Red struct {}
func (r Red) isColor() {}
type Green struct {}
func (g Green) isColor() {}
type RGB struct {
Red byte
Green byte
Blue byte
}
func (r RGB) isColor() {}
func PrintColor(color Color, text string) {
switch c := color.(type) {
case Red:
// print in red here
case Green:
// print in green here
case RGB:
// handle the RGB
}
}
(There is a common misconception among Go programmers that this doesn't seal the type because you can implement a "isColor" method on your own types in other packages, but it won't work. Try it if you want to be sure.)
One could argue they've effectively already been bolted on, all that is missing is some syntax gloss like
sum Color {
Red{}
Green{}
RGB{
Red byte
Green byte
Blue byte
}
}
He also avoided a lot of the more advanced features of Algol68, he thought it too complex, when he designed Pascal
Implementing correctly disjoint unions, i.e. allowing them to be used only exactly like an enumeration in the variable tested by a select/case/switch statement, and then only as the correct type in each of the alternatives, introduces a little overhead in a compiler, but it is certainly not a serious source of bloat in comparison with most other things that must be done by a compiler.
If the programming language designer had clearly in mind how disjoint union types must work, they would have been easy to implement even for the minicomputers and microcomputers of the seventies.
Even Go v1.0 type system is more advanced than Oberon-07 final form.
In my opinion, the most important contributions of Niklaus Wirth to programming languages have been in his early work on Euler, PL360 and ALGOL W, which introduced various features that were novel at that time.
Starting with Pascal in 1970, his programming languages remained reasonably good for teaching programming and how to implement a compiler, due to their simplicity, but all of them were seriously behind contemporaneous languages.
While Mesa of Xerox was a nice and innovative language, that cannot be said about Modula, Wirth's attempt to reimplement similar features after his sabbatical at Xerox, which was only mediocre.
On the other hand the early languages of Wirth were very innovative, e.g. Euler was one of the first 2 languages with pointers, the other being CPL. In contrast with CPL which had implicit pointer dereferencing, Euler had explicit address-of and indirection operators, but it got their syntax right, not like in C, where the indirection operator has been mistakenly defined as prefix, instead of postfix.
Zig is basically Modula-2 type system in C clothing, plus comptime, if only people were equally as hyped back in the 1980's.
The usual "Why Pascal..." fails flat in the presence of Modula-2, which was actually designed as systems language, and not as a language to learn about programming.
Oberon (the 1992 original), for its simplicity, introduced a wider audience to the concept that system programming with automatic resource management isn't something out of this world, even though Cedar is more interesting in features.
I was more interested into Component Pascal and Active Oberon, even though there were the work of other researchers at ETHZ.
Nonetheless it was his work, that inspired me to dig into everything Xerox PARC was doing, and discovering there was more happening there than only Smalltalk.
I became amazed at the work done across Interlisp-D, Mesa, Cedar, how advanced their ideas for what an IDE is supposed to look like, that many mainstream languages still can't offer.
So in a sense that was also a contribution from Niklaus Wirth to everyone that got interested into his work, and decided to go down the rabbit hole.
This seems like a mistake. At the end of the day, a bunch of code and logic has to be written somewhere, and I think it's better done outside the data object, at least some of the time.
Imagine you have the classic Shape class / interface and someone wants to write some code to determine whether a Shape is happy or sad, based on their synesthesia, what are they suppose to do? I guess just add a happy_or_sad() method to the interface? Like, we're just going to pile--err, I mean, "encapsulate"--every possible thing that can be done with the data into the data object?
The OOP way is probably some Shape class hierarchy with a Shape superclass and a bunch of specific Square, Circle, Triangle, subclasses. So I guess you go and modify a dozen subclasses to add your happy_or_sad() method. And you're definitely going to have to fork the code because nobody wants to upstream your personal feelings about which Shapes are happy or sad.
It's better to have a sum type for your Shape and then everyone can put all their code and logic outside of the Shape itself, and the type system will ensure, at compile time, that no Shape variants have been missed, so refactoring is assisted by the type system.
They are all equivalent in principle, but some of them are a lot more annoying to work with, especially when you want to do a pattern matching over multiple values at the same time, or match on nested patterns.
One nice thing about the visitor pattern is that it doesn’t have to match the type hierarchy. For example, you could have a visitor interface method that is invoked for blue shapes, even if there is no BlueShape type. Similarly, the same type hierarchy can support multiple visitor interfaces, so that you can perform different case distinctions on the same value. This is something that sum types can’t do.
Haskell's pattern synonyms should be able to handle this?
The problem with the visitor pattern is that it doesn't compose well. So if you want to match on two values at once, or match deeper into a value, that works well for most pattern matching, but is annoying to piece together with the visitor pattern.
I agree that syntactic sugar for visitor ”matching” would be nice, and it’s something a language could add. The visitor pattern itself doesn’t prevent adding such syntax.
It's not that bad in practice.
You can also simulate it by using if/else everywhere.
At this point, that means you have zero language feature supporting the use case, and type safety is up to the developers implementing patterns correctly everywhere.
In languages of ML linage, we can combine both approaches with a mix of sum types and functors/type classes.
Yes, by default. But doesn't eg Java let you mark classes as final or something like that?
> In languages of ML linage, we can combine both approaches with a mix of sum types and functors/type classes.
I think Rust allows something similar, but I'm not sure whether you'd call it 'ML linage'?
Additionally, modern Java has sum types modeled on the same way as Scala.
Rust is to some extent inspired by ML languages, hence why several OCaml and Haskell refugees also hang around Rust.
Note instead of my worse Optional class, what you are describing is a Shape class where there is a different function for each supported shape. If you add a new shape, everywhere that made a shape visitor would have to be updated do deal with the new shape. (A sibling post described this.)
Amusingly, I recall coworkers that did not want to use the "acceptVisitor" method and would force cast to call over to the methods directly. Caught me incredibly off guard.
https://archive.is/oTbMW works though.
In that talk, Casey Muratori refers to Simula, a PDF of it can be found at https://www.mn.uio.no/tjenester/it/hjelp/programvare/simula/... . You may want to use an OCR tool on that PDF, for instance ocrmypdf is available for a number of Linux distributions. I am not sure if it is the same version of Simula as what is being discussed, but it does have the "connection" statement, at PDF-page 56, which has "inspect" as the first syntactical element. That does look vaguely similar to the pattern matching of ML, but it does not AFAICT support a number of significant features that many love about modern pattern matching, such as nested patterns. Does it have field bindings as part of a pattern, and matching against specific constant values, or only matching the class type? I am not sure if it supports exhaustiveness checking. Does it mandate a finite number of possibilities, to help exhaustiveness checking? And the "connection" statement has two variants. AFAICT, it is the kind of abstraction that is primitive enough that one can get close to its functionality with "switch" in C++ together with a type-cast, and a far cry from what Standard ML (later?) supported. In that light, it might not be surprising that it was not included in C++.
When was pattern matching as we know it in modern times invented, or was it a gradual evolution? https://en.wikipedia.org/wiki/Hope_(programming_language) is cited as introducing https://en.wikipedia.org/wiki/Algebraic_data_type in the 1970s. And Hope had for instance this spin on just one aspect of pattern matching:
> Changing the order of clauses does not change the meaning of the program, because Hope's pattern matching always favors more specific patterns over less specific ones.
This is different from modern pattern matching, where the order (AFAIK generally across modern languages) does matter.
I am not sure that Casey Muratori did a good job of researching this topic, but I am not sure if and how much I can fault him, since the topic is complex and huge and may require a lot of research. Researching the history of programming languages may be difficult, since it would both require a high technical level and also have to be focused on history. One could probably have several full-time university positions just spending their time researching, documenting and describing the history of programming languages. And the topic is a moving target, with the professionals having to have a good understand of multiple languages and of programming language theory in general, and preferably also some general professional software development experience.
All in all, the data types and pattern matching of the 1970s might be extremely different from the discriminated unions and pattern matching of the 1990s. C++ also does not have garbage collection, which complicates the issue. Rust, for instance, that also does not have garbage collection, has different binding modes for the bindings in pattern matches.
It is important to note that subtyping and inheritance are different. And even FP languages can use subtyping.
I think both Casey Muratori (and Graydon Hoare, if he has not already read it) could be interested in reading the book Types and Programming Languages, even though that book is old by now and may not contain a lot of newer advancements and theory. I also think that Casey Muratori could have benefited (in regards to this talk, at least) from learning and using Scala and its sealed traits in regards to pattern matching, if I recall correctly, Scala had as one of its objectives to attempt unify OOP and FP. I do agree that OOP can be abused, and personally I am lukewarm on inheritance, especially as direct modelling of a domain as discussed in the talk without deeper thought whether such an approach is good relative to other options and trade-offs. But subtyping, as well as objects that can be used as a kind of "mini-module", is typically more appealing than inheritance IMO. "Namespacing" of objects is also popular.
Some theory and terminology also discuss "open" and "closed" types.
And, after all, Haskell has type classes, which is not OOP, but is relevant for ad-hoc polymorphism (is Casey Muratori familiar with type classes or ad-hoc polymorphism?), Rust has traits, not quite the same as type classes but related. Scala has various kinds of implicits in regards to that. And Rust also has "dyn" traits, not so commonly used, but are available.
https://stackoverflow.com/questions/3748592/what-are-nk-patt...
> What do they mean by "n+k patterns"? I guess it's the second line, but I don't get what might be wrong with it. Could anyone explain what is the issue there? Why aren't these n + k patterns allowed any more in Haskell 2010?
Should be "understanding".