4 ms·

> Functional programming with immutable values is a wrong pattern for programming languages. Many algorithms, almost all actually, are naturally expressed in im

> Functional programming with immutable values is a wrong pattern for programming languages. Many algorithms, almost all actually, are naturally expressed in imperative style with mutable arrays or variables. The optimal implementation might be imperative but that doesn't mean we need to define our code that way. SQL is a good example here.

agentultra 4y ago
> The optimal implementation might be imperative There are times when it isn't. I'm thinking of Richard Bird's functional pearl, The Smallest Free Number, where the divide-and-conquer algorithm is faster than the imperative one. From the conclusion: One of the differences between a pure functional algorithm designer and a procedural one is that the former does not assume the existence of arrays with a constant-time update operation, at least not without a certain amount of plumbing. For a pure functional programmer, an update operation takes logarithmic time in the size of the array.1 That explains why there sometimes seems to be a logarithmic gap between the best functional and procedural solutions to a problem. But sometimes, as here, the gap vanishes on a closer inspection. The ability to arrive at the divide-and-conquer algorithm is quite fascinating as it uses plain, boring old mathematics and is, for some, quite straight-forward to derive on one's own. Yet people are more convinced by imperative implementations. I'm curious why this is. Is it because we "teach" people to believe programs are executed sequentially and are therefore somehow "inherently" imperative? Or is it easier to reason about algorithms in terms of their operational semantics?
- throwaway17_17 4y ago
  I tend to believe that there is an issue of map/territory confusion in teaching ‘programming’ and in general thinking about programming. Programs are usually envisioned as being statements which are performed in a sequence one after the other. This is comparable to the nature intuition about what an algorithm is, i.e. a series of steps to achieve a result when given some input. The problem then lies in the deeper explanation. It is said that the hardware is just taking instructions and executing them one after another, and that is then mapped to the execution of programming language statements. The issue of ‘imperative’ vs ‘non-imperative’ implementations is really a question of granularity. The map between machine instructions and language constructs is so large (for most every modern machine) that while the imperative algorithm seems more reflective of the underlying architecture it is just a layer of cover up to make programmers feel better. I really think that the appearance of control over fine grained instructional behavior give people the feeling that their imperative code is truer/more-correct in relation to the machine. This feeling leads to the presumption that imperative is more efficient. As a final caveat, the ability for a non-imperative algorithm to be equivalent to its imperative alternative tends to rely on the language’s compiler (and the restrictions inherent in the non-imperative language). This is the origin of the ‘with-a-smart-enough-compiler’ argument that people sometimes level against non-imperative programming, i.e. there is not a compiler smart enough to take your high level language and produce the same machine code I do in my low level language. So I’m sum, I think it is both a teaching error (the continual re-enforcing of confusion between what a program says vs what a machine does) and a general human level confusion as to what an algorithm is at the level of silicon in 2022.
  - hnfong 4y ago
    Show me a non-imperative, in-place, efficient implementation of textbook quicksort and we'll talk.
    - agentultra 4y ago
      Here's a direct translation of a C++ implementation into Haskell with no optimization: https://koerbitz.me/posts/Efficient-Quicksort-in-Haskell.html https://koerbitz.me/posts/Efficient-Quicksort-in-Haskell.htm... Personally I think the Haskell code is a bit nicer. Mutation is inherently unsafe and you need to be more careful when performing such computations. Haskell code makes this painful to read by planting red-flag words like, "unsafe" around. In C++ mutation is the norm and so it's much easier skip past such code. No indication that these operations are unsafe. The experienced reader will scrutinize this carefully or gloss over it at their own peril. The code is terse on the subject as the syntax maximizes efficiency for this case. Here's another: https://stackoverflow.com/a/5269180 https://stackoverflow.com/a/5269180 If you absolutely need in-place mutation, it's available. It's just not the default.
      - hnfong 4y ago
        Yes, but throwaway17_17 was making a philosophical point that imperative algorithms are somehow unnecessary, an out-of-date style of teaching, or merely a compiler detail, instead of being inherent to some algorithms. But I don't think there's a "non-imperative" quicksort algorithm. There's definitely value in preferring functional, non-mutating implementations over imperative where they make sense, but I've seen too many people pretty much claim that functional style of programming is all you need, and that's pretty much a lie IMHO.
- zasdffaa 4y ago
  > Yet people are more convinced by imperative implementations I like and use functional and immutable but saying that's best is like saying a screwdriver is better. Sometimes imperative is cleaner. In a video, the creator of Scala, M. Odersky, said Scala allows mutability because sometimes it is cleaner. As an SQL guy, I remember one time a cursor solution was cleanest and best. Scala's librares have some string stuff which looks immutable but isn't, under the hood. As ever, it depends. > Or is it easier to reason about algorithms in terms of their operational semantics? Good question. I'd say people think in terms of actions not mathematical functions. I certainly do. Imagine teaching an 8-year old. And it does map so well onto the underlying reality of fundamentally mutable hardware.
  - agentultra 4y ago
    > And it does map so well onto the underlying reality of fundamentally mutable hardware. It maps well to the abstraction provided by the hardware. In reality we know that modern architectures are executing instructions out-of-order for efficiencies' sake and that data-accesses are not necessarily sequential either. And we haven't even considered multiple-core processors that are so common these days! As Bird points out in his book, when one looks close enough there are cases where the logarithmic gap between the imperative vs. functional approach disappears. And further, with register targeting and stuff it's not often true that recursive calls are less efficient than their imperative counterparts anymore... although I suppose historically this could be why, at least for small arrays, imperative programmers could assume constant-time indexing and updating. I'm not nearly as versed in functional programming as I'd like to be. I was raised on C and algorithms were always described in terms of procedures to me where the proofs took quite a bit of work to follow. However as I learn more about algorithm design in functional programming and functional data structures I can't help but notice that the proofs are much easier to follow while sometimes the solution seems quite alien and I wonder if that's because of my heritage of thinking operationally rather than by calculation. I've often been surprised to learn that many of my assumptions about the logarithmic complexity of functional algorithms are not always there!
- substation13 4y ago
  Ideally I would write my code in a declarative way and the compiler would figure it out. Second to that, the language can allow interior mutability so I can optimize.

agentultra 4y ago

> The optimal implementation might be imperative There are times when it isn't. I'm thinking of Richard Bird's functional pearl, The Smallest Free Number, where the divide-and-conquer algorithm is faster than the imperative one. From the conclusion: One of the differences between a pure functional algorithm designer and a procedural one is that the former does not assume the existence of arrays with a constant-time update operation, at least not without a certain amount of plumbing. For a pure functional programmer, an update operation takes logarithmic time in the size of the array.1 That explains why there sometimes seems to be a logarithmic gap between the best functional and procedural solutions to a problem. But sometimes, as here, the gap vanishes on a closer inspection. The ability to arrive at the divide-and-conquer algorithm is quite fascinating as it uses plain, boring old mathematics and is, for some, quite straight-forward to derive on one's own. Yet people are more convinced by imperative implementations. I'm curious why this is. Is it because we "teach" people to believe programs are executed sequentially and are therefore somehow "inherently" imperative? Or is it easier to reason about algorithms in terms of their operational semantics?

throwaway17_17 4y ago
I tend to believe that there is an issue of map/territory confusion in teaching ‘programming’ and in general thinking about programming. Programs are usually envisioned as being statements which are performed in a sequence one after the other. This is comparable to the nature intuition about what an algorithm is, i.e. a series of steps to achieve a result when given some input. The problem then lies in the deeper explanation. It is said that the hardware is just taking instructions and executing them one after another, and that is then mapped to the execution of programming language statements. The issue of ‘imperative’ vs ‘non-imperative’ implementations is really a question of granularity. The map between machine instructions and language constructs is so large (for most every modern machine) that while the imperative algorithm seems more reflective of the underlying architecture it is just a layer of cover up to make programmers feel better. I really think that the appearance of control over fine grained instructional behavior give people the feeling that their imperative code is truer/more-correct in relation to the machine. This feeling leads to the presumption that imperative is more efficient. As a final caveat, the ability for a non-imperative algorithm to be equivalent to its imperative alternative tends to rely on the language’s compiler (and the restrictions inherent in the non-imperative language). This is the origin of the ‘with-a-smart-enough-compiler’ argument that people sometimes level against non-imperative programming, i.e. there is not a compiler smart enough to take your high level language and produce the same machine code I do in my low level language. So I’m sum, I think it is both a teaching error (the continual re-enforcing of confusion between what a program says vs what a machine does) and a general human level confusion as to what an algorithm is at the level of silicon in 2022.
- hnfong 4y ago
  Show me a non-imperative, in-place, efficient implementation of textbook quicksort and we'll talk.
  - agentultra 4y ago
    Here's a direct translation of a C++ implementation into Haskell with no optimization: https://koerbitz.me/posts/Efficient-Quicksort-in-Haskell.html https://koerbitz.me/posts/Efficient-Quicksort-in-Haskell.htm... Personally I think the Haskell code is a bit nicer. Mutation is inherently unsafe and you need to be more careful when performing such computations. Haskell code makes this painful to read by planting red-flag words like, "unsafe" around. In C++ mutation is the norm and so it's much easier skip past such code. No indication that these operations are unsafe. The experienced reader will scrutinize this carefully or gloss over it at their own peril. The code is terse on the subject as the syntax maximizes efficiency for this case. Here's another: https://stackoverflow.com/a/5269180 https://stackoverflow.com/a/5269180 If you absolutely need in-place mutation, it's available. It's just not the default.
    - hnfong 4y ago
      Yes, but throwaway17_17 was making a philosophical point that imperative algorithms are somehow unnecessary, an out-of-date style of teaching, or merely a compiler detail, instead of being inherent to some algorithms. But I don't think there's a "non-imperative" quicksort algorithm. There's definitely value in preferring functional, non-mutating implementations over imperative where they make sense, but I've seen too many people pretty much claim that functional style of programming is all you need, and that's pretty much a lie IMHO.
zasdffaa 4y ago
> Yet people are more convinced by imperative implementations I like and use functional and immutable but saying that's best is like saying a screwdriver is better. Sometimes imperative is cleaner. In a video, the creator of Scala, M. Odersky, said Scala allows mutability because sometimes it is cleaner. As an SQL guy, I remember one time a cursor solution was cleanest and best. Scala's librares have some string stuff which looks immutable but isn't, under the hood. As ever, it depends. > Or is it easier to reason about algorithms in terms of their operational semantics? Good question. I'd say people think in terms of actions not mathematical functions. I certainly do. Imagine teaching an 8-year old. And it does map so well onto the underlying reality of fundamentally mutable hardware.
- agentultra 4y ago
  > And it does map so well onto the underlying reality of fundamentally mutable hardware. It maps well to the abstraction provided by the hardware. In reality we know that modern architectures are executing instructions out-of-order for efficiencies' sake and that data-accesses are not necessarily sequential either. And we haven't even considered multiple-core processors that are so common these days! As Bird points out in his book, when one looks close enough there are cases where the logarithmic gap between the imperative vs. functional approach disappears. And further, with register targeting and stuff it's not often true that recursive calls are less efficient than their imperative counterparts anymore... although I suppose historically this could be why, at least for small arrays, imperative programmers could assume constant-time indexing and updating. I'm not nearly as versed in functional programming as I'd like to be. I was raised on C and algorithms were always described in terms of procedures to me where the proofs took quite a bit of work to follow. However as I learn more about algorithm design in functional programming and functional data structures I can't help but notice that the proofs are much easier to follow while sometimes the solution seems quite alien and I wonder if that's because of my heritage of thinking operationally rather than by calculation. I've often been surprised to learn that many of my assumptions about the logarithmic complexity of functional algorithms are not always there!
substation13 4y ago
Ideally I would write my code in a declarative way and the compiler would figure it out. Second to that, the language can allow interior mutability so I can optimize.