I would like to address the idea that many posters have given, that such a language would be "useless". Perhaps it would be useless for humans to write, manually, with the intention of solving some particular task. However, despite being a majority use-case for programming languages, that's certainly not the only use-case. Several use-cases come to mind where such a language is useful, and we can look to those fields for examples of such languages.
Firstly Cort Ammon's allusion to genetics is spot on: the program transformation in the question (substituting
5) can be seen as a mutation. This kind of manipulation is common in the field of evolutionary computation; in particular genetic algorithms perform such transformations on strings, whilst genetic programming transforms programs. In either case, we usually want to assign meaning to every possibility, since that will produce the most compact search space.
Genetic algorithms rely on some sort of evaluation function for strings; if we use a programming language interpreter as our evaluation function, then we have a scenario where a programming language which assigns meaning to all possible strings is useful. In genetic programming, it is assumed that our evaluation function is a programming language interpreter, but we may choose various representations for our programs; for example, many systems operate on abstract syntax trees. If we choose strings as our representation, then we recover the same scenario as with genetic algorithms.
Another situation where we may want every string to be a valid program is when enumerating programs. This is related to the bijection mentioned by CodesInChaos, but we may prefer to operate on strings rather than Natural numbers for several reasons:
- If there is some structure in the language, eg. we can assign meaning to sub-strings, this may be lost when translating to Natural numbers. In this case we may prefer to use strings, in order to reason about and transform sub-strings locally, rather than representing the whole-program as a number. This is analogous to how we might prefer to use bitwise operations on an int rather than arithmetic expressions, when each bit has an individual meaning. This is basically a generalisation of the evolutionary scenario.
- We may want to generate the programs on demand; for example, we might begin executing a program which is completely undetermined, and only generate (eg. randomly) the individual instructions (eg. characters) when/if the instruction pointer reaches them. This is common in algorithmic information theory, where the program is a Turing machine tape, and the aim is to characterise the behaviour of randomly-generated programs. For example, we can formulate the Solomonoff prior over arbitrary strings as the probability that a universal Turing machine with a random tape will output that string.
In terms of example languages, many evolutionary computation systems are based on stack languages like the Push family. These tend to allow arbitrary streams of tokens (which we could represent as individual characters). Sometimes (like with BrainSlugs83's Brainfuck example) there are restrictions on balancing parentheses; however, we can relate this to self-delimiting programs, in that a string like
[ may not be a valid program, but it is a valid program prefix. If we imagine a compiler/interpreter reading source code from stdin, then it won't reject a string like
[, it will simply wait for more input before continuing.
Languages like Binary Combinatory Logic and Binary Lambda Calculus arose directly out of work on algorithmic information theory, eg. from http://tromp.github.io/cl/cl.html
This design of a minimalistic universal computer was motivated by my desire to come up with a concrete definition of Kolmogorov Complexity, which studies randomness of individual objects.