μCurse

µCurse is a Turing-complete, purely functional language based on µ-recursive functions. It was created on May 21st, 2014 by User:Sacchan.

Structure

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(x₁,...,x_n) = x_i)
• 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 ]

Example Programs

Sign Function

 RCAS(C)

Boolean NOT

 RAS(C)C

Boolean OR

 ARCAS(C)(RP0AS(P2))

Boolean AND

(via DeMorgan's Laws)

 ARAS(C)C(AARCAS(C)(RP0AS(P2))(ARAS(C)C(P0)ARAS(C)C(P1)))

Elaborate Identity Function

(Idea: x == y iff y is the smallest value s.t. x - y = 0 => f(x) = µy(x-y))

 MRP0ARCP0(P2)

Bijective Pair Function

f(x,y) = 2^x * (2y+1)-1

 ARP0ARCP0(P2)(ARCARP0AS(P2)(P0P2)(AARAS(C)ARCARP0AS(P2)(P0P2)(P0P2)(AS(AS(C))P0)(P0)ARP0AS(P2)(ARCARP0AS(P2)(P0P2)(AS(AS(C))P1)AS(C)))AS(C))

Literate µCurse

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.

Symbolic Syntax

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 -> µ

Example

 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

Trivia

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.

External resources

• A reference implementation of the interpreter, written in Haskell.