Application pratique du calcul SKI et BCKW

Question

Je peux comprendre comment créer et penser à ski et calcul BCKW, mais je ne suis jamais en mesure de trouver des utilisations pratiques. Peut-être que je ne cherche pas assez profondément? Autrement dit, je me demande si (un exemple seulement s'il vous plaît, je ne veux pas dire cela est vrai) utiliser Java Servlets S largement et générateurs Python sont un exemple de BCW et je suis tout simplement incapable de voir à travers la forêt des arbres?

Answer 1

Dans Haskell, ils sont partout !

• B est-<$>
• C est-flip
• K est-pure
• I est-id
• S est-<*>
• W est-join

D'un point de vue Haskell, des moyens de <$> "font dans un contexte".

• moyens de (+2) <$> (*3) ajouter deux après avoir multiplié par trois .
• des moyens de (+2) <$> [1,2,3] ajouter deux à chaque élément dans la liste .
• des moyens de (+2) <$> (read . getLine) ajouter deux à le numéro que je viens de lire .
• des moyens de (+2) <$> someParser ajouter deux à le numéro que je viens analysable .

Les choses qui ont un contexte sont appelés foncteurs . Tous vos Java / Python / C ++ itérateurs sont simplement étranges versions inside-out de foncteurs.

Une autre connexion: le S et K forment ensemble un combinateur Turing-complet. Dans Haskell, pure et <*> forment ensemble un foncteur applicatif.

Bien sûr, comprendre comment les autres combinateurs inscrivent dans l'apprentissage, il faudra Haskell. Mais cet exemple montre comment combinateurs sont tellement ancrées dans la langue.

Answer 2

Le ski et BCKW CALCULS se démarquer du calcul Lambda (qui a des applications bien connues dans concept de programmation fonctionnelle) parce qu'ils sont dans sous forme de point libre . Voir aussi programmation tacite . Ils forment la base de comprendre comment construire des programmes fonctionnels sans arguments nommés.

Nous voyons des applications de celui-ci dans certaines langues (par exemple Joy et Cat). Une fois, je sur Lambda-the-Ultimate.org posté sur la relation du calcul SK Cat et la joie.

Pour ce que ça vaut. BCKW et SKI (SK) ou lithiase sont pratiquement identiques, mais la base de BCKW est tombé en vogue

Answer 3

Bien que lambda et le calcul ski ne reflètent pas les systèmes d'entrée et de sortie de la plupart des langages de programmation (tels que les graphiques, les connexions réseau, ou même sans doute l'entrée standard et de sortie), la façon dont la programmation informatique pratique est structuré correspond à Lambda (et donc SKI et BCKW), comme l'idée de récursivité et un peu les fonctions de manière sont appelés. Beaucoup de ces langages de programmation ont des abstractions lambda pour une utilisation en tant que fonctions.

Answer 4

Il est question de contrôle.

Peut-être commencer à un niveau inférieur. Un système est juste un applicatif système où les objets peuvent être appliqués à d'autres objets. Un exemple simple d'un système est bash applicatif.     ls | plus On pourrait supposer qu'ils sont dans un certain environnement, et que les moyens ci-dessus font ls sur l'environnement, puis faire plus. Dans la notation est ce applicative     plus @ (ls @ environnement) Cependant, on pourrait faire des choses plus compliquées comme     ls | motif grep | plus Alors maintenant, en notation est ce applicative     plus @ ((grep @ motif) @ (ls @ environnement)). Avis grep @ modèle. Grep est appliquée à un modèle, qui redonne le programme pour correspondre à ce modèle dans le résultat de ls. Ceci est le point d'application, d'appliquer un programme d'arguments, mise en place de nouveaux programmes de programmes (aka BUILTIN) « atomiques ». Cependant, nous ne pouvons pas faire trop de programmation avec juste l'application primitive ou builtins. Nous avons besoin d'un moyen de structurer notre entrée et l'application de nos primitives à notre entrée.

est où lambda entre en jeu. L'utilisation d'un lambda peut généraliser la     (Motif grep @) Pour appliquer grep à une entrée,     (Grep @ X) Cependant, nous devons avoir un moyen d'obtenir l'entrée grep. Ainsi, nous utilisons habituellement des fonctions.     f (X) = X @ grep Le procédé ci-dessus est appelé abstraire sur l'argument. Mais il n'y a aucune raison de penser le nom f comme étant spécial, nous avons donc une syntaxe pour cela:     lambda X. grep @ X Puis lambda X. grep @ X, peut être appliquée à une entrée, et l'entrée sera remplacé dans le corps et évalué. Cependant, la substitution peut être gênant, les variables liées peuvent être gênants pour mettre en œuvre sur une machine. S-K-I (ou B, C, K, W) donne un moyen de faire des choses lambda sans substitution, et au lieu permutant juste des applications.

Pour rappel, l'application est ce qu'il est tout au sujet. Il est très pratique à la raison au niveau de l'application d'un programme à quelque chose (peut-être un autre programme). Lambda calcul donne un moyen de structurer l'entrée et à l'application des programmes aux arguments. SKI donne un moyen de faire lambda sans avoir à remplacer explicitement.

Il convient de noter que la réduction SKI est par nature paresseux, de sorte que certains il faudra peut-être fait dans une utilisation réelle du monde de ski à l'application de la structure. En effet, les arguments pourraient maintenant avoir été complètement évalué et peut être une application partielle aussi bien. On peut contourner ce avec une théorie de type et d'évaluer seulement un programme sur son entrée si le programme est dans la position de la tête de l'application. À savoir, si l'on écrit avec des termes lambda fermés, traduits Skier, puis si p @ arg1 @ .... Il devrait être le cas que si p est un programme primitif, puis la ré-écriture est terminée, et ainsi tous les arguments de celui-ci sont 1) disponibles, 2) une évaluation exhaustive. Cependant, je ne l'ai pas prouvé, et il pourrait ne pas être vrai avec une assez forte théorie de type ...