Unarian

From Esolang
Jump to navigation Jump to search
Unarian
Paradigm(s) Functional
Designed by User:Crb233
Appeared in 2021
Computational class Turing complete
Major implementations Original
File extension(s) .unarian, .un

Unarian is an esoteric programming language in which every program computes a unary (hence the name) function on the natural numbers, and all such programs can be built using only increment, decrement, composition, and branching.

Components

Builtins

There are two primary built-in programs: increment (+) and decrement (-). As their names suggest, increment adds one to its input and decrement subtracts one from its input. However, decrement can fail if applied to input 0 (since doing so would not produce a natural number).

In the reference implementation, there are also two additional builtins ! and ? used for debugging.

Composition

Programs can be composed by writing them in sequence: + + + is the composition of + three times in a row. Unlike standard function composition, these programs are evaluated left to right: a b c evaluates as a then b then c.

If any program in a composition fails, then the resulting program also fails: - - - fails on input 0, 1, and 2.

We can similarly compose user-defined programs. If f is defined as + + and g is defined as - - -, then f g evaluates as + + - - -, which is semantically equivalent to -.

Branching

Program complexity comes from the ability to have branching execution paths. Given programs f and g, the branching program f | g evaluates as f unless f fails, in which case it evaluates as g. For example, - | + maps 0 to 1 because it first tries to decrement 0, fails to do so, and then increments 0. For all other natural numbers, - | + is equivalent to -.

The branching operator | is left-associative and will try evaluating branches from left to right: a | b | c evaluates as a unless a fails, then evaluates as b unless b fails, and finally evaluates as c.

Lastly, empty branches are treated as instances of the identity function: - | has branches - and . It maps 0 to 0 and all other natural numbers x to x - 1.

Syntax

# Basic function definition.
function_name { function_definition }

# Extra spacing doesn't matter.
example_func {
    extra
    spacing
    doesn't
    matter
}

# Function names can contain any characters except whitespace and '#'.
# Strings '+', '-', '!', and '?' are built-in and cannot be redefined.
# Strings '{', '|', and '}' have special meaning.
*10 { multiply_by_10 }
/10 { divide_by_10 }
^2 { square }

# Functions can call themselves recursively.
infinite_loop { infinite_loop solve_p_vs_np }

# There are two primary builtin programs: '+' and '-'.
# Applying '+' to input x returns x + 1
# Applying '-' to input x returns x - 1 if x > 0 and fails if x = 0
add_1 { + }
add_2 { + + }
add_3 { + + + }
subtract_2_or_fail { - - }

# There are two builtin programs used for debugging: '!' and '?'.
# Applying '!' to input x prints the value of x and returns x.
# Applying '?' to input x prints the stack trace and returns x.
print_then_add_1 { ! + }
print_stack_trace { ? }

# Programs can have branching execution paths. The special string '|' is
# used to separate different branches.
do_A_or_B_or_C { A | B | C }

# Empty branches act as the identity function.
subtract_2_or_do_nothing { - - | }

# A nested code block starts with '{' and ends with '}'. Code blocks are
# evaluated as if their contents had been defined as a separate program.
complex { a { b | c } d | { e | { f } } g }

code_1 { b | c }
code_2 { f }
code_3 { e | code_2 }
less_complex { a code_1 d | code_3 g }   # This is equivalent to 'complex'.

Examples

Here is some example code that, given an input n, returns the number of steps for the Collatz sequence starting at n to reach 1:

# Outputs 0.
0 { - 0 | }

# Fails unless input is equal to 0.
if=0 { { - 0 | + } - }

# Fails unless input is greater than 1.
if>1 { - - + + }

# Divides by 2 if divisible by 2. Fails otherwise.
if/2 { - - if/2 + | if=0 }

# Multiplies by 3.
*3 { - *3 + + + | }

# Outputs the number of collatz steps required to reach 1.
collatz { if>1 { if/2 | *3 + } collatz + | - }

main { collatz }

While the Collatz code above is relatively concise, it's much more difficult to perform computations that require more than one number to be stored in memory. Consider the following code which computes Fibonacci numbers:

#========#
# Basics #
#========#

0 { - 0 | }

if=0 { { - 0 | + } - }

if>0 { - + }

#==========================#
# Addition and Subtraction #
#==========================#

+2 { + + }
+8 { + + + + + + + + }
-2 { - - }
-8 { - - - - - - - - }

+000 { }
+001 { + }
+010 { + + }
+011 { + + + }
+100 { + + + + }
+101 { + + + + + }
+110 { + + + + + + }
+111 { + + + + + + + }

-000 { }
-001 { - }
-010 { - - }
-011 { - - - }
-100 { - - - - }
-101 { - - - - - }
-110 { - - - - - - }
-111 { - - - - - - - }

#=============================#
# Multiplication and Division #
#=============================#

*2 { - *2 +2 | }
*8 { - *8 +8 | }

/2 { -2 /2 + | 0 }
/8 { -8 /8 + | 0 }

if/2 { -2 if/2 + | if=0 }

#=====================#
# Modulo Conditionals #
#=====================#

if=000mod8 { -8 if=000mod8 +8 | if=0 }
if=001mod8 { -001 if=000mod8 +001 }
if=010mod8 { -010 if=000mod8 +010 }
if=011mod8 { -011 if=000mod8 +011 }
if=100mod8 { -100 if=000mod8 +100 }
if=101mod8 { -101 if=000mod8 +101 }
if=110mod8 { -110 if=000mod8 +110 }
if=111mod8 { -111 if=000mod8 +111 }

#===============================#
# Getting and Setting Registers #
#===============================#

setR0
    { if=0
    | if/2 setR0 *8
    |   /2 setR0 *8 +
}

getR1
    { if=0
    | if=000mod8 /8 getR1 *2
    | if=001mod8 /8 getR1 *2
    | if=010mod8 /8 getR1 *2 +
    | if=011mod8 /8 getR1 *2 +
    | if=100mod8 /8 getR1 *2
    | if=101mod8 /8 getR1 *2
    | if=110mod8 /8 getR1 *2 +
    | if=111mod8 /8 getR1 *2 +
}

getR2
    { if=0
    | if=000mod8 /8 getR2 *2
    | if=001mod8 /8 getR2 *2
    | if=010mod8 /8 getR2 *2
    | if=011mod8 /8 getR2 *2
    | if=100mod8 /8 getR2 *2 +
    | if=101mod8 /8 getR2 *2 +
    | if=110mod8 /8 getR2 *2 +
    | if=111mod8 /8 getR2 *2 +
}

#=======================#
# Register Conditionals #
#=======================#

ifR0=0
    { if=0
    | if=000mod8 /8 ifR0=0 *8 +000
    | if=010mod8 /8 ifR0=0 *8 +010
    | if=100mod8 /8 ifR0=0 *8 +100
    | if=110mod8 /8 ifR0=0 *8 +110
}

ifR0=1
    { if=001mod8 /8 ifR0=0 *8 +001
    | if=011mod8 /8 ifR0=0 *8 +011
    | if=101mod8 /8 ifR0=0 *8 +101
    | if=111mod8 /8 ifR0=0 *8 +111
}

#=====================#
# Register Operations #
#=====================#

R2=0
    { if=0
    | if=000mod8 /8 R2=0 *8 +000
    | if=001mod8 /8 R2=0 *8 +001
    | if=010mod8 /8 R2=0 *8 +010
    | if=011mod8 /8 R2=0 *8 +011
    | if=100mod8 /8 R2=0 *8 +000
    | if=101mod8 /8 R2=0 *8 +001
    | if=110mod8 /8 R2=0 *8 +010
    | if=111mod8 /8 R2=0 *8 +011
}

R2=1
    { if=0
    | if=000mod8 /8 R2=0 *8 +100
    | if=001mod8 /8 R2=0 *8 +101
    | if=010mod8 /8 R2=0 *8 +110
    | if=011mod8 /8 R2=0 *8 +111
    | if=100mod8 /8 R2=0 *8 +100
    | if=101mod8 /8 R2=0 *8 +101
    | if=110mod8 /8 R2=0 *8 +110
    | if=111mod8 /8 R2=0 *8 +111
}

R0=R0-1
    { if>0 if=000mod8 /8 R0=R0-1 *8 +001
    |      if=001mod8 -
    |      if=010mod8 /8 R0=R0-1 *8 +011
    |      if=011mod8 -
    |      if=100mod8 /8 R0=R0-1 *8 +101
    |      if=101mod8 -
    |      if=110mod8 /8 R0=R0-1 *8 +111
    |      if=111mod8 -
}

R0=R0-2
    { if=000mod8 /8 R0=R0-1 *8 +000
    | if=001mod8 /8 R0=R0-1 *8 +001
    | if=010mod8 /8 R0=R0-1 *8 +010
    | if=011mod8 /8 R0=R0-1 *8 +011
    | if=100mod8 /8 R0=R0-1 *8 +100
    | if=101mod8 /8 R0=R0-1 *8 +101
    | if=110mod8 /8 R0=R0-1 *8 +110
    | if=111mod8 /8 R0=R0-1 *8 +111
}

R1=R1+R2
    { if=0                        +000
    | if=000mod8 /8 R1=R1+R2   *8 +000
    | if=001mod8 /8 R1=R1+R2   *8 +001
    | if=010mod8 /8 R1=R1+R2   *8 +010
    | if=011mod8 /8 R1=R1+R2   *8 +011
    | if=100mod8 /8 R1=R1+R2   *8 +110
    | if=101mod8 /8 R1=R1+R2   *8 +111
    | if=110mod8 /8 R1=R1+R2+1 *8 +100
    | if=111mod8 /8 R1=R1+R2+1 *8 +101
}

R1=R1+R2+1
    { if=0                        +010
    | if=000mod8 /8 R1=R1+R2   *8 +010
    | if=001mod8 /8 R1=R1+R2   *8 +011
    | if=010mod8 /8 R1=R1+R2+1 *8 +000
    | if=011mod8 /8 R1=R1+R2+1 *8 +001
    | if=100mod8 /8 R1=R1+R2+1 *8 +100
    | if=101mod8 /8 R1=R1+R2+1 *8 +101
    | if=110mod8 /8 R1=R1+R2+1 *8 +110
    | if=111mod8 /8 R1=R1+R2+1 *8 +111
}

R2=R1+R2
    { if=0                        +000
    | if=000mod8 /8 R2=R1+R2   *8 +000
    | if=001mod8 /8 R2=R1+R2   *8 +001
    | if=010mod8 /8 R2=R1+R2   *8 +110
    | if=011mod8 /8 R2=R1+R2   *8 +111
    | if=100mod8 /8 R2=R1+R2   *8 +100
    | if=101mod8 /8 R2=R1+R2   *8 +101
    | if=110mod8 /8 R2=R1+R2+1 *8 +010
    | if=111mod8 /8 R2=R1+R2+1 *8 +011
}

R2=R1+R2+1
    { if=0                        +100
    | if=000mod8 /8 R2=R1+R2   *8 +100
    | if=001mod8 /8 R2=R1+R2   *8 +101
    | if=010mod8 /8 R2=R1+R2+1 *8 +010
    | if=011mod8 /8 R2=R1+R2+1 *8 +011
    | if=100mod8 /8 R2=R1+R2+1 *8 +000
    | if=101mod8 /8 R2=R1+R2+1 *8 +001
    | if=110mod8 /8 R2=R1+R2+1 *8 +110
    | if=111mod8 /8 R2=R1+R2+1 *8 +111
}

#===========#
# Fibonacci #
#===========#

# register |  R0  |  R1   |   R2    |
# value    | n-2i | f(2i) | f(2i+1) |

fib'
    { ifR0=0 getR1
    | ifR0=1 getR2
    | R0=R0-2 R1=R1+R2 R2=R1+R2 fib'
}

fib { setR0 R2=1 fib' }

main { fib }

Implementation

See [1] for an involved Python implementation. Here is a much simpler Python interpreter that takes a single Unarian file and evaluates the main function on all standard input:

def tokenize(file):
    for line in file:
        i = line.find('#')
        if i >= 0:
            line = line[:i]
        for tok in line.split():
            yield tok

def parse_group(toks, i):
    if toks[i] != '{':
        raise Exception()
    i += 1
    par = []
    ser = []
    while i < len(toks):
        if toks[i] == '}':
            par.append(ser)
            return par, i
        elif toks[i] == '|':
            par.append(ser)
            ser = []
        elif toks[i] == '{':
            grp, i = parse_group(toks, i)
            ser.append(grp)
        else:
            ser.append(toks[i])
        i += 1
    raise Exception()

def parse(file):
    toks = tokenize(file)
    lib = {}
    i = 0
    while i < len(toks):
        if toks[i] in {'{', '}', '+', '-'}:
            raise Exception()
        name = toks[i]
        i += 1
        grp, i = parse_group(toks, i)
        lib[name] = grp
        i += 1
    return lib

def eval(lib, expr, x):
    stack = [(x, expr, 0, 0)]
    while len(stack) > 0:
        y, expr, i, j = stack.pop(-1)
        if i >= len(expr):
            x = None
        elif x is None:
            x = y
            stack.append((y, expr, i + 1, 0))
        elif j >= len(expr[i]):
            pass
        else:
            stack.append((y, expr, i, j + 1))
            subexpr = expr[i][j]
            if subexpr == '+':
                x += 1
            elif subexpr == '-':
                x = x - 1 if x > 0 else None
            elif isinstance(subexpr, list):
                stack.append((x, subexpr, 0, 0))
            else:
                stack.append((x, lib[subexpr], 0, 0))
    return x

def main():
    import sys
    with open(sys.argv[1]) as file:
        lib = parse(file)
    expr = 'main'
    for x in map(int, input().split()):
        y = eval(lib, expr, x)
        print(y, end=' ')

if __name__ == '__main__':
    main()

Computational class

It's relatively easy to translate arbitrary Fractran programs into Unarian programs. Since Fractran is known to be Turing complete, Unarian also is. Consider, for example, the following translation of the Fractran prime generating algorithm (3/11 847/45 143/6 7/3 10/91 3/7 36/325 1/2 36/5):

#========#
# Basics #
#========#

# Return 0
0 { - 0 | }

# Conditionals
if=0 {   { - 0 | + } -   }
if=1 { - { - 0 | + } - + }
if>0 {   - +   }
if>1 { - - + + }

#==========#
# Addition #
#==========#

+2  { + + }
+3  { + + + }
+5  { + + + + + }
+7  { + + + + + + + }
+11 { + + + + + + + + + + + }
+13 { + + + + + + + + + + + + + }

#=============#
# Subtraction #
#=============#

-2  { - - }
-3  { - - - }
-5  { - - - - - }
-7  { - - - - - - - }
-11 { - - - - - - - - - - - }
-13 { - - - - - - - - - - - - - }

#================#
# Multiplication #
#================#

*2  { - *2  +2  | }
*3  { - *3  +3  | }
*5  { - *5  +5  | }
*7  { - *7  +7  | }
*11 { - *11 +11 | }
*13 { - *13 +13 | }

#================#
# Exact division #
#================#

if/2  { -2  if/2  + | if=0 }
if/3  { -3  if/3  + | if=0 }
if/5  { -5  if/5  + | if=0 }
if/7  { -7  if/7  + | if=0 }
if/11 { -11 if/11 + | if=0 }
if/13 { -13 if/13 + | if=0 }

#===================#
# Base 10 Functions #
#===================#

+10 { + + + + + + + + + + }
-10 { - - - - - - - - - - }

*10 { - *10 +10 | }
if/10 { -10 if/10 + | if=0 }

exp10 { - exp10 *10 | + }
iflog10 { if>1 if/10 iflog10 + | if=1 }

#=================#
# Fractran Primes #
#=================#

# Runs the following Fractran algorithm for generating primes (taken from the
# Fractran page on Esolang https://esolangs.org/wiki/Fractran):
#     3/11 847/45 143/6 7/3 10/91 3/7 36/325 1/2 36/5
# If running in debug mode, it will print out every prime it encounters.

print_power_of_10 { iflog10 ! 0 - | }

fractran_primes' {
    print_power_of_10 {
          if/11           *3
        | if/3 if/3 if/5  *7 *11 *11
        | if/2 if/3       *11 *13
        | if/3            *7
        | if/7 if/13      *2 *5
        | if/7            *3
        | if/5 if/5 if/13 *2 *2 *3 *3
        | if/2
        | if/5            *2 *2 *3 *3
    } fractran_primes'
}

fractran_primes { 0 +10 fractran_primes' }

main { fractran_primes }