KDF 的定义

实现 key stretching [^1] 的方法，具体就是从一个 master key，password 或者 passphrase 派生出一个或者多个密钥，派生的过程，使用PRF（Pseudo Random Function 伪随机函数）可以是某种哈希算法。

[Key stretching]
密钥延长算法（一种更慢的哈希算法），用于将初始密钥转换成增强密钥，在计算过程中刻意延长时间或者消耗空间，这样有利于保护弱密码。

两种密钥派生算法

PBKDF2 (CPU-Hard algorithm)

PBKDF2是基于密码派生出密钥的算法，需要消耗很多算力，为了是防止暴力破解加密。

Scrypt (Memory-Hard algorithm)

Scrypt 也是一种 password-base KDF 算法，比起 PBKDF2 需要消耗更多的资源，从而有效防止了专有硬件 ASIC/ FPGA 的暴力破解。Scrypt 内部用的还是 PBKDF2 算法，不过内部会长时间地维护一组比特数据，这些数据会在生成复杂的 salt 的过程中反复加密（Salsa20，一种流密码^3）得到。网上流行说，以太坊的PoW共识算法是利用Scrypt实现的，但事实上，以太坊自己实现了一套哈希算法，叫做Ethash^2.

区别

一言以蔽之，PBKDF2是算力型，而Scrypt是资源消耗型的。

Both PBKDF2 and scrypt are key derivation functions (KDFs) that implement key stretching by being deliberately slow to compute and, in particular, by having an adjustable parameter to control the slowness.
The difference is that scrypt is also designed to require a large (and adjustable) amount of memory to compute efficiently. The purpose of this is to make cracking it harder to parallelize using devices like GPGPUs or custom ASIC / FPGA hardware. Such devices may have hundreds or even thousands of parallel processing units, each capable of hashing a different password using traditional KDFs like PBKDF2, which don’t require much memory. However, it turns out that, at least using current technology, providing each of these parallel units with large amounts of memory space is a lot more difficult and expensive than making the units themselves.

密钥派生原理

PBKDF2 运行的原理

1
2
3

passphrase -> [dklen, salt, c] > 1000] -> hash

DK = PBKDF2(PRF, Password, Salt, c, dkLen)

其中：

1. PRF(Pseudorandom function)：伪随机数产生的密钥，如：hmac-sha256
2. dklen：派生所产生的密钥的长度
3. salt（盐值）：是一串随机生成的比特，加载密钥的固定位置做哈希后，可以防止彩虹表攻击导致的密码泄露
4. c：迭代的次数
5. DK：期望的密钥 derived key

例子：WPA2 (WiFi Protected Access)

1

DK = PBKDF2(HMAC−SHA1, passphrase, ssid, 4096, 256)

术语

Password
密码就是用于证明身份，获取和身份相称的访问权限。

Passphase
用于用户认证或者加密程序的操作步骤，特别是KDF算法就是从passphrase中派生出来的。

[^1]: Key stretching

关于组件聚合张力图的讨论

周三的午休时间，我在ThoughtWorks北京办公室分享了一场《架构整洁之道导读》。当谈到分享组件聚合原则的时候，很多同事表示难以理解。究其缘由，是我们无法将组件违反原则的后果对应到真实项目的问题上，这就导致原则和实践之间的不一致。讨论的过程异常激烈，但是很遗憾地最终并没有得到一个服众的结论。所以为了进一步澄清这些争议点，我决定专门组织一场针对组件聚合原则张力图的讨论会。在吴大师的鼓动下，时间定在下周四晚上的8点半，与会人员大多是咨询团队的技术教练，也有我们项目上的客户。

在这场长达两个半小时的讨论会上，没想到首先出现争议的点居然是组件的定义。

组件是软件部署的最小单元，是整个软件系统在部署过程中可以独立完成部署的最小实体。

对于这样的定义，大魔头提出了质疑：library（库）并不能独立部署。但凡出现明显的逻辑漏洞的时候，我们最好的方式是抛开译文回去看原文。

Components are the units of deployment. They are the smallest entities that can be deployed as part of a system.

阅读原文之后，我们发现“组件是软件部署的最小单元。”这句话翻译得并没有太大问题，但是第二句就有损原意了，原意是说可以作为系统的一部分被部署的最小实体，而没有强调部署过程这种动态的概念，否则就和前一句是同义反复。所以这个定义里面并没有说组件可以独立部署。后面提到组件可以被链接到一个独立可执行文件或者归档文件，又或者，可以被打包成.jar、.dll或者.exe文件，并以动态加载的插件形式实现独立部署。

解读组件的定义

来自原文：

Components can be linked together into a single executable. Or they can be aggregated together into a single archive, such as a .war file. Or they can be independently deployed as separate dynamically loaded plugins, such as.jar or .dll or .exe files.

来自讨论：

20:56:56 From tianjie : These dynamically linked files, which can be plugged together at runtime, are the software components of our architectures.

联系上下文理解之后，我们知道：组件可以被设计成独立部署的，但是并不是所有的组件都是可以独立部署的。这是要澄清的，不然讨论聚合原则的时候容易出现偏差。

吴大师接着解释说，组件应该是个逻辑单元，而不是物理单元。强制某个代码模块就是一个物理的部署单元是不合适的。另外，鲍勃大叔在介绍架构边界时，也表明了一样的观点：架构的边界并不是服务的边界。

解读REP原则

我按照自己的思路解释过REP、CCP和CRP原则[^1]之后，讨论的焦点很快聚集到REP原则的解读和实践意义上。

吴大师认为REP原则如果简单解读成没有发布过程就不能复用，它就和CCP、CRP原则的排斥力量不均衡，无法形成稳定的三角关系，那么这个张力图就显得有点鸡肋。

尚奇受到CAP（分布式系统基本原理，一致性，可用性和分区容错性）原则的启发提出了另一个解读方向。他说，CAP原则在分布式系统的实践里，都会先站住P原则，然后在C和A中权衡。那么在REP、CCP和CRP三角关系里，REP原则就相当于这里的P原则，必须先满足然后再去取舍CCP和CRP。

大魔头理解REP的意思是可复用性就是组件是独立可复用的。假如回到没有Maven这些工具，没有依赖管理的年代，如果我们所依赖的包还依赖其它第三方包，那么这个包就不能叫做独立可复用。

21:13:04 From YangYun : 我倒是理解REP的意思是你发布出来的一个可重用的包就是独立可重用的，你不能让我必须带着别的jar包才能用它。
21:14:04 From YangYun : The granule of reuse is the granule of release

他接着说，假如有两个提供同样功能的包，其中一个没有第三方的依赖，而另一个有，那我当然选择前者。

技术教练Sara举出了一个相对复杂但是很有启发性的例子。

21:46:35 From Qian Ping : 假设项目包含sub module ABC
 - 如果ABC单纯sub module没有打成jar，又互相直接复用了，就是违反了REP
 - 如果每个sub module，打成jar，互相复用的时候是通过对方特定版本的jar（如snapshot版本），就是符合REP
 - 如果符合REP了，而所有sub module是跟随整个项目一起升级版本，就是符合CCP因为他们是一体一起发布的
 - 这时假如A依赖B和C，我这次单纯想改C，他们一起升版本了。但其实B的Jar完全没有变化，这个对B来说就是一个不必要的发布，B又貌似应该分离出去，但如果它分离出去了，就又离REP和CCP远了

对于最后一句的表述，她澄清道：

之前有遇到一个情况，比如组件A，然后它里面需要用到一个common library, lib里面其实包含了比如3个sub module（1/2/3），全部都是A需要复用的, 这时候如果要改1/2/3里面任意的东西，都会一起升级lib，然后在A里面对应升级版本。

后来，有一些新组件B，它只需要用到common lib里面的3，不需要1/2，于是3一直被改和打包版本。 此时1/2会跟着升版本号，但其实1/2内容本身是完全没有变化的，只是版本号升了。

这个场景中引入了两个组件A和B分别依赖common library的某些模块。在我们讨论一个组件依赖时，面临的约束要简单很多，但是复用的初衷就是给多个组件去依赖，所以这个假设是很有价值。

Sara分析的思路如下：

如果分离出去，等于我有两个common lib（1/2 和 3）, 对于B来说，B只需要3这么一个lib是比较完美的，反正改了3再改B就好了。

但对于A来说，它就需要同时升级1/2的lib和3的lib，等于要3个发布，而它原来只需要2个发布（1/2/3 + A），所以离CRP远了，同时它也要分别维护两个lib分别的版本升级，所以CCP也比原来差了。

在她的分析下，我们发现CRP和CCP不单是互相排斥的，还有可能两者都无法满足。造成这种结果的原因在于1/2/3模块形成的这个common library对于A组件而言都符合CCP和CRP原则，但是对于B组件而言，是不满足REP和CRP原则的，因为每次想要依赖3模块，就得全部依赖1/2/3整个common library（复用困难）。反之，如果我们将3从1/2/3中拆出来成为独立的组件，那就几乎宣告对于A组件而言势必违反CCP和CRP原则，但是B组件却获得了符合REP和CRP原则的好处。

她接着补充道：

其实后来说起对应微服务的时候有另外一个想法，就是比如说我系统里面多个组件需要用计提（Mark to market[^2]）这么一个功能，说白了就是一条公式，那通常可以有几个做法

• 直接把这个公式复制到要用的组件，code level的复用，没有版本 -> REP bad, CCP bad, but CRP not bad (因为要更改时候发布次数还是一样的）
• 把公式写到一个common lib里面再进行复用 -> REP good, CCP good, CRP bad(多发布一次）
• 把公式放在一个独立service -> REP good, CCP bad(因为要维护多一个服务）, CRP good

这个观点就上升到不同层次的复用性上，可以算是对组件聚合原则的普适性的探索。

当话题再次被聚焦到复用性时，技术教练MoMo提出一个观点：我们现在讨论就是可复用组件应该遵循的原则，而REP是对复用粒度的定义。至于那些那些常年采用SNAPSHOT（Java项目里Maven常用的开发版本号），没有发布概念的组件，就不该纳入复用的考虑范围内，那些也就不是REP的反模式。

与此同时，阎王指出了一个翻译上的失误。组件粘合张力图中REP原则的简短描述是“为复用性而组合”，而原文其实是”Group for reusers”，翻译过来应该是为了复用者而组合，复用性的英文是 Reusability。所以为了复用者发布，考虑的就是对外部的承诺。

外部资料

大魔头在加班写方案和讨论的间隙，快速查阅了一些资料，比如wiki上对于REP原则的定义：

21:45:05 From YangYun : Reuse-release Equivalence Principle (REP)
REP essentially means that the package must be created with reusable classes – “Either all of the classes inside the package are reusable, or none of them are”. The classes must also be of the same family. Classes that are unrelated to the purpose of the package should not be included. A package constructed as a family of reusable classes tends to be most useful and reusable. - wiki百科里

在wiki的定义里，可以看到REP原则包含CRP和CCP原则的成分，如此看来，这三大原则并不符合MCME分类原则，就连鲍勃大叔在书中也是模棱两可的态度——REP维护共同的大主题，组件中的类和模块也必须紧密相关，这基本是CCP和CRP的简版描述。

然后大魔头查找到“粒度”这个词在软件设计中详细定义，这是对REP原则定义（软件复用的最小粒度等同于其发布的最小粒度）的分解和再认知。

21:57:03 From YangYun : http://condor.depaul.edu/dmumaugh/OOT/Design-Principles/granularity.pdf

21:58:29 From YangYun : https://fi.ort.edu.uy/innovaportal/file/2032/1/design_principles.pdf

这些观点和学术建议很有代表性，值得大家反复揣摩和思考。

反模式

软件工程师一般有个“正难则反”的习惯。原则较抽象，但是模式很具体，反模式更能指导实践。接下来，大家开始讨论哪些是违反了REP原则的反模式。

首当其冲的就是git submodule，在某些项目中，这种通过源代码划分模块并共享的方式还是挺常见的。因为共享的是代码，所以每次共享代码更新，势必要让依赖方重新编译，发布和部署。这种做法对于复用是痛苦的。

其次是常年使用SNAPSHOT版本的某些项目。这些项目的特点一般都是某个产品团队底下，内部团队之间有复用的要求。缺点其实也很明显，常年SNAPSHOT等于没有版本和发布的流程。使用者并不知道SNAPSHOT中哪些是稳定的，哪些是修改的，拿到的版本到底是最新的还是遗留的，我需要的功能在这个功能有包含，还是你包含了太多我不需要的升级。这种也是复用痛苦的。

REP原则小结

综合以上两个例子以及其它讨论，我们得出了一个好玩的结论：软件工程发展到现在，REP原则已经是基本的要求，它的存在有可能是鲍勃大叔年代感老了的体现。

[^1]: 架构整洁之道导读（二）组件聚合 
[^2]: Mark to market 按市值计价

[1] 架构整洁之道导读（一）编程范式
[2] 架构整洁之道导读（二）组件聚合
于 2018-11-12

组件聚合

组件的定义

组件是软件部署的最小单元，是整个软件系统在部署过程中可以独立完成部署的最小实体。比如，对于Java应用程序而言，Jar包就是组件；Ruby中的组件则是Gem文件；Python中的Egg或Wheel文件以及.Net下的DLL文件。

上回我们说到，编程范式的本质是约束。子过程、类或函数是我们编程过程中的基本元素，所以说编程范式是程序的基础构件。如果将这些基本构件比作建筑里的泥沙石，那么程序中的组件就可以类比成砖头。砖头的工艺注重材料配比，组件也是如此，恰如其分的基础构件配比是组件稳定的基础。组件的内容配比较难定量，但是在实践上，仍然受到指导原则的约束。

软件工程中的约束三角

在软件工程中，我们会看到很多约束条件都能由三角形的方式体现出来。这是因为三角形除了具有稳定的特性以外，还能体现出一种张力。

比如在敏捷项目管理中，我们常会听到时间，资源和成本的约束三角；在分布式计算中，著名的CAP（一致性，可用性和分区容错性）原理也是如此；还有区块链中的不可能三角（性能，安全和去中心化）。这些三角都在反映一种现实中的约束——因为不能全部同时满足，所以需要权衡。

组件聚合张力图

组件的内容配比，最终反映在组件的实践上就是基本构件的拆与合。鲍勃大叔给出了三个拆合的指导原则：REP（复用/发布等同原则），CCP（共同闭包原则）和CRP（共同复用原则）。

1. REP（复用/发布等同原则）：软件复用的最小粒度应该等同于其发布的最小粒度（注：只有那些通过版本追踪系统发布的组件才能被高效地复用）
2. CCP（共同闭包原则）：将同时修改，目的相同的类放到同一个组件；不会同时修改，目的不同的类放到不同的组件
3. CRP（共同复用原则）：不要强迫一个组件的用户依赖他们不需要的东西

这些原则乍看上去是全新的理念，细细品来又好像“新瓶装旧酒”的老把戏。CCP不就是SRP（单一职能原则）？CRP不就是ISP（接口隔离原则）？REP，等等，这个原则不言自明地像个公理呀！难怪有些架构师朋友说，鲍勃大叔老了，又拿着SOLID那一套概念出来忽悠骗钱。

其实，不妨换个思路想想，通常当谈论SOLID、高内聚低耦合、稳定依赖、稳定抽象系列原则的时候，我们是处于软件系统生命周期的哪一环？不出意外，大家都是从编写源代码，即开发（Development）的角度出发的。但是，我们又清晰地了解，软件系统的生命周期其实还包含除开发之外的部署、发布，运行和维护环节。那么问题来了，在这些环节里，哪些指导原则是适用的呢？

在跳脱了开发的思维桎梏之后，我们通过两种手段分析下这三条原则。

分开看

REP原则阐述了一个简单的道理：软件复用是基本要求。在追求软件复用的过程中，逐步形成了标准的发布流程，如：版本号（语义化版本），发布时间，变更内容等。这要求组件中所包含的模块和类都必须同时可发布，而可发布的深层含义既是对用户的承诺，也是对作者的约束。组件是否向后兼容？是否包含破坏性的变更？升级的注意事项？

CCP原则是指尽量把变更频率相同的模块和类放到同一个组件当中。这样做的好处是，当相关功能更新时，我们可以把源代码的变更局限在某一个组件当中，而不需要横跨多个组件，从而减少了部署，验证和发布的次数。概括来说，这是局部化影响的优势。CCP和OCP（开闭原则）中强调的“闭包”也有关联，所谓封装可变因素就是形成闭包的过程，CCP要求将同一时间变更的点聚合起来，达到闭包的效果。

CRP原则是说组件和组件之间的依赖应该达成一种默契——如果不需要完全使用某个组件中所有的模块和类，那么就不要依赖它。这看上去不太可能，但是有一点意义，它指导我们：不是紧密相连的模块和类不应该被放到同一个组件里。因为我们知道一旦某个组件变更升级之后，依赖它的组件往往也会被动的变更升级，即便是和自己那些无关的变更也是如此。而每次变更都意味着重新编译，部署验证和发布。

合起看

REP原则说明软件复用是基础，复用是通过发布流程规范的。在复用和发布的上下文中，CCP原则为了便于后期维护，需要尽可能地将变更频率相同的模块和类放到相同的复用单元——组件中；CRP原则为了避免频繁发布，应该将每个组件分割的足够小，减少无关变更导致依赖链条的连锁发布反应。

如果我们只兼顾REP和CCP原则，那么就可能由于连锁发布反应，出现很多不必要的发布；如果只兼顾REP和CRP原则，那么就可能因为实现一个功能需要横跨多个组件修改，造成过多的组件变更；如果只兼顾CCP和CRP，那我们可能就忘记了复用这档子事儿，这在先前我们批判鲍勃大叔的时候已经体现出来了。

小结

软件系统的生命周期里处处充斥着约束条件，每多一个环节往往就会多一种矛盾，进而衍生出多个方向的约束。组件聚合张力图反映的是发布和开发之间的矛盾，需要尽量遵循REP，CCP和CRP原则，满足其约束，才能减少变更成本。

组件构建过程中，除了聚合原则，还有耦合原则——描述的是组件的依赖关系。聚合原则告诉我们的是软件系统中的最小元素，耦合原则说的是元素之间的关系，当这两者和系统的功能结合到一起，就构成一个运行着的系统^1。系统是逐渐演化出来，即便我们熟知REP，CCP和CRP原则，也没有办法说，在系统构建之初，遵循这些原则就能画出完美的组件结构图。这便是“自顶而下”的设计不靠谱的基本解释。

“自顶而下”的设计不靠谱还有更深层次的原因。本书的第14章“组件耦合”会有答案，且听下回分解。

[1] 架构整洁之道导读（一）编程范式
[2] 架构整洁之道导读（二）续 组件聚合张力图
于2018-10-28

我是《架构整洁之道》(Clean Architecture) 中文版的技术审校者，在审校的过程当中略有感悟，所以希望通过撰写导读的方式分享给大家。

书名的由来

《架构整洁之道》是Clean Architecture的中文译名。看似简单地延续了《代码整洁之道》(Clean Code)的翻译传统，但事实上，对于取中文名字这件事，我们还是花了不少气力的。拿到译文初稿时，编辑提供了几个备选的译名：《架构简洁之道》，《架构至洁》和《Clean Architecture》，这些名字各有各的考量，在没有了解这本书的核心思想之前，我也没有办法给出恰当的判断。所以在通读了原作和译作之后，我在ThoughtWorks咨询群里发起提案，讨论的过程很精彩，最终在骨灰级架构师新哥的建议下，结果大致趋向了整洁架构。

新哥说：“整本书在说依赖治理（管理），也就是如果降低依赖复杂度，和DDD中分离子域分层架构等想法是一致的；如同你整理你的房间，把东西分门别类放好，从这个角度，整齐比简单更合适，或者清晰也可。”

除此之外，对于《架构至洁》这个候选项，大魔头的态度是不要至洁，总感觉脏脏的。言下之意，自行体会。而读MBA的岳岳和XR（XR说他没读过MBA）从用户思维出发，认为《代码整洁之道》和《架构整洁之道》可以相互增强记忆，更容易激发用户的购买行为。

即便敲定了“整洁架构”，大家对“之道”也有不同的看法。《代码整洁之道》对应的原标题和副标题分别是Clean Code - A handbook of Agile Software Craftsmanship，而《架构整洁之道》对应的原标题和副标题分别是Clean Architecture - A Craftsman’s Guide to Software Structure and Design。我们知道“道”是一种形而上的精神层面，老实讲，把Craftsman（手艺人）译做“道”是有点夸张的。

形而上是精神方面的宏观范畴，用抽象（理性）思维，形而上者道理，起于学，行于理，止于道，故有形而上者谓之道；形而下是物质方面的微观范畴，用具体（感性）思维，形而下者器物，起于教，行于法，止于术，故有形而下者谓之器。

道法术器择其一？其实凡事总有权衡，遵循前人的译法往往不会太坏。就像鲍勃大叔书中总结的稳定依赖原则，当我们依赖一种译法次数越多，它就更加稳定，这种稳定先不说能否形成品牌效应，单是SEO就能省去不少功夫，那么何乐而不为呢？

鲍勃大叔的文字平铺直叙、浅显易懂，尤其喜欢用他自己生活中的经验做例子。而且这本书是没有知识断层的，即便是初级程序员，也能在鲍勃大叔的循循善诱下，完成对软件架构认知的转变。因为他总是从最基础的知识点切入，自下而上，一步步地搭起架构的形状。

范式的实质是约束

编程范式是程序员喜闻乐见的话题，就像Vim和Emacs编辑器地位的旷日之争。它们的沉浮过往俨然就是风云诡谲的江湖。结构化编程英雄迟暮逐渐淡出程序员的视野，觊觎已久的面向对象编程（OOP）以迅雷之势称霸武林，独居一隅的函数式编程（FP）隐忍多年终于等来了一次机会。2012-2014年，江湖唱衰OOP的声音不绝于耳，FP就像一名拯救程序员于水火的侠士想要撼动这片天地。硝烟过后，眼前却不是你死我亡的惨状，而是你中有我、我中有你的大团圆结局。当Java这位OOP的保守党融汇了FP的特性lambda表达式，这场范式的冲突之争也算落下了帷幕。

程序员谈编程范式，喜欢党同伐异，作为FP的拥趸，我也不例外。可是鲍勃大叔却娓娓道来，所谓编程范式不过是约束程序的执行，告诉我们什么不能做而已。

1. 结构化编程是对程序控制权的直接转移的规范和限制
2. 面向对象编程是对程序控制权的间接转移的规范和限制
3. 函数式编程是对程序赋值操作的规范和限制

Goto considered harmful

学习C语言编程的第一天，老师就告诉我们不要在程序中使用goto语句，因为goto会破坏程序的结构化。Dijkstra在论文Go To Statement Considered Harmful中证明了goto语句阻止了将大程序递归分解成更小的可证明的单元，这意味着大量使用goto语句的程序是不能被证明的。这里，不能被证明的语义是不可判定，类似说谎者悖论——“我在说谎”这句话不能被证明和证伪，所以不用goto其实是在保证小的程序单元可判定。可惜的是，Dijkstra并没有证明程序单元，这项工作被科学方法——测试取代了。在保证程序单元可判定的前提下，测试是一种可以对其可证伪的科学方法。命题“天下乌鸦一般黑”就是可以证伪的，我们不可能枚举天下所有的乌鸦，等到哪天找到了一只白乌鸦，我们就可以说这个命题是错误的，这就是证伪。Dijkstra说的“测试只能说明bug存在，而不能证明不存在。”是同样的道理。

测试可以保证，在当前已知情况下，程序单元是正确的。一旦有新的测试用例导致程序单元出错，那么我们就可以修正程序，让程序更加接近真相。这或许就是TDD（测试驱动开发）的妙处所在吧。

去除了goto语句之后，我们发现具备顺序，循环和分支判断能力的计算过程还是图灵完备的，也就是说goto的有无并不会影响计算能力。那么goto的在程序中的作用便是弊大于利的。再加上goto的滥用会导致程序结构容易混乱，不利于程序员理解，这更得尽力避免。所以结构化编程限制了对程序直接转移的控制权。

Pointer considered harmful

人人都知道面向对象编程有三大特征：封装，继承和多态。

封装是为了构造抽象屏障（Abstract Barrier），到达隐藏信息的目的。任何编程范式都不会缺少封装，因为这是人的需求，是人类简化问题认知的方式。

继承是一种函数（过程或者API）复用的方式，以前我们想在多个结构相似的数据上使用同样的函数，需要通过强制转换到函数可接收的数据类型（结构体指针）上，这必然存在风险。面向对象的世界里，我们不再需要手动强制转换，只要通过显式地表明继承关系，编程语言就能在运行时自动做到这点。

多态（polymorphism）是一种将不同的特殊行为和单个泛化记号相关联的能力，和多态概念对应的参考实现——运行哪段代码的决策叫做分派，大部分分派基于类型，也可以基于方法参数的个数及其类型，而分派的具体执行过程则仰仗函数指针。当作为单个泛化记号的函数被声明出来，它的具体实现可以多样化。通过这样的记号，事实上，我们解耦声明和实现，而这种解耦的过程恰恰是通过函数指针间接地找到目标函数完成的。所以面向对象编程限制了对程序间接转移的控制权。

Mutability considered harmful

Neal Ford在《函数式编程思想》（Functional Thinking）中提到面向对象编程是通过封装可变因素控制复杂性（makes code understandable），而函数式编程是通过消除可变因素控制复杂性的。函数式的一个显著的特点就是不可变性。不可变性意味着更多的内存消耗，更差的性能？其实不尽然。像Scala，Clojure这些基于JVM上的函数式编程语言大量使用了持久化结构（如：Persistent Vector，见脚注1)，在不损失效率的前提下，实现了不可变的数据结构。这样的数据结构在高并发的环境下具有非常巨大的优势，尤其相对于面向对象编程中为人所诟病的临界区和竞态条件。

不可变的数据结构是无法重复赋值的，所以函数式编程限制了对程序的赋值操作。

小结

鲍勃大叔一针见血地指出，我们过去50年学到的东西主要是——什么不应该做。这等于给全书奠定了基调。可以类比，良好的架构也在传达同样的道理。

为什么从编程范式开始谈起？在审阅完整本书之后，我慢慢发现鲍勃大叔其实在传递一种设计理念：架构设计里，自顶向下的设计往往是不靠谱的。就像本书的目录，从程序的基础构件，谈到组件，最后谈到架构，这个过程非常符合系统自组织的特征。

为什么自顶向下的设计往往不靠谱？本书的第4部分“组件构建原则”会有答案，有需要，且听下回分解。

[1] 函数式编程简介
于 2018-10-21

起源

泛型编程是一种编程风格，其中算法以尽可能抽象的方式编写，而不依赖于将在其上执行这些算法的数据形式。

泛型这个词并不是通用的，在不同的语言实现中，具有不同的命名。在Java/Kotlin/C#中称为泛型（Generics），在ML/Scala/Haskell中称为Parametric Polymorphism，而在C++中被叫做模板（Template），比如最负盛名的C++中的STL。任何编程方法的发展一定是有其目的，泛型也不例外。泛型的主要目的是加强类型安全和减少强制转换的次数。

Java中的泛型编程

在Java中有泛型类和泛型方法之分，这些都是表现形式的改变，实质还是将算法尽可能地抽象化，不依赖具体的类型。

generics add a way to specify concrete types to general purposes classes and methods that operated on Object before

通用的类和方法，具有代表性的就是集合类。在Java1.5之前，Java中的泛型都是通过单根继承的方式实现的。比如：

1
2
3
4
5
6
7

public class ArrayList // before  Java SE 5.0
{
    public Object get(int i)
    public void add(Object o)
    public boolean contains(Object o);
    private Object[] elementData;
}

虽然算法足够通用了，但是这样会带来两个问题。一个是类型不安全，还有一个是每次使用时都得强制转化。减少类型转换次数比较容易理解，在没有泛型（参数化类型）的时候，装进容器的数据，其类型信息丢失了，所以取出来的时候需要进行类型转换。
例如：

1
2
3
4
5

List list = new ArrayList();
list.add(1);

assertThat(list.get(0), instanceOf(Integer.TYPE));
assertThat((Integer)list.get(0), is(1)); //存在强制转换

因为这个类里只有Object的声明，所以任意类型的对象都可以加入到这个集合当中，在使用过程中就会存在强制到具体的类型失败的问题，这将丧失编译器检查的好处。

1
2
3
4
5
6

List list = new ArrayList();
list.add(1);
list.add("any type");

assertThat(list.get(1), instanceOf(String.class));
assertThat((Integer) list.get(1), is(1));//-> java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer

2005 Java SE 5引入了泛型，不仅有效地提高了算法的通用程度，同时也保留强类型语言在编译期检查的好处。

Generics This long-awaited enhancement to the type system allows a type or method to operate on objects of various types while providing compile-time type safety. It adds compile-time type safety to the Collections Framework and eliminates the drudgery of casting.

所以上述的程序会写成这样：

1
2
3
4
5

List<Integer> list = new ArrayList<Integer>();
list.add(1);
// list.add("no way"); 编译出错
assertThat(list.get(0), instanceOf(Integer.TYPE));
assertThat(list.get(0), is(1)); // 不需要强制转换

类型安全

在静态强类型语言中，编译期间的检查非常重要，因为它可以有效地避免低级错误。这些低级错误就是类型安全解决的问题。类型安全包含了赋值安全和调用安全。其底层实质上就是在某块内存中，始终存在被同种类型的指针指向。

1. 类型赋值检查

   1 2	long l_num = 1L; int i_num = l_num; // 编译错误

   在强类型的语言当中，类型不一致是无法互相赋值的。

2. 类型调用检查
Clojure就是一门强类型语言，而且还是一门函数式语言，所以重新赋值不被允许，它的类型安全表现在针对类型的调用安全。

1
2
3

user=> (+ "" 1)
...
java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Number

这里存在一个隐式类型转化的过程，但是由于String无法转化成Number，所以方法调用失败。由于Clojure是动态语言，所以只有在运行时才会抛出错误。

另一个简单的例子，如果一个类型不存在某个方法，那就没法去调用它。在动态强类型语言中，运行时一定会报错。其实质是类型是内存堆上的一块区域，如果该区域之上没有想要调用的方法，那么调用在编译期或者运行期间一定会出错。

1

new Object().sayNothing() // 编译出错

为什么说类型安全对于开发人员友好，这个特性对于编程语言很重要？其实这可以追溯到三次编程范式解决的根本问题上。Clean Architecture（架构整洁之道）一书中，对结构化，面向对象和函数式编程语言做了很透彻的分析。

首先我们得明确一点，这些范式从来没有扩展编程语言的能力，而是在不同方面对编程语言的能力进行了约束。

1. 结构化编程
   对程序的直接控制进行约束和规范，goto considered harmful.
2. 面向对象编程
   对程序的间接控制进行约束和规范，pointer considered harmful.
3. 函数式编程
   对程序的赋值进行约束和规范，mutability considered harmful.

按照这样的思路，泛型编程无非是对既有的范式做了进一步的约束。泛型编程旨在对程序的间接控制进一步进行约束和规范。它把类型安全放在第一位，而将类型转化限制在编译期间。

我们甚至可以遵循前面的定义方式，说：
2.1 泛型编程
对程序的间接控制进一步进行约束和规范，type casting considered harmful.

Kotlin中的泛型编程

和Java泛型中的泛型方法和泛型类概念类似，Kotlin将对应的概念称为参数化函数和参数化类型。

parameterized function 参数化函数

假设我们要返回三个对象中任一一个对象，同时保证类型一致。参数化函数是很恰当的选择。

1

fun <T> random(one: T, two: T, three: T): T

parameterized type 参数化类型

除了参数化函数，类型本身也可以定义自己的参数化类型。比如：

1

class Dictionary<K, V>

bounded polymorphism 限定参数化类型

大部分情况下，参数化类型不会是无限抽象的，无限抽象往往不利于语言的表达性。所以限定的参数化类型应运而生。

1
2
3
4

fun <T : Comparable<T>> min(first: T, second: T): T {
    val k = first.compareTo(second)
    return if (k <= 0) first else second
}

如果需要用多个边界来限定类型，则需要用到where语句，表达T被多个边界类或者接口限制。

1

class MultipleBoundedClass<T> where T : Comparable<T>, T : Serializable

invariance 不变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

open class Animal
class Dog : Animal()
class Cat : Animal()
class Box<T>(val elements: MutableList<T>) {
    fun add(t: T) = elements.add(t)
    fun last(): T = elements.last()
}

fun foo(box: Box<Animal>){
}

val box = Box(mutableListOf(Dog()))
// -> val box: Box<Dog> = Box(mutableListOf(Dog()))
box.add(Dog()) // ok
box.add(Cat()) // 编译错误

这里出现的编译错误，原因是box的真实类型是Box<Dog>，所以尝试向Box<Dog>中添加Cat对象是不会成功的。这样总能保证类型安全。

Dog是Animal的子类型，那么编译器是否承认Box<Dog>是Box<Animal>的子类型，在使用时进行隐式转换呢？

1

val box: Box<Animal> = Box(mutableListOf(Dog())) // type inference failed. Expected type mismatch.

编译器是不会允许这样行为发生。原因就是这样做会导致类型不安全。
我们试想一下，假如这种转换是允许的，那么我们就可以继续添加其它继承了Animal的子类对象，比如：

1
2

val box: Box<Animal> = Box(mutableListOf(Dog())
box.add(Cat())

这样就导致Box<Animal>里面同时保存了Dog和Cat的对象，正如前面提到的，在运行时，调用可能就会抛出ClassCastException，所以这是非类型安全的。

1
2
3

val box = Box(mutableListOf(Dog()))
// val box: Box<Dog> = Box(mutableListOf(Dog()))
val animalBox: Box<Animal> = box // 编译错误

covariance 协变

但是这种限制太过于严苛了，如果我们只需要从这个box读取元素，而不需要往里面添加，那么这种转换就是类型安全的。具体原因稍后再说。

当Dog是Animal的子类型，那么Box<Dog>也是Box<Animal>的子类型，这种继承关系就是协变。在Kotlin中，我们需要使用out关键字表示这种关系。

1
2
3
4

class CovarianceBox<out T : Animal>(val elements: MutableList<out T>) {
    fun add(t: T) = elements.add(t) //编译错误
    fun last(): T = elements.last()
}

基于这种协变关系，我们可以这样调用

1
2
3

val dogs: CovarianceBox<Dog> = CovarianceBox(mutableListOf(Dog(), Dog()))
val animals: CovarianceBox<Animal> = dogs
print(animals.last())

我们注意上面的CovarianceBox的add方法出现了编译错误，原因就是在协变关系中，泛型参数只能作为输出参数，而不能作为输入参数。因为在拒绝了输入泛型参数的前提下，协变发生的时候，才不会出现强制转化的错误。举个例子：

1
2
3

val dogs: CovarianceBox<Dog> = CovarianceBox(mutableListOf(Dog(), Dog()))
val animals: CovarianceBox<Animal> = dogs
dogs.add(Cat()) // add在这里禁止了

如果CovarianceBox允许add方法，那么box里面就会同时存在多个子类型的实例，这样就会导致类型不安全，所以out修饰的参数化类型，只能在函数的返回值上出现。

不过，这种解决方式也不是万能的，属于杀敌一千，自损八百的战术。因为对于Collection而言，不可能做到任何泛型参数都不会出现在入参的位置上。

1
2
3
4

public interface Collection<out E> : Iterable<E> {
    public operator fun contains(element: @UnsafeVariance E): Boolean
    public fun containsAll(elements: Collection<@UnsafeVariance E>): Boolean
}

所以，针对这种情况，我们知道某些方法其实并不会有添加的操作，可以在入参的位置上加上@UnsafeVariance，以此消除掉编译器的错误。

contravariance 逆变

当Dog是Animal的子类型，那么Box<Animal>也是Box<Dog>的子类型，这种继承关系就是逆变。在Kotlin中，我们需要使用in关键字表示这种关系。

1
2
3
4

class ContravarianceBox<in T>(val elements: MutableList<in T>) {
    fun add(t: T) = elements.add(t)
    fun first(): T = elements.first() // 编译错误
}

基于这种逆变关系，我们可以这样调用

1
2
3

val animals = ContravarianceBox(mutableListOf(Animal()))
val dogs: ContravarianceBox<Dog> = animals
dogs.add(Dog())

这个时候，类型始终是安全的。但是我们也注意到ContravarianceBox的first方法出现了编译错误，原因就是在逆变关系中，泛型参数只能作为输入参数，而不能作为输出参数。在拒绝了输出参数的前提下，逆变发生的时候，才不会出现强制转换的错误。

1
2
3
4

val animals = ContravarianceBox(mutableListOf(Animal()))
val dogs: ContravarianceBox<Dog> = animals
dogs.add(Dog())
val dog: Dog = dogs.first() // 编译错误

reification 变现

1

reify is To convert mentally into a thing; to materialize.

Kotlin中的Reification的实现使用的是inline模式，就是在编译期间将类型进行原地替换。

1
2
3
4

// 定义
inline fun <reified T : Any> loggerFor(): Logger = LoggerFactory.getLogger(T::class.java)
// 使用
private val logger = loggerFor<AgreementFactory>()

因此，所以原来调用处的代码会在编译期间展开成如下：

1

private val logger = LoggerFactory.getLogger(AgreementFactory::class.java)

使用reification操作，可以精简掉很多模板代码。

type projection 类型投影

上述过程中，我们看到协变和逆变都是针对可以编辑的类。但是如果遇到已经存在的类，这件事就得运用类型投影技术。拿Class这个类举例：

1
2

val dog = Dog::class.java
val animal: Class<Animal> = dog //编译不通过

Kotlin中的type projection就是为了解决这个问题的。

1
2

val dog = Dog::class.java
val animal: Class<out Animal> = dog

同理，

1
2

val animal = Animal::class.java
val dog: Class<in Dog> = animal

我们来看一个真实的场景

1
2
3
4
5
6
7

val agreementClass: Class<RentalAgreement> = RentalAgreement::class.java

private val virtualTable = mapOf(RentalPayload.type to RentalAgreement::class.java)
private fun dispatch(type: String): Class<out Agreement<Payload>> {
    return virtualTable[type]
            ?: throw RuntimeException("No suitable Agreement of this type found, please check your type: $type")
}

只有这样，我们才能将具体的Class<RentalAgreement>投射到Class<out Agreement<Payload>>父类型之上，后续通过某种方式，实例化出RentalAgreement的实例，其继承自Agreement<Payload>。

泛型编程的思考

Bob 大叔的 Clean Code 一书的第六章《对象和数据结构》中提到了一个很有意思的现象：数据、对象的反对称性。在这里，数据结构暴露数据，没有提供有意义的函数；对象把数据隐藏起来，暴露操作数据的函数。

过程式代码会基于数据结构进行操作。例如：首先会定义好数据结构Square, Circle和Triangle，然后统一在area(shape: Any)的函数中求shape数据的面积，如：

1
2
3
4
5
6

fun area(shape: Any): Double {
    return when(shape) {
      is Square -> return shape.side * shape.side
      else -> 0.0
    }
}

而面向对象拥趸一定会嗤之以鼻——显然应该抽象出一个shape类包含area方法，让其它的形状类继承。如：

1
2
3
4
5
6
7
8
9

interface Shape {
    fun area(): Double
}

class Square(val side: Double) : Shape {
    override fun area(): Double {
        return side * side
    }
}

在添加新的形状的要求下，面向对象的代码是优于过程式的，因为面向对象对类型的扩展开放了。而过程式代码却不得不修改原来area方法的实现。

但是，如果此时需要添加一个求周长primeter的函数。相对于面向对象代码，过程式代码由于无需修改原来的实现，反而更加容易扩展。反观面向对象的代码，在接口Shape中添加一个primeter会导致所有的子类都得发生修改。

这就是数据和类型的反对称性。在变化方向不同的时候，它们面临的阻力也是不一样的。

我们既想要过程式对方法扩展的优点，又执着面向对象自然的类型扩展的好处，该怎么办呢？可以考虑结合起来使用。

这样的结合不是说原有的双向阻力消失了，而是在不同的层次上应用各自的优点。也就是说，Shape需要求面积、周长，同时也要支持类型扩展，这种要求之下，基本不可能调解出一种符合开闭原则的方案。不过，如果对于所有Shape类，都需要统一进行某些操作，例如：集合的排序，过滤等等。那么合并两者的好处就变得可行了。

基于最先分析的通过继承的方式进行泛型编程的缺点：

1. 太多强制转换
2. 非类型安全。
   恰当地引入了泛型T，以期编译期的占位和运行时的替换。

不过没有限定的泛型大部分情况下是没有用处的，因为无限的抽象没有意义，所以需要更加精准的泛型限定。

在我们做完这一切以后，会惊喜地发现依赖倒置（DIP）原则贯穿始终。不论是继承体系，还是改善之后的泛型继承体系。它们秉持的原则就是在编译期，始终朝着稳定、抽象的方向移动，而且不断在易变、具体的方向延迟决策，直到运行时方能确定。

书籍推荐

脑图

参考链接
泛型 一个会写诗的程序员

说服自己

学习新的编程语言的最终目的是解决实际问题。掌握编程语言的过程，在某种程度上近似学习一种新的工程实践。不仅解决问题固然可乐，学习的过程也同样充满了新鲜感，不过需要谨防的是新鲜感带来的胜任力错觉。

胜任力错觉指的是反复接触新东西，发现不用花费什么气力就理解了其中所有的内容。说的简单点，就是自以为是。这种胜任力错觉导致最常见的后果是以为掌握了某种技能，真正开始解决问题时，要么是半天摸不着头绪，要么就是处处掣肘。所以我始终相信，阅读是一码事，理解是一码事，掌握还是另一码事，所谓一码归一码，大抵就是这么回事。

以终为始，方得始终。老子（真·老子，非我）也说，慎终如始，则无败事。这里的“终”就是目标，在软件工程中，有一种实践很好得反映了这种做事方式——测试驱动开发。借我司的一位牛人的原话：看一个人会不会测试驱动开发，不是看他的测试写得好不好，而是要看他是不是始终从测试出发去解决问题。脑子里条件反射的就是测试该怎么测？这种才是测试驱动开发的实质。

学习，说白了就是一个不会到会的过程，这里头最难的是学会了什么？在学习方法上，我们很多时候喜欢遵循前人的套路，美其名曰知识体系化。我承认体系是前人经验和群体智慧的积累，但是学习体系不代表你具备形成体系的能力，就像你学习了著名开发框架（Spring or Rails）也不会说你能开发这套框架一样。学习的关键还是发散、收敛和再发散、再收敛的渐进过程，感性的定性分析到理性的定量分析，在不断丰富和修正认知，处处用实践检验认知。这种过程坚持下来，得到就不单单是知识，可能是元知识（方法论）或者智慧。

看书抄代码是个学习的好方法，不过书中的例子一般都被加工（简化）过，我们很容易陷入套路中，谨记胜任力陷阱。比较推荐的方式，自己认准一段有用的程序，反复练习（也可以每次增加些体系化的功能）直到娴熟。在接触新语言时，不去看一套完整的语言体系，而是事先把这段程序可能用到的基本类型、数据结构、流程控制结构、模块化和功能组件列出来，然后去找它们在这门语言中对应的实现。

有目的地试错

我常用的练手程序叫tree，功能是list contents of directories in a tree-like format. 这个程序需要用到的基本构件有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

基本类型（basic type)
1. str
 
数据结构（data structure）
1. list
2. map

流程控制结构（control flow structure）
1. if, else
2. recursion

模块化（modulize）
1. function
2. module/namspace/package

功能组件（function components）
1. IO
2. File
3. Path

分类清晰之后，对应找起来很方便，有的基本不用找，经验足矣。现在的编程语言基本都有repl，多尝试几遍就有了感性认识。我说的很轻松，但是如果不去尝试，一样会难住。Elixir中有iex命令作为repl，而且这门语言深受Clojure的影响，尤其是文档和例子方面很充足，对于初学者再友好不过。

换种思维

在编写tree的过程中，我会时不时停下来思考Elixir在某个功能点上应该怎么用才好？因为历史上，把Java的代码写成C风格的人不在少数，这足以让人警惕。再说，学会用新语言的思维方式编程是我初始的目的之一。

这里举个例子，map的key使用哪种基本类型会比较合适？Clojure中有keyword，如{:name "clojure"}，而Python中并没有这样的数据类型，我只好使用{'name': "python"}，那么Elixir呢？它推荐的是atom/symbol，%{:name => "elixir"} #or %{name: "elixir"}

遇到需要join path的时候，凭借原来的经验，我会去寻找Path模块。具体可以去问谷歌，也可以问repl

1
2
3
4

iex<1> h Path.join
or
iex<1> Path.join <TAB> #用tab键
join/1    join/2

看到join/1 join/2的时候，我有些许迷茫，但是很快就变成了欣喜。我们知道，在动态类型语言中，arity指的是方法参数的个数，这里的1和2其实表明的就是join有两个重载的方法，分别接受一个参数和两个参数。更进一步，arity是方法（函数）实现静态多态的依据之一。再进一步，多态是函数的特性，而非OO中固化下来的概念——类的特性。

组织代码

上面的验证只需要repl就足够了。但是，真正编写还是得有组织和结构。软件工程中，控制复杂度（复杂度从来不会被消除）的基本法则就是模块化。这就引出了module和function，还有对模块可见性（private, public etc.）的修饰。

1
2
3
4
5

defmodule Tree do
  defp tree_format(parent_dir, dir_name) do
    %{:name => dir_name, :children => []}
  end
end

defp定义了一个私有的方法tree_format，它是用来格式化目录的。目录结构是树形结构，所以很容易递归实现。

1
2
3
4
5
6
7
8
9
10
11

defp children(path) do
  if (path |> File.dir?) do
    File.ls!(path) |> Enum.map(fn f -> tree_format(path, f) end)
  else
    []
  end
end

defp tree_format(parent_dir \\ ".", dir_name) do
  %{:name => dir_name, :children => Path.join(parent_dir, dir_name) |> children}
end

在利用递归的过程中，我使用File.ls!（查文档，注意!号）列出子目录，然后递归地格式化。这些都比较好理解，不过这里其实出现了两个新的玩意（当然也不是一蹴而就的，认识之后才重构成这样）。一个是\\ "."，还有一个是|>。第一个比较容易猜，叫做默认参数（default arguments）；第二个有Clojure基础的也手到擒来，叫做管道操作符（pipe operator），用来将左边表达式的结果传入右边方法的首个参数。这里就是children(path)的path.

结构，解构

完成目录结构的格式化，接下来需要做的是渲染这组树状的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13

defp decorate(is_last?, [parent | children]) do
  prefix_first = (if (is_last?), do: "└── ", else: "├── ")
  prefix_rest = (if (is_last?), do: "    ", else: "│   ")
  [prefix_first <> parent | children |> Enum.map(fn child -> prefix_rest <> child end)]
end

defp render_tree(%{name: dir_name, children: children}) do
  [dir_name 
   | children 
   |> Enum.with_index(1)
   |> Enum.map(fn {child, index} -> decorate(length(children) == index, render_tree(child)) end) 
   |> Enum.flat_map(fn x -> x end)]
end

到这里，我学到的是参数解构（arguments destructing），map-indexed的新实现，字符串的拼接（string concatenation）还有列表元素的前置操作。

Elixir和所有函数式编程语言一样，具备强大的模式匹配（Pattern matching）的功能，参数解构其实就是其中的一个应用场景。

1
2
3
4
5
6

%{name: dir_name, children: children}
matching
%{:name => ".", :children => ["tree.exs"]}
# ->
dir_name == "."
children == ["tree.exs"]

渲染的过程也是递归的。最终返回的是一个加上分支标识前缀的列表

1

[dir_name | children]

这是一种将dir_name前置到children列表头部，形成新列表的做法。和Clojure（绝大数Lisp）中的(cons dir_name children)类似。

操作符|除了可以前置列表元素，递归解构也是一把好手。

1
2
3

defp decorate(is_last?, [parent | children]) do
  ...
end

参数列表中的[parent | children]，解构出了列表的head和rest，这对于递归简直就是福音。

在添加前缀的步骤[prefix_first <> parent...]中，经验里字符串的拼接常用符号+不起作用了，换成了<>，这个是靠试错得出来的。

除了说到的这部分内容，我还运用了Enum.map, Enum.with_index, Enum.flat_map等函数式语言的标配。这些零散的知识点，可以添加到基本构件中，以便持续改进。

入口

程序要执行，就需要一个入口。每次我都会猜猜argv会在哪里出现呢？是sys(Python)，os(Go)，还是process(Node.js)，这回又猜错了，Elixir管这个叫做System.

1
2
3
4
5
6
7

  def main([dir | _]) do
    dir |> tree_format |> render_tree |> Enum.join("\n") |> IO.puts
  end
# ---
Tree.main(System.argv)
# ---
$ elixir tree.exs .

重构

这里重构的目的是让程序更加贴近Elixir的表达习惯，那么哪里不是很符合Elixir风格呢？我注意到了if...else，可以考虑模式匹配实现多态。

1
2
3
4
5
6
7

defp children(path) do
  if (path |> File.dir?) do
    File.ls!(path) |> Enum.map(fn f -> tree_format(path, f) end)
  else
    []
  end
end

File.ls!中的!表示如果指定目录有问题，函数会抛出error或者异常。然而，Elixir还给出了一个File.ls方法，即便出错，也不会有抛出的动作，而是返回{:error, ...}的元组，至于正常结果，则是{:ok, ...}. 这恰恰可以使用模式匹配做动态分派了。

1
2
3
4
5
6
7
8
9
10
11

defp children(parent) do
  children(parent |> File.ls, parent)
end

defp children({:error, _}, parent) do
  []
end

defp children({:ok, sub_dir}, parent) do
    sub_dir |> Enum.map(fn child -> tree_format(parent, child) end)
end

一旦 children(parent |> File.ls, parent)中的parent不是目录，File.ls返回的就会是{:error, ...}元组，它会被分派到对应的方法上，这里直接返回一个空的列表。反之，我们就可以拿到解构之后的子目录sub_dir进行交互递归，实现全部子目录的格式化。

小结

在学习Elixir的过程中我收获了很多乐趣，不过，这离掌握Elixir还有很远的距离。我曾经看过一部科幻电影“降临”，剧情受到了萨丕尔-沃夫假说（语言相对性原理）的影响，这个假说提到：人类的思考模式受到其使用语言的影响，因而对同一事物时可能会有不同的看法。既然如此，那么自然语言也好，编程语言也罢，如果能换种思维方式解决同一种问题，说不定能收获些奇奇怪怪的东西，编程之路，道阻且长，开心就好。 – 2018-06-08

如何高效地学习编程语言
怎样才算学会Python
Elixir
萨丕尔-沃夫假说

Python 实践基础

起源

假如你已经有了编程基础，那么学习一门新语言的困难点绝对不在语法、语义和风格等代码层面上的，而在于语言范式（OO，FP还是Logic），语言的生态（如：依赖管理和包发布等）和工具（编辑器，编译器或者解释器）这些方面，请参看如何高效地学习编程语言。再假如你已经对各类语言范式都有一定的了解，那么最后的困难之处就是…细节，它是魔鬼。

我相信真正拥抱一门新语言，花在工具和语言生态上的时间一定很多。庞大的社区利用群体智慧构筑的生态圈充满了各种零碎的知识点，这些知识点可能是前人趟过的陷阱（Common Gotchas），基于局部共识经由经典项目实践过之后的约定（Convention）和惯用法（Idioms），也可能是总结出的概念模式（Pattern），甚至是审美（Aesthetic）和禅（Zen）或道（Dao）。这些知识点作用到了工具和语言生态之中，意味着你需要使用合适工具、遵循生态的玩法才能从中受益。

工具

工欲善其事必先利其器，对于程序员而言，这个器是编辑器…吗？Emacs, Vim, VS Code or PyCharm?

解释器

当然不是，这个器应当是让你能立马运行程序并立刻看到结果的工具，在Python的上下文中，它是Python的解释器。一般情况下，我们会选择最新版的解释器或者编译器，但是Python有一点点例外，因为Python3和2并不兼容，那么该选择哪个版本呢？寻找这类问题的答案其实就是融入Python社区的过程。幸运的是，社区出版了一本书 *The Hitchhiker’s Guide to Python*，里面诚恳地给出了建议。所以不出意外，Python3是比较合适的选择。

因为Python安装起来很简单，我们跳过…吧？不过，大侠留步，你可知道Python其实只是一个语言标准，它的实现程序不止一个，其中官方的实现是CPython，还有Jython和IronPython等。不过，CPython作为使用最为广泛的解释器当然是开发之首选。

1
2
3
4
5
6

$ python3
Python 3.6.5 (default, Jun 17 2018, 12:13:06)
[GCC 4.2.1 Compatible Apple LLVM 9.1.0 (clang-902.0.39.2)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> print("hello world")
hello world

编辑器

虽然面向REPL编程（Repl-Oriented Programming）是一种比单元测试的反馈速度更快的编程方式，但是在REPL中编写应用程序并不合适，不合适的地方表现在代码不易组织（分模块）和代码没法记录（存盘）。所以我们需要可以编辑的源代码、目录和其它相关文件，这个时候就需要挑选趁手的编辑器。

神之编辑器Emacs中内置了python-mode，如果已经是Emacs用户，这款编辑器当是写Python的不二之选。编辑器之神的Vim排第二，如果你比较喜欢折腾Vim8.0的插件，或者想自己构建NeoVim的话。其它的编辑器，我不知道，不想用。不过PyCharm是Jetbrains家的IDE，靠谱。

有功夫在Terminal中装一个emacsclient，然后下载一个oh-my-zsh的插件emacsclient，就可以很愉悦地在Terminal中使用Emacs编辑文件了。

1
2
3
4
5
6
7
8
9
10
11
12

$ te hello_world.py # te: aliased to /Users/qianyan/.oh-my-zsh/plugins/emacs/emacsclient.sh -nw

"""
hello_world.py
Ctrl+x+c 退出emacs :)
"""
print("hello world")

$ python3 hello_world.py
hello world
$ python3 -m hello_world #注意没有.py的后缀
hello world

生态

基本工具比较好把握，但是何时选择什么工具做什么样的事情就不好拿捏了，而且如何把事情做成Pythonic的模样也是对经验和能力的考验。

如果我们不是编程小白的话，就需要充分利用迁移学习的能力了。学习的最好方法就是解决问题。不得不承认，在动手实践的过程，时间走得是最快的，在同一件事上花的时间越多也就越熟悉。

我们尝试用Python编写一个tree命令行（Command-Line Application），顾名思义，打印目录层级结构的程序，详细描述参看这篇命令行中 tree 的多重实现。

测试模块

怎么写测试呢？多年养成的TDD习惯让我首先想要了解什么是Python中常用的测试工具。答案不难寻找，unittest是Python内置的测试模块，而pytest是比unittest更简洁和强大的选择，所以我选择后者。

这个程序的测试我使用pytest，但是它并不是所有项目测试的唯一选择，所以最好能局部安装，尤其是限制在当前工程目录里。搜索查找的结果是，Python3内置的虚拟环境（Virtual Environment)模块可以做到这点。

虚拟环境
在当前创建venv目录(python3 -m venv venv)，然后用tree命令查看该目录的结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

$ python3 -m venv venv
$ tree -L 4 venv
venv
├── bin
│   ├── activate
│   ├── activate.csh
│   ├── activate.fish
│   ├── easy_install
│   ├── easy_install-3.6
│   ├── pip
│   ├── pip3
│   ├── pip3.6
│   ├── python -> python3
│   └── python3 -> /usr/local/bin/python3
├── include
├── lib
│   └── python3.6
│       └── site-packages
│           ├── __pycache__
│           ├── easy_install.py
│           ├── pip
│           ├── pip-9.0.3.dist-info
│           ├── pkg_resources
│           ├── setuptools
│           └── setuptools-39.0.1.dist-info
└── pyvenv.cfg

进入虚拟环境，然后使用pip3安装pytest测试模块，会发现venv目录多了些东西。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

$  . venv/bin/activate
venv ❯ pip3 install pytest
Collecting pytest
...

$ tree -L 4 venv
venv
├── bin
│   ├── py.test
│   ├── pytest
├── include
├── lib
│   └── python3.6
│       └── site-packages
│           ├── __pycache__
│           ├── _pytest
│           ├── atomicwrites-1.1.5.dist-info
│           ├── attr
│           ├── attrs-18.1.0.dist-info
│           ├── more_itertools
│           ├── more_itertools-4.2.0.dist-info
│           ├── pluggy
│           ├── pluggy-0.6.0.dist-info
│           ├── py
│           ├── py-1.5.3.dist-info
│           ├── pytest-3.6.2.dist-info
│           ├── pytest.py
│           ├── six-1.11.0.dist-info
│           └── six.py

此时，虚拟环境会在PATH变量中前置./bin目录，所以可以直接使用pytest命令进行测试。根据约定，测试文件的名称必须以test_开头，如test_pytree.py，测试方法也必须如此，如test_fix_me。遵循约定编写一个注定失败的测试如下：

1
2
3
4
5
6
7
8
9
10
11
12

"""
test_pytree.py
"""
def test_fix_me():
    assert 1 == 0

$ pytest
...
    def test_fix_me():
>       assert 1 == 0
E       assert 1 == 0
test_pytree.py:5: AssertionError

测试失败了，说明测试工具的打开方式是正确的。在进入测试、实现和重构（红-绿-黄）的心流状态之前，我们需要考虑测试和实现代码该放在哪里比较合适。

假设我们会把pytree作为应用程序分发出去供别人下载使用，那么标准的目录结构和构建脚本是必不可少的，Python自然有自己的一套解决方案。

目录结构

在Packaging Python Projects的指导下，我们略作调整，创建和源代码平级的测试目录（tests），得到的完整目录如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

.
├── CHANGES
├── LICENSE
├── README.md
├── docs
├── pytree
│   ├── __init__.py
│   ├── __version__.py
│   ├── cli.py
│   └── core.py
├── setup.cfg
├── setup.py
├── tests
│   ├── fixtures
│   └── test_pytree.py
└── venv

这样的目录结构不仅可以清晰地模块化，隔离测试和实现，提供使用指导和版本更新记录，还可以很方便地做到包依赖管理和分发，这得归功于setup.py，它是Python项目中事实标准（de facto standard）上的依赖和构建脚本，pytree下的setup.py内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

# setup.py
# -*- coding: utf-8 -*-

from setuptools import setup, find_packages
from codecs import open
import os

here = os.path.abspath(os.path.dirname(__file__))

about = {}
with open(os.path.join(here, 'pytree', '__version__.py'), 'r', 'utf-8') as f:
    exec(f.read(), about)
    
with open('README.md') as f:
    readme = f.read()

with open('LICENSE') as f:
    license = f.read()

setup(
    name='pytree',
    version=about['__version__'],
    description='list contents of directories in a tree-like format.',
    long_description=readme,
    author='Yan Qian',
    author_email='qianyan.lambda@gmail.com',
    url='https://github.com/qianyan/pytree',
    license=license,
    packages=find_packages(exclude=('tests', 'docs')),
    classifiers=(
        "Programming Language :: Python :: 3",
        "License :: OSI Approved :: MIT License",
        "Operating System :: OS Independent",
    ),
    setup_requires=['pytest-runner'],
    tests_require=['pytest'],
    entry_points = {
        'console_scripts': [
            'pytree = pytree.cli:main'
        ]
    },
    install_requires=[]
)

setup.py能帮助我们解决测试中依赖模块的问题，这样我们把pytree作为一个package引入到测试代码中。

1
2
3
4
5
6
7
8
9
10
11
12
13

venv ❯ python3
Python 3.6.5 (default, Jun 17 2018, 12:13:06)
[GCC 4.2.1 Compatible Apple LLVM 9.1.0 (clang-902.0.39.2)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys, pprint
>>> pprint.pprint(sys.path)
['',
 '/usr/local/Cellar/python/3.6.5_1/Frameworks/Python.framework/Versions/3.6/lib/python36.zip',
 '/usr/local/Cellar/python/3.6.5_1/Frameworks/Python.framework/Versions/3.6/lib/python3.6',
 '/usr/local/Cellar/python/3.6.5_1/Frameworks/Python.framework/Versions/3.6/lib/python3.6/lib-dynload',
 '/Users/qianyan/Projects/personal/public/pytree/venv/lib/python3.6/site-packages',
 '/Users/qianyan/Projects/personal/public/pytree/venv/lib/python3.6/site-packages/docopt-0.6.2-py3.6.egg',
 '/Users/qianyan/Projects/personal/public/pytree']

然后运行pytest或者python3 setup.py pytest，此时pytest会把.pytree/tests前置到PATH变量中，验证如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

# test_pytree.py
import sys

def test_path():
    assert sys.path == ''

venv ❯ pytest
-> AssertionError: assert ['/Users/qianyan/Projects/personal/public/pytree/tests', 
'/Users/qianyan/Projects/personal/public/pytree/venv/bin', ...] == ''

venv ❯ python3 setup.py pytest
-> AssertionError: assert ['/Users/qianyan/Projects/personal/public/pytree/tests', 
'/Users/qianyan/Projects/personal/public/pytree', ...] == ''

这里python3 setup.py pytest可以通过setup.cfg设置别名（alias）：

1
2
3

# setup.cfg
[aliases]
test=pytest

python3 setup.py test的效果和前面的命令等同。

使用TDD的方式实现了pytree核心的功能（源代码），然后考虑如何把它变成真正的命令行程序。首先要解决的问题是如何以用户友好的方式显示需要哪些传入参数，我们期待pytree -h能提供一些帮助信息，为了不重复造轮子，挑选现成的Option解析库比较轻松。Python内置的argparse已经足够用了，不过docopt值得尝试。

依赖管理

setup.py提供了依赖管理功能，声明依赖及其版本号。

1
2
3

# setup.py
...
install_requires=[docopt==0.6.2]

然后运行python3 setup.py develop安装。就绪之后，编写cli.py作为命令行程序的入口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#!/usr/bin env python3
"""list contents of directories in a tree-like format.
  Usage: 
    pytree <dir>
    pytree -h | --help | --version
"""
import pytree.core as pytree
import pytree.__version__ as version

def main():
    from docopt import docopt
    arguments = docopt(__doc__, version=version.__version__)
    dir_name = arguments['<dir>'] 
    print('\n'.join(pytree.render_tree(pytree.tree_format('', dir_name))))

if __name__ == "__main__":
    main()

通过打印help信息的方式验证是否符合预期：

1
2
3
4
5

$ python3 pytree/cli.py --help
list contents of directories in a tree-like format.
  Usage:
    pytree <dir>
    pytree -h | --help | --version

当然理想的结果是直接可以运行pytree --help，setup.py的console_scripts刚好派上用场。

1
2
3
4
5
6

# setup.py
    entry_points = {
        'console_scripts': [
            'pytree = pytree.cli:main' #以pytree作为命令行程序的调用名
        ]
    }

此时查看which pytree显示/Users/qianyan/Projects/personal/public/pytree/venv/bin/pytree，说明pytree已经在路径变量当中，可以直接执行：

1
2
3

$ pytree tests/fixtures
tests/fixtures
└── child

完成了命令行程序并通过测试，我们尝试发布到测试仓库（TestPyPI）供其他人下载使用。

包发布

依照文档描述，先去TestPyPI注册用户，本地打包成发行版，然后安装twine工具发布。

1
2
3
4
5
6
7
8

$ python3 -m pip install --upgrade setuptools wheel
$ python3 setup.py sdist bdist_wheel
$ pytree dist # pytree查看dist目录
dist
├── pytree-1.0.2-py3-none-any.whl
└── pytree-1.0.2.tar.gz
$ python3 -m pip install --upgrade twine
$ twine upload --repository-url https://test.pypi.org/legacy/ dist/* #or twine upload --repository testpypi dist/* 如果你配置了~/.pypirc

上传成功需要一段时间，等待服务完成同步才可以下载，我们在另一个虚拟环境中进行验证：

1
2
3
4
5
6
7
8

$ python3 -m venv test
$ . test/bin/activate
test > python3 -m pip install --index-url https://test.pypi.org/simple/ pytree==1.0.2
test > ls venv/lib/python3.6/site-packages/
...
pytree
pytree-1.0.2.dist-info
...

确保site-packages目录下有这两个目录：pytree和pytree-1.0.2.dist-info，然后我们就可以完成最后的验证阶段了，如下：

1
2
3

test > pytree tests/fixtures
tests/fixtures
└── child

这里版本号之所以是1.0.2，是因为已经上传过了0.0.1, 1.0.0, 1.0.1 等版本，TestPyPI不允许同名同版本的文件重复上传，即使删除原来的文件也不行。前面的版本都有一定的错误，错误的根因在于find_packages以及package_dir的配置项文档说明很模糊，而且只有到上传到TestPyPI然后下载下来，才能验证出来，这种缓慢的反馈是Python的应该诟病的地方。

注意
find_package()也是一个深坑，第一个参数如果写成find_packages('pytree', exclude=...)，那么pytree下的所有Python文件都会被忽略。原因是pytree已经是package，所以不应该让setup去这个目录找其他的packages.

这个package_dir也是如此，我们如果设置package_dir={'': 'pytree'}，setup.py就会将/Users/qianyan/Projects/personal/public/pytree/pytree前置到PATH中，这会导致console_scripts': ['pytree = pytree.cli:main']抛出错误 ModuleNotFoundError: no module named ‘pytree’，究其原因是pytree/pytree导致setup尝试在pytree/pytree这个package里头找自己（pytree），自然找不到。但是如果改成console_scripts': ['pytree = cli:main']，因为cli在pytree/pytree底下，所以就能成功执行。当然这是一种错误的写法。

如果遇到了 ModuleNotFoundError: no module named ‘pytree’ 的错误
，最好的方式就是import sys, pprint然后pprint.pprint(sys.path)，很容易发现Python运行时的执行路径，这有助于排查潜在的配置错误。

资料

1. Pytree Source Code
2. The Hitchhiker’s Guide to Python
3. Emacs python-mode
4. Python Test Tool
5. Packaging Python Projects

关于环境和数据类型

简介

1. Emacs集成 Idris 开发环境
2. Idris repl 使用说明
3. Idris 代数类型定义

1. Emacs 安装 idris-mode

1
2
3
4
5
6
7

(use-package idris-mode
  :mode (("\\.idr$" . idris-mode)
         ("\\.lidr$" . idris-mode))
  :ensure t
  :defer t)

(provide 'init-idris)

emacs 打开任何以*.idr和*.lidr作为后缀的文件，都可以启用idris-mode.
另外，使用C-c C-l可以在*idris-repl*中加载当前文件并启用 type check 进行检查，出现的错误会打印在*idris-notes* buffer中。

注意
关于 IO 的调用问题，经典 Hello World 程序：

1
2
3
4

module Main

main : IO ()
main = putStrLn "Hello World"  

当需要在repl中调用 main 方法时，需要通过:x main 执行，才能看到执行结果，Hello World 会显示在*idris-process* buffer 中。原因是 repl 会返回一个 IO action，这个 IO action 只会在 idris 之外 hook 的 terminal 中才会执行。https://github.com/idris-lang/Idris-dev/issues/3152

1

:x  <expr>  Execute IO actions resulting from an expression using the interpreter

2. 自定义数据类型

我们先定义一下自然数：自然数就是从0开始，后面的数都比前一个自然数多1的数列。我们从小知道的自然数0, 1, 2,…,100,… 看上去只是一系列割裂开的一组符号，但是事实上，数列本身必然存在一些属性，数与数之间必然存在规律。

基于前面提到的自然数的属性，我们定义自然数如下

1

data Natural = Z | S Natural

读作：自然数要么是Z（零），要么是自然数的后继(S)

2.1 定义加法

接下来，我们定义自然数的加法运算

1
2
3

plus : Natural -> Natural -> Natural
plus Z     m = m            -- 模式1
plus (S n) m = S (plus n m) -- 模式2

首先定义出了 plus 函数的类型，它是接收两个自然数，然后返回一个自然数的函数，这里使用了柯里化的表现方式。
plus Z m = m 表示任何自然数加上零，都得自然数本身；
plus (S n) m = S (plus n m) 表示任何两个自然数相加，都等于其中一个自然数的前趋和另一个自然相加结果的后继。这句话说起来比较绕，但是只要展开之后就比较容易理解了。

考察1 + 1 = 2，可以表达如下：

1
2
3
4

(S Z) # 1 是 0 的后继
plus (S Z) (S Z) -- 1 + 1
S (plus Z (S Z)) -- 根据模式2展开上面的式子
(S (S Z))      -- 根据模式1展开上面的式子

(S (S Z)) 就是自然数2

2.2 定义乘法

1
2
3

mult : Natural -> Natural -> Natural
mult Z     m = Z
mult (S n) m = plus m (mult n m)

mult Z m = Z表示任何自然数乘以零，都得零；
mult (S n) m = plus m (mult n m)表示任何两个自然相乘，都等于其中一个自然数和另一个自然数的前趋相乘结果再加上这个自然数。

学习资料
[1] Idris mode
[2] Learn idris
[3] Idris docs

太长不读篇

《技术简史》原著*Ruling the wave, From the Compass to the Internet, a History of Business and Politics along the Technological Frontier)*。依书中的视角，从15世纪的地理大发现到21世纪的网络音乐，每一次技术的创新和商业发展都大致遵循4个阶段规律：

1. 创新
2. 市场化
3. 创造性的混乱
4. 制定规则

而制定规则者为王就是本书的核心观点。引用1993年获得诺贝尔经济学奖的Douglass North的研究：市场刚出现时，稍大的组织可以通过行会或协会来规范市场的交易，但这些早期的市场如果想要最终发展成为高效的大型企业的话，就需要国家介入，制定各种规章制度以保证贸易顺畅。用他的话来说就是，巩固市场所需的财产所有权必须由政治制度和司法体制通过保证签订契约的成本最小化来落实。

不过，这里的问题是政府就能保证签订契约的成本最小化么？如果出现一种新的技术，它可以让这个成本小于政府的监管和司法投入，那么它就不仅是一种技术的革新，同时是对技术发展既定规律的革新。答案是区块链？没有产权和交易的规则，市场一定不会发展。这里的产权对应区块链应用中资产转账，而交易规则对应的是智能合约。那么答案可能真是区块链了。

作者简介

Debora. spa，女，哈佛大学博士，哈佛商学院教授。著有《The baby business》和《Ruling the waves》（译本：技术简史）。这本《Ruling the waves》最早出版于2001年，中文译本于2017年4月由中信出版社出版。主要描述了从15世纪的大航海到21世纪的互联网时代，创新技术的发展规律，得出制定规则者为王的结论。

配合《维多利亚时代的互联网》一起读，对电报带来的社会变革会更有切身感受，通过时间线串联起来理解效果更佳。

历史在一遍遍重演

“没文化，真可怕！”
回到中世纪那黑暗的1000年间，教会的僧侣掌握着知识的生产和传播，未曾开化的愚民既没有能力也没有渠道获取知识，其中就包括圣经抄本及其解释权。这些愚民只能听从教会宣扬的神祗和信仰，怀疑者统统被审判为异教徒和魔女，火烧异教徒和魔女狩猎甚嚣尘上，一切都是没有文化的恶果。但是压迫必然遭遇反抗，活字印刷术的出现让知识出版变得开放和自由并且廉价，知识的生产和传播开始规模化，人们可以直接获取知识而不再依赖教会，解读圣经的权利得以回归，随之稀释的是教会的控制权。但是教会也不会坐以待毙，他们建立自己的天主教印刷工厂推动反宗教改革，印制大量《圣经》和核心书刊，并且知道如何争取有读写能力的追随者，进而掌握了知识的核心传播形式，其统治地位并没有被动摇。虽然如此，但是世界的规则已经改变，权力发生了转移。

印刷术将物理世界中这些以前需要手抄的竞争性资源变得廉价，让知识持久化下来，打破了时间的侵蚀，但是知识的传播却还是受限于距离，行进缓慢。每当这时，总有英雄出现。19世纪，电报的发明以及历经坎坷的商业化进程，彻底改变信息传播的形式，加速了全球的信息互联。再加上19世纪末，电话和无线电通讯的发明，整个世界宛若突然缩小成一体，信息的传递变得不可思议得快速和廉价。20世纪计算机的发明奠定了20世纪末的互联网诞生的基础，信息传递不仅变得快速，其内容还异彩纷呈。这个时代，没有哪个组织和团体可以垄断信息及其传播形式。

第一次浪潮

15-17世纪的大航海时代，航海技术的大发展开启了一个新的商业世界。
葡萄牙亨利王子，获得“航海家”亨利的称号，1460去世，大航海时代来临。

技术创新
14世纪，欧洲的船运贸易无法远离海岸，受制于变幻莫测的天气和有限的航海技术。威尼斯的商人只敢在亚得里亚海和爱奥尼亚海（地中海）航运，不敢穿越直布罗陀海峡（西班牙和北非摩洛哥）来到北大西洋。英国商人也只敢航行到法国西部的比斯开湾。

14世纪初，船舶工艺升级，厚重的船让位于轻快的帆船，这些船比原来的更大也更轻。另外，13世纪中期，《图解海航手册》可让航海员可以估算地理位置。15世纪早期，指南针等技术也等到了广泛应用。

先驱
葡萄牙的亨利王子，为了实际的目的——西非的黄金，基督教布道等，沿着非洲的西海岸航行，并且记录下了航海活动的信息收集。在这过程中，改良了地图绘制和造船工艺，让很少的人就能操作很大的船。早期的船只能顺风航行，但是亨利王子的轻快的小船在逆风时也能航行，这样远航的船只也能顺利返航。

亨利王子与1460年去世，新一代的探险者正式开启了大航海的时代。葡萄牙海员率先南下到达非洲的最南端，并且来到了印度洋的西海岸。1484年，哥伦布得到了西班牙国王费迪南的资助，发现了美洲新大陆；1521年，麦哲伦绕过了南美洲最南端，进入太平洋，然后到达亚洲。这证明了世界是圆的。

1569年，比利时的绘图者墨卡托（Mercator）发明了一种新式的地图绘制方法，墨卡托投影，把地球沿着经线分割开然后展开成一个矩形，这样的绘制技巧在精度上有了质的飞跃。普通的航海员也可以远航了。

创新性的混乱
海盗。16-18世纪，伴随着大海航时代的到来，海盗猖獗。主要原因一个是海上并没有很好的法律约束，还有一个最重要的原因是国家在维护自己的权益。这个时代大部分的欧洲国家都在从事私掠活动。给海盗授予掠夺的权利是最经济的打压敌国贸易的政治手段。

大海盗弗朗西斯德雷克（Francis Drake）的故事

德雷克大半个人生都是海盗。早年间，他在英国精英的支持下，做起了“三角贸易”。从非洲俘获奴隶，然后卖到加勒比海的西班牙殖民者，再从他们手上换取毛皮等货物，然后再带回英国。不过，在一次返回英国的航行中，他的船遭到了来自西班牙军队的袭击死里逃生。复仇的怒火在心里燃烧。自从被英国赋予掠夺权之后，他开始袭击美洲的西班牙殖民地，掠夺海上的丝绸和黄金。1581年，伊丽莎白一世女王授予他爵位。一以贯之的海盗生存法则——“在合适的时候，跳上正确的船”。

制定规则
1701年，英国政府公开绞死了著名的海盗之一的威廉·基德
1721年，当罗杰斯离开拿骚岛，加勒比海最猖狂的“黑胡子”艾华德·蒂奇和“白棉布”杰克也已经绝迹。

1730年，海盗的黄金时代结束了，但是知道1830年才算几乎根除。

为何原本受到国家暗中保护的海盗突然遭到了所有政府的封杀？因为规则改变了。海盗这个团体不再是政府的政治手段，反而成为了问题。1588年，西班牙无敌舰队在和英国的海战中战败，伴随而来的是西班牙在大西洋垄断时代的没落。而且原来的大海航时代的先驱逐渐占领了海洋贸易这些商人，他们为了维护自己的利益，也开始要求政府打击海盗。1856年，欧洲7个国家的代表在巴黎会面，签署了《巴黎宣言》，正式宣布任何海上的私掠行为都被禁止。

电报时代

技术创新
1791年法国的查普兄弟通过铜锅和同步的2倍速时钟传递信息。法国的查普发明了感观电报，1793年，法国建立起第一个观感电报塔。1837年，摩尔斯发明了摩尔斯电码和电报，并将电报推出实验室。

电报先驱
库克，菲尔德，奥莱利，彭德这些电报先驱们看到了电报的商业潜力，然后发展起了新的市场。

创新性混乱
电报市场发展起来之后，遇到了和其它技术一样的问题。最大的问题就是如何合作：电报的线路是分离的，同时使用的code book（代码本）也不同。

如果电报网络互不兼容，那么每条线路的价值都会被降低。电报先驱们开始制定标准和规则。

制定规则
欧洲和美国一开始介入市场的方式不同。欧洲各国都有自己的电报线路和标准，因为当时大部分的电报公司都和政府有关系，为了能够实现国际间的通讯，欧洲大陆共同推行相同的标准和技术规范，这要归功于成立的国际电报联盟。

不过美国恰好相反，政府在早期就退出了电报市场。然后私营企业强强联合，建立起了一套共同遵守的规则。不过市场竞争的本质就是消除竞争，在各自利益的驱使下，短暂建立起的联盟是脆弱。这表现在电报市场就是西部联合公司一家独大，而这实质上就是垄断。最后，政府颁布了公共规则。1910年，美国国会通过一项法案，授予州际商业委员会调查电报收费的权利。1934年，通过通信法案，正式把规范电报业的任务交给了联邦通信委员会。

无线电时代

技术创新
19世纪20年代末，电磁感应让无线电的研究向前一步。1865年，苏格兰数学家麦克斯韦证明了电和光可以以相同的速度在空气中传播。最终在1887年，德国科学家赫兹成功地用实验证明了麦克斯韦用数学说明的现象。

马可尼发明了无线电装置，并成功将它进行了商业化应用。

无线电先驱
马可尼无线电报公司和德国德律风根公司，那时候还只是能够传递电码；1918年美国的RCA（美国无线电公司）诞生，已经可以进行声音广播了。

创新性混乱
1910年左右，传播信号开始互相干扰。1912年4月12日，豪华巨轮”泰坦尼克号“撞到冰山沉没，因为信号阻塞特别严重，导致家属迟迟得不到救援信息。因为这件事，美国政府要求业余无线电操作员需要取得营业执照，而且无线电频谱变为离散状态。

自从广播播放音乐火了之后，人们开始私自搭设电台，同时混乱使用频道的方式开始发生。

制定规则
1927年，美国出台了《无线电法案》，大公司相当统一，无线电行业在这个时候”可能是全美唯一一个全体一致要求管制自身的行业“了。究其缘由，有线电报的所有者和财产所有权是明确的，但是无线电波是无形的，因为没有一个成形的财产所有权分配系统，所以建立频段划分系统除了政府没有人可以胜任。

卫星电视和数字电视时代

1983年，鲁伯特·默多克（Rupert Murdoch）的新闻集团购买了一家英国的卫星电视SATV（卫星电视）并更名为 Sky，他们想在英国的电视市场努力地开创出一片卫星电视的天地。因为卫星电视在后期的维护以及远距离传播上有天然的优势。而且，BBC电视只为政府代言，播放充满精英文化的正经说道题材也确实让民众难以下咽。以丘吉尔为代表的保守党重新掌权（二战期间）之后，开始稳步地将竞争引入电视市场。

英国的无线电视技术的历史久远。早在1926年，一名叫做约翰·贝尔德（John Baird)的企业家，说服了英国广播公司（BBC）发展广播可视图画的技术，进而演化成了BBC电视业务。经历过一段时间的国有垄断之后，由于政策的允许，各大商业独立电视台也开始进入电视市场，并且在市场份额上形成了势均力敌的局面。当然，政府的监管机制从来没有落下，ITA（独立电视局，类似广电总局）负有监管和审核独立电视节目的责任。只不过这个还只是地面上的无线电视广播，压根没有卫星电视什么事儿。

时间来到了1977年，世界无线电管理委员会分配了已知的卫星空间，同时规定参与国可以得到当时广播卫星所有频道中5个频道。英国将其中的2个频道分配给了老牌的BBC，剩下的3个频道通过竞标的方式分配给了BSB（英国卫星广播公司）。Sky公司却在竞标的过程中失败了，但却不一定是坏事。当BSB调用大量精英研发新技术（D-MAC）标准的时候，Sky公司租了位于法国，比利时和德国三国交界处，一个叫做卢森堡大公国的通讯卫星。这个决策的厉害之处是恰逢欧洲委员会规定：对任何广播卫星的制裁只能由来源国发起。Sky公司绕过了英国的法律约束，同时发动和推出了上门推销技能和免费的售后服务，这些举措成功地吸引了客户，并最终帮助Sky公司占领了市场。在这场商业角逐当中，Sky成功扭转局势，打败了主要竞争对手BSB。1990年，两家公司达成协议，合并成一家公司，并取名为BSkyB公司。同时默多克的新闻集团获得了50%的股份，并拥有绝对的控制权。

BSkyB的故事并没有结束，因为有一位创奇的人物还没有登场。

由于商业模式和原来那些独立电视没有太大区别，导致BSkyB没有足够的订单来获得广告收入，再加上合并之后内部摩擦不断，BSkyB在起飞阶段的日子并不好过。于是，默多克私下邀请萨姆·克里泽木（Sam Chisholm）加入了Sky。在那之前，克里木泽就以果敢和成就而闻名。

克里泽木迅速采取了行动。他首先抢占先机控制电视内容，飞去美国和好莱坞的影片公司签约，这其中就包含默多克自己的福克斯公司（21 Century FOX）。非常意外的，他应好莱坞影片公司对产权的保护要求，发展出了一种全新的商业模式——通过加密技术保护产权，并引导顾客为片源付费，从而建立起来一种关联影片提供商和顾客的全新收费模式。除此之外，他也和体育赛事联盟签约，将原来处于公共领域的体育赛事直播转化成了私营方式。虽然这种方式遭到各方质疑和控诉，但是最终还是安然无事，并获得了巨额回报。

其次运用准入控制手段，他联合以色列的Adi Shamir（RSA加密方式中A指的就是他）建立了一家专门为BSkyB公司提供加密服务的NDC（News datacom）公司。同时积极开发包含加解密、内容管理功能的机顶盒。在稳固新建立的商业模式的同时，还通过市场份额的优势，迫使其它内容供应商加入自己的系统。这种做法巩固了BSkyB的生态环境，也为后来其它竞争手对其垄断的控诉提供了证据。

回顾Sky公司的一路辉煌，就会发现挺符合辩证法中的否定之否定的规律。卫星电视技术，因为其创新的特征，让Sky公司绕过了英国的法律和规则，以一种“海盗式”的手段，打开了顽固的英国电视市场。当竞争者开始用反垄断法为自己发言的时候，它又用自创的商业模式——付费电视，把自己隐藏到整个电视市场这个大背景下，躲过了制裁。貌似一切规则都失效了——这就是创新的力量。但是中国有句老话“成也萧何败也萧何”，技术界从来不缺乏新闻。

数字电视时代扑面而来。由于数字信号比模拟信号具有可压缩，可降噪的优势，很快得到政府的重视。1996年，英国推出了《广播法》并统一建立6个新的数字频道。在过渡到数字电视的阶段，英国政府提供了很多对私营企业十分友好的条件。一开始混有BSkyB血统的BDB（英国数字广播电视，后改名为ONdigital）在政治和商业利益的驱使下，将BSkyB从联盟中踢出，并获得了政府划拨的近一半的地面数字波段。

BDB因为有了数字许可证，便开始和BSkyB展开了合作和竞争。一方面BSkyB依赖于BDB的许可证；另一方面，BDB又依赖BSkyB提供的影片服务。这期间BDB更名为ONdigital。1999年末，BSkyB和ONdigital公司成为了英国数字电视市场的两大巨头。经过这轮技术洗牌之后，政治方向也开始朝着不利于BSkyB公司的方向倾斜，表现在BSkyB对足球俱乐部曼彻斯特连队接管被禁止。另外，政府颁布了新一轮的电视标准中，要求提供一种标准的接口，而BSkyB公司从未使用过，而且这相当于打破了BSkyB的生态闭环，也意味着它不得不和其它电视公司展开公开竞争。

这一波数字技术的截胡操作，让BSkyB失去了垄断的地位。否定之否定同样作用到了BSkyB自己的身上。不管如何，电视技术还在持续发展中。

密码朋克

密码朋克（crypherpunk）指的是一帮倡导使用强加密技术保护个人隐私的活动家，他们的敌人是企图剥夺民众使用加密技术的政府。触发密码朋克组织形成的导火索是1993年美国政府企图在所有的计算机和手机植入一种Clipper芯片，这种芯片会包含一个私钥，当设备被卖出后，对应的私钥会被存储在第三方的契约账户中。一旦政府获得许可就会取出私钥查看传输的情报。然而，这种措施无疑刺激到了密码朋克们的神经，对于他们而言，这是政府企图建立“网络极权国家”的阴谋，必须反抗！结果白宫方面放弃了这一方案。这是属于密码朋克的胜利。

加密技术的发展有自己鲜明的特征。首先是制定标准的过程，几乎不存在混沌的状态。新的加密技术出现，旧的就随之淘汰，顺应自然；其次它也不存在拥塞状态，毕竟它分明就不是一种通讯技术，相比于电报、无线电、互联网以及区块链在初期遇到的拥塞问题，加密技术几乎不存在需要分割的稀缺资源，也就无需外部力量维持所有权的分配秩序；最后，纵观加密技术的历史，这项技术从诞生之初就很少申请过专利。当然现代加密技术倒是申请了不少专利，但是加密界有自己独特的一套共识——闭源的加密算法是不安全的。这或许不能构成对所有权混乱的理由，不过，由于政府最初对加密技术的封闭，所以它在发展过程中没有出现创造性的混乱状态，所以对于加密技术所有权的任何保护措施也就不太重要了。

微软托拉斯

微软帝国的崛起和侵权案件

1968年，比尔·盖茨接触到计算机的世界。他和保罗·艾伦（Paul Allen）一起为DEC（数字设备公司）编写程序。1975年7月，艾伦在Altair机器上成功地演示了改良过的BASIC语言五个月之后，微软（MicroSoft）公司成立了。这时候的微软靠卖BASIC语言的光盘获取版权收入，即便彼时的软件所有权概念还很模糊。

微软的将BASIC语言据为己有的做法在当时引起了轩然大波，而争论的中心发生在一家业余爱好者俱乐部——家酿计算机俱乐部最初的理念是“通过共享经验和相互交流构想，我们促进了这门艺术的发展，使更多的人用低价的计算机成为可能”。成员复制了微软的BASIC代码，并开始随意分发，在他们看来，微软的BASIC代码本来就属于公众。这种做法影响了微软的版权收入，同时也惹恼了比尔·盖茨。盖茨批判这帮人是强盗，但是这些人认为比尔·盖茨把几百人花了几年做出来的软件占为己用的行为才是强盗行径。

虽然盖茨在这次争论中缓和了态度，但是软件的版权问题迟迟没有定论。直到Altair公司被出售给加利福尼亚的一家较大的公司，这个公司声称BASIC语言归自己所有，并且禁止其他生产商使用。这回盖茨没有怂，微软同这家公司进行了长达6个月的诉讼大战，最终赢得了胜利。这个案件不仅仅宣告了微软对BASIC语言的所有权，也意味着一种定论：软件是私有财产。

1983-1986年，苹果公司和微软的达成合作，微软将Word等常用办公软件提供给了苹果，而苹果通过销售Macintosh电脑帮助微软销售软件。但是微软发布了Windows2.03，抢占了苹果公司在PC的市场份额，苹果公司这时冷静不下去了，以盗用Macintosh界面所有权的理由将微软告上法庭。虽然最终对于微软的所有控诉都被法院解除了，苹果公司也因此遭受了巨大的打击，但是微软也因为反托斯拉法案受到了美国联邦贸易委员会（FTC）的调查，并且在1994年签署一项包含了若干义务的法律协议，其中规定了微软不得在操作系统中捆绑销售自家的软件，同时微软也承诺不再使用任何许可协议。

浏览器战争中的反托斯拉

时间来到了1995年，这是互联网商业化的元年。这一年，如今已经是两大世界级电子商务巨头的eBay和Amazon上线运营，在中国，杭州的大学英语老师马云和宁波的电信员工丁磊离开公职，分别创办了阿里巴巴和网易。Jim clark和Mark Anderson成立的公司Netscape凭借Navigator（前身是Mosaic）这款网络浏览器迅速横扫互联网市场。在CERN（欧洲粒子研究院）研究员Tim Berners-Lee发明了HTML、HTTP协议和URL之后，信息通讯发生了变革，这让非技术用户上网成为了可能。这时候，Anderson等人就想着如何把图像和多媒体引入网络，最后的答案便是通过浏览器。

大公司总是习惯后知后觉，微软也不例外。在Netscape公司的Navigator浏览器迅速占领了超过90%的浏览器市场份额后，微软按捺不住了——以卖自家软件见长的微软很害怕Navigator成为网络的入口，用户便可以下载任何产商的软件。所以微软开始行动了，首先它成立了一个互联网平台和工具部门，其次通过威逼利诱的手段限制和控制Netscape公司，最后通过“行贿”的方式联合AOL推广自己的IE浏览器。当然，这些措施生效了，Netscape在浏览器市场上的份额迅速缩减了一半以上。然而，微软这种行为最终还得诉诸法律。

当商业利益上竞争不过巨头的时候，留给这些创业公司最后的武器就是反垄断法。在这场旷日持久的诉讼案件中，法院确定了微软的反垄断行为，但是并没有接受Jackson法官拆分微软的命令。2001年11月2日，联邦司法部与微软就案件达成了和解，但是这次和解既没有要求微软修改源码从Windows中剥离IE浏览器，也没有限制微软未来在Windows中捆绑其它软件，所以令很多人感到不满。

微软的故事告诉我们，当进入一个崭新的领域时，原先社会上比较分明的所有权和反托拉斯的界定问题变得模棱两可起来。大公司可以很快地在新兴的市场之上建立起法则这时候法律监管是滞后的。但是一旦新兴企业创造出自己的市场之后，原先的大公司还想要入场并部署自己的规则，那么不论是企业、用户还是政府都会介入进来反对垄断和维护秩序。

网络音乐

1999年，19岁的Shawn Fanning辍学创建了Napster这个革命性的网站，它允许用户在网站上自由地交换歌曲，这种免费的上传和分发的模式很快就颠覆了传统的唱片行业。传统的唱片行业掌控了音乐录制，分发渠道，前期宣传和明星包装，也同时形成了对音乐制作人的“奴役”和压榨。随着数字音乐技术（MP3）的成熟，有些歌手直接将自己的音乐上传到如Naspter这样的网站上，听众就可以自由地下载和分发了。

随着Napster网站上用户数的不断增加，盗版的问题也日益严重起来。原本歌手将音乐上传到网上，是想脱离唱片公司根深蒂固的体系，但是后果是歌手也没法获得相应的报酬了。于是，围绕网络空间中的知识产权保护也引来了大量的讨论。有人说“未来将会胜利，在网络世界中不存在所有权”，也有人说“知识产权的整个结构和价值都在改变……技术性障碍将几乎为零……法律本身变得无所适从或遭到削弱”。

但是从历史中走过来，我们发现网络世界的版权还是保留了下来。苹果公司的Jobs开创的iTunes和iPod从某种程度上，拯救了数字音乐的版权和唱片公司。早在2004年，iTunes store 在合法数字音乐市场的份额就超过了70%，2011年数字音乐的市场份额更是超过了实体音乐（刻录在唱片等载体上的音乐）。当正版商开始用资本发展网络商业模式时，它也会收购那些盗版的公司，自己也得到进一步发展。从这些方面看，不难得出数字版权更像是在唱片公司、数字音乐公司以及公众参与下共同制定的一项行业标准，然后由政府强制执行。所以最终胜利还是属于那些制定行业标准的家伙，尽管总有人存在一种理想国的幻想。

– 于 2018-05-01

[1] 技术简史

解题思路

1. 利用递归，将目录转换成 {:name: ".", :children: []} 结构
2. 对于第一层目录名，前缀装饰成 T_branch = "├── " 或者 L_branch = "└── "
3. 对于子目录，前缀装饰成 I_branch = "│ "或者SPACER = " "
   举例如下：

   1 2 3 4 5 6 7 8 9 10 11

   . ├── tree.py # 不是最后一项，所以使用 T_branch 前缀 ├── files.py ├── lists.py ├── tuples.py ├── resources │ └── README.md # 由于其父亲不是最后一项，所以使用 I_branch 前缀 ├── recursion.py └── data # 是最后一项，所以使用 L_branch 前缀 ├── output.txt # 由于其父亲是最后一项，所以使用 SPACE 前缀 └── data.txt

python 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

#!/usr/local/bin/python
# -*- coding: UTF-8 -*-

"""
list a directory in tree way.

children(path):
    map(lambda name: tree(path, name), listdir(path))

tree(parent, dir_name):
    if is_file(parent, dir_name):
        return {'name': dir_name, 'children': []}
    else:
        children = children(join(parent, dir_name))
        return {'name': dir_name, 'children': children}
"""
import os
import functools as fp

I_branch = "│   "
T_branch = "├── "
L_branch = "└── "
SPACER = "    "

def _children(path):
    return map(lambda filename: tree_format(path, filename), os.listdir(path))

def tree_format(parent, dir_name):
    path = os.path.join(parent, dir_name)
    is_file = os.path.isfile(path)
    children = [] if is_file else _children(path)
    return {'name': dir_name, 'children': list(children)}

def render_tree(tr):
    name = tr['name']
    children = tr['children']
    return [name] + fp.reduce(lambda l, r: l + r,
                              map(lambda arg: render(len(children))(*arg),
                                  enumerate(children)),
                              [])

def render(length):
    def prefix(index, child):
        is_last = (index == length - 1)
        prefix_first = L_branch if is_last else T_branch
        prefix_rest = SPACER if is_last else I_branch
        tr = render_tree(child)
        head = prefix_first + tr[0]
        tail = [prefix_rest + t for t in tr[1:]]
        return [head] + tail
    return prefix

if __name__ == "__main__":
    print '\n'.join(render_tree(tree('', sys.argv[1])))

$ python3 tree.py . #打印当前的目录的所有文件及子目录
.
├── tree.py
├── files.py
├── lists.py
├── tuples.py
├── resources
│   └── README.md
├── recursion.py
└── data
    ├── output.txt
    └── data.txt

Clojure 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

(ns tree
  (:require [clojure.java.io :as io]
            [clojure.string :as str]))
(def L-branch "└── ")
(def T-branch "├── ")
(def I-branch "│   ")
(def SPACE    "    ")

(declare tree)

(defn children [path]
  (map #(tree %) (.listFiles path)))

(defn tree [dir-name]
  (let [path (io/file dir-name)
        dir? (.isDirectory path)]
    {:name (.getName path)
     :children (if dir? (children path))}))

(defn render-tree [{name :name children :children}]
  (cons name
        (mapcat (fn [child index]
                  (let [last? (= index (dec (count children)))
                        prefix-first (if last? L-branch T-branch)
                        prefix-rest (if last? SPACE I-branch)
                        sub-tree (render-tree child)]
                    (cons (str prefix-first (first sub-tree))
                          (map #(str prefix-rest %) (rest sub-tree)))))
                children
                (range))))

(defn -main [& args]
  (->> 
      (tree (first args))
      (render-tree)
      (str/join "\n")
      (println)))
$ lein run -m tree .
.
├── tree.py
├── files.py
├── lists.py
├── tuples.py
├── resources
│   └── README.md
├── recursion.py
└── data
    ├── output.txt
    └── data.txt

Golang 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

package main

import (
	"fmt"
	"io/ioutil"
	"os"
	"path"
	"strings"
)

const (
	I_branch = "│   "
	T_branch = "├── "
	L_branch = "└── "
	SPACER   = "    "
)

type entry struct {
	name     string
	children []entry
}

func (e entry) String() string {
	if len(e.children) == 0 {
		return e.name
	} else {
		s := e.name
		for _, child := range e.children {
			s += child.String()
		}

		return s
	}
}

func Children(path string) []entry {
	result := []entry{}
	files, _ := ioutil.ReadDir(path)
	for _, f := range files {
		result = append(result, Tree(path, f.Name()))
	}

	return result
}

func Tree(parent, dirName string) entry {
	realPath := path.Join(parent, dirName)
	theChildren := []entry{}
	if f, ok := os.Stat(realPath); ok == nil {
		if f.IsDir() {
			theChildren = Children(realPath)
		}
	}
	return entry{name: dirName, children: theChildren}
}

func RenderTree(e entry) []string {
	name := e.name
	children := e.children
	result := []string{name}

	for index, child := range children {
		subTree := RenderTree(child)
		prefixFirst := T_branch
		prefixRest := I_branch
		if index == len(children)-1 {
			prefixFirst = L_branch
			prefixRest = SPACER
		}

		result = append(result, prefixFirst+subTree[0])

		for _, sub := range subTree[1:] {
			result = append(result, prefixRest+sub)
		}
	}
	return result
}

func main() {
	fmt.Println(strings.Join(RenderTree(Tree("", os.Args[1])), "\n"))
}
$ go run tree.go .
.
├── data
│   ├── data.txt
│   └── output.txt
├── files.py
├── lists.py
├── recursion.py
├── resources
│   └── README.md
├── tree.py
└── tuples.py

NodeJS 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

const path = require('path')
const fs = require('fs')
const I_branch = '│   '
const T_branch = '├── '
const L_branch = '└── '
const SPACER   = '    '

function children(path) {
    return fs.readdirSync(path).map(filename => tree(path, filename))
}

function tree(parentDir, dirName) {
    let realPath = path.join(parentDir, dirName)
    let isDir = fs.statSync(realPath).isDirectory()
    return {name: dirName, children: isDir ? children(realPath) : []}
}

function prefix(len) {
    return (tr, index) => {
        let isLast = len == index + 1
        let prefixFirst = isLast ? L_branch : T_branch
        let prefixRest = isLast ? SPACER : I_branch
        let [head, ...tail]= renderTree(tr)

        return [prefixFirst + head].concat(tail.map(name => prefixRest + name))
    }
}

function renderTree({name: name, children: children}) {
    return [name]
        .concat(children
            .map(prefix(children.length))
            .reduce((l, r) => l.concat(r), []))
}

console.log(renderTree(tree('', process.argv[2])).join('\n'))

$ node tree.js .
.
├── data
│   ├── data.txt
│   └── output.txt
├── files.py
├── lists.py
├── recursion.py
├── resources
│   └── README.md
├── tree.py
└── tuples.py

Kotlin script

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import java.io.File

val I_branch = "│   "
val T_branch = "├── "
val L_branch = "└── "
val SPACER   = "    "

data class Entry (val name: String, val children: List<Entry>)

fun children(path: File): List<Entry> {
    return path.listFiles().map {tree(it)}
}

fun tree(path: File): Entry {
    val isDir = path.isDirectory()
    return Entry(path.getName(), if(isDir) children(path) else listOf<Entry>())
}

fun renderTree(tree: Entry): List<String> {
    val name = tree.name
    val children = tree.children

    return listOf(name) + children.mapIndexed { i, e -> prefix(children.size)(i, e) }.fold(listOf<String>()) {l, r -> l + r}
}

fun prefix(size: Int): (Int, Entry) -> List<String> {
    return {index, entry ->
        val isLast = index + 1 == size
        val prefixFirst = if(isLast) L_branch else T_branch
        val prefixRest = if(isLast) SPACER else I_branch
        val subTree = renderTree(entry)

        listOf(prefixFirst + subTree.first()) + subTree.drop(1).map {t -> prefixRest + t}
    } 
}

println(renderTree(tree(File(args[0]))).joinToString("\n"))

$ kotlinc -script tree.kts .
.
├── tree.py
├── files.py
├── lists.py
├── tuples.py
├── resources
│   └── README.md
├── recursion.py
└── data
    ├── output.txt
    └── data.txt

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

import java.io._
val I_branch = "│   "
val T_branch = "├── "
val L_branch = "└── "
val SPACER   = "    "

case class Entry(name: String, children: List[Entry])

def children(path: File): List[Entry] = path.listFiles().toList.map((it: File) => tree(it))

def tree(path: File): Entry = Entry(path.getName(), if(path.isDirectory()) children(path) else List[Entry]())

def prefix(size: Int) = (index: Int, entry: Entry) => {
    val isLast = index + 1 == size
    val prefixFirst = if(isLast) L_branch else T_branch
    val prefixRest = if(isLast) SPACER else I_branch
    val subTree = renderTree(entry)
    List(prefixFirst + subTree.head) ++ subTree.tail.map(t => prefixRest + t)
}

def renderTree(tree: Entry): List[String] = {
    val name = tree.name
    val children = tree.children

    return List(name) ++ children
      .zipWithIndex
      .map({case (e: Entry, i: Int) => prefix(children.size)(i, e)})
      .fold(List[String]())((l, r) => l ++ r)
}

println(renderTree(tree(new File(args(0)))).mkString("\n"))

$ scala tree.scala .
.
├── tree.py
├── files.py
├── lists.py
├── tuples.py
├── resources
│   └── README.md
├── recursion.py
└── data
    ├── output.txt
    └── data.txt

Elixir

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#!/usr/bin/env elixir

defmodule Tree do
  def main([dir | _]) do
    dir |> tree_format |> render_tree |> Enum.join("\n") |> IO.puts
  end

  defp children(path) do
    if (path |> File.dir?) do
      File.ls!(path) |> Enum.map(fn f -> tree_format(path, f) end)
    else
      []
    end
  end

  defp tree_format(parent_dir \\ ".", dir_name) do
    %{:name => dir_name, :children => Path.join(parent_dir, dir_name) |> children}
  end

  defp decorate(is_last?, [parent | children]) do
    prefix_first = (if (is_last?), do: "└── ", else: "├── ")
    prefix_rest = (if (is_last?), do: "    ", else: "│   ")
    [prefix_first <> parent | children |> Enum.map(fn child -> prefix_rest <> child end)]
  end

  defp render_tree(%{name: dir_name, children: children}) do
    [dir_name 
     | children 
     |> Enum.with_index(1)
     |> Enum.map(fn {child, index} -> decorate(length(children) == index, render_tree(child)) end) 
     |> List.flatten]
  end

end

Tree.main(System.argv)

$ elixir tree.exs .
.
├── tree.py
├── files.py
├── lists.py
├── tuples.py
├── resources
│   └── README.md
├── recursion.py
└── data
    ├── output.txt
    └── data.txt