Booleanos de la iglesia
Una iglesia booleana es una función que devuelve x
verdadero y y
falso donde x
es el primer argumento de la función y y
es el segundo argumento de la función. Se pueden componer funciones adicionales a partir de estas funciones que representan las operaciones lógicas and
not
or
xor
y implies
.
Reto
Construir los booleanos Iglesia y and
not
or
xor
y implies
Puertas de la iglesia en un idioma de su elección. and
or
y xor
debe tomar dos funciones (que representan booleanos de la Iglesia) y devolver una función (que representa otro booleano de la Iglesia). Del mismo modo, not
debe invertir la función que toma y la implies
puerta debe realizar booleana implica lógica donde el primer argumento es implies
el segundo.
Tanteo
La longitud total de todo el código necesario para hacer Iglesia true
y false
en su idioma y el and
not
or
xor
e implies
Iglesia puertas excluyendo el nombre de la función. (por ejemplo, false=lambda x,y:y
en Python serían 13 bytes). Puede reutilizar estos nombres más adelante en su código con ellos contando 1 byte hacia el total de bytes de esa puerta.
Pseudocódigo Ejemplos:
Las funciones que cree deberían poder llamarse más adelante en su código de esta manera.
true(x, y) -> x
false(x, y) -> y
and(true, true)(x, y) -> x
and(true, false)(x, y) -> y
# ... etc
fuente
true([x, y])
,and([true, true])([x, y])
)?Respuestas:
Cálculo binario de Lambda ,
13.87512.875 bytes (103 bits)Binary Lambda Calculus Language (BLC) de John Tromp es básicamente un formato de serialización eficiente para el cálculo lambda. Es una gran opción para esta tarea, ya que la notación de la Iglesia es incluso la forma "idiomática" de trabajar con booleanos en BLC.
Utilicé las siguientes funciones lambda para los combinadores,
algunos de los cuales copié y jugué golf de la respuesta de Haskell:que se encontraron mediante una búsqueda exhaustiva con un límite de prueba de 20 reducciones β para cada caso. Hay una buena posibilidad de que estos sean lo más cortos posible.Estos se traducen en las siguientes secuencias de código BLC (binario):
Las funciones anteriores son en total
111 bits de largo (13.875 bytes)103 bits de largo (12.875 bytes). No necesitan estar alineados con los límites de bytes para ser utilizados dentro de un programa, por lo que tiene sentido contar bytes fraccionarios.No hay reutilización de código entre los combinadores, porque no hay variables / referencias / nombres en BLC: todo tuvo que copiarse. Aún así, la eficiencia de la codificación hace una representación bastante concisa.
fuente
And: (\a \b a b a)
funcionará?\a \b a a b
. Sin embargo, es más largo que el que usé en BLC.Haskell , 50 - 6 = 44 bytes
-1 byte gracias a Khuldraeseth na'Barya, y -1 byte gracias a Christian Sievers.
Pruébalo en línea!
fuente
Show
casos deconst
yconst id
e imprimir los booleanos iglesia directamente. Pruébalo en línea! .a
se puede acortarf=n t
?t=pure
lugar det=const
.t=pure
se producirá un error al intentar aplicara
,o
,x
, oi
para ella. Declarar el tipo det
para arreglar esto cuesta más bytes que simplemente usart=const
.Python 2 , (-3?)
10195 bytes¡David Beazley te come el corazón!
-6 gracias a Chas Brown (movió el texto repetido
:
al de unión>. <)Pruébalo en línea!
Creo que podría deberse a
95 - 3
que no reutilizo las funcionesA
,X
oI
, pero uso una sola=
para la asignación (en frente delambda
). Tal vez no pueda eliminar ninguno; tal vez incluso puedo eliminar 3.5?fuente
exec
significa que no puedo? Puedo ver que va en cualquier dirección: no reutilizo A, X o yo, pero el código no funcionará sin ellos. (¡¿Tal vez incluso pueda eliminar 3.5 ?!)JavaScript (Node.js) ,
928683 - 7 = 76 bytesPruébalo en línea! El enlace incluye casos de prueba básicos. Editar: Guardado
69 bytes gracias a @tsh.fuente
t
,f
,n
se utilizan.t
,f
yn
en su caso).Python 2 ,
133 - 6 = 12794 bytesPruébalo en línea!
Robando descaradamente la idea furtiva detrás de la respuesta de Jonathan Allan ; Sin embargo, no se deducen bytes.
fuente
J , 67 bytes - 7 = 60
Pruébalo en línea!
Vale la pena señalar:
Las funciones de orden superior funcionan de manera diferente en J que en un lenguaje funcional. Para crear un nuevo verbo a partir de 1 o 2 verbos existentes, debe usar un adverbio (en el caso de 1) o una conjunción (en el caso de 2).
Sintácticamente, los adverbios vienen después de un verbo, y las conjunciones van entre ellos. Por lo tanto, "no" es un verbo
f
que hacesf n
, y "y" verbosf
yg
túf a g
.fuente
Wolfram Language (Mathematica) , 61-7 = 54 bytes
Pruébalo en línea!
sin golf: inspirado en Wikipedia ,
fuente
Baja carga ,
5652 bytesPruébalo en línea! (incluye un traje de prueba y texto que identifica partes del programa)
Esto es sorprendentemente bueno para un esolang de muy bajo nivel. (Los números de iglesia, los booleanos de la iglesia, etc. se usan muy comúnmente en Underload por esta razón; el lenguaje no tiene números y booleanos integrados, y esta es una de las formas más fáciles de simularlos. Dicho esto, también es común codificar booleanos como los números de la Iglesia 0 y 1.)
Para cualquiera que esté confundido: Underload le permite definir funciones reutilizables, pero no le permite nombrarlas de la manera normal, simplemente flotan en la pila de argumentos (por lo tanto, si define cinco funciones y luego desea llamar a la primera) usted definió, necesita escribir una nueva función que tome cinco argumentos y llame al quinto de ellos, luego llámela con suficientes argumentos para que busque argumentos de repuesto para usar). Llamarlos los destruye de manera predeterminada, pero puede modificar la llamada para que no sea destructiva (en casos simples, solo necesita agregar dos puntos a la llamada, aunque los casos complejos son más comunes porque necesita asegurarse de que las copias en la pila no se interponga en su camino), por lo que el soporte de funciones de Underload tiene todos los requisitos que necesitaríamos de la pregunta.
Explicación
cierto
Este es bastante sencillo; nos deshacemos del argumento que no queremos y el argumento que queremos simplemente permanece allí, sirviendo como valor de retorno.
falso
Este es aún más sencillo.
no
Esta es la diversión:
not
no llama a su argumento en absoluto, solo usa una composición de función. Este es un truco común en Underload, en el que no inspeccionas tus datos en absoluto, solo cambias su funcionamiento al pre y post componer cosas con ellos. En este caso, modificamos la función para intercambiar sus argumentos antes de ejecutar, lo que claramente niega un número de Iglesia.y
La pregunta permite definir funciones en términos de otras funciones. Definimos "y" siguiente porque cuanto más recientemente se ha definido "no", más fácil es usarlo. (Esto no resta de nuestro puntaje, porque no estamos nombrando "no" en absoluto, pero ahorra bytes al escribir la definición nuevamente. Esta es la única vez que una función se refiere a otra, porque se refiere a cualquier función pero la definición más reciente costaría demasiados bytes).
La definición aquí es
and x y = (not x) false y
. En otras palabras, sinot x
, entonces volvemosfalse
; de lo contrario, volvemosy
.o
@Nitrodon señaló en los comentarios que
or x y = x x y
normalmente es más corto queor x y = x true y
, y que resulta ser correcto en Underload también. Sería una implementación ingenua de eso(:~^)
, pero podemos aprovechar un byte adicional al notar que no importa si ejecutamos el primer argumento original o la copia del mismo, el resultado es el mismo de cualquier manera.Underload en realidad no admite curry en el sentido habitual, ¡pero definiciones como esta hacen que parezca que sí! (El truco es que los argumentos no consumidos simplemente se quedan, por lo que la función que llama los interpretará como sus propios argumentos).
implica
La definición utilizada aquí es
implies x y = not (y false x)
. Si y es verdadero, esto se simplifica anot false
, es decirtrue
. Si y es falso, esto se simplifica anot x
, lo que nos da la tabla de verdad que queremos.En este caso, lo estamos utilizando
not
nuevamente, esta vez reescribiendo su código en lugar de hacer referencia a él. Simplemente se escribe directamente(~)~*
sin paréntesis, por lo que se llama en lugar de definirse.xor
Esta vez, estamos evaluando solo uno de nuestros dos argumentos, y usándolo para determinar qué componer en el segundo argumento. Underload te permite jugar rápido y suelto con arity, por lo que estamos usando el primer argumento para elegir entre dos funciones de dos argumentos y dos retornos; el intercambio de argumentos que los devuelve a ambos pero en el orden opuesto, y la función de identidad que los devuelve a ambos en el mismo orden.
Cuando el primer argumento es verdadero, por lo tanto, producimos una versión editada del segundo argumento que intercambia sus argumentos antes de ejecutar, es decir, precompone con "argumentos de intercambio", es decir
not
. Entonces, un primer argumento verdadero significa que devolvemosnot
el segundo argumento. Por otro lado, un primer argumento falso significa que componimos con la función de identidad, es decir, no hacemos nada. El resultado es una implementación dexor
.fuente
or x y = x x y
guarda algunos bytesor x y = x true y
.Ruby , 82-4 = 78 bytes
Pruébalo en línea!
fuente
Java 8, puntaje:
360358319271233 (240-7) bytesEsto fue más difícil de lograr de lo que pensé cuando lo comencé ... Especialmente elEDITAR: Ok, no volver a usar las funciones, sino simplemente duplicar el mismo enfoque es mucho más barato en términos de conteo de bytes para Java ... Y obtengo el bono completo -7 por no usar ninguna de las funciones también.implies
. De todos modos, funciona ... Probablemente se puede jugar un poco de golf aquí y allá.Pruébalo en línea.
Explicación:
fuente
C ++ 17,
207−49 = 158195- 58 = 137 bytesLos saltos de línea son innecesarios (aparte de los dos primeros).
Pruébalo en línea!
Probado en unidad con afirmaciones como:
ACTUALIZADO: anteriormente había tenido
pero la respuesta de Roman señaló el camino a la versión más corta. Tenga en cuenta que ahora
not_(std::plus<>)
está mal formado, donde antes era equivalente astd::plus<>
; pero comostd::plus<>
no "representa a una iglesia booleana", creo que cualquiera de los dos comportamientos está bien según las reglas.fuente
Forth (gforth) ,
133bytes - 7 =126122Pruébalo en línea!
-4 bytes gracias a Quuxplusone
Inicialmente pensé demasiado en esto, considerando cosas como macros y literales, pero luego me di cuenta de que si definía las cosas en términos de verdadero y falso (como debería haber hecho en primer lugar), se vuelve mucho más simple.
Explicación del código
fuente
execute
tres veces. Definir la taquigrafía: j execute ;
le ahorraría 4 bytes.SKI-cálculo + C combinador, 36 bytes
En realidad, no conozco ningún intérprete que le permita definir combinadores adicionales en términos de los anteriores, así que tuve que probar esto usando http://ski.aditsu.net/ pegando los combinadores deseados, por ejemplo, las
CCKK(SK)pq
salidasq
, , mostrando queK
no implicaSK
.fuente
Julia 1.0 , 36 bytes
No sé si eso cuenta, en realidad solo estoy sobrecargando al nativo
Bool
tipo para que se pueda llamar, por lo que obtengo la mayoría de las puertas lógicas de forma gratuita. Desafortunadamente, Julia no tiene unaimplies
puerta, así que tuve que escribir mi propia función.Pruébalo en línea!
fuente
Perl 6 ,
120106102101 bytes-1 byte gracias a Jo King
Pruébalo en línea!
fuente
C ++ 17,
202−49 = 153193- 58 = 135 bytesInspirado por la discusión de comentarios sobre lo que cuenta como una función de 2 arios de todos modos, aquí hay una versión al curry de mi solución C ++ 17 anterior. En realidad es más corto porque podemos usar la misma macro para definir
not_
y definir todas las demás funciones.Pruébalo en línea!
Este se prueba con afirmaciones como
Observe que
or_
se define como efectivamentePodríamos definir
or_
más "concisamente" comopero eso nos costaría porque ya no podríamos usar la
D
macro.fuente
True
y enFalse
lugar detrue_
yfalse_
? Y similar para los otros operadores. Eso ahorrará 12 bytes.APL (dzaima / APL) , 47 bytes SBCS
Basado en la solución J de Jonah .
true
yfalse
son funciones de infijo,not
es un operador de sufijo y el resto son operadores de infijo.Según OP, esto cuenta todo, incluso
←
hasta el final de cada línea, y cuenta cada llamada de una definición previa como un solo byte.Pruébalo en línea!
verdadero y falso son las funciones de identidad izquierda y derecha.
not
simplemente intercambia los argumentos de su función operando.El resto implementa el árbol de decisión:
and
usa la función derecha⍹
para seleccionar el resultado de la función izquierda⍶
si es verdadero, de lo contrario, el resultado de lafalse
función.or
usa la función de la izquierda⍶
para seleccionartrue
si es verdadero, de lo contrario, el resultado de la función de la derecha⍹
.xor
usa la función derecha⍹
para seleccionar el resultado negado de la función izquierda⍶not
si es verdadero, de lo contrario, el resultado de la función izquierda.implies
usa la función izquierda⍶
para seleccionar el resultado de la función derecha⍹
si es verdadero, de lo contrario, el resultado de latrue
función.fuente
Stax , 34 bytes
¡Ejecútelo y depúrelo en staxlang.xyz!
Empuja un montón de bloques a la pila. Cada bloque espera su último argumento sobre la pila, seguido en orden inverso por el resto.
Desempaquetado (41 bytes):
Cada par de
{ }
es un bloque. Usé los dos registros X e Y para mantenerlostrue
ynot
así podría acceder a ellos fácilmente más tarde. Desafortunadamente,false
no podría ser simplemente un no-op, ya que eso dejaría la pila desordenada y arruinaría un solo caso XOR.Conjunto de pruebas, comentado
fuente
Befunge-98 ,
1057765 bytesJugando aún más con la noción de "función" en idiomas sin funciones ... ¡aquí hay una versión Befunge-98 de los booleanos de la Iglesia!
En este dialecto restringido de Befunge-98, un programa consiste en una serie de "líneas" o "funciones", cada una de las cuales comienza con un
>
instrucción (Ir a la derecha) en la columna x = 0. Cada "función" se puede identificar con su número de línea (coordenada y). Las funciones pueden recibir información a través de la pila de Befunge , como de costumbre.La línea 0 es especial, porque (0,0) es la IP inicial. Para hacer un programa que ejecute la línea L, simplemente coloque las instrucciones en la línea 0 que, cuando se ejecute, vuele el puntero de instrucción a (x = L, y = 0).
La magia ocurre en la línea 1. La línea 1, cuando se ejecuta, saca un número
L
de la pila y salta al número de líneaL
. (Esta línea había sido anteriormente> >>0{{2u2}2}$-073*-\x
, lo que puede "saltar de forma absoluta" a cualquier línea; pero me di cuenta de que, dado que sé que esta línea está vinculada a la línea 1, podemos "saltar de forma relativa"L-1
líneas de en muchísimo menos código).La línea 2 representa a la Iglesia
FALSE
. Cuando se ejecuta, aparece dos númerost
yf
de la pila y luego vuela al número de líneaf
.La línea 3 representa a la Iglesia
TRUE
. Cuando se ejecuta, aparece dos númerost
yf
de la pila y luego vuela al número de líneat
.La línea 6, que representa a Church
XOR
, es innovadora. Cuando se ejecuta, muestra dos númerosa
yb
de la pila, y luego vuela a la líneaa
con la entrada de la pilaNOT EXEC b
. Entonces, sia
representa a la IglesiaTRUE
, el resultado dea NOT EXEC b
seráNOT b
; y sia
representa a la IglesiaFALSE
, el resultado dea NOT EXEC b
seráEXEC b
.Aquí está la versión sin golf con arnés de prueba. En la línea 0, configure la pila con su entrada. Por ejemplo,
338
significaIMPLIES TRUE TRUE
. ¡Asegúrese de que el cierrex
aparezca exactamente en (x, y) = (0,15) o de lo contrario nada funcionará! También asegúrese de que su configuración de pila comienceba
, de modo que el programa realmente termine con alguna salida.Pruébalo en línea!
Aquí está la versión cuyos bytes conté.
Observe que para definir una función en este dialecto no menciona su nombre en absoluto; su "nombre" está determinado por su ubicación de origen. Para llamar a una función, mencionas su "nombre"; por ejemplo,
XOR
(6
) se define en términos deNOT
yEXEC
(5
y1
). Pero todos mis "nombres de funciones" ya solo toman un byte para representar. Entonces esta solución no obtiene ajustes de puntuación.fuente