Search

The annual ICFP Programming Contest has become one of the premiere programming competitions in the world. The 9th incarnation of the contest, “The Cult of the Bound Variable,” was held in July 2006 and organized by the Principles of Programming group at Carnegie Mellon University. This report details the contest tasks, the technology used to produce the contest, and the contest results. Several tasks draw ideas from programming languages research. For example, participants implemented a simple virtual machine, played an adventure game based on a substructural logic, and programmed in a two-dimensional circuit language with a discordantly high-level operational semantics. The contest technology includes an optimizing compiler for a high-level functional language that targets our virtual machine. By the end of the three day contest, 365 teams, composed of 700 programmers from all over the world, solved at least one of the contest tasks.

We begin by recalling the essentially global character of universes in various models of homotopy type theory, which prevents a straightforward axiomatization of their properties using the internal language of the presheaf toposes from which these model are constructed. We get around this problem by extending the internal language with a modal operator for expressing properties of global elements. In this setting we show how to construct a universe that classifies the Cohen-Coquand-Huber-Mörtberg (CCHM) notion of fibration from their cubical sets model, starting from the assumption that the interval is tiny - a property that the interval in cubical sets does indeed have. This leads to an elementary axiomatization of that and related models of homotopy type theory within what we call crisp type theory.