Mic

Mic is a stack-based esoteric programming language created by User:D, loosely based on the concept of primitive recursive functions.

Data Structures

The primary data structure is a numeric stack, but there's also an "accumulator" (which is actually a stack of lists).

A demonstration of the A stack:

|    [5]    | <-- TOS
|[1,2,3,4,5]|
|  [1,2,3]  |

Commands

Numeric commands

• 123: Push the number onto the stack.
• s: Increment TOS.

"Accumulator" commands

• @: Pop x. Pops x values from the stack. Push this list onto A.
• A: Retrieve TOS of A. Dump this list onto the stack.
• ;: Drop the TOS of A.
• k: Pops x. Push the x-th item of the TOS of A.

Looping Commands

• I: Push positive infinity. Notes:

• Inf() - 1 is still Inf().
• No natural number can equal Inf().

• (...): "Mic" loop. Pop x:

• For each integer i in the range [0 .. x-1]:

• Push i.
• Execute ... as Mic code.
• Pop t. If t == 0: Exit the loop.

• Push the last assigned value of i.

Primitive recursive operators in Mic

In the following implementations, we use [g] to represent the body of the function g (a sequence of stack commands).

Composition

Here's a demonstration with 3 arguments (replace the bracket-enclosed commands with your actual commands):

Stack: 1 2 3

3@ A [h1] A [h2] [g] ;

Primitive Recursion

For simplicity purposes, we'll do this instead:

P(g,h)(0, ...a) = g(...a)
P(g,h)(n, ...a) = h(n-1, P(g,h)(n-1, ...a), ...a)

Say, we have the following items on the stack:

n a1 a2 ... ai

We'll use {i} to represent the constant value of i.

For the base case, we simply call g on a1 ... ai.

{i}@A [g]

Now, before we enter the recursive case, we update the accumulator to prepend it with our g value.

A;{i}s@

Here's the recursive case (with n as the argument to the "Mic" loop):

(A [h] 2k 3k ... {i}sk ; {i}s @ 1)

(Where the ... represents an enough number of k commands to push all arguments except for the first)

Drop the number returned by the "Mic" loop:

1@;

Finally, we push the first item of the final value of the accumulator (which is our application result):

1k ;

The full program, again:

{i}@A [g] A;{i}s@ (A [h] 2k 3k ... {i}sk ; {i}s @ 1) 1@; 1k ;

Minimization

I([g])

Examples

Predecessor

(s)

External Links

• Reference Implementation (Python)