Monday, February 14, 2005

Doing infinity with parametricity

After talking about using laziness to simulate infinite quantities, I've started thinking about parametricity.

In this Dr. Dobbs interview, Phil Wadler talks about how you can avoid code explosion in languages with parametric polymorphism by exploiting parametricity results: the exact same algorithm applies at all types, so you don't have to duplicate the code at each instantiation of the type parameter.

This property applies at the value level, too: the same algorithm works for all inputs (of the required type), so you can reuse the same code without duplication. Kenichi's paper with Matsuoka and Yonezawa, which is on using selective duplication to simulate infinite towers of reflective interpreters with a finite number of copies of a meta-circular interpreter, probably offers some insight into the interaction between laziness and sharing in simulating infinities. Kenichi just gave me a copy of that paper today, and it looks very cool.

No comments: