Last active
May 9, 2018 06:30
-
-
Save mofas/0ee59c81b305dbecabdcc33c16f3ff90 to your computer and use it in GitHub Desktop.
Lambda calculus in JS
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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); | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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)