Palace

Palace

Paradigm(s)	Functional
Designed by	User:Hakerh400
Appeared in	2020
Computational class	Turing complete
Major implementations	Interpreter
File extension(s)	.txt

Palace is a functional programming language that implements some sort of Peano arithmetic. It is similar to ƎↃИAЯT, but in this language there is no addition. Instead, the successor operator is the only predefined operator. All values are non-negative integers and the only constant that can appear in the source code is zero.

Overview

Source code contains one or more function definitions. Each function definition consists of function name, formal arguments and the return value. Example:

f(x) = x

It is an identity function. It takes argument x and returns x. Successor is denoted by prefix + and it can appear either in the formal argument, or in the return expression. For example:

g(x, 0) = x
g(x, +y) = y

The above function g has two definitions, but both definitions define the same function g. The first definition can be applied when the second argument is zero, while the second definition can be applied when the second argument is a successor of something. It should be clear from these two examples how the syntax works.

I/O format

Input is an array of non-negative integers. Output is a single non-negative integer. The first function that appears in the source code is the main function (its name is irrelevant) and its arity must match the length of the input array, because it is called when program starts.

Examples

Successor

succ(x) = +x

Predecessor

Zero stays zero.

pred(0) = 0
pred(+x) = x

Is zero

 isZero(0) = +0
 isZero(+x) = 0

Less than or equal

 leq(x, y) = isZero(sub(x, y))

Addition

add(x, 0) = x
add(x, +y) = add(+x, y)

Subtraction

$\max(x-y,0)$

sub(x, 0) = x
sub(x, +y) = sub(pred(x), y)

Multiplication

mul(x, 0) = 0
mul(x, +y) = add(x, mul(x, y))

Division

Rounds down. Does not halt when the divider is zero and the divident is nonzero.

div(x, y) = div1(x, y, 0, 0)
div1(x, y, z, 0) = div1(x, y, +z, leq(+x, mul(y, +z)))
div1(x, y, z, +r) = pred(z)

Exponentiation

exp(x, 0) = +0
exp(x, +y) = mul(x, exp(x, y))

Root

Returns $y$-th root of $x$. Rounds down. Does not halt if $y=0\land x\neq 0$.

root(x, y) = root1(x, y, +0, leq(+x, y))
root1(x, y, z, 0) = root1(x, y, +z, leq(+x, exp(+z, y)))
root1(x, y, z, +r) = pred(z)

Examples of non-primitive-recursive functions

All previous examples are primitive-recursive (if we ignore the fact that some of them do not halt on invalid input, like division). Here we show some total computable functions that are not primitive-recursive.

Ackermann function

A(0, n) = +n
A(+m, 0) = A(m, +0)
A(+m, +n) = A(m, A(+m, n))

Sudan function

F(0, x, y) = add(x, y)
F(+n, x, 0) = x
F(+n, x, +y) = F(n, F(+n, x, y), +add(F(+n, x, y), y))

Goodstein function

(TODO)

Interpreters

Interpreter