#include<stdio.h>
#include<stdlib.h>

#define Nil 0
#define BOOL int

// define the following functional types (pointers to functions)

typedef int (*intfun)(int);     // integer function  (int -> int)
typedef BOOL (*predicate)(int); // integer predicate (int -> bool)
typedef intfun (*curried)(int); // Curried function (int -> int -> int)
typedef int (*binop)(int,int);  // binary operator (int*int) -> int
typedef void (*action)();          // type unit -> unit
typedef void (*consumer)(int n);      // type int -> unit

// These are TYPES, not functions.

// I and K combinators

void* untyped_I(void* x) { return x; }

// but will simplify this - otherwise will have to typecast

int I(int x) { return x; }

int wrongK(int x, int y) { return x; }

intfun K(int x) {  // type of K is curried.  lambda x.lambda y.x
  int inner(int y) { return x; }
  return inner;
}

// so how can we fix this?  probably not in C - no ability to create
// a CLOSURE.  (C++ will be different)

intfun K2(int x) {
  int* hx = malloc(sizeof(int)); 
  *hx = x; // copy x to heap
  int inner(int y) {
    return *hx;
  }
}// but this will have the same problem: the lifetime of the pointer
// itself will end when K2 returns, and will be replaced by another pointer
// when K2 is called again.  Another problem here is a MEMORY LEAK.

// But KI is OK

intfun KI(int x) {
  //int inner(int y) { return y; }
  //return inner;
  return I;
}

typedef void* (*genericfun)(void*);
genericfun realK(void* x) {
  void* inner(void* y) { return x; }
  return inner;
}

// so can't have curried function that returns a proper closure, elminates
// some of the things we can do in lambda-calculus, in particular data
// structures, pairs. So we have to go "low level" if we wish to have these
// structures.  However, we can create a layer of abstraction above most of
// of the low-level use of memory, and create cons, car cdr that are
// admissible to how they should behave in lambda calculus.
// I.E abstract away the use and management of memory

struct cell {
  int item;
  struct cell* next;
};
// use Nil for empty list
typedef struct cell* list;

list cons(int i, list n) {
  list newcell = malloc(sizeof(struct cell));
  newcell-> item = i;
  newcell->next = n;
  return newcell;
}
int car(list m) { return m->item; }
list cdr(list m) { return (*m).next; }
BOOL isnil(list m) { return m==Nil; }

// abstraction created, no need to worry about memory, pointers, deferencing etc

// except
void freelist(list m) {
  if (!isnil(m)) {
    list tmp = cdr(m);
    free(m);
    freelist(tmp);
  }
}// freelist

////// show ASSIGNMENT. NO ASSIGNMENT. NO LOOPS, NO POINTERS.
// no whiles, no goto!  But you can do something like this:!
void loop(action a, int n) {
  if (n>0) {
    a();
    loop(a,n-1);
  }
}// "loop"

// TAIL RECURSION.

// reverse a linked list
list reverse(list m) {
  list inner_rev(list m, list stack) {
    if (isnil(m)) return stack;
    else return inner_rev(cdr(m),cons(car(m),stack));
  }
  return inner_rev(m,Nil);
}

// map
list map(intfun f, list m) {
  list minner(list m, list stack) {
    if (isnil(m)) return stack;
    else return minner(cdr(m),cons(f(car(m)),stack));
  } // ok to have f free because it's not returned.
  return minner(m,Nil);
}

int reduce(binop op, int ax, list m) {
  if (isnil(m)) return ax;
  else return reduce(op, op(ax,car(m)), cdr(m));
}// initial ax should be left-identity (default value) of op.

// forall
BOOL forall(predicate p, list m) {
  //BOOL and(BOOL a, BOOL b) { return a&&b; }
  //reduce(and,1,map(p,m)); // BOOL and int are the same
  return isnil(m) || (p(car(m)) && forall(p,cdr(m))); // tail recursive?
  // answer: SHOULD BE, but not necessarily with gcc.
  /*
    if (isnil(m)) return 1;
    else if (!p(car(m))) return 0;
    else return forall(p,cdr(m));
   */
}
BOOL exists(predicate p, list m) {
  BOOL notp(int x) { return !p(x); }
  return !forall(notp,m);
}

int main() {
  // does K behave like K should?
  printf("K(1)(2) is %d\n",K(1)(2));
  printf("K(3)(5) is %d\n",K(3)(5));
  // but how about as a Curried function?
  intfun K3 = K(3);
  intfun K1 = K(1);
  
  printf("K1(2) is %d\n",K1(2));  // should print 1
  printf("K3(5) is %d\n",K3(5));  // should print 3
  // explain stack, introduce concept of LIFETIME.

  curried CKI = (curried)realK(I);
  printf("CKI(1)(2) is %d\n",CKI(1)(2));  // should print 2

  intfun KI1 = KI(1);
  intfun KI2 = KI(2);
  printf("KI1(2) is %d\n",KI1(2));
  printf("KI2(4) is %d\n",KI2(4));  

  //intfun K4 = K2(1);
  //intfun K5 = K2(5);
  //printf("K4(2) is %d\n",K4(2));  // should print 4
  //printf("K5(5) is %d\n",K5(5));  // should print 5

  void hello() { printf("hello world\n"); }
  loop(hello,10);

  list m = cons(2,cons(3,cons(5,cons(7,cons(13,cons(11,Nil))))));
  int print(int x) {printf("%d ",x);}
  map(print,m);
  int larger(int a, int b) { if (a>b) return a; else return b; }
  int max = reduce(larger,car(m),cdr(m));
  printf("\nmax is %d\n",max);

  BOOL odd(int x) { return x%2==1; }
  printf("all odd? %d\n", forall(odd,m));
  printf("exists odd? %d\n", exists(odd,m));
  
  freelist(m);
  return 0;
}