Mu

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
Category:Languages
Category:Functional paradigm
Category:Stack-based
Category:2023
Category:Implemented
Category:High-level
Category:Turing complete