## McCarthy’s 91 Function

### September 20, 2013

First, a simple version that just computes the value of the function:

`(define (m n)`

(if (< 100 n) (- n 10)

(m (m (+ n 11)))))

To show all the recursive steps requires that we track the depth of the recursion:

`(define (mccarthy n)`

(define (m n d)

(do ((i 0 (+ i 1))) ((= i d) (display n))

(display "M("))

(do ((i 0 (+ i 1))) ((= i d) (newline))

(display ")"))

(if (positive? d)

(if (< 100 n)

(m (- n 10) (- d 1))

(m (+ n 11) (+ d 1)))))

(m n 1))

Example output for `(mccarthy 87)`

was shown on the first page. If you want to have some fun, try `(mccarthy -3)`

. You can run the program at http://programmingpraxis.codepad.org/BKsY6oeS.

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 :).