Tips for golfing in Underload

Question

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)

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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.