Quelle est la contribution du lambda calcul au domaine de la théorie du calcul?

85

Je suis en train de lire sur le calcul lambda pour "apprendre à le connaître". Je le vois comme une forme alternative de calcul par opposition à la machine de Turing. C'est une manière intéressante de faire les choses avec des fonctions / réductions (en gros). Certaines questions continuent à me harceler:

Quel est l'intérêt du lambda calcul? Pourquoi passer par toutes ces fonctions / réductions? Quel est le but?
En conséquence, je reste à me demander: qu'est-ce que le lambda calcul a fait exactement pour faire avancer la théorie de la CS? Quelles sont ses contributions qui me permettraient d'avoir un moment "aha" de compréhension de la nécessité de son existence?
Pourquoi le lambda calcul n'est-il pas couvert dans les textes sur la théorie des automates? L'itinéraire habituel consiste à passer en revue divers automates, grammaires, machines de Turing et classes de complexité. Le lambda calcul n'est inclus dans le programme que pour les cours de style SICP (peut-être pas?). Mais j'ai rarement vu que cela faisait partie du programme de base de CS. Cela signifie-t-il que ce n'est pas si précieux? Peut-être pas et peut-être que je manque quelque chose ici?

Je suis conscient que les langages de programmation fonctionnels sont basés sur le lambda calcul, mais je ne considère pas cela comme une contribution valable, car ils ont été créés bien avant les langages de programmation. Alors, à quoi sert vraiment de comprendre / comprendre le lambda calcul, ses applications / contributions à la théorie?

soft-question big-picture lambda-calculus ho.history-overview Doctorat
la source

6

Un ensemble de réponses connexes explique la différence de pouvoir entre le

calculus et les TM: cstheory.stackexchange.com/questions/1117/…

λ

$\lambda$

Suresh Venkat

4

Peut-être que la discussion sur les raisons historiques de l'adoption de la machine de Turing en tant que modèle de calcul primaire présente également un intérêt.

Martin Berger

5

En un sens, sa contribution a été de créer le champ. N'oubliez pas que Church a mis au point le lambda calcul, mais que ce n'était pas au début considéré comme un modèle de calcul universel.

Dan Hulme

Dans mes études principales, j'ai Functional Programmingabordé Haskell et un peu de Lisp. Son successeur était le Principles of Programming LanguagesML et l’introduction du lambda calcul. Comme le montrent certaines réponses, c’est vraiment à cela que revient le lambda calcul: dans un cours sur les langages de programmation, la dactylographie, etc.

Shaz

cette question est une relation similaire entre les TM et le calcul Lambda et traite également de la préséance historique du calcul Lambda

vzn

96

-calculus a deux rôles clés. $\lambda$

C'est une base mathématique simple d'un comportement de calcul séquentiel, fonctionnel et d'ordre supérieur.
C'est une représentation des preuves en logique constructive.

Ceci est également connu comme la correspondance de Curry-Howard . Conjointement, la double vision du calcul comme preuve et comme langage de programmation (séquentiel, fonctionnel, d'ordre supérieur), renforcée par la sensation algébrique du calcul (qui n'est pas partagée par les machines de Turing), a conduit à un transfert de technologie massif. entre la logique, les fondements des mathématiques et la programmation. Ce transfert est toujours en cours, par exemple dans la théorie des types d'homotopie . En particulier, le développement des langages de programmation en général, et des disciplines de dactylographie en particulier, est inconcevable sans $\lambda$ $\lambda$ $\lambda$ -calcul. La plupart des langages de programmation ont une certaine dette vis-à-vis de Lisp et ML (par exemple, le ramassage des ordures a été inventé pour Lisp), descendants directs du -calculus. Un deuxième volet de travail fortement influencé par le calcul est celui des assistants de preuve interactifs . $\lambda$ $\lambda$

Doit-on connaître -calcul pour être un programmeur compétent, voire un théoricien de l'informatique? Si vous n'êtes pas intéressé par les types, les langages de vérification et de programmation avec des fonctionnalités d'ordre supérieur, alors c'est probablement un modèle de calcul qui ne vous sera pas très utile. En particulier, si vous êtes intéressé par la théorie de la complexité, alors -calculus n’est probablement pas un modèle idéal, car l’étape de réduction de base est puissante: elle peut créer un nombre arbitraire. de copies sur , donc $\lambda$ $\lambda$

(λ x . M) N \to_{β} M [N / x]

$(\lambda x.M) N \rightarrow_{\beta} M[N/x]$

N

$N$

\to_{β}

$\rightarrow_{\beta}$ est une notion de base irréaliste dans la comptabilisation du coût de calcul microscopique. Je pense que c'est la raison principale pour laquelle la théorie A n'est pas tellement amoureuse du

calcul. Inversement, les machines de Turing ne sont pas très inspirantes pour le développement de langage de programmation, car il n’existe pas de notions naturelles de composition de la machine, alors que pour

-calculus, si

et

sont des programmes,

. Cette vision algébrique du calcul concerne naturellement les langages de programmation utilisés dans la pratique, et une grande partie du développement du langage peut être comprise comme la recherche et la recherche de nouveaux opérateurs de composition de programmes.

λ

$\lambda$

λ

$\lambda$

M

$M$

N

$N$

M N

$MN$

Pour un aperçu encyclopédique de l'histoire du calcul, voir Histoire du lambda-calcul et Logique combinatoire de Cardone et Hindley . $\lambda$

Martin Berger
la source

8

C'est une très bonne réponse.

Suresh Venkat

9

En ce qui concerne "l'irréalisme" de

réduction

: Beniamino Accattoli et Ugo Dal Lago ont récemment montré un résultat surprenant, indiquant que le nombre de pas-

à la forme normale dans toute stratégie de réduction standard (par exemple, la plus à l'extrême) est une mesure de complexité invariante. Cela signifie que, même si la mise en œuvre de

réduction

tant que telle est coûteuse, compter le nombre de réductions n’est pas une mesure de complexité irréaliste (par exemple, cela n’affecterait pas la définition de la classe

).

β

$\beta$

β

$\beta$

β

$\beta$

P

$\mathsf P$

Damiano Mazza

5

@DamianoMazza Puisqu'il s'agit d'un nouveau résultat, il n'aurait pu influencer l'histoire de la théorie A. En outre, je pense que cela ne concerne que certaines notions de réduction. L'article de P = NP de IIRC Asperti , jusqu'à partage, montre que P et NP s'effondrent si vous avez une stratégie de réduction «optimale» au sens de J.-J. Prélèvement.

Martin Berger

6

@MartinBerger: oui bien sûr. Mon commentaire visait à ajouter des informations sur la complexité de la

réduction, mais pas du tout à "corriger" votre affirmation sur le manque d’influence sur la théorie A (que j’ai répété dans ma réponse). Soit dit en passant, le résultat obtenu par Accattoli et Dal Lago est valable pour la

réduction habituelle la plus extrême ( voir p.2, c.2, l.11 de leur article). C'est pourquoi c'est si intéressant (et mérite d'être mentionné). Le résultat d'Asperti concerne, comme vous le dites, la réduction optimale de Lévy, qui n'est pas une stratégie de

réduction (en particulier, l'extrême gauche n'est pas optimale).

β

$\beta$

β

$\beta$

β

$\beta$

Damiano Mazza

27

$\lambda$ $\lambda$

$\lambda$ $\mu$
Deuxièmement, en ce qui concerne le langage de programmation fonctionnel, je ne comprends pas la contribution qui n’est pas valable : tous nos modèles de calcul ont été inventés bien avant que rien ne se passe en informatique! Ainsi, -calculus a apporté une autre vision du calcul, en quelque sorte orthogonale aux machines de Turing, très fructueuse dans le domaine des langages de programmation (qui fait partie du domaine de la théorie du calcul). $\lambda$
Enfin, et à titre d'exemple plus spécifique, je pense à la complexité de calcul implicite qui vise à caractériser les classes de complexité au moyen de langages dédiés. Les premiers résultats tels que le théorème de Bellantoni-Cook ont été énoncés en termes de fonctions récursives, mais des résultats plus récents utilisent le vocabulaire et les techniques de -calculus. Voir cette brève introduction à la complexité de calcul implicite pour plus d'informations et d'indicateurs, ou pour consulter les débats des ateliers DICE . $\mu$ $\lambda$

Bruno
la source

20

$\lambda$

Qu'a fait exactement le lambda calcul pour faire avancer la théorie de la CS?

$\lambda$ $\lambda$ $\lambda$

$\lambda$

Damiano Mazza
la source

2

λ

$\lambda$

λ

$\lambda$

π

$\pi$

π

$\pi$

5

Si je pouvais me reproduire moi-même, je ferais un duplicata pour examiner le rapport P / NP à l'aide de BLL et de sa réalisabilité. Les relations logiques ne semblent pas être des "preuves naturelles", la discipline de type linéaire évite de relativiser, et les théorèmes de complétude polytime de BLL semblent vous permettre d'éviter de vous demander s'il existe des classes d'algorithmes que vous avez manquées. La relation entre la linéarité et la théorie de la représentation suggère également des liens avec la GCT. Je suppose que tout cela explique pourquoi vous êtes tentés et frustrés. :)

Neel Krishnaswami

1

Hey @NeelKrishnaswami, pourriez-vous s'il vous plaît me diriger vers la lecture de documents qui traitent de BLL (logique linéaire bornée) et de preuves naturelles?

Martin Berger

Re B vs. A: le lambda-calcul ne vise qu'à mieux structurer les mêmes calculs, mais ne peut pas, par exemple, produire de meilleurs algorithmes. Par élimination de la coupe et par la propriété subformula du résultat, tout programme de type du premier ordre peut être écrit sans fonctions de première classe. Mais l'élimination de la coupe correspond à la duplication de code: nous constatons donc à nouveau que vous n'avez pas besoin de fonctions d'ordre supérieur si vous êtes prêt à faire suffisamment de copier-coller. (La défonctionnalisation de Reynolds vous permet d'éviter même le copier-coller, mais c'est une transformation globale, il est donc préférable de laisser le soin à un compilateur).

Blaisorblade

De manière anecdotique, mon commentaire est motivé par la programmation avec un algorithme - il est génial, mais il semble résumer beaucoup moins que ce que je trouve souhaitable. Je ne prétends pas que c'est général, mais j'affirme que les abstractions dans le code ne sont souvent pas nécessaires / accentuées lors de l'écriture d'algorithmes. (Considérez combien d’implémentations quicksort incorporent la fonction de partition - je trouve cela inacceptable).

Blaisorblade

13

Vos questions peuvent être abordées de plusieurs côtés. J'aimerais laisser de côté les aspects historiques et philosophiques et aborder votre question principale, que je considère être la suivante:

Quel est l'intérêt du lambda calcul? Pourquoi passer par toutes ces fonctions / réductions?

Quel est l'intérêt de l'algèbre booléenne, de l'algèbre relationnelle, de la logique du premier ordre, de la théorie des types ou de tout autre formalisme / théorie mathématique? La réponse est qu’ils n’ont aucun but inhérent , même si leurs concepteurs les ont créés pour un but ou un autre. Leibniz, lors de l’édification des fondations de l’algèbre booléenne, avait un projet philosophique à l’esprit; Boole l'a étudié pour ses propres raisons. Le travail de de Morgan sur l'algèbre relationnelle a également été motivé par ses différents projets. Peirce et Frege avaient leurs propres motivations pour créer une logique moderne.

Le point est le suivant: quelle que soit la raison pour laquelle l’Église a eu à créer le lambda calcul, le point du lambda calcul varie d’un pratiquant à un autre.

Pour quelqu'un, c'est une notation commode pour parler de calculs; une alternative aux machines de Turing, et ainsi de suite.
Pour un autre, c'est une base mathématique solide sur laquelle construire un langage de programmation plus sophistiqué (par exemple, McCarthy, Stanley).
Pour une troisième personne, il s'agit d'un outil rigoureux permettant de donner la sémantique des langages naturels et de programmation (par exemple, Montague, Fitch, Kratzer).

Je pense que le Lambda calcul est un langage formel qui mérite d’être étudié pour son propre intérêt. Vous pouvez apprendre le fait que, dans le calcul lambda non typé, nous avons ces petites bêtes appelées «combinateurs en Y» et comment elles nous aident à définir les fonctions récursives et à rendre la preuve de l'indécidabilité si élégante et simple. Vous pouvez apprendre le fait étonnant qu’il existe une correspondance intime entre le lambda calcul simplement typé et un type de logique intuitionniste . Il y a beaucoup d'autres sujets intéressants à explorer (par exemple, comment devrions-nous donner la sémantique du calcul lambda? Comment pouvons-nous transformer le calcul lambda en un système déductif comme FOL?)

Consultez Introduction aux combinateurs et λ – Calculus de Hindley & Seldin pour une introduction. The Lambda Calculus de Barendregt est la bible, donc si vous êtes accro à Hindley & Seldin, vous pourrez explorer de nombreux sujets de nature sémantique et syntaxique.

Hunan Rostomyan
la source

6

Je n'achète pas cet argument "pour son propre bien". Le but d'un formalisme mathématique est d'élucider notre compréhension d'un concept. Ce qui est élucidé peut évoluer avec le temps, mais à moins qu'un formalisme ne nous aide à réfléchir plus clairement à une idée, il disparaît généralement. Dans ce sens, il est valide de demander comment le lambda calcul élucide le concept de calcul d’une manière qui n’est pas englobée par les MT.

Sasho Nikolov

1

Je pense que l'on peut étudier le calcul lambda sans jamais penser à la réduction et à la substitution en tant que calcul. Si j'ai raison et que c'est en fait possible, alors nous pouvons avoir un intérêt pour le calcul lambda même si le calcul ne nous intéresse pas du tout. Mais merci pour votre commentaire. J'essaierai de modifier ma réponse en conséquence dès que j'en aurai l'occasion.

Hunan Rostomyan

@SashoNikolov - "d'une manière qui ne soit pas englobée par les MT." Par définition, cela est impossible, car LC et TM sont équivalents. Tout ce que vous pouvez exprimer ou prouver avec l'un, vous pouvez le faire avec l'autre (et vice-versa). Ils se rendent donc mutuellement inutiles (comme ils le font tous les deux avec la théorie générale récursive, encore un autre formalisme équivalent à TM). Cela signifie-t-il que nous devrions éliminer tous les systèmes équivalents à la MT, à l'exception de la MT elle-même? Je ne dirais pas cela, car il est parfois plus facile d'exprimer en LC que TM ou inversement. C'est juste une autre façon de parler de calculabilité.

Gabriel L.

1

@ GabrielL. Si vous lisez toute la phrase, vous verrez "comment le calcul lambda élucide-t-il le concept de calcul de manière à ne pas être englobé par les MT". Deux définitions mathématiques formellement équivalentes peuvent encore élucider le même concept sous-jacent de manière différente et complémentaire. Mon commentaire signifiait qu'il était raisonnable de se demander quelle clarté est obtenue en exprimant la calculabilité en termes de calcul lambda, plutôt qu'en termes de MT. Ce n'est pas du tout une équivalence formelle.

Sasho Nikolov

Compris - réussi à passer à côté du mot clé. Merci pour la réponse.

Gabriel L.

12

Turing a fait valoir que les mathématiques peuvent être réduites à une combinaison de symboles de lecture / écriture, choisis parmi un ensemble fini, et à la commutation entre un nombre fini «d'états» mentaux. Il a réifié cela dans ses machines de Turing, où les symboles sont enregistrés dans des cellules sur une bande et un automate garde la trace de l'état.

Cependant, les machines de Turing ne sont pas une preuve constructive de cette réduction. Il a fait valoir que toute «procédure efficace» peut être mise en œuvre par une machine de Turing et a montré qu'une machine de Turing universelle pouvait implémenter toutes ces autres machines, mais il n'a en réalité pas indiqué de symboles, d'états ni de règles de mise à jour mettant en œuvre les mathématiques. de la manière dont il a discuté. En d'autres termes, il n'a pas proposé de "machine de Turing standard", avec un ensemble standard de symboles que nous pouvons utiliser pour écrire nos mathématiques.

Lambda Calcul, en revanche, est précisément cela. Church essayait spécifiquement d'unifier les notations utilisées pour écrire nos mathématiques. Une fois qu'il a été démontré que LC et TM sont équivalents, nous pourrions utiliser LC comme notre «machine de Turing standard» et tout le monde pourrait lire nos programmes (enfin, en théorie;)).

Maintenant, nous pourrions nous demander pourquoi traiter le LC comme un primitif plutôt que comme un dialecte de MT. La réponse est que la sémantique de LC est dénotationnelle : les termes de LC ont une signification «intrinsèque». Il y a des chiffres d'église, il y a des fonctions pour l'addition, la multiplication, la récursivité, etc. Cela rend LC très bien aligné sur la façon dont les mathématiques (formelles) sont pratiquées, c'est pourquoi de nombreux algorithmes (fonctionnels) sont toujours présentés directement dans LC.

Par contre, la sémantique des programmes de MT est opérationnelle : la signification est définie comme le comportement de la machine. En ce sens, nous ne pouvons pas couper une partie de la bande et dire "ceci est un ajout", car cela dépend du contexte. Le comportement de la machine, lorsqu'il frappe cette partie de la bande, dépend de l'état de la machine, des longueurs / décalages / etc. des arguments, combien de bande sera utilisée pour le résultat, si une opération précédente a corrompu cette section de bande, etc. Ceci est une façon de travail épouvantable ("Personne ne veut programmer une machine de Turing"), c'est pourquoi de nombreux algorithmes (impératifs) sont présentés sous forme de pseudocode.

Warbo
la source

5

les autres réponses sont bonnes, voici un angle / motif supplémentaire à considérer qui se confond avec d’autres tout en étant peut-être encore plus définitif, mais peut-être encore plus difficile à garder à l’esprit car les anciennes origines se perdent un peu dans le temps:

préséance historique!

Le lambda calcul a été introduit au moins dès 1932 dans la référence suivante:

A. Church, "Un ensemble de postulats pour le fondement de la logique", Annals of Mathematics, Series 2, 33: 346–366 (1932).

La machine de Turing a été introduite vers 1936. Lambda Calculus est donc bien antérieure à l’apparition de la TM de plusieurs années!

Turing, AM (1936). "Sur des nombres calculables, avec une application au problème d'Entscheidungs". Actes de la London Mathematical Society. 2 (1937) 42: 230-265. doi: 10.1112 / plms / s2-42.1.230

Donc, en d'autres termes, une réponse fondamentale est que Lambda Calculus est à bien des égards le système hérité ultime du TCS. Il est toujours dans les mêmes termes que Cobol, même si peu de nouveaux développements se produisent dans la langue! il semble que le système de calcul Turing Complete le plus récent ait été introduit et soit même antérieur à l’idée fondamentale de Turing Completeness. ce n’est que plus tard une analyse rétrospective qui a montré que le calcul lambda, les machines de Turing et le problème de correspondance après correspondance étaient équivalents et a introduit le concept d’équivalence de Turing et la thèse de Church-Turing .

Le calcul lambda est simplement le moyen d'étudier le calcul à partir d'un pov centré sur la logique en termes de représentation sous forme de théorèmes mathématiques et de dérivations de formules logiques, etc. il montre également la relation profonde entre l'informatique et la récursivité et le couplage plus étroit avec l'induction mathématique .

c’est un fait assez remarquable car il suggère que, à bien des égards, les origines (au moins théoriques ) de l’informatique étaient essentiellement logiques / mathématiques , thèse développée par Davis dans son ouvrage Engines of Logic / Mathematicians et les origines de l'ordinateur . (Bien entendu, les origines et le rôle fondamental de l’algèbre booléenne renforcent également ce cadre historique conceptuel.)

de manière dramatique, on pourrait même dire que le calcul lambda est un peu une machine à remonter le temps pédagogique pour explorer les origines de l'informatique!

vzn
la source

1

En outre, le calcul lambda semble également avoir été fortement influencé par Principia mathematica de Whitehead / Russell, qui a également été une inspiration majeure pour Godels thm . Une partie de cette recherche est également inspirée par le dixième problème de Hilberts au tournant du siècle, qui demandait une solution algorithmique avant que "algorithme" ne soit précisément défini (mathématiquement), et en fait cette quête est en grande partie ce qui a conduit à la définition technique précise.

vzn

btw / clarification / iiuc c'était en fait des systèmes post canoniques qui ont été étudiés en premier par Post et apparemment, le plus simple problème de Post Correspondance est un cas particulier. Kleene a également joué un rôle déterminant dans le développement du concept de complétude de Turing (ce qui n’a pas été dit sous ce nom) en aidant à prouver que les 3 systèmes principaux sont interchangeables / équivalents (TM, Lambda Calculus, système post-canonique).

vzn

voir aussi wikipedia sur l’ histoire de l’Eglise-Turing qui retrace de nombreux détails historiques / corrélations

vzn

4

J'ai du mal à ne pas être offensé par la comparaison Cobol.

Neil Toronto

-2

Je viens de tomber sur ce message et malgré le fait que mon message soit plutôt tard dans la journée (année!), Je pensais que peut-être mon "centime" pourrait être utile.

En étudiant le sujet à l'université, j'avais une pensée similaire à ce sujet; alors, j'ai posé la question du "pourquoi" au conférencier et la réponse a été: "compilateurs". Dès qu'elle en a parlé, le pouvoir derrière la réduction et l'art d'évaluer la meilleure façon de la manipuler ont soudain rendu tout son objectif: pourquoi il était et reste un outil potentiellement utile.

Eh bien, c’était pour ainsi dire mon moment "aha".

À mon avis, nous considérons souvent les langages de haut niveau, les modèles, les automates, la complexité des algorithmes, etc. utiles, car nous pouvons les associer à la "tâche" en cours; alors que lamdba calculus semble un peu trop abstrait. Cependant, il y a encore des personnes qui travaillent avec des langues de faible niveau - et j'imagine que le lambda calcul, le calcul d'objet et d'autres formalisations connexes les ont aidés à comprendre et peut-être développer de nouvelles théories et technologies dont le programmeur moyen peut ensuite bénéficier. En fait, ce n’est probablement pas un module de base pour cette raison, mais (pour les raisons que j’ai énoncées), il ne restera que quelques rares personnes - autres que les universitaires - qui le trouveront peut-être au cœur de leur choix de carrière en informatique.

utilisateur30412
la source

Quel était le "aha" sur les compilateurs ?

PhD

Votre dernier paragraphe semble entièrement spéculatif et vous n’expliquez jamais réellement pourquoi le mot "compilateurs" répond à la question.

David Richerby

@PhD: La bêta-réduction et la substitution ne sont pas utilisées lors de l'exécution de programmes, mais sont utilisées dans l'optimisation des compilateurs. Ce n'est pas la principale importance du lambda-calcul, mais c'est une application très concrète.

Blaisorblade

Quelle est la contribution du lambda calcul au domaine de la théorie du calcul?

Réponses: