5 ms·
Defunctionalization: Everybody does it, nobody talks about it (2019)
- kangalioo 5y agoI'd love to read more about that little bit from the beginning about representing refactoring as mathematical operations
- lstamour 5y agoI 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 https://softwareengineering.stackexchange.com/a/140879 as starting points more generally though.
- Groxx 5y agoSo... specialization? It's a very common thing when talking about generics in programming languages, anyway.
- contravariant 5y agoPut 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.
- whitten 5y agoCould 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.
- matheusmoreira 5y agoInstead 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
- kristianp 5y agoOn 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."
- choeger 5y agoThe 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.
- cratermoon 5y agoSo 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?
- BobbyJo 5y ago> 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.
- cratermoon 5y agoThis 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?
- SinParadise 5y agoThe article in video form: https://www.youtube.com/watch?v=vNwukfhsOME https://www.youtube.com/watch?v=vNwukfhsOME
- cyanydeez 5y agoi,m too dumb for this ideza
- cratermoon 5y agoHis 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.
- mlazos 5y agoInteresting 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.
- dang 5y agoDiscussed at the time: Defunctionalization: Everybody Does It, Nobody Talks About It - https://news.ycombinator.com/item?id=21916774 https://news.ycombinator.com/item?id=21916774 - Dec 2019 (20 comments)
- FullyFunctional 5y agoDefunctionalization 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 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
- codeismath 5y agoThe 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 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&context=lcsmith_other https://surface.syr.edu/cgi/viewcontent.cgi?article=1012&con... [1] [PDF] https://homepages.inf.ed.ac.uk/wadler/papers/papers-we-love/reynolds-definitional-interpreters-1972.pdf https://homepages.inf.ed.ac.uk/wadler/papers/papers-we-love/... [2] https://homepages.inf.ed.ac.uk/wadler/topics/history.html#definitional-interpreters https://homepages.inf.ed.ac.uk/wadler/topics/history.html#de... [3] [PDF] https://homepages.inf.ed.ac.uk/wadler/papers/papers-we-love/reynolds-definitional-interpreters-revisited.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/reynolds-discoveries.pdf https://homepages.inf.ed.ac.uk/wadler/papers/papers-we-love/...
- codeismath 5y agoIt'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?
- remexre 5y agoI 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.
- amelius 5y agoWhile a useful technique, it seems like this gives a new dimension to the problem of "what color is your function?"
- galaxyLogic 5y agoIsn'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.
- sullyj3 5y agoThis 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 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.