Finity

Finity is a programming language created by User:Silver. It compiles to a finite automaton. This means it's well below turing-complete, but it has desirable properties for metacomputing about Finity programs. For instance, you can determine whether arbitrary Finity programs halt, or optimise them perfectly (if you have enough compute time). Note that since physical computers are finite, all real-world languages actually have the same restrictions - the thing that Finity does is explicitly construct the finite automaton that a program is equivalent to, which is possible but comparatively difficult for programs in other languages.

Syntax

Finity is a simple language. Each (nonempty) line must contain one of the following statements:

Statement	Description
[variable or quoted string] -> OUTPUT	print output
[variable] <- input	take input
:[LABEL]	label for goto statements
[variable] = [expression]	assignment
GOTO [LABEL]	unconditional goto
GOTO [LABEL] IF [expression]	conditional goto

All variable names must be lowercase (plus underscores), all label names must be all uppercase (plus underscores). An expression consists of variables, integer literals and the operations +, -, *, /, ==, < and >. Comparison operators return 1 or 0 for true or false, and likewise conditional gotos jump if the given expression has a nonzero value. Division is integer division.

MAXINT

Finity has an associated constant MAXINT, which can be configured in the example implementation. All variables in Finity are nonnegative integers less than MAXINT. The example implementation sets MAXINT to 4 for proof of concept purposes, since it makes the compiling and optimising run quickly.

Examples

hello world

"hello world\n" -> OUTPUT

truth machine

x <- INPUT
GOTO END IF x == 0
:LOOP
1 -> OUTPUT
GOTO LOOP
:END
0 -> OUTPUT

bubble sort

The interesting thing about this is that after optimisation, it produces the same code that a more sophisticated sorting algorithm would.

"enter five items to be sorted:\n" -> OUTPUT
"1: " -> OUTPUT
a <- INPUT
"2: " -> OUTPUT
b <- INPUT
"3: " -> OUTPUT
c <- INPUT
"4: " -> OUTPUT
d <- INPUT
"5: " -> OUTPUT
e <- INPUT


:CHECKSORTED

GOTO BUBBLE IF a > b
GOTO BUBBLE IF b > c
GOTO BUBBLE IF c > d
GOTO BUBBLE IF d > e

"list sorted: " -> OUTPUT
a -> OUTPUT
", " -> OUTPUT
b -> OUTPUT
", " -> OUTPUT
c -> OUTPUT
", " -> OUTPUT
d -> OUTPUT
", " -> OUTPUT
e -> OUTPUT
"\n" -> OUTPUT
GOTO END


:BUBBLE

GOTO SKIPBUBBLEA IF a < b
store = a
a = b
b = store
:SKIPBUBBLEA

GOTO SKIPBUBBLEB IF b < c
store = b
b = c
c = store
:SKIPBUBBLEB

GOTO SKIPBUBBLEC IF c < d
store = c
c = d
d = store
:SKIPBUBBLEC

GOTO SKIPBUBBLED IF d < e
store = d
d = e
e = store
:SKIPBUBBLED

GOTO CHECKSORTED

:END
// halt

Example Implementation

The example implementation can be found here. It comes with an optimiser that minimises the automaton.