FALSE
FALSE (named after the author's favourite truth value) is an early Forth-like esoteric programming language invented by Wouter van Oortmerssen in 1993, with the goal of creating a powerful (and obfuscated) language with as small a compiler as possible. The original compiler is 1024 bytes, written in 68000 assembler. FALSE inspired the prominent esoteric languages Brainfuck and Befunge, among other languages.
Despite the small compiler size FALSE has a lot of features. A stack is used extensively, but there are also a few variables (characters a-z). FALSE has also lambda functions, arithmetic, certain stack functions, if and while structures, and input/output support. Comments can also be used.
Commands
Literals
- 123 put integer onto the stack
- 'c put character code onto the stack
Stack
- $ DUP
- % DROP
- \ SWAP
- @ ROT
- ø PICK (dup the nth stack item)
Arithmetic
- +
- -
- *
- /
- _ negate (negative numbers are entered "123_")
- & bitwise AND
- | bitwise OR
- ~ bitwise NOT
Comparison
False is 0. True is all bits set (-1 or ~0), so that bitwise operators can be used.
- > greater than
- = equals
Lambda and Flow control
(tests for non-zero)
- [...] define and put a lambda onto the stack
- ! execute lambda
- ? conditional execute: condition[true]?
- if-else can be expressed as: condition$[\true\]?~[false]?
- # while loop: [condition][body]#
Names
- a-z put a reference to one of the 26 available variables onto the stack
- : store into a variable
- ; fetch from a variable
I/O
- ^ read a character (-1 for EOF)
- , write a character
- "string" write a string (may contain embedded newlines)
- . write top of stack as a decimal integer
- ß flush buffered input/output
Other
- {...} comment
- ` compile short as 68000 machine instruction in the original Amiga FALSE implementation
- whitespace is ignored, but may be needed to separate consecutive integers
Examples
Hello, World!
"Hello, World!"
Factorial
Takes a base 10 number as input, outputs its factorial
0 0[ß^$$47>\58\>&][48-\10*+]#%[$1>][$1-]#[\$0=~][*]#%.
Fibonacci
Takes a base 10 number n as input, outputs the n-th fibonacci number.
{read input n}
0 n:
[^ $ $ '9 > \ '0 \ > | ~]['0 - n; 10 * + n:]#
%
{compute n-th fibonacci number iteratively}
0 1
[n; 1 - $ n: 1_=~][$ @ +]#
% .
Recursive
A horribly inefficient implementation that recursively computes the n-th Fibonacci number. This is useful to get a rough ballpark estimate of the speed of a FALSE interpreter.
[$ 1 > [1- $ f;! \ 1- f;! +]?]f:
33 f;! . {compute & print 33th fibonacci number}
99 Bottles of Beer
99b: [b;0=["No more bottles of beer"]?b;1=["1 more bottle of beer"]?b;1>[b;." bottles of beer"]?]a: [b;0>][a;!" on the wall"10,a;!10,"Take one down, pass it around"10,b;1-b:a;!" on the wall"]#
Computational class
Assuming (as usual) that any memory size limits of the implementation are ignored, proving Turing-completeness of FALSE is subtle, because FALSE has no way to change items deep in the stack without popping most of those above, nor a way to construct new functions.
However, FALSE is indeed Turing-complete, as the command subset $%\[]! is equivalent to the Underload command subset :!~()^, which is Turing-complete (% is optional but convenient). This construction essentially uses the call stack as an extra stack to implement the tape of a Turing machine.
Other strategies for showing Turing-completeness rely on also having unbounded integers:
It might be possible to use the command ø to copy elements from arbitrarily deep in the stack. Rather than changing the original contents of the stack, it is possible to create a complete, but slightly modified, copy of the stack above the old one, at least if it is formatted suitably. This is enough to simulate changing the stack, and so give Turing completeness, but only if ø can be given arbitrarily large arguments, which requires unbounded integers on the stack.
In False dialects that use unbounded integers, there is another way to demonstrate Turing completeness, via unlimited register machines. Since False allows full access to the top three stack positions, these can be used to simulate a register machine with 2 registers. It was shown by Minsky (proof at wikipedia) that 2-register unlimited register machines are Turing complete. Note, however, that the False specification states that "all variables (and also stack-items) are 32bits"; interpreters adhering to this cannot simulate an unlimited register machine using only three stack positions.