Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Conjunctive Types and SKInT

Jean Goubault-LarrecqContact Information

(6)  G.I.E. Dyade, INRIA, Inria bâtiment 30, F-78153 Le Chesnay Cedex
Abstract
The λ-calculus and its typed versions are important tools for studying most fundamental computation and deduction paradigms. However, the non-trivial nature of substitution, as used in the definition of λ-reduction notably, has spurred the design of various first-order languages representing λ-terms, λ-reduction and λ-conversion, where computation is simple, first-order rewriting, and substitution becomes an easy notion again. Let us cite Curry’s combinators [7], Curien’s categorical combinators [5], the myriad of so-called λ-calculi with explicit substitutions, among which λσ [1], λσ⇑. [12], λυ [17], λζ [19], etc. Unfortunately, each one of these calculi has defects: Curry’s combinators do not model λ-conversion fully, categorical combinators, λσ and λσ⇑ do not normalize strongly in the typed case [18], λυ is not confluent in the presence of free variables (a.k.a. metavariables), λζ models λ-conversion but not λ-reduction, etc.
This work has been done in the context of Dyade (Bull/Inria R&D joint venture).

Contact Information Jean Goubault-Larrecq
Email: Jean.Goubault@inria.fr
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: mpweb07
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)