201801 DDD DSL Design War Semantics of How Many in Python - xiaoxianfaye/Courses GitHub Wiki
- 1 Problem
- 2 Showcase & Discuss
- 3 Analysis
- 4 Design
- 5 Implementation
- 6 Summary
- 7 Homework
编写一个程序，数一数图中有多少个三角形。(How many triangles?)
请学员展示自己之前的设计思路和实现方式，大家可以互相点评、讨论。以学员为主，讲师为辅。
分析：定义清楚问题是什么。
- 数出给定图形中三角形的个数。
- 最终实现的程序肯定不是只能数题面上这个特定图形的三角形个数。
数出给定图形中三角形的个数。这个问题看上去很“简单”，或者说问题本身的描述是很简单的。但需要注意的是，我们最终实现的程序肯定不是只能数题面上这个特定图形的三角形个数。这意味着什么呢？后面就知道了。
设计：问题分析清楚以后，提出解决问题的逻辑框架。
既然是“数三角形”的问题，“三角形(triangle)”和“数(count)”是这个问题领域的核心概念。
这两个概念既是这个问题领域的核心概念，也是最顶层的概念。它们可以由更底层的概念组合产生。
设计的第一步：找到合适的语义。
What is Semantics?
语义，简单来讲，就是我们在解决一个问题的时候，经常问，它到底是什么意思。可能会有很多答案，但是要选一种既能精确清晰地表达出来又能够教给计算机去做的语义。
How to find an appropriate Semantics?
我们在做领域驱动设计时，首先考虑是否能将问题领域映射到一个熟悉的同构领域。如果能，就可以借用那个领域的机制来表达问题领域的概念，而不是重新发明。如果能找到这样一种同构领域，应该是一个最好的结果，如果实在找不到，再自己发明。但一般来说，最终一定能在数学层面上找到一个同构领域，有可能只是没找到而已。
设计的第二步：形式化地表达语义。
语义(Semantics)需要形式化地表达(Formalization)，否则没法可计算化。一旦要表达，就必须选择一种记法，用符号来表达。可能有很多种表达方式，选择的记法一定要是可计算的，可以教给计算机去做的，而且语义层次还要高。注意先不要考虑如何实现。
在这次课程中，我们尝试将这两步合起来一起做。
既然要数三角形，那我们首先要知道，什么是一个三角形？
三个点，两两相连且不在一条线上。
这是关于三角形的一种描述，是我们大脑中的数三角形这个问题领域中的概念，是隐式的。如果要教给计算机去做的话，就要把这个描述变成可计算的。可计算的第一步是形式化。我们要把这个描述显式、精确、清晰地表达出来，虽然现在还不知道怎么实现。
假设三角形有三个点P1、P2和P3，两两相连(connected)，且不在一条线上(not on_a_line)。先不管connected、on_a_line如何实现，先从语义层面来形式化地表达三角形。
可能有很多种表达方式，但一定要选一种可计算的，这样才能教给计算机去做。有时候你找到的表达很好理解，但可能这个表达的层次教给计算机去做还是很困难，这时候就要再想一想，这就是设计过程。然后，选择的表达方式，不仅要可计算，而且语义层次还要高。
假设connected、on_a_line这些primitive的语义都有了，通过这些语义的组合产生了triangle的语义。如果connected、on_a_line已经有人设计好了，我们直接拿来用即可，但因为现在是我们自己实现整个系统，所以我们要继续追问，什么是connected？什么是on_a_line？逐层寻找语义。
“connected”是两点在一条线上，“on_a_line”是三点在一条线上。那么，我们首先要知道，什么是一条线？
先来看一个例子。
箭头左边是问题领域中画的一条线，线的两端是点a和b，看得见但不可计算。箭头右边是用“{a, b}”来表达的由a和b组成的集合。这里的集合就是我们很熟悉的数学领域中的集合，其含义是明确清晰的。
至于这里的集合如何在程序语言里表达和实现，可以先不用考虑。程序语言的表达和实现无非就是对“{a, b}”集合这个概念的解释而已。
再来看一个例子。
同理，箭头左边的问题领域中的一条线可以映射为箭头右边的用“{a, b, c}”来表达的由a、b和c组成的集合。
线(Line)可以映射为点的集合(Set)。
这里需要注意的一点是：数学领域的集合是没有顺序的，“{a, b, c}”和“{a, c, b}”是一样的。但在我们目前的语义域里，需要在数学领域的集合概念上稍微做点约束，“{a, b, c}”和“{a, c, b}”是不一样的。在实现这个语义的时候，要记住这个约束。
以上就是线(Line)的语义和形式化表达。
箭头左边的a和b都是一个点，分别用箭头右边的a和b来表达。
箭头左边的以a和b为端点的线，用箭头右边的“{a, b}”集合来表达。
那么，什么是“Connected”？既然前面选择将问题领域映射到数学领域的集合，那么如何用集合语言来描述这个语义？
先来看一个例子。
如果a和b是Connected的话，那么a和b在一条线上。用集合语言来表达，就是说a和b都属于{a, b}这个集合。
下面我们来做一个数学推导。a属于集合{a, b}，b也属于集合{a, b}，由子集的数学定义可知，由a和b构成的集合{a,b}是集合{a,b}的子集。
再来看一个例子，这个例子可能更明显一些。
数学推导过程同理。a属于集合{a, c, b}，b也属于集合{a, c, b}，由子集的数学定义可知，由a和b构成的集合{a,b}是集合{a, c, b}的子集。
这样，我们就把Connected映射成了子集(Subset)。
用一个集合来表达两个点，用另一个集合来表达线，两点是否Connected就是前者是否是后者的子集。
再进一步(Further More)。
左边的图形中有4条线：{a, c, b}，{a, d}，{c, d}，{b, d}
右边的图形中也有4条线：{a, c}, {c, b}, {b, d}, {d, a}
如何判断a、b两点是否Connected呢？
有一组线(Lines)，用集合语言来表达就是“线的集合”或“点的集合的集合”。如果a和b两点Connected，就是说a和b在Lines中的某一条线上。用集合语言来表达，就是说集合{a, b}是“线的集合”的某一个元素(某一条线)的子集。更纯粹地表达，集合{a, b}是“集合的集合(SetOfSet)”的某一个元素——集合(Set)的子集。
我们给这个语义起一个名字“belong”，表示集合{a, b}“归属于”Lines。
以上就是Connected的语义和形式化表达。
什么是On a Line？
在我们目前的问题领域里，因为是数三角形，On a Line就是指三个点是否在一条线上。
有一组线(Lines)，如果a、b、c三点在一条线上，就是说a、b、c在Lines中的某一条线上。用集合语言来表达，就是说集合{a, b, c}是“线的集合”的某一个元素(某一条线)的子集。更纯粹地表达，集合{a, b, c}是“集合的集合(SetOfSet)”的某一个元素——集合(Set)的子集。
可以使用现成的“belong”来表达这个语义，集合{a, b, c}“归属于”Lines。
以上就是On a Line的语义和形式化表达。
到目前为止，我们解决了“什么是三角形”这个问题。
最开始的形式化表达其实是Wishful Thinking。通过“什么是三角形”，追问“什么是connected”、什么是“on_a_line”，把问题领域映射到数学的集合领域，用集合领域的语言精确地形式化地来表达问题领域的语义。
知道了什么是三角形，接下来看怎么数。
把“数”的过程形式化表达出来。
先来看一个简单的例子。
左图
右图
右边就是把数左边三角形的过程形式化出来的结果。
左边是“数三角形”的问题领域，右边是使用我们自己发明的一套语言对这个问题的形式化表达。
再来看一个稍微复杂一点的例子。
左图
右图
同理，左边是“数三角形”的问题领域，右边是使用我们自己发明的一套语言对这个问题的形式化表达。
在上面的第二个例子中，为什么写了四个断言？还能写出更多的吗？
不能。第二个例子穷举出来就是三个三角形。
Count本质上是什么意思？
以上图为例。有四个点，从四个点中取出三个点，判断是否是三角形——这就是“数”的过程。人在数的时候，图中“a、d、b”其实是判断过的，只不过大脑运转得太快，直接把它忽略掉了，不易觉察，所以一定要把大脑的活动显式地表达出来。
Count可以分为两个步骤：
- 从所有点中选出所有三个点；
- 逐个判断每三个点是否是三角形。
Counting consists of two steps:
- Choose all triple points from all points.
- Determine whether each triple points is triangle one by one.
第2个步骤，前面已经设计出来了。这里我们重点看一下第1个步骤。
“从所有点中选出所有三个点”是一种实现层面的描述方法，是一种低层次的实现语义。这是我们比较习惯的一种思维方式，最终实现出来一定是需要这种思维方式的。但是我们在做设计的时候，特别是希望代码写得比较清晰的时候，要把实现层面的语义放在下面。这个事情到底是个什么事情，要把它表达出来，而且最好是通过另外一个领域，比如数学领域的语言来表达。
把目前的问题形式化表达一下：
目前的问题领域可以映射为数学领域的组合：
这样，我们就把数三角形的问题领域映射到了数学领域的集合语义领域和组合语义领域。我们完全可以用一套数学领域的语言把数三角形的过程形式化表达出来，和实现完全没有关系，非常精确，无二义性，而且是可以实现的。
什么是数三角形？
用数学领域的语言来表达就是：给一些点、一些线，从所有点中取C(Points, 3)的组合，然后判断每三个点是不是三角形(子集、所有线)。
实现：选择实现技术把逻辑框架的软件模型实现出来。
我们选择Python语言实现。
如何用Python语言表达一个点？(How to express a point in Python?)
可以用Python的String表达一个点。
a -> 'a'
b -> 'b'
c -> 'c'
如何用Python语言表达多个点？(How to express multiple points in Python?)
可以用Python的String List表达多个点。
a, b, c -> ['a', 'b', 'c']
如何用Python语言表达一条线？(How to express a line in Python?)
根据设计，线是点的集合，可以用Python的List来表达，List的元素是点对应的String。
还记得之前设计时提到的那个约束吗？
数学领域的集合是没有顺序的，“{a, b, c}”和“{a, c, b}”是一样的。但在我们目前的语义域里，需要在数学领域的集合概念上稍微做点约束，“{a, b, c}”和“{a, c, b}”是不一样的。在实现这个语义的时候，要记住这个约束。
Python的List正好可以满足这个约束。
但List也有个缺点，数学领域的集合是没有重复元素的，而Python的List是可以有重复元素的。如果是开发产品代码的话，可以对List做一个封装，保证List没有重复。
Line {a, b} -> ['a', 'b']
Line {a, c, b} -> ['a', 'c', 'b']
如何用Python语言表达多条线？(How to express multiple lines in Python?)
多条线Lines就是“线的集合”或“点的集合的集合”。也可以用Python的List嵌套List来表达。
Line1 {a, d, b} -> ['a', 'd', 'b']
Line2 {a, c} -> ['a', 'c']
Line3 {b, c} -> ['b', 'c']
Line4 {c, d} -> ['c', 'd']
Lines -> [['a', 'd', 'b'], ['a', 'c'], ['b', 'c'], ['c', 'd']]
实现也应分层：
- 用setop模块来实现集合操作：subset、belong；
- 用combinator(排列组合属于组合数学的范畴)来实现组合操作：combinate；
- 用trianglecounter模块来实现“count”和“triangle”，以及支撑它们的connected和on_a_line。
让用户以String List的形式输入所有点、以List嵌套String List的形式输入所有线，还是不太友好。
例如，下面这个图形：
用户可以这样告诉我们所有点：(Users can tell us all points like this:)
"abcd"
用户可以这样告诉我们所有线：(Users can tell us all lines like this:)
"acb", "ad", "cd", "bd"
这样就需要一个parse的步骤，将用户的输入数据转换成系统内部的数据结构。
根据设计，按以下顺序来实现：
- subset
- belong
- connected
- on_a_line
- triangle
代码路径：HOME
test_all.py
import unittest
from tests.test_setop import TestSetop
if '__name__' == '__main__':
unittest.main()tests.test_setop.py
import unittest
from setop import *
class TestSetop(unittest.TestCase):
def test_subset(self):
s1 = [1, 2]
self.assertTrue(subset([], s1))
self.assertTrue(subset([1], s1))
self.assertTrue(subset([2], s1))
self.assertTrue(subset([1, 2], s1))
s2 = ['a', 'b', 'c']
self.assertTrue(subset([], s2))
self.assertTrue(subset(['a'], s2))
self.assertTrue(subset(['b'], s2))
self.assertTrue(subset(['c'], s2))
self.assertTrue(subset(['a', 'b'], s2))
self.assertTrue(subset(['a', 'c'], s2))
self.assertTrue(subset(['b', 'c'], s2))
self.assertTrue(subset(['a', 'b', 'c'], s2))setop.py
def subset(s1, s2):
return all([ele1 in s2 for ele1 in s1])tests.test_setop.py
def test_belong(self):
sos1 = [[1, 2], [2, 3], [3, 4]]
self.assertTrue(belong([2, 3], sos1))
self.assertFalse(belong([1, 3], sos1))
sos2 = [['a', 'c', 'b'], ['c', 'd']]
self.assertTrue(belong(['a', 'c', 'b'], sos2))
self.assertTrue(belong(['a', 'c'], sos2))
self.assertTrue(belong(['c', 'b'], sos2))
self.assertFalse(belong(['a', 'd'], sos2))
self.assertFalse(belong(['b', 'd'], sos2))setop.py
def belong(s, sos):
return any([subset(s, ele) for ele in sos])test_all.py
from tests.test_trianglecounter import TestTrianglecountertests.test_trianglecounter.py
import unittest
from trianglecounter import *
class TestTrianglecounter(unittest.TestCase):
def test_connected(self):
lines = [['a', 'c', 'b'], ['c', 'd']]
self.assertTrue(connected('a', 'c', lines))
self.assertTrue(connected('c', 'b', lines))
self.assertTrue(connected('c', 'd', lines))
self.assertFalse(connected('a', 'd', lines))
self.assertFalse(connected('b', 'd', lines))trianglecounter.py
from setop import belong
def connected(p1, p2, lines):
return belong([p1, p2], lines)tests.test_trianglecounter.py
def test_on_a_line(self):
lines = [['a', 'c', 'b'], ['c', 'd']]
self.assertTrue(on_a_line('a', 'c', 'b', lines))
self.assertFalse(on_a_line('a', 'c', 'd', lines))
self.assertFalse(on_a_line('b', 'c', 'd', lines))trianglecounter.py
def on_a_line(p1, p2, p3, lines):
return belong([p1, p2, p3], lines)tests.test_trianglecounter.py
def test_triangle(self):
lines = [['a', 'c', 'b'], ['c', 'd'], ['a', 'd'], ['b', 'd']]
self.assertTrue(triangle('a', 'c', 'd', lines))
self.assertTrue(triangle('b', 'c', 'd', lines))
self.assertTrue(triangle('a', 'b', 'd', lines))
self.assertFalse(triangle('a', 'c', 'b', lines))trianglecounter.py
def triangle(p1, p2, p3, lines):
return connected(p1, p2, lines) and \
connected(p2, p3, lines) and \
connected(p1, p3, lines) and \
(not on_a_line(p1, p2, p3, lines))根据设计，按以下顺序来实现：
- combinate
- count
Python的itertools库的combinations()函数可用于求组合。itertools.combinations()函数返回一个嵌套Tuple，需要转成嵌套List。
test_all.py
from tests.test_combinator import TestCombinatortests.test_combinator.py
import unittest
from combinator import *
class TestCombinator(unittest.TestCase):
def test_combinate(self):
s = [1, 2, 3, 4]
self.assertEquals([[1], [2], [3], [4]], combinate(s, 1))
self.assertEquals([[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], combinate(s, 2))
self.assertEquals([[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]], combinate(s, 3))
self.assertEquals([[1, 2, 3, 4]], combinate(s, 4))
self.assertEquals([['a', 'b', 'c'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd']],
combinate(['a', 'b', 'c', 'd'], 3))combinator.py
from itertools import combinations
def combinate(s, n):
return [list(ele) for ele in combinations(s, n)]也可以按以下思路尝试自己写一个combinate的实现。
组合数的计算公式为：C(n, k) = C(n-1, k-1) + C(n-1, k)。
来看一下该式的意义。
C(n, k)是n中选k的组合总数。因此，上式可以用以下文字来描述。
“n中选k的组合数”等于“n-1中选k-1的组合数”加上“n-1中选k的组合数”。
n和k有点抽象？举个具体的例子。我们假设n=5，k=3，“5中选3的组合数”等于“4中选2的组合数”加上“4中选3的组合数”。
还是比较抽象？再举个更具体的例子。我们假设现在有“A、B、C、D、E”5张牌，“从这5张牌中选3张的组合数”等于“包含A的组合数”加上 “不包含A的组合数”。
5张牌中选3张时，选出的3张牌要么是“包含A的3张”，要么是“不包含A的3张”。通过是否包含A来兼顾完整性和排他性，由于没有重复，所以可以使用加法法则。
如何求出“包含A的组合数”呢？由于A是既定的，因此剩下的就是从除A以外的4张牌中选出2张就行了，即4中选2的组合总数。
如何求出“不包含A的组合数”呢？必须从A以外的4张牌中选出3张，即4中选3的组合总数。
再从具体的例子中抽象一下：
C(n, k) = C(n-1, k-1) + C(n-1, k)
在该式中，根据是否包含某张特定的牌，可将从n张牌中取出k张的情况分为两种：
- 选择特定的牌，从剩余的n-1张中选择k-1张的组合；
- 不选择特定的牌，从剩余的n-1张中选择k张的组合。
再举一个例子，从集合{a, b, c, d, e}任取3个元素。
分为“有a”和“无a”两种情况。
- “有a”
从剩下的{b, c, d, e}中选取2个元素：
{{b, c}, {b, d}, {b, e}, {c, d}, {c, e}, {d, e}}
再把a和这些集合分别合并：
{{a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}}
- “无a”
从剩下的{b, c, d, e}中选取3个元素：
{{b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}}
再把两种情况的结果合并：
{{a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e},
{b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}}
tests.test_combinator.py
def test_combinate2(self):
s = [1, 2, 3, 4]
self.assertEquals([[1], [2], [3], [4]], combinate2(s, 1))
self.assertEquals([[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], combinate2(s, 2))
self.assertEquals([[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]], combinate2(s, 3))
self.assertEquals([[1, 2, 3, 4]], combinate2(s, 4))
self.assertEquals([['a', 'b', 'c'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd']],
combinate2(['a', 'b', 'c', 'd'], 3))combinator.py
def combinate2(s, n):
if n == 1:
return [[ele] for ele in s]
if n == len(s):
return [s]
comb1 = [[s[0]] + ele for ele in combinate2(s[1:], n - 1)]
comb2 = combinate2(s[1:], n)
return comb1 + comb2tests.test_trianglecounter.py
def test_inner_count(self):
self.assertEquals(3, inner_count(['a', 'b', 'c', 'd'],
[['a', 'c', 'b'],['a', 'd'], ['c', 'd'], ['b', 'd']]))trianglecounter.py
from combinator import combinate
def inner_count(points, lines):
return len([triplepoints for triplepoints in combinate(points, 3)
if triangle(triplepoints[0], triplepoints[1], triplepoints[2], lines)])tests.test_trianglecounter.py
def test_parse_points(self):
self.assertEquals(['a', 'b', 'c', 'd'], parse_points("abcd"))
def test_parseLines(self):
self.assertEquals([['a', 'c', 'b'], ['a', 'd'], ['c', 'd'], ['b', 'd']],
parse_lines(["acb", "ad", "cd", "bd"]))trianglecounter.py
def parse_points(points):
return [point for point in points]
def parse_lines(lines):
return [parse_points(line) for line in lines]再回到最开始的题目，我们给题目中的图形做上标记。
tests.test_trianglecounter.py
def test_count(self):
self.assertEquals(24, count("abcdefghijk", ["abc", "adef", "aghi", "ajk", "bdgj", "cehj", "cfik"]))trianglecounter.py
def count(points, lines):
return inner_count(parse_points(points), parse_lines(lines))
可以看到把问题领域映射到数学领域、把数学领域映射到实现语言(Java)，两级映射很清晰，映射关系很重要，层次很重要。
第一步是把问题领域中的点、线映射到数学领域中的集合，把问题领域中的Connected、On A Line映射到数学领域中的子集，把Count中的步骤一映射成数学领域中的组合。
第二步是把数学领域中的集合映射成实现语言中的List，把数学领域中的集合映射成subset函数，把数学领域中的组合映射成combinate函数。
我们希望在做设计、编程的时候，显式地表达语义和语义层次，并且保留清楚，不能把它们模糊掉。一旦模糊掉，做再多的工作(代码行数再短、圈复杂度再小、应用再多的设计模式和设计原则)也于事无补，设计已经模糊掉了。
语义和语义层次是否还在——这是我们在软件设计开发过程中，代码质量不腐化的根本所在。
任何可计算的东西都是个数学问题。这就是我们希望最好找到一个数学领域来表达语义的原因，因为问题可计算一定是一个数学问题。
Design = semantics + computation
“可计算”(computation)加上“语义”(semantics)是设计(design)的核心活动。
代码包路径：fayelab.ddd.trianglecounter.original
设计就是把问题变成可计算的。
在这道题目里，这一点应该感受很深刻。
设计出的计算模型所提供的语义和问题领域的根本需求是否匹配，匹配就是好的设计，不匹配就是不好的设计。
在这道题目里，什么是抽象？
用集合来表达点和线，用子集来表达Connected和On A Line，用组合来表达Count，这就是数三角形问题的抽象。抽象就是说我们要发明一套语义来更加精确的描述问题，语义层次和问题相匹配，这是抽象的核心。
- 对问题领域进行深入分析，发现问题领域的核心需求；
- 通过核心需求驱动出计算模型和语义；
- 再围绕这个计算模型提供一套语言，给外面的人使用这个计算模型提供一个接口，这个接口可以是API、可以是数据表达、也可以是语言；
- 最终要实现这个计算模型，实现的方法有解释器和编译器两种。
这就是DDD！这才是DDD！
这就是DSL！这才是DSL！
| “编程”不过是在某个计算模型上用某种语言去表达计算。 | 用DSL编程不过是在问题领域的计算模型上用DSL来表达计算。 |
| 计算模型是相应领域中的“通用机器”。 | 问题领域的计算模型是问题领域的通用机器。 |
| 编程语言不过是描述计算机器的一种方法。 | DSL描述的是DSL语言的计算机器。 |
| 程序是对特定机器的描述，这个特定机器可以被通用机器仿真。 | 用DSL程序实现了问题领域中的某个功能，这个DSL程序就是对这个功能(特定机器)的描述。 |
- 从问题领域导出核心需求，得到领域的计算模型(通用计算机器)，在上面可以包装一个DSL语言或者数据或者API，基于这些开发程序和应用。
- 领域的计算模型和通用语言的计算模型之间存在鸿沟，可以用解释器或者编译器来填补。
- 解释器和编译器听起来很复杂，其实思想很简单，而且我们没有必要实现一个工业级别的、非常全面的解释器和编译器，只要借鉴这个思想实现我们的计算模型就够了。
Common Languages(Java/C) UML对应Java/C/Python通用语言。
Common Languages(Java/C) UM对应Java/C/Python通用语言提供的计算模型(通用计算机器)。
提升设计能力的根本在于提升计算模型构造和语义定义能力。
Thinking, thinking, thinking …
Practice, practice and practice …
No shortcuts.
数一数图中有多少个三角形。(How many triangles?)
我们给题目中的图形做上标记。
tests.test_trianglecounter.py
def test_count_2(self):
self.assertEquals(72, count("abcdefghijklmnopqrstu", ["abcd", "agmnps", "ahkqrt", "aiju", "defghi",
"donlkj", "dstu", "uqlmfb", "urpoec"]))