一切都从一颗小树苗开始。小树苗逐渐成长为树干，在其上又长出了许多新芽，在不知不觉间又长成了一颗茂密的参天大树.
在数字世界中也存在着这样一棵树，被称为Merkle Tree. Merkle Tree主要由根，中间节点，叶子结点组成。一棵树可以有大量的叶子结点，但叶节点不再拥有子节点。Merkle Tree用来解决什么问题呢？我们一起看看。

The Basics

一颗Merkle Tree是一个非线性，二叉，基于哈希的树状数据结构。每个叶子节点存储数据的hash值，每个中间节点存储两个子节点hash的hash.使用Merkle Tree的主要优势是数据元素(或整个数据集)的许多重要信息可被验证,而无需访问整个数据集。例如，在无需下载整个数据集的前提下，可以验证一个特定的数据元素是否是一个大数据集的一部分. 由于这些特性，Merkle Tree经常被使用在区块链等基于P2P网络构建并经常会涉及从非信任源获取数据的业态中，因此数据在获取的同时也得到了了验证. 有了Merkle Tree之后，可以避免这样的场景，即在下载完整个数据集之后，发现数据是不可验证的，因而节省了大量的时间与带宽。
区块链平台的场景下，总体来说，用户只需要同步哪些与自己账号相关的数据和事务信息。如果用户想要下载全量数据，效率则会大打折扣。因此，区块链实现了一种被称之为SPV(Simple Pay Verification)的技术。使用这项验证技术，用户可以在只需要极小量数据的前提下构建和验证Merkle Proof。这直接导致对于终端用户只需要极小的存储和带宽需求。
Merkle Tree拥有着丰富的应用场景。其中之一便是生成区块Merkle Tree，其中区块中的transaction是叶子节点。这些记录被用做这些事务确实曾发生在区块链上的证明。这篇文章主要目标是描述Ontology在实现Merkle Tree时是如何做了各种优化的。

Merkle Tree数据结构存储

大部分区块链为不同区块实现以transaction hash为叶子节点的Merkle Tree。然而在Ontology区块链的场景下，随着区块数量的增加区块Merkle Tree在不断地被动态修改，导致了一个比传统范式更复杂的场景。这自然提出了一个问题：如何存储Merkle Tree？让我们看看这个问题的不同答案。

方案一：Cache Storage

这个方案主要是缓存Merkle Tree. 但有两个明确的缺点。第一，缓存意味着树被存储在易失性内存里，当机器关机或重启时，需要重新扫描以构建完整的Merkle Tree，这是一个想对耗时的过程。同时，随着区块高度的增加，树也在不断变大。因此，内存需求在线性增加，这极大影响了扩展性。因此，我们可以很明确地说缓存不是一个长期的最优解。

方案二：KV数据库存储

这个方案主要涉及将Merkle Tree存储在KV数据库中（如LevelDB）. 由于KV的简单性，将树状结构序列化/反序列化为KV的表达方式，是一个绕不开的问题。同时，获取树中一个具体节点需要多次读取操作，这无疑降低了系统的整体效率。

方案三：文件存储

由于Merkle Tree的节点都是定长的hash值，如果我们将hash值与整数形成一个1-1映射，就有可能将整棵树压缩为一个整型数组。对应的整型值先被计算出来，然后将对应节点数据存储在以该整型值为下标的数组元素中。当访问一个具体节点时，先计算出该整型数值，再直接访问该整型值为下标的数组元素。将这个数组存储在文件中可以解决Merkle Tree线性增长的问题。
有许多种将节点映射为整型的方法，最为直接的是基于树深度的逐层序列化。但，这种序列化方式有一个问题。即每次树的大小变化时，一个节点的序列号也会变化。因此，整个数据都需要被解析，序列化，再重新存储。这会极大的影响系统的运行效率。因此，文件存储方案的稳定性极大地依赖于找到一种高效的序列化方法。

Merkle Tree更新和节点序列化Schemes

除了节点序列化，使用文件存储还存在着其他问题。随着区块不断的增加，Merkle Tree的节点被不断修改，因此文件也许不断的更新和重写。这是另一个会导致效率快速降低的因素。
再增加一点难度，可能还需要一个数据一致性的处理机制。考虑这样一个假想的但一定会频繁出现的场景，节点数据被更新了，更新过程处理了一半，突然一个新的区块产生了。这会导致Merkle tree数据文件的不一致。
如果你仔细观察Merkle Tree的插入过程，Merkle Tree中存在着两种节点：临时节点，它的节点hash会随着新节点的插入而变化；稳定节点，那些不会因新节点插入而变化的节点。很容易总结出，一个节点成为稳定节点的前提是它及其子孙节点已经构成了一个完全二叉树。同时，非常明确的是临时节点的数量也是有限的(只有log(n))。临时节点数量可以由稳定节点数量退推导得出，在出入内存之后，会随着新节点的插入而变化。
因此，在Ontology的方案中，只有稳定节点被写进文件中。另一个有趣的巧合是未定节点形成的序列本身是一个稳定的序列化顺序。考虑上面提到的事实，只有一种动作会发生在文件上，那就是append。同时这解决了因重写文件可能会带来的数据一致性问题。

Merkle Tree的压缩形式

由稳定节点性质，可以推出稳定节点的字节点对于Merkle Tree的更新过程不会有任何参与度。因此，对于那些不需要提供证明服务，并且只需要计算最新的Merkle Tree根节点hash值的参与者来说，可以只简单地存储完整Merkle Tree的log(n)数量级的节点数据。这就足以表达整颗Merkle Tree的状态了，因此将需要存储的节点数量缩小到了log(n)级别，这使得可以很方便的用LevelDB的一个Key来存储这些节点。更新Merkle Tree将只需要一次读写操作。数据结构定义如下：

1
2
3
4

type CompactMerkleTree struct {
  hashes []common.Uint256
  treeSize uint32
}

计算Merkle Tree的根Hash

从压缩后的Merkle Tree的定义可以很容易发现，为了获得Merkle tree的根节点hash，存储的不稳定节点的hash array需要从后向前不断解析。算法如下：

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

func (self *CompactMerkleTree) Root() common.Uint256 {
  if (len(self.hashes) == 0) {
    return empty_hash();
  }
  hashes = self.hashes;
  l := len(hashes);
  accum = hashes[l-1]; //从最后一个节点(会参与root hash计算的)开始
  for i:=l - 2; i >= 0; i-- { //从后向前，即使需要计算root hash的顺序，后面的图示中将明确阐释
    accum = hash_children(hashes[i], accum); //计算子节点hash的hash
  }
  return accum;
}

插入新的叶子节点

当新的叶子节点插入时，动态更新依据当前Merkle Tree的状态被执行。具体的算法如下：

1
2
3
4
5
6
7
8
9
10

func (self *CompactMerkleTree) Appen(leaf common.Uint256) {
  size := len(self.hashes);
  for s := self.treeSize; s%2 == 1; s = s >> 1 { //终止条件是再向前都是完全二叉树了(只有有单数才是非完全)；s>>1，每次向上移动一层;
    leaf = hash_children(selft.hashes[s - 1], leaf); //根据新叶子和上一层的左侧兄弟节点计算hash.
    size -= 1;
  }
  self.treeSize += 1;
  self.hashes = self.hashes[0:szie];
  self.hashes = append(self.hashes, leaf);
}

#随着Merkle Tree不断增长,数据变化的示意图
在hash values以及存储文件中压缩存储的数据随Merkle Tree增长而变化的情况展示如下：

第一张图是Merkle Tree只有单一节点的情况

当一个新节点b插入Merkle Tree时，size会+1. 新节点b可以用来与a一起计算出hash值c.

当一个新节点d插入时，由于当前树是完全二叉树, 该节点独立成为一个新子树. 树的size加1

此时，每次有一个新节点插入时，我们都可以通过之前讨论过的算法得到对应的位置和hash值。

总结

Merkle Tree在不同的场景中存在着广泛的应用。在Ontology的场景下，Merkle Tree的一个应用是以叶节点的形式记录每个区块，然后为transactions是否在链上发生过以及是否是这些区块的一部分提供证明。
对于那些不需要提供证明的场景, Merkle Tree可以显著的提升共识节点的性能和存储效率。Ontoloty在实现Merkle Tree时只记录了关键节点。其效果是，我们可以仅通过一次LevelDB读写更新Merkle Tree。时间复杂度被减小到O(logn).
更进一步，当需要提供证明服务时，本文提到的方案可以解决存储文件需要频繁重写的问题，并通过使文件操作只有append一种来简化一致性负担。

文章翻译子

https://medium.com/ontologynetwork/everything-you-need-to-know-about-merkle-trees-82b47da0634a

单元测试是验证代码正确性的重要工具。但 写出好的测试用例却远远不只是关于验证正确性 – 为了保证可读与可维护，一个测试用例还需要拥有其他几项属性。

其中之一，就是 Clarity。

Clarity意味着一个测试用例对于人来说应该是一个可读的文档，用以通过public API描述待测代码的能力。
测试用例不应该依赖于实现细节。一个类的测试用例的名字应该能讲清楚这个类在做什么，并且测试用例也应该作为使用该类的样例。

另外两个重要的属性是完整性(completeness)以及简洁性(conciseness)。 译者注：相比简洁性，高信噪比可能是更合适的描述方式。
只有当测试用例的Body包含了所有用以理解TA的信息时，才能称之为完整的；只有当测试用例不包含任何的多余信息时，才能成指为简洁的。
下面的测试用例在这两个方面都跪下了：

1
2
3
4
5
6

@Test public void shouldPerformAddition() {
  Calculator calculator = new Calculator(new RoundingStrategy(), 
      "unused", ENABLE_COSIN_FEATURE, 0.01, calculusEngine, false);
  int result = calculator.doComputation(makeTestComputation());
  assertEquals(5, result); // Where did this number come from?
}

非常多多余且令人分心的信息被传入了构造函数，且重要的信息被隐藏在了一个helper方法中。测试用例可以通过明确helper方法的目的来增强完整性，可以通过另一个helper方法隐藏构造calculator时不相关的细节来提高简洁性：

1
2
3
4
5

@Test public void shouldPerformAddition() {
  Calculator calculator = newCalculator();
  int result = calculator.doComputation(makeAdditionComputation(2, 3));
  assertEquals(5, result);
}

另一个重要的属性是韧性。一旦写完，一个具备韧性的测试用例，在待测代码的行为和目的没发生变化时，是不需要变化的。增加一个新的行为只需要增加新的测试用例，不用修改老的。上述的第一版测试用例是不具备韧性的，因为只要在构造函数中增加一个新的不想关的参数，就需要更新TA(可能还有其他几十个测试用例)。把这些细节移入helper方法中，可以解决这个问题。

翻译自：

https://testing.googleblog.com/2014/03/testing-on-toilet-what-makes-good-test.html

编程语言给了我们充分的表达力。操作符、条件等概念是非常重要的工具，TA们使得我们可以写出处理范围极其广泛的输入。但，这种灵活性也带来了更多的复杂度，这会导致我们的程序更加难以被理解。
不像业务代码，在测试用例中简单比灵活更加重要。大多数的单元测试都是验证：一个确定的输入，产生一个确定的输出。测试可以通过直接列出输入和输出而不是计算他们，来显著的降低复杂度。不然，测试用例将很容易产生Bug。
我们一起看一个简单例子。下面这个测试用例，看起来是对的吧？

1
2
3
4
5
6

@Test public void shouldNavigateToPhotosPage() {
  String baseUrl = "http://plus.google.com/";
  Navigator nav = new Navigator(baseUrl);
  nav.goToPhotosPage();
  assertEquals(baseUrl + "/u/0/photos", nav.getCurrentUrl());
}

1
2
3
4
5

@Test public void shouldNavigateToPhotosPage() {
  Navigator nav = new Navigator("http://plus.google.com/");
  nav.goToPhotosPage();
  assertEquals("http://plus.google.com//u/0/photos", nav.getCurrentUrl()); // Oops!
}

文章翻译自：

https://testing.googleblog.com/2014/07/testing-on-toilet-dont-put-logic-in.html

不论我们是在写一个单独的单元测试，还是设计一个产品的完整测试流程，退后一步想一想我们的测试在发现代码Bug方面的效率如何都是很有意义的。为了更高效，有3个重要的质量，需要每个测试用例都尽力做到最大化。

Fidelity(可信度)

当待测代码被破坏了，测试用例应该break。
一个高Fidelity的测试用例对于待测代码的缺陷极其敏感的，防止bug偷偷潜入我们的代码中。
通过保证测试用例覆盖了所有通过你代码的路径并包含所有相关的断言，来最大化Fidelity。

Resilience(韧性)

一个测试用例在待测代码没有引入缺陷时，不应该break。
一个具备韧性的测试用例，当且仅当待测代码引入了破坏性修改时，才会失败.
对于代码的重构以及其他的非破坏性修改不应该需要修改测试用例，以降低测试用例的维护成本。
通过测试待测代码明确暴露的接口，以最大化韧性；避免深入到代码的内部实现细节。使用stubs及fakes，而不是mocks；不要验证与相关依赖的交互，除非这交互是你明确要验证的关键部分。一个脆弱的测试用例显然韧性是非常低的。

Precision(精准)

当一个测试用例失败时，一个精准的测试用例会准确的告诉你是哪里引入了缺陷。一个好的单元测试可以准确的告诉你哪一行代码是有问题的。质量较低的测试用例(尤其是大型end-to-end测试)通常是精准度极低的，只告诉你有东西挂了，但没说哪里挂了。
通过保持你的测试尽可能的规模小且专注，可以最大化精准度。选择一个描述性的方法名字，改名字应该充分且准确的表达这个测试用例在验证些什么。对于系统集成测试，在每个边界处验证状态。

综述

上述的3个维度通常是互斥的。写一个高韧性的测试用例是很简单的(比如说一个空的测试用例)，但写一个同时具备较高可信度和较高韧性的测试用例是非常困难的。

在你做设计或是写测试用例时，可以使用上述三个维度作为引导实现的框架

文章翻译自

https://testing.googleblog.com/2014/05/testing-on-toilet-effective-testing.html

当我们在写测试用例时,通过mock来忽略待测代码的依赖看起来是很简单的.

1
2
3
4
5
6
7
8
9
10

public void testCreditCardIsCharged() {
  paymentProcessor = new PaymentProcessor(mockCreditCardServer);
  when(mockCreditCardServer.isServerAvailable()).thenReturn(true);
  when(mockCreditCardServer.beginTransaction()).thenReturn(mockTransactionManager);
  when(mockTransactionManager.getTransaction()).thenReturn(transaction);
  when(mockCreditCardServer.pay(transaction, creditCard, 500)).thenReturn(mockPayment);
  when(mockPayment.isOverMaxBalance()).thenReturn(false);
  paymentProcessor.processPayment(creditCard, Money.dollars(500));
  verify(mockCreditCardServer).pay(transaction, creditCard, 500);
}

然而,不使用mocks有时会使测试用例更简单,也更有效果.

1
2
3
4
5

public void testCreditCardIsCharged() {
  paymentProcessor = new PaymentProcessor(creditCardServer);
  paymentProcessor.processPayment(creditCard, Money.dollars(500));
  assertEquals(500, creditCardServer.getMostRecentCharge(creditCard));
}

过度使用mocks可能会引起诸多问题:

• 测试变得更加难以维护了.当你实现mock逻辑的时候,你是在把代码的实现细节漏进测试的代码里.当业务代码中的实现细节变了的时候,你也需要更新测试用例的mock逻辑以反映最新的状态.测试用例应该尽量少了解代码的实现,且应该专注于测试代码的公有接口.
• 测试对代码正常工作提供的保证是很少的.当你告诉你的mock应该如何表现时,获得的唯一保证是:只有在你的mock与真实实现一致时,才能保证线上的代码是经过验证的.这是非常难以保证的事,并且随着时间的推移会变得越来越难,主要是因为真实实现的行为会逐渐与mock不一致.
  一些迹象可以用以辅助判断”是否过度使用了mock”, 比如当你不只是mock一两个类的时候, 或者是当你的mock需要明确指定”怎么做”而不是”做什么”的时候.

如果你尝试阅读一个使用了mock的测试用例时,发现自己不自主的跳进了待测代才能理解测试用例时, 那么你可能就是过度使用mock了
有时,你没办法在测试中使用一个真实实现(比如,太慢或者需要使用网络),但有比mock更好的选择,比如hermetic server(比如一个信用卡服务,在本机启动,服务于你的测试)或是一个fake实现(例如一个内存版的信用卡服务).
关于hermetic更多的信息,参考http://googletesting.blogspot.com/2012/10/hermetic-servers.html.

Great Q&A

Q1: mocks的问题是复制了一遍业务代码逻辑-立刻违反了DRY原则.必须要使用mocks是一种”code smell”, 通常意味着需要重构了.
A1: Mocks在不包含逻辑,只是为了让你的代码到达指定状态的时候工作的很好(比如,你对于依赖组件返回的list为空有特殊处理时,你可以使用mock来让依赖组件返回空列表,以保证测试可以覆盖到这样的场景). 这本质上是stubs. from coderfengyun Mocks在测交互的时候也表现很好:http://googletesting.blogspot.com/2013/03/testing-on-toilet-testing-state-vs.html, 这本质上类似于spy from coderfengyun

Q2: 单元测试的要点就是你试图只测试功能的一小部分. 一个单元通常被理解为一个类. 然而, 有时这个类用来与文件,数据库,网络,或其他类打交道, 把这些依赖一股脑拉近测试,会是的单元不再明晰. 用mock来处理与其他系统间的交互,是我理解的对于mock比较好的用法. 有一个场景是无法避免使用mock的: 测试与人交互之后代码的行为. 我最近mock了一个对话框服务, 以使得我可以mock用户选择了’yes’或是’no’. 如果你想要去自动化测试与人的交互相关的,mocking是你唯一的选择.
A2: 单元更好的定义是一个独立的类或是一组相关的类. 如果不这么定义,当你把一些util性质的代码从一个类中重构到一个helper类时, 这个helper类就成为了一个独立的单元, 意味着之前只是实现细节的现在成为了你必须要mock的东西, 这也十分容易导致测试用例难以维护.
即使是在用mock来分离独立单元的场景下, mocking有时也会使事情变得极其复杂. 只有在要mock的接口极其简单时,mock才会真正有意义(比如,如果你的代码调用了一个方法,这个方法返回了一个list,你的代码对这个list做了些复杂处理,你可以用mock来返回一个空list,只包含一个元素的list,等等). 但如果有更多更复杂的交互, 需要多个mock来互相操作, 或是需要mock来返回其他mock, 更好的办法是用一个fake, 或是干脆直接用真实实现(如果TA并没有那么的重).

翻译自

https://testing.googleblog.com/2013/05/testing-on-toilet-dont-overuse-mocks.html

写了多年博客之后,你决定自己写一套博客平台的API。你开始写了，但你意识到：如果没有测试对于远程博客服务器的调用，怎么才能说明你的代码没问题呢？

1
2
3
4
5

public void deletePostsWithTag(Tag tag) {
  for (Post post : blogService.getAllPosts()) {
    if (post.getTags().contains(tag)) { blogService.deletePost(post.getId()); }
  }
}

1
2
3
4
5
6
7
8
9
10
11

public class FakeBlogService implements BlogService {  
  private final Set<Post> posts = new HashSet<Post>(); // Store posts in memory
  public void addPost(Post post) { posts.add(post); }
  public void deletePost(int id) {
    for (Post post : posts) {
      if (post.getId() == id) { posts.remove(post); return; }
    }
    throw new PostNotFoundException("No post with ID " + id);
  }
  public Set<Post> getAllPosts() { return posts; }
}

翻译自

https://testing.googleblog.com/2013/06/testing-on-toilet-fake-your-way-to.html

下面的测试mock掉了对CloudService服务的调用。这样的测试能够给我们信心，说：对该服务的调用是正常工作的吗？

1
2
3
4
5
6
7
8
9
10
11

@Test public void uploadFileToCloudStorage() {
  when(mockCloudService.write(
          WriteRequest.newBuilder().setUserId(“testuser”).setFileType(“plain/text”)...))
    .thenReturn(WriteResponse.newBuilder().setUploadId(“uploadId”).build());

  CloudUploader cloudUploader = new CloudUploader(mockCloudService);


  Uri uri = cloudUploader.uploadFile(new File(“/path/to/foo.txt”));
  // The uploaded file URI contains the user ID, file type, and upload ID. (Or does it?)
  assertThat(uri).isEqualTo(new Uri(“/testuser/text/uploadId.txt”));

很多事情可能出错，尤其是当服务契约变得复杂时。例如，plain/text可能并不是一个有效值，同时也没有办法验证上传文件后生成的URI是正确的。
如果待测代码依赖该服务的契约，首选直接调用TA，而不是把这个调用mock掉。这可以给你给你更多自信，相信自己正确的使用了对应的服务：

1
2
3
4
5

@Test public void uploadFileToCloudStorage() {
  CloudUploader cloudUploader = new CloudUploader(cloudService);
  Uri uri = cloudUploader.uploadFile(”/path/to/foo.txt”);
  assertThat(cloudService.retrieveFile(uri)).isEqualTo(readContent(“/path/to/foo.txt));
}

1. 使用一个Fake。一个fake是一个快速且轻量的实现，同时TA还表现的与真实服务一致。fake通常由服务的owner提供；不要创建你自己的fake，除非你可以保证fake的行为能够始终与真是实现保持一致。关于fake，参见：testing.googleblog.com/2013/06/testing-on-toilet-fake-your-way-to.html。
2. 使用一个Hermetic server。这是一个在测试用例中拉起来的真实服务，并且与测试用例跑在同一台机器上。使用hermetic server的一个问题是，启动它以及与它交互会使测试执行变慢。关于hermetic servers，参考testing.googleblog.com/2012/10/hermetic-servers.html。

如果你依赖的服务没有fake或是hermetic server，mock就变成了你唯一的选择。但是如果你的测试用例没有真的验证服务调用契约，你必须使用额外的手段来保证服务调用是没问题的，比如通过一组详尽的end-to-end测试套件，或是依赖手工测试(这是很低效，且很难扩展的)。

翻译自

https://testing.googleblog.com/2018/11/testing-on-toilet-exercise-service-call.html

在Element上增加ID属性可以使TA更容易写跟DOM交互的测试(例如WebDriver测试)。考虑下面的DOM，包含两个按钮，这两个按钮只有文案不同：

在这种情况下，如何告诉WebDriver来跟”Save”按钮交互呢？你有几个选择。一个选择是通过CSS selector来跟按钮交互：

1

div.button

1

//div[@class='button' and text()='Save']

1
2

contact-form.save-button
contact-form.edit-button

1

<tr id="feedback-{{$index}}" class="feedback" ng-repeat="feedback in ctrl.feedbacks" >

翻译自

https://testing.googleblog.com/2014/08/testing-on-toilet-web-testing-made.html

下面这段代码mock了一个第三方类库。这么做会有什么问题呢？

1
2
3
4
5
6
7
8

//Mock a salary payment library
@Mock SalaryProcessor mockSalaryProcessor;
@Mock TransactionStrategy mockTransactionStrategy;
...
when(mockSalaryProcessor.addStrategy()).thenReturn(mockTransactionStrategy);
when(mockSalaryProcessor.paySalary()).thenReturn(TransactionStrategy.SUCCESS);
MyPaymentService myPaymentService = new MyPaymentService(mockSalaryProcessor);
assertThat(myPaymentService.sendPayment()).isEqualTo(PaymentStatus.SUCCESS);

Mocking哪些不属于你的类型将使得维护变得更加困难

• 这可能会使得升级到该类库的新版本更加困难：硬编码在测试里的对于API的假设，可能会出错或是过时。在需要升级的时候，可能需要大量耗时的手工更新这些mock逻辑。在上面的例子中，如果该类库将addStrategy()的返回值修改为TransactionStrategy的一个子类(比如SalaryStrategy)，就需要所有测试中的mock更新到这个类型，尽管待测代码是不需要修改的，因为待测代码仍然可以使用TransactionStrategy。
• 这可能使得判断该类库的更新是否引入Bug变得更加困难。随着三方类库不停迭代，写成mock的假设可能会过时，会使得虽然测试通过但待测代码中存在着Bug。在上面的例子中，如果该类库将paySalary()的反馈值改为TransationStrategy.SCHEDULED，由于待测代码没有正确的处理这个返回值，一个潜在的Bug就产生了。然而，待测代码的维护者无法感知到问题，因为mock没有返回这个值，且测试用例仍然是通过的状态。

与其使用mock，不如使用真实实现，如果真实实现不可行，那么就用一个fake实现，该fake实现需要由类库的作者来提供。这使得维护的成本得以降低，因为上面列出来的mock可能会引入的问题不会在一个真实实现或fake实现中出现。例如：

1
2
3

FakeSalaryProcessor fakeProcessor = new FakeSalaryProcessor(); // Designed for tests
MyPaymentService myPaymentService = new MyPaymentService(fakeProcessor);
assertThat(myPaymentService.sendPayment()).isEqualTo(PaymentStatus.SUCCESS);

如果无法在测试中使用真实实现，而且fake实现也不存在(并且类库的维护者也没有创建一个fake)，创建一个wrapper类来调用类库中的类，然后mock这个wrapper类。这减轻了维护负担，因为测试代码中的mock不再依赖第三方类库的(方法)签名，因此一旦对方签名变化是也不会产生散弹式修改。例如：

1
2
3
4
5
6
7

@Mock MySalaryProcessor mockMySalaryProcessor; // Wraps the SalaryProcessor library
...
// Mock the wrapper class rather than the library itself
when(mockMySalaryProcessor.sendSalary()).thenReturn(PaymentStatus.SUCCESS);

MyPaymentService myPaymentService = new MyPaymentService(mockMySalaryProcessor);
assertThat(myPaymentService.sendPayment()).isEqualTo(PaymentStatus.SUCCESS);

“Don’t mock types you don’t own”也被Steve Freeman和Nat Pryce在他们的书Growing Object Oriented Software, Guided by Tests。关于过度使用mock的缺点(即使是用来mock你自己的类)，可以看看Google Testing Blog的这篇文章。

翻译自

https://testing.googleblog.com/2020/07/testing-on-toilet-dont-mock-types-you.html

本文翻译自：https://prl.ccs.neu.edu/img/p-tr-1971.pdf

摘要

本文主要讨论用以提升系统的灵活性及可理解性，同时缩短开发时间的模块化机制。模块化的有效性依赖于模块划分的范式。后文将以两个系统设计为例，对任何一个，都展示了一个常规划分方式和一个非常规划分方式。同时也阐明非常规的划分方式在指定的目标上具备显著优势。这些划分本身遵循的范式也在本文中得到了讨论。非常规的划分方式，常规划分方式是指一个模块🈶一个或多个子程序组成，在大多数情况下都可能不会发挥应有效力。文章也简单描述了另一种没有这样（负面）影响的实现方式。

简介

如果程序员会唱赞美诗，那么大部分流行的赞美诗将献给模块化编程。作者在一本讲述系统设计的书中找到这么一句关于模块化编程哲学的表述：

在明确定义项目如何分段上的努力使得系统具备模块化特性。每个任务形成了一个独立的程序模块。在实现阶段，每个模块的input和output都被很好的定义了，对于系统其他模块来说都不存在着不明确。在验证的时候，模块是否完整的实现了TA的承诺则被分别测试；验证阶段也不需要协调多个任务的完成时间。最后，系统通过模块化的方式维护；系统错误和依赖可以被追踪到具体的模块，因此缩小了缺陷搜查的范围。

首先，我非常赞同这段陈述，但不太赞同引申而来的一些可能的诠释。注意，关于如何将系统划分为多个模块，上述论述什么也没聊。因为将系统划分为大小适中的模块的决定并不能真的导向解耦，本文会讨论这个问题，并且将通过例子的方式，推荐一种应该被用来将系统划分为模块的范式。

回顾下该领域的现状

在模块化编程领域的主要进展是(1)编码技巧的发展以及(2)编译器在“在编写一个模块时可以不关心其他模块”上的发展，其中(2)使得模块可以独立于整个系统来重新编制和替换。这项便利对于生产大规模代码是极有价值的，但这项技术的使用还没带来预期的收益。事实上，那些经常被用来讲述大规模系统的例子本身就是高度模块化的程序，这些程序使用了上述复杂的编码和编译技术。

模块化编程承诺的优势

模块化编程承诺的优势可以分为如下三类：(1)可管理 – 因为不同组织工作在不同的模块，且极少需要沟通(也不必事后后悔当时为什么没做更充分的沟通)，因此研发时间被大大缩短了；(2)生产的灵活性 – 希望能够做到一个模块发生剧烈变化是可以不影响其他模块；(3)可读性 – 希望整个系统可以被逐个模块的学习，因为更容易理解系统也就会得到更好的设计。

什么是“模块化”

在这个的上下文中，模块最好被理解为一个独立的工作单元而不是一个子程序。模块化想要描述的是在各个模块的工作开始前必须要做的设计决策。尽管在不同的方案中的决策差异极大，但所有方案的(决策)意图都被描述为系统级的决策(例如，那些会影响超过一个模块的决策)。

示例系统1：关键字索引生成系统

对于不了解什么是关键字索引的人来说，下面这段（关于关键字索引）介绍对于理解本文就足够了。关键字索引系统接收一个顺序的文字行的集合，每一行是一个顺序的词的集合，每个词是一个顺序的字母的集合(对于英文)。每一行都可能是”循环移位的”，即，不断地将第一个单词移掉在拼接到行的末尾。这个关键字索引系统以字母序输出每一行的所有循环移位。这是个很小的系统。除非是极端情况(巨大的数据集，没有支持软件)，这样一个系统都可以在1-2周的时间搞定。因此这是个不合适的例子，因为没有任何必要在这样的系统上进行模块化编程。因为细致又完全地分解一个大系统是不实际的，因此我们还是试着把这个问题当做是个大项目吧。我们给出了两种模块化的方式。第一个，我们觉着，是现在比较典型的工程划分办法；另一个是在毕设中成功被应用的划分方法。

模块划分方法一

我们看下面的模块：
Module 1：输入：这个模块包含一个主程序，TA读取输入设备中的数据行，然后存储在core中，以待其他模块的处理。在core中，每四个字符被存储在一个字中，一个未被使用的字符被用来标识一个字的结束。维护了一个索引来展示每行的开始地址。
Module 2：循环移位：这个模块在输入模块结束之后被调用。本模块准备了一个索引，用以给出每个循环移位的开始字符，以及module 1生成的行数组的原始index，而不是将所有循环移位都存在core里，本模块把输出通过一个个的pair存入core中（每个pair由原始行号，开始地址组成）。
Module 3：字母序排序：本模块把module 1和module 2的输出作为输入。本模块产生了一个跟module 2（产生的结果）一样的数组。然后，将其按照字母序排序。
Module 4：输出：使用module 3和module 1输出的数组，本模块输出一个格式化好的输出，该输出列出了所有的循环移位。在一个复杂系统中，每一行的起始点会被标记，指向一行中更多信息的指针会在后续的步骤中被插入进来，每个循环移位的起始可能不是行中的第一个字母，等等。
Module 5：主流程控制：这个模块只关注以一定的顺序把上述四个模块串联起来。TA也可能会处理错误信息，内存分配等等。
很明确，上述的说明并不是一个详尽的文档。在正式工作开始前，还需要提供更多的信息。定义文档应该包含一系列展示核心格式，指针使用规范，调用规范等等。只有当四个模块间的所有接口被确定之后，工作才能真的开始。
这是大部分的模块化编程支持真想要表达的“模块化”。系统被划分成几个相对独立的模块，且模块间接口定义清晰；每一个模块足够小，且足够简单，使得更容易理解以及编码。小范围的实验表明，这几乎是大部分接到这个任务的程序员首选的模块分解方式。图1给出了这个系统的结构图。

模块化方法2

我们看如下的模块：
Module 1：Line Storage：这个模块包含了几个方法，这些方法在图2中给出了精确的定义。通过调用这些方法，可以在最后一行的最后一个单词增加一个字母，开始一个新的单词，或开始新的一行。也可以通过调用其他方法来查找第j行的的第k个单词的第k个字母。本模块的其他方法，可以用来查找行数，一行中的单词数，一个单词的字母数。这个模块的精确定义在图2中。定义的方法在引文[3]中详细阐述了。
Module 2: Input：这个模块从输入设备中读取原始输入，调用Line Storage模块来存储。
Module 3: 循环移位器：这个模块包含了如下几个方法：CSSTUP使得其他的方法又有初始值。其他的方法与模块1中提供的方法信息类似。使用他们，可以得到第i个循环移位的第j个单词的第k个字母，同时也可以获得所有行、单词的长度，等等。这也在图3中展示出来了。
Modeule 4：字母顺序排序器：这个模块主要包含两个方法。第一个，ALPH，必须在另一个方法(ITH)有了初始值之前调用。第二个，ITH，作为一个索引使用。ITH(i)会给出在字母序排序后的第i行在循环移位中的下标。这些方法的正式定义在图4中描述。
Module 5：输出：这个模块提供了任意循环移位需要的打印方式。该模块需要在循环移位方法之后被调用。
Module 6：主控制逻辑：与模块化方式1中的(主控制模块)类似。

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

Figure 2：LineStorage定义
介绍：这份定义描述了一个机制，该机制会容纳p1行，每行包含最多p2个词，每个词包含最多p3个字母。
其中ERLXXX的方法需要由模块的使用者提供。这个调用意味着该用户违背了模块定义的约束；这些方法中需要包含TA自己的恢复逻辑。

Function WORD
	possible values: integers
	initial values: undefined
	parameters: l, w, c all integers
	effect:
		call ERLWEL if l < 1 or l > p1
		call ERLWNL if l > LINES
		call ERLWEW if w < 1 or w > p2
		call ERLWNE if w > WORDS(l)
		call ERLWEC if c < 1 or c > p3
		call ERLWNC if c > CHARS(l, w)

Function SETWRD
	possible values: non
	initial values: not applicable
	parameters: l,w,c,d all integers
	effect:
		call ERLSLE if l < 1 or l > p1
		call ERLSBL if l > 'LINES' + 1
		call ERLSBL if l < 'LINES'
		call ERLSWE if w < 1 or w > p2
		call ERLSBW if w > 'WORDS'(l) + 1
		call ERLSBW if w < 'WORDS'(l)
		call ERLSCE if c < 1 or c > p3
		call ERLSBC if c .noteq. 'CHARS'(l,w)+1
		if l = 'LINES' + 1 then LINES = LINES + 1
		if w = 'WORDS'(l) + 1 then WORDS(l) = w
		CHARS(l, w) = c
		WORD(l,w,c) = d

Function WORDS
	possible values: integers
	initial values: 0
	parameters: l an integer
	effect:
		call ERLWSL if l < 1 or l > p1
		call ERLWSL if l > LINES
		call ERLWSL(MN) if l > LINES

Function LINES
	possible values: integers
	initial value: 0
	parameters: none
	effect: non
	
Function DELWRD
	possible values: none
	initial value: not applicable
	parameters: l,w both integers
	effect: 
		call ERLDLE if l < 1 or l > LINES
		call ERLDWE if w < 1 or w > 'WORDS'(1)
		call ERLDLD if 'WORDS'(l) = 1
		WORDS(l) = 'WORDS'(l) - 1
		for all c WORD(l,v,c) = 'WORD'(l, v+1, c) if v >= w
		for all v > w or v = w CHARS(l, v) = 'CHARS'(l, v+1)

Function DELLINE
	possible values: none
	initial values: not applicable
	parameters: l an integer
	effect:
		call ERLDLL if l < 0 or l > 'LINES'
		LINES = 'LINES' - 1
		if r = 1 or r > 1 then for all w, for all c
					(WORDS(r) = 'WORDS'(r+1)
					 CHARS(r, w) = 'CHARS'(r+1, w)
					 WORD(r, w ,c) = 'WORD'(r+1, w ,c))

Function CHARS
	possible vlaues: integer
	initial value: 0
	parameters: l,w both integers
	effect:
		call ERLCNL if l < 1 or l > LINES
		call ERLCNW if w < 1 or w > WORDS(l)

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

Figure 3 循环移位模块定义
在本定义中，我们假定line holder的方法有值，并且定义一个方法（TA允许我们以各种方式处理lineholder，除了把行的所有循环移位都包含在line holder中）。一个附带的功能是可以把指定行标记为"取消"，尽管他们可以访问。     
Function CSWROD
	possible values: integers
	initial values: undefined
	parameters: l,w,c all integer
	effect:
		call ERCWNL(MN) if l < 1 or l > p4
		call ERCWNL(MN) if l > CSLINES
		call ERCWNW(MN) if w < 1 or w > p2
		call ERCWNC(MN) if c < 1 or c > p3
		call ERCWNC(MN) if c > CSCHARS(l,w)

Function CSWORDS
	possible values: integers
	initial value: 0
	parameters: l an integer
	effect:
		call ERCWNL(MN) if l < 1 or l > p4
		call ERCWNW(MN) if l > CSLINES

Function CSLINES
	possible values: integers
	initial values: 0
	parameters: none
	effect: none

Function CSCHRS
	possible values: integer
	initial value: 0
	parameters: l,w both integers
	effect:
		call ERCCNL(MN) if l < 1 or l > CSLINES
		call ERCCNW(MN) if w < 1 or w > CSWORDS(l)

Function CSSTUP
	possible values: none
	initial value: not applicable
	parameters: none
	effect:
		call ERCNES(MN) if SUM(1,l,'LINES','WORDS'(1)) > p4
		CSLINES = SUM(1, l, 'LINES', 'WORDS'(l))
		let HIP(l) = minimum k such that SUM(1, l, k, 'WORDS'(l)) .> or =.
		let SHI(l) = l - SUM(1, l, HIP(1) - 1, 'WORDS'(l) - 1)
		then for all l such that l .< or =. CSLINES
			CSWORDS(l) = 'WORDS'(HIP(l))
			CSCHARS(l,w) = 'CHARS'(HIP(l), (w+SHI(l))mod 'CHWORDS'(l))
			CSWORD(l,w,c) = 'WORD'(HIP(l), (w+SHI(l))mod 'CSWORDS'(l), c)

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

Figure 4 对于Line Holder做字母序排序
这个模块完成对于上述模块产生的内容进行字母序排序，本模块提供了一个方法ITH，TA给出了第i行在字母序排序后的序列中的下标。

Function ITH
	possible values: integers
	initial values: undefined
	parameters: i an integer
	effect: 
		call ERAIND if value of function undefined for parameter given

Function ALPHC
	possible values: integers
	initial value: ALPHC(l) = index of l in alphabet used
		       ALPHC(l) = infinite if character not in alphabet
		       ALPHC(undefined) = 0
	parameter: l an integer
	effect: 
		call ERAABL if l not in alphabet being used, i.e., if ALPHC(1) = infinite

Mapping Function EQW
	possible values: true, false
	parameters: l1, l2, w1, w2 all integers
	values：EQW(l1, l2, w1, w2) = for all c('WORD'(l1, w1, c) = 'WORD'(l2, w2, c))
	effect：
		call ERAEBL if l1 < 1 or l1 > 'LINES'
		call ERAEBL if l2 < 1 or l2 > 'LINES'
		call ERAEBW if w1 < 1 or w1 > 'WORDS'(l1)
		call ERAEBW if w2 < 1 or w2 > 'WORDS'(l2)

Mapping Function ALPHW
	possible values: true, false
	parameters：l1, l2, w1, w2 all integers
	values: ALPHW(l1, w1, l2, w2) = if !'EQW'(l1, w1, l2, w2) and
		k = min c such that ('WORD'(l1, w1, c) != 'WORD'(l2, w2, c))
		then 'ALPH'('WORD'(l1, w1, k)) < 'ALPHC'('WORD'(l2, w2, k))
		else false;
	effect: 
		call ERAWBL if l1 < 1 or l1 > 'LINES'
		call ERAWBL if l2 < 1 or l2 > 'LINES'
		call ERAWBW if w1 < 1 or w1 > 'WORDS'(l1)
		call ERAWBW if w2 < 1 or w2 > 'WORDS'(l2)

Mapping Function EQL
	possible values: true, false
	parameters: l1, l2 both integers
	values: EQL(l1, l2) = for all k ('EQW'(l1, k, l2, k))
	effect: 
		call ERALEL if l1 < 1 or l1 > 'LINES'
		call ERALEL if l2 < 1 or l2 > 'LINES'

Mapping Function ALPHL
	possible values: true, false
	parameters: l1, l2 both integers
	values: ALPHL(l1, l2) = if !'EQL'(l1, l2) then
		(let k = min c such that 'EQW'(l1, k, l2, k))
		'ALPHW'(l1, k, l2, k) else true
	effect:
		call ERAALB if l1 < 1 or l1 > 'LINES'
		call ERAALB if l2 < 1 or l2 > 'LINES'

Function ALPH
	possible values: none
	initial values: not applicable
	effect:
		for all i >=1 and i <= 'LINES' (
		ITH(i) is given values such that (
			for all j >= 1 and j <= LINES
			there exists a k such that ITH(k) = j
		for i > -1 and i < 'LINES' (that 'ALPHL'(ITH(i), ITH(i+1)))
		)
		)

比较这两个模块化方法

两种方式都是可以工作的，第一个是非常常见的做法；第二个被成功的应用在一个课程项目中了。两种方式都将编程工作分解成了多个相对独立的，小的，可控的程序。我们必须看的更加深入，才能看到我们之前承诺的目标达到了什么程度。
我必须强调在两种分解方式中，我没有修改任何的描述或方法。我的目标就是把原本可能是一个客观实体的内容以两种方式切分开。以第一种分解方式划分的系统在经过编译后可以与第二种分解方式下的系统在功能上是完全相同的。两个以不同方式划分出来的系统的主要区别是，这些模块的定义，工作的划分方式，接口等。在两个系统中用的算法可以是相同的。我想强调的是，即使系统的运行时表现相同，他们也是完全不同的。这可能是因为运行时表示是只用来运行的（面向机器的）；其他的表示则是用来更改，写文档，理解的。在其他的表示中，这两个系统就完全不同了。
(1) Changeability。一些设计决策可能是有问题的，并且在多数情况下很容易改变。一个不完全列表如下：

1. 输入格式。
2. 将所有行存储在内存里的决策。对于大型索引，在同一时间将所有行存储在内存中可能是不方便或完全不可能的。
3. 将四个字母压缩成一个word存储的决策。在处理较小的索引时，可能不需要压缩这些字母，将存储变为一个字母一个word很可能会降低开发/执行时间。甚至有可能，我们会希望以其他格式来压缩存储。
4. 对循环移位做index而不是把所有的循环移位都存储起来，这个决策，也是一样的。再一次，对于一个小索引或一个大内存，直接存储所有循环移位可能是最高效的。
5. 一次性将整个列表排序而不是在需要时查询，或者是类似Hoare’s查找中实现的部分排序，这个决策，也是类似。在一些场景下，将创建索引时排序所需的计算分散开，可能会是比较有利的。

通过观察这些改变，我们可以看到上述两种模块化方式的区别。第一种变化，在两种模块化方式中，都被控制在一个模块中了，但第二种改变会导致第一种模块化方式中所有模块的变更。第三种变化也是同样。在第一种分解方式中，行的存储格式必须被所有模块使用。在第二种分解方式中，故事则完全不同。行存储的确切方式，被完全隐藏起来了，除了module 1没有人需要了解。所有存储方式上的变更，也都只需要改这一个模块。

实际上，在这个系统的多个版本中，分解时还存在着附加的模块。一个符号表被用来实现行的存储模块。这个事实，是真的，也是对系统的其余部分完全不可见。

第四种变化，对于第二种分解方式，只影响循环移位模块；但在第一种划分方式中，排序模块与输出模块也需要了解这个变化。

第五种变化，在第一种分解方式中也是困难的。输出模块会其他索引已经被完全排好序了。第二种分解方式中的排序模块被设计得用户无法发现排序确切是在什么时候进行的。没有其他模块需要变化。
(2) 独立开发。在第一个模块化方式中，各个模块间的接口是比较复杂的，如上面的表格描述的。这些现存的设计决策不容易被轻易的改变。表结构与组织方式关系到多个模块的效率，因此必须被仔细设计。这个部分的开发会成为模块开发的一个重要部分，但该部分还需要多个开发团队的共同协作。在第二种模块化方式中，接口更加抽象，他们只包含方法名和参数的类型和数量。有一些简单的决策和模块的独立开发可以更早开始。

(3) 可读性。为了理解第一种模块化方式中的输出模块，必须要理解排序模块，循环移位模块和输入模块。输出模块使用的表，有许多信息是因为其他模块的工作依赖与此。会因为其他模块使用的算法影响表的结构。整个系统必须要放在一起才能理解。我的主观判断是，在第二种模块化方式中不存在这样的问题。

划分的标准

现在，大多数读者应该明白，每种划分方式使用了怎样的标准了。在第一个划分方式中，标准是将每个“主要步骤”在一个单独模块中处理。也可以说，通过第一种划分方式，得到了一个流程图。图1是一个流程图。这是最常见的划分方式了。这是所有程序员培训的副产品，这些培训教我们先从一个大致的流程图开始，然后再逐步填充实现。当代码量在5000-10000行时，流程图是一种有用的抽象，但一旦超出这个界限，流程图看起来就不够用了；一些额外的标准必须被加进来。
第二种划分方式是以“信息隐藏”为标准划分的。这些模块不再对应于流程中的一个步骤。例如，行存储模块，被系统中的大部分行为使用了。排序可能也可能不对应一流程中的一个阶段，这完全取决于怎么用了。类似的，循环移位在一些场景下，不提前存任何表，完全是在按需计算。第二种分解方式中的每一个模块都是，按照它需要对其他模块隐藏的设计决策，来描述的。TA的接口或是定义会尽量少的展示其内部究竟是如何工作的。

循环移位模块的优化

为了展示划分标准的影响，让我们再仔细看看第二种划分方式中的循环移位模块的定义。后见之明，这个定义中包含了不需要暴露的信息。当我们小心的隐藏存储及计算循环移位列表的具体实现时，我们预示着该列表是有序的。程序可以被高效的写出来，如果我们只说明: (1)循环移位定义中的”lines”都会在”table”中存在，(2)有且只包含一次，(3) 有个方法可以提供这样的能力，即可以根据”shift”得到原始行。通过提前描述循环移位的顺序，我们提供了很多不必要的信息，这些信息反过来制约了我们系统在不改变定义前提下的灵活性。例如，我们没有允许构建这样一个系统，在这个系统中，循环移位以字母序的方式产生，alph是空的，且ITH简单的返回了入参。如果我们使用第二种分解方式构建系统时，这可以非常清晰的被认定为设计失误。

效率和实现

如果我们不小心一点，第二中分解方式将会非常低效。如果每个功能点被实现成了一个需要进行一系列调用的程序，那么将会产生大量跨module频繁切换控制权的调用。第一种分解方式则不受这个问题的影响，因为相对来说模块间控制流的转移不算频繁。
为了在避免程序调用的额外开销的同时还能获得第二种分解方式的好处，我们我们必须采用一种非常规方式来实现这些模块。大多数情况下，常用方法最好是通过汇编器插入到代码中；其他情况下，高度定制且高效的转移需要被单独插入。为了成功且高效的使用第二种解耦方式，需要一个工具，通过这个工具可以实现，方法看起来像实际存在的，但其实现可以在汇编时选择合适的（就是dependency injection）。如果使用这样的技术，模块划分在最终生成的代码中可能是看不出来的。换句话说，程序的另一种表示(前面提到的)必须在”支持映射该展现模式”的机器上运维起来。

第二个例子：一个MARKOV算法翻译器

尽管第一个例子已经展示了本文的大部分观点，再看看其他的例子也会非常有帮助。这是一个要实现Markov算法的翻译器。Markov算法在很多地方都被论述过了；作为编程语言的描述最棒的是Galler and Perlis。对于那些不熟悉的人，Markov算法可以被描述为穷人版SNOBOL。机器上唯一的内存是一个字符串(只要需要就可以随意扩展)。算法通过一系列的规则描述。每个规则包含一个待匹配的规则，和一个用于替换被匹配部分的字符串。顺序性原则标明规则的匹配遵循最左匹配原则（匹配一次则不再匹配）。当替换完成之后，第一个可应用规则仍然有效(例如，对于最后一个规则来说没有内存供匹配了，即到头了)。

常规的模块化方式

对于这种翻译器，有两种常见的模块化方式。他们分别是：

Interpretor

输入模块：读取输入，分析成规则列表，把规则的一种直接表现形式存进主存中。
Intepretor：尝试将每一条规则应用到寄存器上。TA访问存储规则的数据结构，使用对应的pattern来做匹配，如果匹配上了，就替换掉寄存器上对应的部分。
也会有个输出模块，来做对应的打印。

Compiler：

输入模块：读取输入，分析，并将每个句法单元作为参数传给下一个模块，encoder。
Encoder：这个模块包含用于“运行一个规则或部分规则”，并产生对应的机器码程序，例如，TA们对每个pattern分别产生一个机器码程序，这些程序搜索对应pattern出现的位置。这被称为编译代码。
运行时：包含了机器码成需的标准集合，这些程序会被各个算法使用。被编译的程序被链接到这些标准程序上，比如输出方法等等。

一种替代的搞法

我们成功的使用了如下的模块化方式：
规则存储：在主存中存储了规则的一种表示形式。这个模块跟之前说的Line存储有点相近。
规则分析：了解规则的具体含义，例如，知道如何解析存储的规则，以及如何应用这些规则。
寄存器操作：包含了一系列操作寄存器的常用方法。
排序器：选择下一个要被应用的规则。
输入：读取输入，然后调用规则存储及寄存器操作模块，来做内部存储。
输出：对寄存器做必要的打印，以及最好一条规则的应用，等等。

对于第二个例子的讨论

许多关于第一个例子的讨论都可以在这里重复。例如将寄存器操作模块与其他模块分离开，使得修改寄存器的具体展示方式更加容易。规则排序与规则分析的分离，使得更容易尝试其他形式的Markov算法。
我们选择这个例子是为了表明另一个观点。这种模块化方式没有在解释器或编译器上做出决策。我们可以将一个解释型翻译器和一个编译型翻译器相对容易的替换，且我们也可以从二者身上各自选取一些优点。寄存器操作，排序器，输入和输出都可以保持不变。主要的修改都会集中在分析器模块上，假如采用编译器模式那么就将生成的机器码程序存储起来，但如果使用的是解释器模式就在被调用时应用这些规则。在这两种方式中可能存在这大量相同的代码。例如，寄存器操作代码可以在两个版本中都被使用。在编译器方式中，(寄存器操作代码)是运行时程序的一部分；在解释器方式中，会被规则解析模块调用。

层次化结构

我们可以通过Dijkstra提出的分解方式方式找到程序的层次结构。如果一个符号表存在，并且可以不依赖其他模块工作，那么TA在第一层。如果没有用符号表的话，Line存储在第一层；如果用了符号表，则在第二层。输入和循环移位器需要Line存储。输出和排序器需要循环移位器，但由于循环移位器和line holder在某种意义上是兼容的，因此做一个可以用于同时支持排序/输出原始行或者循环移位后的行的程序是比较容易的。在第一种(打印原始行)使用方式中不需要循环移位器；在第二种(打印循环移位后的行)则需要。换句话说，我们的设计允许我们将一种程序运行在两个不同的层次上。
在讨论系统结构的时候，容易混淆好的分解方式的收益和层次化结构的收益。如果模块或程序将可以定义某种关系，且该关系是偏序的，那么我们就拥有了一个层次结构。我们关注的关系主要是”uses”或”depends upon”。如果大多数情况下，一个模块只依赖于有限个其他模块，那么在程序之间有关系是比较好的(例如循环移位器只依赖与line holder的输出部分，与SETWORD则无关)。可以想象，我们可以获得我们讨论过的好处，但不依赖于偏序，比如，所有的模块都在同一层。偏序关系给了我们另外的两个好处。第一，上层系统可以使用下层系统提供的能力。第二，我们可以砍掉上层，仍然可以继续使用下层。例如，符号表可以被用在其他应用中，line holder可以作为一个问答系统的基础部分。层次结构的存在是的我们可以减去树的上层，然后在树干上再开一颗新树。如果我们设计了一个系统，在系统中“底层”模块依赖了上层模块，我们就不具备层次了，我们会发现移除系统中的一部分将非常困难，并且“层次”在系统中也会包含非常杂的信息。
可以想象，如果我们可以通过第一种分解方式来构建系统但保持了层次结构，我们必须得出这样的结论层次化结构和”干净”的分解是两种有意义但相互独立的系统属性。

结论

我们试图通过这些例子说明，通过流程图来做系统分解几乎总是不正确的。我们建议根据一系列困难或易变的设计决策来做分解。每一个模块都被设计以对其他模块隐藏一个决策。因此，在大多数情况下，设计决策是跨越执行时间的，模块可能不会对应到流程上的步骤。为了得到一种高效的实现，我们必须摒弃这种假设(模块是一个或多个子程序)，取而代之，应该允许程序通过将多个不同模块汇编到一起得到。