201706 DDD DSL Design War GCD & LCM of Natural Numbers - xiaoxianfaye/Courses GitHub Wiki
- 1 Problem
- 2 Showcase & Discuss
- 3 Analysis
-
4 Design
- 4.1 Computing
- 4.2 Core Concepts
- 4.3 Semantics and Formalization
- 4.3.1 Unified Process
- 4.3.2 Specification
- 4.4 Summary
- 5 Implementation
- 6 Summary
- 7 Homework
- 8 Code
求任意n个自然数的最大公因数和最小公倍数。这个题目来自于小学四年级奥数。
数学求解步骤是：
- 将n个自然数逐个分解质因数；
- 从这n个自然数的质因数中取出共同质因数，将这些质因数的最小次幂运算的结果乘起来得到这n个自然数的最大公因数；
- 从这n个自然数的质因数中取出所有不重复的质因数，将这些质因数的最大次幂运算的结果乘起来得到这n个自然数的最小公倍数。
请学员展示自己之前的设计思路和实现方式，大家可以互相点评、讨论。以学员为主，讲师为辅。
分析：定义清楚问题是什么。
这个问题本身不复杂，把数学求解过程整理清楚了，这个问题就分析清楚了。
下面以三个自然数“90、420、9450”为例，求出它们的最大公因数(GCD: Greatest Common Divisor)和最小公倍数(LCM: Least Common Multiple)。
- 将n个自然数逐个分解质因数
90 = 2*3*3*5 = 2*(3^2)*5
420 = 2*2*3*5*7 = (2^2)*3*5*7
9450 = 2*3*3*3*5*5*7 = 2*(3^3)*(5^2)*7
^表示幂，例如，3^2表示3的2次幂
采用短除法分解质因数。
以“90”为例，90除以2得到45, 45再除以3得到15, 15再除以3得到5, 5是质数，无法再分解。所有的除数和最后的商就是90的质因数。
2|90
3|45
3|15
5
90 = 2*3*3*5
- 求最大公因数 (GCD: Greatest Common Divisor)
从这n个自然数的质因数中取出共同质因数，将这些质因数的最小次幂运算的结果乘起来得到这n个自然数的最大公因数
在这个例子中，共有2、3、5、7四个不重复的质因数。2是共同质因数，最小次幂是1。3是共同质因数，最小次幂是1。5是共同质因数，最小次幂是1。7不是共同质因数。所以三个自然数“90、420、9450”的最大公因数为：
(2^1) * (3^1) * (5^1) = 30
- 求最小公倍数 (LCM: Least Common Multiple)
从这n个自然数的质因数中取出所有不重复的质因数，将这些质因数的最大次幂运算的结果乘起来得到这n个自然数的最小公倍数。
在这个例子中，一共有2、3、5、7四个不重复的质因数。2的最大次幂是2, 3的最大次幂是3，5的最大次幂是2, 7的最大次幂是1。所以三个自然数“90、420、9450”的最小公倍数为：
(2^2) * (3^3) * (5^2) * (7^1) = 18900
设计：问题分析清楚以后，提出解决问题的逻辑框架。
设计就是把问题变成可计算的。这个问题的可计算化比较简单。输入一组自然数，输出它们的最大公因数或/和最小公倍数。“或/和”在这里并不重要，先“或”，再“和”也很容易。
形式化地表达如下：
gcd: [number] -> gcd
lcm: [number] -> lcm
[]: list, number: natural number,
gcd: greatest common divisor, lcm: least common multiple
仍以三个自然数“90、420、9450”为例：
gcd: [90, 420, 9450] -> 30
lcm: [90, 420, 9450] -> 18900
核心概念包括：
- Prime factor (质因数)
- Operations around the prime factor (围绕质因数有以下操作)：
- Prime factorize (质因数分解)
- GCD
- Extract common prime factors (提取共同质因数)
- Product of minimum power operation on common prime factors (求共同质因数的最小次幂运算结果的乘积)
- LCM
- Extract all non-repetitive prime factors (提取所有不重复的质因数)
- Product of maximum power operation on all non-repetitive prime factors (求所有不重复的质因数的最大次幂运算结果的乘积)
设计或者说建模，一般分为两个步骤：
- 找到合适的同构语义领域；
- 用同构语义领域的语言精确地形式化地表达语义。
我们在做领域驱动设计时，首先考虑是否能将问题领域映射到一个熟悉的同构领域。如果能，就可以借用那个领域的机制来表达问题领域的概念，而不是重新发明。如果能找到这样一种同构领域，应该是一个最好的结果，如果实在找不到，再自己发明。但一般来说，最终一定能在数学层面上找到一个同构领域，有可能只是没找到而已。
语义(Semantics)需要形式化地表达(Formalize)，否则没法可计算化。一旦要表达，就必须选择一种记法，用符号来表达。可能有很多种表达方式，选择的记法一定要是可计算的，可以教给计算机去做的，而且语义层次还要高。注意先不要考虑如何实现。
深入思考一下，求最大公因数和求最小公倍数的过程是可以统一的。
统一过程可形式化地表达如下：
unified_proc: (gcd|lcm, [number]) -> result
( , ) ->: input parameters, |: optional, []: list, result: gcd or lcm
Main Steps of Unified Process (统一过程的主要步骤)：
- Prime factorize (质因数分解)
- Extract prime factors according to the specification (按规格说明提取质因数)
- Extract powers of the extracted prime factors according to the specification (按规格说明提取这些质因数的幂)
- Product of power results (做幂运算并求乘积)
统一过程中的某些步骤需要按照规格说明执行。
目前，规格说明主要涉及到两处：提取质因数和幂运算，可形式化地表达如下：
{
gcd: {extract_pf: common, extract_power: min}
lcm: {extract_pf: all_np, extract_power: max}
}
{key: value}: key mapping value
pf: prime factor, all_np: all non-repetitive
接下来对统一过程的主要步骤逐一进行设计。
在执行统一过程的主要步骤之前，首先要从总的规格说明中根据输入是gcd还是lcm提取相应的规格说明项，作为后续步骤的输入参数。
形式化地表达如下：
extract_spec_items: (gcd|lcm, spec) ->
{extract_pf_spec_item, extract_power_spec_item}
{}: tuple
质因数分解本身是一个很基本的数学领域问题，不用再映射到其他数学领域了。
回顾前面描述的“短除法”。
人脑对90进行质因数分解：90除以2得到45, 45再除以3得到15, 15再除以3得到5, 5是质数，无法再分解。所有的除数和最后的商就是90的质因数。
让计算机对90进行质因数分解：从最小的质数2开始尝试整除，90可以被2整除得到45，分解出第一个质因数2。但接下来，计算机不会像人脑一样一下子跳到质因数3，它还是要从最小的质数2开始尝试整除，45不能被2整除，尝试下一个质数3，45可以被3整除得到15，分解出第二个质因数3，……，直到整除的商为1。
其实人脑也是这么计算的，只不过人脑运转得太快了，不容易感觉到。
这里有一个问题需要仔细考虑，如何表达对一个自然数进行质因数分解后的结果？
一般情况下，一个自然数会被分解成多个质因数。以“90”为例，质因数分解的结果可以表达为：
90 => [2, 3, 3, 5]
根据前面描述的数学求解过程，为了方便后续计算，质因数分解的结果可以进一步表达为：
90 => (2, 3^2, 5) => ({2, 1}, {3, 2}, {5, 1})
(): set
一个自然数的质因数分解，可以形式化地表达如下：
prime_factorize: number -> ({pf, p})
pf: prime factor, p: power
根据前面描述的数学求解过程，为了方便后续计算，n个自然数的质因数分解结果，可以形式化地表达如下：
prime_factorize_list: [number] -> {[(pf)], [({pf, p})]}
这里的输出包括两个部分：质因数集合的列表、由质因数和幂构成的元组的集合的列表。
仍以三个自然数“90、420、9450”为例：
prime_factorize_list: [90, 420, 9450] -> {
[(2, 3, 5), (2, 3, 5, 7), (2, 3, 5, 7)],
[({2, 1}, {3, 2}, {5, 1}),
({2, 2}, {3, 1}, {5, 1}, {7, 1}),
({2, 1}, {3, 3}, {5, 2}, {7, 1})]
}
按规格说明提取质因数，可形式化地表达如下：
extract_prime_factors: (common|all_nonrepetitive, [(pf)]) -> (pf)
从这n个自然数的质因数中取出共同质因数，可以映射为数学领域的求数学集合的交集。
求数学集合的交集，可形式化地表达如下：
intersect: [(pf)] -> (pf)
从这n个自然数的质因数中取出所有不重复的质因数，可以映射为数学领域的求数学集合的并集。
求数学集合的并集，可形式化地表达如下：
union: [(pf)] -> (pf)
这样，我们就把问题领域的提取共同质因数和所有非不重复的质因数映射到了数学领域的求数学集合交集和并集的语义领域。
第二步质因数分解的输出包括两个部分：质因数集合的列表、由质因数和幂构成的元组的集合的列表，即{[(pf)], [({pf, p})]}。
第三步提取质因数的输出是满足规格说明的质因数集合，即(pf)。
从由质因数和幂构成的元组的集合的列表中取出每个质因数的幂列表，根据规格说明求最小次幂或最大次幂，最终输出一个列表，列表中的每个元素是质因数和它的最小次幂或最大次幂。
形式化的表达如下：
extract_powers: ((pf), [({pf, p})]) -> [{pf, mp}]
mp: mininum or maximum of the powers
第四步提取幂的输出是一个列表，列表的每个元素由质因数和它的幂组成，作为这一步的输入，输出是一个数。
形式化地表达如下：
product_powers: [{pf, p}] -> result
实现：选择实现技术把逻辑框架的软件模型实现出来。
这里选用Erlang语言实现并详细讲解实现过程。其他语言的实现过程是一样的，只是落实到实现语言层面的语言细节略有不同。
定义一下规格说明。
%% Specification
spec() ->
[
{gcd, [{extraction_type_pf, common}, {extraction_type_power, min}]},
{lcm, [{extraction_type_pf, all_np}, {extraction_type_power, max}]}
].接下来实现统一过程。
先把统一过程的框架写出来，再逐一实现框架中的具体步骤。
%% Unified Process
unified_proc(SolutionType, Ns) ->
{ExtractionTypePf, ExtractionTypePower} = extract_spec_items(SolutionType, spec()),
{ListOfPfs, ListOfPfPs} = prime_factorize_list(Ns),
Pfs = extract_prime_factors(ExtractionTypePf, ListOfPfs),
PfPs = extract_powers(ExtractionTypePower, Pfs, ListOfPfPs),
product_powers(PfPs).% Extract Specification Items
extract_spec_items(SpecKey, Spec) ->
{_, SpecItems} = lists:keyfind(SpecKey, 1, Spec),
{_, ExtractPfSpecItem} = lists:keyfind(extract_pf, 1, SpecItems),
{_, ExtractPowerSpecItem} = lists:keyfind(extract_power, 1, SpecItems),
{ExtractPfSpecItem, ExtractPowerSpecItem}.
test_extract_spec_items() ->
{common, min} = extract_spec_items(gcd, spec()),
{all_np, max} = extract_spec_items(lcm, spec()),
test_extract_spec_items_ok.在Erlang中，没有**集合(set)**这种数据结构，在这里可以用List，可以满足语义要求。
% Prime Factorize
prime_factorize_list(Ns) ->
ListOfPfPs = [prime_factorize(N) || N <- Ns],
ListOfPfsAndPs = [lists:unzip(PfPs) || PfPs <- ListOfPfPs],
{ListOfPfs, _} = lists:unzip(ListOfPfsAndPs),
{ListOfPfs, ListOfPfPs}.
prime_factorize(N) ->
prime_factorize(N, 2, []).
prime_factorize(1, _C, PfPs) ->
lists:reverse(PfPs);
prime_factorize(N, C, PfPs) ->
case is_prime(C) andalso is_factor(C, N) of
true ->
NewPfPs = acc_prime_factors(C, PfPs),
prime_factorize(N div C, 2, NewPfPs);
false ->
prime_factorize(N, C + 1, PfPs)
end.
acc_prime_factors(Pf, PfPs) ->
case lists:keyfind(Pf, 1, PfPs) of
false ->
[{Pf, 1} | PfPs];
{Pf, P} ->
lists:keyreplace(Pf, 1, PfPs, {Pf, P + 1})
end.
%% Math Operations
is_prime(N) ->
lists:all(fun(I) -> N rem I =/= 0 end, lists:seq(2, N - 1)).
is_factor(N1, N2) ->
N2 rem N1 =:= 0.
% Math Operation Tests
test_is_prime() ->
true = is_prime(2),
true = is_prime(3),
false = is_prime(4),
true = is_prime(5),
test_is_prime_ok.
test_is_factor() ->
true = is_factor(1, 3),
false = is_factor(2, 3),
true = is_factor(3, 3),
true = is_factor(2, 6),
test_is_factor_ok.
% GCD and LCM Tests
test_prime_factorize() ->
[{2, 1}] = prime_factorize(2),
[{2, 1}, {3, 1}] = prime_factorize(6),
[{2, 1}, {3, 2}, {5, 1}] = prime_factorize(90),
[{2, 2}, {3, 1}, {5, 1}, {7, 1}] = prime_factorize(420),
[{2, 1}, {3, 3}, {5, 2}, {7, 1}] = prime_factorize(9450),
test_prime_factorize_ok.
test_prime_factorize_list() ->
{[[2, 3, 5], [2, 3, 5, 7], [2, 3, 5, 7]],
[[{2, 1}, {3, 2}, {5, 1}],
[{2, 2}, {3, 1}, {5, 1}, {7, 1}],
[{2, 1}, {3, 3}, {5, 2}, {7, 1}]]
} = prime_factorize_list([90, 420, 9450]),
test_prime_factorize_list_ok.Erlang没有专门的集合操作的工具库，需要我们打造自己的工具箱。
% Extract Prime Factors According to the Specification
extract_prime_factors(common, ListOfPfs) ->
intersect(ListOfPfs);
extract_prime_factors(all_np, ListOfPfs) ->
union(ListOfPfs).
%% Set Operations
intersect(Ss) ->
if
Ss =:= [] ->
[];
length(Ss) =:= 1 ->
[];
true ->
[H|T] = Ss,
lists:foldl(fun(S, Acc) -> intersect(S, Acc) end, H, T)
end.
union(Ss) ->
if
Ss =:= [] ->
[];
length(Ss) =:= 1 ->
[H|_T] = Ss,
H;
true ->
[H|T] = Ss,
lists:foldl(fun(S, Acc) -> union(S, Acc) end, H, T)
end.
intersect([], _S2) ->
[];
intersect([H1|T1], S2) ->
case lists:member(H1, S2) of
true ->
[H1|intersect(T1, S2)];
false ->
intersect(T1, S2)
end.
union([], S2) ->
lists:sort(lists:reverse(S2));
union([H1|T1], S2) ->
case lists:member(H1, S2) of
false ->
union(T1, [H1|S2]);
true ->
union(T1, S2)
end.
% Set Operation Tests
test_intersect() ->
[] = intersect([], []),
[] = intersect([1], []),
[] = intersect([], [1]),
[2, 3] = intersect([1, 2, 3, 5], [2, 3, 4]),
[] = intersect([1, 2, 3], [4, 5]),
[] = intersect([]),
[] = intersect([[1]]),
[2, 3] = intersect([[1, 2, 3, 5], [2, 3, 4]]),
[] = intersect([[1, 2, 3], [4, 5]]),
[3, 4] = intersect([[1, 2, 3, 4], [3, 4, 5], [3, 4, 5, 6]]),
test_intersect_ok.
test_union() ->
[] = union([], []),
[1] = union([1], []),
[1] = union([], [1]),
[1, 2, 3, 4] = union([1, 3], [2, 4]),
[1, 2, 3, 4] = union([1, 2, 3], [3, 4]),
[1, 2, 3, 4, 5] = union([1, 2, 3], [2, 3, 4, 5]),
[] = union([]),
[1] = union([[1]]),
[1, 2, 3, 4] = union([[1, 3], [2, 4]]),
[1, 2, 3, 4] = union([[1, 2, 3], [3, 4]]),
[1, 2, 3, 4, 5] = union([[1, 2, 3], [2, 3, 4, 5]]),
[1, 2, 3, 4, 5, 6] = union([[1, 2, 3], [3, 4], [4, 5, 6]]),
test_union_ok.
% GCD and LCM Tests
test_extract_prime_factors() ->
[2, 3, 5] = extract_prime_factors(common, [[2, 3, 5], [2, 3, 5, 7], [2, 3, 5, 7]]),
[2, 3, 5, 7] = extract_prime_factors(all_np, [[2, 3, 5], [2, 3, 5, 7], [2, 3, 5, 7]]),
test_extract_prime_factors_ok.% Extract Powers of the Extracted Prime Factors According to the Specification
extract_powers(ExtractionTypePower, Pfs, ListOfPfPs) ->
[{Pf, extract_power(ExtractionTypePower, extract_pf_powers(Pf, ListOfPfPs))} || Pf <- Pfs].
extract_pf_powers(Pf, ListOfPfPs) ->
[extract_pf_power(Pf, PfPs) || PfPs <- ListOfPfPs].
extract_pf_power(Pf, PfPs) ->
case lists:keyfind(Pf, 1, PfPs) of
{Pf, P} -> P;
false -> 0
end.
extract_power(min, Ps) -> lists:min(Ps);
extract_power(max, Ps) -> lists:max(Ps).
test_extract_powers() ->
Pfs = [2, 3, 5],
ListOfPfPs = [[{2, 1}, {3, 2}, {5, 1}],
[{2, 2}, {3, 1}, {5, 1}, {7, 1}],
[{2, 1}, {3, 3}, {5, 2}, {7, 1}]],
[{2, 1}, {3, 1}, {5, 1}] = extract_powers(min, Pfs, ListOfPfPs),
[{2, 2}, {3, 3}, {5, 2}] = extract_powers(max, Pfs, ListOfPfPs),
test_extract_powers_ok.% Product of Power Results
product_powers(PfPs) ->
lists:foldl(fun({Pf, P}, Acc) -> pow(Pf, P) * Acc end, 1, PfPs).
% Math Operations
pow(_N, 0) ->
1;
pow(N, P) ->
lists:foldl(fun(_I, Acc) -> N * Acc end, 1, lists:seq(1, P)).
% Math Operation Tests
test_pow() ->
1 = pow(1, 0),
8 = pow(2, 3),
test_pow_ok.
% GCD and LCM Tests
test_product_powers() ->
30 = product_powers([{2, 1}, {3, 1}, {5, 1}]),
18900 = product_powers([{2, 2}, {3, 3}, {5, 2}, {7, 1}]),
test_product_powers_ok. %% gcd lcm
gcd(Ns) ->
unified_proc(gcd, Ns).
lcm(Ns) ->
unified_proc(lcm, Ns).
test_gcd() ->
30 = gcd([90, 420, 9450]),
test_gcd_ok.
test_lcm() ->
18900 = lcm([90, 420, 9450]),
test_lcm_ok.在前面的实现里，语义的表达、执行方式、执行时机三者彻底解耦，实现了计算描述与执行的分离。
计算描述与执行分离这种设计思想非常强大。它带来的好处是：一方面在描述层面可以很自由，可以任意组装，不受限于执行层面；另一方面在执行层面可以做很多优化，比如并发，或者解释成其他的结果。需求变化的复杂性和代码修改的复杂性是线性关系，重要的是还不影响描述层面。
前提是先要有语义，解耦到什么程度，看具体问题和你的选择，但作为设计者要知道可能存在的耦合。
设计模式里最后一个模式是Interpreter模式，但这个模式很少有人提，但其实是最重要的。
switch/case一般会认为是一种bad smell，但switch/case并不总是魔鬼。其实switch/case是一种非常好的语言构造。代码有switch/case不能说好，但好的代码一定存在switch/case，说明程序中存在层次。
解释器的核心就是switch/case，switch/case的上面是Specification，switch/case下面是通用语言(Java/C/Python)，switch/case把两者隔离开了。
所以，如果switch/case是用来解决层次问题的话，就是好的switch/case，千万不要把它改掉。一个好的程序一定是一个语义层次分明的程序，里面一定有switch/case，一层一层的，下层解释上层。
当然把程序写得很糟糕，也会有很多switch/case。
设计就是把问题变成可计算的。
设计出的计算模型所提供的语义和问题领域的根本需求是否匹配，匹配就是好的设计，不匹配就是不好的设计。
- 对问题领域进行深入分析，发现问题领域的核心需求；
- 通过核心需求驱动出计算模型和语义；
- 再围绕这个计算模型提供一套语言，给外面的人使用这个计算模型提供一个接口，这个接口可以是API、可以是数据表达、也可以是语言；
- 最终要实现这个计算模型，实现的方法有解释器和编译器两种。
这就是DDD！这才是DDD！
这就是DSL！这才是DSL！
| “编程”不过是在某个计算模型上用某种语言去表达计算。 | 用DSL编程不过是在问题领域的计算模型上用DSL来表达计算。 |
| 计算模型是相应领域中的“通用机器”。 | 问题领域的计算模型是问题领域的通用机器。 |
| 编程语言不过是描述计算机器的一种方法。 | DSL描述的是DSL语言的计算机器。 |
| 程序是对特定机器的描述，这个特定机器可以被通用机器仿真。 | 用DSL程序实现了问题领域中的某个功能，这个DSL程序就是对这个功能(特定机器)的描述。 |
- 从问题领域导出核心需求，得到领域的计算模型(通用计算机器)，在上面可以包装一个DSL语言或者数据或者API，基于这些开发程序和应用。
- 领域的计算模型和通用语言的计算模型之间存在鸿沟，可以用解释器或者编译器来填补。
- 解释器和编译器听起来很复杂，其实思想很简单，而且我们没有必要实现一个工业级别的、非常全面的解释器和编译器，只要借鉴这个思想实现我们的计算模型就够了。
Common Languages(Java/C) UML对应Java通用语言。
Common Languages(Java/C) UM对应Java通用语言提供的计算模型(通用计算机器)。
提升设计能力的根本在于提升计算模型构造和语义定义能力。
Thinking, thinking and thinking …
Practice, practice and practice …
No shortcuts.
请用函数式编程实现，并比较解释器和函数式这两种实现方式的差异。
Solving Problem with Design, Not with the implementation language construction.
在前面的语义实现里，Specification是用我们自己设计的DSL写的程序，Interpreter是我们自己写的解释器，解释执行Specification。没有用到Erlang语言的函数式编程等高级特性，只用了最基本的语言特性。
通过设计来解决问题，而不是用你选择的实现语言的构造来解决问题。先有设计，再选择合适的语言构造来表达，一定要强迫自己使用最简单的语言构造解决问题，除非实在没有办法，再选择高级的语言特性解决问题。
语言越强，复杂性越高，而控制复杂性是软件工程里要解决的唯一问题。
- gcd_lcm.erl: Specification & Interpreter
- gcd_lcm_f.erl: Functional
- fayelab.ddd.gcdlcm.interpreter: Specification & interpreter
- fayelab.ddd.gcdlcm.functional: Functional
- gcd_lcm.py: Specification & Interpreter
- gcd_lcm_f.py: Functional