Typed Lambda Calculi and Applications

1. Front Matter

   PDF

2. On Mints' reduction for ccc-calculus

   • Yohji Akama

   Pages 1-12

3. A formalization of the strong normalization proof for System F in LEGO

   • Thorsten Altenkirch

   Pages 13-28

4. Partial intersection type assignment in applicative term rewriting systems

   • Steffen van Bakel

   Pages 29-44

5. Extracting constructive content from classical logic via control-like reductions

   • Franco Barbanera, Stefano Berardi

   Pages 45-59

6. Combining first and higher order rewrite systems with type assignment systems

   • Franco Barbanera, Maribel Fernández

   Pages 60-74

7. A term calculus for Intuitionistic Linear Logic

   • Nick Benton, Gavin Bierman, Valeria de Paiva, Martin Hyland

   Pages 75-90

8. Program extraction from normalization proofs

   • Ulrich Berger

   Pages 91-106

9. A semantics for λ &-early: a calculus with overloading and early binding

   • Giuseppe Castagna, Giorgio Ghelli, Giuseppe Longo

   Pages 107-123

10. An abstract notion of application

    • Pietro Di Gianantonio, Furio Honsell

    Pages 124-138

11. The undecidability of typability in the Lambda-Pi-calculus

    • Gilles Dowek

    Pages 139-145

12. Recursive types are not conservative over F≤

    • Giorgio Ghelli

    Pages 146-162

13. The conservation theorem revisited

    • Philippe Groote

    Pages 163-178

14. Modified realizability toposes and strong normalization proofs

    • J. M. E. Hyland, C. -H. L. Ong

    Pages 179-194

15. Semantics of lambda-I and of other substructure lambda calculi

    • Bart Jacobs

    Pages 195-208

16. Translating dependent type theory into higher order logic

    • Bart Jacobs, Tom Melham

    Pages 209-229

17. Studying the fully abstract model of PCF within its continuous function model

    • Achim Jung, Allen Stoughton

    Pages 230-244

18. A new characterization of lambda definability

    • Achim Jung, Jerzy Tiuryn

    Pages 245-257

19. Combining recursive and dynamic types

    • Hans Leiß

    Pages 258-273

20. Lambda calculus characterizations of poly-time

    • Daniel Leivant, Jean-Yves Marion

    Pages 274-288

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.

• Automat
• Beweis-Verifikation
• Denotational Semantics
• Getypter Lambda-Kalkül
• Models of Computation
• Proof Verification
• Rechenmodelle
• SPIN
• Term Rewriting
• Term-Ersetzung
• lambda calculus
• programming
• programming language
• semantics

Policies and ethics