
Sign up to save your podcasts
Or
The simplified version of Lamping's algorithm for optimal beta-reduction is discussed. We have duplicators which eat their way through lambda graphs. When copying a lambda abstraction, we send one duplicator down the variable port, and another down the body port. When they meet, they cancel each other and the duplication is done. But duplication can get paused waiting for a value to come in on a wire from outside the lambda abstraction. This can lead to a situation where some other duplication needs to duplicate a lambda graph containing frozen duplicators. Then we have to decide, when two duplicators meet, should they cancel each other (signalling the end of a duplication on one level), or should one duplicate the duplicators (for an outer duplication of some lambda graph containing frozen duplicators). The abstract algorithm leaves this choice undetermined. The hairy versions of the algorithm add complex additional machinery to keep track of these levels of duplication to resolve that nondeterminism.
5
1717 ratings
The simplified version of Lamping's algorithm for optimal beta-reduction is discussed. We have duplicators which eat their way through lambda graphs. When copying a lambda abstraction, we send one duplicator down the variable port, and another down the body port. When they meet, they cancel each other and the duplication is done. But duplication can get paused waiting for a value to come in on a wire from outside the lambda abstraction. This can lead to a situation where some other duplication needs to duplicate a lambda graph containing frozen duplicators. Then we have to decide, when two duplicators meet, should they cancel each other (signalling the end of a duplication on one level), or should one duplicate the duplicators (for an outer duplication of some lambda graph containing frozen duplicators). The abstract algorithm leaves this choice undetermined. The hairy versions of the algorithm add complex additional machinery to keep track of these levels of duplication to resolve that nondeterminism.
272 Listeners
90,584 Listeners
30,962 Listeners
109 Listeners
4,130 Listeners
31 Listeners
15,313 Listeners
34 Listeners
11 Listeners
10,294 Listeners
3,096 Listeners
47 Listeners
21 Listeners