Iowa Type Theory Commute
Iowa Type Theory Commute
Aaron Stump
Lamping's abstract algorithm
10 minutes Posted Jul 25, 2020 at 8:00 pm.
0:00
10:15
Download MP3
Show notes

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.