编程中的函数是干什么用的？

目的：在宿主语言（Host language）上运行目标语言（Target language）目标语言：此例为“函数式语言”。过于宽泛，因此我们暂且忽略有否元编程特性、类型系统、IO、异常处理、primitive operator等问题，只考虑一个核心特性的实现：一等函数（First-class function）宿主语言：可以是诸如JavaScript之类本身就有一等函数支持的语言，也可以是特定平台的机器码。最偷懒的做法就是做代码生成时直接用高级语言的一等函数来代表自己的一等函数，不过可能会受困于宿主语言缺乏尾递归等问题；改进的做法是先用高级语言实现目标语言，然后对实现进行几次变换，逐步去掉对高级特性的依赖（最后可以连高级语言自己的调用栈都不需要了），最终实现底层语言中跑函数式语言。实现方式：前面忽略了一大堆东西，但有一个没法忽略：规约策略。至少要区分你要做strict的语言还是non-strict的。non-strict函数式语言：这里就不考虑call by name了，默认是有sharing的call by need策略。简单的做法，graph rewriting，规约过程就是对AST进行重写，这个过程当中产生的一等函数，都是一棵子树，这棵子树称为一个thunk，代表一个也许已经规约到WHNF（Weak Head Normal Form）的表达式，同时可以有多个指针指向这个thunk。这个rewriting的过程是可以自动并行化的。更复杂一些的做法，就是编译到G-machine或者TIM（Three Instruction Machine）等抽象机器。non-strict这部分一本不错的参考是SPJ的《Implementing Functional Languages: A Tutorial》strict函数式语言：最简单的搞法是，首先用ML系的语言写一个基于环境的解释器（不介意的话可以看王垠博客那篇教写解释器的），然后一步一步地把解释器进行变换，首先对解释器做CPS变换，变换完了以后解释器就不再依赖Host language里的general recursion，只依赖tail recursion了；接下来再做defunctionalization，把CPS变换里的continuation用简单的数据类型表示，这样一来解释器就不再依赖Host language里的高阶函数了。现在，解释器已经低级到很容易重写到C甚至汇编的地步了。欲知详情可以看Andrew Appel的《Compiling with Continuations》。复杂的搞法，讲不完了。。加入类型：前面，我们的各种实现中，函数的参数都是某个可以代表基本类型数据或者又一个函数的东西，它们在内存中的表示都是（有gc兜着的）一些堆上的数据结构。当加入类型系统，可以去掉运行时的一些判断（比如指针指向的堆上对象不是个函数，却放在了函数应用式左边，报错）；留下来的指针标签，只用来区分ADT的constructor，用于模式匹配。更复杂的情况，比如依赖类型之类需要运行时存留一些类型信息的场合，不讲了。。新手常见误区：写解释器/编译器，一上手就考虑“环境”和“闭包”等概念（它们并非必需品），而不知悉一些更基础的概念，比如beta reduction。不看书的话至少把wikipedia过一遍，草稿纸上把常用的组合子都算一算，再想怎么实现的事。。题外话：这是我的最后一贴。在这里涨了姿势，认识了菊苣，我玩得很开心！