3 ms·

"Syntactic sugar on the lambda calculus" is just silly, really. I wish people would stop saying this. It's like saying imperative languages are syntactic sugar

by TheBoff 15y ago

"Syntactic sugar on the lambda calculus" is just silly, really. I wish people would stop saying this. It's like saying imperative languages are syntactic sugar on Turing Machines. This is a bit of a pet peeve for me, really. It seems like an unnecessary pithy dismissal of computation theory.

lubutu 15y ago
Especially since they aren't. GHC Haskell, for example, is essentially syntactic sugar for System FC, not λ-calculus.
- DanWaterworth 15y ago
  And system FC is... a polymorphically typed λ-calculus.
  - TheBoff 15y ago
    Possibly we just a have a different idea of what a lambda calculus is: I was thinking of Church's untyped lambda calculus, which is a much weirder beast than System FC.
    - DanWaterworth 15y ago
      Even if you restrict lambda calculus to mean untyped lambda calculus, it's common practice to discard the types once type-checking has completed and continue the compilation without them.
  - deleted 15y ago
    [deleted]
DanWaterworth 15y ago
I disagree, it's not like saying "imperative languages are syntactic sugar on Turing Machines" at all. Haskell compilers generally compile in the following way: text -> tokens -> AST -> lambda calculus variant -> abstract functional machine code -> imperative IR -> machine code the AST to lambda calculus variant step is a single step. It takes the Haskell representation of the lambda calculus and outputs lambda calculus. Contrast this with an imperative compilation: text -> tokens -> AST -> imperative IR -> machine code The imperative IR may be LLVM IR. LLVM IR is almost a first order functional programming language, it is certainly not machine code for a turing machine. So imperative languages are not syntactic sugar of a turing machine, there is no desugaring step in the pipeline (except maybe when building the AST).
- lubutu 15y ago
  And what of Lisp, of which most dialects have mutable state? If a Lisp compiler would convert to genuine λ-calculus it would be as large a step as it would for C.
  - DanWaterworth 15y ago
    If you would re-read my comment, you'll find that I didn't actually say I agree that all functional languages are syntactically sweetened lambda calculus, though I certainly said Haskell was. My point was that although there are functional languages that are syntactic sugar over the lambda calculus, I don't know of any imperative languages (and in fact it would not make sense to design an imperative language) that is syntactic sugar over turing machine code. I should have made my position clearer. I do agree that compiling any non-pure functional language via lambda calculus is a fruitless endeavor.
Locke1689 15y ago
That was a joke -- calling all functional languages syntactic sugar on λ-calculus is just as ridiculous as calling everything with S-expressions lisp. Sorry, sarcasm doesn't translate well over the Internet.

by TheBoff 15y ago

lubutu 15y ago

Especially since they aren't. GHC Haskell, for example, is essentially syntactic sugar for System FC, not λ-calculus.

DanWaterworth 15y ago
And system FC is... a polymorphically typed λ-calculus.
- TheBoff 15y ago
  Possibly we just a have a different idea of what a lambda calculus is: I was thinking of Church's untyped lambda calculus, which is a much weirder beast than System FC.
  - DanWaterworth 15y ago
    Even if you restrict lambda calculus to mean untyped lambda calculus, it's common practice to discard the types once type-checking has completed and continue the compilation without them.
- deleted 15y ago
  [deleted]

DanWaterworth 15y ago

I disagree, it's not like saying "imperative languages are syntactic sugar on Turing Machines" at all. Haskell compilers generally compile in the following way: text -> tokens -> AST -> lambda calculus variant -> abstract functional machine code -> imperative IR -> machine code the AST to lambda calculus variant step is a single step. It takes the Haskell representation of the lambda calculus and outputs lambda calculus. Contrast this with an imperative compilation: text -> tokens -> AST -> imperative IR -> machine code The imperative IR may be LLVM IR. LLVM IR is almost a first order functional programming language, it is certainly not machine code for a turing machine. So imperative languages are not syntactic sugar of a turing machine, there is no desugaring step in the pipeline (except maybe when building the AST).

lubutu 15y ago
And what of Lisp, of which most dialects have mutable state? If a Lisp compiler would convert to genuine λ-calculus it would be as large a step as it would for C.
- DanWaterworth 15y ago
  If you would re-read my comment, you'll find that I didn't actually say I agree that all functional languages are syntactically sweetened lambda calculus, though I certainly said Haskell was. My point was that although there are functional languages that are syntactic sugar over the lambda calculus, I don't know of any imperative languages (and in fact it would not make sense to design an imperative language) that is syntactic sugar over turing machine code. I should have made my position clearer. I do agree that compiling any non-pure functional language via lambda calculus is a fruitless endeavor.

Locke1689 15y ago

That was a joke -- calling all functional languages syntactic sugar on λ-calculus is just as ridiculous as calling everything with S-expressions lisp. Sorry, sarcasm doesn't translate well over the Internet.