Je commence un cours de premier cycle en informatique à l'automne prochain, mais je ne peux pas vraiment comprendre le λ-calcul dans le contexte de la programmation fonctionnelle. Je peux mal interpréter cela complètement, mais basé sur cette définition de la Stanford Encyclopedia of Philosophy, c'est juste une autre notation pour les fonctions.
Si c'est juste que, pourquoi est - il avantageux d'utiliser λ-calcul sur les notations de la fonction habituelle pour calculer l' algorithme temps d'exécution?
Réponses:
En informatique, nous voulons analyser et comprendre le code source avec une rigueur mathématique. C'est la seule façon de prouver des propriétés intéressantes (telles que la terminaison) avec une certitude absolue. Pour cela, nous avons besoin d'un langage avec une signification très bien définie pour chaque construction.
En théorie, cela pourrait être n'importe quelle langue avec une bonne sémantique formelle . Mais pour rendre les choses moins compliquées et moins sujettes aux erreurs, il est préférable d'utiliser un langage aussi simple que possible mais toujours capable d'exprimer n'importe quel programme (c'est-à-dire que Turing est complet ). Pour raisonner sur le code impératif, il existe des machines de Turing . Mais pour raisonner sur la programmation fonctionnelle, il y a le -calculus.λ
Le -calculus de base est comme un langage de programmation fonctionnel, mais avec beaucoup de «bagages» sortis. Ce n'est pas important que ce soit un langage agréable pour écrire des programmes, ni que ce soit un langage efficace. Juste que c'est simple et expressif. Par exemple, nous n'avons pas besoin de boucles, car nous pouvons les simuler avec la récursivité. Et nous n'avons pas besoin de fonctions avec plusieurs paramètres, car nous pouvons les simuler avec Currying .λ
Maintenant, à un moment donné, vous voudrez peut-être prouver les propriétés des constructions qui ne font pas partie de la base ( ) -calculus. C'est pourquoi les informaticiens l'ont étendu dans différentes directions au fil des ans. Par exemple, pour raisonner sur les systèmes de type-il y a un grand nombre de variations de dactylographiée -calculi .λ λ
la source
étrangement, beaucoup de livres parlent du calcul sans mentionner Lisp ou Scheme , des langages de programmation modernes basés sur lui, laissant malheureusement aux étudiants l'idée que son ancien et abstrait et surtout théorique. étudier Lisp ou Scheme peut être un excellent angle pour aider énormément à comprendre calcul .λ λ
il y a de nombreux avantages à utiliser Lisp ou la programmation fonctionnelle et le calcul du temps d'exécution de l'algorithme n'est qu'une possibilité (bien qu'il serait utile si vous citez une référence pour cela). étant donné que son déjà en notation fonctionnelle, la détermination des formules de temps d'exécution via des relations d'induction ou de récurrence peut parfois avoir une relation plus forte ou plus évidente avec le code d'origine. d'autres types d'analyse de l'algorithme sont également simplifiés.
un autre avantage principal est la simplicité syntaxique. les analyseurs pour d'autres langues sont très complexes mais les analyseurs Lisp sont très simples. Lisp est donc un excellent langage pour étudier la théorie de l'analyse.
un autre aspect clé consiste à analyser les logiciels plus dans une optique / vue logique ou mathématique plutôt que dans une perspective «informatique».
comme le souligne l'autre réponse, Lisp est tout au sujet de la récursivité au lieu de l'itération et la récursivité est très au cœur de CS.
plus d' avocations pour une " -view" et des détails peuvent être trouvés dans [1], une référence gratuite en ligne et semi-célèbre.λ
[1] Structure et interprétation des programmes informatiques, par Abelson & Sussman
la source