some image logo

HOME

SEARCH

CURRENT ISSUE

REGULAR ISSUES

   Volume 1 (2005)

   Volume 2 (2006)

   Volume 3 (2007)

   Volume 4 (2008)

   Volume 5 (2009)

   Volume 6 (2010)

   Volume 7 (2011)

   Volume 8 (2012)

   Volume 9 (2013)

   Volume 10 (2014)

   Volume 11 (2015)

   Volume 12 (2016)

      Issue 1

      Issue 2

      Issue 3

      Issue 4

   Volume 13 (2017)

SPECIAL ISSUES

SURVEY ARTICLES

AUTHORS

ABOUT

SERVICE

LOGIN

FAQ

SUPPORT

CONTACT

VOLUME 12, ISSUE 2, PAPER 12


No solvable lambda-value term left behind

©Álvaro García-Pérez, Reykjavík University, Iceland
©Pablo Nogueira, IMDEA Software Institute, Madrid, Spain

Abstract
In the lambda calculus a term is solvable iff it is operationally relevant. Solvable terms are a superset of the terms that convert to a final result called normal form. Unsolvable terms are operationally irrelevant and can be equated without loss of consistency. There is a definition of solvability for the lambda-value calculus, called v-solvability, but it is not synonymous with operational relevance, some lambda-value normal forms are unsolvable, and unsolvables cannot be consistently equated. We provide a definition of solvability for the lambda-value calculus that does capture operational relevance and such that a consistent proof-theory can be constructed where unsolvables are equated attending to the number of arguments they take (their "order" in the jargon). The intuition is that in lambda-value the different sequentialisations of a computation can be distinguished operationally. We prove a version of the Genericity Lemma stating that unsolvable terms are generic and can be replaced by arbitrary terms of equal or greater order.

Publication date: June 30, 2016

Full Text: PDF | PostScript
DOI: 10.2168/LMCS-12(2:12)2016

Hit Counts: 2774

Creative Commons