JavaScript与Lisp，通向编程圣殿[1]: "

JavaScript在设计时，注入了Scheme的血液，虽然设计者为了“商业”目的，为其披上了“Ｃ外衣”和“面向对象的礼帽”，但是其本质上应该是Lisp的，Lisp的思想，我们可以在JavaScript作出相同的模拟，你只需要使用“子集”，抛开伪装的“Ｃ外衣”和华而不实的“面向对象礼帽”。

历史和趋势让我逐渐相信，在早期，我们需要更优化更省资源的编程方式，能让机器运转的代码更有价值，随着计算机硬件的进化，“节省资源”“高并发”“分布式”都将不再是需要考虑的，智能化的程序将会成为主体。

许多年前，许多人都嘲笑JavaScript，至今仍然有，只是因为其简易低效的浮点数计算和单纯难以预测的类型系统，至今还有人在拿类型系统说事，你甚至看到TypeScript加入了类型系统。

呵呵～～～

同学，Lisp中是没有类型系统声明的，即便假设编译器有，但是编写过程是没有的，这就是JavaScript为什么没有。

JavaScript大众化的“Ｃ外衣”让他在浏览器获得了至高无上的地位，但是只有明智之士才明白：JavaScript之所以可以流行，是凭借内部轻量、逻辑有序的数据结构和计算方式，而这些都是Lisp的灵魂所在。

再过几年，或者10年，高并发分布式将不再是主题，因为实现他们都非常简单。智能化的程序，可分析的程序将会成为主题。即数学将会成为真正的程序。现在已经有了一些JavaScript的机器学习库，甚至神经网络库，虽然还没有广泛使用，但是硬件速度的提升早晚会使其大放异彩。

所以，从现在开始，掌握JavaScript的Lisp本质是非常重要的，这能让我们写出更加“智慧”的程序。

树的基本

让我们来点实际的东西，无论言语多么鲜华，没有干脆清晰的解决问题，都是空洞的。所以，让我们从Lisp的本质开始，也是Lisp的唯一：列表开始。

在其他的编程语言学科，更喜欢用“Tree树”这个字来形容，那么让我们来看一棵树：

        A
   /  /   \  \
  B   C    D   E
 /   / \
F   G   H

上边的这颗树，如何用程序来表示呢？
作为JavaScript，你可以用JSON来表示，用数组对象表示。

那么Lisp是怎么表示的？

(A (B F) (C G H) D E)

这就是Lisp的列表表示法，只有一个方式(元素 ...)，然后以此递归。
我们可以写出相同的JavaScript方式：

['A', ['B', 'F'], ['C', 'G', 'H'], 'D', 'E']

仔细查看，你很容易就能得出一个规律：
他们都是使用数组嵌套的，并且递归

从某些层面来讲，JavaScript的作者完全为这门语言融入了Lisp的列表，虽然没有提供方便的car cdr函数，但是如果想要模拟，是很方便的。

更复杂的一棵树

让我们再把树做的稍复杂一点，看看应该怎么用JavaScript表示：

        A
   /  /   \  \
  B   C    D   E
 /   / \    \
F   G   H    I
   /     \
  J       K

根据我们上面的推导，可以这样表示这棵树：

['A', ['B', 'F'], ['C', ['G', 'J'], ['H', 'K']], ['D', 'I'], 'E']

• 使用数组表示节点
• 一棵树本身就是一个特别大的节点，所以树即是节点，树即是数组
• 每一个主节点，是一个数组的第一项
• 每一个数组第一项后面的所有元素，都是该数组第一项的直接字节点

如果使用Lisp来表示，那么这棵树就是一个列表：

(A (B F) (C (G J) (H K)) (D I) E)

现在，你应该了解，表示一棵树，在JavaScript中是多么容易，多么的Lisp吧！

为树添加计算

让我们写个程序，来把我们刚才的树绘制一下，来表示一下JavaScript的Lisp血统。

比如，我们写个程序，输入

['A', ['B', 'F'], ['C', ['G', 'J'], ['H', 'K']], ['D', 'I'], 'E']

在控制台上打印出这样的树图形：

A
  B
    F
  C
    G
      J
    H
      K
  D
    I
  E

每当节点的深度增加一个时，打印的字符前面加2个空格，这个树图形字符串表示如下：

A\n  B\n    F\n  C\n    G\n      J\n    H\n      K\n  D\n    I\n  E\n

现在让我们来编写Lisp血统的JavaScript程序：

1. 一个计算空格的程序

   首先我们需要一个能计算空格的程序。当节点在０深度时，输出0个空格，第一个深度时，输出１个空格，第２个深度时，输出２个空格，这样我们才能有效打印

   A
     B
   ...
   

   这样的格式字符。

   function spaces(n) {
       return (function walk(i, spaces) {
           if (i <= 0) {
               return spaces;
           }
           return walk(i - 1, spaces + '  ');
       } (n, ''));
   }
   

   这是非常Lisp的程序，使用了递归的方式，来计算空格。
   当输入要求n的时候，这个程序递归计算，返回所有的空格。

   spaces(3) => '   ' 
   

2. 一个计算字符的程序

   所有的递归操作都可以用“左->右”来表示
   我们不停的计算“左”的值，然后将他们相加

   定义计算(节点):
   如果节点是一个字符：　返回字符
   如果节点是一个空结构：返回''
   其他，有效节点：　　　返回结果 = 计算(节点第一项) + 计算(节点后边的项)

   function string(list, deep, isCarList) { 
       // 如果节点是一个字符：返回字符
       if (typeof list === 'string') {
           return spaces(deep) + list + '\n';
       }
       // 如果节点是一个空节点：返回''
       if (list instanceof Array && list.length === 0) {
           return '';
       }
       // 其他，有效节点：返回结果 = 计算(节点第一项) + 计算(节点后边的项)
       var car = list.shift(),
           cdr = list;  
       return isCarList
              ? string(car, deep, false) + string(cdr, deep + 1, false)
              : car instanceof Array
                ? string(car, deep, true) + string(cdr, deep, false)
                : string(car, deep, false) + string(cdr, deep, false);
   }   
   

   这个程序定义为string(list, deep, isCarList)。

   list就是每一个节点的值，最开始是
   ['A', ['B', 'F'], ['C', ['G', 'J'], ['H', 'K']], ['D', 'I'], 'E']。

   我们取list最左边的项，即list[0]，为了与Lisp保持一致，我们采用了list.shift()，将第一项提取出来，剩下的list作为等待操作的新的list，然后对第一项和剩下的list进行递归求值。

   第一项有可能也是个数组。

   如果你仔细观察，你会发现这十分类似斐波那契数列，甚至就是斐波那契数列。

3. 打印

   现在可以打印我们的程序了：

   console.log(string(['A', ['B', 'F'], ['C', ['G', 'J'], ['H', 'K']], ['D', 'I'], 'E'], 0, true));
   

   打开nodejs控制台，输入程序，你将能看到：

   A
     B
       F
     C
       G
         J
       H
         K
     D
       I
     E   
   

   这个树型图。

改良版本的树形打印程序

最后，发上一个完整的改良版本：

function spaces(n, star) {
    if (typeof star !== 'string') {
        star = ' ';
    }
    return (function walk(i, spaces) {
        if (i <= 0) {
            return spaces;
        }
        return walk(i - 1, spaces + star + star);
    } (n, ''));
}

function string(list, star) { 
    return (function walk(list, deep, isCarList) {
        if (typeof list === 'string') {
            return spaces(deep, star) + list + '\n' ;
        }
        if (list instanceof Array && list.length === 0) {
            return '';
        }
        var car = list.shift(), cdr = list;  
        return isCarList
               ? walk(car, deep, false) + walk(cdr, deep + 1, false)
               : car instanceof Array
                 ? walk(car, deep, true) + walk(cdr, deep, false)
                 : walk(car, deep, false) + walk(cdr, deep, false);    
    }(list, 0, true));
}

console.log(string(['A', ['B', 'F'], ['C', ['G', 'J'], ['H', 'K']], ['D', 'I'], 'E'], '--'));

这个程序将会输出这样的一个树：

A
----B
--------F
----C
--------G
------------J
--------H
------------K
----D
--------I
----E

备注：为了解释简单，此文中的代码并未做深入的计算优化，特别是缓存，如果你想了解如何通过缓存记忆进一步提升计算效率，可以参看算法技巧: 如何使用JavaScript编写高效的fabonacci数列。