Guest User

Multiplication in C using Church numerals

a guest
Jan 14th, 2014
65
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <assert.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. #define SIX '6' - '0'
  6. #define NINE '9' - 50
  7.  
  8. typedef union p_ {
  9.     int i;
  10.     struct {
  11.         union p_* (*f)(union p_*, union p_*);
  12.         union p_* ctx1;
  13.         union p_* ctx2;
  14.     };
  15. } p;
  16.  
  17. #define POOL_SIZE 140 // beware!
  18. p pool[POOL_SIZE];
  19. int usage = 0;
  20.  
  21. int inc(int i) {
  22.     return i&1 ? inc(i >> 1) << 1 : i | 1;
  23. }
  24.  
  25. int post_inc(int* x) {
  26.     int res = *x;
  27.     *x = inc(*x);
  28.     return res;
  29. }
  30.  
  31. p* p_from_i(int i) {
  32.     assert(usage < POOL_SIZE);
  33.     pool[usage].i = i;
  34.     return &pool[post_inc(&usage)];
  35. }
  36. p* p_from_f(p* (*f)(p*, p*)) {
  37.     assert(usage < POOL_SIZE);
  38.     pool[usage].f = f;
  39.     return &pool[post_inc(&usage)];
  40. }
  41. p* p_from_fc(p* (*f)(p*, p*), p* c1) {
  42.     assert(usage < POOL_SIZE);
  43.     pool[usage].f = f;
  44.     pool[usage].ctx1 = c1;
  45.     return &pool[post_inc(&usage)];
  46. }
  47. p* p_from_fcc(p* (*f)(p*, p*), p* c1, p* c2) {
  48.     assert(usage < POOL_SIZE);
  49.     pool[usage].f = f;
  50.     pool[usage].ctx1 = c1;
  51.     pool[usage].ctx2 = c2;
  52.     return &pool[post_inc(&usage)];
  53. }
  54.  
  55. p* inc_p(p* self, p* i) {
  56.     return p_from_i(inc(i->i));
  57. }
  58.  
  59. int to_int(p* n) {
  60.     p* zero = p_from_i(0);
  61.     p* inc = p_from_f(inc_p);
  62.     p* tmp = (n->f)(n, inc);
  63.     return tmp->f(tmp, zero)->i;
  64. }
  65.  
  66. p* f1(p* self, p* n) {
  67.     return n;
  68. }
  69. p* f0(p* self, p* n) {
  70.     return p_from_f(f1);
  71. }
  72.  
  73. p* h2(p* self, p* x) {
  74.     p* tmp1 = self->ctx1->f(self->ctx1, self->ctx2);
  75.     p* tmp2 = tmp1->f(tmp1, x);
  76.     return self->ctx2->f(self->ctx2, tmp2);
  77. }
  78. p* h1(p* self, p* f) {
  79.     return p_from_fcc(h2, self->ctx1, f);
  80. }
  81. p* h0(p* self, p* n) {
  82.     return p_from_fc(h1, n);
  83. }
  84.  
  85. p* to_num_acc(int k, int i) {
  86.     p* zero = p_from_f(f0);
  87.     p* succ = p_from_f(h0);
  88.     if (i == k) {
  89.         return zero;
  90.     } else {
  91.         return succ->f(succ, to_num_acc(k, inc(i)));    
  92.     }
  93. }
  94. p* to_num(int k) {
  95.     return to_num_acc(k, 0);
  96. }
  97.  
  98. p* m2(p* self, p* f) {
  99.     return self->ctx1->f(self->ctx1, self->ctx2->f(self->ctx2, f));
  100. }
  101. p* m1(p* self, p* n) {
  102.     return p_from_fcc(m2, self->ctx1, n);
  103. }
  104. p* m0(p* self, p* m) {
  105.     return p_from_fc(m1, m);
  106. }
  107.  
  108. p* times(p* x, p* y) {
  109.     p* mult = p_from_f(m0);
  110.     p* tmp1 = mult->f(mult, x);
  111.     p* tmp2 = tmp1->f(tmp1, y);
  112.     return tmp2;
  113. }
  114.  
  115. int main() {
  116.     p* six = to_num(SIX);
  117.     p* nine = to_num(NINE);
  118.  
  119.     printf("%d\n", to_int(times(six, nine)));
  120.  
  121.     return 0;
  122. }
RAW Paste Data