L&L: =>

arrow.js

// this code is safe to copy/paste into your browser
// but you should really try to write it out line-by-line ;)

// this gist is based on a number of other excellent introductions to lambda calculus
// classic: https://github.com/sjsyrek/presentations/blob/master/lambda-calculus/lambda.js
// ornithology: https://www.youtube.com/watch?v=3VQ382QG-y4&t=3349s
// and this one, in Ruby, called "Programming With Nothing" (excellent title) https://www.youtube.com/watch?v=VUhlNx_-wYk

pair = x => y => a => a(x)(y)

p1 = pair(1)(2)
p1(x => y => x)

left = x => y => x
right = x => y => y

first = p => p(left)
second = p => p(right)

first(p1)

cons = x => xs => pair(x)(xs)

head = first
tail = second

// list = cons(1)(cons(2)(cons(3)(...?)))

// we want empty_list to return itself if we try to get first or second

empty_list = a => a(empty_list)(empty_list)

list = cons(1)(cons(2)(cons(3)(empty_list)))

head(list)
head(tail(list))
head(tail(tail(list)))
head(tail(tail(tail(list))))

// naturally now that we have lists we need map

map = f => xs => is_empty(xs) ? empty_list : cons(f(head(xs)))(map(f)(tail(xs)))

// but ? : is kind of lame...

map = f => xs => if_then_else(is_empty(xs))
  (empty_list)
  (cons(f(head(xs)))(map(f)(tail(xs))))

is_empty = xs => xs === empty_list

// laaaame should be

is_empty = xs => equals(xs)(empty_list)

// equals = p => q => p === q // ugh...

/*
There are just two boolean values, and we know how they should behave so,
we should be able to make functions that behave the same way without too much trouble.

we want something that directs traffic, for doing stuff like `p ? x : y` let's try...
*/

TRUE = left
FALSE = right

// case analysis!

// and = p => q => p(?)(?)
// and = FALSE => q => FALSE(?)(?) so it will return the second value
// and = FALSE => q => FALSE(?)(FALSE) we just short circuit out
// and = TRUE => q => TRUE(?)(FALSE) it will return the first value
// and = TRUE => q => TRUE(q(?)(?))(FALSE) result depends on q
// and = TRUE => FALSE => TRUE(FALSE(TRUE)(FALSE))(FALSE) returns the second TRUE && FALSE === FALSE
// and = TRUE => FALSE => TRUE(TRUE(TRUE)(FALSE))(FALSE) returns the first TRUE && TRUE == TRUE

and = p => q => p(q(TRUE)(FALSE))(FALSE)
and = p => q => p(q)(FALSE) // simplify, if q is TRUE return TRUE, if q is FALSE return FALSE... just return q!
and = p => q => p(q)(p) // same deal, if p is FALSE return FALSE is the same as just return p

// or = p => q => p(?)(?)
// or = p => q => p(p)(?) // if p is TRUE return p (short circuit)
// or = p => q => p(p)(q) // is p is FALSE then p || q depends only on q

or = p => q => p(p)(q) // nooice!

not = p => p(FALSE)(TRUE)

equals = p => q => p(q(TRUE)(FALSE))(q(FALSE)(TRUE))
equals = p => q => p(q)(not(q))

// woo!

// is_empty = ... ugh but this is only comparing bools, how do we compare lists?
// let's just add an empty flag to our list object

cons = x => xs => pair(FALSE /* not empty */)(pair(x)(xs))
empty_list = pair(TRUE)(pair(empty_list)(empty_list)) // this won't work
empty_list = x => pair(TRUE)(pair(empty_list)(empty_list))(x) // we need to defer it

head = xs => first(second(xs))
tail = xs => second(second(xs))

list = cons(1)(cons(2)(cons(3)(empty_list)))

head(list)
head(tail(list))
head(tail(tail(list)))
head(tail(tail(tail(list))))

is_empty = xs => equals(first(xs))(TRUE)

is_empty(list)
is_empty(empty_list)
is_empty(head(empty_list))
is_empty(tail(empty_list))
is_empty(tail(tail(tail(list))))

if_then_else = p => x => y => p(x)(y) // this is basically equivalent to just using the boolean straight up so...

map = f => xs => is_empty(xs)
  (empty_list)
  (cons(f(head(xs)))(map(f)(tail(xs))))

try {
  map(x => x + 1)(list)
} catch (e) {
  console.log(e.message)
}

/* Javascript has eager evaluation, so in the expression
`if_then_else(p)(f(x))(g(x))`
_both_ f(x) and g(x) are evaluated, but only one is returned
compare this to
`p ? f(x) : g(x)` in which only one of the two branches is evaluated
*/

map = f => xs => is_empty(xs)
  (empty_list)
  (x => cons(f(head(xs)))(map(f)(tail(xs)))(x)) // delayed

l2 = map(x => x + 1)(list)

head(list)
head(tail(list))
head(tail(tail(list)))
head(tail(tail(tail(list))))

// woo!!! DONE!!!

// ... well, almost... there are two things wrong with the above code
// first, it uses numbers like 1 and operators like +
// second, map = map only works because javascript's `=` operator has certain properties
// but we _only_ want `=` to alias one thing to another
// if we alias map to map, then when we try to expand the expression we get an infinite recurse

/*
is_empty(empty_list)
(xs => equals(first(xs))(TRUE))(x => pair(TRUE)(pair(empty_list)(empty_list))(x))
(xs => (p => q => p(q)(not(q)))((p => p(left))(xs))((x => x => y)))(x => pair(TRUE)(pair(empty_list)(empty_list))(x))
... etc we are just doing find/replace

you can implement the whole transpiler this way

but with map...

f => xs => is_empty(xs)
  (empty_list)
  (x => cons(f(head(xs)))(map(f)(tail(xs)))(x))

f => xs => is_empty(xs)
  (empty_list)
  (x => cons(f(head(xs)))((f => xs => is_empty(xs)
  (empty_list)
  (x => cons(f(head(xs)))((f => xs => is_empty(xs)
  (empty_list)
  (x => cons(f(head(xs)))((f => xs => is_empty(xs)
  (empty_list)
  (x => cons(f(head(xs)))(map(f)(tail(xs)))(x)))(f)(tail(xs)))(x)))(f)(tail(xs)))(x)))(f)(tail(xs)))(x))

... the expansion step never ends
*/

/* We need some way to do recursion without using the alias in the function definitions...
we can achieve this with... COMBINATORS!!!

Which will be the subject of my next L&L
*/