|Computational class||Turing complete|
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.
- 1 Overview
- 2 I/O format
- 3 Examples
- 4 Examples of non-primitive-recursive functions
- 5 Interpreters
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.
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.
succ(x) = +x
Zero stays zero.
pred(0) = 0 pred(+x) = x
isZero(0) = +0 isZero(+x) = 0
Less than or equal
leq(x, y) = isZero(sub(x, y))
add(x, 0) = x add(x, +y) = add(+x, y)
sub(x, 0) = x sub(x, +y) = sub(pred(x), y)
mul(x, 0) = 0 mul(x, +y) = add(x, mul(x, y))
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)
exp(x, 0) = +0 exp(x, +y) = mul(x, exp(x, y))
Returns -th root of . Rounds down. Does not halt if .
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.
A(0, n) = +n A(+m, 0) = A(m, +0) A(+m, +n) = A(m, A(+m, n))
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))