Introduce to Y Combinator with Javascript

layout	title	date	tags
title	Introduce to Y Combinator with Javascript	2018-03-24 15:46:19 -0700

梳理总结一下自己对 Y Combinator 理解，也来重新认识这样一个有趣的东西。

在开始之前有必要先来介绍一下图灵机和λ演算之间的关系。

图灵机

图灵机最早是由 Alan Mathison Turing 在1936年提出的一种抽象计算模型，是用来描述一种让机器来进行“计算”理论方法。当然图灵机也是一个可以被建造出来真正计算的机器，那么图灵机究竟长什么样子？描述了一个什么理论呢？推荐大家自行阅读下面相关文章：

图灵机具体介绍

計算機理論的始祖---圖靈機

图灵机长什么样——现代技术模拟版（youtube 视频）

λ演算

λ演算是数学家 Alonzo Church 在1928首次发表的另外一种抽象计算过程的方法，图灵机通过输入、输出、状态、规则表来描述一个计算过程。而λ演算则完全不同，实际上λ演算的发明者 Alonzo Church 也是图灵的老师，这两种描述计算的方法虽然诞生于同一个时代但风格却是截然不同的。

关于图灵计算和λ演算的对比仁者见仁智者见智，下面是王银的一些理解：丘奇和图灵图灵的光环

λ演算的基本语法

在 lambda 中只有三种表达式：

1.函数定义

λx. x
--------
x => x // javascript 语法

2.标识符（变量）引用

x  // 对 x 这个标识符的引用，这句话本身也是合法的 lambda 表达式

3.函数调用

(λx. plus x x) y
----------
(x => x + x)(y)  // javascript 语法

就这么简单吗？还是没有搞清楚这个λ演算能做什么事情！下面我们来看一些例子：

定义一个加法函数

λ.x (λ.y (plus x y))
------------
x => y => x + y // javascript 语法

大概是因为遵循简单的原则，lambda 演算只接受一个参数作为输入，那么想要实现传入两个参数 x/y 然后相加这样的功能就需要用到另外一种形式即 Currying。先接受 x 这样一个参数（假设 x 是10），然后返回另外一个 lambda λ.y 10 + y，这时候再传入一个 y 参数即可进行计算。乍一看你可能会觉得这种写法非常不直观，为什么不直接用 (x, y) => x + y 这样的形式呢？我的理解是保持原子级别的简单，一生二，二生三，三生无穷。至于你真的想接受两个参数我想也是可以通过语法糖来解决这个问题的。

表达 if/else 语句

再表达 if/else 之前先来定义一下如何表达布尔值

true = λ.x λy. x
false = λ.x λy. y

// 如何表达 true ? a : b
(λ.x λ.y x) a b
代入a化简: (λ.y a) b
继续化简: a

可以看到 lambda 版本的三元表达式也是非常清晰的，甚至在整个化简过程就像你在作业本上解题的过程，这样一种逻辑描述语言不能不用美妙来形容。

那么究竟 lambda 演算和我们今天的主角 Y Combinator 又有什么关系呢？这要从编程语言开始说起了，最近几年函数式编程突然开始在各种库如 redux/react 中流行了起来，但实际上函数式编程这一思想其实是可以追溯到 lambda 演算的。基于 lambda 演算发展而来的编程语言有 Lisp、Haskell 以及 Standard ML等。我们可以看到在 lambda 演算中和基于图灵机演变而来的语言有一些区别，这样的语言一般没有 for 这样的循环以及赋值这样的语句。那么普遍的一个疑问就是如果没有赋值和循环这样的东西存在，这样的编程语言是图灵完全或者说能和基于图灵机演变而来的语言有等价计算能力吗?下面我们通过定义一个阶乘函数来揭开谜底。

const factorial = n => n === 0 ? 1 : n * factorial(n - 1);
factorial(5) // 120

这是一个很普通的利用递归实现的阶乘函数，那么试想一下如果使用基于 lambda 演算的语言没有 const 这样的定义如何来实现这样的一个阶乘函数，没有函数名又要如何在函数中进行自递归调用。

首先我们可以知道的是及时没有 const 这样的关键字存在我们依然有一种可以给变量命名引用的方法即λx.x 中的 λx。

x => x // 函数的参数 x 其实是一种变量引用的方式
x => x() // 如果传入一个函数，那么内部是可以执行这个函数来达到递归的效果的
fn => n => n === 0 ? 1 : n * fn(n - 1) // 似乎来看这样就可以做到通过传入一个参数来进行自调用

这样一个函数要怎么去调用呢？开动一下脑子...

是不是自己调用自己就好了呢？

(fn => n => n === 0 ? 1 : n * fn(n - 1))(fn => n => n === 0 ? 1 : n * fn(n - 1))

(...)(5)得到的结果是 NaN，也就是说计算失败了，所以哪里出了问题呢？

fn => n => n === 0 ? 1 : n * fn(n - 1)

仔细看这个函数，其实是接受一个函数作为参数，返回的也是另外一个函数，没错返回值是需要调用一下的。

fn => n => n === 0 ? 1 : n * fn()(n - 1) // fn(n-1) 这里是需要先调用一下自身得到生成的函数的
(fn => n => n === 0 ? 1 : n * fn()(n - 1))(fn => n => n === 0 ? 1 : n * fn()(n - 1)) // 来运行一下，结果是 Uncaught TypeError: fn is not a function

所以哪里出了问题呢? fn 也就是这个函数的参数目前不是一个函数

fn()(n - 1) // fn() 的返回值不是一个函数，因为 fn 接受一个函数作为参数，因此我们需要
fn(fn)(n - 1)

(fn => n => n === 0 ? 1 : n * fn(fn)(n - 1))(fn => n => n === 0 ? 1 : n * fn(fn)(n - 1))(5)

yay ~~ 成功了 可以看到虽然整个过程比较艰难但我们仍然实现了匿名函数递归做到阶乘的效果，那上面这样一长串代码可以说可读性很差，而且违反了我们所提倡的 DRY 原则。所以下一步我们就来一步一步优化上面的函数。

// 先来定义这样一个函数用来消除重复
const runFn = f => f(f);
(f => f(f))  // 只是用匿名函数的形式来表达了一下
(f => n => n === 0 ? 1 : n * f(f)(n - 1))

这里的 n * f(f)(n - 1) 中的 f(f) 的作用就是得到整个递归函数函数体，这一部分也可以拿出来，因为这个阶乘的业务逻辑是没有关系的。

(f => f(f))
(f =>
  (g => n => n === 0 ? 1 : n * g(n - 1))
  (f(f))
)

似乎上面的程序应该是合理的，我们提出了 f(f) 变成了 g，现在中间的函数变成了：

                          g => n => n === 0 ? 1 : n * g(n-1)
对比原始函数： const factorial = n => n === 0 ? 1 : n * factorial(n - 1);

可以看到我们的函数已经非常接近于我们期待的阶乘函数的定义了，然而执行上面的函数会有问题。

(f => f(f))
(f =>
  (g => n => n === 0 ? 1 : n * g(n - 1))
  (f(f))
)
// Uncaught RangeError: Maximum call stack size exceeded

原因是什么呢？试想你定义了这样一个函数会有问题吗？

const f => f;
f(x - 1)

函数的结果还是会报错，因为 Javascript 的求值策略是 call-by-value 也就是说在 f 这个函数执行之前，参数 x - 1 已经被执行了，函数内部只知道一个值。因此我们上面定义的函数爆出死循环的原因也就是因为我们的 (f(f)), 解决办法就是让这个函数懒执行: (v => f(f)(v))

(f => f(f))
(f =>
  (g => n => n === 0 ? 1 : n * g(n - 1))
  (v => f(f)(v))
)

现在我们的函数可以正常运行了，那么接下来还要怎么优化呢？那就是想办法把我们的业务逻辑函数也就是阶乘函数的主体提取出来 g => n => n === 0 ? 1 : n * g(n - 1)

const Y = logic =>
  (f => f(f))
  (f =>
    logic
    (v => f(f)(v))
  )

const Y = logic =>
  (f =>
    logic
    (v => f(f)(v))
  )(f =>
    logic
    (v => f(f)(v))
  )

上面这个函数就是我们今天的主角，Y Combinator 啦，这样的一个函数应该怎么使用呢：

Y(g => n => n === 0 ? 1 : n * g(n - 1))

我们想要的阶乘函数就这样定义好了, Y 这个函数自动的把传入的函数 wrapper 了一层并给这个匿名函数了一个名字 g 以方便自调用。实际上我们的 Y 函数还可以继续优化，毕竟我们是在写 Javascript :p

Y := λf.(λx.f (x x)) (λx.f (x x))

Y g := (λf.(λx.f (x x)) (λx.f (x x))) g
     = (λx.g (x x)) (λx.g (x x))
     = g ((λx.g (x x)) (λx.g (x x))) //(λx.g (x x)) (λx.g (x x)) 这一块其实就等于 Y g
     = g (Y g)

const Y = g => g(Y(g)); // 因为求值策略的问题，我们需要把 Y(g) 这个函数延迟执行
const Y = g => g(() => Y(g))  // 但是这种写法也存在一个问题，就是我们的业务逻辑函数想要递归调用自己的时候先要执行以下自己得到递归函数体

传统的 Y 如何调用：Y(g => n => n === 0 ? 1 : n * g(n - 1))
精简版 Y 如何调用：Y(g => n => n === 0 ? 1 : n * g()(n - 1))

TBC....

什么是 combinator? 如果一个函数没有自由变量，那我们称这个函数为 combinator。

什么是自由变量？如果一个变量在函数声明的时候是未定义的，那这个变量就是自由变量。

什么是 Fixed point 不动点？ cos(0.73908513321516067) 一直等于 0.73908513321516067 所以这个数字 0.73908513321516067 就是 cos 函数的不动点。

nothingrealhappen/post.md

图灵机