Je commence ma première année (au collège) en informatique l'année prochaine et j'écris surtout en C (si c'est important). J'ai essayé de chercher mais la plupart de ce que je trouve suppose une connaissance du calcul lambda. Pourquoi le calcul lambda est-il considéré comme beaucoup plus utile que le calcul à variable unique dans la programmation? Existe-t-il une relation entre les expressions lambda et les programmes fonctionnels? Est-ce le travail d'Alonzo Church sur le lambda calcul qui a influencé le développement des langages de programmation?
Tout le monde en dehors de l'école continue de bourdonner à ce sujet et je n'ai aucune idée de ce dont ils parleront même si j'ai hâte de l'apprendre et de voir comment cela se rapporte directement à ma programmation et à ma compréhension des langages de programmation.
la source
Réponses:
Le Lambda Calculus est intéressant, élégant et facilite beaucoup la compréhension des langages de programmation fonctionnels. Cependant, vous ne rencontrerez pas le LC dans un cours de baccalauréat CS typique, donc vous n'avez pas à l'apprendre maintenant - je recommanderais d'expérimenter avec les langages fonctionnels avant de revoir le Lambda Calculus. Je crois qu'OCaml est un bon point de départ dans la programmation fonctionnelle pour un programmeur C, et que Scheme est un bon point de départ pour plonger dans le Lambda Calculus.
Le Lambda Calculus n'est pas associé au Calculus (qui devrait plutôt s'appeler Analysis). En général, un calcul est un «système formel», c'est-à-dire un ensemble de règles pour faire quelque chose. Alors que le calcul différentiel fournit des règles concernant le changement de valeurs, les règles du calcul lambda décrivent le calcul lui-même. À partir de cet ensemble de règles très basiques, nous pouvons construire des calculs arbitraires, des représentations de données telles que des booléens, des entiers ou des listes, et même contrôler des constructions de flux telles que des conditionnelles ou des boucles. Le LC est équivalent aux machines de Turing, mais les deux modèles ont des forces différentes.
Lambda Calculus a eu un impact immense sur les langages de programmation. Le deuxième langage de haut niveau à implémenter était Lisp, qui peut être compris comme un encodage direct du LC dans un langage de programmation. Cette «programmation fonctionnelle» a un effet immense sur l'évolution des langages de programmation. Des fonctionnalités telles que les fonctions anonymes, les pointeurs de fonction, les fermetures (fonctions imbriquées), la récupération de place, la portée variable, la métaprogrammation, les avancées dans les systèmes de type, l'inférence de type, les langages interprétés, les langages à typage dynamique, la programmation orientée objet sont tous dus en grande partie à la branche de programmation fonctionnelle des langages de programmation. Il y a une blague que tout nouveau langage de programmation (non académique) n'ajoute que des fonctionnalités que Lisp possède déjà depuis des décennies.
Au-delà de cela, le Lambda Calculus et d'autres calculs connexes sont des outils indispensables dans la théorie du langage de programmation et dans certaines techniques de construction de compilateurs.
Tout langage qui a des fonctions anonymes qui se comportent comme des fermetures et peuvent être transmises librement contient immédiatement un codage du calcul lambda. Les fonctions anonymes correspondent à des expressions lambda, sauf que dans les fonctions LC ont toujours exactement un argument. Cependant, n'importe quel langage Turing-complete est équivalent au LC, donc le LC peut toujours être implémenté au-dessus de ces langages. Cela a tendance à se produire dans des systèmes de correspondance de règles ou dans des formats de configuration trop intelligents, donnant lieu à la «dixième règle de Greenspun» (en plaisantant - principalement): « Tout programme C ou Fortran suffisamment compliqué contient un ad hoc, spécifié de manière informelle, rempli de bogues , implémentation lente de la moitié de Common Lisp. "
la source
x = fn (a, b, c) => a + b + c
(typeint * int * int -> int
, invocationfn (1, 2, 3)
) peut être transformé enx = fn a => fn b => fn c => a + b + c
(typeint -> int -> int -> int
, invocation((x 1) 2) 3
- parens facultatif en ML). Maintenant, au lieu de fournir les trois arguments, nous pouvons également n'en fournir que deux:plus3 = x 1 2
qui a du typeint -> int
. Il s'agit d'une application / curry partielle.Le calcul lambda n'a rien à voir avec le calcul différentiel / intégral. Le calcul dans le sens le plus générique du mot signifie simplement un système de calcul.
À un niveau très élevé, le calcul lambda est un modèle de calcul de la même manière qu'une machine de Turing est un modèle de calcul. La raison pour laquelle les chercheurs en langage de programmation étudient le calcul lambda est que, en tant que modèle, il a des liens étroits avec des méthodes formelles en mathématiques comme la logique et la théorie des catégories. Ainsi, les méthodes de ces domaines peuvent être appliquées à l'étude de divers aspects et extensions du calcul lambda qui, à leur tour, aide à concevoir de meilleurs langages de programmation avec certaines propriétés.
L'influence la plus directe du calcul lambda dans les langages de programmation apparaît généralement sous la forme de fonctions et de fermetures de première classe. C ne prend pas en charge les fermetures et vous devrez donc explorer le concept dans un langage de plus haut niveau comme Lisp, Python, Ruby, JavaScript, etc. Historiquement, Lisp est considéré comme la première implémentation concrète du lambda calcul en tant que langage de programmation. .
la source