Le calcul lambda ne semblait pas abstrait. Et je ne vois pas l'intérêt

18

La question sous-jacente:

Que fait le calcul lambda pour nous que nous ne pouvons pas faire avec les propriétés de fonction de base et la notation généralement apprises en algèbre de collège?

Tout d'abord, que signifie l'abstrait dans le contexte du lambda calcul? Ma compréhension du mot abstrait est quelque chose qui est dissocié de la machinerie, le résumé conceptuel d'un concept.

Cependant, les fonctions lambda, en supprimant les noms de fonction, empêchent un certain niveau d'abstraction. Par exemple:

f(x) = x + 2
h(x, y) = x + 5 y

Mais même sans définir le mécanisme de ces fonctions, on peut facilement parler de leur composition. Par exemple:

1. h(x, y) . f(x) . f(x) . h(x, y) or 
2. h . f . f . h

Nous pouvons inclure les arguments si nous voulons, ou nous pouvons résumer complètement pour donner un aperçu de ce qui se passe. Et nous pouvons rapidement les réduire à une seule fonction. Regardons la composition 2. Je peux avoir des couches de détails avec lesquelles je peux écrire en fonction de mon accent:

g = h . f . f . h
g(x, y) = h(x, y) . f(x) . f(x) . h(x, y)
g(x, y) = h . f . f . h = x + 10 y + 4

Réalisons ce qui précède avec lambda calcul, ou au moins définissons les fonctions. Je ne suis pas sûr que ce soit vrai, mais je crois que les première et deuxième expressions augmentent de 2.

(λuv.u(u(uv)))(λwyx.y(wyx))x

Et à multiplier par 5 ans.

(λz.y(5z))

Plutôt que d'être abstrait, cela semble entrer dans le mécanisme même de ce que cela signifie d'ajouter, de multiplier, etc. L'abstraction, à mon avis, signifie un niveau supérieur plutôt qu'un niveau inférieur.

De plus, j'ai du mal à voir pourquoi le calcul lambda est même une chose. Quel est l'avantage de

(λuv.u(u(uv)))(λwyx.y(wyx))x

plus de

h(x) = x + 5 y

ou une notation combinée

Hxy.x+5y

ou même la notation de Haskell

h x y = x + 5 * y

Encore une fois, que fait le calcul lambda pour nous que nous ne pouvons pas faire avec les propriétés et la notation de la fonction de style f (x) que beaucoup connaissent.

lambda-calculus programming-paradigms JDG
la source

9

C'est drôle que vous donniez un exemple de Haskell, car Haskell est basé sur le calcul lambda. Le calcul lambda ne concerne pas une notation particulière. C'est un modèle informatique, équivalent aux machines de Turing, dans lequel "tout est fonction".

Yuval Filmus

2

Oui, on me dit que c'est basé sur le calcul lambda. La question à laquelle je n'ai pas encore trouvé de réponse d'une manière qui me semble logique est pourquoi haskell est basé sur le calcul lambda par opposition à juste. . . les attributs de base des fonctions que j'ai apprises à l'école primaire. C'est vraiment l'essentiel de toute cette question.

JDG

6

N'est-ce pas «aucun but qui vient immédiatement à l'esprit» presque la définition de «abstrait»? :-)

David Richerby

1

Je ne dirais pas que c'est désobligeant. Ce traitement des fonctions est utilisable par le calcul. Mais je peux voir comment être qualifié de collège pourrait ainsi être interprété. Je vais l'ajuster.

JDG

6

Je doute que vous ayez réellement une définition formelle de "notation de fonction d'algèbre de collège". Si vous avez une définition pour de telles fonctions, c'est probablement celle de la théorie des ensembles qui n'a pas de signification informatique. Une partie de l'intérêt du calcul lambda est de comprendre une telle notation selon ses propres termes et, oserais-je le dire, abstraite d'applications particulières comme les fonctions polynomiales ou le calcul.

Derek Elkins a quitté le SE

24

Il existe de nombreuses raisons pour lesquelles le calcul lambda est si important.

Une raison très importante est que le calcul lambda nous permet d'avoir un modèle de calcul dans lequel les fonctions calculables sont des citoyens de première classe.

On ne peut pas exprimer des fonctions d'ordre supérieur dans le langage de l'algèbre du collège.

Prenons comme exemple l'expression lambda

λ f . λ g . λ x . f (g (x))

$\lambda f. \lambda g. \lambda x. f(g(x))$

Cette expression simple nous montre que, dans le calcul lambda, la composition des fonctions est elle-même une fonction. En algèbre de collège, cela ne s'exprime pas facilement.

Dans le calcul lambda, il est très facile d'exprimer qu'une fonction retournera une fonction comme résultat.

Voici un petit exemple. L'expression (où je suppose ici un calcul lambda appliqué avec addition et constantes entières)

(λ f . λ g . λ x . f ((g (x))) (λ x . x + 2)

$(\lambda f. \lambda g. \lambda x. f((g(x)))(\lambda x. x+2)$

se réduira à

λ g . λ x . g (x) + 2

$\lambda g. \lambda x. g(x)+2$

Notez également que dans le calcul lambda, les fonctions sont des expressions et non des définitions de la forme . Cela nous libère de la nécessité de nommer des fonctions et de distinguer entre une catégorie syntaxique d'expressions et une catégorie syntaxique de définitions. $f(x) = e$

De plus, lorsqu'il devient impossible (ou simplement encombrant sur le plan de la notation) d'exprimer des fonctions d'ordre supérieur, il sera également difficile d'affecter des types à des expressions.

La composition des fonctions est de type polymorphe

\forall α . \forall β . \forall γ . (β \to γ) \to ((α \to β) \to γ)

$\forall \alpha.\forall \beta. \forall \gamma. (\beta \rightarrow \gamma) \rightarrow ((\alpha \rightarrow \beta) \rightarrow \gamma)$

dans le système de type Hindley-Milner.

Un argument de vente très fort pour le calcul lambda est la notion précise de calcul lambda typé . Les différents systèmes de types pour les langages de programmation fonctionnels tels que Haskell et la famille ML sont basés sur des systèmes de types pour les calculs lambda, et ces systèmes de types fournissent de fortes garanties sous la forme de théorèmes mathématiques:

Si un programme est bien typé et réduit au résiduel , alors sera également bien typé. $e$ $e$ $e'$ $e'$

Et si est bien tapé, ne présentera pas certaines erreurs. $e$ $e$

Les preuves comme correspondance de programmes sont particulièrement remarquables. L'isomorphisme de Curry-Howard (voir par exemple https://www.rocq.inria.fr/semdoc/Presentations/20150217_PierreMariePedrot.pdf ) montre qu'il existe une correspondance très précise entre le calcul lambda simplement tapé et la logique propositionnelle intuitionniste: pour chaque type correspond une formule logique . Une preuve de correspond à un terme lambda de type , et une bêta-réduction de ce terme correspond à effectuer une élimination de coupure dans la preuve. $T$ $\phi_T$ $\phi_T$ $T$

J'exhorte ceux qui pensent que l'algèbre du collège est une bonne alternative au calcul lambda à développer un compte rendu de l'algèbre du collège de type polymorphe d'ordre supérieur avec une notion appropriée d'isomorphisme de Curry-Howard. Si vous pouvez même élaborer un assistant de preuve interactif basé sur l'algèbre du collège qui nous permettrait de prouver les nombreux théorèmes formalisés à l'aide d'assistants de preuve basés sur le calcul lambda tels que Coq et Isabelle, ce serait encore mieux. Je commencerais alors à utiliser l'algèbre du collège, et donc, j'en suis sûr, j'en ferais beaucoup d'autres avec moi.

Hans Hüttel
la source

C'est une excellente explication. Il est utile d'entendre que les fonctions d'ordre supérieur (comme la composition) et le typage sont mieux représentés dans le calcul lambda est encourageant, d'autant plus que cela facilite les preuves et le code prouvable. Je ne vois pas les ramifications de beaucoup de ce que vous avez mentionné et pourquoi la notation traditionnelle est inadéquate (par exemple, ne pas avoir besoin d'une syntaxe de définition séparée f (x) = e), mais il est utile que vous ayez nommé certaines de ces raisons et il donne une idée des domaines qui sont améliorés par le calcul lambda.

JDG

On peut bien sûr introduire des définitions locales de la forme

mais ceux-ci peuvent déjà être exprimés dans la syntaxe du calcul lambda comme

. Le calcul lambda nous permet d'exprimer des fonctions sans avoir à les nommer, tout comme on peut (en algèbre de collège!) Parler du nombre

sans avoir à les nommer par quelque variable.

let x = e^{'} in e

$\texttt{let}\; x = e' \; \text{in}\; e$

(λ x . e) e^{'}

$(\lambda x.e)e'$

4

$4$

Hans Hüttel

5

Lorsque les fonctions sont décrites pour la première fois aux jeunes, elles sont essentiellement identifiées par des graphiques (graphiques), ou peut-être par des formules; c'est ainsi que les fonctions étaient comprises historiquement avant l'avènement des tendances formalistes en mathématiques. De nos jours , les fonctions, comme cela est enseigné dans le premier calcul de l' année, sont des fonctions réelles, qui est, les fonctions de à . $\mathbb{R}$ $\mathbb{R}$

Les fonctions du calcul lambda sont beaucoup plus générales. La définition exacte dépend de si votre calcul lambda est tapé ou non. Dans le calcul lambda pur non typé, tout est fonction. C'est beaucoup plus général que les fonctions réelles du calcul.

Même les langages procéduraux utilisent parfois des idées du calcul lambda. La fonction de tri en C accepte comme paramètre une fonction de comparaison , qu'elle utilise pour comparer des éléments. Le calcul lambda va beaucoup plus loin - les fonctions acceptent non seulement les fonctions comme entrées, mais peuvent également les produire.

Le calcul lambda est un modèle de calcul équivalent en puissance aux machines de Turing. C'est un système complet en soi. Le calcul lambda pur n'a pas "5" ou "+" comme termes primitifs - ils peuvent être définis à l'intérieur du calcul, tout comme "5" et "+" ne sont pas des primitives de la théorie des ensembles. (Les langages de programmation pratiques implémentent nativement les nombres naturels pour des raisons d'efficacité.)

Je soupçonne que l'une des raisons pour lesquelles vous n'êtes pas impressionné par le calcul lambda est que ses idées ont tellement imprégné le discours de programmation qu'il ne semble plus innovant.

Yuval Filmus
la source

"Je soupçonne que l'une des raisons pour lesquelles vous n'êtes pas impressionné par le calcul lambda" Therin se trouve la question que je pose: Que fait le calcul lambda pour nous? En d'autres termes, lorsque nous n'utilisons pas le calcul lambda, que se passe-t-il? Lorsque nous utilisons le calcul lambda, que gagnons-nous? Si le calcul lambda était la première fois que les gens pensaient, et si les fonctions pouvaient elles-mêmes créer des fonctions, est-ce impressionnant? Parmi mes programmes python initiaux, j'ai fait du texte contenant des fonctions que j'ai évaluées plus tard, un peu comme déléguer la tâche de prise de décision à une autre personne. Semble évident?

JDG

c'était avant que je sache beaucoup de choses. Je pensais simplement que le code était ennuyeux à taper encore et encore et que la programmation devrait m'aider à générer automatiquement des fonctionnalités, y compris les fonctions elles-mêmes.

JDG

2

Python prend en charge la programmation fonctionnelle. Les premiers langages de programmation ne l'ont pas fait. Si vous aviez programmé dans FORTRAN, vous n'auriez pas créé de programmes avec du texte contenant des fonctions que vous avez évaluées ultérieurement. Sans même le remarquer, vous avez utilisé les capacités fournies par les idées du calcul lambda.

Yuval Filmus

2

Eval est originaire de LISP , qui a été fortement influencé par le calcul lambda. Quelque chose comme ça n'est pas possible dans FORTRAN, C, COBOL et de nombreux autres langages de programmation.

Yuval Filmus

Oui, python prend en charge la programmation fonctionnelle --- mais je ne suis pas sûr que sa capacité eval () ait été inspirée par λCalc --- vous ne pensez pas à λCalc: je veux générer automatiquement du code que je pourrai évaluer plus tard. C'est comme dire que λCalc doit penser: «Je vais dire à Miranda d'utiliser son meilleur jugement sur la façon de gérer son département» --- en d'autres termes, obtenir une fonction pour générer ses propres fonctions. Vous n'avez pas besoin de λCalc pour penser à déléguer des tâches de haut niveau. Si vous voulez parler de l'inspiration de λCalc, il est plus approprié de parler des fonctions lambda, des compréhensions, etc.

JDG

4

$x^2$ $x$ $x^2$

$\lambda x.x^2$ $x^2$

$f$ $f(x) = x^2$ $f$

L'utilisation d'expressions lambda dans les langages de programmation présente un avantage similaire; vous pouvez écrire ce que fait la fonction là où elle est nécessaire plutôt que d'avoir à définir une toute nouvelle fonction ailleurs dans votre programme.

$\frac{d}{dx} x^2$ $\frac{d}{dx}$ $x^2$

$\theta : V \to V^{**}$

θ (v) (f) = f (v)

$\theta(v)(f) = f(v)$

Beaucoup de gens trouvent cette notation à double évaluation déroutante et / ou troublante, ainsi que cette utilisation récursive de la définition ponctuelle d'une fonction. La version abstraction lambda

θ = λ v . λ f . f (v)

$\theta = \lambda v . \lambda f . f(v)$

n'a pas ce problème.

Enfin, il existe un théorème de non-sens abstrait selon lequel "le calcul lambda simplement tapé" est fondamentalement la même chose que la "catégorie fermée cartésienne" - donc si jamais vous vous retrouvez à vouloir faire un calcul dans une catégorie fermée cartésienne, c'est probablement une bonne idée d'utiliser il suffit de taper lambda calculus pour le faire.

la source

Je reviens à cette question et je trouve cette réponse excellente. Je vous remercie. Les réponses ici en général sont vraiment intéressantes.

JDG

4

Je dirai d'emblée que je ne suis pas un expert sur ce sujet, mais je viens de passer un peu de temps à l'étudier et l'une des choses les plus fascinantes pour moi dans n'importe quel sujet est l'histoire derrière. Donc, pour moi, comprendre un peu l'histoire derrière le calcul lambda aide à expliquer pourquoi il est utile.

Le bref résumé est qu'au début des années 1900 après la théorie des ensembles a commencé à décoller et en mathématiques a été re-Envisagé basée sur des ensembles, certains mathématiciens ont remarqué que si une théorie des ensembles définition permet d'affirmer qu'une certaine structure réelle , ils ne pas vous dire comment pour le construire et le calculer. Les définitions de la théorie des ensembles ne sont donc pas constructives . Mathématiciens commença à se demander s'il y avait un moyen de développer constructives définitions qui vont au - delà prouver que quelque chose est et au lieu de prouver comment c'est .

De Wikipédia :

En mathématiques, une preuve constructive est une méthode de preuve qui démontre l'existence d'un objet mathématique en créant ou en fournissant une méthode pour créer l'objet. Cela contraste avec une preuve non constructive (également connue sous le nom de preuve d'existence ou théorème d'existence pure) qui prouve l'existence d'un type particulier d'objet sans fournir d'exemple.

$*$ qui ont été adoptés dans des expressions régulières, et il y avait quelqu'un d'autre (je ne m'en souviens pas au hasard) qui a développé une autre méthode. Tous ces éléments ont été développés dans le but de construire un système mathématique sur une base qui permettrait des définitions constructives dès le départ.

Il a ensuite été démontré que le calcul lambda et la machine de Turing pouvaient tous deux représenter n'importe quelle fonction calculable et sont donc équivalents.

En théorie, tout fonction ou concept mathématique peut être codé sous forme de calcul lambda et calculé. Cela signifie que le calcul lambda peut être une base complètement distincte pour les mathématiques, bien qu'évidemment extrêmement fastidieuse.

Le calcul lambda n'est pas "utile" dans le sens où vous n'écrirez pas de code en l'utilisant, mais il constitue la base de la sémantique dénotationnelle qui est utilisée pour décrire les programmes et leurs effets dynamiques. Ceci est utilisé dans les discussions sur l'exactitude du programme et la signification sémantique. Il a aussi évidemment fortement influencé le développement des langages de programmation fonctionnels, qui tirent tout leur concept d'exécution du calcul lambda.

J'espère que cela pourra aider.

Modifier pour ajouter: je viens de signaler cet article montrant la relation entre la topologie, le calcul lambda et la physique. Le survolant brièvement, je suis tombé sur cette déclaration fantastique:

Alors qu'une machine de Turing peut être considérée comme un modèle simplifié et idéalisé de matériel informatique , le calcul lambda ressemble plus à un simple modèle de logiciel . ... Poétiquement parlant, le lambda calcul décrit un univers où tout est programme et tout est donnée: les programmes sont données .

Le fait est que le calcul lambda est un modèle idéalisé de calcul logiciel et, en tant que tel, n'est lié à une implémentation particulière dans aucun langage de programmation. Il modélise le calcul pur .

Dave
la source

Pour en savoir plus sur l'histoire: Brève histoire du λ-calcul à la Stanford Encyclopedia of Philosophy. Ils ont plus d'entrées que l'on ne peut traiter dans une vie.

David Tonhofer

3

$\lambda$

Aristu
la source

3

Le calcul lambda n'a pas été conçu pour être un langage de programmation. En effet, il a été créé dans les années 1930, des décennies avant même que nous ayons des ordinateurs programmables. Il a plutôt été créé comme un modèle formel pour étudier le calcul lui-même. Si vous êtes déçu de la facilité avec laquelle il exprime le code ou les fonctions mathématiques, c'est parce que ce n'est pas à cela qu'il sert.

Andrew
la source

1

"des décennies avant même d'avoir des ordinateurs programmables" - faux. L'ordinateur programmable existait avant (sinon peut-être des ordinateurs universels) et les premiers ordinateurs universels ont été construits dans les années 1930.

Raphael

-2

Le calcul lambda existe pour que des fonctions anonymes (aka lambda) puissent être créées. Si vous ne supprimez pas les noms de fonctions, l'espace de noms peut être encombré et on peut manquer de noms de fonctions disponibles. Ceci est particulièrement important lorsqu'il s'agit de «fonctions d'ordre supérieur» qui renvoient des fonctions (ou des pointeurs de fonction) pour des raisons évidentes.

Essentiellement, les fonctions lambda sont équivalentes aux variables de portée locale. La programmation fonctionnelle sans fonctions lambda est analogue à la programmation procédurale sans aucune variable locale, c'est-à-dire une idée terrible.

"pourquoi le calcul lambda est même une chose" les mathématiciens aiment la redondance. le calcul lambda est rarement utilisé en mathématiques car, comme vous l'avez découvert, la notation n'est pas très utile.

«Si vous pouvez même élaborer un assistant de preuve interactif basé sur l'algèbre du collège qui nous permettrait de prouver les nombreux théorèmes formalisés à l'aide d'assistants de preuve basés sur le calcul lambda tels que Coq et Isabelle, ce serait encore mieux. puis commencer à utiliser l'algèbre du collège, et donc, j'en suis sûr, j'en ferais beaucoup d'autres avec moi. Avez-vous entendu parler de métamath? Aucun calcul lambda impliqué ici, ne peut prouver la plupart des théorèmes coq / isabelle

sn
la source

Mis à part certaines opinions, que propose cette réponse?

Raphael

@Raphael désinformation. La plupart de cette réponse n'a même pas de sens. Les noms ne manquent pas. Les "fonctions lambda" ne sont pas équivalentes aux variables de portée locale; cela n'a même pas de sens. Je suppose que cela est censé faire référence let, mais bien qu'il letpuisse être encodé avec des fonctions anonymes, vous ne pouvez clairement pas aller dans l'autre sens. La programmation fonctionnelle ne nécessite pas de "fonctions lambda", par exemple FP ou Sisal de Backus .

Derek Elkins a quitté le SE

la plupart du temps je voulais poster un commentaire à la réponse de hans mais je n'avais pas assez de karma. j'ai donc décidé de transformer le commentaire en une réponse à part entière

sn

Le calcul lambda ne semblait pas abstrait. Et je ne vois pas l'intérêt

Réponses: