Booleanos da igreja
Um booleano de igreja é uma função que retorna x
para verdadeiro e y
para falso onde x
é o primeiro argumento para a função e y
é o segundo argumento para a função. Outras funções podem ser compostas a partir dessas funções, que representam as operações and
not
or
xor
e implies
lógicas.
Desafio
Construir as booleans Igreja e and
not
or
xor
e implies
Portas da igreja em um idioma de sua escolha. and
or
e xor
deve assumir duas funções (representando os booleanos da Igreja) e retornar uma função (representando outro booleano da Igreja). Da mesma forma, not
deve inverter a função necessária e o implies
gate deve executar booleano implica lógica onde o primeiro argumento é implies
o segundo.
Pontuação
O comprimento total de todo o código necessário para fazer Igreja true
e false
na sua língua eo and
not
or
xor
e implies
Igreja portões excluindo o nome da função. (por exemplo, false=lambda x,y:y
em Python seria 13 bytes). Você pode reutilizar esses nomes posteriormente no seu código, contando 1 byte no total de bytes desse gate.
Exemplos de pseudo-código:
As funções que você cria devem poder ser chamadas posteriormente em seu código, assim.
true(x, y) -> x
false(x, y) -> y
and(true, true)(x, y) -> x
and(true, false)(x, y) -> y
# ... etc
fonte
true([x, y])
,and([true, true])([x, y])
)?Respostas:
Cálculo lambda binário ,
13,87512,875 bytes (103 bits)A linguagem de cálculo binário lambda (BLC) de John Tromp é basicamente um formato de serialização eficiente para o cálculo lambda. É uma ótima opção para essa tarefa, pois a notação da Igreja é até a maneira "idiomática" de trabalhar com booleanos no BLC.
Usei as seguintes funções lambda para os combinadores,
algumas das quais copiei e joguei na resposta Haskell:,que foram encontradas por uma pesquisa exaustiva com um limite de prova de 20 β-reduções para cada caso. Há uma boa chance de que sejam os mais curtos possíveis.Isso se traduz nas seguintes seqüências de código BLC (binárias):
As funções acima têm no total
111 bits de comprimento (13,875 bytes) e103 bits de comprimento (12,875 bytes). Eles não precisam estar alinhados aos limites de bytes para serem usados dentro de um programa; portanto, faz sentido contar bytes fracionários.Não há reutilização de código entre os combinadores, porque não há variáveis / referências / nomes no BLC - tudo teve que ser copiado. Ainda assim, a eficiência da codificação cria uma representação bastante concisa.
fonte
And: (\a \b a b a)
funcionar?\a \b a a b
. É mais longo que o que eu usei no BLC.Haskell , 50 - 6 = 44 bytes
-1 byte graças a Khuldraeseth na'Barya e -1 byte graças a Christian Sievers.
Experimente online!
fonte
Show
casos deconst
econst id
e imprimir as booleans igreja diretamente. Experimente online! .a
pode ser encurtado.f=n t
?t=pure
vez det=const
.t=pure
causará um erro quando tento aplicara
,o
,x
, oui
para ele. Declarar o tipo det
correção isso custa mais bytes do que apenas usart=const
.Python 2 , (-3?)
10195 bytesDavid Beazley come seu coração!
-6 graças a Chas Brown (moveu o repetido
:
para o texto de junção>. <)Experimente online!
Eu acho que pode ser
95 - 3
porque eu não reutilizar as funçõesA
,X
ouI
, mas eu uso um único=
para a atribuição (em frentelambda
). Talvez eu não consiga remover nenhum; talvez eu até consiga remover 3.5?fonte
exec
meios que não posso? Eu posso ver indo de qualquer maneira - não reutilizo A, X ou I, mas o código não funcionará sem eles. (Talvez eu até consiga remover 3.5 ?!)JavaScript (Node.js) ,
928683 - 7 = 76 bytesExperimente online! O link inclui casos de teste básicos. Editar: salvou
69 bytes graças a @tsh.fonte
t
,f
,n
são usados.t
,f
e,n
no seu caso).Python 2 ,
133 - 6 = 12794 bytesExperimente online!
Roubando descaradamente a ideia furtiva por trás da resposta de Jonathan Allan ; embora não sejam deduzidos bytes.
fonte
J , 67 bytes - 7 = 60
Experimente online!
Vale nada:
Funções de ordem superior funcionam de maneira diferente em J do que em uma linguagem funcional. Para criar um novo verbo a partir de 1 ou 2 verbos existentes, você precisa usar um advérbio (no caso de 1) ou uma conjunção (no caso de 2).
Sintaticamente, advérbios vêm após um verbo e conjunções vão entre eles. Assim, para "não" um verbo que
f
você fazf n
, e para "e" verbosf
eg
, vocêf a g
.fonte
Wolfram Language (Mathematica) , 61-7 = 54 bytes
Experimente online!
sem golfe: inspirado na Wikipedia ,
fonte
Carga insuficiente ,
5652 bytesExperimente online! (inclui um conjunto de testes e um texto que identifica partes do programa)
Isso é surpreendentemente bom para um esolang de nível muito baixo. (Numerais da igreja, booleanos da igreja etc. são muito comumente usados no Underload por esse motivo; o idioma não possui números e booleanos incorporados, e essa é uma das maneiras mais fáceis de simulá-los. Dito isso, também é comum codificar booleanos como os números 0 e 1. da Igreja)
Para quem está confuso: Underload permite definir funções reutilizáveis, mas não permite que você as nomeie da maneira normal, elas meio que flutuam na pilha de argumentos (por isso, se você definir cinco funções e depois chamar a primeira) você definiu, precisa escrever uma nova função que use cinco argumentos e chame o quinto deles, depois chame-a com argumentos insuficientemente para que procure argumentos extras a serem usados). Chamá-los destrói-os por padrão, mas você pode modificar a chamada para torná-la não destrutiva (em casos simples, você só precisa adicionar dois pontos à chamada, embora os casos complexos sejam mais comuns porque você precisa garantir que as cópias na pilha não atrapalha), então o suporte às funções do Underload tem todos os requisitos que precisamos da pergunta.
Explicação
verdade
Essa é bem direta; nos livramos do argumento que não queremos e o argumento que queremos permanece lá, servindo como valor de retorno.
falso
Este é ainda mais direto.
não
É divertido:
not
não chama de argumento, apenas usa uma composição de função. Esse é um truque comum no Underload, no qual você não inspeciona seus dados, apenas altera a forma como eles funcionam pré e pós-compondo as coisas com ele. Nesse caso, modificamos a função para trocar seus argumentos antes da execução, o que claramente nega um numeral da Igreja.e
A questão permite definir funções em termos de outras funções. Definimos "e" a seguir, porque quanto mais recentemente "não" tiver sido definido, mais fácil será usá-lo. (Isso não subtrai nossa pontuação, porque não estamos nomeando "não", mas economiza bytes ao escrever a definição novamente. Essa é a única vez que uma função se refere a outra, porque se refere a qualquer função mas o definido mais recentemente custaria muitos bytes.)
A definição aqui é
and x y = (not x) false y
. Em outras palavras, senot x
retornarmosfalse
; caso contrário, retornamosy
.ou
O @Nitrodon apontou nos comentários que
or x y = x x y
normalmente são menores queor x y = x true y
e que também estão corretos no Underload. Uma implementação ingênua disso seria(:~^)
, mas podemos obter um byte adicional observando que não importa se executamos o primeiro argumento original ou a cópia dele, o resultado é o mesmo.Underload não suporta curry no sentido usual, mas definições como essa fazem com que pareça! (O truque é que argumentos não consumidos permanecem por aí, então a função que você chama os interpretará como seus próprios argumentos.)
implica
A definição usada aqui é
implies x y = not (y false x)
. Se y for verdadeiro, isso simplifica paranot false
, ietrue
. Se y for falso, isso simplifica anot x
, fornecendo a tabela de verdade que queremos.Nesse caso, estamos usando
not
novamente, desta vez reescrevendo seu código em vez de fazer referência a ele. É apenas escrito diretamente como(~)~*
sem parênteses, portanto é chamado e não definido.xor
Desta vez, estamos avaliando apenas um dos nossos dois argumentos e usá-lo para determinar o que compor no segundo argumento. Underload permite que você jogue rápido e livre com aridade, então estamos usando o primeiro argumento para escolher entre duas funções de dois argumentos e dois retornos; a troca de argumentos que retorna os dois, mas na ordem oposta, e a função de identidade que retorna os dois na mesma ordem.
Quando o primeiro argumento é verdadeiro, produzimos uma versão editada do segundo argumento que troca seus argumentos antes da execução, ou seja, pré-compõe com "argumentos de troca", ou seja
not
. Portanto, um verdadeiro primeiro argumento significa que retornamosnot
o segundo argumento. Por outro lado, um primeiro argumento falso significa que compomos com a função de identidade, ou seja, não fazemos nada. O resultado é uma implementação dexor
.fonte
or x y = x x y
salva alguns bytesor x y = x true y
.Ruby , 82 - 4 = 78 bytes
Experimente online!
fonte
Java 8, score:
360358319271233 (240-7) bytesIsso foi mais difícil de realizar do que eu pensava quando comecei. Especialmente oEDIT: Ok, não reutilizar funções, mas apenas duplicar a mesma abordagem é muito mais barato em termos de contagem de bytes para Java .. E eu recebo o bônus total de -7 por não usar nenhuma das funções também.implies
. Enfim, funciona .. Provavelmente pode ser jogado um pouco aqui e ali.Experimente online.
Explicação:
fonte
C ++ 17,
207−49 = 158195 - 58 = 137 bytesAs quebras de linha são desnecessárias (exceto as duas primeiras).
Experimente online!
Testado em unidade com afirmações como:
ATUALIZADO: anteriormente eu tinha
mas a resposta de Roman apontou o caminho para a versão mais curta. Observe que agora
not_(std::plus<>)
está mal formado, onde antigamente era equivalentestd::plus<>
; mas comostd::plus<>
"não representa um booleano da Igreja", acho que um ou outro comportamento é bom pelas regras.fonte
Quarto (gforth) ,
133bytes - 7 =126122Experimente online!
-4 bytes graças a Quuxplusone
Inicialmente, pensei demais sobre isso, considerando coisas como macros e literais, mas depois percebi que se eu definir as coisas em termos de verdadeiro e falso (como eu deveria ter feito em primeiro lugar), fica muito mais simples.
Explicação do código
fonte
execute
três vezes. Definir a abreviação: j execute ;
economizaria 4 bytes.Combinado SKI-calculus + C, 36 bytes
Na verdade, eu não conheço nenhum intérprete que permita definir combinadores adicionais em termos dos anteriores, então tive que testar isso usando http://ski.aditsu.net/ colando nos combinadores desejados, por exemplo ,
CCKK(SK)pq
saídasq
, mostrando queK
não implicaSK
.fonte
Julia 1.0 , 36 bytes
Não sei se isso conta, na verdade estou sobrecarregando o
Bool
tipo nativo para que seja possível chamar, por isso recebo a maioria dos portões lógicos de graça. Infelizmente, Julia não tem umimplies
portão, então tive que escrever minha própria função.Experimente online!
fonte
Perl 6 ,
120106102101 bytes-1 byte graças a Jo King
Experimente online!
fonte
C ++ 17,
202−49 = 153193 - 58 = 135 bytesInspirado pela discussão-comentário sobre o que conta como uma função de 2 árias de qualquer maneira, aqui está uma versão atualizada da minha solução anterior do C ++ 17. Na verdade, é mais curto, porque podemos usar a mesma macro para definir
not_
e definir todas as outras funções!Experimente online!
Este é testado com afirmações como
Observe que
or_
é definido como efetivamentePoderíamos definir de forma
or_
mais "concisa" comomas isso nos custaria porque não poderíamos mais usar a
D
macro.fonte
True
e emFalse
vez detrue_
efalse_
? E semelhante para os outros operadores. Isso economizará 12 bytes.APL (dzaima / APL) , 47 bytes SBCS de
Baseado em solução J de Jonah .
true
efalse
são funções infix,not
é um operador de sufixo e o restante são operadores infix.De acordo com o OP, isso conta tudo, inclusive e
←
até o final de cada linha, e cada chamada é uma definição anterior como um byte único.Experimente online!
verdadeiro e falso são as funções de identidade esquerda e direita.
not
simplesmente troca os argumentos de sua função de operando.O restante implementa a árvore de decisão:
and
usa a função da mão direita⍹
para selecionar o resultado da função mão esquerda,⍶
se verdadeiro, caso contrário, o resultado dafalse
função.or
usa a função esquerda⍶
à para selecionartrue
se verdadeiro, caso contrário, o resultado da função à direita⍹
.xor
usa a função da mão direita⍹
para selecionar o resultado negado da função mão esquerda,⍶not
se verdadeiro, caso contrário, o resultado da função mão esquerda.implies
usa a função mão esquerda⍶
para selecionar o resultado da função mão direita,⍹
se verdadeiro, caso contrário, o resultado datrue
função.fonte
Stax , 34 bytes
Execute e depure-o em staxlang.xyz!
Empurra um monte de blocos para a pilha. Cada bloco espera seu último argumento no topo da pilha, seguido na ordem inversa pelo resto.
Descompactado (41 bytes):
Cada par de
{ }
é um bloco. Usei os dois registradores X e Y para armazenartrue
e,not
assim, poderia acessá-los facilmente mais tarde. Infelizmente,false
não poderia ser simplesmente um não-op, pois isso deixaria a pilha confusa e atrapalharia um único caso XOR.Conjunto de teste, comentado
fonte
Befunge-98 ,
1057765 bytesBrincando ainda mais com a noção de "função" em idiomas sem funções ... aqui está uma versão Befunge-98 dos booleanos da Igreja!
Nesse dialeto restrito do Befunge-98, um programa consiste em uma série de "linhas" ou "funções", cada uma das quais começa com uma
>
instrução (Vá para a direita) na coluna x = 0. Cada "função" pode ser identificada com seu número de linha (coordenada y). Funções podem receber entrada através da pilha do Befunge , como de costume.A linha 0 é especial, porque (0,0) é o IP inicial. Para criar um programa que execute a linha L, basta colocar instruções na linha 0 que, quando executada, mova o ponteiro da instrução para (x = L, y = 0).
A mágica acontece na linha 1. A linha 1, quando executada, exibe um número
L
da pilha e salta para o número da linhaL
. (Essa linha tinha sido anteriormente> >>0{{2u2}2}$-073*-\x
, o que pode "saltar absoluto" para qualquer linha; mas acabei de perceber que, como sei que essa linha está atrelada à linha 1, podemos "saltar relativo"L-1
linhas com muito menos código.)A linha 2 representa a Igreja
FALSE
. Quando executado, ele exibe dois númerost
ef
da pilha e depois voa para o número da linhaf
.A linha 3 representa a Igreja
TRUE
. Quando executado, ele exibe dois númerost
ef
da pilha e depois voa para o número da linhat
.A linha 6, representando a Igreja
XOR
, é inovadora. Quando executado, ele exibe dois númerosa
eb
da pilha e depois voa para alinhara
com a entrada da pilhaNOT EXEC b
. Então, sea
representa IgrejaTRUE
, o resultado dea NOT EXEC b
seráNOT b
; e sea
representa igrejaFALSE
, o resultadoa NOT EXEC b
seráEXEC b
.Aqui está a versão não destruída com equipamento de teste. Na linha 0, configure a pilha com sua entrada. Por exemplo,
338
significaIMPLIES TRUE TRUE
. Certifique-se de que o fechamentox
apareça exatamente (x, y) = (0,15) ou então nada funcionará! Verifique também se a configuração da pilha começa comba
, para que o programa realmente termine com alguma saída.Experimente online!
Aqui está a versão cujos bytes eu contei.
Observe que, para definir uma função nesse dialeto, você não menciona seu nome; o seu "nome" é determinado pela sua localização de origem. Para chamar uma função, você menciona seu "nome"; por exemplo,
XOR
(6
) é definido em termos deNOT
eEXEC
(5
e1
). Mas todos os meus "nomes de funções" já levam apenas um byte para representar. Portanto, esta solução não recebe ajustes de pontuação.fonte