Redundancy, and how to avoid it

The other answers have covered various ways to ensure people can translate useful algorithms into concise code in a language. This answer will focus on the other side of this: reducing redundancy in a language by ensuring that concise code translates to distinct, useful algorithms.

This means minimising the number of programs that either behave identically to another program, or yield no useful computation - leaving space for useful programs to fill the gaps. In the general case, eliminating redundant programs entirely is equivalent to the Halting Problem, but I'll cover several ways this can be worked towards, some that have been implemented in golfing languages and some that, practically, cannot be.

Error cases

Throwing an error and halting execution, or yielding a null result due to some sort of error, are generally undesirable in a golfing language. Instead, we want to replace those error cases with useful functionality.

Type errors and overloading

The most common form of error case is when a built-in function receives arguments of the wrong type. For example, say we have a language with two types, lists and integers, and an addition builtin + that takes two numbers and adds them. Out of all possible programs, a reasonable amount will attempt to add two lists - so what can we do to make this behaviour useful?

This is called operator overloading, and the details of how to properly design it could fill a whole answer, but I'll give a few examples here:

• In Python, the + operator concatenates two lists, so [1, 2, 3] + [4, 5, 6] yields [1, 2, 3, 4, 5, 6]. This is the most general form of overloading: assigning related functions to an operator to add useful functionality and decrease the number of cases where it causes an error.
• In JavaScript, the + operator also concatenates two strings, and when given anything other than a pair of numbers, it will attempt to turn them into strings before concatenation. Lists are stringified by joining them with commas, so [1, 2, 3] + [4, 5, 6] becomes 1,2,34,5,6. In terms of intuitive language design, this is a bizarre and frequently criticised choice, but it is still objectively more useful for golfing than having the same operation throw an error, or return some null type. This is coercion: transforming the arguments of a builtin into some type that said builtin can use.
• In array languages like J, K and APL (along with many golfing languages), operations like addition will vectorise over arrays, applying over each pair of elements to yield an array of the results. This means that [1, 2, 3] + [4, 5, 6] yields [1 + 4, 2 + 5, 3 + 6] = [5, 7, 9]. This is vectorisation: implicitly applying a scalar function over every element of a list by default. Like all the methods of overloading in this list, it allows for code that wouldn't otherwise be possible: Instead of having to explicitly write out something like map(add, zip(list_a, list_b)), you can simply write list_a + list_b.
• Some languages will go even further with operator overloading: Husk is a statically typed golfing language, meaning that the types passed to each operator can be determined at parse time - and the way the program parses can even change based on the provided types. I won't elaborate much here, but you can think of this as overloading not just individual operators, but the entire program.

In general, overloading an operator to add useful behaviour is ^almost always going to make the language golfier - but not all overloads are created equal. I would consider Python's + operator on lists to be significantly more useful for code golf than JavaScript's: the former is a common operation, while the latter creates a specific format of string that's only useful in very niche circumstances. It's very easy to add things in language design, but difficult to remove them: If you're not sure what behaviour to assign to an overloaded operator, it's perfectly fine to leave it as an error case.

Syntax errors and a change of paradigm

The other common form of error, when considering the space of all possible programs, is that of invalid syntax. What if I leave a parenthesis unclosed, a structure missing its parts, or an operator with one argument where it needs two?

lyxal's answer touches on how we can implicitly add behaviour to these cases - for example, if an operator's missing arguments, with the given Python example print("Hello, "+), one possible way to define this behaviour could be to use the program's input as the other argument, treating it as print("Hello, "+input()).

Similarly, building off existing programming languages, strings can be automatically closed, parentheses provided where necessary, structures automatically completed, and other shortcuts provided to make syntax more concise. Japt, one of at least three golfing languages that spawned out of a frustration with String.fromCharCode, is a shortened form of JavaScript that has done exactly this, and for all its questionable design choices, it is a reasonably powerful golfing language.

But even with all these changes, the syntax and structure of conventional programming languages remains unwieldy for golfing purposes. Even if all the builtins are represented by a single byte each, extra code is required to transfer values between them. And that's why many golfing languages have decided to change paradigms altogether.

Let's consider a program that takes two integers, a and b, and computes (a + 7) * b. The graph of how we'd want the program to flow looks something like this:

^{made with tldraw}

The core of the program is those three nodes: 7, *, and + - and we'd like our language to require as little code as possible to transfer values between those nodes. But in a traditional programming language, this is still going to require something like (a+7)*b to make the graph explicit, including parentheses due to operator precedence. What if there was another way?

In the golfing language Fig, the code to do this is just three characters: *+7. Fig is a prefix-based language: each operator has a fixed arity (number of arguments taken), and reads that many tokens in front of it - for example, the snippet + 3 5 would evaluate to 8.

Once Fig has run out of tokens to parse, it implicitly reads input - so the operator + takes 7 as one of its arguments, and the first input, a, as the other, resulting in a + 7. The operator * then takes the result of that as its first argument, and the second input b as its second, resulting in (a + 7) * b, which is implicitly output.

Other golfing languages use different paradigms. The same code in Vyxal is 7+* - Vyxal uses a stack-based paradigm, where operations push and pop from a stack - 3 would push the number 3 to the stack, and + would pop two values from the stack and push their sum. So:

• 7 pushes 7 to the currently-empty stack, leaving the stack as [7]
• + attempts to pop two values from the stack. The first time, it takes 7; the second time, the stack is empty, so it takes the first input a. It then pushes their sum to the stack, leaving it as [a + 7].
• Finally, * pops two values, the first being a + 7 and the second being the second input b, and pushes their product (a + 7) * b. This is popped from the stack and implicitly output.

Jelly, meanwhile, uses a tacit paradigm similar to that of J and APL. I won't go into the details of how it works here (although the tutorial contains an explanation), but the same program is +7×, with × being multiplication. Other paradigms include Pip's infix precedence-based notation, and iogii's "circular programming", each of which provides different, concise ways to represent a program's graph.

Different paradigms have different advantages: For example, when computing (a + b) * (a - b), Vyxal has to use 4 characters, with an extra character of overhead necessary to manipulate its inputs - ₌+-*, while the way Jelly's chaining works allows it to use only 3 - +×_. These are trivial examples, but the more complex the graph, the more important the choice of paradigm becomes, and the more concise golfing paradigms become compared to traditional languages.

And the rest

There are a few other error cases that come up in golfing language design. For example, many languages will throw an error or return a null value when attempting to read past the ends of an array - in Javascript, [1, 2, 3, 4][5] will return undefined, and in Python, it will throw an error.

One behaviour golfing languages often assign to this is using modular indexing: wrapping indices around the array and essentially performing [1, 2, 3, 4][5 % 4], as the array has 4 items. There are a few more smaller cases like this, but I'll move on to the second part of this answer.

Redundant programs

Most of the issues I've mentioned up to this point are reasonably close to solved in current golfing languages - program graphs can be represented concisely with very little overhead. However, the issues I'll present here are very much still open problems.

Common operators and compression coding

Naturally, some built-in functions are going to be used more often than others - for example, although addition and base conversion might both be a single character, addition is going to be used significantly more. Statistically, it might be worth representing the former with a shorter encoding than the latter, perhaps using Huffman coding or similar.

However, we can go further. If we have a large corpus of existing code, we can train a custom compression algorithm on it, and this is precisely what Vyncode and Kamila Scewzyck's Jcram do for Vyxal and JavaScript respectively. Vyncode uses a range coding algorithm trained on common substrings, while Jcram uses a more complex approach tailored to JavaScript.

These are both fairly effective: Vyncode tends to shorten Vyxal code by 6-10%, and Jcram, given golfed JavaScript, produces an encoding that is not far off modern golfing language, despite having none of their common builtins. However, these still have their flaws.

First, while these tend to compress existing code well, they tend to still produce questionable code a lot of the time - try inputting a random string into Jcram's decompressor, for example - the chance that the result will be valid JS is extremely small. Second, they're unpredictable: The training set that they operate on is large enough that a human has no way to know which of several alternatives for a snippet produces the shortest compression.

Redundant builtins

If you have two builtins that are functionally identical in certain contexts, that means there's a whole family of programs that behave identically when the two characters are swapped. For example, Vyxal's addition builtin + concatenates two strings, but so does the list concatenation operator J. They both have other, distinct purposes, but in the context of two strings, the two are identical.

Most golfing languages do a fairly good job of keeping builtins distinct. However, when you allow two or more builtins in a row, many more redundant combinations emerge - I'll use Vyxal for the following examples, although these problems exist everywhere:

• Various combinations of stack builtins achieve either nothing, or very close to nothing. For example, _ is the pop builtin, so 0_ pushes and pops a 0, doing nothing. Similarly, :_ duplicates and pops the top of the stack.
• Some combinations of operators just do nothing, at least in most contexts: for example, N negates a number, so NN results in the original number. A similar case occurs with Ṙ (reverse), and you can also just have things like 0+ and 0-, adding/subtracting 0 to/from a number.
• Some combinations of operators behave identically to others - : pushes two copies of something to the stack, while D pushes three - so :: behaves the same as D, and :D behaves the same as D:.

Generally, it's just accepted that these issues exist, as long as they're not too obvious. But by carefully choosing builtins, it's possible to reduce these issues significantly. The golfing language nibbles fits each builtin into half a byte by default, so has a much smaller builtin space to play with - and because of that, it chooses to assign useful meanings to some otherwise-redundant combinations of operators. Through this careful choice of operators and leveraging static typing, Nibbles manages to be fairly competitive with other modern golfing languages.

Redundant structure

The main point I'll be covering here is something known as "unparseable nilads". Like how monads are functions of one argument and dyads are functions of two, nilads are functions of 0 arguments, i.e. constants - for example, 0, "hello", [] are all nilads. The issue occurs when we place a nilad somewhere where it can't usefully interact with the rest of the program.

Let's take the (a + 7) * b program from earlier in Vyxal - 7+* - and append a 0 to it to get 7+*0. Now, the program does the same computation as earlier - and then chucks a 0 on top, which is printed. The previous result is discarded, rendering everything before the nilad 0 useless.

Pretty much every golfing language has this problem in some form. Jelly will sometimes attempt to print those nilads in addition to the output; a certain version of Vyxal 3 will attempt to rearrange the program into something that uses the nilad, but often with redundancy; and some languages will just ignore nilads added in inaccessible places - but still leaving a redundant set of programs.

To some degree, we can eliminate these cases, by either giving meanings to these programs or disallowing them via program encoding. But just like how the redundancy of traditional programming languages can only be removed so much before a paradigm shift is required, to fully remove these structural issues, we need another shift.

To date, no golfing languages exist that fully handle these issues. However, some have been theorised: By encoding the structure of a program separately from the operators it uses, we can ensure the program graph has no redundant parts, which is the idea behind rydwolf's long-abandoned project catstruct. To be clear, this isn't a principle or a rule - just one idea of how certain redundancies could be addressed.

---

The last thing I'll address here is the idea of the language strangeness budget within golfing languages. Making a complex encoding necessarily makes a language more confusing to golf - and while quite a few golfing languages have a "literate mode", where the user writes out a sequence of builtins without having to manipulate the underlying encoding, the user still has to deal with the size of the encoding.

Similarly, choosing a builtin set that's overly large or overly simple may make it harder to pick up, and choosing an unusual paradigm may further steepen the learning curve (I will admit I still don't understand Brachylog.) Like with all languages, designing a golfing language is always a tradeoff between golfiness, accessibility, and development time.

---

So, when designing a golfing language, expressing algorithms with concise programs is just as important as ensuring the rest of the program space contains something useful. Some of the methods to reduce redundancy mentioned here are well worth implementing, and some should perhaps just be kept in mind.

The main thing you really want to focus on is being implicit over explicit.

That is to say, if it is possible to infer behaviour from context, requiring users to explicitly write out that behaviour is a waste of bytes.

For example, consider handling inputs to a program. You can always call an input function to read the next input from STDIN/ARGV, but that requires extra bytes:

print("Hello, "+input()) 

But what if you were to make a language design choice to assume that whenever an operator or function is missing arguments, input is automatically taken? The example might become:

print("Hello, "+) 

Where the interpreter/compiler automatically inserts a call to input() at the position of the missing argument.

But this can be taken a step further. Most code golf programs require displaying an output at the end of the program. Therefore, you can infer that more often than not, there will be a print statement somewhere in every program. And you can also infer that this print statement will more often than not be at the end of a program, representing the final output of any computed results. Our example then could become:

"Hello, "+ 

This last statement would be automatically wrapped in a call to print.

Syntax and parsing problems aside, this idea of providing a set of compiler assumptions for when pieces of code are omitted is powerful in terms of making programs short.

Ultimately, when designing your golflang, analyse where your language could usefully reconstruct missing context. Don't make users spend extra bytes on things that don't need to be said.

Common techniques include:

• Optimizing for tasks that are common in "golf problems". In extreme cases you get languages like hq9+ — generally taken as a joke, but it does demonstrate the idea. A bit more seriously, 05AB1E was originally designed to have "an advantage in base conversion" code golf problems, and now boasts operators for things like "compute the first n primes (or Fibonacci numbers) and put them on the stack".

• Using shorter tokens for built-in library functions, operators, control flow etc. Readability is generally not considered here, although some languages (such as Jelly) specify custom encodings so that some things can be expressed using (single) fancy Unicode characters without needing multiple bytes to encode them in UTF-8. Some even go as far as having tokens that are fundamentally parsed from a bit stream rather than a byte or character stream; the length of programs in these languages may be expressed in bits even if they must be padded to the nearest byte to store them. For example, Pyth has a "packed" variant using 7 bits per character. (One could similarly imagine a "packed Brainfuck using 3 bits per token - although this language is normally used as a challenge rather than to compete on program length.) All of these techniques can be thought of as a sort of manual Huffman coding applied to the source code.

• Relying on idioms that naturally lead to simpler language grammars and shorter code. For example, every operation in Retina is the application of a regular expression, so it a) takes advantage of the power of a cryptic domain-specific language already (i.e., the language of regular expressions) and b) avoids the need for special syntax to distinguish regular expressions from the rest of the program, or to explicitly apply them (and it can use short tokens to describe different ways of applying them). Many other "golfing" languages are stack-based, which avoids the need for parentheses to disambiguate precedence, and often also makes it easier for programmers to use fewer identifiers in the code. Functional programming idioms are also common, since operations like map/reduce/filter are fundamentally very powerful.

Golfy languages allow solving problems with program lengths, on average, approaching the Kolmogorov complexity of the problem as close as possible.

I say on average here because for a given problem, you can always create a programming language that solves that problem using a program length of one bit. Thus, it is a set of problems that you want to optimize for. Often, it's the set of programming challenges that you find on sites like LeetCode and HackerRank, and of course our own Code Golf site, as opposed to problems like implementing a web browser or any other "normal" application.

These languages work by using the smallest tokens for the most common operations. The set of operations they support is also chosen such that you can do everything you want (i.e., they are Turing complete, although that is a very low barrier), but such that complex problems are still solvable with relatively few tokens (as opposed to, say, Brainfuck which only supports 8 operations, but requires very long programs to do even simple things). But again, they often focus on a particular set of problems, so you often find things like an operation that generates an infinite series of prime numbers (Þp in Vyxal), something which would be considered ridiculous to even include in the standard library of most "normal" programming languages, but which will actually be helpful in many code challenges.

To have short tokens, they simply make use of all possible ASCII or even Unicode characters, and if they have more operations than can be assigned to individual characters, they typically use as short as possible sequences of characters. Ideally one could order operations by their frequency of occurrence in the target set of problems, and then use Huffman coding to assign sequences of bits to each operation, in such a way that the programs will on average be as small as possible. However, this is not done by most of the golfy languages, but they do approach this optimal coding, but still allow a human with any text editor to write programs.

There are other techniques golfy languages use to reduce program sizes besides their choice of operations and token sizes. For example, it's quite common that these languages are stack-oriented, because this removes the need for assigning values to variables; instead a single operation will often pop one or more values from the stack and replaces them with the result of the operation.

In the end, the golfy languages are still intended for humans to write in, and it's a nice challenge to learn which operations there are, what characters they map to, and then to do some puzzling to figure out how to solve challenges in such a language.