Mu

Not to be confused with μ.

Mu is a stack-based esoteric programming language created by User:D, based on general recursive functions.

Execution

Mu has a value stack where the numbers are pushed onto, and the functions are applied on.

Internally, it also has a separate function stack for storing [ ... ] codeblocks, but programs cannot process this stack directly without using the combinators.

(In the Python implementation, the initial stack is read as a Python list (which can be an empty string, which sets the stack to []). The resulting stack after execution is outputted.)

Commands (Functions)

• 123: Push the natural number onto the stack.
• z: Pops x, pushes 0.

• e.g. 3z -> 0

• s: Pops x, pushes x+1.

• e.g. 2s -> 3

• k: Pops k and i. Pops k items from the stack, and pushes the i-th item of these items (1-indexed).

• e.g. If stack is 0 1 2 3, 3 1k will pop 1 2 3 and push 1 (the 1st item of these items).
• The resulting stack would be 0 1

• [ ... ]: Pushes everything between the brackets onto the function stack.

Combinators (Operators)

In the following descriptions, n (used to describe the arity of functions) represents any natural number (including 0).

P (primitive recursion)

This combinator expects two functions on the function stack, g and h. Represented by the form of:

[g][h]P

Where g is the base case, and h is the recursive case.

Calling process

Here, n is the arity of g.

• Pop n+1 items off the stack (as L)
• Then, the last item (x) is popped off L.
• For each natural number i in the downwards range of [x-1 .. 0]:

• Push all items of L onto the stack, along with i.

• Finally, push all items of L onto the stack.

Returning process

Here, x is the extracted last item of L.

• Call g on the stack.
• Repeat x times:

• Call h on the stack.

An example

If we call [] [3 3ks] P on the following stack:

3 2

The arity of g is 1 (inferred), so our composed P function takes 2 arguments (one more than g).

This means that we pop 2 items off the stack. Our extracted list (L) is, therefore, [3, 2].

Next, we extract the last item of the list L as x. This means that x = 2 and L = [3].

Then, for each item in [ x-1 .. 0 ], we push items on the the stack, with the procedure described above:

3 1
3 1 3 0
3 1 3 0 3

The stack is left like this (after the calling process):

3 1 3 0 3

We apply g (which is []) onto our stack.

[] does the same thing as [1 1k]. Therefore, the value in the base case is left untouched.

We call h 2 times (Since x = 2). h selects the third argument and returns its successor.

3 1 3 0 3
3 1 4
5

After the execution of the P combinator, 5 is left on the stack, which is the sum of its two arguments.

C (composition)

C expects a sequence of functions in the following form:

[h1] [h2] ... [hk] [g] C

Let's say that the arities of [h1] through [hk] is n. (g is a k-ary function.)

• Pop n items off the stack. Call this list L.
• For each function (f) in [h1] through [hk]:

• Call f, using L as the stack.
• Push the result onto the value stack.

• Call g on the value stack.

An example

Here, we call [z][[3 1k][3 3k][[][3 3ks]P]C]P (multiplication) on the following stack:

2 3

During the calling of P:

2 2 2 1 2 0 2

In the base case, z turns the 2 into a 0.

---

In the recursive case, we have a C combinator:

[3 1k] [3 3k] [[][3 3ks]P] C

Here, h1 is [3 1k], and h2 is [3 3k].

Since the h functions require 3 arguments, we pop 3 items off the stack as L:

L = [2, 0, 0]
stack: 2 2 2 1

(For clarity purposes, I'll be using ... to represent 2 2 2 1 on the stack.)

First, we call [3 1k] on L. This selects the 1st argument out of 3 arguments. We get 2:

stack: ... 2

Next, calling [3 3k] on L (we get 0):

stack: ... 2 0

Finally, we apply g (which is [][3 3ks]P, the addition function demonstrated above) onto the stack.

stack: ... 2

---

Through the repeated application of P, the stack undergoes the following changes:

2 2 2 1 2 0 0
2 2 2 1 2
2 2 4
6

The product is left on the top of the stack.

M (minimization)

M expects a function on the function stack, in the following form:

[g] M

We'll say that the arity of g is n+1.

• Pop n items from the stack. Call this L.
• For each natural number i in the range [0 .. +∞]:

• Call g with L appended with i as the stack.
• If the result equals 0:

• Push i onto the stack.
• Terminate the loop.

See also

• Conglument

External Links

• Python interpreter