Quel type de calcul lambda serait Lisp vaguement un exemple?

Question

Je suis en train d'obtenir une meilleure adhérence sur la façon dont les types entrent en jeu dans le calcul lambda. Certes, beaucoup de choses de la théorie de type est sur ma tête. Lisp est un langage typé dynamiquement, qui serait correspond approximativement au calcul typées lambda? Ou est-il une sorte de « lambda-calcul typé dynamiquement » que je ne suis pas au courant de?

Answer 1

  

Lisp est un langage typé dynamiquement, serait que correspondent à peu près au calcul typées lambda?

Oui, mais seulement à peu près. Dans le « pur » calcul typées lambda, tout est codé comme fonctions. (Vous pouvez google pour le populaire « Eglise encoding » et moins populaire « Scott encodage ».) Lisp a des données non fonctionnelles, comme des atomes et des nombres et autres, donc cela compterait comme « calcul typées lambda étendu avec des constantes. »

Une autre différence importante est ordre d'évaluation . Règles pour la réduction des termes lambda-calcul sont très nondéterministe. (Il y a un théorème, le théorème de Church-Rosser, qui dit vaguement que, tant que les choses prennent fin, ordre d'évaluation n'a pas d'importance). Dans la pratique lambda termes sont généralement réduits en utilisant le plus à gauche-externe aka réduction « ordre normal » parce que si tous stratégie de réduction se termine, que l'on fait. Ceci est très différent de Lisp qui évalue toujours des arguments à la forme normale avant de faire une réduction de la bêta. Cette commande d'évaluation est appelée « appel en valeur ».

En résumé, Lisp correspond à un non typé, appel par la valeur lambda calcul étendu avec des constantes .

Answer 2

John McCarthy introduit LISP dans son Avril 1960 papier « Fonctions récursives des expressions symboliques et leur calcul par la machine, la partie I ". Le paragraphe suivant est de la page 6:

  

e. Fonctions et formulaires. Il est habituel en mathématiques - en dehors de la logique mathématique - d'utiliser le mot « fonction » et d'appliquer imprécisément à des formes   tel que y ² + x. Parce que nous verrons plus loin calculer avec des expressions pour les fonctions,   nous avons besoin d'une distinction entre les fonctions et les formes et une notation pour Express-   ing cette distinction. Cette distinction et une notation pour décrire, à partir   que nous écartons trivialement, est donnée par l'Église [3].   ...
  3. A. CHURCH, Le Calculi de Lambda-Conversion (Université de Princeton   Press, Princeton, N. J., 1941).

Le article de Wikipedia sur lambda-calcul a une histoire des publications de l'Église. Le document 1941 référencé par McCarthy semble être sur le typé lambda-calcul, en contradiction avec l'introduction de l'article de Wikipedia.

Le mot-clé dans lambda Lisp peut être compris de se référer au lambda-calcul que par analogie. A Lisp expression lambda est un type de fonction anonyme .

Answer 3

Lisp est pas « un calcul lambda », je ne sais pas ce que « un calcul lambda » est.

Si vous voulez identifier lambda par lithiase il système de type alors Lisp est son propre bien sûr. Le « lambda » mot-clé dans un Lisp avant Scheme est certainement prétentieux, et après le schéma, il y a de la place aussi dire qu'il est. Tout en utilisant « func » aurait été plus humble. Lisp est un processeur de liste principalement, pas un « calcul lambda »

J'ai aussi écrit un article assez vaste de cette fois que les tentatives de démontrer pourquoi A: le terme « programmation fonctionnelle » n'a pas de sens et B: pourquoi parler d'un « calcul lambda » plutôt que « un système de type » l'est aussi :

http://blog.nihilarchitect.net/archives/289/ sur-fonctionnelle programmation /

De plus, gardez à l'esprit que, dans Lisp, toutes les fonctions sont en effet seul argument et ne peut être avez listes que leurs arguments.