À quoi sert le calcul du combinateur SKI (ou même le calcul lambda)? Quels sont quelques exemples concrets de son utilisation?

Je comprends ce que c'est, mais je ne vois pas à quoi ça sert les algorithmes ou quoi que ce soit. Peut-être que je manque quelque chose. J'ai besoin que quelqu'un me donne un exemple de la façon dont il peut être utilisé pour que je puisse mieux le comprendre.

algorithms lambda-calculus combinatory-logic Kenneth Onyebinachi
la source

Il existe plusieurs langages de programmation ésotériques basés sur la logique combinatoire, par exemple Unlambda . Voir aussi ici . Vous pouvez trouver plus d'informations en explorant les liens dans les articles.

Anton Trunov

Réponses:

L'application évidente du lambda calcul est tout langage de programmation fonctionnel (par exemple, Lisp, ML, Haskell) et tout langage qui prend en charge les fonctions anonymes.

En ce qui concerne le calcul combinatoire, doit-il y avoir une "application réelle"? Les machines de Turing, par exemple, ne sont presque jamais utilisées "dans le monde réel" mais elles constituent la base de la théorie du calcul. Une caractéristique utile des calculs combinatoires est qu'ils sont des systèmes plus simples que, par exemple, les machines de Turing. Si vous voulez prouver qu'un autre système est complet de Turing, il pourrait être plus facile de montrer comment il peut simuler des combinateurs que de montrer qu'il peut simuler une machine de Turing.

David Richerby
la source

Bien sûr, des combinateurs ont été utilisés dans la compilation de langages fonctionnels (mais pas le calcul SKI lui-même).

cody

@cody Veuillez poster une réponse à ce sujet! Ce n'est pas quelque chose que je connais donc je préfère ne pas modifier ma réponse.

David Richerby

Par exemple, le système de type de Scala s'est révélé être Turing-complet en y incorporant le SK-calcul. Je ne peux même pas commencer à imaginer la complexité absurde de l'intégration d'une machine de Turing (universelle). Ironiquement (étant donné le nom) la complétude de Turinf est rarement montrée avec les machines de Turing. SQL s'est avéré être TC en implémentant un système de balises cycliques, HTML + CSS avec la règle 101, l'Intel MMU en codant une instruction "Déplacer, Brancher si Zéro, Décrémenter".

Jörg W Mittag

@ JörgWMittag re: " HTML + CSS avec la règle 101 " vouliez-vous dire "la règle 110 "?

RBarryYoung

@RBarryYoung: Bien sûr, une faute de frappe stupide. Le code est ici: github.com/elitheeli/stupid-machines

Jörg W Mittag

J'ai trouvé SKI utile pour comprendre certains axiomes logiques.

Par exemple, une axiomatisation de style Hilbert de l'implication (intuitionniste) est

\begin{array}{l} (une \to b \to c) \to (une \to b) \to une \to c \\ une \to (b \to une) \end{array}

$\begin{array}{l} (a \rightarrow b \rightarrow c) \rightarrow (a \rightarrow b) \rightarrow a \rightarrow c \\ a \rightarrow (b \rightarrow a) \end{array}$

La première fois que j'ai vu ces axiomes, je me suis demandé pourquoi diable ils devraient fonctionner. Bien sûr, il est facile de vérifier qu'ils tiennent. Mais pourquoi cela suffirait-il, c'est-à-dire pourquoi l'utilisation de ces deux postulats seuls suffit à prouver (à travers le modus ponens) toutes les autres tautologies implicatives? Mystère ... ou est-ce?

Eh bien, il s'avère que chaque tautologie doit correspondre au type d'un terme lambda, grâce à l'isomorphisme de Curry-Howard. Mais ledit terme lambda peut être réécrit de manière équivalente en terme de combinateurs $S,K$ seul. Ainsi, les types de $S$ et $K$ doit générer, par application, les types de toute tautologie. Et en effet, les deux axiomes ci-dessus sont les types les plus généraux pour $S$ et $K$ .

chi
la source

Jetez un œil à LINQ (Language INtegrated Query) de Microsoft. Il fait un usage étendu et assez direct du calcul lambda pour manipuler et transformer les arbres d'expression. L'exemple le plus complet et sophistiqué serait probablement Linq2SQL (l'implémentation de SQL Server) qui effectue efficacement des transformations complexes qui séparent les parties de l'arborescence d'expressions qui peuvent être déléguées au serveur de base de données.

Ce n'est pas la première technologie qui permet des requêtes combinant des données provenant de plusieurs sources, mais c'est peut-être la première qui automatise le démêlage des dépendances pour tirer parti des capacités de manipulation en masse des serveurs de bases de données. Ce n'est pas parfait (parfois vous devez l'aider) mais il fonctionne très bien et avec une attention aux détails que vous n'obtiendrez pas des humains.

Lorsque vous ne devez l' aider à sortir, comprendre le calcul vous prendra un long chemin vers déterminer ce qui dérange - donc , en plus de quoi sert-il? voici votre réponse à Pourquoi dois-je apprendre cela quand les machines le feront pour moi?

Peter Wone
la source