Defunctionalization: Everybody Does It, Nobody Talks About It | Hacker News Reader

Defunctionalization: Everybody Does It, Nobody Talks About It

blog.sigplan.org

60 pointsnancyhua20 comments

> defunctionalization, a transformation that replaces higher-order functions with equivalent first-order ones.

For anyone else who got nothing from the title.

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.

What are the ergonomics-first languages of the functional world?

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).

Looks like the language you wanted to mention is Scala. Pragmatic and has all the things you mentioned.

Kotlin doesn't have destructuring pattern matching.

LISPers would say LISP.

TXR Lisp, for one.

Clearly, but a subset of functional features help to reduce cognitive load. And this subset is what modern languages target (see my comment below).

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.

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...

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/

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.

By the way I kept going down this rabbit-hole and found an example of what you described : https://unsat.cs.washington.edu/projects/serval/

IIUC Serval uses an interpreter built in Rosette (?) to build a Symbolic execution tool.

> 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.

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.

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.

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.

We would do a worse disservice by skipping over more concrete stuff to teach group theory or, worse, category theory.

First, even if you can teach group theory or category theory to an 8-year-old, if you wind up with an 8-year-old who knows category theory but can't add, is that a win? No, it isn't. They need to be able to add in a way that they don't need group theory.

But, second, you can't in any meaningful way teach category theory, or even group theory, to an 8-year-old. But you can teach them to add.

So again, I say, concrete first, then abstractions. First because they can function better knowing one concrete form and no abstract than they can knowing the abstract and zero concrete forms. And second, they are able to learn the most-useful concrete form younger and with less background than they are able to learn the abstraction.

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-yo...

Reply on news.ycombinator.com