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.

About these ads

Pages: 1 2

10 Responses to “McCarthy’s 91 Function”

  1. Paul said

    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 n
    
  2. raj said

    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));
    }
    }

  3. John said

    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);
    }
    
  4. Jussi Piitulainen said


    (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)))))

  5. Graham said

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

    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)
    
  6. 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
    *)
    
  7. #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;
    }

  8. #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;
    }
    
  9. Juan Ignacio Saba said

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

  10. Juan Ignacio Saba said

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: