Skip to content

Instantly share code, notes, and snippets.

@mofas
Last active May 9, 2018 06:30
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mofas/0ee59c81b305dbecabdcc33c16f3ff90 to your computer and use it in GitHub Desktop.
Save mofas/0ee59c81b305dbecabdcc33c16f3ff90 to your computer and use it in GitHub Desktop.
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[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);
@mofas
Copy link
Author

mofas commented May 8, 2018

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)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment