## McCarthy’s 91 Function

### September 20, 2013

John McCarthy’s 91 function is a recursive function designed as a test case for formal verification of computer programs. It is defined as follows:

`M(n) = n - 10, if n > 100`

= M(M(n+11)), if n <= 100

For instance, when n = 87:

`M(87)`

M(M(98))

M(M(M(109)))

M(M(99))

M(M(M(110)))

M(M(100))

M(M(M(111)))

M(M(101))

M(91)

M(M(102))

M(92)

M(M(103))

M(93)

M(M(104))

M(94)

M(M(105))

M(95)

M(M(106))

M(96)

M(M(107))

M(97)

M(M(108))

M(98)

M(M(109))

M(99)

M(M(110))

M(100)

M(M(111))

M(101)

91

Your task is to write a program that shows the call history of a call to the 91 function in a manner similar to that shown for M(87) above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

In Python.

class rec

{

public int print(int n,int k)

{

for(int i=0;i<k;i++)

System.out.print("M(");

System.out.print(n);

for(int i=0;i100)

return n-10;

else

{

n = print(n+11,k+1);

return print(n,k);

}

}

public static void main(String args[])

{

rec r = new rec();

System.out.println(r.print(87,1));

}

}

C++

(define (expand M e)

(if (pair? e) `(M ,(apply expand e))

(if (> e 100) (- e 10) `(M (M ,(+ e 11))))))

`(define (trace n)`

(let loop ((e `(M ,n)))

(write e) (newline)

(if (pair? e) (loop (apply expand e)))))

I used this as an excuse to learn about Haskell’s

`Writer`

monad.An interpreter for “M” expressions in SML

#include <stdlib.h>

#include <stdio.h>

long mccarthy(long in, int depth)

{

int i;

for (i = 0; i <= depth; ++i) {

printf("M(");

}

printf("%ld", in);

for (i = 0; i <= depth; ++i) {

printf(")");

}

printf("\n");

if (in > 100) {

return in – 10;

} else {

return mccarthy(mccarthy(in + 11, depth+1), depth);

}

}

int main(int argc, char** args)

{

if (argc != 2) return 1;

printf("%ld\n", mccarthy(atoi(args[1]), 0));

return 0;

}

My first attempt was to do it recursively:

http://pastebin.com/DxVUhJP5

It works pretty well. It does give me the “Deep recursion on subroutine …” warning for numbers below 53, but that’s harmless in this case.

Still, I wanted a clean output and didn’t want to recompile Perl to change the recursion threshold, so here’s the non-recursive implementation:

http://pastebin.com/R5n0eakF

I did leave the tostring implementation recursive. I guess I like recursion :).

Ha! actually, it still gives me deep recursion warning for numbers below -977, but that’s now because of the tostring funcion :).