Church Booleans



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.


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.


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

Ryan Schaefer

Posted 2019-08-19T17:31:47.190

Reputation: 561

2Do 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 – 2019-08-19T19:18:36.670

@UnrelatedString the inputs to the function are essentially a cat program that copy input to output, but based on if they are true or false. For example, a true church boolean takes in two inputs (which chould be "foo" and 3, basically anything) and returns the first argument ("foo"). They don't have to be the exact functions you previously described, but I would imagine it would save a lot of space if you did this. – Ryan Schaefer – 2019-08-19T19:21:14.873

@JonathanAllan I added it later, and I am regretting it. I should've just kept it to purely gates. – Ryan Schaefer – 2019-08-19T21:23:22.833

1@JonathanAllan I edited it so it was correct. The prompt is as it should be now. – Ryan Schaefer – 2019-08-19T21:27:49.903

2Can we take lists as arguments (e.g. true([x, y]), and([true, true])([x, y]))? – ar4093 – 2019-08-20T05:59:09.527

@ar4093 I am going to rule no as technically this isn't true to the underlying lambda calculus in this question. The proposed functions you have take in 1 argument not 2 like a true Church Boolean. – Ryan Schaefer – 2019-08-20T13:08:27.233

@ar4093 FWIW, I don't see any fundamental problem with saying "Define an N-ary _F_unction as a unary function whose argument must be a list of N items. Then the _F_unctions corresponding to the Church booleans are..." I mean, the top-voted Haskell answer already exploits currying ("Define a 2-ary _F_unction as a unary function which returns a unary function. Then the _F_unctions corresponding to the Church booleans are..."). Sometimes currying is idiomatic; sometimes taking-a-list-of-args is idiomatic. And heck, sometimes golfed solutions are unidiomatic. ;) – Quuxplusone – 2019-08-20T14:54:49.873

2@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 – 2019-08-20T17:58:29.763

Please can you double-check the score on my Node.js answer as three people have now disagreed with my understanding of your paragraph on scoring. – Neil – 2019-08-20T23:54:59.057

1The 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 – 2019-08-21T11:09:14.127

@JoKing I’ve stated my opinion that i would change the scoring if I could but it’s too late now because of all the answers. – Ryan Schaefer – 2019-08-21T12:25:38.897

FWIW, even though I see a lot of people apparently confused about the scoring, I think the rule is great. The rule recognizes that any identifier can be golfed down to one byte, so it doesn't penalize people for using nice function names like true, false, xor. (OTOH, it makes it harder to count bytes because the code whose bytes you count is hardly ever the same as the code that you run. So that's a downside.) – Quuxplusone – 2019-08-24T18:31:35.253



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.

Pavel Potoček

Posted 2019-08-19T17:31:47.190

Reputation: 156

1I don't know blc, but will And: (\a \b a b a) work? – tsh – 2019-08-21T02:34:53.147

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 – 2019-08-21T11:41:57.967


Haskell, 50 - 6 = 44 bytes

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

f=n t
a=n n f

Try it online!


Posted 2019-08-19T17:31:47.190

Reputation: 9 181


Side note: you can define Show instances for const and const id and print the church booleans directly. Try it online!.

– nimi – 2019-08-19T21:08:47.850

a can be shortened. – Khuldraeseth na'Barya – 2019-08-19T22:20:08.377

4Why is no one using f=n t? – Christian Sievers – 2019-08-20T00:25:00.230

3You can save a byte by using t=pure instead of t=const. – Joseph Sible-Reinstate Monica – 2019-08-20T02:24:28.657

4@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 – 2019-08-20T04:26:52.933

how about f=seq;t=n f – H.PWiz – 2019-08-21T11:12:00.300

@H.PWiz I didn't know about that function, but from what I've been able to find online, it would depend on whether I need to handle as an input. – Nitrodon – 2019-08-21T17:07:29.947


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?

Jonathan Allan

Posted 2019-08-19T17:31:47.190

Reputation: 67 804

@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 – 2019-08-19T22:12:36.513

95 bytes (before the -3) – Chas Brown – 2019-08-20T02:50:36.113

Thanks @Chas! The colon that slipped through the net :) Good job on the replace for -1 BTW – Jonathan Allan – 2019-08-20T11:36:08.753


JavaScript (Node.js), 92 86 83 - 7 = 76 bytes


Try it online! Link includes basic test cases. Edit: Saved 6 9 bytes thanks to @tsh.


Posted 2019-08-19T17:31:47.190

Reputation: 95 035

1seems you cannot claim this as -7 since t, f, n are used. – tsh – 2019-08-20T09:40:07.067

1@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 – 2019-08-20T10:02:12.803

@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 – 2019-08-20T21:46:27.650

2@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 – 2019-08-20T23:58:00.387

@RyanSchaefer where is that rule? I've never seen it done like that. – asgallant – 2019-08-22T16:16:55.933


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.

Chas Brown

Posted 2019-08-19T17:31:47.190

Reputation: 8 959

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 – 2019-08-19T19:18:35.363

I'd wager that although the answer is yes, it would be considerably longer in Python. – Unrelated String – 2019-08-19T19:19:56.227

I stand corrected – Unrelated String – 2019-08-19T19:28:07.680

@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 – 2019-08-19T20:56:32.270

@Mr. Xcoder: Modified as per your observations. – Chas Brown – 2019-08-20T01:05:39.437


J, 67 bytes - 7 = 60

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.


Posted 2019-08-19T17:31:47.190

Reputation: 8 729


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


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]


Posted 2019-08-19T17:31:47.190

Reputation: 1 190

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 – 2019-08-22T10:02:50.297

@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 – 2019-08-22T10:32:53.207

I read "1 byte later" to mean usage within another function costs a byte. This aligns with how others have scored too. – Jonathan Allan – 2019-08-22T11:21:02.197

@JonathanAllan I'm less interested in exegesis and more in code golfing – Roman – 2019-08-22T12:22:36.030


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.



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


( )   Define function:
 !      Delete first argument

This one's even more straightforward.


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


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


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


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


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


Posted 2019-08-19T17:31:47.190

Reputation: 11

or x y = x x y saves some bytes over or x y = x true y. – Nitrodon – 2019-08-23T16:47:27.600

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 – 2019-08-23T21:20:20.130


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!


Posted 2019-08-19T17:31:47.190

Reputation: 11 099


Java 8, score: 360 358 319 271 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.


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

Kevin Cruijssen

Posted 2019-08-19T17:31:47.190

Reputation: 67 575


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;};
A not_=[](A f){return f(false_,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.


Posted 2019-08-19T17:31:47.190

Reputation: 625

Shouldn't "other than the first one" be updated to "other than the first two"? – L. F. – 2019-08-20T10:12:19.913

@L.F.: Absolutely correct. Updated. :) – Quuxplusone – 2019-08-20T14:46:59.863


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


Posted 2019-08-19T17:31:47.190

Reputation: 1 361

1You repeat the long word execute three times. Defining the shorthand : j execute ; would save you 4 bytes. – Quuxplusone – 2019-08-24T18:28:01.763


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!


Posted 2019-08-19T17:31:47.190

Reputation: 10 037


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;};};

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.


Posted 2019-08-19T17:31:47.190

Reputation: 625

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 – 2019-08-24T14:08:03.180

@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 – 2019-08-24T15:39:20.313

Ah, I missed that. – G. Sliepen – 2019-08-24T17:09:52.230


SKI-calculus + C combinator, 36 bytes


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 by pasting in the desired combinators e.g. CCKK(SK)pq outputs q, showing that K does not imply SK.


Posted 2019-08-19T17:31:47.190

Reputation: 95 035


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!


Posted 2019-08-19T17:31:47.190

Reputation: 381

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 – 2019-08-21T11:01:08.790

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. – user3263164 – 2019-08-21T11:23:47.473

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 – 2019-08-21T11:31:38.693


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.


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.


Posted 2019-08-19T17:31:47.190

Reputation: 37 779


Stax, 34 bytes


Run and debug it at!

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


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

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

{d}    stack:   x y
 d     discard: x

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

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

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

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

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

Khuldraeseth na'Barya

Posted 2019-08-19T17:31:47.190

Reputation: 2 608


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.

>$^<< }u-30\<

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.


Posted 2019-08-19T17:31:47.190

Reputation: 625