Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Deductive lambda calculus
Résumé
Deductive lambda calculus considers what happens when lambda terms are regarded as mathematical expressions. One interpretation of the untyped lambda calculus is as a programming language where evaluation proceeds by performing reductions on an expression until it is in normal form. In this interpretation, if the expression never reduces to normal form then the program never terminates, and the value is undefined. Considered as a mathematical deductive system, each reduction would not alter the value of the expression. The expression would equal the reduction of the expression.
Alonzo Church invented the lambda calculus in the 1930s, originally to provide a new and simpler basis for mathematics. However soon after inventing it major logic problems were identified with the definition of the lambda abstraction: The Kleene–Rosser paradox is an implementation of Richard's paradox in the lambda calculus. Haskell Curry found that the key step in this paradox could be used to implement the simpler Curry's paradox. The existence of these paradoxes meant that the lambda calculus could not be both consistent and complete as a deductive system.
Haskell Curry studied of illative (deductive) combinatory logic in 1941. Combinatory logic is closely related to lambda calculus, and the same paradoxes exist in each.
Later the lambda calculus was resurrected as a definition of a programming language.
Lambda calculus is the model and inspiration for the development of functional programming languages. These languages implement the lambda abstraction, and use it in conjunction with application of functions, and types.
The use of lambda abstractions, which are then embedded into other mathematical systems, and used as a deductive system, leads to a number of problems, such as Curry's paradox. The problems are related to the definition of the lambda abstraction and the definition and use of functions as the basic type in lambda calculus. This article describes these problems and how they arise.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.