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

#define NIL 0
#define BOOL int

typedef unsigned int uint;  // convenient name for unsigned int

/* Emulating Scheme in C 

Programming in pure lambda calculus, or a close approximation of it,
implies applying a very high level of abstraction.  We can exercise this
principle in Scheme, but also see how close we can get to it in C.

BASIC RULES: YOU MAY NOT USE ANY OF THE FOLLOWING:

 1. while-loops, for-loops, do-while loops, goto, or any other kind of loop:
    YOU CAN ONLY USE TAIL RECURSION.

 2. The assignment statement that changes the value of a declared variable:
  
    int x = 1; // this is fine and corresponds to (define x 1), (let ((x 1))..
    x = x+1;   // THIS IS NOT ALLOWED  (neither is x++, --x, etc.)

   IDEA IS TO ABSTRACT AWAY USE OF MEMORY. Lambda Calc is "STATELESS"
*/

/*  Another example of tail-recursion: (fibonacci function)
(define (fib n)
 (define (ifib n a b) (if (< n 3) b (ifib (- n 1) b (+ a b)))) ; a,b=1
 (ifib n 1 1))

*/
int fib(int n)
{  
  int ifib(int n, int a, int b) // locally visible function.
  {
    if (n<3) return b; else return ifib(n-1,b,a+b);
  }
  return ifib(n,1,1);
}

// types of functions   
typedef unsigned int uint;
typedef int (*fun)(int); // fun is a TYPE of functions int->int
typedef BOOL (*predicate)(int);
//int f(int x) { return x-1;}
//fun g = f;
typedef int (*binop)(int,int);
typedef void(*action)();  // void f() {..}

void repeat(action f, uint n) // call f n times
{
  if (n>0) {
    f();
    repeat(f,n-1);
  }
}//repeat
//(define (repeat f n) (if (> n 0) (begin (f) (repeat f (- n 1)))))

//(define (applyntimes f x n) (if (< n 1) x (applyntimes f (f x) (- n 1))))
// (applyntimes (lambda (x) (* x x)) 2 4)
int applyntimes(fun f, int x, uint n)
{
  if (n<1) return x; else return applyntimes(f,f(x),n-1);
}

// what about functions that returns functions
// cons (pair) = lambda x:lambda y:lambda s:s(x)(y)  (cons 2 3)
// (define K (lambda (x) (lambda (y) x)))   ((K 1) 2)
//int K(int x, int y) { return x; } // not "Curried"
fun K(int x)
{
  int inner(int y) { return x; }
  return inner;
}
// C allocates args and local vars strictly on the stack

fun Kh(int x)
{
  int *px = (int*)malloc(sizeof(int));  
  *px = x;
  int inner(int y) { return *px; }
  return inner;
} // still doesn't work

struct cell
{
  int item;
  struct cell * next;
};
typedef struct cell* list;
list cons(int x, list n)
{
  list newcell = (list)malloc(sizeof(struct cell));
  newcell->item =x;
  (*newcell).next = n;
  return newcell;
}
int car(list m) { return m->item; }
list cdr(list m) { return m->next; }
// NIL is the empty list (if m==NIL)
/*
(define (length m) (if (null? m) 0 (+ 1 (length (cdr m)))))
int length(list m) {if (m==NIL) return 0; else return 1+length(cdr(m)); }
*/
int length(list m)
{
  int len(list m, int cx)
  {
    if (m==NIL) return cx; else return len(cdr(m),cx+1);
  }
  return len(m,0);
}
// map-reduce  (Google -- Hadoop, Sparc )
list reverse(list m)
{
  // need a stack, initially null
  list irev(list m, list stack)
  {
    if (m==NIL) return stack; else return irev(cdr(m), cons(car(m),stack));
  }
  return irev(m,NIL);
}
/*
(define (map f m) (if (null? m) m (cons (f (car m)) (map f (cdr m)))))
*/
list map(fun f, list m)
{
  list imap(list m, list stack)
  {
    if (m==NIL) return stack;
    else return imap(cdr(m), cons(f(car(m)),stack));
  }
  return reverse(imap(m,NIL));
}

/* reduce  id means bop(x,id)=x for all x
(define (reduce bop id m)
  (if (null? m) id (reduce bop (bop (car x) id) (cdr m))))
  (reduce (lambda (x y) (+ x y)) 0 '(3 4 5 1))
*/
int reduce(binop bop, int id, list m)
{
  if (m==NIL) return id; else return reduce(bop,bop(car(m),id),cdr(m));
}

/* there-exists:
(define (exists p m)   
  (if (null? m) #f 
     (if (p (car m)) #t (exists p (cdr m)))))
*/
BOOL exists(predicate p, list m)
{
  return m!=NIL && (p(car(m)) || exists(p,cdr(m)));
}// is this tail recursive? TRICK QUESTION

BOOL forall(predicate p, list m)
{
  BOOL notp(int x) { return !p(x); }
  return !exists(notp,m);  //forall x.P(x) == !exists x.!P(x)
}

int main()
{
  /*
  printf("%d\n",fib(5));
  void greeting() { printf("hello\n"); }
  repeat(greeting,10);
  int square(int x) { return x*x; }
  printf("%d\n", applyntimes(square, 2, 4)); // 64K

  printf("K(1)(2): %d\n",K(1)(2)); // seems to work, but...   1
  printf("K(3)(4): %d\n",K(3)(4)); // seems to work, but...   3
  fun K1 = K(1);
  fun K3 = K(3);
  printf("K1(2): %d\n",K1(2)); //  should be 1, but printed 3
  printf("K3(4): %d\n",K3(4)); //  should be 3, could crash

  fun Kh1 = Kh(1);
  fun Kh3 = Kh(3);
  printf("Kh1(2): %d\n",Kh1(2)); //  should be 1, but printed 3
  printf("Kh3(4): %d\n",Kh3(4)); //  should be 3, could crash  
  */
  int square(int x) { return x*x; }  
  list m = cons(2,cons(3,cons(13,cons(7,NIL)))); // '(2 3 5 7)
  list sm = map(square,m);
  //print the contents of a list
  int pr(int x) { printf("%d ",x); return 0; }
  map(pr,m);  printf("\n");
  map(pr,sm); printf("\n");

  int larger(int x, int y) { if (x>y) return x; else return y; }
  int max = reduce(larger,0x80000000,m);
  printf("max is %d\n",max);

  BOOL even(int x) { return x%2==0; }
  printf("even: %d\n", exists(even,m));
  printf("even: %d\n", forall(even,m));  
  
  return 0;
}