¿Cuál es el propósito del cálculo combinador de SKI (o incluso cálculo lambda)? ¿Cuáles son algunos ejemplos de la vida real de su uso?

Entiendo lo que es, pero no veo cómo sirve para algoritmos ni nada. Tal vez me estoy perdiendo algo. Necesito que alguien me dé un ejemplo de cómo se puede usar para poder entenderlo mejor.

algorithms lambda-calculus combinatory-logic Kenneth Onyebinachi
fuente

Existen varios lenguajes de programación esotéricos basados en lógica combinatoria, por ejemplo, Unlambda . Ver también aquí . Puede encontrar más información explorando los enlaces en los artículos.

Anton Trunov

Respuestas:

La aplicación obvia del cálculo lambda es cualquier lenguaje de programación funcional (por ejemplo, Lisp, ML, Haskell) y cualquier lenguaje que admita funciones anónimas.

En cuanto al cálculo del combinador, ¿tiene que haber una "aplicación del mundo real"? Las máquinas de Turing, por ejemplo, casi nunca se usan "en el mundo real", pero forman la base de la teoría de la computación. Una característica útil de los cálculos del combinador es que son sistemas más simples que, por ejemplo, las máquinas de Turing. Si desea demostrar que algún otro sistema está completo de Turing, podría ser más fácil mostrar cómo puede simular combinadores que mostrar que puede simular una máquina de Turing.

David Richerby
fuente

Por supuesto, los combinadores se usaron en la compilación de lenguajes funcionales (aunque no el cálculo SKI en sí).

cody

@cody ¡Por favor publique una respuesta al respecto! No es algo que sepa, así que prefiero no editarlo en mi respuesta.

David Richerby

Por ejemplo, se ha demostrado que el sistema de tipos de Scala es completo de Turing al incrustar el cálculo SK en él. Ni siquiera puedo comenzar a imaginar la absurda complejidad de incrustar una máquina de Turing (universal). Irónicamente (dado el nombre), la integridad de Turinf rara vez se muestra con las máquinas de Turing. Se demostró que SQL era TC al implementar un Sistema de etiqueta cíclica, HTML + CSS con la Regla 101, la MMU Intel al codificar una instrucción "Mover, bifurcar si es cero, decrementar".

Jörg W Mittag

@ JörgWMittag re: " HTML + CSS con la Regla 101 " ¿quiso decir " Regla 110 "?

RBarryYoung

@RBarryYoung: Por supuesto, error tipográfico estúpido. El código está aquí: github.com/elitheeli/stupid-machines

Jörg W Mittag

Encontré SKI útil para comprender algunos axiomas lógicos.

Por ejemplo, una axiomatización al estilo de Hilbert de implicación (intuicionista) es

\begin{array}{l} (a \to b \to c) \to (a \to b) \to a \to c \\ a \to (b \to a) \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 primera vez que vi estos axiomas, me pregunté por qué demonios deberían funcionar. Claro, es fácil comprobar que aguantan. Pero, ¿por qué deberían ser suficientes, es decir, por qué usar estos dos postulados solo es suficiente para probar (a través de modus ponens) todas las demás tautologías de implicación? Misterio ... ¿o sí?

Bueno, resulta que cada tautología debe corresponder al tipo de término lambda, gracias al isomorfismo de Curry-Howard. Pero dicho término lambda puede reescribirse de manera equivalente en términos de combinadores $S,K$ solo. Entonces, los tipos de $S$ y $K$ debe generar, a través de la aplicación, los tipos de cualquier tautología. Y de hecho, los dos axiomas anteriores son los tipos más generales para $S$ y $K$ .

chi
fuente

Eche un vistazo a LINQ (consulta integrada en el idioma) de Microsoft. Hace un uso extenso y bastante directo del cálculo lambda para manipular y transformar árboles de expresión. Probablemente, el ejemplo más completo y sofisticado sería Linq2SQL (la implementación de SQL Server) que realiza transformaciones complejas de manera eficiente que segregan las partes del árbol de expresión que pueden delegarse en el servidor de la base de datos.

Esta no es la primera tecnología que permite consultas que combinan datos de varias fuentes, pero puede ser la primera que automatice el desenredado de dependencias para aprovechar las capacidades de manipulación masiva de los servidores de bases de datos. No es perfecto (a veces hay que ayudarlo), pero funciona muy bien y prestando atención a los detalles que no obtendrá de los humanos.

Cuando no tiene que ayudarla a salir, la comprensión del cálculo le llevará un largo camino para averiguar lo que está molestando - lo que además de ¿De qué sirve? ahí está tu respuesta a ¿Por qué tengo que aprender esto cuando las máquinas lo harán por mí?

Peter Wone
fuente