Introducción: lógica combinatoria
La lógica combinatoria (CL) se basa en cosas llamadas combinadores , que son básicamente funciones. Hay dos combinadores básicos "incorporados" Sy K, que se explicarán más adelante.
Asociatividad izquierda
CL es asociativo a la izquierda , lo que significa que los corchetes (que contienen cosas) que están en el extremo izquierdo del otro par de corchetes que lo contienen se pueden quitar, con su contenido liberado. Por ejemplo, algo como esto:
((a b) c)
Se puede reducir a
(a b c)
Donde (a b)está en el extremo izquierdo del soporte más grande ((a b) c), por lo que se puede quitar.
Un ejemplo mucho más grande de asociación izquierda (los corchetes son explicaciones):
((a b) c ((d e) f (((g h) i) j)))
= (a b c ((d e) f (((g h) i) j))) [((a b) c...) = (a b c...)]
= (a b c (d e f (((g h) i) j))) [((d e) f...) = (d e f...)]
= (a b c (d e f ((g h i) j))) [((g h) i) = (g h i)]
= (a b c (d e f (g h i j))) [((g h i) j) = (g h i j)]
Los corchetes también se pueden reducir cuando más de un par envuelve los mismos objetos. Ejemplos:
((((a)))) -> a
a ((((b)))) -> a b
a (((b c))) -> a (b c) [(b c) is still a group, and therefore need brackets.
Note that this doesn't reduce to `a b c`, because
`(b c)` is not on the left.]
Builtins
CL tiene dos combinadores "incorporados" Sy K, que pueden cambiar objetos (combinadores individuales, o un grupo de combinadores / grupos envueltos entre paréntesis) de la siguiente manera:
K x y = x
S x y z = x z (y z)
Donde x, yy zpueden ser sustitutos para cualquier cosa.
Un ejemplo de Sy Kson los siguientes:
(S K K) x [x is a stand-in for anything]
= S K K x [left-associativity]
= K x (K x) [S combinator]
= x [K combinator]
Otro ejemplo:
S a b c d
= a c (b c) d [combinators only work on the n objects to the right of it,
where n is the number of "arguments" n is defined to have -
S takes 3 arguments, so it only works on 3 terms]
Los anteriores son ejemplos de declaraciones CL normales, donde la declaración no puede evaluarse más y logra un resultado final en una cantidad de tiempo finita. Hay declaraciones no normales (que son declaraciones CL que no terminan y se seguirán evaluando para siempre), pero no están dentro del alcance del desafío y no necesitarán ser cubiertas.
Si desea obtener más información sobre CL, lea esta página de Wikipedia .
Tarea:
Su tarea es hacer combinadores adicionales, dado el número de argumentos, y lo que evalúa como entrada, que se da así:
{amount_of_args} = {evaluated}
Donde {amount_of_args}es un número entero positivo igual al número de args, y {evaluated}consiste en:
- argumentos hasta la cantidad de
1argumentos,2siendo el primer argumento, el segundo, etc.- Se le garantiza que no aparecerán números de argumento por encima de la cantidad de argumentos (por lo que solo es un
4cuándo ) .{amount_of_args}3{evaluated}
- Se le garantiza que no aparecerán números de argumento por encima de la cantidad de argumentos (por lo que solo es un
- soportes
()
Entonces ejemplos de entradas son:
3 = 2 3 1
4 = 1 (2 (3 4))
La primera entrada es pedir un combinador (digamos R) con tres argumentos ( R 1 2 3), que luego se evalúa en:
R 1 2 3 -> 2 3 1
La segunda entrada pide esto (con un nombre de combinador A):
A 1 2 3 4 -> 1 (2 (3 4))
Dada la entrada en este formato, debe devolver una cadena de S, Ky (), cuando se sustituye con un nombre de combinador y se ejecuta con argumentos, devuelve la misma instrucción evaluada que el {evaluated}bloque cuando el bloque de comando se sustituye por ese nombre de combinador.
La declaración del combinador de salida puede tener su espacio en blanco eliminado y los corchetes externos eliminados, por lo que (S K K (S S))se puede convertir algo así SKK(SS).
Si desea probar las salidas de su programa, @aditsu ha hecho un analizador de lógica combinatoria (que incluye S, K, Ie incluso otros como By C) aquí .
Puntuación:
Dado que este es un metagolf , el objetivo de este desafío es lograr la menor cantidad de bytes en la salida posible, dados estos 50 casos de prueba . Ponga sus resultados para los 50 casos de prueba en la respuesta, o haga un pastebin (o algo similar) y publique un enlace a ese pastebin.
En caso de empate, gana la primera solución.
Reglas:
- Su respuesta debe devolver la salida CORRECTA; por lo tanto, dada una entrada, debe devolver la salida correcta según la definición de la tarea.
- Su respuesta debe aparecer dentro de una hora en una computadora portátil moderna para cada caso de prueba.
- No se permite ninguna codificación de soluciones. Sin embargo, puede codificar hasta 10 combinadores.
- Su programa debe devolver la misma solución cada vez para la misma entrada.
- Su programa debe devolver un resultado válido para cualquier entrada dada, no solo para casos de prueba.
fuente
1, puede restar1de todo y luego envolver la solución para esa respuestaK(). Ejemplo: Solución para2 -> 1isK, por lo tanto, solución para3 -> 2isKK, solución para4 -> 3isK(KK)etc.Respuestas:
Haskell , puntuación 5017
Esto combina el algoritmo más tonto posible para la eliminación de abstracción ((λ x . X ) = I; (λ x . Y ) = K y ; (λ x . M N ) = S (λ x . M ) (λ x . N ) ) con un optimizador de mirilla utilizado después de cada aplicación. La regla de optimización más importante es S (K x ) (K y ) ↦ K ( xy ), que impide que el algoritmo explote siempre exponencialmente.
El conjunto de reglas se configura como una lista de pares de cadenas, por lo que es fácil jugar con nuevas reglas. Como beneficio adicional de reutilizar el analizador de entrada para este propósito, S, K y yo también se aceptan dentro de los combinadores de entrada.
Las reglas no se aplican incondicionalmente; más bien, se mantienen tanto las versiones antiguas como las nuevas, y las versiones subóptimas se podan solo cuando su longitud supera la de la mejor versión en más de una constante (actualmente 3 bytes).
La puntuación se mejora ligeramente al tratar a I como un combinador fundamental hasta que la etapa de salida lo reescribe en SKK. De esta forma, KI = K (SKK) se puede acortar en 4 bytes a SK en la salida sin confundir el resto de las optimizaciones.
Pruébalo en línea!
Salida
fuente
S (K x) (K y) = K (x y))?ruleStrings. Si no lo hiciéramos, la salida sería exponencialmente más larga: para este pequeño ejemplo, habríamos obtenido S (S (KS) (S (S (KS) (S (KK) (KS))) (S (S (KS) (S (KK) (KK))) (S (KK) (SKK))))) (S (S (KS) (S (S (KS) (S (KK) (KS))) ( S (S (KS) (S (KK) (KK))) (SK)))) (S (KK) (SK))) en lugar de S (KS) K.Suma de longitudes de solución:
12945 85085872Código Haskell que toma líneas de entrada de stdin y no le importa si el separador es
=o->:Implementa la abstracción de soporte mejorada de la sección 3.2 de John Tromp: Binary Lambda Calculus and Combinatory Logic que está vinculado desde el artículo de Wikipedia sobre lógica combinatoria. Los casos especiales más útiles solo usan el
Scombinador para succionar subterms alrededor para evitar el anidamiento profundo de las variables. El caso que verifica la igualdad de algunos subterms no es necesario para ninguno de los casos de prueba. Si bien no existe un caso especial para manejar elWcombinador (ver la respuesta de Peter), las reglas trabajan juntas para encontrar laSS(SK)expresión más corta . (Primero cometí un error al intentar optimizar las llamadas internasabstract, luego estaWoptimización no ocurrió y el resultado general fue 16 bytes más largo).Y aquí están los resultados de los casos de prueba:
fuente
8486 usando S, K, I, W
Explicación
El algoritmo estándar (como por ejemplo se describe en el capítulo 18 del Para Mock un Mockingbird ) utiliza cuatro casos, correspondientes a los combinadores
S,K,I = SKK, y simple dejó-asociación. Creo que esto es lo que implementa la respuesta de Christian. Esto es suficiente, pero no necesariamente óptimo, y dado que se nos permite codificar hasta 10 combinadores, deja 7 opciones.Otros combinadores combinatorios bien conocidos son
que, junto con
K, forman una base completa . En SK estos sony las
SKIreglas derivan esas mismas expresiones paraByC, pero paraWderivanS S (K (S K K)). Por lo tanto, elegí implementarWcomo un caso especial.Programa (CJam)
Conjunto de pruebas en línea
Salidas generadas:
fuente