Deriving the Y-combinator in Objective-C. Based on http://igstan.ro/posts/2010-12-01-deriving-the-y-combinator-in-7-easy-steps.html

test-y.m

// clang -Wall -fobjc-arc -framework Foundation -o test-y test-y.m

// Based on http://igstan.ro/posts/2010-12-01-deriving-the-y-combinator-in-7-easy-steps.html

#import <Foundation/Foundation.h>

int main(int argc, char **argv)
{
  // Version 1
  // Simple factorial recursive version, __block needed to capture fact inside
  // the block by reference.
  __block int (^fact1)(int n) = ^int(int n) {
    if (n < 2) return 1;
    return n * fact1(n - 1);
  };

  // Version 2
  // Ugly hiding of recursive type behind id, and casting back to a very complex
  // type inside the function... twice.
  int (^fact2)(int) = (^(id f) {
    return ^int(int n) {
      if (n < 2) return 1;
      return n * ((int (^(^)(id))(int))f)(f)(n - 1);
    };
  })(^(id f) {
    return ^int(int n) {
      if (n < 2) return 1;
      return n * ((int (^(^)(id))(int))f)(f)(n - 1);
    };
  });

  // Version 3
  // Remove duplication of code inside an external helper.
  // Hiding and casting still there.
  int (^(^recursive3)(id))(int) = ^(id f) {
    return ((int (^(^)(id))(int))f)(f);
  };
  
  int (^fact3)(int) = recursive3(^(id f) {
    return ^int(int n) {
      if (n < 2) return 1;
      return n * ((int (^(^)(id))(int))f)(f)(n - 1);
    };
  });

  // Version 4
  // Hide the f(f)(n - 1) call inside a g function. Factorial is more similar to
  // the original version.
  int (^(^recursive4)(id))(int) = ^(id f) {
    return ((int (^(^)(id))(int))f)(f);
  };
  
  int (^fact4)(int) = recursive4(^(id f) {
    int (^g)(int) = ^int(int n) {
      return ((int (^(^)(id))(int))f)(f)(n);
    };
  
    return ^int(int n) {
      if (n < 2) return 1;
      return n * g(n - 1);
    };
  });

  // Version 5
  // Now the factorial function is mostly what we started with.
  int (^(^recursive5)(id))(int) = ^(id f) {
    return ((int (^(^)(id))(int))f)(f);
  };
  
  int(^(^wrap5)(int(^(^)(int (^)(int)))(int)))(int) = ^(int(^(^h)(int (^)(int)))(int)) {
    return recursive5(^(id f) {
      int (^g)(int) = ^int(int n) {
        return ((int (^(^)(id))(int))f)(f)(n);
      };
  
      return h(g);
    });
  };
  
  int (^fact5)(int) = wrap5(^(int (^g)(int)) {
    return ^int(int n) {
      if (n < 2) return 1;
      return n * g(n - 1);
    };
  });

  // Version 6
  // Inline g inside wrap
  int (^(^recursive6)(id))(int) = ^(id f) {
    return ((int (^(^)(id))(int))f)(f);
  };
  
  int(^(^wrap6)(int(^(^)(int (^)(int)))(int)))(int) = ^(int(^(^h)(int (^)(int)))(int)) {
    return recursive6(^(id f) {
      return h(^int(int n) {
        return ((int (^(^)(id))(int))f)(f)(n);
      });
    });
  };
  
  int (^fact6)(int) = wrap6(^(int (^g)(int)) {
    return ^int(int n) {
      if (n < 2) return 1;
      return n * g(n - 1);
    };
  });

  // Version 7
  // Inline recursive inside wrap, which is Y combinator
  int(^(^Y7)(int(^(^)(int (^)(int)))(int)))(int) = ^(int(^(^h)(int (^)(int)))(int)) {
    return (^(id f) {
      return ((int (^(^)(id))(int))f)(f);
    })(^(id f) {
      return h(^int(int n) {
        return ((int (^(^)(id))(int))f)(f)(n);
      });
    });
  };
  
  int (^fact7)(int) = Y7(^(int (^g)(int)) {
    return ^int(int n) {
      if (n < 2) return 1;
      return n * g(n - 1);
    };
  });

  // Version 8
  // Easier to read with a typedef.
  typedef int (^IntIntFn)(int);
  IntIntFn (^Y8)(IntIntFn (^)(IntIntFn)) = ^(IntIntFn (^h)(IntIntFn)) {
    return (^(id f) {
      return ((IntIntFn (^)(id))f)(f);
    })(^(id f) {
      return h(^int(int n) {
        return ((IntIntFn (^)(id))f)(f)(n);
      });
    });
  };
  
  IntIntFn fact8 = Y8(^(IntIntFn g) {
    return ^int(int n) {
      if (n < 2) return 1;
      return n * g(n - 1);
    };
  });

  // Version 9
  // Trying to hide the typesystem doesn't work that well. We can generate Y
  // combinators for a typedef, but then the last block (the one inside h) needs
  // to know the parameters of the typedef and the names of those parameters.
  // This preprocessor macro works for functions with only one parameter.
  // typedef int (^IntIntFn)(int);
  #define Y(fntype, ptype, ...) (^fntype(fntype (^h)(fntype)) { \
    return (^(id f) { \
      return ((fntype (^)(id))f)(f); \
    })(^(id f) { \
      return h(^(ptype n) { \
        return ((fntype (^)(id))f)(f)(n); \
      }); \
    }); \
  })(__VA_ARGS__)
  
  IntIntFn fact = Y(IntIntFn, int, ^(IntIntFn g) {
    return ^int(int n) {
      if (n < 2) return 1;
      return n * g(n - 1);
    };
  });

  typedef float (^FloatFloatFn)(float);
  FloatFloatFn fib = Y(FloatFloatFn, float, ^(FloatFloatFn g) {
    return ^float(float n) {
      if (n == 0.f) return 0.f;
      if (n == 1.f) return 1.f;
      return g(n - 1.f) + g(n - 2.f);
    };
  });

  NSLog(@"5! = %d", fact(5));
  NSLog(@"fib(15) = %f", fib(15.f));

  return 0;
}