Defunctionalization: Everybody does it, nobody talks about it (2019) | Hacker News Reader

Defunctionalization: Everybody does it, nobody talks about it (2019)

blog.sigplan.org

59 pointsTomte26 comments

The thing is, and the article correctly mentions it, that defunctionalization sacrifices composability. This is not just a technical matter, mind you. If you design your distributed system around defunctionalized higher-order functions, you have to ensure that client and server have the same understanding of valid parameters. That's a non-trivial problem.

So while this might be a cool technique for whole-program compilers, I think it doesn't really fit into anything that has an API boundary.

So you don't think that a website would not benefit this? Imagine a design where the user selects options in the browser front end for how to filter product search results, and the system has contract whereby the front end can call the search API with a set of valid filters and get the results back. Yes, I know that typically the front end would ask the back end, for example, all things in a category, then do the filtering within the search results at the browser. I'm speaking to a hypothetical system that wouldn't be dependent on the user providing some classifying condition at first. Imagine, say, a library. You could require the user to pick an LC catalog classification first, but how many non-librarians know that Class D is World History and History of Europe, Asia, Africa, Australia, New Zealand, Etc?

> Yes, I know that typically the front end would ask the back end, for example, all things in a category, then do the filtering within the search results at the browser

Please no.

This is fairly common when the data involved are relatively small. It's much faster and a much better user experience to query the server once for a couple of hundred items and allow the user to view it with different criteria than it is to do a round trip to the server every time the user wants to change or refine the selected data.

What's your objection to it?

I've just never seen a scenario where the amount of data wasn't too large for the browser to be responsive while doing things this way.

You would use higher-order functions particularly when you cannot determine the scope of your input ahead of time. For instance when you provide something that searches an unstructured database of documents (e.g., mongo).

In such a scenario, you could apply defunctionalization. But you'd need to re-apply this technique whenever a new filter comes up or one becomes obsolete. Then you would have to make sure that both your client and server have the same version of the API.

If you design a functional system instead, say by allowing filters in a domain-specific language, ala jq, you write your filter function once and never need to touch the API, because it is "complete".

Which alternative do you prefer?

> Which alternative do you prefer?

It depends. How hard it is to write the generalized functional system and how many filters do I need to support initially? How much do filters really change? The "but what if you need to change something" objection comes up quite a lot. In practice it is often better to apply the knowledge and requirements I have and evolve the system as my understanding changes than to try to anticipate all possible scenarios up front. In the latter case, if I put a lot of effort into something and I make the wrong call I either don't have as many changes as I thought, so it's wasted effort, or changes happen in ways I didn't anticipate, so my solution activity works against me.

This seems like exactly the sort of issue the Unison language is trying to tackle. They want straightforward execution of distributed computations using the same language, with no friction across machine boundaries, no sacrificing composibility.

The article mentions:

> remote procedure calls with higher-order functional arguments would require serializing those functions, which is not easy to do safely or efficiently.

This is exactly what Unison is designed to do. Code is not stored as text, but is stored in a serialized AST form and identified by hash. Therefore, transmission between nodes is trivial. The language is still a work in progress, but it's making rapid strides.

Here's an explanation: https://www.youtube.com/watch?v=gCWtkvDQ2ZI

The part relevant to distributed computation is at 30:08, but the earlier parts go through the basics of how code is stored, and why this design choice was made, which might help with understanding what's going on.

It's been on my list of things to explore for a while... the relationship between defunctionalization, continuations, and "Algebraic Effects".

The reason... I like seeing how different languages handle asynchronous code vs synchronous code. F# has their way, C# has theirs, JavaScript async/await, colored functions, Project Loom, co-routines, React Fibers, etc. I'm intrigued that a language that has built-in algebraic effects can do async wihtout any other changes to the language (as if async and sync were the same).

Is there any relation to defunctionalization for this kind of stuff?

I don't think the article's SIGIO example made much sense -- if you have delimited continuations, you _don't_ need defunctionalize them if they're staying in-process.

Discussed at the time:

Defunctionalization: Everybody Does It, Nobody Talks About It - https://news.ycombinator.com/item?id=21916774 - Dec 2019 (20 comments)

Put like this defunctionalisation is just eval for a domain-specific-language that you hope doesn't do the things you don't want it to.

Could you clarify this, and give an example? This is an intriguing idea of eval that gets limited kinds of expressions, whether from defunctionalization or for security reasons.

Instead of having a function that can accept an arbitrary function as parameter, the compiler enumerates all known uses of the function into a data type and uses that as input instead. The resulting code is no longer general purpose.

It's as if you gave Intel your program and they produced a special optimized processor that runs just the instructions found in your program and nothing else.

> the insight of defunctionalization is to find all actual uses of the higher-order function

> Each distinct use of the filter function yields a new case in the Filter datatype

Defunctionalization was introduced by John Renolds in 1972 [1] and entire compiler backends have been based on it [2].

[1] "Definitional Interpreters for Higher-Order Programming Languages", John C. Reynolds, 1972 as per https://en.wikipedia.org/wiki/Defunctionalization

[2] "The GRIN project: A highly optimising back end for lazy functional languages", Urban Boquist, Thomas Johnsson, 2005

"A modern look at GRIN, an optimizing functional language back end", Péter Dávid Podlovics, Csaba Hruska, Andor Pénzes, 2019

The Reynolds paper is one of my favorites. It was re-typeset in 1998 making it a lot easier to follow the math [0]. It's fun to compare it to a copy of the original from 1972 [1].

Philip Wadler had this to say about the paper: "Certain papers change your life. McCarthy's 'Recursive Functions of Symbolic Expressions and their Computation by Machine (Part I)' (1960) changed mine, and so did Landin's 'The Next 700 Programming Languages' (1966). And I remember the moment, halfway through my graduate career, when Guy Steele handed me Reynolds's 'Definitional Interpreters for Higher-Order Programming Languages' (1972)."[2] This is how I discovered it I believe.

The paper is exceedingly approachable. It was so well written that I immediately purchased a used copy of Reynolds' book on programming languages (which I did not have as easy time with compared to the paper - and still remains unfinished on my bookshelf).

When they republished the paper in 1998, Reynolds wrote about how the paper came to be [3], and I believe about the discoveries of continuations [4].

I recently implemented Reynold's meta-circular interpreter in TypeScript and serialized the abstract syntax into JSON. Coincidentally, a few days later I saw a post on HN something about "executable JSON" or some such "programming language" that the creator was very proud of making it into a product of sorts. (found it... JSON Logic: https://news.ycombinator.com/item?id=27306263). Queue Greenspun's tenth rule. I chuckled as I looked at the JSON Logic syntax knowing that a little Reynold's interpreter with its AST serialized to JSON is infinitely more powerful and extensible (allowing higher-order functions and such). I highly recommend anyone reading this to write the 50 or so lines of TypeScript necessary to implement Reynold's meta-circular interpreter (EXTREMELY EASY and nearly identical line-for-line to the 1998 paper, only in TypeScript instead of lambda calculus).

Good stuff.

[0] [PDF] https://surface.syr.edu/cgi/viewcontent.cgi?article=1012&con...

[1] [PDF] https://homepages.inf.ed.ac.uk/wadler/papers/papers-we-love/...

[2] https://homepages.inf.ed.ac.uk/wadler/topics/history.html#de...

[3] [PDF] https://homepages.inf.ed.ac.uk/wadler/papers/papers-we-love/...

[4] [PDF] https://homepages.inf.ed.ac.uk/wadler/papers/papers-we-love/...

Please share the code! I’d love to learn about this space with the benefit of it as I am not well versed in functional languages. Also on the JSON Logic comment. I am using it in production to serialize the product of a GUI query builder and execute it on the backend. I don’t know of a better solution do you?

The article in video form:

https://www.youtube.com/watch?v=vNwukfhsOME

His discussion of how refactorings can be described as mechanical transformations is worth reading for itself. In fact, the logical, mechanical nature of refactorings is why there are tools that can do them automatically, at least in languages where the code can be statically analyzed for them.

On continuations: "This suggests that language-level support for defunctionalization could be used to keep the beauty of explicit continuations while gaining the scalability of multiple machines.

A few systems, such as the MFlow and jmacro-rpc frameworks, have tried to circumvent this problem by sending continuations over the wire in a different way: by sending over information about the execution’s past, so that the other machine may replay a function call in order to get to where the first machine left off. This can be seen as an application of my ICFP 2018 paper on thermometer continuations."

Interesting article, to me it just appears to be deciding how much you know at compile time vs runtime. (Runtime expressibility vs compile-time proofs) If you make your code a DSL you’re implicitly limiting your code to the semantics of your DSL, (you know at compile time that your code will do some finite set of things) while if you enable arbitrary code to be passed as higher order functions you lose this compile time knowledge. In the distributed systems case this is a positive because you want to limit the behavior of programs sent over the wire for security reasons.

So... specialization? It's a very common thing when talking about generics in programming languages, anyway.

Isn't de-functionalization the only way systems can communicate over the network? You have to serialize your data say by turning it into JSON which you can not transport functions between the systems - which would also be a security risk.

While a useful technique, it seems like this gives a new dimension to the problem of "what color is your function?"

I'd love to read more about that little bit from the beginning about representing refactoring as mathematical operations

I was trying to find an article as a quick summary of some approaches but couldn’t after a bit of searching. Googling some different keywords suggested https://softwareengineering.stackexchange.com/a/140879 as starting points more generally though.

Reply on news.ycombinator.com