Time flies like an applicative functor

Conor McBride

Department of Computer and Information Sciences
University of Strathclyde, Glasgow

Thursday, 7 January 2010, 16:00 (note the unusual time)
Cybernetica Bldg (Akadeemia tee 21), room B101

Abstract: Circular programs always make my head spin, and sometimes my computer too. Lazy evaluation allows us to trade in data which do not yet exist, in the hope that they can be computed just in time. If an apparently circular program does not, in fact, have cyclic data dependencies, it will work! However, it is only too easy to write well-typed programs which consume data before they are produced and spiral into a black hole. This talk presents a typed approach to circular programming, abstractly modelling relative time, ensuring that the present does not depend on the future. Classic perplexing examples, such as repMin, and even the breadth-first tree-labelling algorithm of Jones and Gibbons are explicable in this setting, with a minimum of fuss.

Tarmo Uustalu
Last update 5 January 2010