IMDEA Software

Iniciativa IMDEA

Inicio > Eventos > Software Seminar Series > 2010 > The Beta Cube
Esta página aún no ha sido traducida. A continuación se muestra la página en inglés.

Álvaro García

martes 6 de julio de 2010

11:00am Meeting room 302 (Mountain View), level 3

Álvaro García, Post-doctoral Researcher, IMDEA Software Institute

The Beta Cube

Abstract:

Pure lambda calculus reduction strategies have been thoroughly studied, as they constitute the foundations of evaluation in many programming languages. Sestoft recopiled and defined several of them as sets of big-step rules, thus clarifying varying and inaccurate definitions in the literature. From Sestoft’s work, we present a rule template which can instantiate any of the foremost strategies and some more. Abstracting the parameters of the template, we propose a space of reduction strategies we like to call the Beta Cube. We also formalise a hybridisation operator—informally suggested by Sestoft—which produces new strategies by composing a subsidiary and a base strategy from the cube. This space gives new and interesting insights about the algebraic properties of reduction strategies. In particular, we present and prove the Absorption Theorem, which states that subsidiaries are left-identities of their hybrids. More properties from the cube remain to be explored.