Each µCurse-program describes a function from a tuple of natural numbers to a natural number. As it is a purely functional language, there are no side-effects and no output besides the computed result.
Syntax and Semantics
There are six basic building blocks in µCurse, all of which describe either a primitive function or an operation to create a function from other functions. These are:
- S, the unary successor function
- C, the constant zero function
- Pi, the tuple projection function for the i-th element (i.e. Pi(x1,...,xn) = xi)
- A, the function application/concatenation operator
- R, the primitive recursion operator
- M, the µ-Minimization operator
S, C and Pi are functions by themselves, A, R and M can be used to create new functions from other functions. The syntax is as follows (note that x is a vector of input values, of arbitrary size):
Ag(h1) means g(h1(x)) Ag(h1h2h3) means g(h1(x),h2(x),h3(x)) Rgh gives function f: f(x,0) = g(0), f(x,S(y)) = h(x,y,f(x,y)) Mg gives function f: f(x) = The minimal y such that g(x,y'), y' < y is defined and g(x,y) = 0
Note that Mg does not have to be determined and can lead to partial functions.
A program in µCurse is just the function definition written in a single line. For instance, a program that calculates the sum of two inputs is:
RP0AS(P2), read: f(x,0) = P0(x) [ = x ], f(x,S(y)) = S(P2(x,y,f(x,y))) [ = f(x,y) + 1 ]
(via DeMorgan's Laws)
Elaborate Identity Function
(Idea: x == y iff y is the smallest value s.t. x - y = 0 => f(x) = µy(x-y))
Bijective Pair Function
f(x,y) = 2x * (2y+1)-1
In the dialect "Literate µCurse", one can write multiple function definitions (one per line) and use them for other definitions with the U prefix. The main function has to be called main. A function definition may only contain lower-case letters. For example, take the Boolean AND function from above:
sign=RCAS(C) plus=RP0AS(P2) not=RAS(C)C or=AUsign(Uplus) and=AUnot(AUor(AUnot(P0)AUnot(P1))) main=Uand
Since it is forbidden to create cycles with this definition, it amounts to not much more than string replacement.
By replacing the function letters with symbols and erasing the syntactically unnecessary open parenthesis, a more brainfuck-esque program look can be achieved.
S -> + C -> 0 Pi -> !<i times _> Ag(h1..hi) -> [gh1..hi] R -> @ M -> µ
ARAS(C)C(AARCAS(C)(RP0AS(P2))(ARAS(C)C(P0)ARAS(C)C(P1))) => [@[+0]0[[@0[+0]@![+!__]][@[+0]0!][@[+0]0!_]]]
for the Boolean AND described above
According to the Kleene normal form theorem, every recursive function f can be expressed as
f(x) = UµyTexy
for fixed, primitive recursive predicates U and T. A consequence is that every µCurse program can be written with at most one M.
- A reference implementation of the interpreter, written in Haskell.