什么是Memoization
似乎我已经在很多书上看到函数的Memoization了，《JavaScript语言精粹》提到过，《SICP》也提到过。然而《JavaScript语言精粹》里面提到的那个memoization没什么意思，因为它那个函数并不通用，但是《SICP》提到的就不一样了，它几乎做到了通用性。
从维基上可以看到具体的定义，简单来说Memoization可以对重复并且计算量大的函数进行优化，并且该函数必须没有状态，也就是说无论调用该函数多少次函数值都一样。Memoization的做法就是将计算的值保存起来，并且在下次再调用同样参数时直接返回该值。
Scheme的Memoization实现
其实以前我就写过这样的文章，它是C语言实现，但是与《JavaScript语言精粹》一样做不到通用，只能针对一个参数而且类型为整型的，而且更加不通用的是写函数的人必须意识到Memoization的存在。Google的MapReduce就几乎不需要使用者意识到这个系统的存在，要是能做到MapReduce那样的通用性就好了，结果今天在《SICP》中看到下面这个Scheme语言实现的函数，当时就被震惊了，这个函数几乎实现了最大的通用性。
(define memo-fib
(memoize (lambda (n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (memo-fib (- n 1))
(memo-fib (- n 2))))))))
(define (memoize f)
(let ((table (make-table)))
(lambda (x)
(let ((previously-computed-result (lookup x table)))
(or previously-computed-result
(let ((result (f x)))
(insert! x result table)
result))))))
使用的示例函数同样是计算斐波那契数，因为这个函数是O(n2)复杂度的，比较能体现优化的性能。其中memoize函数做缓存工作，并在没有缓存时再调用函数并进行缓存，memoize做的就是提供一个键值的映射，在这里是一对一的映射，但如果稍微修改一下程序就能处理多对一的映射了，从例子中也可以看出用户在编写计算斐波那契的函数时根本不需要意识到memoize的存在！它的实现原理就是Scheme函数所支持的Lambda演算，也就是说所有的支持Lambda演算的语言都能做到这样的通用性，众所周知的JavaScript就支持，不过唯一可惜的就是Scheme语言并没有提供make-table这个基本函数，需要用户自己实现，但是如果能实现一个非常快速查找表，那么它也可以与MapReduce一样通用。
为什么要学习Lisp
从这个例子也可以看出能够将函数当成参数来传递可以提供非常强大的抽象能力，也是许多赞扬Lisp的人的原因之一——你的编程语言能做到这样的通用性吗？其他语言很少有支持在函数内定义函数并把函数当值传递的，比较大众的语言中只有JavaScript支持这样的功能，而JavaScript又被许多人给用烂了，讨论JavaScript的都是讨论如何做一些特效的，根本没有讨论如何编程更优美的人。在豆瓣的Lisp小组中也能看到很多人学习Lisp主要是为了学习思想。学习Lisp的确能够让你学到在其他语言中学不到的很多思想，特别是《SICP》这本书，才到书的一半就已经提到了很多编程的模式了，学Lisp也并不是说其他语言就是垃圾，而是因为学习其他语言的人很少讨论语言的优雅性。总的来说学习Lisp能够真正让你体会到编程的乐趣。