7 ms·

The Curse of the Excluded Middle (2014)

27 points by alexzeitler 3y ago

beanjuiceII 3y ago
whats it mean
- 082349872349872 3y ago
  imperative programming is like sitting in one chair; pure functional programming like sitting in the neighbouring chair; and Meijer's thesis in TFA is that "mostly functional" programming will turn out to be like attempting to sit in the space between them. for the title, see https://en.wikipedia.org/wiki/Law_of_excluded_middle https://en.wikipedia.org/wiki/Law_of_excluded_middle (given his involvement with C#, I am willing to consider the notion that his views may well reflect having had unpleasant experiences. If Rust moves beyond the "innovator" segment, it would be a counterexample.) Edit: NB (2014) ; he may well have revisited this topic more recently?
  - beanjuiceII 3y ago
    thanks, I know erik uses kotlin often, does he think we just have to live in that middle area? is the paper just an observation ? how do you think rust solves the problem?
- mrkeen 3y ago
  In imperative programming, you write statements which change the state of the system. When you go to debug a method, you need to be able to recreate the state of the system in order see how the method misbehaves. But a function always has the same output given the same input. It doesn't matter how big the function gets or how many other functions it calls. So if f(1, "foo", 47) throws an exception on a prod server, you can run exactly that function locally and watch it throw the same exception. Now someone might come along and change f's source code so that it mutates something, or reads from something which can be mutated. And they might call f 'mostly functional'. But it no longer returns the same output for the same input. f(1, "foo", 47) may or may not equal f(1, "foo", 47), so you're back to debugging methods, not functions. A method being 'mostly-functional' is like 'int i' being 'mostly-const'.
  - beanjuiceII 3y ago
    thanks! so does erik suggest one or the other? or that we must all live in that middle? last I checked he was knee deep in kotlin which I'm assuming is in that middle area?
asplake 3y ago
> The idea of "mostly functional programming" is unfeasible. It is impossible to make imperative programming languages safer by only partially removing implicit side effects. Except that people do it all the time, and they find it safer than not doing it.
- jt2190 3y ago
  If I understand the article correctly, even if the programmer is reasoning and coding functionally in an imperative language, the compiler can not assert that the code is safe for concurrency and parallelism. (You may find you get other benefits from programming functionally.)
  - phoe-krk 3y ago
    Rust seems to have solved some of this with its borrow checking semantics that automatically prove which parts of code are automatically paralellizable without running into issues like simple data races - or am I wrong?
    - kibwen 3y ago
      The Rust compiler doesn't automatically parallelize, but all single-threaded Rust code upholds the invariants necessary to be thread-safe, so it's relatively easy (and sometimes entirely trivial) to turn a single-threaded program into a parallel program.
kupopuffs 3y ago
honestly, I've yet to see a practical application of pure functional programming that is that much better than mostly functional. it's hard for most people to follow a completely pure functional programming model, but certain concepts like anonymous functions are still very nice and practical
- Twey 3y ago
  Every ten years it's discovered that another idea PL researchers have been harping on about about for forty years is very nice and practical once people get used to it :) I remember when anonymous functions (indeed, first-class functions at all) were considered academic nonsense that just obfuscated problems. After all, who can keep track of all that complexity of functions calling functions?
  - lelanthran 3y ago
    > I remember when anonymous functions (indeed, first-class functions at all) were considered academic nonsense that just obfuscated problems. I've been programming since the mid-90s. I've used both Lisp and Haskell. I don't ever remember even crusty old C greybeards considering anonymous functions to be academic nonsense.
    - Twey 3y ago
      I've honestly had people say this to me within the last year!
- grumpyprole 3y ago
  There are many practical examples already in Haskell. Pure functional programming is not necessarily about avoiding effects, but about controlling, tracking and managing them. This enables better reasoning and more safety guarantees. For example, software transactional memory, the STM monad, allows optimistic updates to shared mutable state by safely supporting rollbacks.
stephendause 3y ago
> Imperative programs describe computations by repeatedly performing implicit effects on a shared global state. Is this necessarily true? In Rust programs, operations do not operate on a shared global state – at least not in the way I think most people would understand 'effects on a shared global state.'
- kibwen 3y ago
  The enemy is shared mutable state. Functional languages solve the problem by focusing on immutability and statelessness, whereas Rust solves the problem by letting your state be shared xor mutable.
  - shermantanktop 3y ago
    Tools that prevent the developer from expressing fundamentally invalid ideas? Great. Not so great are: - Tools that force the user to adopt a mindset that the tool designer prefers; essentially this bounds the expressive power of the tool artificially for aesthetic or other opinions. - Tools that prevent the user from even understanding the danger that the tool is guarding against. IMO developers need to know what concurrency is, what the range of various numeric types are, how signed values actually work. I know others disagree on this, but idiot-proof tooling doesn’t help people grow past a certain point.
    - qsort 3y ago
      Idiot-proof tooling helps non-idiots, whereas idiots may not by definition be helped in any way. I know the internal representation of integers and floats and I know how important that knowledge is. I reverse-engineered a gnarly bug in a codebase just last month using it. I'd still rather my programming language have 10*100 resolve to the actually correct answer rather than undefined behavior. I have written production code with pthreads, but I'd still rather use async if realistic for the task at hand. I know how to manage my own memory but I'd still rather use a GC'd language if realistic for the task at hand. I know how to write queries directly to the postgres socket, but I'd still rather use a proper client. I know how to write code in vi but I'd still rather write code in jetbrains. (...) Where does the fascination for not using proper tools come from? I'm reminded of this: https://www.youtube.com/watch?v=3I_Ds2ytz4o https://www.youtube.com/watch?v=3I_Ds2ytz4o
kibwen 3y ago
Title here should have (2014).
- alexzeitler 3y ago
  done
jackblemming 3y ago
I haven't found this to be the case at all, and have found great success in taking the good parts of OOP and functional programming.
- ngcc_hk 3y ago
  In real life it is really a mix. But talk by or to fundamentalist is a waste of time. Not that functional is bad, it is good. But pure functional …
  - ParetoOptimal 3y ago
    Pure functional in my experience is even better, scaling with the length of the projects life.
tbrownaw 3y ago
This of course explains quite clearly why Haskell has taken over all large-scale software development in the decade since it was written. Personally, I prefer to just not be careless with side-effects. And maybe add some runtime invariant checks if I do have to write something that's too easy to misuse.
carterschonwald 3y ago
Ironically: via the lens of ideas embodied by classical / full linear logic, there’s very elegant programming ideas the exactly correspond with the law of excluded middle.
- 082349872349872 3y ago
  Unfortunately: as much of programming (eg any non-degenerate evaluation) fails to be injective, the law of excluded middle fails just where one might wish most to apply it.
markisus 3y ago
> Like dieters falling for magic 10-minute-miracle exercise gadgets, developers seem ready to fall for easy solutions to the latest crises in their field. > Just like "mostly secure," "mostly pure" is wishful thinking. The slightest implicit imperative effect erases all the benefits of purity, just as a single bacterium can infect a sterile wound. Taking the analogy to its logical conclusion, the only healthy diet is a 100% strict diet allowing no impure substances. Very few people can actually live this way and it's questionable whether anyone should. The author's audience is those who wish to make safe programs. He advocates modeling all effectful computations using the type system using the framework of monads. He acknowledges that there are even more expressive frameworks like separation logic systems, but that these require too much theory to be useful to the everyday developer. So the author clearly acknowledges the tradeoff between pragmatism and safety, but it's unclear why it's better to draw the line at monads rather than separation logic. Many software developers draw the line at, "seems like it should work" and most are satisfied with the type of "mostly safe, mostly functional" assurances offered by Rust. Very few go as far as to prove their programs safe in separation logic, and indeed the cost benefit is questionable for most software systems. In my earlier career, I might have read an article like this and become some sort of a monad zealot and insist that the entire codebase has to be rewritten using monads in pure functional style. In most cases, this would be a highly questionable decision. If you are writing a game, or making a web server for a dating app, an imperative style is probably the better choice.
- ParetoOptimal 3y ago
  If we take familiarity out of the equation, why is a web server inherently better implemented in an imperative style rather than a functional one using monads?
  - markisus 3y ago
    Familiarity is part of the equation. Writing an efficient web server requires being familiar with the imperative model since the underlying specs, protocol reference implementations, and libraries are probably given in imperative style. Familiarity aside, using a monadic style introduces constraints in your code. I concede that sometimes those constraints will protect you. But for most use cases, these constraints will just produce nuisance compiler errors, forcing you to write dummy wrapper functions to coerce certain types into other types. Consider the example of a loop whose condition and body are dependent on user input and a global state variable. global max_iterations = 100 def get_messages(): iterations = 0 messages = [] while input() != 'quit' and iterations < max_iterations: messages.append(input()) iterations += 1 Writing this in monadic style requires much more finesse. The global variable must be eliminated. Then function body has to be represented as an expression of type IO[list[string]]. The loop body evidently has type (bool, int, list[string]) -> IO[(int, list[string])], and the conditional has type int -> IO[bool]. Sequencing the conditional and the body requires a recursive function and then maybe a lift operators to convince the compiler that the types work out. See https://conscientiousprogrammer.com/blog/2015/12/11/24-days-of-hackage-2015-day-11-monad-loops-avoiding-writing-recursive-functions-by-refactoring/ https://conscientiousprogrammer.com/blog/2015/12/11/24-days-...
ur-whale 3y ago
"Fundamentalist" is the correct word for this article indeed. And like other fundamentalist thinking in other areas, the real world begs to differ.
scotty79 3y ago
Why do people slip into Haskell syntax the second they task themselves with explaining monads to us, peons, once again? Use C, JS, Python, Rust, PHP. Show us you really understand the essence of them not that you can just reproduce notation like they were some magic incantation that needs to be invoked verbatim otherwise magic won't work. Why do any signs of being polyglot vanish immediately when they mention monads?
- Twey 3y ago
  A (correct) description of monads requires talking about higher-kinded types, which rules out those languages immediately, unless MyPy has come a long way since I last looked. Apart from that, frankly, I think that Haskell syntax (or just mathematical type syntax, which looks very similar) is so much cleaner when talking about higher-order functions that it's worth spending a little while explaining what `m a → (a → m b) → m b` means in the prerequisites of the article rather than have the reader have to wade through `Callable[[Kind[M, A]], Callable[[Callable[[A], Kind[M, B]]], Kind[M, B]]]` [1] for the rest of it. When you're trying to explain a novel topic, the last thing you want to force your reader to do is waste their brainpower counting brackets. [1]: https://sobolevn.me/2020/10/higher-kinded-types-in-python https://sobolevn.me/2020/10/higher-kinded-types-in-python
  - scotty79 3y ago
    > A (correct) description of monads requires talking about higher-kinded types, which rules out those languages immediately No it doesn't. The fact that those languages don't have syntax for some specific form of typing doesn't mean there is no way to express concept of a monad in those languages. https://dev.to/rgeraldporter/building-expressive-monads-in-javascript-introduction-23b https://dev.to/rgeraldporter/building-expressive-monads-in-j... It's way easier to explain something if you can express it in the language that the recipient already knows like js or English instead of introducing completely new bizzare syntax and vocabulary. If I want to know what's a variance I don't need to know all associated theorems with proofs and special notations and vocabulary. I need a formula and examples of application.
lebaux 3y ago
Sorry for dumb question, but can someone please explain to a non-programmer, why the author made the title "The Curse of the Excluded Middle"? What is so special about "middle"? What is middle in programming? I am a fairly dumb person, but I am lately super interested in 1=0 math paradox/proof and it just occurred to me, what is the middle of rational numbers? What is the middle of irrational numbers? To me, it feels like the middle of all numbers is 0, but if irrational numbers are not considered "real", it can't be 0. These 2 things are probably wildly unrelated, but I would appreciate any explanation of the linked blog post in the simplest terms. Thank you!

27 points by alexzeitler 3y ago

beanjuiceII 3y ago

whats it mean

082349872349872 3y ago
imperative programming is like sitting in one chair; pure functional programming like sitting in the neighbouring chair; and Meijer's thesis in TFA is that "mostly functional" programming will turn out to be like attempting to sit in the space between them. for the title, see https://en.wikipedia.org/wiki/Law_of_excluded_middle https://en.wikipedia.org/wiki/Law_of_excluded_middle (given his involvement with C#, I am willing to consider the notion that his views may well reflect having had unpleasant experiences. If Rust moves beyond the "innovator" segment, it would be a counterexample.) Edit: NB (2014) ; he may well have revisited this topic more recently?
- beanjuiceII 3y ago
  thanks, I know erik uses kotlin often, does he think we just have to live in that middle area? is the paper just an observation ? how do you think rust solves the problem?
mrkeen 3y ago
In imperative programming, you write statements which change the state of the system. When you go to debug a method, you need to be able to recreate the state of the system in order see how the method misbehaves. But a function always has the same output given the same input. It doesn't matter how big the function gets or how many other functions it calls. So if f(1, "foo", 47) throws an exception on a prod server, you can run exactly that function locally and watch it throw the same exception. Now someone might come along and change f's source code so that it mutates something, or reads from something which can be mutated. And they might call f 'mostly functional'. But it no longer returns the same output for the same input. f(1, "foo", 47) may or may not equal f(1, "foo", 47), so you're back to debugging methods, not functions. A method being 'mostly-functional' is like 'int i' being 'mostly-const'.
- beanjuiceII 3y ago
  thanks! so does erik suggest one or the other? or that we must all live in that middle? last I checked he was knee deep in kotlin which I'm assuming is in that middle area?

asplake 3y ago

> The idea of "mostly functional programming" is unfeasible. It is impossible to make imperative programming languages safer by only partially removing implicit side effects. Except that people do it all the time, and they find it safer than not doing it.

jt2190 3y ago
If I understand the article correctly, even if the programmer is reasoning and coding functionally in an imperative language, the compiler can not assert that the code is safe for concurrency and parallelism. (You may find you get other benefits from programming functionally.)
- phoe-krk 3y ago
  Rust seems to have solved some of this with its borrow checking semantics that automatically prove which parts of code are automatically paralellizable without running into issues like simple data races - or am I wrong?
  - kibwen 3y ago
    The Rust compiler doesn't automatically parallelize, but all single-threaded Rust code upholds the invariants necessary to be thread-safe, so it's relatively easy (and sometimes entirely trivial) to turn a single-threaded program into a parallel program.

kupopuffs 3y ago

honestly, I've yet to see a practical application of pure functional programming that is that much better than mostly functional. it's hard for most people to follow a completely pure functional programming model, but certain concepts like anonymous functions are still very nice and practical

Twey 3y ago
Every ten years it's discovered that another idea PL researchers have been harping on about about for forty years is very nice and practical once people get used to it :) I remember when anonymous functions (indeed, first-class functions at all) were considered academic nonsense that just obfuscated problems. After all, who can keep track of all that complexity of functions calling functions?
- lelanthran 3y ago
  > I remember when anonymous functions (indeed, first-class functions at all) were considered academic nonsense that just obfuscated problems. I've been programming since the mid-90s. I've used both Lisp and Haskell. I don't ever remember even crusty old C greybeards considering anonymous functions to be academic nonsense.
  - Twey 3y ago
    I've honestly had people say this to me within the last year!
grumpyprole 3y ago
There are many practical examples already in Haskell. Pure functional programming is not necessarily about avoiding effects, but about controlling, tracking and managing them. This enables better reasoning and more safety guarantees. For example, software transactional memory, the STM monad, allows optimistic updates to shared mutable state by safely supporting rollbacks.

stephendause 3y ago

> Imperative programs describe computations by repeatedly performing implicit effects on a shared global state. Is this necessarily true? In Rust programs, operations do not operate on a shared global state – at least not in the way I think most people would understand 'effects on a shared global state.'

kibwen 3y ago
The enemy is shared mutable state. Functional languages solve the problem by focusing on immutability and statelessness, whereas Rust solves the problem by letting your state be shared xor mutable.
- shermantanktop 3y ago
  Tools that prevent the developer from expressing fundamentally invalid ideas? Great. Not so great are: - Tools that force the user to adopt a mindset that the tool designer prefers; essentially this bounds the expressive power of the tool artificially for aesthetic or other opinions. - Tools that prevent the user from even understanding the danger that the tool is guarding against. IMO developers need to know what concurrency is, what the range of various numeric types are, how signed values actually work. I know others disagree on this, but idiot-proof tooling doesn’t help people grow past a certain point.
  - qsort 3y ago
    Idiot-proof tooling helps non-idiots, whereas idiots may not by definition be helped in any way. I know the internal representation of integers and floats and I know how important that knowledge is. I reverse-engineered a gnarly bug in a codebase just last month using it. I'd still rather my programming language have 10*100 resolve to the actually correct answer rather than undefined behavior. I have written production code with pthreads, but I'd still rather use async if realistic for the task at hand. I know how to manage my own memory but I'd still rather use a GC'd language if realistic for the task at hand. I know how to write queries directly to the postgres socket, but I'd still rather use a proper client. I know how to write code in vi but I'd still rather write code in jetbrains. (...) Where does the fascination for not using proper tools come from? I'm reminded of this: https://www.youtube.com/watch?v=3I_Ds2ytz4o https://www.youtube.com/watch?v=3I_Ds2ytz4o

kibwen 3y ago

Title here should have (2014).

alexzeitler 3y ago
done

jackblemming 3y ago

I haven't found this to be the case at all, and have found great success in taking the good parts of OOP and functional programming.

ngcc_hk 3y ago
In real life it is really a mix. But talk by or to fundamentalist is a waste of time. Not that functional is bad, it is good. But pure functional …
- ParetoOptimal 3y ago
  Pure functional in my experience is even better, scaling with the length of the projects life.

tbrownaw 3y ago

This of course explains quite clearly why Haskell has taken over all large-scale software development in the decade since it was written. Personally, I prefer to just not be careless with side-effects. And maybe add some runtime invariant checks if I do have to write something that's too easy to misuse.

carterschonwald 3y ago

Ironically: via the lens of ideas embodied by classical / full linear logic, there’s very elegant programming ideas the exactly correspond with the law of excluded middle.

082349872349872 3y ago
Unfortunately: as much of programming (eg any non-degenerate evaluation) fails to be injective, the law of excluded middle fails just where one might wish most to apply it.

markisus 3y ago

> Like dieters falling for magic 10-minute-miracle exercise gadgets, developers seem ready to fall for easy solutions to the latest crises in their field. > Just like "mostly secure," "mostly pure" is wishful thinking. The slightest implicit imperative effect erases all the benefits of purity, just as a single bacterium can infect a sterile wound. Taking the analogy to its logical conclusion, the only healthy diet is a 100% strict diet allowing no impure substances. Very few people can actually live this way and it's questionable whether anyone should. The author's audience is those who wish to make safe programs. He advocates modeling all effectful computations using the type system using the framework of monads. He acknowledges that there are even more expressive frameworks like separation logic systems, but that these require too much theory to be useful to the everyday developer. So the author clearly acknowledges the tradeoff between pragmatism and safety, but it's unclear why it's better to draw the line at monads rather than separation logic. Many software developers draw the line at, "seems like it should work" and most are satisfied with the type of "mostly safe, mostly functional" assurances offered by Rust. Very few go as far as to prove their programs safe in separation logic, and indeed the cost benefit is questionable for most software systems. In my earlier career, I might have read an article like this and become some sort of a monad zealot and insist that the entire codebase has to be rewritten using monads in pure functional style. In most cases, this would be a highly questionable decision. If you are writing a game, or making a web server for a dating app, an imperative style is probably the better choice.

ParetoOptimal 3y ago
If we take familiarity out of the equation, why is a web server inherently better implemented in an imperative style rather than a functional one using monads?
- markisus 3y ago
  Familiarity is part of the equation. Writing an efficient web server requires being familiar with the imperative model since the underlying specs, protocol reference implementations, and libraries are probably given in imperative style. Familiarity aside, using a monadic style introduces constraints in your code. I concede that sometimes those constraints will protect you. But for most use cases, these constraints will just produce nuisance compiler errors, forcing you to write dummy wrapper functions to coerce certain types into other types. Consider the example of a loop whose condition and body are dependent on user input and a global state variable. global max_iterations = 100 def get_messages(): iterations = 0 messages = [] while input() != 'quit' and iterations < max_iterations: messages.append(input()) iterations += 1 Writing this in monadic style requires much more finesse. The global variable must be eliminated. Then function body has to be represented as an expression of type IO[list[string]]. The loop body evidently has type (bool, int, list[string]) -> IO[(int, list[string])], and the conditional has type int -> IO[bool]. Sequencing the conditional and the body requires a recursive function and then maybe a lift operators to convince the compiler that the types work out. See https://conscientiousprogrammer.com/blog/2015/12/11/24-days-of-hackage-2015-day-11-monad-loops-avoiding-writing-recursive-functions-by-refactoring/ https://conscientiousprogrammer.com/blog/2015/12/11/24-days-...

ur-whale 3y ago

"Fundamentalist" is the correct word for this article indeed. And like other fundamentalist thinking in other areas, the real world begs to differ.

scotty79 3y ago

Why do people slip into Haskell syntax the second they task themselves with explaining monads to us, peons, once again? Use C, JS, Python, Rust, PHP. Show us you really understand the essence of them not that you can just reproduce notation like they were some magic incantation that needs to be invoked verbatim otherwise magic won't work. Why do any signs of being polyglot vanish immediately when they mention monads?

Twey 3y ago
A (correct) description of monads requires talking about higher-kinded types, which rules out those languages immediately, unless MyPy has come a long way since I last looked. Apart from that, frankly, I think that Haskell syntax (or just mathematical type syntax, which looks very similar) is so much cleaner when talking about higher-order functions that it's worth spending a little while explaining what `m a → (a → m b) → m b` means in the prerequisites of the article rather than have the reader have to wade through `Callable[[Kind[M, A]], Callable[[Callable[[A], Kind[M, B]]], Kind[M, B]]]` [1] for the rest of it. When you're trying to explain a novel topic, the last thing you want to force your reader to do is waste their brainpower counting brackets. [1]: https://sobolevn.me/2020/10/higher-kinded-types-in-python https://sobolevn.me/2020/10/higher-kinded-types-in-python
- scotty79 3y ago
  > A (correct) description of monads requires talking about higher-kinded types, which rules out those languages immediately No it doesn't. The fact that those languages don't have syntax for some specific form of typing doesn't mean there is no way to express concept of a monad in those languages. https://dev.to/rgeraldporter/building-expressive-monads-in-javascript-introduction-23b https://dev.to/rgeraldporter/building-expressive-monads-in-j... It's way easier to explain something if you can express it in the language that the recipient already knows like js or English instead of introducing completely new bizzare syntax and vocabulary. If I want to know what's a variance I don't need to know all associated theorems with proofs and special notations and vocabulary. I need a formula and examples of application.

lebaux 3y ago

Sorry for dumb question, but can someone please explain to a non-programmer, why the author made the title "The Curse of the Excluded Middle"? What is so special about "middle"? What is middle in programming? I am a fairly dumb person, but I am lately super interested in 1=0 math paradox/proof and it just occurred to me, what is the middle of rational numbers? What is the middle of irrational numbers? To me, it feels like the middle of all numbers is 0, but if irrational numbers are not considered "real", it can't be 0. These 2 things are probably wildly unrelated, but I would appreciate any explanation of the linked blog post in the simplest terms. Thank you!