Rob Pike: Simplicity Is Complicated [video]
thedotpost.com
thedotpost.com
In Java, serialization and generics interact with practically everything.
In C++, RAII interacts with exceptions, which is the point but isn't exactly pleasant.
Haskell programmers famously point this out with the observation that a generic fmap is safer than one that has knowledge of the concrete types it uses. The type signature of fmap is this:
fmap :: Functor f => (a -> b) -> f a -> f b
In practice, what this means is that you can be assured that your fmap implementation can only apply the passed function over the value(s) wrapped in the functor, because of the fact that it cannot have visibility into what types it will operate on.
In golang, because of a lack of generics, you can write a well-typed fmap function, but it will inherently be coupled with the type of the slice it maps over. It also means the author of such a function has knowledge of all the properties involved in the argument and return type of the function passed, which means the writer of an fmap can do all kinds of things with that data that you have no assurances over.
With either GADTs or type families, this nice property is lost.
With respect to type families, I'm probably being a little bit unfair. Personally, I don't have much against associated type families. (Although I think Rust handles them much more gracefully than GHC.) But very important libraries in the GHC ecosystem like vector and lens make extensive use of free-floating type families, which I find... ugh... I don't want to get angry.
No, they're not -- not in the same sense, at least. A GADT/TypeFamily is going to be visible in the API. None of the things you mentioned are visible in the API.
There's a HUGE difference.
Only works if you're never going to make abstract types. Which I guess is technically true in Haskell - the most you can do is hide the constructors of a concrete type. But the ability to make abstract types is very useful.
Don't get me wrong, I love Haskell. It's precisely because I love Haskell that I hate it when they add features that make it as hard to reason about as C++. (Yes, there I said it - type families are morally C++ template specialization.)
Am I missing some way to "abuse" GADTs/TFs to violate the abstraction boundary or something like that? (I seriously can't see what you think the problem is here. I mean, you can equally well abuse unsafeCoerce/unsafePerformIO to do all kinds of weird things to violate parametricity, so I don't see why GADTs/TFs should be singled out.)
Note 1: And there are higher-kinded analogues, but I hope you get the idea from this.
Note 2: There are also exceptions, like `IORef` and friends.
I can pass data from one part of the program to another without coordinating both parts to respect the same memory management convention, and without having to pass that information from one place to another. This makes it easier to compose software, and in particular to reuse software like libraries (that frequently end up as layers between one component and another). For a concrete example, in a Java program I can simply publish an event into a Guava EventBus [1] without worrying where it will end up at the time I write that code. There's no real risk that I'll end up with a memory leak. I can connect two things together that weren't designed to be used together, and I can do it while inserting intermediate layers that transform, copy, record, measure, that data.
Garbage collection significantly reduces the amount of coordination necessary between unrelated parts of the code base, thereby improving code reuse. This is what I would claim is less commonly recognized win, beyond the more commonly recognized wins from eliminating classes of obvious mistakes. EventBus is just one random example that involves plugging things together - the same effect is present all over Java libraries, from logging frameworks to collections to concurrent data structures.
The ability to write interesting programs in a language comes from the interaction between its features. The real problem is features that interact in unpleasant ways, which almost always results from a lack of foresight on the language designer's part.
> In C++, RAII interacts with exceptions, which is the point but isn't exactly pleasant.
The interaction between control effects (of which exceptions are a particular case) and substructural types (of which C++'s RAII is a very broken particular case) is certainly nontrivial [0], but this doesn't mean we should give up on either feature. Control effects make it easier to design and implement extensible programs. Substructural types allow you to safely manipulate ephemeral resources, such as file handles, database connections or GUI objects.
[0] http://users.eecs.northwestern.edu/~jesse/pubs/substructural...
Sometimes I wonder about giving up.
A nitpick, but what constitutes an effect is rather arbitrary. An effect in the PFP sense is not an operational definition (other than IO) but a linguistic one. This is why I think that handling errors well, handling mutation well and handling IO well are three completely different problems that are only accidentally bundled into one by PFP for no cognitive/empirical reason other than that the lambda calculus happens to be equally challenged by all three.
There is a fourth effect, which is just as operational as IO (and thus a "truer" effect than errors or mutation) and is often the most interesting, yet it happens to be the one that baffles PFP/LC most: the passage of time. This is why there are usually two ways to sleep in PFP languages, one considered an effect, and the other is not (but happens to be much more operationally disruptive, and thus a stronger "effect").
Of course, substructural types are also a language concept (that does indeed interact badly with non-local jumps), which is why I said it was a nitpick about the use of the word "effect".
What exactly makes it arbitrary? It's pretty sensible, even if you don't have substructural types.
> Of course, substructural types are also a language concept (that does indeed interact badly with non-local jumps)
Control effects and substructural types don't interact “badly”. They just require care if you want them together. If you desugar control effects into delimited continuations (that is, normal higher-order functions), it becomes clear as daylight how to correctly handle their interaction with substructural types.
The word effect in the PFP world denotes anything that a language-level function does which may affect other functions and is not an argument or a return parameter. That definition is not valid outside of PFP/LC, because it defines as effects as things that are indistinguishable from non-effects in other models of computation. E.g. it calls assignments to certain memory cells "effects" while assignments to other memory cells non-effects.
Again, my (very minor) point is that the word "effect" as you use it simply denotes a PFP linguistic concept rather than an essential computational thing. The only reason I mention it is that the word "effect" has a connotation of something that's real and measurable beyond the language. That's true for IO and time (computational complexity, which, interestingly, is not generally considered an effect in PFP), but not true for jumps (or continuations) and mutation.
> delimited continuations (that is, normal higher-order functions)
Again, you are assuming PFP nomenclature. Delimited continuations do not require language-level functions at all, and higher-order functions can be defined in terms of delimited continuations just as the opposite is true. Delimited continuations are no more higher-order functions than higher-order functions (or monads, rather) are delimited continuations. PFP is not the only way to look at abstractions and not the only fundamental nomenclature.
This is absolutely just a choice. It all ends up depending upon how you define equality of arrows. You could probably even get weirder notions of purity if you relax equality to a higher-dimensional one.
So, it's of course arbitrary in the sense that you can just pick whatever semantics you like and then ask whether or not purity makes much sense there. You point out that "passage of time" is an impurity often ignored and this is, of course, true since we're talking (implicitly) about "Haskell purity" which is built off something like an arm-wavey Bi-CCC value semantics.
A much more foundational difference of opinion about purity arises from whether or not you allow termination.
I'd be interested to see a semantics where setting mutable stores is sufficiently ignored by the choice of equality as to be considered a non-effect. I'm not sure what it would look like, though.
Termination or non-termination? One of the (many) things that annoy me about PFP is the special treatment of non-termination, which is nothing more than unbounded complexity. In particular, I once read a paper by D.A. Turner about Total Functional Programming that neglected to mention that every program ever created in the universe could be turned into a total function by adding 2^64 (or a high enough counter) to every recursive loop without changing an iota of its semantics, therefore termination cannot offer a shred of added valuable information about program behavior. Defining non-termination as an effect -- as in F* or Koka (is that a Microsoft thing?) -- but an hour's-computation as pure is just baffling to me.
> I'd be interested to see a semantics where setting mutable stores is sufficiently ignored by the choice of equality as to be considered a non-effect. I'm not sure what it would look like, though.
I think both transactions and monotonic data (CRDTs), where mutations are idempotent, are a step in that direction.
And of course that's true! Trivially so, though, in that we could do the same by picking the counter to be 10 instead of 2^1000, since we don't appear to care about changing the meaning of the program.
If we do, then we have to consider whether we want our equality to distinguish terminating and non-terminating programs. If it does distinguish, then non-terminating ones are impure.
Now, what I think you're really asking for is a blurry edge where we consider equality module "reasonable finite observation" in which something different might arise.
But in this case you need partial information so we're headed right at CRDTs, propagators, LVars, and all that jazz. I'm not for a single second going to state that there aren't interesting semanticses out there.
Although I will say that CRDTs have really nice value semantics with partial information. I think it's a lot nicer than the operational/combining model.
But this is what bugs me. As someone working on algorithms (and does not care as much about semantics and abstractions), the algorithm's correctness is only slightly more important than its complexity. While there are (pragmatic) reasons to care about proving partial correctness more than total correctness (or prioritizing safety over liveness in algorithmists' terms), it seems funny to me to almost completely sweep complexity -- the mother of all effects, and the one at the very core of computation -- under the rug. Speaking about total functions does us no favors: there is zero difference between a program that never terminates, and one that terminates one nanosecond "after" the end of the physical universe. Semantic proof of termination, then, cannot give us any more useful information than no such proof. Just restricting our computational model from TM to total-FP doesn't restrict it in any useful way at all! Moreover, in practical terms, there is also almost no difference (for nearly all programs) between a program that never terminates and one that terminates after a year.
Again, I fully understand that there are pragmatic reasons to do that (concentrate on safety rather than liveness), but pretending that there is a theoretical justification to ignore complexity -- possibly the most important concept in computation -- in the name of "mathematics" (rather than pragmatism) just boggles my mind. The entire notion of purity is the leakiest of all abstractions (hyperbole; there are other abstractions just as leaky or possibly leakier). But we've swayed waaaay off course of this discussion (entirely my fault), and I'm just venting :)
Or, to unpack that last statement, simulate the machine instructions.
I'm never one to argue that a single semantic model should rule them all. Things are wonderful then multiple semantic models can be used in tandem.
But while I'd like to argue for the value of cost models, at this point I'd like to also fight for the value-based ones.
Totality is important not because it has a practical effect. I vehemently agree with how you are arguing here to that end.
It's instead important because in formal systems which ignore it you completely lose the notion of time. Inclusion of non-termination and handling for it admits that there is at least one way which we are absolutely unjustified in ignoring the passage of time: if we accidentally write something that literally will never finish.
It is absolutely a shallow way of viewing things. You're absolutely right to say that practical termination is more important that black-and-white non-termination.
But that's why it's brought up. It's a criticism of certain value-based models: you guys can't even talk about termination!
And then it's also brought up because the naive way of adding it to a theorem prover makes your logic degenerate.
Well, I'd argue that disallowing non-termination in your logic doesn't help in the least[1], so you may as well allow it. :) But we already discussed in the past (I think) the equivalence classes of value-based models, and I think we're in general agreement (more or less).
[1]: There are still infinitely many different ways to satisfy the type a -> a (loop once and return x, loop twice, etc. all of them total functions), and allowing (and equating) all of them loses the notion of time just as completely as disallowing just one of them, their limit (I see no justification for assuming a "discontinuity" at the limit).
[1]: The relationship between classical math and computation is in some ways like that of math and physics, except that physics requires empirical corroboration, while computation is a kind of a new "physical" math that incorporates time. In either case the result can be the same: the math could be sound but useless. In physics it may contradict observation; in computation it can allow unbounded (even if not infinite) complexity.
By yours are you referring to `forall a . a -> a`? I don't see how that principle is troubling at all.
Now back to my issue. Suppose that somewhere along the way you rely not on a non-terminating function but on a high-complexity function (e.g. a function that factors integers). You may then believe you've constructed a program, but your program is not only just as useless as the non-terminating one, but useless in the same way. A program that takes 10000 years is much more equivalent to a non-terminating program than to one that completes in one second. Your types are still populated with "false" elements, and so your logic, while now useful for proving mathematical theorems, may still prove "false" programs, in the sense of useless programs.
HOWEVER, what I said has a practical flaw, which still keeps excluding non-termination but allowing high-complexity useful. And that is that it's much easier for human beings to accidentally create programs with infinite complexity, rather than accidentally create programs with a finite, but large complexity. I don't know if we have an answer as to why exactly that is so. It seems that there are many cases of "favored" complexity classes, and why that is so is an open problem. Scott Aaronson lists the following as an open question[1]:
The polynomial/exponential distinction is open to obvious objections: an algorithm that took 1.00000001^n steps would be much faster in practice than an algorithm that took n^10000 steps! But empirically, polynomial-time turned out to correspond to “efficient in practice,” and exponential-time to “inefficient in practice,” so often that complexity theorists became comfortable making the identification... How can we explain the empirical facts on which complexity theory relies: for example, that we rarely see n^10000 or 1.0000001^n algorithms, or that the computational problems humans care about tend to organize themselves into a relatively-small number of equivalence classes?
Nevertheless, it is important to notice that what makes non-termination-exclusion useful in practice is an empirical rather than a mathematical property (at least as far as we know). Which is my main (and constant) point that computation and software are not quite mathematical, but in many ways resemble physics, and so relying on empirical (even cognitive) evidence can be just as useful than relying on math. The two should work in tandem. It is impossible to reason about computation (more precisely, software), with math alone; there are just too many empirical phenomena in computation (and software in particular) for that to make sense. I feel (and that may be a very biased, wrong observation) that the software verification people do just that, while the PLT people (and by that I don't mean someone like Mattias Felleisen, but mostly PFP and type theory people) do not.
How can that look in practice? Well, observing (empirically) that the complexity spectrum is only sparsely populated with programs humans write (and that's true not only for instruction counts but also of IO operations, cache-misses etc.), perhaps we can create an inferrable type system that keeps track of complexity? I know that integer systems with addition only are inferrable, but I'm not sure about multiplication (I don't think so, and I know division certainly isn't). Perhaps we can have a "complexity arithmetics" that is inferrable, and allows "useful rough multiplication" even if not exact multiplication? A Google search came up with some work in that direction: http://cristal.inria.fr/~fpottier/slides/fpottier-2010-05-en... (I only skimmed it).
As an example, consider the humble cons list type constructor. Looks like the free monoid, right? Well, wrong. The free monoid is a type constructor of finite sequences, and Haskell lists are potentially infinite. But even if we consider only finite lists, as in Standard ML or Scheme, the problem remains that, while list concatenation is associative, it's much less efficient when used left-associatively than when used right-associatively. The entire point to identifying a monoid structure is that it gives you the freedom to reassociate the binary operation however you want. If using this “freedom” will utterly destroy your program's performance, then you probably won't want to use this freedom much - or at least I know I wouldn't. So, personally, I wouldn't provide a Monoid instance for cons lists. Instead, I would provide a Monoid instance for catenable lists. [0]
By the way, this observation was made by Stepanov long ago: “That is the fundamental point: algorithms are defined on algebraic structures.” [1] This is the part Haskellers acknowledge. Stepanov then continues: “It took me another couple of years to realize that you have to extend the notion of structure by adding complexity requirements to regular axioms.” [1]
Of course, none of this justifies pron's suspicion of linguistic models of computation.
[0] http://www.westpoint.edu/eecs/SiteAssets/SitePages/Faculty%2...
Of course. :)
But my view stems from the following belief that finally brings us back to your original point and my original response: there can be no (classical) mathematical justification to what you call linguistic models of computation because computation is not (classical) math, as it does not preserve equality under substitution. The implication I draw from this is not quite the one you may attribute to me such as an overall suspicion, complete rejection or dismissal of those models, but the recognition that their entire justification is not mathematical but pragmatic, and that means that the very same (practical) reasons that might make us adopt the (leaky) abstraction of those models, might lead us to adopt (or even prefer) other models that are justified by pragmatism alone -- such as empirical results showing a certain "affinity" to human cognition -- even if they don't try to abstract computation as classical math.
Of course, computation is more foundational. It's mathematics that's just applied computation.
> as it does not preserve equality under substitution
You just need to stop using broken models.
> but the recognition that their entire justification is not mathematical but pragmatic
I don't see a distinction. To me, nothing is more pragmatic to use than a reliable mathematical model.
> the (leaky) abstraction of those models
Other than the finiteness of real computers, what else is leaky? Mind you, abstracting over the finiteness of the computer is an idea that even... uh... “less mathematically gifted” languages (such as Java) acknowledge as good.
> such as empirical results showing a certain "affinity" to human cognition
Experience shows that humans are incapable of understanding computation at all. But computation is here to stay, so the best we can do is rise to the challenge. Denying the nature of computation is denying reality itself.
No computation preserves equality under substitution. If your model assumes that equality, it is a useful, but leaky abstraction.
> Other than the finiteness of real computers, what else is leaky?
The assumption of equality between 2 + 2 and 4, which is true in classical math but false in computation (if 2+2 were equal to 4, then there would be no such thing as computation, whose entire work is to get from 2 + 2 to 4; also, getting from 2+2 to 4 does not imply the ability to get from 4 to 2+2).
> Experience shows that humans are incapable of understanding computation at all.
Experience shows that humans are capable of creating very impressive software (the most impressive exemplars are almost all in C, Java etc., BTW).
Using Lisp syntax, you are wrongly conflating `(+ 2 2)`, which is equal to `4`, with `(quote (+ 2 2))`, which is obviously different from `(quote 4)`. Obviously, a term rewriting approach to computation involves replacing syntax objects with syntactically different ones, but in a pure language, they will semantically denote the same value.
Incidentally:
0. This conflation between object and meta language rôles is an eternal source of confusion and pain in Lisp.
1. Types help clarify the distinction. `(+ 2 2)` has type `integer`, but `(quote (+ 2 2))` has type `abstract-syntax-tree`.
> very impressive software
For its lack of conceptual clarity. And for its bugs. I'm reduced to being a very conservative user of software. I wouldn't dare try any program's most advanced options, for fear of having to deal with complex functionality implemented wrong.
It is not equal to 4; it computes to 4. Substituting (+ 2 2) for 4 everywhere yields a different computation with a different complexity.
> but in a pure language, they will semantically denote the same value.
The same value means equal in classical math; not in computation. Otherwise (sort '(4 2 3 1)) would be the same as '(1 2 3 4), and if so, what does computation do? We wouldn't need a computer if that were so, and we certainly wouldn't need to power it with so much energy or need to wait long for it to solve the traveling salesman problem.
> For its lack of conceptual clarity. And for its bugs.
That's a very glass-half-empty view. I for one think that IBM's Watson and self-driving cars are quite the achievements. But even beyond algorithmic achievements and looking at systems, software systems that are successfully (and continuously) maintained for at least a decade or two are quite common. I spent about a decade of my career working on defense software, and that just was what we did.
Since I don't wish to discuss this topic further with rude people, but I do wish to explain my point to other readers, I'll note that the entire concept of computational complexity, which is probably the most important concept in all of computer science (and is at the very core of computation itself -- there can be no computation without computational complexity), is predicated on the axiom that in computation 2+2 does not equal 4 (in the sense that they are "the same"), but is computed to be 4. If 2+2 were actually 4, there would be no computational complexity (and so no computation).
As a matter of fact, an entire model, or definition of computation (another is the Turing Machine) called lambda calculus is entirely based on the concept that substitution is not equality in the theory of computation, by defining computation to be the process of substitution (which is what lambda calculus calls reductions). If 4 and 2+2 were the same (as they are in classical math), there would be no process, and the lambda calculus would not have been a model of computation but simply a bunch of trivial (classical) mathematical formulas.
Indeed, some people confuse the LC notation with classical mathematical notation (which it resembles), and mistakenly believe that 2+2 equals 4 in LC in the same sense that it does in math (I assume because the same reductions preserve equality in math). This is wrong (in LC reductions do not preserve "sameness" but induce -- or rather, are -- computation). To their defense, LC does make this fundamental distinction easy to miss in hiding 100% of what it is meant to define -- namely, computation -- in operations that classical mathematicians associate with equality[1], and in itself does not have a useful formulation of complexity[2]. Nevertheless, those people might ignore computational complexity, which is the same as ignoring computation itself, and while they may turn out to be great mathematicians, you would not want them specifying or writing your traffic signal or air-traffic control software.
[1]: Although I believe most notations take care to not separate consecutive reductions with the equal sign but with an arrow or a new line, precisely to signify that reduction is not equality. Also, unlike in math, LC reductions are directional, and some substitutions can't be reversed. In this way, LC does directly represent one property of time: it's directionality.
[2]: The challenge complexity poses to LC is great, and only in 2014 was it proven that it is not just a model of computation but one of a "reasonable machine": http://arxiv.org/abs/1405.3311
This is a big hairy problem in untyped LC, though, since untyped LC has non-termination and therefore is not confluent. This is what I mean by taking non-termination seriously is one way to force "time" and "computation" back into models. It means that LC has no beta-equivalence the same way that, say, simply typed LC does.
So anyway, you're wrong to say that LC has no notion of complexity—people count reduction steps all the time—but right to say that often this is intentionally ignored to provide simpler value semantics. It's foolish to think of this as equivalent to LC, though.
This paper is interesting. I think what they prove was at least folk belief for a long time, but I've never seen a proof.
I didn't say that it has no notion of complexity; I said it "does not have a useful formulation of complexity", as reduction step count are not very useful in measuring algorithmic complexity, at least not the measures of complexity most algorithms are concerned with.
> It's foolish to think of this as equivalent to LC, though.
Oh, I don't think that at all, which is why I specifically said that some people make the mistake of confusing LC reductions with classical substitutions (equality). They may then think that computation can be equational (false), rather than say it may sometimes be useful to think of computation in equational terms, but that's an abstraction -- namely, a useful lie -- that has a cost, i.e. it is "leaky" (true).
This. And nothing reflects entanglement better than a formal semantics. English (or any other natural language) always lets you sweep it under the rug. The only objective measure of simplicity is the size of a formal semantics.
I expand on this here: https://www.reddit.com/r/programming/comments/3sstis/for_bet...
A formal semantics is just a way to translate from one formalism to another.
It's rather obvious that choosing the target formalism determines how simple the language will appear, when you talk about "formal semantics" you should specify "which one": operational? denotational? axiomatic?
Stricly speaking a compiler or an interpreter represents a formal semantics for a language: operational semanthics rules are often very very similar to the code of an AST interpreter, for example.
One could interpreter your statement to mean that the smaller the compiler the simpler the language, which means that assembly language was the simplest language all along!
For example, in your reddit post you claim that := is problematic, and indeed its semantics is tricky and often trips beginners (and even experienced!) programmers. However := semantics is not actually that complicated "define every variable that isn't defined inside the current scope, otherwise assign them" and the errors stem from the fact that people assume that the scope lookup for := is recursive, which would arguably result in a more complicated formal semantics.
Of course, we need to reach a gentleman's agreement regarding which formalism is a good “foundation” for defining everything else. My personal preference would be to define all other formal systems in terms of rules of inference.
> It's rather obvious that choosing the target formalism determines how simple the language will appear, when you talk about "formal semantics" you should specify "which one": operational? denotational? axiomatic?
I am fine with any, as long as the same choice is made for all languages being compared. What ultimately interests me is proving a type safety theorem, that is, a precise sense in which “well typed programs don't go wrong”, so perhaps this makes a structural operational semantics more appropriate than the other choices.
> Stricly speaking a compiler or an interpreter represents a formal semantics for a language: operational semanthics rules are often very very similar to the code of an AST interpreter, for example.
> One could interpreter your statement to mean that the smaller the compiler the simpler the language, which means that assembly language was the simplest language all along!
Sure, but the target languages used by most compilers are often themselves very complex. Which means a realistic compiler or interpreter most likely won't be a good benchmark for semantic simplicity.
If you are interested in defining "low cognitive load" that's a poor choice, in my opinion.
>I am fine with any, as long as the same choice is made for all languages being compared. What ultimately interests me is proving a type safety theorem, that is, a precise sense in which “well typed programs don't go wrong”, so perhaps this makes a structural operational semantics more appropriate than the other choices.
I'm not aware of any such thing, the kinds of formal semantics that academics prefer deal very poorly with the realities of finite execution speed and memory, the kinds that pratictioners use (which usually isn't referred to as "formal semantics" but rather "what does this compile to") deal very poorly output correctness.
However this has little to do with cognitive load, even if such formal semantics existed it doesn't necessarily mean it would be easy for a human mind.
> Sure, but the target languages used by most compilers are often themselves very complex. Which means a realistic compiler or interpreter most likely won't be a good benchmark for semantic simplicity.
If you agree that formal semantics is just a translation from one formalism to another, you can't claim that a formalism A is semantically more complex than formalism B without picking a formalism C as a reference point.
I'm interested in “low cognitive load without sacrificing technical precision.” It's a much harder goal to achieve than “low cognitive load if we hand-wave the tricky details.”
> However this has little to do with cognitive load, even if such formal semantics existed it doesn't necessarily mean it would be easy for a human mind.
Which is exactly my point. I only consider a language simple if its formal description is simple.
> If you agree that formal semantics is just a translation from one formalism to another, you can't claim that a formalism A is semantically more complex than formalism B without picking a formalism C as a reference point.
No disagreement here. I even stated my personal choice of C.
You don't seem to be interested in low cognitive load at all, otherwise:
> No disagreement here. I even stated my personal choice of C.
you would have attempted to motivated your choice of reference point in terms of cognitive load. Even if induction mathematics was the way the human mind worked (which it isn't) it's very different from CPUs and there is a cognitive load (and semantical distance) in going from mathematics to CPUs.
Even if it isn't how the human mind works, it's how computing itself works. Would you take seriously a physicist who denies gravity? I wouldn't take seriously a computer scientist who denies structural induction.
but it's not the whole story when it comes to computers.
Clearer examples of unnecessary complexity in Go would be the function-scoped nature of "defer" (implicit mutable state is much more complicated than block scoping) and the inconsistent behavior of "nil" with the built-in collections (reading from a nil map returns zero values, but reading from a nil slice panics).
If we accept that, then simplicity alone is not a desirable goal. Something may well be formally simple but at the same time incompatible with human cognition. Indeed, that may not be objective, but since when do we value things only by objective measures? That the only objective measure of simplicity may be the size of formal semantics does not mean that it is the most useful measure of simplicity (if we wish to view simplicity as possessing a positive value that implies ease of understanding).
Agreed. Otherwise, Forth and Scheme would've taken over the world.
> Something may well be formally simple but at the same time incompatible with human cognition.
Do you have a concrete example?
> (if we wish to view simplicity as possessing a positive value that implies ease of understanding).
I don't particularly fetishize simplicity. What I want is the least effort path to writing correct programs. The following features help:
0. Simplicity - smaller formal systems have less room for nasty surprises.
1. Using the right tool for resource management - sometimes it's a garbage collector, sometimes it's substructural types.
2. Typeful programming - it's an invaluable tool for navigating the logical structure of the problem domain.
Off the top of my head, and since we're talking about computation, I'd say SK combinator calculus. Or Church numerals.
> Typeful programming
It is, but it can also be a hindrance. Finding the sweet spot is a matter for empirical study.
They're a PITA to use, but not because they're hard to understand.
(I recognize that this doesn't invalidate the point you are trying to make in the parent post. They aren't incompatible with human understanding. They're incompatible with writing programs in a reasonable amount of time, though.)
> Do you have a concrete example?
Brainfuck?
Or maybe simplicity in terms of the formal semantics is a desirable goal, but not the simplicity of the language alone.
At the end of the day, what determines mental load is the complexity of solving a particular problem using a particular language.
I don't think this simplicity follows from the simplicity of the language itself. There may not even be the slightest correlation.
(This is in general. The big way around this is to pick a language that is well-suited for your particular problem.)
Designing a simple implementation of something means that it is as close to the essence of what you've designed it for, and by doing so you've made it more universal, and therefore more flexible/adaptable.
> If all the formal semantic models for a language are unwieldy then you've probably got a non-simple language.
Now, "simplicity" is a mental construct, a language UX construct. To handle this, I think of "unwieldy" as a bit of a technical term. What does it mean to be unwieldy? It means that there is significant non-ignorable complexity.
Significant here must be defined almost probabilistically, too. If there is significant complexity which is ignorable across 99/100 real-world uses of a language then it really should win some significant points.
Ignorable complexity is also an important concept. It asks you to take empirical complexity measures (you mention Kolmogorov complexity; sure why not?) and temper them against the risk of using a significantly simpler "stand-in" semantic model. I accept that the stand-in model will fail to capture what we care about sometimes, but if it does so with an acceptable risk profile then I, pretty much definitionally, don't care.
Now that I've weakened your idea so much, it's clear how to slip in justifications for really terrible languages. Imagine one with a heinous semantics but a "tolerable" companion model which works "most of the time".
From this the obvious counterpoint is that "most of the time" isn't good enough for (a) large projects (b) tricky problems and (c) long support timelines. Small probabilities grow intolerable with increased exposure.
---
But after all this, we're at an interesting place because we can now talk about real languages as being things with potentially many formally or informally compatible formal or informal semantic models. We can talk about how complexity arises when too few of these models are sufficiently simple. We can also talk about whether or not any of these models are human-inelligible and measure their complexity against that metric instead of something more alien like raw Kolgomorov complexity.
So here's what I'd like to say:
> Languages which hide intolerable complexity in their semantics behind surface simplicity are probably bad long-term investments.
and
> Languages which have many "workably compatible" semantic models, each of which being human-intelligible, are vastly easier to use since you can pick and choose your mode of analysis with confidence.
and
> Value-centric semantic models (those ones with that nasty idea of "purity" or whatever) are really great for reasoning and scale very well.
In particular, I'm personally quite happy to reject the assertion made elsewhere that value-centric semantics are not very human intelligible. On the other hand
> Simple operational semantic models are also pretty easy to understand
I just fear that they scale less well.
My take on “simplicity” is very computational. To me, a programming language is a system of rules of inference, whose judgments are of the form “program is well-formed” (which covers syntax and type checking) and “program does this at runtime” (a reduction relation, a predicate transformer semantics, or whatever fits your language's dynamics best). Then, simplicity is just some measure of the language's size as a collection of rules of inference. Also:
0. Undecidable rules of inference (e.g., type reconstruction for a Curry-style System F-omega) are considered cheating. Undefined behavior (e.g., C and C++) is also considered cheating. Cheating is penalized by considering the entire language infinitely complex.
1. Languages (e.g., ML's module system) are allowed to be defined by elaboration into other languages (e.g., System F-omega). Elaboration into a language that cheats is considered cheating, though.
> To handle this, I think of "unwieldy" as a bit of a technical term. What does it mean to be unwieldy? It means that there is significant non-ignorable complexity.
I don't see any complexity as ignorable at all. I just see some complexity as worth the price - but you, the programmer, need to be aware that you're paying a price. For instance, the ease with which one can reason about Haskell programs (without the totally crazy GHC extensions) justifies the increased complexity w.r.t., say, Scheme.
> Significant here must be defined almost probabilistically, too. If there is significant complexity which is ignorable across 99/100 real-world uses of a language then it really should win some significant points.
This is ease of use, which is subject to statistical analysis; not simplicity, which is not.
There are frequent misunderstandings of this essay -- the argument isn't as coarse as "crappy software wins", or "release early and often".
The tradeoff is: do you want a simple interface (MIT style) or a simple implementation (NJ style)? If you want a simple interface, you have to hide a bunch of complexity underneath. If you want a simple implementation, you punt on some hard things and expose it to the user.
Despite its authorship, and marketing as a better C (which is the epitome of NJ style), Go is MIT style! The concurrency model hides a lot of stuff under the covers: sync vs async syscalls, segmented stacks, etc. And GC is probably the ultimate MIT-style feature, in that the interface is very simple (just pretend you have infinite memory), but implementations are tremendously complex -- basically each GC is unique and its own research project.
[1] https://www.jwz.org/doc/worse-is-better.html
EDIT: From paging through the slides, this seems to be basically the gist of the last half, but I don't see that he mentioned "Worse is Better" or MIT vs NJ style...
It is very easy to implement, and leaves a lot of the complexity (null pointers, generics, etc) to the user instead of solving it in the language.
This is a classic example of worse-is-better.
An MIT-style language would be Rust, which indeed struggled to get to v1.0 and Go vs. Rust plays out quite similarly to what worse-is-better would predict.
Rust can reuse nearly all C tools like kcov, gdb, perf, valgrind. On top of it, it has a solid set of its own tools. For example it has rustfmt, cargo, rustdoc (having the ability to test your Rust documentation is great).
Only thing it truly misses is a IntelliJ IDE for Rust and possibly a Rust oriented coverage system.
For Rust and Go the example I'm thinking of is rustfmt and gofmt.
That said, if you're talking about source code formatters, I'm pretty sure that clang-format predates gofmt (and surely clang-format was not the first automatic source code formatter for C++). The coup for Go was that they got the community at large to standardize upon and champion gofmt, which is not something that C++ has ever matched.
How useful the extra tooling is, I don't really know.
The extra stuff that rustfmt does stems from the fact that rustfmt wants to aesthetically format code well, matching the style that the community had settled on prior to its introduction (e.g. avoiding long lines, lining up parameters), while gofmt is fine with less aesthetically pleasing code (long lines, all parameters on one line) as long as the implementation of gofmt remains simple. There's nothing stopping anyone from implementing a bare-bones rustfmt in the style of gofmt and trying to push its style onto the community, but Nick had different goals.
I'm curious how "tooling" is easier in Go than in Rust. To my mind, dynamic tooling (instrumentation, profiling, debugging, etc.) is much easier in Rust than in Go, because Rust uses the OS facilities and looks much like native code, while Go's runtime reinvents the world.
This is in fact what we've seen—Rust didn't have to write custom profilers, custom debuggers, language-specific race detectors, and so on, because the native system tools work just fine.
(NB: I'm not saying Go made the wrong decision with a userland scheduler; I'm objecting to the idea that it's somehow simpler to do that. It's much more complex.)
Are they useful, I'm not sure. They feel useful but I have little trust in my judgment. When I switched back in the day from VS to emacs I didn't seem to miss all of the refactoring tools VS provided.
C won over Lisp, not because “worse is better”, but because the C's advantages over Lisp (performance on cheap machines) were more pronounced than the other way around (“safety” achieved by means of lots of runtime checking - by no means was it possible to statically rule out errors). Lispers fancy their language of choice the pinnacle of computer science, but the falsity of this claim becomes evident under close scrutiny.
> Go vs. Rust plays out quite similarly to what worse-is-better would predict.
I see a brighter future for Rust in the long run, for the following reasons:
First, Go doesn't do enough for the programmer: Haskell and Erlang are safer and easier to use, and have much better parallelism and concurrency stories. What kind of silly value proposition is “safer than C” or “less verbose than Java”? Rust offers something genuinely new: half-assed attempts at “better C++s” have existed for a while, but “safer C++s” haven't.
Second, Rust plays much more nicely with other languages. Rust is no more difficult than C to call from, say, Python. On the other hand, Go seems to be more of an all-or-nothing proposition: “If you want to use Go libraries, use them from applications written in Go.”
I also think Lisp is not truly "better" in the sense "worse-is-better" is ascribing. But if we suspend disbelief - then the Go vs. Rust story matches the one described in "Worse is better".
Perhaps Rust will win out in the end and "worse is better" won't prevail. Despite liking the idea of Rust very much, I don't think it will.
Seems like a "boo Go" echo chamber in here, but as someone that moved their entire backend infrastructure to Go, the offering was so compelling it was worth going against common wisdom and actually rewriting huge pieces of infrastructure code. And I'm hardly alone - many huge companies felt the same value proposition and made the same decisions.
Go isn't perfect for many things, but where it's placed itself - among often headless networking infrastructure projects and backends, it's exceedingly good at what it offers.
Edit: had repeated myself.
What did you move from?
When I tried Go, things went like this: First, I deliberately wrote a program with a data race, which the data race detector didn't detect. Then, I honestly tried to write a race-free program, and again the data race detector didn't complain. A couple of hours later, I realized that the second program also contained a data race.
Not having to implement a userland OS scheduler, a production-quality garbage collector, and an industrial-strength compiler backend from scratch strikes me as a fairly New Jersey-style approach, don't you think?
(I think this whole "Rust vs. Go" as "MIT vs. New Jersey" argument is pretty silly. There are many factors going into why Go released 1.0 before Rust did, and both communities have consensus that you shouldn't treat Rust vs. Go as a horse race anyway.)
System comprehensibility is how long it takes for me to learn the minimal set of atoms in order for me to comprehend an entire system.
Rob Pike criticizes map and reduce and other functional idioms as not machine simple. And although Rob Pike doesn't say this, I might argue on his behalf that functional code has a mild reputation for less readability.
But I would argue that functional idioms permit tasteful tradeoffs between machine simplicity and system comprehensibility. I would also argue that when a system gets to a certain largeness, I would be sometimes okay with sacrificing some readability and machine simplicity for system comprehensibility. I would also say that although I might lose some performance advantages with a functional approach, the improvement to system comprehension might mean an improved cognitive capacity for the human to optimize for distributed multi-core contexts, which might offset the losses from machine simplicity.
You don't even need to bring in parallelism for functional approaches to gain in performance. Here's an example (in Rust) of how you'd implement collecting an iterator into a vector using the "machine simple" approach:
let mut array = vec![];
for element in some_iterator {
array.push(element);
}
let array = some_iterator.collect();
In fact, it turns out that the second approach is often significantly faster, because the standard library contains the equivalent of:
let mut array = Vec::with_capacity(some_iterator.size_hint());
for element in some_iterator {
array.push(element);
}
What are the chances that you'd do this important optimization manually? Not high: it adds noise, it's esoteric, and it's easy to forget. But if you use the functional idiom, you benefit from the optimized approach every time. That is the true benefit of abstraction, which is really the key point here. "Machine simple" and "fast" are frequently in opposition, and too often people think that the former implies the latter.
Obviously, this kind of thing isn't a magic bullet, but in general I'd say the key for any kind of program is to express your intent at the highest level possible. This benefits both optimization and human readers! (That obviously means that the programming language must support such abstraction in a non-leaky way.)
[1] Which would show up prominently on a profile.
Source: I've used oprofile, and later perf, to hunt exactly this kind of performance bug.
.
Of course, fixing a pervasive issue like that is much more tedious than just finding it. :-(
I honestly have no idea what this even means.
It is also strange that he makes so many claims about readability, considering it is the most subjective attribute of a programming language there is. For example, some code that would have been completely unapproachable to me a couple of years ago is perfectly readable to me today, because I've learned new concepts.
I suspect most people disagree with you and think, for example, that the features in high level languages make it easier to program in those languages than in low level ones.
I react in horror to the features being added to CUDA and SyCL to make them closer to C++.
I still hate C++ with a passion, grepping around in gecko is much harder than servo.
Because if you didn't the programming language would never do anything at all.
It seems to me that what Pike is getting at here is how easy it is to build mental models of the code, the language, the underlying system, down through all its layers, and, yes, the code's original author and any subsequent authors.
I share your frustration at the subjectivity of readability claims. There's actually starting to be good academic research on code readability, for instance this paper:
https://www.cs.virginia.edu/~weimer/p/weimer-tse2010-readabi...
> Recent studies in the literature have shown that syntax remains a significant barrier to novice computer science students in the field. While this syntax barrier is known to exist, whether and how it varies across programming languages has not been carefully investigated. For this article, we conducted four empirical studies on programming language syntax as part of a larger analysis into the, so called, programming language wars.
http://neverworkintheory.org/2014/01/29/stefik-siebert-synta...
Obviously I can't force everything through that filter, some problems require complex solutions.
Hacker News is full of really bright people who like the expressiveness of Haskell et al. So it's not surprising that Rob's not going over well here. Just saying that us dumb people really appreciate his efforts.
Some of us use Haskell because we're also dumb people.
The part about how features should be orthogonal does seem similar to the "not entangled" (and to DRY / SRP).
The part about visible surface area -- garbage collection is "simple" because you can't explicitly talk to it -- seems to be a closer match for "easy" tho, as do the examples (smell test: anything with "and" in the name probably means there are entangled concepts).
...huh. Which means that his concept of "simple" does in fact contain multiple things entangled together, or in other words is complicated. ;-)
Instead of "simplicity" saving me time as Mr. Pike suggests, it leaves me dissatisfied with the results after wasting my time in attempts to prevent my dissatisfaction.
This probably isn't an issue for someone new to programming without the expectations experience with other languages may bring, but for a seasoned C programmer Go often feels like a regression.
IMHO, what largely makes Go useful over C is the language-level support of coroutines, and not because the simplicity of the "go" keyword or channels, but because it eliminates the need to design and integrate with snowflake event loops or the specifics of blocking/non-blocking file descriptors.
As a result, packages are written without concern for how the caller's event loop will be integrated, you just write blocking code everywhere and it can be used by every Go program with significantly less potential for impedance mismatch. The garbage collection and overall elimination of the need for allocating and freeing memory also contributes to this; no longer do you have to understand the resource life-cycle strategy of some C library you've decided to use, or if it's using the C library's allocator or its own, or if it's capable of using your allocator via some elaborate and unique initialization scheme.
Unfortunately Golang's concurrent execution model is also what makes it a pretty terrible language for system programming. Golang's inescapable and largely opaque underlying use of threads is a constant source of pain for anyone programming operating system facilities which influence only the calling thread's state, particularly state inherited by child threads.
I often encounter misuse of runtime.LockOSThread() in attempts to overcome this problem but as of now this is completely inadequate because the Go scheduler creates new OS threads on an as-needed basis from whichever currently-executing OS thread happens to be executing at the time. This leaks whatever unique state the thread may have into a newly created, unlocked OS thread, which may then go execute any goroutine - likely the very thing you were attempting to prevent in using runtime.LockOSThread().
There's plenty more to whine about, but I'll stop here.
And as far as do and while go, why would you hide part of the state determining when you're loop exits at the end of the loop just to save a few lines at the top. I am going to naturally try to read your code from top to bottom not top to bottom to top. The more you make me skip around the longer it will take me to understand what you are doing. 90% of my job is maintaining code not writing new code. Programmers who write as if that isn't the case just make the long term cost of maintaining the software they write larger.
While C++ is something extreme in term of complexity , the other extreme, Go, is problematic as well. I've yet to find a language that has a good balance between the 2. But Go certainly showed that the tooling is as important as the language itself, and it's a great part of its success.
"Philosophically" , no question, I agree with Rob Pike. On practice, things are a bit more nuanced.
I have been thinking about the same thing: that the simplest languages have a minimal set of "orthogonal" features; though it never occurred to me to describe them in those terms.
But hey, it's Rob Pike. I was bound to walk away with something after listening to him talk :)
In the case of programming languages, this is not only a development cost, it's a maintenance cost as well. But this concept seems to apply to many more things than just programming.
> The key point here is our programmers are Googlers [...] They’re not capable of understanding a brilliant language but we want to use them to build good software. So, the language that we give them has to be easy for them to understand and easy to adopt.
http://channel9.msdn.com/Events/Lang-NEXT/Lang-NEXT-2014/Fro...
Even if it were true (which I don't believe for a second), you've created a language released to the community at large. Your users are not just google engineers. If you want to encourage broader acceptance of your language, you're going to need to make a good faith attempt to listen to their requests.
Also, I'm pretty sure the "brilliant" is meant somewhat sardonically.
Any genius that is able to invert binary trees on whiteboards, count the balls on a vending machine, do a C++ compiler course, describe the random code in a magazine, ....
Can surely cope with a modern programming language.
Or at least wrong when we talk about general programming.
Go isn't a 'bad' language. Go is simple another tool for one job and it's doing his job good, cause of his simplicity.
However not every problem is so easy to solve with this simplicity. Some problems doesn't fit well with the Go approach. And I always hate it when people talk about "why x is superior because less/more features", mostly things emerge when the problem emerges.
The biggest reason that other features get added to languages to make them ubiquitous is because in MANY cases companies marry their infrastructure to a particular language. With that infrastructure commitment you end up with an investment into doing everything with that particular language so if you have a feature or methodology in another language that would be good for a particular use case, your existing investments prevent you from being able to EASILY introduce a new language just for that feature.
Microservice architecture goes a lot way toward countering those investments. Heroku actually does a great job of removing language specific infrastructure investments from your process that make it easier to introduce language-per-purpose approaches.
Wrote a bit article on it for Codeship a couple of months ago. http://blog.codeship.com/exploring-microservices-architectur...
haha, that's a good one :)