Ronald Garcia
Carnegie Mellon University

Lazy Evaluation and Delimited Control

Researchers have long observed a connection between call-by-need evluation and computations that exhibit coroutine-like control operations, this this connection has not been well understood.

In this work, we explore this connection by examining the operational characteristics of call-by-need evaluation, as modeled by Ariola and Felleisen's call-by-need lambda calculus.

By a series of reasoning steps, we systematically unpack the standard-order reduction relation of the calculus and discover a novel abstract machine definition which, like the calculus, goes "under lambdas."

Unlike traditional abstract machines, delimited control plays a significant role in the machine's behavior. In particular, the machine replaces the manipulation of a heap using store-based effects with disciplined management of the evaluation stack using control-based effects. In short, state is replaced with control.

To further articulate this observation, we use the abstract machine to motivate and develop a simulation of call-by-need in a call-by-value language that supports delimited control operations.

Host: Frank Pfenning

Friday, September 11, 2009
3:30 p.m.
Gates & Hillman Centers 9115

Principles of Programming Seminars