像Lisp一样写JavaScript--构建堆栈 - JAVA

老子有言：“道生一，一生二，二生三，三生万物！”说来惭愧，我始终未能领会其中奥义。直到最近学习lisp，虽只是略知其皮毛，却无意发现Lisp中竟能蕴藏了如此高深莫测的思想，惊喜和感慨之余，便在前写下了《java script实现Lisp列表(list)及操作》的笔记。但仔细想来这仅仅只是让java script具有像Lisp一样的能力，并没有像Lisp一样去使用这些能力，然而后者才是Lisp真正的奥义所在。

正如开头所阐释的那样，Lisp的奥义并非深不可测，而恰是简单到了极致。如果总结一下那就是：“道生原子，原子生列表，列表生万物！”。Lisp做到这些只用了三个操作cons、car、cdr。cons操作用两个值来构成一个cons对象，car和cdr则是能够访问cons对象的所有方法，Lisp做到这一切也正是cons的简单但是强大的数据描述能力。一个cons对象包含两个值，这个值可以是原子对象，也可以是cons对象本身，cons对象就像是一个可以分裂的细胞，细胞复生细胞，通过不同的组合构成了Lisp程序所需要的数据结构。下面的各种结构各异的结构仅仅是常用的一些数据结构：

图一

图二

图三

< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KCjxzdHJvbmc+08NMaXNwwdCx7cC0yrXP1rbR1buy2df3PC9zdHJvbmc+CjxwPjwvcD4KPHA+yrXP1sr9vt294bm5ttHVu8rHuPbLtcP3TGlzcLrDtKa1xLrcusPA/dfTo6wgttHVu7XEzNi148rHuvO9+M/Is/YobGFzdCBpbiBmaXJzdCBvdXQpICwgIM7Sw8e63Mjd0te3os/Wy/zKx9PJ1bu2pdSqy9i6zcqjz8K1xLK/t9bX6bPJo6zV4rrNwdCx7bXEzNi1476qyMu1xM/gJiMyMDI4NDujrMjnzbzSu9bQo6zSu7j2wdCx7dPQwb2yv7fW1+mzybfWsfDNqLn9Y2Fyus1jZHKjrMTHw7TO0sPHv8nS1NPDwdCx7daxvdPAtLHtyr620dW7o6xjYXKx7cq+1bu2pWNkcrHtyr7Ko9Pgsr+31qGjttTT2rbR1btwdXNostnX96Os1rvQ6NKqzai5/WNvbnPAtLS0vajSu7j20MLB0LHto6y8tChjb25zIG9iaiBzdGFjaykgt7W72NDCwdCx7aOs0ru49mNvbnMgz+C1sdPa0ru0znB1c2iy2df3oaPI5yhjb25zCiA0MiAoY29ucyA2OSAoY29ucyA2MTMgbmlsKSkpIM/gtbHT6yDBrND4sNE2MTOhojY5oaI0MiDRucjrv9W20dW7o6y5ubPJyOfNvLb+1tC1xMHQse2ho0xpc3C/ydLU08O66rrcyN3S17XEtqjS5bP21eLBvbj2stnX96O6PC9wPgo8cD48L3A+CjxwcmUgY2xhc3M9"brush:java;">(defmacro our-push (obj lst) `(setf ,lst (cons ,obj ,lst))) (defmacro our-pop (lst) `(let ((x (car ,lst))) (setf ,lst (cdr ,lst)) x))

用JavaScript实现堆栈

在java script去实现一个堆栈并无必要，因为Array已经包含了push,pop操做完全满足了需要。但是本着没有困难也要创造困难的精神，我们才有机会探索java script这么语言充满想象力的语言。在上一篇笔记《java script实现Lisp列表(list)及操作》介绍了java script中实现cons、car、cdr的操作，它们的实现实际上并未依赖任何java script提供的数据结构，而是是通过java script闭包的特性，把数据放在function对象中。因此可以说，java script中function可以用来表示列表。今天我们将故技重演，让它来为我们表示堆栈, Stack类的代码如下：

var Stack = (function() {
    function Stack() {
        this.stack;
    };

    Stack.cons = function(x, y) {
        return function(lambda) {
            return lambda(x, y);
        }
    }

    Stack.prototype.push = function(obj) {
        this.stack = Stack.cons(obj, this.stack);
        return this;
    }

    Stack.prototype.pop = function() {
        if (this.stack === undefined) {
            return undefined;
        }
        var top = this.stack(function(x, y) {
            return x;
        });
        this.stack = this.stack(function(x, y) {
            return y;
        });
        return top;
    }
    return Stack;
})();

代码解释：

如前所诉，我们仍然利用闭包，利用function对象来表示堆栈，函数Stack.cons用于返回一个新的堆栈。像在Lisp中的堆栈一样，堆栈就是栈顶和剩余部分的组合，所以堆栈push操作就是把新元素和旧堆栈组合返回一个新的堆栈

Stack.cons = function(x, y) {
        return function(lambda) {
            return lambda(x, y);
        }
    }
Stack.prototype.push = function(obj) {
        this.stack = Stack.cons(obj, this.stack);
        return this;
    }

我们大可以把Stack.cons函数看成Lisp中的cons，把它返回值function对象看成是lisp中的cons对象，首先它像(cons x y)一样包含了两个参数，其次是function本身可以当成参数作为Stack.cons的参数以构成更复杂的对象。

有了堆栈的创建方法，自然还要可以读取栈顶和剩下部分的方法，就像是有了cons操作还有对于的car和cdr一样。pop操作就提供了访问堆栈中的栈顶和剩余部分的方法，这里有有意思的是，堆栈被定义成是一个高阶函数，传递一个函数给它，堆栈就可以返回所包含的数据(x, y)，如果不这样做将很难取到它隐藏的秘密。

Stack.prototype.pop = function() {
        if (this.stack === undefined) {
            return undefined;
        }
        var top = this.stack(function(x, y) {
            return x;
        });
        this.stack = this.stack(function(x, y) {
            return y;
        });
        return top;
    }

总结：在使用java script实现列表操作和刚刚构造的堆栈的实现中，都是function来描述所需的数据结。这样的function有两个特点：闭包和高阶函数。闭包的作用是保存数据，而高阶函数的作用是为了访问数据。