函数式编程的数学基础（八）函数式编程

lambda演算作为图灵机的等价，理论上我们能够知道它能够作为任何编程语言的模型。（即使是过程式语言）

lambda演算与函数式编程

如果我们只保留JavaScript的箭头函数和函数调用，那么我们可以轻易发现JavaScript语言和Lambda演算的对应关系。

对于编程语言中的基本类型，如整型，我们可以理解为邱奇数，也可以理解为带类型的lambda表达式。

与之对应的运算符，我们则可以理解为预先定义的函数。

值得一提的是，常量可以理解为函数的参数，只要在代码外套一个函数即可，以下是一个综合例子：

const a = 1;
const b = 2;
a + b;

(\lambda a.\lambda b.+\ a\ b)\ 1\ 2

若出现递归调用，则必须借助Y组合子，请看以下例子：

const f = (s, i) => 
    i <= 100 ? f(s + i, i + 1) : s
f(0, 0);

(Y\ \lambda f.\lambda s. \lambda i. ((<=\ i\ 100)\ (f\ (+\ s\ i)\ (+\ i\ 1))\ s))\ 0\ 0

对于更标准的函数式语言，此对应关系更为明显。

对于一门现代编程语言来说，必定要处理时间、随机数、输入输出、网络等，所以几乎找不到纯粹无副作用函数的编程语言。下表总结了一些典型的编程语言与函数式编程之间的联系：

编程语言	有闭包特性	函数是一等公民	有过程式特性	通常认为是函数式的
Haskell	是	是	否	是
Scheme	有	是	否	是
JavaScript	有	是	是	部分
Python	有	是	是	部分
Java	部分	部分	是	否
C++(20)	部分	部分	是	否
C（99）	否	部分	是	否
php	否(默认否)	否	是	否

实际上，我们也可以给可变数据用lambda建模，我们把赋值代码的前后视为两层不同的函数，用闭包来解决这个问题：

let a = 1;
a = a + 1
a;

(\lambda a.((\lambda a.a)\ (+\ a\ 1)))\ 1

考虑到任何循环都可以以递归形式写出，我们也可以用lambda来给纯过程式代码建模：

let s = 0;
let i = 0;
while(i <= 100) {
    i ++;
    s += i;
}
s;

(Y\ \lambda f.\lambda s. \lambda i. ((<=\ i\ 100)\ (f\ (+\ s\ i)\ (+\ i\ 1))\ s))\ 0\ 0

所有图灵机等价的模型都能互相转化，尽管lambda可以为过程式代码建模，但因为涉及语法结构上的变换（顺序书写变为嵌套结构），所以一般不认为变量、循环等结构属于函数式编程，即，过程式编程与函数式编程是互斥的。

既然我们可以把一段代码认为是lambda表达式，那么从数学的视角来看，代码执行的过程是什么呢？

很容易想到，代码执行过程可以视为不断对lambda进行 $\beta$ 归约。

church-rosser定理保证了以不同归约顺序，总能计算得到一致的结果，因此，如果一个程序能够得到运行结果，它必定是唯一的。

但一旦涉及停机问题，计算机语言跟lambda演算可能就不太一样了，计算机语言可能认为某些结构永远无法得到结果。请看以下例子：

function f(){
   f();
}
function g() {
   return 0;
}
g(f());

对于lambda演算来说，此式一定能归约到0，但对于JavaScript语言（和绝大多数其它编程语言）来说，它的结果必定是不停机。

从lambda演算的角度看，这些编程语言并不是随意对lambda参数进行 $\beta$ 归约，而是规定了归约的顺序，先从函数参数开始。这种行为在计算机语言领域中被称作传值调用（call-by-value）。

那么有没有 call-by-value 以外的参数传递方式呢？实际上还有很多，但是lambda演算模型最方便处理的两种方式就是 call-by-name 和 call-by-value。

接下来我们就来看看这两种调用方式有什么区别。

我们把JavaScript运算符也视为函数，我们会发现有些特殊的运算符行为有所不同。

function f(){
   console.log("f is called!");
}
false && f();

我们可以看到，尽管我们形式上调用了函数f，但因为&&的特殊性，实际代码并没有执行，这样的行为被称作函数的传名调用（call-by-name）。在古典时期，也有一些编程语言的默认函数调用行为就是传名调用。

从lambda的角度，这又涉及到了 $\beta$ 归约的顺序问题。

对于无副作用的函数式系统来说，传值调用还是传名调用仅仅影响计算的效率，并不影响最终的执行结果。但是传值调用还是传名调用可能影响停机问题。

对于一个有副作用的系统而言，传值调用还是传名调用则影响最终的执行结果，此时church-rosser定理不成立。