Instantly share code, notes, and snippets.

# mofas/lc.js Last active May 9, 2018

Lambda calculus in 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; 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); addStream(0)(1); addStream(0)(1)(2); const multStream = stream((n , m) => n * m); multStream(1); multStream(1)(3); multStream(1)(3)(5); // 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); console.log(ret_sps);
Owner Author

### mofas commented May 8, 2018 • edited

 Future talk Lambda extend : Continuation / Logic programming(Unification) / Category Theory (Monads) / Partial Evaluation(Staging) Type : Lambda Cube ( STLC / Type Operators / System F / System T / Dependent Type)