# 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
o=(t) x=(n>>=) i=o.n  Try it online! • Side note: you can define Show instances for const and const id and print the church booleans directly. Try it online!. – nimi Aug 19 '19 at 21:08 • a can be shortened. – Khuldraeseth na'Barya Aug 19 '19 at 22:20 • Why is no one using f=n t? – Christian Sievers Aug 20 '19 at 0:25 • You can save a byte by using t=pure instead of t=const. – Joseph Sible-Reinstate Monica Aug 20 '19 at 2:24 • @JosephSible I tried that initially. Unfortunately, t=pure will cause an error when I try to apply a, o, x, or i to it. Declaring the type of t to fix this costs more bytes than just using t=const. – Nitrodon Aug 20 '19 at 4:26 # Python 2, (-3?) 101 95 bytes David Beazley eat your heart out! -6 thanks to Chas Brown (moved the repeated : into the join text >.<) 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())  Try it online! I think it might be 95 - 3 because I don't reuse the functions A, X, or I, but I use a single = for assignment (in front of lambda). Maybe I cant remove any; maybe I even get to remove 3.5? • @Ryan Schaefer can I remove three or does my use of exec mean I cannot? I can see going either way - I don't reuse A, X, or I but the code wont work without them. (Maybe I even get to remove 3.5?!) – Jonathan Allan Aug 19 '19 at 22:12 • 95 bytes (before the -3) – Chas Brown Aug 20 '19 at 2:50 • Thanks @Chas! The colon that slipped through the net :) Good job on the replace for -1 BTW – Jonathan Allan Aug 20 '19 at 11:36 # JavaScript (Node.js), 9286 83 - 7 = 76 bytes 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)  Try it online! Link includes basic test cases. Edit: Saved 6 9 bytes thanks to @tsh. • seems you cannot claim this as -7 since t, f, n are used. – tsh Aug 20 '19 at 9:40 • @tsh That's not how I understand the scoring system; it explicitly excludes the name in the definition, although the name in the use costs 1 byte. – Neil Aug 20 '19 at 10:02 • @Neil you can't claim the byte discount for function names that are called by your code (t, f, and n in your case). – asgallant Aug 20 '19 at 21:46 • @asgallant no. It’s no bytes for the name and 1 byte when it is used later. ‘T f n a o x i’ are no bytes then 1 byte when used later. I wanted to improve readability but now I realize I should’ve just left it fully golfed and it’s too late to change it now – Ryan Schaefer Aug 20 '19 at 23:58 • @RyanSchaefer where is that rule? I've never seen it done like that. – asgallant Aug 22 '19 at 16:16 # Python 2, 133 - 6 = 127 94 bytes 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:')  Try it online! Shamelessly stealing the sneaky idea behind Jonathan Allan's answer; no bytes deducted though. • I was going to post an answer to my own question but I was unsure if this was allowed and I think that this is against the spirit of it. So I think I will just guide you along instead. Instead of using lists, is there anyway you can use the functions that are being input themselves and the specific manner in which they return their inputs to shorten the code? – Ryan Schaefer Aug 19 '19 at 19:18 • I'd wager that although the answer is yes, it would be considerably longer in Python. – Unrelated String Aug 19 '19 at 19:19 • I stand corrected – Unrelated String Aug 19 '19 at 19:28 • @Mr.Xcoder you are correct, I had the wrong number of bytes for the example function. They would be allowed to remove 6 bytes though for the names of the functions. – Ryan Schaefer Aug 19 '19 at 20:56 • @Mr. Xcoder: Modified as per your observations. – Chas Brown Aug 20 '19 at 1:05 # 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]  • Pretty sure the newlines are necessary to separate function definitions. Also you reference t f and n in other function definitions so you cannot deduct those ones, so 61-4=57. – Jonathan Allan Aug 22 '19 at 10:02 • @JonathanAllan I've re-read the scoring instructions and agree that the newlines should count, thanks. I disagree with your second part: when I reuse the names, I do indeed count them as "1 byte toward the byte total of that gate", which is implicit here as I use 1-byte names. As my reading of the instructions goes, there is no mention of further counting them as one byte toward the total of the original definition as well. So I'm going with N-7 bytes. Also, another comment by the OP clarifies: "It’s no bytes for the name and 1 byte when it is used later." – Roman Aug 22 '19 at 10:32 • I read "1 byte later" to mean usage within another function costs a byte. This aligns with how others have scored too. – Jonathan Allan Aug 22 '19 at 11:21 • @JonathanAllan I'm less interested in exegesis and more in code golfing 😀 – Roman Aug 22 '19 at 12:22 # 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  The question permits defining functions in terms of other functions. We define "and" next because the more recently "not" has been defined, the easier it is to use it. (This doesn't subtract from our score, because we aren't naming "not" at all, but it saves bytes over writing the definition out again. This is the only time that one function refers to another, because referring to any function but the most recently defined would cost too many bytes.) The definition here is and x y = (not x) false y. In other words, if not x, then we return false; otherwise, we return y. ### or (:^) ( ) Define function: : Copy the first argument ^ Execute the copy, with arguments {implicitly, the original first argument} {and implicitly, our second argument}  @Nitrodon pointed out in the comments that or x y = x x y is normally shorter than or x y = x true y, and that turns out to be correct in Underload as well. A naive implementation of that would be (:~^), but we can golf off an additional byte by noting that it doesn't matter whether we run the original first argument or the copy of it, the result is the same either way. Underload doesn't actually support currying in the usual sense, but definitions like this make it look like it does! (The trick is that non-consumed arguments just stick around, so the function you call will interpret them as its own arguments.) ### implies (~(!)~^(~)~*) ( ) Define function: ~ Swap arguments ~^ Execute the new first (original second) argument, with argument: (!) false {and implicitly, our second argument} (~)~* Run "not" on the result  The definition used here is implies x y = not (y false x). If y is true, this simplifies to not false, i.e. true. If y is false, this simplifies to not x, thus giving us the truth table we want. In this case, we're using not again, this time by rewriting its code rather than referencing it. It's just written directly as (~)~* without parentheses around it, so it gets called rather than defined. ### xor (()~(~)~^~*) ( ) Define function: ~ ~^ Execute the first argument, with arguments: (~) "swap arguments" () identity function ~* Precompose the second argument with {the result}  This time, we're evaluating only one of our two arguments, and using it to determine what to compose onto the second argument. Underload lets you play fast and loose with arity, so we're using the first argument to choose between two two-argument two-return functions; the argument swap that returns them both but in the opposite order, and the identity function that returns them both in the same order. When the first argument is true, we therefore produce an edited version of the second argument that swaps its arguments before running, i.e. precompose with "swap arguments", i.e. not. So a true first argument means we return not the second argument. On the other hand, a false first argument means we compose with the identity function, i.e. do nothing. The result is an implementation of xor. • or x y = x x y saves some bytes over or x y = x true y. – Nitrodon Aug 23 '19 at 16:47 • Underload is often counter-intuitive when it comes to replacing literals with reused variables, but in this case, that transformation turns out to save more bytes than expected, rather than fewer. Thanks for the improvement! – ais523 Aug 23 '19 at 21:20 # Ruby, 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}}"}  Try it online! # Java 8, score: 360358319271 233 (240-7) bytes 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);  This was trickier to accomplish than I thought when I started it.. Especially the implies. Anyway, it works.. Can probably be golfed a bit here and there. 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. Try it online. Explanation: // 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);  ## 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. # 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. • Shouldn't "other than the first one" be updated to "other than the first two"? – L. F. Aug 20 '19 at 10:12 • @L.F.: Absolutely correct. Updated. :) – Quuxplusone Aug 20 '19 at 14:46 # 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  • You repeat the long word execute three times. Defining the shorthand : j execute ; would save you 4 bytes. – Quuxplusone Aug 24 '19 at 18:28 # 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! • I think you still need to include the overloaded operators in your submission... but the scoring doesn't count them, since they're just names? So it would be +6 bytes from the newlines? I'm not too sure how the scoring works with this challenge – Jo King Aug 21 '19 at 11:01 • I'm not 100% sure how it works either, but having to include code that literally does nothing doesn't make any sense to me. – Simeon Schaub Aug 21 '19 at 11:23 • Even if the code is already declared, then you still have to include it, otherwise every other golfing language submission would be zero bytes. You just don't have to assign it to anything – Jo King Aug 21 '19 at 11:31 # Perl 6, 120106102 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.

• 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.