# Church booleans

A Church boolean is a function that returns x for true and y for false where x is the first argument to the function and y is the second argument to the function. Further functions can be composed from these functions which represent the and not or xor and implies logical operations.

# Challenge

Construct the Church booleans and and not or xor and implies Church gates in a language of your choice. and or and xor should take in two functions (representing Church booleans) and return a function (representing another Church boolean). Likewise, not should invert the function it takes and the implies gate should perform boolean implies logic where the first argument implies the second.

# Scoring

The total length of all of the code required to make Church true and false in your language and the and not or xor and implies Church gates excluding the function's name. (for example, false=lambda x,y:y in Python would be 13 bytes). You can reuse these names later in your code with them counting 1 byte toward the byte total of that gate.

# Pseudo code Examples:

The functions you create should be able to be called later in your code like so.

true(x, y) -> x
false(x, y) -> y
and(true, true)(x, y) -> x
and(true, false)(x, y) -> y
# ... etc
• Do we have to treat the function inputs (or closest substitutes) as black-box functions, or can we inspect the code within? And must the return values of the logical operations be the same functions as previously defined as the Church booleans, or can they be something else which does the same thing? – Unrelated String Aug 19 '19 at 19:18
• @JonathanAllan I edited it so it was correct. The prompt is as it should be now. – Ryan Schaefer Aug 19 '19 at 21:27
• Can we take lists as arguments (e.g. true([x, y]), and([true, true])([x, y]))? – ar4093 Aug 20 '19 at 5:59
• @RyanSchaefer I think you should reconsider allowing the arguments to be in an ordered list, as one could simply wrap the arguments at the beginning of the solutions. I don't think that requiring that does anything to improve this challenge (in fact I think it limits interesting golfing potential). Of course, this is just my opinion, and it is fine if you do not agree. – FryAmTheEggman Aug 20 '19 at 17:58
• The scoring is rather confusing. Wouldn't it be better to let people submit anonymous functions, but if they use them in other parts they have to assign them, just like usual – Jo King Aug 21 '19 at 11:09

# Binary Lambda Calculus, 13.875 12.875 bytes (103 bits)

Binary Lambda Calculus Language (BLC) by John Tromp is basically an efficient serialization format for lambda calculus. It is a great fit for this task, as Church notation is even the "idiomatic" way to work with booleans in BLC.

I used the following lambda functions for the combinators, some of which I copied and golfed from the Haskell answer:, which were found by an exhaustive search with a proof limit of 20 β-reductions for each case. There is a good chance these are shortest possible.

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))

These translate to the following (binary) BLC code sequences:

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

Functions above are in total 111 bits long (13.875 bytes) 103 bits long (12.875 bytes). They don't need to be aligned to byte boundaries to be used inside a program, so it makes sense to count fractional bytes.

There is no code re-use between the combinators, because there are no variables/references/names in BLC - everything had to be copied over. Still, the efficiency of the encoding makes for quite a terse representation.

• I don't know blc, but will And: (\a \b a b a) work? – tsh Aug 21 '19 at 2:34
• Yes, it works. I actually used this formula for my code sequences. I just forgot to update the corresponding lambda function (now corrected). The equivalent function works for Or: \a \b a a b. It is longer than the one I used in BLC though. – Pavel Potoček Aug 21 '19 at 11:41

# Haskell, 50 - 6 = 44 bytes

-1 byte thanks to Khuldraeseth na'Barya, and -1 byte thanks to Christian Sievers.

t=const
f=n t
n=flip
a=n n f

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.

• Since C++ is case-sensitive, how about using True and False instead of true_ and false_? And similar for the other operators. That will save 12 bytes. – G. Sliepen Aug 24 '19 at 14:08
• @G.Sliepen: OP's scoring algorithm already takes into account that identifiers are effectively one character long. Quote: "The total length of all of the code required to make Church true and false in your language and the and not or xor and implies Church gates excluding the function's name. (for example, false=lambda x,y:y in Python would be 13 bytes). You can reuse these names later in your code with them counting 1 byte toward the byte total of that gate." – Quuxplusone Aug 24 '19 at 15:39
• Ah, I missed that. – G. Sliepen Aug 24 '19 at 17:09

# APL (dzaima/APL), 47 bytesSBCS

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

true
{d}    stack:   x y

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, 10577 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.