5 ms·

> Complexity is not about additivity, it's about entanglement. This. And nothing reflects entanglement better than a formal semantics. English (or any other na

> 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_better_or_for_worse/cx0cp0q https://www.reddit.com/r/programming/comments/3sstis/for_bet...

deleted 11y ago
[deleted]
EdiX 11y ago
> 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.
- catnaroek 11y ago
  > 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.
  - EdiX 11y ago
    >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.
    - catnaroek 11y ago
      > 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.
      - 11y ago
- pcwalton 11y ago
  > 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).
pron 11y ago
> 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).
- catnaroek 11y ago
  > 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.
  - pron 11y ago
    > 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.
    - catnaroek 11y ago
      > I'd say SK combinator calculus. Or Church numerals. They're a PITA to use, but not because they're hard to understand.
tel 11y ago
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.
- 11y ago

deleted 11y ago

[deleted]

EdiX 11y ago

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

catnaroek 11y ago
> 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.
- EdiX 11y ago
  >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.
  - catnaroek 11y ago
    > 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.
    - 11y ago
pcwalton 11y ago
> 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).

pron 11y ago

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

catnaroek 11y ago
> 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.
- pron 11y ago
  > 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.
  - catnaroek 11y ago
    > I'd say SK combinator calculus. Or Church numerals. They're a PITA to use, but not because they're hard to understand.

tel 11y ago

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.

11y ago