News for hackers. Stuff that matters.
Re:Rob Pike: Simplicity Is Complicated [video] by catnaroek on Thursday December 03, 2015 @01:49AM (#10668165)
> Complexity is not about additivity, it's about entanglement.

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...

Re:Rob Pike: Simplicity Is Complicated [video] by EdiX on Thursday December 03, 2015 @03:24AM (#10668512)
> nothing reflects entanglement better than a formal semantics

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.

Re:Rob Pike: Simplicity Is Complicated [video] by pcwalton on Thursday December 03, 2015 @12:18PM (#10670839)
> 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.

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).

Re:Rob Pike: Simplicity Is Complicated [video] by catnaroek on Thursday December 03, 2015 @04:15AM (#10668642)
> A formal semantics is just a way to translate from one formalism to another.

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.

Re:Rob Pike: Simplicity Is Complicated [video] by EdiX on Thursday December 03, 2015 @04:50AM (#10668751)
>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.

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.

Re:Rob Pike: Simplicity Is Complicated [video] by catnaroek on Thursday December 03, 2015 @05:10AM (#10668816)
> If you are interested in defining "low cognitive load" that's a poor choice, in my opinion.

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.

Re:Rob Pike: Simplicity Is Complicated [video] by EdiX on Thursday December 03, 2015 @05:21AM (#10668838)
> I'm interested in “low cognitive load without sacrificing technical precision.”

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.

Re:Rob Pike: Simplicity Is Complicated [video] by catnaroek on Thursday December 03, 2015 @05:40AM (#10668895)
> Even if induction mathematics was the way the human mind worked (which it isn't)

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.

Re:Rob Pike: Simplicity Is Complicated [video] by EdiX on Thursday December 03, 2015 @06:02AM (#10668958)
> it's how computing itself works

but it's not the whole story when it comes to computers.

Re:Rob Pike: Simplicity Is Complicated [video] by pron on Thursday December 03, 2015 @06:07AM (#10668978)
> The only objective measure of simplicity is the size of a formal semantics.

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).

Re:Rob Pike: Simplicity Is Complicated [video] by catnaroek on Thursday December 03, 2015 @07:28AM (#10669222)
> If we accept that, then simplicity alone is not a desirable goal.

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.

Re:Rob Pike: Simplicity Is Complicated [video] by AnimalMuppet on Thursday December 03, 2015 @01:02PM (#10671266)
> > Something may well be formally simple but at the same time incompatible with human cognition.

> Do you have a concrete example?

Brainfuck?

Re:Rob Pike: Simplicity Is Complicated [video] by pron on Thursday December 03, 2015 @07:39AM (#10669241)
> Do you have a concrete example?

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.

Re:Rob Pike: Simplicity Is Complicated [video] by catnaroek on Thursday December 03, 2015 @07:52AM (#10669281)
> I'd say SK combinator calculus. Or Church numerals.

They're a PITA to use, but not because they're hard to understand.

Re:Rob Pike: Simplicity Is Complicated [video] by AnimalMuppet on Thursday December 03, 2015 @01:00PM (#10671248)
But for writing actual programs, the complexity of using matters as much as the complexity of understanding.

(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.)

Re:Rob Pike: Simplicity Is Complicated [video] by fauigerzigerk on Thursday December 03, 2015 @09:28AM (#10669700)
>If we accept that, then simplicity alone is not a desirable goal

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.

Re:Rob Pike: Simplicity Is Complicated [video] by AnimalMuppet on Thursday December 03, 2015 @12:59PM (#10671232)
In general, the simpler the language, the more complex the code to implement the solution in that language, and so the harder it is to understand the code. But the more complex the language, the simpler (and easier to understand) the code, but the language itself is harder to understand. It's almost like you want the language to have the square root of the complexity of the problem.

(This is in general. The big way around this is to pick a language that is well-suited for your particular problem.)

Re:Rob Pike: Simplicity Is Complicated [video] by ZenoArrow on Thursday December 03, 2015 @10:36AM (#10670100)
If you want an alternative explanation for simplicity, I'd say simplicity implies flexibility.

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.

Re:Rob Pike: Simplicity Is Complicated [video] by catnaroek on Thursday December 03, 2015 @06:03PM (#10673391)
This would work if compilers were written in simple languages, and if target languages themselves were simple. In other words, in a parallel universe.
Re:Rob Pike: Simplicity Is Complicated [video] by tel on Thursday December 03, 2015 @09:13AM (#10669613)
So I sort of agree with you here, but only as a partial converse:

> 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.

Re:Rob Pike: Simplicity Is Complicated [video] by catnaroek on Thursday December 03, 2015 @02:10PM (#10671800)
> Now, "simplicity" is a mental construct, a language UX construct.

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.

Re:Rob Pike: Simplicity Is Complicated [video] by tel on Thursday December 03, 2015 @02:29PM (#10671905)
I don't want to deny that those "quantitative" measures exist. I want to cast doubt that they're the dominant mechanism for modeling how real people think when they're accomplishing a task in a formal system.