Booleany kościelne

Kościół logiczna jest funkcją, która wraca xdo prawdziwego i yfałszywego gdzie xjest pierwszy argument funkcji i yjest drugi argument funkcji. Dalsze funkcje mogą składać się z tych funkcji, które reprezentują and not or xori implieslogicznych operacji.

Wyzwanie

Skonstruowania wartości logicznych i kościelnych and not or xororaz impliesChurch Gates w języku wyboru. and ori xorpowinien przyjąć dwie funkcje (reprezentujące boolean Kościoła) i zwrócić funkcję (reprezentującą inny boolean Kościoła). Podobnie, notpowinno odwrócić funkcję, którą przyjmuje, a impliesbramka powinna wykonać wartość logiczną, co oznacza logikę, w której pierwszy argument impliesjest drugim.

Punktacja

Łączna długość całego kodu wymaganego do utworzenia Kościoła trueoraz falsew twoim języku oraz bramek and not or xori impliesKościoła z wyłączeniem nazwy funkcji. (na przykład false=lambda x,y:yw Pythonie byłoby 13 bajtów). Możesz użyć tych nazw później w swoim kodzie, licząc 1 bajt w sumie bajtów tej bramki.

Przykłady pseudokodu:

Utworzone funkcje powinny mieć możliwość późniejszego wywołania w kodzie.

true(x, y) -> x
false(x, y) -> y
and(true, true)(x, y) -> x
and(true, false)(x, y) -> y
# ... etc

Binary Lambda Calculus , 13,875 12,875 bajtów (103 bity)

Binary Lambda Calculus Language (BLC) Johna Trompa jest w zasadzie wydajnym formatem serializacji dla rachunku lambda. Doskonale pasuje do tego zadania, ponieważ notacja kościelna jest nawet „idiomatycznym” sposobem pracy z booleanami w BLC.

Użyłem następujących funkcji lambda dla kombinatorów, z których niektóre skopiowałem i grałem w golfa z odpowiedzi Haskella: które zostały znalezione przez wyczerpujące poszukiwanie z limitem dowodu wynoszącym 20 β-redukcji dla każdego przypadku. Istnieje duża szansa, że ​​są one możliwie najkrótsze.

True:  (\a \b a)
False: (\a \b b)
Not:   (\a \b \c a c b)
And:   (\a \b b a b)
Or:    (\a a a)
Xor:   (\a \b b (a (\c \d d) b) a)
Impl:  (\a \b a b (\c \d c))

Przekładają się one na następujące (binarne) sekwencje kodu BLC:

 bits |  name | BLC
------+-------+---------
    7 | True  | 0000 110
    6 | False | 0000 10
   19 | Not   | 0000 0001 0111 1010 110
   15 | And   | 0000 0101 1011 010
    8 | Or    | 0001 1010
   28 | Xor   | 0000 0101 1001 0111 0000 0101 0110
   20 | Impl  | 0000 0101 1101 0000 0110

Powyższe funkcje mają w sumie 111 bitów (13,875 bajtów), 103 bity długości (12,875 bajtów). Nie trzeba ich wyrównywać do granic bajtów, aby mogły być używane w programie, dlatego warto liczyć ułamkowe bajty.

Ponowne użycie kodu między kombinatorami jest niemożliwe, ponieważ w BLC nie ma żadnych zmiennych / referencji / nazw - wszystko trzeba było skopiować. Mimo to wydajność kodowania stanowi dość zwięzłą reprezentację.

Haskell , 50–6 = 44 bajty

-1 bajt dzięki Khuldraeseth na'Barya, a -1 bajt dzięki Christian Sievers.

t=const
f=n t
n=flip
a=n n f
o=($t)
x=(n>>=)
i=o.n

Wypróbuj online!

Python 2 , (-3?)  101  95 bajtów

David Beazley zjedz swoje serce!

-6 dzięki Chasowi Brownowi (przeniesiono powtórzony :do tekstu łączenia>. <)

exec'=lambda x,y=0:'.join('F y;T x;N x(F,T);A x(y,F);O x(T,y);X x(N(y),y);I O(y,N(x))'.split())

Wypróbuj online!

Myślę, że może tak być, 95 - 3ponieważ nie używam ponownie funkcji A, Xlub I, ale używam jednego =do przypisania (przed lambda). Może nie mogę usunąć żadnego; może nawet uda mi się usunąć 3.5?

JavaScript (Node.js) , 92 86 83 - 7 = 76 bajtów

t=p=>q=>p
f=t(q=>q)
n=p=>p(f)(t)
a=p=>n(p)(f)
o=p=>p(t)
x=p=>p(n)(f())
i=p=>n(p)(t)

Wypróbuj online! Link zawiera podstawowe przypadki testowe. Edycja: Zapisano 6 9 bajtów dzięki @tsh.

Python 2 , 133 - 6 = 127 94 bajty

exec"t!u;f!v;n!u(f,t);a!u(v,f);o!u(t,v);x!u(n(v),v);i!o(v,n(u))".replace('!','=lambda u,v=0:')

Wypróbuj online!

Bezwstydnie kradnie podstępny pomysł stojący za odpowiedzią Jonathana Allana ; nie odjęto jednak bajtów.

J, 67 bytes - 7 = 60

t=.[
f=.]
n=.~
a=.2 :'u v]'
o=.2 :'[u v'
x=.2 :'u~v u'
i=.2 :'v u['

Try it online!

Worth noting:

Higher order functions work differently in J than in a functional language. To create a new verb from 1 or 2 existing verbs, you need to use either an adverb (in the case of 1) or a conjunction (in the case of 2).

Syntactically, adverbs come after a verb, and conjunctions go between them. Thus to "not" a verb f you do f n, and to "and" verbs f and g, you f a g.

Wolfram Language (Mathematica), 61-7=54 bytes

t=#&
f=#2&
a=#2~#~f&
o=t~#~#2&
n=f~#~t&
x=n@#~#2~#&
i=#2~#~t&

Try it online!

un-golfed: inspired by Wikipedia,

t[x_, y_] := x
f[x_, y_] := y
and[x_, y_] := x[y, f]
or[x_, y_] := x[t, y]
not[x_] := x[f, t]
xor[x_, y_] := y[not[x], x]
imply[x_, y_] := x[y, t]

Underload, 56 52 bytes

(~!)(!)((~)~*):((!)~^)*(:^)(~(!)~^(~)~*)(()~(~)~^~*)

Try it online! (includes a testsuite and text identifying parts of the program)

This scores surprisingly well for a very low-level esolang. (Church numerals, Church booleans, etc. are very commonly used in Underload for this reason; the language doesn't have numbers and booleans built in, and this is one of the easier ways to simulate them. That said, it's also common to encode booleans as the Church numerals 0 and 1.)

For anyone who's confused: Underload lets you define reusable functions, but doesn't let you name them in the normal way, they just sort of float around on the argument stack (so if you define five functions and then want to call the first one you defined, you need to write a new function that takes five arguments and calls the fifth of them, then call it with insufficiently many arguments so that it looks for spare arguments to use). Calling them destroys them by default but you can modify the call to make it non-destructive (in simple cases, you just need to add a colon to the call, although the complex cases are more common because you need to make sure that the copies on the stack don't get in your way), so Underload's function support has all the requirements we'd need from the question.

Explanation

true

(~!)
(  )  Define function:
 ~      Swap arguments
  !     Delete new first argument (original second argument)

This one's fairly straightforward; we get rid of the argument we don't want and the argument we do want just stays there, serving as the return value.

false

(!)
( )   Define function:
 !      Delete first argument

This one's even more straightforward.

not

((~)~*)
(     )  Define function:
    ~*     Modify first argument by pre-composing it with:
 (~)         Swap arguments

This one's fun: not doesn't call its argument at all, it just uses a function composition. This is a common trick in Underload, in which you don't inspect your data at all, you just change how it functions by pre- and post-composing things with it. In this case, we modify the function to swap its arguments before running, which clearly negates a Church numeral.

and

:((!)~^)*
 (     )   Define function:
     ~^      Execute its first argument with:
  (!)          false
               {and implicitly, our second argument}
        *  Edit the newly defined function by pre-composing it with:
:            {the most recently defined function}, without destroying it

Pytanie pozwala zdefiniować funkcje w kategoriach innych funkcji. Definiujemy „i” dalej, ponieważ im niedawno „nie” zostało zdefiniowane, tym łatwiej jest z niego korzystać. (Nie odejmuje się to od naszego wyniku, ponieważ w ogóle nie nazywamy „nie”, ale oszczędza bajty po ponownym zapisaniu definicji. Jest to jedyny raz, gdy jedna funkcja odnosi się do innej, ponieważ odnosi się do dowolnej funkcji ale ostatnio zdefiniowany kosztowałby zbyt wiele bajtów).

Oto definicja and x y = (not x) false y. Innymi słowy, jeśli not x, to wrócimy false; w przeciwnym razie wracamy y.

lub

(:^)
(  )  Define function:
 :      Copy the first argument
  ^     Execute the copy, with arguments
          {implicitly, the original first argument}
          {and implicitly, our second argument}

@Nitrodon wskazał w komentarzach, które or x y = x x ysą zwykle krótsze niż or x y = x true y, i okazuje się, że jest to poprawne również w przypadku niedociążenia. Naiwna implementacja tego byłaby (:~^), ale możemy oderwać się od dodatkowego bajtu, zauważając, że nie ma znaczenia, czy uruchomimy oryginalny pierwszy argument, czy jego kopię, wynik jest taki sam w obu przypadkach.

Niedociążenie nie obsługuje curry w zwykłym znaczeniu tego słowa, ale takie definicje sprawiają, że wygląda tak! (Sztuczka polega na tym, że niewykorzystane argumenty po prostu się trzymają, więc wywołana funkcja zinterpretuje je jako własne argumenty.)

implikuje

(~(!)~^(~)~*)
(           )  Define function:
 ~               Swap arguments
     ~^          Execute the new first (original second) argument, with argument:
  (!)              false
                   {and implicitly, our second argument}
       (~)~*     Run "not" on the result

Stosowana tutaj definicja to implies x y = not (y false x). Jeśli y jest prawdziwe, upraszcza to not false, tj true. Jeśli y jest fałszywe, upraszcza to not x, dając nam tabelę prawdy, której chcemy.

W tym przypadku używamy notponownie, tym razem przepisując kod zamiast odwoływać się do niego. Jest napisany bezpośrednio, jak (~)~*bez nawiasów wokół, więc jest wywoływany, a nie definiowany.

Xor

(()~(~)~^~*)
(          )  Define function:
   ~   ~^       Execute the first argument, with arguments:
    (~)           "swap arguments"
 ()               identity function
         ~*     Precompose the second argument with {the result}

Tym razem oceniamy tylko jeden z naszych dwóch argumentów i używamy go do ustalenia, co skomponować na drugim argumencie. Niedociążenie pozwala ci grać szybko i luźno z arity, więc używamy pierwszego argumentu, aby wybierać między dwiema dwuargumentowymi funkcjami z dwoma zwrotami; zamiana argumentów, która zwraca je obie, ale w odwrotnej kolejności, oraz funkcja tożsamości, która zwraca je obie w tej samej kolejności.

Gdy pierwszy argument jest prawdziwy, tworzymy zredagowaną wersję drugiego argumentu, który zamienia swoje argumenty przed uruchomieniem, tj. Wstępnie składa się z „argumentami zamiany”, tj not. Tak więc prawdziwy pierwszy argument oznacza, że ​​zwracamy notdrugi argument. Z drugiej strony fałszywy pierwszy argument oznacza, że ​​komponujemy z funkcją tożsamości, tzn. Nie robimy nic. Rezultatem jest wdrożenie xor.

Rubin, 82 - 4 = 78 bytes

f,t,a,n,i,o,x=%w(y:y x:x f:y t:f t:y y:t y:n[y]).map{|s|eval"->x,y=0{x==f ?#{s}}"}

Wypróbuj online!

Java 8, wynik: 360 358 319 271 233 (240–7) bajtów

interface J<O>{O f(O x,O y,J...j);}J t=(x,y,j)->x;J f=(x,y,j)->y;J n=(x,y,j)->j[0].f(y,x);J a=(x,y,j)->j[0].f(j[1].f(x,y),y);J o=(x,y,j)->j[0].f(x,j[1].f(x,y));J x=(x,y,j)->j[0].f(j[1].f(y,x),j[1].f(x,y));J i=(x,y,j)->j[0].f(j[1].f(x,y),x);

To było trudniejsze do osiągnięcia, niż myślałem, kiedy go zaczynałem. Zwłaszcza implies. W każdym razie to działa .. Prawdopodobnie można tu grać w golfa. EDIT: Ok, not re-using functions but just duplicating the same approach is a lot cheaper in terms of byte-count for Java.. And I get the full -7 bonus for not using any of the functions as well.

Wypróbuj online.

Wyjaśnienie:

// Create an interface J to create lambdas with 2 Object and 0 or more amount of optional
// (varargs) J lambda-interfaces, which returns an Object:
interface J<O>{O f(O x,O y,J...j);}

// True: with parameters `x` and `y`, always return `x`
J t=(x,y,j)->x;
// False: with parameters `x` and `y`, always return `y`
J f=(x,y,j)->y;

// Not: with parameters `x`, `y`, and `j` (either `t` or `f`), return: j(y, x)
J n=(x,y,j)->j[0].f(y,x);

// And: with parameters `x`, `y`, and two times `j` (either `t` or `f`), return:
//      j1(j2(x,y), y);
J a=(x,y,j)->j[0].f(j[1].f(x,y),y);

// Or: with parameters `x`, `y`, and two times `j` (either `t` or `f`), return:
//     j1(x, j2(x,y))
J o=(x,y,j)->j[0].f(x,j[1].f(x,y));

// Xor: with parameters `x`, `y`, and two times `j` (either `t` or `f`), return:
//      j1(j2(y,x), j2(x,y))
J x=(x,y,j)->j[0].f(j[1].f(y,x),j[1].f(x,y));

// Implies: with parameters `x`, `y`, and two times `j` (either `t` or `f`), return:
//          j1(j2(x,y), x)
J i=(x,y,j)->j[0].f(j[1].f(x,y),x);

C++17, 207−49=158 195 − 58 = 137 bytes

The linebreaks are unnecessary (other than the first two).

#define A auto
#define D(v,p)A v=[](A x,A y){return p;};
D(true_,x)
D(false_,y)
A not_=[](A f){return f(false_,true_);};
D(and_,x(y,false_))
D(or_,x(true_,y))
D(xor_,x(not_(y),y))
D(implies,x(y,true_))

Try it online!

Unit-tested with assertions such as:

static_assert('L' == true_('L', 'R'));
static_assert('R' == not_(true_)('L', 'R'));
static_assert('L' == and_(true_, true_)('L', 'R'));
static_assert('L' == or_(true_, true_)('L', 'R'));
static_assert('R' == xor_(true_, true_)('L', 'R'));
static_assert('L' == implies(true_, true_)('L', 'R'));

UPDATED: formerly I'd had

A not_=[](A f){return[f](A x,A y){return f(y,x);};};

but Roman's answer pointed the way to the shorter version. Notice that now not_(std::plus<>) is ill-formed, where formerly it was equivalent to std::plus<>; but since std::plus<> doesn't "represent a Church boolean," I think either behavior is okay by the rules.

Forth (gforth), 133 bytes - 7 = 126 122

: j execute ;
: t drop ;
: f nip ;
: n ['] f ['] t rot j ;
: a dup j ;
: o over j ;
: x 2dup a n -rot o a ;
: m over n -rot a o ;

Try it online!

-4 bytes thanks to Quuxplusone

Initially I significantly overthought this, considering things like macros and literals, but then I realized that if I define things in terms of true and false (like I should have done in the first place), it gets much simpler.

Code explanation

\ Helper function to save some bytes
: j        \ define a new word
  execute  \ execute the word at the provided address
;          \ end word definition

\ True
: t        \ define a new word
  drop     \ drop the second argument
;          \ end the word

\ False
: f        \ define a new word
  nip      \ drop the first argument
;          \ end the word

\ Not - The "hardest" one because we have to reference true and false directly
: n        \ define a new word
  ['] f    \ get address of false
  ['] t    \ get the address of true
  rot      \ stick the input boolean back on the top of the stack
  j        \ call the input boolean, which will select the boolean to return
;          \ end the word

\ And 
: a        \ define a new word
  dup      \ duplicate the 2nd input value
  j        \ call the 2nd input on the first and second input
;          \ end the word

\ Or
: o        \ define a new word
  over     \ duplicate the 1st input value
  j        \ call the 1st input on the first and second input
;          \ end the word

\ Xor
: x        \ define a new word
  2dup     \ duplicate both of the inputs
  a n      \ call and, then not the result (nand)
  -rot     \ move the result behind the copied inputs
  o a      \ call or on the original inputs, then call and on the two results
;          \ end the word

\ Implies
: m        \ define a new word
  over     \ duplicate the 1st input value
  n        \ call not on the 1st input value
  -rot     \ move results below inputs
  a o      \ call and on the two inputs, then call or on the two results
;          \ end the word

SKI-calculus + C combinator, 36 bytes

true=K
false=SK
not=C
and=CC(SK)
or=CIK
xor=C(CIC)I
implies=CCK

I don't actually know of any interpreter that allows you to define additional combinators in terms of previous ones, so I had to test this using http://ski.aditsu.net/ by pasting in the desired combinators e.g. CCKK(SK)pq outputs q, showing that K does not imply SK.

Julia 1.0, 36 bytes

(b::Bool)(x,y)=b ? x : y;i(x,y)=!x|y

I don't know if that counts, I'm actually just overloading the native Bool type to be callable, so I get most of the logic gates for free. Unfortunately, Julia doesn't have an implies gate, so I had to write my own function.

Try it online!

Perl 6, 120 106 102 101 bytes

-1 byte thanks to Jo King

my (\t,\f,&n,&a,&o,&i,&x)={@_[0]},{@_[1]},|<f,t &^v,f t,&^v &^v,t n(&^v),&v>>>.&{"&\{\&^u($_)}".EVAL}

Try it online!

C++17, 202−49=153 193 − 58 = 135 bytes

Inspired by the comment-discussion of what counts as a 2-ary function anyway, here's a curried version of my previous C++17 solution. It's actually shorter because we can use the same macro to define not_ as to define all the other functions!

#define D(v,p)auto v=[](auto x){return[=](auto y){return p;};};
D(true_,x)
D(false_,y)
D(not_,x(false_)(true_)(y))
D(and_,x(y)(false_))
D(or_,x(true_)(y))
D(xor_,x(not_(y))(y))
D(implies,x(y)(true_))

Try it online!

This one is tested with assertions like

static_assert('R' == and_(true_)(false_)('L')('R'));
static_assert('L' == or_(true_)(false_)('L')('R'));

Notice that or_ is defined as effectively

auto or_=[](auto x){return[=](auto y){return x(true_)(y);};};

We could define or_ more "concisely" as

auto or_=[](auto x){return x(true_);};

but that would cost us because we wouldn't get to use the D macro anymore.

APL (dzaima/APL), 47 bytes^SBCS

Based on Jonah's J solution.

true and false are infix functions, not is a suffix operator, and the rest are infix operators.

true←⊣
false←⊢
and←{⍺(⍶⍹false)⍵}
not←⍨
or←{⍺(true⍶⍹)⍵}
xor←{⍺(⍶not⍹⍶)⍵}
implies←{⍺(⍹⍶true)⍵}

As per OP, this counts everything from and including ← to the end of each line, and counts each call a previous definition as a single byte.

Try it online!

true and false are the left and right identity functions.

not simply swaps the arguments of its operand function.

The rest implement the decision tree:

and uses the righthand function ⍹ to select the result of the lefthand function ⍶ if true, else the result of the false function.

or uses the lefthand function ⍶ to select the true if true, else the result of the righthand function ⍹.

xor uses the righthand function ⍹ to select the the negated result of the lefthand function ⍶not if true, else the result of the lefthand function.

implies uses the lefthand function ⍶ to select the result of the righthand function ⍹ if true, else the result of the true function.

Stax, 34 bytes

¿S£↓♣└²≡é♫Jíg░EèΩRΦ♂°┤rà╝¶πï╡^O|Θà

Run and debug it at staxlang.xyz!

Pushes a bunch of blocks to the stack. Each block expects its last argument atop the stack, followed in reverse order by the rest.

Unpacked (41 bytes):

{sd}Y{d}{y{d}a!}X{ya!}{b!}{cx!sa!}{sx!b!}

Each pair of { } is a block. I used the two registers X and Y to hold true and not so I could access 'em easily later. Unfortunately, false couldn't simply be a no-op, as that would leave the stack cluttered and mess up a single XOR case.

Test suite, commented

false
{sd}    stack:   x y
 s      swap:    y x
  d     discard: y

true
{d}    stack:   x y
 d     discard: x

not
{y{d}a!}    stack:  p
 y{d}       push:   p f t
     a      rotate: f t p
      !     apply:  p(f,t)

and
{ya!}    stack:  p q
 y       push:   p q f
  a      rotate: q f p
   !     apply:  p(q,f)

or
{b!}    stack:  p q
 b      copies: p q p q
  !     apply:  p q(q,p)

xor
{cx!sa!}    stack:  p q
 c          copy:   p q q
  x!        not:    p q nq
    s       swap:   p nq q
     a      rotate: nq q p
      !     apply:  p(nq,q)

implies
{sx!b!}    stack:  p q
 s         swap:   q p
  x!       not:    q np
    b      copies: q np q np
     !     apply:  q np(np,q)

Befunge-98, 105 77 65 bytes

Playing further with the notion of "function" in languages without functions... here's a Befunge-98 version of Church booleans!

In this constrained dialect of Befunge-98, a program consists of a series of "lines" or "functions," each of which begins with a >(Go Right) instruction in column x=0. Each "function" can be identified with its line number (y-coordinate). Functions can take input via Befunge's stack, as usual.

Line 0 is special, because (0,0) is the starting IP. To make a program that executes line L, just place instructions on line 0 that, when executed, fly the instruction pointer to (x=L, y=0).

The magic happens on line 1. Line 1, when executed, pops a number L from the stack and jumps to line number L. (This line had previously been > >>0{{2u2}2}$-073*-\x, which can "absolute jump" to any line; but I just realized that since I know this line is pegged to line 1, we can "relative jump" L-1 lines in a heck of a lot less code.)

Line 2 represents Church FALSE. When executed, it pops two numbers t and f from the stack and then flies to line number f.

Line 3 represents Church TRUE. When executed, it pops two numbers t and f from the stack and then flies to line number t.

Line 6, representing Church XOR, is innovative. When executed, it pops two numbers a and b from the stack, and then flies to line a with stack input NOT EXEC b. So, if a represents Church TRUE, the result of a NOT EXEC b will be NOT b; and if a represents Church FALSE, the result of a NOT EXEC b will be EXEC b.

Here's the ungolfed version with test harness. On line 0, set up the stack with your input. For example, 338 means IMPLIES TRUE TRUE. Make sure the closing x appears at exactly (x,y)=(0,15) or else nothing will work! Also make sure your stack setup begins with ba, so that the program will actually terminate with some output.

Try it online!

>  ba 334  0f-1x
> >>1-0a-\x             Line 1: EXEC(x)(...) = goto x
> $^< <            <    Line 2: FALSE(t)(f)(...) = EXEC(f)(...)
> \$^                   Line 3: TRUE(t)(f)(...) = EXEC(t)(...)
> 3\^                   Line 4: OR(x)(y)(...) = EXEC(x)(TRUE)(y)(...)
> 3\2\^                 Line 5: NOT(x)(...) = EXEC(x)(FALSE)(TRUE)(...)
> 1\5\^                 Line 6: XOR(x)(y)(...) = EXEC(x)(NOT)(EXEC)(...)
> 2>24{\1u\1u\03-u}^    Line 7: AND(x)(y)(...) = EXEC(x)(y)(FALSE)(...)
> 3^                    Line 8: IMPLIES(x)(y)(...) = EXEC(x)(y)(TRUE)(...)

> "EURT",,,,@
> "ESLAF",,,,,@

Here's the version whose bytes I counted.

>>>1-0a-\x
>$^<< }u-30\<
>\$^
>3\^\
>3\2^
>1\5^
>2>24{\1u\1u^
>3^

Notice that to define a function in this dialect you don't mention its name at all; its "name" is determined by its source location. To call a function, you do mention its "name"; for example, XOR (6) is defined in terms of NOT and EXEC (5 and 1). But all my "function names" already take only one byte to represent. So this solution gets no scoring adjustments.