Ê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
Logique combinatoire
Résumé
En logique mathématique, la logique combinatoire est une théorie logique introduite par Moses Schönfinkel en 1920 lors d'une conférence et développée dès 1929 par Haskell Brooks Curry pour supprimer le besoin de variables en mathématiques, pour formaliser rigoureusement la notion de fonction et pour minimiser le nombre d'opérateurs nécessaires pour définir le calcul des prédicats à la suite de Henry M. Sheffer. Plus récemment, elle a été utilisée en informatique comme modèle théorique de calcul et comme base pour la conception de langages de programmation fonctionnels.
Le concept de base de la logique combinatoire est celui de combinateur qui est une fonction d'ordre supérieur ; elle utilise uniquement l'application de fonctions et éventuellement d'autres combinateurs pour définir de nouvelles fonctions d'ordre supérieur. Chaque combinateur simplement typable est une démonstration à la Hilbert en logique intuitionniste et vice-versa . On appelle ceci la correspondance de Curry-Howard
La logique combinatoire est fondée sur deux « opérations » de base (on dit aussi deux « combinateurs ») S et K que nous définirons plus loin ; plus précisément nous en définirons le comportement ou l'« intention », car la logique combinatoire est une approche de la logique qui montre plutôt comment marchent les choses que comment les objets peuvent être décrits, on dit alors que c'est une approche intentionnelle de la logique. Si l'on veut définir la fonction que nous appellerons C et qui prend trois paramètres et rend comme résultat le premier appliqué au troisième, le tout étant appliqué au second, on pourra l'écrire :
C ≡ S ((S (K S) K) (S (K S) K) S) (K K)
qui, comme on le voit, ne comporte pas de variable. On pourra regretter que l'avantage de ne pas utiliser de variables se paie par la longueur des expressions et une certaine illisibilité. Aujourd'hui la logique combinatoire est surtout utilisée par les logiciens pour répondre positivement à la question « Est-il possible de se passer de variables ? » et par les informaticiens pour compiler les langages fonctionnels.
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.