Typed Lambda Calculi and Applications: International Conference on Typed Lambda Calculi and Applications TLCA ’93 March, 16–18, 1993, Utrecht, The Netherlands Proceedings

Yohji Akama (auth.), Marc Bezem, Jan Friso Groote (eds.)3540565175, 9783540565178

The lambda calculus was developed in the 1930s by Alonzo Church. The calculus turned out to be an interesting model of computation and became theprototype for untyped functional programming languages. Operational and denotational semantics for the calculus served as examples for otherprogramming languages. In typed lambda calculi, lambda terms are classified according to their applicative behavior. In the 1960s it was discovered that the types of typed lambda calculi are in fact appearances of logical propositions. Thus there are two possible views of typed lambda calculi: – as models of computation, where terms are viewed as programs in a typed programming language; – as logical theories, where the types are viewed as propositions and the terms as proofs. The practical spin-off from these studies are: – functional programming languages which are mathematically more succinct than imperative programs; – systems for automated proof checking based on lambda caluli. This volume is the proceedings of TLCA ’93, the first international conference on Typed Lambda Calculi and Applications,organized by the Department of Philosophy of Utrecht University. It includes29 papers selected from 51 submissions.

---

Table of contents :
On Mints’ reduction for ccc-calculus….Pages 1-12
A formalization of the strong normalization proof for System F in LEGO….Pages 13-28
Partial intersection type assignment in applicative term rewriting systems….Pages 29-44
Extracting constructive content from classical logic via control-like reductions….Pages 45-59
Combining first and higher order rewrite systems with type assignment systems….Pages 60-74
A term calculus for Intuitionistic Linear Logic….Pages 75-90
Program extraction from normalization proofs….Pages 91-106
A semantics for λ &-early: a calculus with overloading and early binding….Pages 107-123
An abstract notion of application….Pages 124-138
The undecidability of typability in the Lambda-Pi-calculus….Pages 139-145
Recursive types are not conservative over F≤….Pages 146-162
The conservation theorem revisited….Pages 163-178
Modified realizability toposes and strong normalization proofs….Pages 179-194
Semantics of lambda-I and of other substructure lambda calculi….Pages 195-208
Translating dependent type theory into higher order logic….Pages 209-229
Studying the fully abstract model of PCF within its continuous function model….Pages 230-244
A new characterization of lambda definability….Pages 245-257
Combining recursive and dynamic types….Pages 258-273
Lambda calculus characterizations of poly-time….Pages 274-288
Pure type systems formalized….Pages 289-305
Orthogonal higher-order rewrite systems are confluent….Pages 306-317
Monotonic versus antimonotonic exponentiation….Pages 318-327
Inductive definitions in the system Coq rules and properties….Pages 328-345
Intersection types and bounded polymorphism….Pages 346-360
A logic for parametric polymorphism….Pages 361-375
Call-by-value and nondeterminism….Pages 376-390
Lower and upper bounds for reductions of types in λ and λP (extended abstract)….Pages 391-405
λ -Calculi with conditional rules….Pages 406-417
Type reconstruction in Fω is undecidable….Pages 418-432