Quelle est l'origine et la signification de la phrase "Lambda the ultimate?"

43

Je bricole les langages de programmation fonctionnels depuis quelques années et je rencontre toujours cette phrase. Par exemple, il s’agit d’un chapitre de "The Little Schemer", qui précède certainement le blog sous ce nom. (Non, ce chapitre ne permet pas de répondre à ma question.)

Je comprends ce que signifie lambda, l’idée d’une fonction anonyme est à la fois simple et puissante, mais je ne comprends pas ce que «l’ultime» signifie dans ce contexte.

Lieux que j'ai vus cette phrase:

  1. Le titre du chapitre 8 de The Little Schemer
  2. Un blog: http://lambda-the-ultimate.org/
  3. Une série de documents "Lambda the ultimate X": http://library.readscheme.org/page1.html

J'ai l'impression qu'il me manque une référence ici, quelqu'un peut-il aider?

Eric Wilson
la source
1
On dirait que c'est le nom d'un blog populaire, mais s'il y a une autre source historique, ça m'intéresse ...
Klaim
1
Pouvez-vous fournir des références aux endroits où vous avez vu cette phrase? Ce contexte serait extrêmement utile pour trouver une réponse.
Adam Crossland
@Adam - a ajouté quelques références.
Eric Wilson
La série de publications redirige vers cultureua.com Quelqu'un peut-il fournir un lien mis à jour s'il vous plaît?
Tejasbubane

Réponses:

47

Oui, c’est tout simplement une phrase récurrente dans le titre de plusieurs articles, à partir d’un couple des années 70, dans laquelle Sussman et Steele démontrent l’utilisation du lambda calcul pour la programmation, au moyen d’un dialecte minimaliste appelé " Scheme " qu'ils ont conçu pour le but. Vous pouvez trouver les papiers eux-mêmes ici ; ils sont intéressants et étonnamment pertinents.

Je ne sais pas si cela est dit explicitement, mais il est clair (à partir du contexte, après avoir lu les documents et connaissant le contexte général et les intérêts de recherche des auteurs) que la phrase est simplement un slogan accrocheur pour leur affirmation que des abstractions lambda , en tant que primitif informatique, ne sont pas seulement universels au sens formel (être capable de coder n’importe quel programme de quelque manière que ce soit, même maladroits), mais universels au sens pratique que toute construction présente dans d’autres langues, même celles qui le sont. cuit à partir de la base, il peut être réimplémenté dans un langage à base de lambda d’une manière à la fois efficace et naturelle.

La phrase répétée mène à la forme généralisée évidente "pour tout X, lambda est le X ultime", ce qui est le sens que j'ai généralement donné à "Lambda the Ultimate" comme étant le nom du blog, notant que LtU s'intéresse au langage de programmation conception et théorie. Ironiquement, LtU serait probablement aussi l’un des meilleurs endroits pour trouver quelqu'un qui pourrait vous parler de quelque chose pour lequel lambda n’est pas l’implémentation ultime. :]

Notez également que Sussman est l’un des auteurs de SICP , un manuel très influent qui utilise également le langage Scheme et passe assez de temps à introduire le concept d’abstractions lambda.

CA McCann
la source
2
+1 pour localiser ces papiers classiques. Guy L. Steele, Jr. a également écrit le livre sur Common LISP . LISP et Scheme n'étaient pas la fin de la route pour Guy, qui a ensuite contribué à J , à la forteresse et à d'autres langues. Guy a également été impliqué dans le fichier de jargon et le dictionnaire des hackers .
John Tobler
@ John Tobler: Tout à fait! Je me suis concentré uniquement sur Sussman, car il semblait être plus impliqué dans Scheme, qui est profondément lié aux Lambda Papers. Je ne voulais pas donner l’impression que Steele n’avait rien fait d’autre, c’est loin d’être vrai. :]
CA McCann le
28

Lambda The Ultimate renvoie à l'idée que les lambdas du lambda-calcul peuvent implémenter efficacement chaque concept intégré dans tous les langages de programmation, passés, présents et futurs. Classes, Modules, Paquets, Objets, Méthodes, Flux de contrôle, Structures de données, Macros, Continuations, Coroutines, Générateurs, Compréhensions de liste, Flux, etc.

En l'occurrence, cette nature ultime implique de représenter une fonction anonyme. Mais les lambdas ne sont pas fondamentalement limités à des fonctions anonymes. On les enseigne de cette façon, mais l’essence de lambda est bien plus profonde que les fonctions mathématiques sans noms. En d'autres termes, je suis en désaccord avec:

Je comprends ce que signifie lambda, l’idée d’une fonction anonyme est à la fois simple et puissante, mais je ne comprends pas ce que «l’ultime» signifie dans ce contexte.

En pratique, l’utilisation de lambdas en tant qu’abstractions syntaxiques («macros»), qui ne sont pas appelées par valeur / applicatives (fonctions mathématiques utilisées), est absolument cruciale pour souscrire à l’idée que les lambdas peuvent réellement servir de base. noyau de chaque système de traitement de langage de programmation.

Pour la théorie: Il existe un lien intéressant entre le paradoxe de Bertrand Russell et les axiomes de la compréhension (et de l'extension) dans la théorie des ensembles naïve. Un lambda est aux fonctions ce que la notation de constructeur est à des ensembles: les lambdas sont des notations de constructeur de fonctions. Il existe une différence importante, généralement ignorée, entre (lambda (x) (* xx)) et ce à quoi elle correspond (la fonction qui met les carrés). Si l’on ne fait pas la distinction entre les deux en général, c’est-à-dire entre la notation et la dénotation (une erreur commise par Church et Frege), on a alors affaire à des paradoxes. Pour les décors et Frege, c'est le Barbier de Séville de Bertrand Russell qui illustre l'erreur. pour les fonctions et l'Eglise, c'est Halacle Oracle d'Alan Turing.

Notez que les paradoxes sont bons, pratiques. Nous voulons que EVAL soit exprimable, et nous voulons que lambdas signifie plus que des fonctions. Supposer que le contraire mène à la contradiction est le résultat souhaitable; c'est un bon test de bon sens: les lambdas ne peuvent être ultimes que s'ils n'expriment que de simples fonctions


Racket (anciennement PLT Scheme) continue de défendre l’idée que des langages de programmation pratiques peuvent vraiment être construits, à partir de la base, sur 'just lambda'.

Kernel , de Shutt, affirme que lambda n'est pas vraiment l'abstraction ultime. Il soutient qu'il existe un concept encore plus primitif (pour le grec, surnommé vau) que Sussman connaissait sous le nom de FEXPR.

Felleisin et compagnie (pour Racket) tirent une grande partie de la puissance de la vau de Shutt en utilisant le concept de phases , ou metalevels, qui correspond approximativement à l'exécution du code source à travers plusieurs étapes de la traduction (comme avec le prétraitement C, mais en utilisant le même langage à chaque fois). «étape» et les «étapes» ne sont pas en réalité totalement distinctes dans le temps). (Ainsi, ils soutiennent qu'un lambda dans une phase supérieure se rapproche suffisamment d'un vau.) En fait, ils affirment que les phases sont meilleures que les FEXPR, précisément parce qu'elles sont plus limitées; en bref, "les FEXPR sont trop puissants" (voir le travail de Wand, ce que Shutt soutient contre).

Le document 3-Lisp de Brian Smith, "Réflexion procédurale dans les langages de programmation", tente une reformulation rigoureuse de la théorie des langages de type LISP, en distinguant nettement les notations (symboles / langage / programmes) des dénotations (choses / références / valeurs / résultats). ) http://dspace.mit.edu/handle/1721.1/15961

"La théorie des FEXPRs est triviale" de Mitchell Wand envoie plus de clous dans le cercueil (temporaire?) Que Kent Pittman a créé pour les FEXPR (qui, comme Felleisen, soutient que les FEXPR rendent la compilation trop ardue).

Paul Graham affirme avec force et longuement dans "On Lisp" que le véritable pouvoir réside dans les lambdas en tant que transformateurs de syntaxe (macros), plutôt qu'en tant que transformateurs de valeurs (fonctions mathématiques). Le développement du lambda-calcul applicatif par Plotkin pourrait être considéré comme quelque peu contrasté, car Plotkin limite le calcul de Church à son sous-ensemble appel par valeur / applicatif. Bien entendu, la gestion efficace de la partie applicative est très importante. Il est donc important de développer une théorie spécialisée dans cette utilisation de lambda. (Plotkin et Graham ne se disputent pas.)

En fait, en général, la notion de Lambda en tant qu’ultime n’est qu’un de ces retournements dans le débat éternel entre efficacité et expressivité; c'est la position selon laquelle lambda est l'outil ultime de l'expressivité et, avec suffisamment d'études, s'avérera être également l'outil ultime de l'efficacité. En d’autres termes, nous pouvons, si nous le souhaitons, voir l’avenir des langages de programmation comme étant rien de plus, rien d’autre que l’étude de la manière de mettre efficacement en œuvre tous les fragments du calcul du lambda, qui présentent un intérêt pratique.

"Les 700 prochains langages de programmation" de Landin, http://www.cs.cmu.edu/~crary/819-f09/Landin66.pdf , est une référence accessible qui contribue au développement de ce concept selon lequel Lambda est Ultime.

William Cushing
la source
Sensationnel. Réponse digne d'une ovation. Tant d'indices à suivre.
hmijail
13

Je suppose que c'est simplement une référence à des articles écrits par Sussman et Steele entre 1975 et 1980 et intitulés:

  • Lambda: l'impératif ultime
  • Lambda: l'ultime déclaratif
  • Lambda: le nec plus ultra
  • LAMBDA: l'opcode ultime

Voir l'article de Wikipedia.

Trasplazio Garzuglio
la source