Lambda calculus in JS

## lc.js
// We learn lots of functional "concept" when we coding, such as point-free, high order function, avoiding side effect
// function composition.

// We are told they are good and we should code like that way.

// We feel strugging when learn the advanced conecpt like monads, and have difficulty to apply them to our coding.
// Sometime I feel using "functional programming" create more problems or not realistic.

// Like Using Rambda

// Where those idea come from and how they developed?

// we can category programming language into four categories

// imperative / object oriented / functional / logic

// We use imperative lang to manuipate turing machine

// We use OO to encapsulate / organize code

// Why functional pl not be called as function oriented?

// Is fnctional pl is just another way to organize our code?

// To understand functional pl, we need to know what is "function"

// Everything are functions, but not everything are functions

// Alonzo Church invenr lambda calculus as part of his research of the foundations of mathematics.
// 1936 proof the lambda calculus is universal.

// At that time Alonzo Church is colleague of Alan Turning in Princeton University.


// Syntax of lambda calculus
// e := x | (x) => e | e(e)

// static semantic

// dynamic / operational semantic
// alpha conversion / beta reduction / etha conversion

// boolean

const True = x => y => x
const False = x => y => y
const IF = p => thn => els => p(thn)(els)

const AND = a => b => a(b)(a);
const OR = a => b => a(a)(b);
const NOT = a => a(FALSE)(TRUE);

// number

const num0 = f => x => x;
const num1 = f => x => f(x);
const num2 = f => x => f(f(x));
const num3 = f => x => f(f(f(x)));

// arithmetic

const add1 = n => f => x => f(n(f)(x));
const plus = n => m => f => x => n(f)(m(f)(x));
const mult = n => m => f => x => n(m(f))(x);

// sub1 is difficult!!!

// pair

const Pair = a => b => f => f(a)(b);
const Car = p => p(True);
const Cdr = p => p(False);

// It is a convention
// const Nil = x => True;
// const isNil = p => p(x => y => False);

// We can do better by using tag trick.
const Nil = Pair(True)(True)
const isNil = x => Car(x)
const Cons = a => b => Pair(False)(Pair(a)(b))
const Head = x => Car(Cdr(x))
const Tail = x => Cdr(Cdr(x))

// Object
// Object is the poor man's closure
const emptyMap = key => null;
const extend = map => key => value => x => x === key ? value : map(x);


// constant assignment / global environment

(True => False => IF =>  pred => IF(pred)(True)(False)  )(x => y => x)(x => y => y)(p => thn => els => p(thn)(els));


// recursion
var fact = n => (n < 2 ? 1 : n * fact(n - 1));
var fact2 = f => n => (n < 2 ? 1 : n * f(n - 1));
var fact3 = (f => n => (n < 2 ? 1 : n * f(f)(n - 1)))(f => n => (n < 2 ? 1 : n * f(f)(n - 1)));
var fact4 = (x => x(x))(f => n => (n < 2 ? 1 : n * f(f)(n - 1)));

// We did it!
(x => x(x))(f => n => (n < 2 ? 1 : n * f(f)(n - 1)))(5);

var Ys = x => x(x);
Ys(f => n => (n < 2 ? 1 : n * f(f)(n - 1)))(6)

// However, it is a little bit annoy, we need to apply f to f everytime we make recursive call.
// Can we do it better?
// How about write a function that help us to apply them?

// var Ys = f => (x => x(x))(f);
// var Ys = f => (x => x(x))(x => f(x));
var Y = f => (x => x(x))(x => f(y => x(x)(y)));
Y(f => n => n < 2 ? 1 : n * f(n - 1))(6);


// effect
const sumDivByMax = arr => {
  let sum = 0;
  let max = arr[0];

  for(let i = 0; i < arr.length ;i++){
    sum = sum + arr[i];
    if(arr[i] > max){
      max = arr[i];
    }
  }
  return sum * max;
}

// you may want to use two recursion to avoid using side effect in your code.
// let me force you must have side effect

// var sumFn = ..

// stateFn(1)(2)();     // return 3
// stateFn(1)(2)(3)();  // return 6

const stateFn = f => (x=> x(x))(y => n => m => m ? y(y)(f(n, m)) : n );
const sumFn = stateFn((x, acc) => x + acc);
sumFn(1)(2)(3)();
sumFn(1)(2)(3)(4)();
sumFn(1)(2)(3)(4)(5)();


// Stream
const stream = f => (x=> x(x))(y => n => [n, (m)=>y(y)(f(n, m))]);
const addStream = stream((n , m) => n + m);
addStream(0)[0];
addStream(0)[1](1)[0];
addStream(0)[1](1)[1](2)[0];

const multStream = stream((n , m) => n * m);
multStream(1)[0];
multStream(1)[1](3)[0];
multStream(1)[1](3)[1](5)[0];


// Infinity
// const omega = (f => f(f))(f => f(f))

// Hunger function
const hunger = (f => _ => f(f))(f => _ => f(f));

// Flow control
// let see how to break / early return recursion.

const sumOfNullableList = arr => {
  let sum = 0;
  for(let i = 0; i < arr.length; i++){
    if(arr[i] !== null){
      sum = sum + arr[i];
    } else {
      return -1;
    }
  }
  return sum;
}

sumOfNullableList([1, 2, 3, 4]) // 10
sumOfNullableList([1, 2, null, 4]) // -1


// Continuation
const fib = n => n < 2 ? 1 : fib(n-1) + fib(n-2);

const fib_cps = (n, k) => {
  console.log(n);
  if (n < 2) {
    return k(1);
  }
  else {
    return fib_cps(n - 1, c1 => {
      return fib_cps(n - 2, c2 => {
        return k(c1 + c2);
      })
    });
  }
}

// Early return
var times = arr => {
  const [x, ...xs] = arr;
  console.log('times', x);
  return x !== undefined ? x * times(xs) : 1;
}

times([1,2,3,4,5]);
times([0,1,2,3,4,5]);


var timesCps = (arr, k) => {
  const [x, ...xs] = arr;
  console.log('timesCps', x);
  if(x !== undefined){
   if(x === 0){
     return k(0);
   } else {
     return x * times(xs, k);
   }
  }
  else {
    return k(1);
  }
}

timesCps([1,2,3,4,5], x => x);
timesCps([0,1,2,3,4,5], x => x);


const sumOfNullableListRes = (ls, k) => {
  if(ls.length){
    const [x, ...xs] = ls;
    if(x == null) {
      return -1;
    }
    else {
      return sumOfNullableListRes(xs, v => k(v+x));
    }
  }
  else {
    return k(0);
  }
}

sumOfNullableListRes([1, 2, 3, 4], x=>x);
sumOfNullableListRes([1, 2, null, 4], x=>x);

const fib = n => {
  console.log('fib', n);
  return n < 2 ? 1 : fib(n - 1) + fib(n - 2);
};

const fib_sps = (n, store) => {
  console.log('fib_sps', n);
  if (store(n)) {
    return [store(n), store];
  } else if (n < 2) {
    return [1, store];
  } else {
    const [val_n1, store1] = fib_sps(n - 1, store);
    const [val_n2, store2] = fib_sps(n - 2, store1);
    const value = val_n1 + val_n2;
    return [value, extend(store2)(n)(value)];
  }
};

console.log(fib(10));

const ret_sps = fib_sps(10, emptyMap)[0];
console.log(ret_sps);