3 ms·

> helps to reduce incidental complexity to some extent This extend stays untapped. You cannot even imagine how far this ability to eliminate complexity extends

by 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.
  - pjc50 10y ago
    try not to confuse a size with a complexity Before we go any further you're going to have to define complexity.
    - sklogic 10y ago
      The kind of complexity that is important for software engineering is defined by the size of the atomic modules you can get (those that cannot be broken down any further and still be practical) and number of dependencies between such modules. This complexity defines how well the labour can be split between team members - i.e., defines the development scalability. This complexity defines how easy it is to understand any individual module and to change anything. Of course we can start nitpicking, go into a definition of the Kolmogorov complexity and all that (but, remember, Chaitin defines this complexity with Lisp, btw.), and it will all be irrelevant to the problems of the software engineering.
  - dunkelheit 10y ago
    That is a brave statement to make. How about you write a Lisp program that (serving as a perfect embodiment of "code is data" philosophy) takes another Lisp program as input and determines whether it would terminate? That would be just a handful of Lisp macros, right?
    - sklogic 10y ago
      Now you're talking about an infinite complexity. It cannot be reduced no matter how hard you try. It has nothing to do with the kind of complexity that software engineering have to deal with. But, for all things practical, yes, it's just a handful of Lisp macros. Because in most cases it worth designing your DSLs as total languages, and totality proof is totally trivial, as well as a proof of an opposite.
      - dunkelheit 10y ago
        Now that's moving the goal posts. You then claim that I am nitpicking and Lisp eliminates not all complexity but only the complexity software engineers care about (not true either: even Lisp programs don't write themselves and someone still has to type in the letters). After that the conversation moves into wishy-washy domain of opinions which can be debated forever without ever reconciling them.
        sklogic 10y ago
        Pay attention to what you're answering to. It was you who moved the goal posts. > there are well known techniques for eliminating any complexity you can find in a chain of compiler transforms, Can you imagine finding a working termination proof in a compiler pipeline and finding yourself in a dire need of simplifying this complexity down to something manageable?
        dunkelheit 10y ago
        vitaly is that you?

by sklogic 10y ago

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.
- pjc50 10y ago
  try not to confuse a size with a complexity Before we go any further you're going to have to define complexity.
  - sklogic 10y ago
    The kind of complexity that is important for software engineering is defined by the size of the atomic modules you can get (those that cannot be broken down any further and still be practical) and number of dependencies between such modules. This complexity defines how well the labour can be split between team members - i.e., defines the development scalability. This complexity defines how easy it is to understand any individual module and to change anything. Of course we can start nitpicking, go into a definition of the Kolmogorov complexity and all that (but, remember, Chaitin defines this complexity with Lisp, btw.), and it will all be irrelevant to the problems of the software engineering.
- dunkelheit 10y ago
  That is a brave statement to make. How about you write a Lisp program that (serving as a perfect embodiment of "code is data" philosophy) takes another Lisp program as input and determines whether it would terminate? That would be just a handful of Lisp macros, right?
  - sklogic 10y ago
    Now you're talking about an infinite complexity. It cannot be reduced no matter how hard you try. It has nothing to do with the kind of complexity that software engineering have to deal with. But, for all things practical, yes, it's just a handful of Lisp macros. Because in most cases it worth designing your DSLs as total languages, and totality proof is totally trivial, as well as a proof of an opposite.
    - dunkelheit 10y ago
      Now that's moving the goal posts. You then claim that I am nitpicking and Lisp eliminates not all complexity but only the complexity software engineers care about (not true either: even Lisp programs don't write themselves and someone still has to type in the letters). After that the conversation moves into wishy-washy domain of opinions which can be debated forever without ever reconciling them.
      - sklogic 10y ago
        Pay attention to what you're answering to. It was you who moved the goal posts. > there are well known techniques for eliminating any complexity you can find in a chain of compiler transforms, Can you imagine finding a working termination proof in a compiler pipeline and finding yourself in a dire need of simplifying this complexity down to something manageable?
        dunkelheit 10y ago
        vitaly is that you?