当设计一门语言时，函数部分设计五花八门，各种设计所对应的实现方式也各有千秋。

函数式编程

函数式编程 是一种编程范式(programming paradigm)，也就是如何写程序的方法论。它将计算机运算看作是数学中函数的计算，并且避免了状态以及变量的概念。在函数式编程语言中，函数跟其他数据类型一样，处于平等地位，可以赋值给其他变量，也可以作为参数，传入另一个函数，或者作为别的函数的返回值。且函数中没有副作用(函数内部与外部互动，如内部修改全局变量值)，因此函数只返回新的值，不修改系统变量。在输入参数相同的情况下，得到的结果总是相同的。

C语言中的函数

C语言中的函数并不是严格意义上的函数，它具有副作用。这种函数的实现方式十分简单，对于函数体部分，生成相关代码，保存在静态区域即可。对于函数调用部分，可以将参数压入栈，然后调用。

比如 printf(1, 2, 2); 可以翻译成如下代码：

push 2
push 2
push 1
call printf

高阶函数

我们把接受一个或多个函数作为参数，或者能返回函数的函数叫做高阶函数。在C语言中可以通过函数指针进行传递函数：

typedef void(*func)();
void test() {}
void call(func f) {
    f();
}

这样是将函数地址传递给调用函数，可以用汇编简要解释：

push offset _test
call _call

; in call
call [ebp-4]

嵌套函数

pascal 之类的语言就支持嵌套函数，所谓嵌套，就是可以在函数内部定义函数。C语言并不支持嵌套函数，我们假设其支持嵌套函数：

void global_func() {
    int a = 20;
    void nest_func() {
        a = 10;
    }
    void nest_func1() {
        int a = 40;
        void test() {
            nest_func();
            a = 30;
        }
        a == 40;
        test();
        a == 30;
    }
    nest_func();
    a == 10;
    a = 20;
    nest_func1();
    a == 10;
}
nest_func(); /* error */

可以看到的是，嵌套定义函数可以访问外部作用域，并产生副作用。不同作用域相互之间屏蔽。嵌套作用域给函数实现带来了不少麻烦，比如在查找变量所在作用域时，需要沿着栈帧回溯。如上诉例子，test 在查找变量 a 时，应该找到 nest_func1 中的变量 a ，而 test 中调用的 nest_func 所查找的 a 却应该是 global_func 中的 a。(这里假定使用的是 词法作用域， 而不是 动态作用域)这样就不能直接使用原有的向上回溯查找变量的方法，不过这有相应的解决办法。对于每个函数的帧，我们加入一个访问链指针，其指向当前调用栈中，该函数定义所在的外层函数最近一次调用的帧。比如对于上面的例子，在调用 nest_func1() 中的 test() 时，test 中的指针应当指向其直接上层 nest_func1 , 但是对于 test() 调用中的函数 nest_func ，其上层不应当是 test()。

top ->  nest_func()
        test()
        nest_func1()
        global_func()
bottom ->
简单的函数调用栈

这里 nest_func 访问链应当指向最上面的 global_func()。这样，函数在查找变量时，就可以通过访问链回溯而不是调用栈回溯。关于访问链的具体实现，可以参考龙紫书。还需要注意的是如果嵌套函数中有引用外层变量，那么是无法将内层函数当作返回值返回，所以这里需要引入闭包的概念。

柯里化函数

在闭包之前需要了解柯里化函数(Currying)，简单来说柯里化函数就是函数生成的函数，比如以下C++代码：

int func(int a, int b) {
    return a + b;
}
auto call = std::bind(func, 1, _1);
call(1);

在这里我们传递给函数 func 一个参数，然后生成一个保存了当前状态的函数，然后再后续补完全部参数时调用，这就是一个简单的柯里化函数应用。现在来考虑如何实现柯里化函数，柯里化函数需要保存当前已有的状态，那么我们对每一个函数包括普通函数定义一个 frame ，在每一次调用时，检测参数数目，如果满足所有参数都有对应的实参，那么就调用，否则生成一个新函数，将原有的 frame 拷贝一份，并加入新的参数。

if (args.size() == params.size())
    call function;
else 
    insert new function
    copy frame to new frame and insert params

闭包

闭包是指可以包含自由(未绑定到特定对象)变量的代码块，这些变量不是在这个代码块内或者任何全局上下文中定义的，而是在定义代码块的环境中定义。可以把闭包当作嵌套的高阶柯里化函数，嵌套对应着代码块或全局上下文，柯里化函数则是保存当前上下文状态，高阶使得函数可以通过参数或返回值进行传递。对于闭包有多种实现方式，这里紧紧讨论一种非常 native 的实现方式。首先需要对闭包中访问的自由变量进行捕获，然后隐式地作用参数传递给闭包体，生成新函数返回。这样变换以后，新生成的函数并不依赖于其父作用域，使得函数可以在任意地方调用。

(define (func x) 
    (lambda (a) （+ a x))
    
可以改为

(define (func x)
    ((define (nest_func x a)
        (+ a x)) x))