# Tips for golfing in Underload

Underload is a stack-based semi-functional tarpit created by ais523. I've recently been trying to golf in it, as it's a surprisingly elegant language.

What tips do you have for golfing in Underload? (One tip per answer)

• I like that the only form of control flow is an eval command, I've never seen a language like that before. – ETHproductions Feb 11 '17 at 2:17

## Use * for output

Because you can output by leaving a string on the stack, it might be useful to accumulate the string by using * rather than outputting with S. Say your challenge was "take a string and append a space", the way to do it with output would be:

S( )S


The way to do it with *, on the other hand is one byte shorter:

( )*


The problem is that if your output has a lot of accumulation, it might cost bytes to deal with the output element on the stack.

# Use a dictionary of repeatedly reused functions

If you need to use a piece of code a lot, it makes sense to store that code on the stack and duplicate-and-eval it every now and then. So far, that's just normal Underload programming. Unfortunately, keeping a value around on the stack for a long time is difficult and tends to cause your code to become verbose, and that's true even if the value is a function rather than data. This gets a lot worse if you have multiple functions that need to be reused repeatedly.

In the sort of larger program that might benefit from several reused functions, a solution you can use is to instead make one large function that can fulfil any of their purposes depending on the way it's called (either based on what's underneath it on the stack, or via using longer calling sequences than just ^; a carefully written function can distinguish ^^ from ^:^ from ^*^ from ^~^, giving you four distinct, fairly short sequences). You can also store other useful things, such as strings that you use multiple times, in this "dictionary". Note that if you use the dictionary heavily, it may make sense to make it a kind of quine, pushing a copy of itself back onto the stack, so that you don't need to manually copy it with : to be able to use it without losing the ability to use it in the future.

• I would go mad long before I got any program big enough in Underload that this became an issue :P – Esolanging Fruit Feb 14 '17 at 6:55
• I once wrote some examples on the esolangs page of how to do dictionaries with my preferred ^!!!!^ style lookup (which I've also used in several other examples on the page, especially in the minimization section.) Although that might not give the shortest lookup. – Ørjan Johansen Apr 16 '17 at 3:25

# Choose data formats specialized to the operations the problem needs

As a simple example, the most commonly seen implementation of booleans are !() for false (i.e. integer 0), and the null string for true (i.e. integer 1), but if you have a problem that's heavily based around logical XOR, it might make more sense to use the null string for false, and ~ for true (this data format can be converted into any other boolean format using (false)~(true)~^!, and allows the very terse implementation * for XOR.

It's possible to take this general principle even further and use functions that your program will need later as part of your data values; that saves having to store the functions and data separately on the stack. This can make the control flow rather more confusing, but when golfing, maintainability often has to take a back seat, and it's not like Underload is all that usable anyway.

• I used to use (!) and (~!) for booleans, but your way seems better. – Esolanging Fruit Apr 16 '17 at 15:23

## "Dirty" Decrement

The functionally-pure way to decrement a Church numeral is to use the lambda calculus predecessor function:

\n.n(\p.\z.z($(pT))(pT))(\z.z0[whatever you define the predecessor of 0 to be])  Where 0 = \x.\y.y, T = \x.\y.x, and$ is the successor.

Rewritten in Underload, this is 28 bytes:

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


This is alright, but we can exploit some of Underload's useful properties, namely that :! and ()* do are no-ops. This means that, for a number n, :ⁿ!!()()*ⁿ (where cⁿ is c repeated n times) yields n-1. For example doing this for the Church numeral 3 yields this:

:::!!()()***


Removing no-op pairs, we get:

:*


Which is 2.

So this is the new and shorter predecessor operation:

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


This is 7 bytes shorter.

• That breaks on n=0 though. If you need that to work, (()~(:))~:(^!!())*~(*)~^**  is still 3 bytes shorter. – Ørjan Johansen Apr 16 '17 at 3:16
• @ØrjanJohansen Generally, you'd have a special case for n=0, because with Underload's numbers decrementing 0 makes no sense anyway. – Esolanging Fruit Apr 16 '17 at 15:15

# Put Unneeded Stack Values into the Program Space

Underload actually has two stacks—the stack of strings, and the stack of commands that make up the source code. Underload's ^ instruction lets us move strings from the former stack to the latter. By doing this, we can save a lot of unnecessary stack manipulation.

For example, say we have (a)(b)(c) on the main stack and we'd like to concatenate the bottom two elements, ignoring (c), to get (ab)(c). The naïve way to do this is to rotate the stack to get (c)(a)(b) and then concantenate and swap back:

a~a~*~a*^*~


This is bad. Using a~a~*~a*^ to rotate the stack like this is extremely costly, and should be avoided when possible. By putting (c) into the program space instead, this can be made four bytes shorter:

a(*)~*^


The idea is to take the instructions you'd like to execute and then add an instruction to push (c) back at the end, and then evaluate the result. This means that we don't have to worry about (c) until it's pushed back after we've finished.

• You can also write it as (*)~a*^, which I think is a bit more composable. Essentially ~a*^ is the dip command from Joy. – Ørjan Johansen Mar 8 '18 at 7:41