Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Lazy evaluation (call-by-need) is normal reduction order for lambda calculus with memoization (nothing is reduced more than once). It has been proven a long time ago that if lambda expression has a non-reducible form, it can be reached with normal reduction order, but not always with the others (eager reduction being one such example - Lean uses eager/strict evaluation, thus it is... interesting).
 help



Yes I know that, what does this have to do with my comment? Or did you want to say that call-by-name is not "lazy", which it is by many definitions?

Either way, call-by-need does not have incremental higher-order sharing. Call-by-need + incremental sharing = Lévy-optimal reduction, as was shown by Asperti and many others. This can be implemented directly with interaction combinators, without any kind of extension.


I also do not understand what you call higher order sharing. Can you provide a definition and/or paper or presentation about it?

Why is incremental higher order sharing is important?

Can interaction combinators be implemented with just lazy (graph reducing) computations?

https://bathtub-01.github.io/technical/ouros-demo/ - that was on Hacker News front page not so long ago. It is a data flow CPU implementing Haskell through graph reduction.

This is why I consider graph reduction and data flow superior to interaction nets.


As I said, I don't know much about whether interaction nets are superior to data flow (especially in hardware), I just wanted to mention some general advantages of the paradigm. My other comment explains the relation to laziness.

Incremental sharing mean essentially that when arguments are duplicated and they are _needed_ (as in call-by-need), only the outermost "constructor" (graph node) of the shared computation is duplicated, while the rest is left as-is. This duplication proceeds only whenever more constructors are _needed_. It is essentially lazy, or, incremental.

Incremental higher-order sharing is when incremental sharing can be applied to higher-order functions, say in a lazy semantics. This is very tricky (Asperti wrote a whole book on it), but, when done correctly, can make some algorithms exponentially faster than call-by-need, without affecting performance negatively.

Intuitively, you rarely need the whole body of a (shared) function duplicated in order to know how to continue with evaluation. Incremental duplication makes a lot more sense to me, and it shows in benchmarks.


Call-by-name is not lazy, because it will perform the same computations whenever value of the computation is required.

Sorry, but it is, except if you'd also provide a (non-standard) definition of laziness. Lazy means to not evaluate the argument of a function when evaluating its application. A lazy semantics can be implemented using call-by-name or call-by-need, either not sharing the evaluation, or sharing it. See Maraist, Odersky & Wadler (1998), an initial introduction to call-by-need, that defines call-by-name as being lazy - or almost all of the subsequent literature that I know.

However, in call-by-need reduction, sharing never goes beyond a function's body: In two different invocations of the same function, shared computation in their bodies will still be evaluated twice. This is different when sharing incrementally, which can famously not be implemented just by a reduction strategy (Lévy etc.). Instead, you require a whole different model of computation - for example interaction nets. Commutation propagates duplication nodes (ie. sharing of computation) incrementally, step-by-step, in a lazy manner. Only when duplication is also incremental, then can it be strongly confluent. See Lafont's initial work on interaction nets and combinators for the reasoning.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: