Antoine Allioux (Institut de Recherche en Informatique Fondamentale, Paris, France) |

The Krivine machine is an abstract machine implementing the linear head reduction of lambda-calculus. Ehrhard and Regnier gave a resource sensitive version returning the annotated form of a lambda-term accounting for the resources used by the linear head reduction. These annotations take the form of terms in the resource lambda-calculus.
We generalize this resource-driven Krivine machine to the case of the algebraic lambda-calculus. The latter is an extension of the pure lambda-calculus allowing for the linear combination of lambda-terms with coefficients taken from a semiring. Our machine associates a lambda-term M and a resource annotation t with a scalar k in the semiring describing some quantitative properties of the linear head reduction of M. In the particular case of non-negative real numbers and of algebraic terms M representing probability distributions, the coefficient k gives the probability that the linear head reduction actually uses exactly the resources annotated by t. In the general case, we prove that the coefficient k can be recovered from the coefficient of t in the Taylor expansion of M and from the normal form of t. |

Published: 17th January 2017.

ArXived at: https://dx.doi.org/10.4204/EPTCS.238.3 | bibtex | |

Comments and questions to: eptcs@eptcs.org |

For website issues: webmaster@eptcs.org |