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