Hacker News Reader

It turns out that it is possible to optimally minimize the number of beta reductions in a lambda calculus program. See this excellent blog post: https://medium.com/@maiavictor/some-functions-may-have-negat...

View on HN

Approaches like the Abstract Algorithm (that you link to) turn out to just shift the costs elsewhere; in particular to the "book keeping" (IIUC nodes act differently depending on which "path" we're traversing, and keeping track of that exactly cancels out the benefits of optimal sharing).

For example, see links at https://www.reddit.com/r/haskell/comments/2zqtfk/why_isnt_an...

Reply on news.ycombinator.com