(~!)(!)((~)~*):((!)~^)*(:^)(~(!)~^(~)~*)(()~(~)~^~*)
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.
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