// How can we emulate lambda calculus in C, what are C's limitations?
// Must compile with real Gnu gcc
#include<stdio.h>
#include<stdlib.h>

#define NIL 0
#define BOOL int

typedef unsigned int uint;

typedef int (*intfun)(int);  // type int -> int
typedef BOOL (*intpred)(int);  // int -> bool
typedef int (*intop)(int,int); // (int,int) -> int
typedef void (*action)();


// I and K combinators, Currying in C:
int I(int x) { return x; }
int notk(int x, int y) { return x; }  // not really K, not Curried.
intfun K(int x)
{
  // no direct lambda notation, but Gnu C allows inner functions:
  int inner(int y) { return x; }
  return inner;
} // will this work? Can C create a CLOSURE?

// don't give up!
intfun Km(int x)
{
  // copy x to heap  (copy to local clearly won't work)
  int *hx = (int*)malloc(sizeof(int));
  *hx = x;
  int inner(int y) { return *hx; }
  return inner;
}// still won't work

intfun KI(int x)
{
  int inner(int y) { return y; }  // this is fine, it's *closed*
  return inner;
}
// cons = lambda a.lambda b.lambda c. c a b.  can't do it this way.
// have to go low level directly, even though c is a high-level language.

// map out what linked lists look like in memory:
struct cell
{
  int head;
  struct cell* tail;
};
typedef struct cell* list;
// now define cons, car, cdr:
list cons(int h, list t)
{
  list newcell = (list)malloc(sizeof(struct cell)); // heap allocated
  newcell->head = h;
  newcell->tail = t;
  return newcell;
}//cons
int car(list m) { return m->head; }
list cdr(list m) { return m->tail; }

struct cell CONS(int h, list t) { // return actual struct on stack
  struct cell newcell; // stack allocated
  newcell.head = h;
  newcell.tail = t;
  return newcell;
} // avoids heap allocation, most memory errors, but is this practical?

// although we skipped lambda calc, these functions provide the same level of
// abstraction, so as long as we use them exclusively, we retain all the properties
// of lambda calculus.
// function to test for list membership

BOOL contains(list m, int x)
{
  if (m==NIL) return 0;
  else if (x==car(m)) return 1;
  else return contains(cdr(m),x);
  //we really would like contains to be defined with just one line:
  // return m!=NIL && (x==car(m) || contains(cdr(m),x)); 
  //this is tail recursive because booleans are short-circuited,
  //but the C compiler does not recognize it as tail-recursive.
}
// sum of all values in list
int sumlist(list m)
{
  if (m==NIL) return 0; else return car(m)+sumlist(cdr(m));
}// tail recursive? no.

int listsum(list m)
{
  int iter(list m, int ax)
  {
    if (m==NIL) return ax; else return iter(cdr(m),car(m)+ax);
  }
  return iter(m,0);
}

list reverse(list m)
{
  list iter(list m, list ax)
  {
    if (m==NIL) return ax; else return iter(cdr(m),cons(car(m),ax));
  }
  return iter(m,NIL);
}

list map(intfun f, list m) { // create new list by applying f to each value
  list inner(list m, list stack) {
    if (m==NIL) return stack;
    else return inner(cdr(m), cons(f(car(m)),stack));
  }//inner tail-recursive function
  return reverse(inner(m,NIL));
}//map

// higher order functions:
void repeat(action a, uint n) // repeat action n times.
{
  a();
  if (n>0) repeat(a,n-1);
}

// functions that take functions as arguments.
// instead of contains, a more generic "there exists function"
BOOL exists(intpred p, list m)
{
  //return m!=NIL && (p(car(m)) || exists(p,cdr(m));  //tail recursive
  if (m==NIL) return 0;
  else if (p(car(m))) return 1;
  else return exists(p,cdr(m));
}

int left_reduce(list m, intop op) // assumes m is not empty
{
  int iter(list m, int ax)
  {
    if (m==NIL) return ax; else return iter(cdr(m),op(ax,car(m)));
  }
  return iter(cdr(m),car(m)); // will crash if there's no car
}

int reduce(list m, intop op, int left_id) // ax is initially left-identity
{
  // little issue with - having no left-id  (id-x=x)
  int inner(list m, int ax)
  {
    if (m==NIL) return ax; else return inner(cdr(m),op(ax,car(m)));
  }
  if (m==NIL) return left_id; else return inner(cdr(m),car(m));
}
// version of reduce that's right-associative

int fold1(list m, intop op, int right_id) // not tail-recursive
{
  if (m==NIL) return right_id;
  else return op(car(m),fold1(cdr(m),op,right_id));
}// not tail-recursive

    
//int apply(intfun f, int x) {return f(x);}

// list delete - should hide this somehow, certainly not pure lambda calculus
void dealloc(list m)
{
  if (m!=NIL) { // don't dealloc twice!
    list cdrm = cdr(m);
    free(m);
    dealloc(cdrm);
  }
}

int main() // only main can call printf
{
   printf("(K 1 2): %d\n",K(1)(2));
   intfun K1 = K(1); // returns a function that waits for second arg

   //printf("apply: %d\n", apply(K1,5));

   printf("K1 2: %d\n",K1(2)); // should also print 1
   intfun K3 = K(3);
   printf("K3 4: %d\n",K3(4)); // should print 3, and does.

   //But  ...
   //printf("K1 2: %d\n",K1(2)); // will no longer print 1!

  // why? because the 1 was popped off of the stack - we were just
  // lucky that it wasn't replaced by something else the first time we called
  // K1(2).

  // stuff with lists:
  // try to allocate a list directly on stack, simplifies memory management:
  struct cell D = CONS(8,NIL);
  struct cell C = CONS(6,&D);  // can't do CONS(6,&CONS(4,&D))
  struct cell B = CONS(14,&C);
  struct cell A = CONS(2,&B);  
  list M = &A;  // stack allocated list, painfully created.
  // cleary not practical for creating large lists.

   list m = cons(2,cons(3,cons(17,cons(7,cons(11,NIL)))));
   int print(int x) { printf("%d ",x); return 0; } // dummy return val, but..
   map(print,m); // prints list
   printf("\n");
   BOOL even(int x) { return x%2==0; }
   printf("even prime: %d\n", exists(even,m));
   int larger(int a, int b) {if (a>b) return a; else return b;}
   printf("largest: %d\n", reduce(m,larger,0x80000000));

  list m2 = cons(1,cdr(cdr(m)));
  dealloc(m);
  list m3 = cons(10,cons(20,cons(30,NIL)));
  map(print,m2); // should print 1 17 7 11
  printf("\n");

  void f() {printf("hello\n");}
  repeat(f,10);

  int subtract(int x, int y) { return x-y; }
  m = cons(5,cons(3,cons(2,NIL)));
  printf("reduce: %d\n", left_reduce(m,subtract));
  printf("fold: %d\n", fold1(m,subtract,0));  
  return 0;
}