5 ms·

Defunctionalization: Everybody Does It, Nobody Talks About It

60 points by nancyhua 7y ago

mikelyons 7y ago
> defunctionalization, a transformation that replaces higher-order functions with equivalent first-order ones. For anyone else who got nothing from the title.
- deleted 7y ago
  [deleted]
- duelingjello 7y ago
  I admit to fawning for functional languages like Haskell, Clojure and OCaml for fun, but it seems like they are not more popular because having many additional, higher-order constructs makes code “obsfucated” behind clever features rather than written as simply as possible (but no simpler). Maybe for a coding shop full of insane geniuses (i.e., quants, CalTech aerospace, physicists or Stanford research department) it’s all good, but the learning curve of tight functional code is too steep in the vast majority of situations. Even if it’s good, clean and small code, functional is too often a “white elephant” because of the dearth of its practitioners. Hence the pervasiveness of C++, Java, .NET, Python and especially JS. One the fundamental UX, copy-writing, devops/sysadmin and programming axioms is: Don’t make me think e.g., reduce cognitive load by making knowledge works as easy to digest as possible using simple, familiar/conventional, intentional and clear patterns.
  - Gravityloss 7y ago
    What are the ergonomics-first languages of the functional world?
    - The_rationalist 7y ago
      I would say that rust and kotlin are good at providing most of the useful concepts from functional programming (higher order functions, common functors (map, filter, etc), tail call, pattern matching, destructuring, expressions, lazy evaluation, immutable collections, actor model, algebraic data types) Sadly they lack some features at the type system level (higher kinded types, intersection and union types) TypeScript do a better job at it but lack some other features (pattern matching).
      - pkolaczk 7y ago
        Looks like the language you wanted to mention is Scala. Pragmatic and has all the things you mentioned.
      - kod 7y ago
        Kotlin doesn't have destructuring pattern matching.
    - twic 7y ago
      LISPers would say LISP.
    - kazinator 7y ago
      TXR Lisp, for one.
  - The_rationalist 7y ago
    Clearly, but a subset of functional features help to reduce cognitive load. And this subset is what modern languages target (see my comment below).
  - whateveracct 7y ago
    This genius talk is so wrong. I have an bachelors in engineering from a state school. I've worked in Haskell with multiple people with no computer science education. You don't need to be a genius to know Haskell, and knowing Haskell doesn't make you a special genius. And in my experience, the Haskell codebases I've worked in best exemplify the axiom you mention. I've solved so many problems by barely using my brain thanks to FP. The main prerequisite is a good attitude.
deleted 7y ago
[deleted]
touisteur 7y ago
The authors work seems very interesting, and could maybe lead to the automatic generation of a language server with semantic query and refactoring capabilities, for any programming language. Or portable (in the 'language to language' sense) static analysis tools or interpreters or symbolic execution tools... Just wondering (out loud) how you formalize language semantics so they can be consumed... I know about grammar formalisms (bnf/ebnf, antlr, peach/xsd/asn.1...) but what is the lingua franca of language semantics? Except for latex papers...
- aseipp 7y ago
  Most people formalize "kernel languages" that contain all the bare essentials of the language at hand. There are a variety of tools to do this; a lot of people just end up embedding their language semantics in Coq or something and writing proofs about the theories there. Alternatively, a lot of people will tend to just write literal interpreters for their kernel language in a language like Haskell or OCaml; interpreters can be seen as a lightweight machine-runnable definition. And they have the added bonus you can play with them! Another popular tool I'm aware of for this is Ott[1], which lets you write a high-level semantics description, much like you'd write in a LaTeX paper. It can then compile it to Coq, LaTeX, etc for further work. Ott is probably a much better place to start without getting too far into the weeds, if you want to write real high-level sketches. In general, I (unfortunately) don't think there's anything like a "library" of language semantics definitions that are easily reusable or anything like that. Modular definitions of semantics that can be reused like a library/API is basically a programming language abstraction problem, but I'm not sure what the current forefront of research on that is. In general, very few languages have fully specified machine-checked semantics, or even unproven ones. [1]: https://www.cl.cam.ac.uk/~pes20/ott/ https://www.cl.cam.ac.uk/~pes20/ott/
  - touisteur 7y ago
    Thanks a lot for this answer and the references. I think the author is working on a generic semantic tool to generate all kinds of language tooling automatically ; I'll be sure to follow his work.
  - 7y ago
skybrian 7y ago
> For instance, I teach programmers to tune out the noise of refactoring catalogs and learn how most familiar refactorings instead follow from a few primordial algebraic laws Why "instead?" Knowing more math is good, but I think the author is doing his students a disservice. You don't need to memorize refactoring catalogs, but if someone says "maybe you should use a visitor pattern here" it's helpful to look it up and know what it means. It's not deep, but this is the vocabulary of the programming profession, not noise, and we're not going to switch to speaking in abstract mathematics just because some people like math or see a deeper meaning in it. Defunctionalization seems like it might be a useful addition to the catalog.
- zozbot234 7y ago
  They can learn that stuff after they've become familiar with the fundamentals. Visitor pattern is just a way to implement pattern matching starting from the primitives Java and the like provide.
  - AnimalMuppet 7y ago
    That's like saying that people can learn arithmetic after they learn group theory, which they can learn after they learn category theory. No, learn the concrete first, then learn the abstractions, so that you have some concept of why the abstractions are relevant.
    - strbean 7y ago
      I'm not sure we do kids a service by skipping over fundamental aspects of mathematics in order to stick to the 'more concrete' stuff. The staggeringly vast majority of kids will never learn a lick of group theory or category theory, and I think that is unfortunate because the fundamentals aren't difficult or big. Most high school grads will hardly have touched even basic logic, and it is frighteningly common to run into people who don't understand that "A -> B; B; Therefore A" isn't valid.
      - AnimalMuppet 7y ago
agbell 7y ago
I enjoyed this talk, and accompanying transcript on defunctionalization. Despite the verbose name, the concept is quite simple and does come up a lot. http://www.pathsensitive.com/2019/07/the-best-refactoring-youve-never-heard.html http://www.pathsensitive.com/2019/07/the-best-refactoring-yo...

60 points by nancyhua 7y ago

> defunctionalization, a transformation that replaces higher-order functions with equivalent first-order ones. For anyone else who got nothing from the title.

deleted 7y ago
[deleted]
duelingjello 7y ago
I admit to fawning for functional languages like Haskell, Clojure and OCaml for fun, but it seems like they are not more popular because having many additional, higher-order constructs makes code “obsfucated” behind clever features rather than written as simply as possible (but no simpler). Maybe for a coding shop full of insane geniuses (i.e., quants, CalTech aerospace, physicists or Stanford research department) it’s all good, but the learning curve of tight functional code is too steep in the vast majority of situations. Even if it’s good, clean and small code, functional is too often a “white elephant” because of the dearth of its practitioners. Hence the pervasiveness of C++, Java, .NET, Python and especially JS. One the fundamental UX, copy-writing, devops/sysadmin and programming axioms is: Don’t make me think e.g., reduce cognitive load by making knowledge works as easy to digest as possible using simple, familiar/conventional, intentional and clear patterns.
- Gravityloss 7y ago
  What are the ergonomics-first languages of the functional world?
  - The_rationalist 7y ago
    I would say that rust and kotlin are good at providing most of the useful concepts from functional programming (higher order functions, common functors (map, filter, etc), tail call, pattern matching, destructuring, expressions, lazy evaluation, immutable collections, actor model, algebraic data types) Sadly they lack some features at the type system level (higher kinded types, intersection and union types) TypeScript do a better job at it but lack some other features (pattern matching).
    - pkolaczk 7y ago
      Looks like the language you wanted to mention is Scala. Pragmatic and has all the things you mentioned.
    - kod 7y ago
      Kotlin doesn't have destructuring pattern matching.
  - twic 7y ago
    LISPers would say LISP.
  - kazinator 7y ago
    TXR Lisp, for one.
- The_rationalist 7y ago
  Clearly, but a subset of functional features help to reduce cognitive load. And this subset is what modern languages target (see my comment below).
- whateveracct 7y ago
  This genius talk is so wrong. I have an bachelors in engineering from a state school. I've worked in Haskell with multiple people with no computer science education. You don't need to be a genius to know Haskell, and knowing Haskell doesn't make you a special genius. And in my experience, the Haskell codebases I've worked in best exemplify the axiom you mention. I've solved so many problems by barely using my brain thanks to FP. The main prerequisite is a good attitude.

deleted 7y ago

[deleted]

touisteur 7y ago

The authors work seems very interesting, and could maybe lead to the automatic generation of a language server with semantic query and refactoring capabilities, for any programming language. Or portable (in the 'language to language' sense) static analysis tools or interpreters or symbolic execution tools... Just wondering (out loud) how you formalize language semantics so they can be consumed... I know about grammar formalisms (bnf/ebnf, antlr, peach/xsd/asn.1...) but what is the lingua franca of language semantics? Except for latex papers...

aseipp 7y ago
Most people formalize "kernel languages" that contain all the bare essentials of the language at hand. There are a variety of tools to do this; a lot of people just end up embedding their language semantics in Coq or something and writing proofs about the theories there. Alternatively, a lot of people will tend to just write literal interpreters for their kernel language in a language like Haskell or OCaml; interpreters can be seen as a lightweight machine-runnable definition. And they have the added bonus you can play with them! Another popular tool I'm aware of for this is Ott[1], which lets you write a high-level semantics description, much like you'd write in a LaTeX paper. It can then compile it to Coq, LaTeX, etc for further work. Ott is probably a much better place to start without getting too far into the weeds, if you want to write real high-level sketches. In general, I (unfortunately) don't think there's anything like a "library" of language semantics definitions that are easily reusable or anything like that. Modular definitions of semantics that can be reused like a library/API is basically a programming language abstraction problem, but I'm not sure what the current forefront of research on that is. In general, very few languages have fully specified machine-checked semantics, or even unproven ones. [1]: https://www.cl.cam.ac.uk/~pes20/ott/ https://www.cl.cam.ac.uk/~pes20/ott/
- touisteur 7y ago
  Thanks a lot for this answer and the references. I think the author is working on a generic semantic tool to generate all kinds of language tooling automatically ; I'll be sure to follow his work.
- 7y ago

skybrian 7y ago

> For instance, I teach programmers to tune out the noise of refactoring catalogs and learn how most familiar refactorings instead follow from a few primordial algebraic laws Why "instead?" Knowing more math is good, but I think the author is doing his students a disservice. You don't need to memorize refactoring catalogs, but if someone says "maybe you should use a visitor pattern here" it's helpful to look it up and know what it means. It's not deep, but this is the vocabulary of the programming profession, not noise, and we're not going to switch to speaking in abstract mathematics just because some people like math or see a deeper meaning in it. Defunctionalization seems like it might be a useful addition to the catalog.

zozbot234 7y ago
They can learn that stuff after they've become familiar with the fundamentals. Visitor pattern is just a way to implement pattern matching starting from the primitives Java and the like provide.
- AnimalMuppet 7y ago
  That's like saying that people can learn arithmetic after they learn group theory, which they can learn after they learn category theory. No, learn the concrete first, then learn the abstractions, so that you have some concept of why the abstractions are relevant.
  - strbean 7y ago
    I'm not sure we do kids a service by skipping over fundamental aspects of mathematics in order to stick to the 'more concrete' stuff. The staggeringly vast majority of kids will never learn a lick of group theory or category theory, and I think that is unfortunate because the fundamentals aren't difficult or big. Most high school grads will hardly have touched even basic logic, and it is frighteningly common to run into people who don't understand that "A -> B; B; Therefore A" isn't valid.
    - AnimalMuppet 7y ago

agbell 7y ago

I enjoyed this talk, and accompanying transcript on defunctionalization. Despite the verbose name, the concept is quite simple and does come up a lot. http://www.pathsensitive.com/2019/07/the-best-refactoring-youve-never-heard.html http://www.pathsensitive.com/2019/07/the-best-refactoring-yo...