Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

blog.sigplan.org

Post reply on HN
Print view View original

11–20 of 28 posts

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

#11

Post by FullyFunctional »

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

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

#12

Post by cratermoon »

choeger wrote: post #5

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 comp…

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?

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

#14

Post by whitten »

contravariant wrote: post #3

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.

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

#15

Post by codeismath »

FullyFunctional wrote: post #11

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…

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

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

#16

Post by matheusmoreira »

whitten wrote: post #14
contravariant wrote: post #3

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

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

#17

Post by lstamour »

kangalioo wrote: post #13

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.

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

#18

Post by codeismath »

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?

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

#20

Post by lootsauce »

codeismath wrote: post #15
FullyFunctional wrote: post #11

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…

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 Progr…

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?
Post reply on HN