5 ms·

My theory is that because programming is mostly about fighting incidental complexity, it is very easy to believe that if there were some way of getting rid of i

My theory is that because programming is mostly about fighting incidental complexity, it is very easy to believe that if there were some way of getting rid of it, programs would write itself and programming would be reduced to sipping daiquiris on a beach. Lisp (especially compared to C) indeed helps to reduce incidental complexity to some extent. So it is easy fall into almost religious belief that Lisp is the way to pure programming bliss. Of course the promise is never fulfilled because domain complexity and even incidental complexity is here to stay.

sklogic 10y ago
> helps to reduce incidental complexity to some extent This extend stays untapped. You cannot even imagine how far this ability to eliminate complexity extends. Of course, it's not just Lisp, it's Lisp (or any other meta-language) combined with a certain design methodology. A methodology which pretty much boils down to a notion that "everything is a compiler". And, since compilers are trivial and there are well known techniques for eliminating any complexity you can find in a chain of compiler transforms, this way you can eliminate all possible complexity, no matter what your domain is. Yet, I find it amusing that only a handful of people are even aware of this ultimate methodology.
- pjc50 10y ago
  since compilers are trivial No. and there are well known techniques for eliminating any complexity you can find in a chain of compiler transforms Any complexity? Really?
  - sklogic 10y ago
    > No. Why would you say so? There is nothing simpler than compilers. They can be broken down into pieces as small as you like which are still independent and fully sequential. Most of the rewrites you'll ever need to do can be done in a total language - i.e., you don't even need Turing-completeness for most of your code. > Any complexity? Really? I have not met a kind of complexity that cannot be decomposed into trivial pieces mechanically using this technique. And I've seen a lot of very different things. P.S. And try not to confuse a size with a complexity. E.g., C++ spec is huge, and implementing a compiler for the full language is a daunting task. Long, but not complex.
    - hga 10y ago
      Well, one thing I can tell you is that I've heard that much of the woe that came from the Common Lisp standard started with the line "any sufficiently advanced compiler..." in a discussion.
      - sklogic 10y ago
        Are we talking about optimisations now? Or still about a compilation? Optimisations are a totally different story. They can bring some complexity in, but the nice part is that they're totally optional and not required for solving the problem.
        hga 10y ago
        Minimally acceptable optimizations, because if your implementation is too slow, they're not optional. The examples are legion; to go to another domain, look at one of the reasons the VLIW Itanium failed, except for some numeric code the compiler(s) couldn't schedule enough operations for those Very Long Instruction Words. (Perhaps a more primary reason was that x86 code ran too slow, denying customers an easy upgrade path that due to volume sales might have resulted in more effort being put into the VLIW compilers.)
        sklogic 10y ago
        Remember, we're not talking about high performance C compilers and all that here. We're talking about the programming paradigm where everything is a compiler. Network protocol parsing is a form of compilation, all file formats parsing is a form of compilation, reacting to the UI events is a form of a compilation, processing data in whatever ways is a form of a compilation. Yet, you can only invent any optimisations at all for a small subset of compiler transformations, so for most of the cases optimisation is just totally irrelevant. As for the minimally acceptable optimisations, they're all trivial anyway. What you'd normally expect to see in most of the IRs is: constant propagation/folding (trivial), ADCE (trivial), algebraic simplification (trivial, no matter how ugly it is in, say, instcombine pass in LLVM - they're just doing it wrong), partial evaluation (trivial), inlining (trivial), backtracking for the latter two (trivial, but rarely seen, most would resort to awfully complex heuristics instead), CSE (trivial), escape analysis (trivial). What is not trivial is the stuff you'd rarely need in the high level languages, and this paradigm is all about the high level languages indeed. Not trivial: loop fusion, polyhedral analysis, vectorisation, and, finally, everything related to the code generation: instruction selection, register allocation, instruction scheduling, VLIW packing, all that. You'll never see this stuff in any high level domain specific language - you already have a common low level backend to take care of it for you anyway.

sklogic 10y ago

> helps to reduce incidental complexity to some extent This extend stays untapped. You cannot even imagine how far this ability to eliminate complexity extends. Of course, it's not just Lisp, it's Lisp (or any other meta-language) combined with a certain design methodology. A methodology which pretty much boils down to a notion that "everything is a compiler". And, since compilers are trivial and there are well known techniques for eliminating any complexity you can find in a chain of compiler transforms, this way you can eliminate all possible complexity, no matter what your domain is. Yet, I find it amusing that only a handful of people are even aware of this ultimate methodology.

pjc50 10y ago
since compilers are trivial No. and there are well known techniques for eliminating any complexity you can find in a chain of compiler transforms Any complexity? Really?
- sklogic 10y ago
  > No. Why would you say so? There is nothing simpler than compilers. They can be broken down into pieces as small as you like which are still independent and fully sequential. Most of the rewrites you'll ever need to do can be done in a total language - i.e., you don't even need Turing-completeness for most of your code. > Any complexity? Really? I have not met a kind of complexity that cannot be decomposed into trivial pieces mechanically using this technique. And I've seen a lot of very different things. P.S. And try not to confuse a size with a complexity. E.g., C++ spec is huge, and implementing a compiler for the full language is a daunting task. Long, but not complex.
  - hga 10y ago
    Well, one thing I can tell you is that I've heard that much of the woe that came from the Common Lisp standard started with the line "any sufficiently advanced compiler..." in a discussion.
    - sklogic 10y ago
      Are we talking about optimisations now? Or still about a compilation? Optimisations are a totally different story. They can bring some complexity in, but the nice part is that they're totally optional and not required for solving the problem.
      - hga 10y ago
        Minimally acceptable optimizations, because if your implementation is too slow, they're not optional. The examples are legion; to go to another domain, look at one of the reasons the VLIW Itanium failed, except for some numeric code the compiler(s) couldn't schedule enough operations for those Very Long Instruction Words. (Perhaps a more primary reason was that x86 code ran too slow, denying customers an easy upgrade path that due to volume sales might have resulted in more effort being put into the VLIW compilers.)
        sklogic 10y ago
        Remember, we're not talking about high performance C compilers and all that here. We're talking about the programming paradigm where everything is a compiler. Network protocol parsing is a form of compilation, all file formats parsing is a form of compilation, reacting to the UI events is a form of a compilation, processing data in whatever ways is a form of a compilation. Yet, you can only invent any optimisations at all for a small subset of compiler transformations, so for most of the cases optimisation is just totally irrelevant. As for the minimally acceptable optimisations, they're all trivial anyway. What you'd normally expect to see in most of the IRs is: constant propagation/folding (trivial), ADCE (trivial), algebraic simplification (trivial, no matter how ugly it is in, say, instcombine pass in LLVM - they're just doing it wrong), partial evaluation (trivial), inlining (trivial), backtracking for the latter two (trivial, but rarely seen, most would resort to awfully complex heuristics instead), CSE (trivial), escape analysis (trivial). What is not trivial is the stuff you'd rarely need in the high level languages, and this paradigm is all about the high level languages indeed. Not trivial: loop fusion, polyhedral analysis, vectorisation, and, finally, everything related to the code generation: instruction selection, register allocation, instruction scheduling, VLIW packing, all that. You'll never see this stuff in any high level domain specific language - you already have a common low level backend to take care of it for you anyway.