3 ms·

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 en

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.

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.