Subterra
Subterra is a tarpit-style language created by Katrina Scialdone that attempts to get as close to being a proper imperative programming language as possible within the following restrictions:
- Only single-character instructions
- A single stack rather than variables
- Integers are the only datatype (syntactic sugar excepted)
To this end, it implements a unique subroutine system that allows for simple pseudo-functions, as well as an import system (a rather unusual feature for a tarpit language).
Language reference
An up-to-date language reference is maintained on GitHub (see External Resources).
Computational class
Subterra is Turing-complete (and in fact has numerous Turing-complete subsets). The simplest way to show this is to see that the stack can be reversed using @, effectively making it into a double-ended queue (i.e. enough data storage ability for Turing-completeness), and the language has no shortage of useful control flow structures ({} subroutines don't do any stack manipulation, thus can be freely used for control flow without disturbing the data storage).
More complex Turing-completeness constructions also exist, e.g. using the call stack and the data stack as the two stacks required to store the required amount of data.
Examples
Hello, world!
Recursive:
0{s0>?{c0#}}"Hello world!"$0#
Non-recursive:
"Hello world!"w[0>]{bct1-}
99 bottles of beer
~ Includes proper plurals!
0 { w [0>] { bct1- } $ } ~ Simple print function
100 w {1-&0>} [
&p" bottle"0#&1!?(\sc)" of beer on the wall,\n"0#
&p" bottle"0#&1!?(\sc)" of beer,\n"0#
"Take one down, pass it around,\n"0#
1-&0=?("No"0#):[p]" bottle"0#&1!?(\sc)" of beer on the wall.\n\n"0#
]
Cat program
Recursive: (warning: will crash with large inputs!)
0{s0>?{c0#}}i$0#
Non-recursive:
iw[0>]{bct1-}
Collatz sequence
Change the 25 at the beginning to change the starting number.
25 w [1>] {
&p10c
&2%0!? {3*1+} : {2/}
} p
Factorial
Change the 5 on line 3 to change the input number.
0 { &1>?{&1-0#}s1>?{*} }
5;0#p