FALSE
From Esolang
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 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 features. A stack is used extensively, but there are also a few variables (characters a-z). FALSE has also lambda functions, ability to do arithmetics, some stack functions, means of doing if and while structures, and input/output support. Also, comments can be used.
[edit] 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 zero, true is all bits set (-1 or ~0) so that bitwise operators may be used)
- > greater than
- = equals
Lambdas and flow control (tests are 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 end-of-input)
- , 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, may be needed to separate consecutive integers
[edit] Computational Class
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, it might seem that it couldn't be Turing complete, even assuming as usual that all size limits of the implementation are ignored. However, this is not entirely clear, because there does exist a command ΓΈ to copy elements from arbitrarily deep in the stack. Rather than changing the original contents of the stack, it might be possible to create a complete, but slightly modified copy of the stack above the old one, at least if it is formatted suitably. This might be enough to simulate changing the stack, and so give Turing completeness.
A language extension which gives access to a secondary stack (such as the continuation stack) is the standard way to make a push-down automata Turing complete (see DUP).
