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.
Programming Praxis 
In Python.
def m91(n): level = 1 while level: print "M(" * level + str(n) + ")" * level if n > 100: n -= 10 level -= 1 else: n += 11 level += 1 print nclass 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++
#include <iostream> using namespace std; int M (int n, int level = 1); int main() { int n = M(87); cout << n << endl; return 0; } int M (int n, int level) { for (int i = 0; i < level; i++) cout << "M("; cout << n; for (int i = 0; i < level; i++) cout << ")"; cout << endl; if (n > 100) return n - 10; else return M(M(n+11, level+1), level); }(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
Writermonad.import Control.Monad.Writer -- Simple recursive version m :: Integer -> Integer m n | n > 100 = n - 10 | otherwise = m . m $ n + 11 -- Recursive with counter and writer for output m' :: Integer -> Int -> Writer [String] Integer m' n c | c <= 0 = do tell [show n] return n | otherwise = do let crc = concat . replicate c tell [crc "M(" ++ show n ++ crc ")"] if n > 100 then m' (n - 10) (c - 1) else m' (n + 11) (c + 1) -- Example main :: IO () main = mapM_ putStrLn $ snd $ runWriter (m' 87 1)An interpreter for “M” expressions in SML
datatype m = I of int | M of m fun step (M (I n)) = if n > 100 then I (n - 10) else M (M (I (n + 11))) | step (M x) = M (step x) | step (I x) = I x fun show x = let fun showM (I x) = print (Int.toString x) | showM (M m) = (print "M("; showM m; print ")") in (showM x ; print "\n") end fun eval (I x) = x | eval x = let val y = step x in (show y; eval y) end (* :- eval (M (I 87)); M(M(98)) M(M(M(109))) ... M(101) 91 *)#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;
}
#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
#!/usr/bin/perl -w use strict; use warnings; my $n = <STDIN>; chomp($n); mprint($n, 1); sub mprint { my $n = shift; my $level = shift; print tostring($n, $level)."\n"; return if $level == 0; mprint($n+11, $level+1) if $n <= 100; mprint($n-10, $level-1) if $n > 100; } sub tostring { my $n = shift; my $level = shift; return "$n" if $level <= 0; return "M($n)" if $level == 1; return "M(".tostring($n, $level-1).")"; }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
#!/usr/bin/perl -w use strict; use warnings; my $n = <STDIN>; chomp($n); mprint($n, 1); sub mprint { my $n = shift; my $level = shift; while($level > 0) { print tostring($n, $level)."\n"; if($n <= 100) { $n += 11; $level++; } else { $n -= 10; $level--; } } print tostring($n, $level)."\n"; } sub tostring { my $n = shift; my $level = shift; return "$n" if $level <= 0; return "M($n)" if $level == 1; return "M(".tostring($n, $level-1).")"; }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 :).