201712 DDD DSL Design War FizzBuzzWhizz Reloaded in Python - xiaoxianfaye/Courses GitHub Wiki
- 1 Review
- 2 Stop to Think
- 3 Interpreter
-
4 Interpreter & Compiler
- 4.1 Overview
- 4.2 Program + Parser + Interpreter
- 4.3 Program + Parser + Compiler
- 5 Summary
- 6 Homework
- 7 My Homework
你是一名体育老师，在某次课距离下课还有五分钟时，你决定搞一个游戏。此时有100名学生在上课。游戏的规则是：
-
设定三个不同的特殊数：3、5、7。
-
让所有学生排成一队，然后按顺序报数。
-
学生报数时，如果所报数字是第一个特殊数(3)的倍数，那么不能说该数字，而要说Fizz；如果所报数字是第二个特殊数(5)的倍数，那么要说Buzz；如果所报数字是第三个特殊数(7)的倍数，那么要说Whizz。
-
学生报数时，如果所报数字同时是两个特殊数的倍数情况下，也要特殊处理，比如第一个特殊数和第二个特殊数的倍数，那么不能说该数字，而是要说FizzBuzz, 以此类推。如果同时是三个特殊数的倍数，那么要说FizzBuzzWhizz。
-
学生报数时，如果所报数字包含了第一个特殊数，那么也不能说该数字，而是要说相应的单词，比如本例中第一个特殊数是3，那么要报13的同学应该说Fizz。 如果数字中包含了第一个特殊数，那么忽略规则3和规则4，比如要报35的同学只报Fizz，不报BuzzWhizz。
请编写一个程序来模拟这个游戏。
设计的第一步：找到合适的语义。
What is Semantics?
- 在解决一个问题的时候，经常问“What does this mean?”；
- 既能够被精确清晰地表达出来，又能够教给计算机去做。
How to find an appropriate Semantics?
- 首先考虑是否能将问题领域映射到一个熟悉的同构领域。如果能，就可以借用那个领域的机制来表达问题领域的概念，而不是重新发明。
- 最好是映射到数学领域。一般来说，最终一定能在数学层面上找到一个同构领域，有可能只是没找到而已。
把问题领域映射到了数学上的布尔代数的语义领域。
设计的第二步：形式化地表达语义。
语义(Semantics)需要形式化地表达(Formalization)，否则没法可计算化。
一旦要表达，就必须选择一种记法，用符号来表达。这种记法：
- 一定要是可计算的;
- 语义层次要高。
注意：先不要考虑如何实现。
与实现语言无关的DSL Specification：
r1_3 atom times 3 to_fizz
r1_5 atom times 5 to_buzz
r1_7 atom times 7 to_whizz
r1 or r1_3 r1_5 r1_7
r1_357 and r1_3 r1_5 r1_7
r1_35 and r1_3 r1_5
r1_37 and r1_3 r1_7
r1_57 and r1_5 r1_7
r2 or r1_357 r1_35 r1_37 r1_57
r3 atom contains 3 to_fizz
rd atom always_true to_str
spec or r3 r2 r1 rd
Python API Specification：
def spec():
r1_3 = Atom(Times(3), ToFizz())
r1_5 = Atom(Times(5), ToBuzz())
r1_7 = Atom(Times(7), ToWhizz())
r1 = OR3(r1_3, r1_5, r1_7)
r2 = OR4(AND3(r1_3, r1_5, r1_7),
AND(r1_3, r1_5),
AND(r1_3, r1_7),
AND(r1_5, r1_7))
r3 = Atom(Contains(3), ToFizz())
rd = Atom(AlwaysTrue(), ToStr())
return OR4(r3, r2, r1, rd)这里的Specification是精确无二义的，而且是可计算的，因为布尔代数本身就是精确、可计算的。
以上都是语义(Semantics)层面的。不考虑实现，只考虑语义。
找到一个跟FizzBuzzWhizz问题领域完全同构的布尔代数领域，把问题领域映射到布尔 代数领域，用布尔代数领域的语言(AND、OR)形式化地表达问题领域的整个语义模型。
设计的两个步骤：
- 找到合适的同构语义领域；
- 用同构语义领域的语言精确地形式化地表达语义。
这就是“建模”的本质。
在语义层面设计好以后，接下来就是选择合适的编程语言实现。
在实现层面，用一系列“接口”、“对象”来实现语义。
def spec():
r1_3 = Atom(Times(3), ToFizz())
r1_5 = Atom(Times(5), ToBuzz())
r1_7 = Atom(Times(7), ToWhizz())
r1 = OR3(r1_3, r1_5, r1_7)
r2 = OR4(AND3(r1_3, r1_5, r1_7),
AND(r1_3, r1_5),
AND(r1_3, r1_7),
AND(r1_5, r1_7))
r3 = Atom(Contains(3), ToFizz())
rd = Atom(AlwaysTrue(), ToStr())
return OR4(r3, r2, r1, rd)在实现层面，用一系列“接口”和“对象”来实现语义。
代码路径：oo
在实现层面，用一系列“函数”来实现语义。
代码路径：functional
test_all.py
import unittest
from tests.test_fizzbuzzwhizz import TestFizzBuzzWhizz
if __name__ == '__main__':
unittest.main()test_fizzbuzzwhizz.py
import unittest
from fizzbuzzwhizz import *
class TestFizzBuzzWhizz(unittest.TestCase):
def test_times(self):
times3 = times(3)
self.assertTrue(times3(3))
self.assertTrue(times3(6))
self.assertFalse(times3(5))
times5 = times(5)
self.assertTrue(times5(5))
self.assertTrue(times5(10))
self.assertFalse(times5(7))
times7 = times(7)
self.assertTrue(times7(7))
self.assertTrue(times7(14))
self.assertFalse(times7(3))
def test_contains(self):
contains3 = contains(3)
self.assertTrue(contains3(13))
self.assertTrue(contains3(35))
self.assertTrue(contains3(300))
self.assertFalse(contains3(24))
def test_alwaystrue(self):
at = alwaystrue()
self.assertTrue(at(1))
self.assertTrue(at(3))
self.assertTrue(at(5))fizzbuzzwhizz.py
def times(base):
def predicate(n):
return n % base == 0
return predicate
def contains(digit):
def predicate(n):
return str(digit) in str(n)
return predicate
def alwaystrue():
def predicate(n):
return True
return predicate以 “times”为例。从语言层面来看，times(base)是一个High-order Function，因为返回的是一个函数。从语义层面来看，times(base)是一个函数，这个函数的输入是一个整数，输出是一个布尔值。从语义理解更重要、也更容易。
test_fizzbuzzwhizz.py
def test_tofizz(self):
tf = tofizz()
self.assertEquals('Fizz', tf(3))
def test_tobuzz(self):
tb = tobuzz()
self.assertEquals('Buzz', tb(5))
def test_towhizz(self):
tw = towhizz()
self.assertEquals('Whizz', tw(7))
def test_tostr(self):
ts = tostr()
self.assertEquals('6', ts(6)) fizzbuzzwhizz.py
def tofizz():
def act(n):
return 'Fizz'
return act
def tobuzz():
def act(n):
return 'Buzz'
return act
def towhizz():
def act(n):
return 'Whizz'
return act
def tostr():
def act(n):
return str(n)
return act以 “tostr”为例。从语言层面来看，tostr()是一个High-order Function，因为返回的是一个函数。从语义层面来看，tostr()是一个函数，这个函数的输入是一个整数，输出是一个字符串。
test_fizzbuzzwhizz.py
def test_atom(self):
r1_3 = atom(times(3), tofizz())
self.assertEquals((True, 'Fizz'), r1_3(3))
self.assertEquals((False, ''), r1_3(4))
r1_5 = atom(times(5), tobuzz())
self.assertEquals((True, 'Buzz'), r1_5(10))
self.assertEquals((False, ''), r1_5(11))
r1_7 = atom(times(7), towhizz())
self.assertEquals((True, 'Whizz'), r1_7(14))
self.assertEquals((False, ''), r1_7(13))
r3 = atom(contains(3), tofizz())
self.assertEquals((True, 'Fizz'), r3(3))
self.assertEquals((True, 'Fizz'), r3(13))
self.assertEquals((True, 'Fizz'), r3(31))
self.assertEquals((False, ''), r3(24))
rd = atom(alwaystrue(), tostr())
self.assertEquals((True, '1'), rd(1))
self.assertEquals((True, '3'), rd(3))fizzbuzzwhizz.py
def atom(predication, action):
def apply(n):
if predication(n):
return True, action(n)
return False, ''
return apply从语言层面来看，atom(predication, action)是一个High-order Function，因为返回的是一个函数。从语义层面来看，atom(predication, action)是一个函数，这个函数的输入是一个整数，输出二选一的"(True, String)|(False, '')"。
atom(predication, action)是一个构造器，接受一个predication和一个action构造出一个原子rule。这里的rule不再是一个对象，而是一个函数。这个函数的输入是一个整数，输出是二选一的"(True, String)|(False, '')"。
test_fizzbuzzwhizz.py
def test_OR(self):
r1_3 = atom(times(3), tofizz())
r1_5 = atom(times(5), tobuzz())
r1_7 = atom(times(7), towhizz())
rd = atom(alwaystrue(), tostr())
or_35 = OR(r1_3, r1_5)
self.assertEquals((True, 'Fizz'), or_35(6))
self.assertEquals((True, 'Buzz'), or_35(10))
self.assertEquals((True, 'Fizz'), or_35(15))
self.assertEquals((False, ''), or_35(7))
or_357 = OR3(r1_3, r1_5, r1_7)
self.assertEquals((True, 'Fizz'), or_357(6))
self.assertEquals((True, 'Buzz'), or_357(10))
self.assertEquals((True, 'Whizz'), or_357(14))
self.assertEquals((False, ''), or_357(13))
or_357d = OR4(r1_3, r1_5, r1_7, rd)
self.assertEquals((True, 'Fizz'), or_357d(6))
self.assertEquals((True, 'Buzz'), or_357d(10))
self.assertEquals((True, 'Whizz'), or_357d(14))
self.assertEquals((True, '13'), or_357d(13))fizzbuzzwhizz.py
def OR(rule1, rule2):
def apply(n):
result1 = rule1(n)
if result1[0]:
return result1
return rule2(n)
return apply
def OR3(rule1, rule2, rule3):
return OR(rule1, OR(rule2, rule3))
def OR4(rule1, rule2, rule3, rule4):
return OR(rule1, OR3(rule2, rule3, rule4))从语言层面来看，OR(rule1, rule2)是一个High-order Function，因为返回的是一个函数。从语义层面来看，OR(rule1, rule2)是一个函数，这个函数的输入是一个整数，输出是二选一的"(True, String)|(False, '')"。
OR(rule1, rule2)是一个构造器，接受两个rule构造出一个新的rule。这里的rule不再是一个对象，而是一个函数。这个函数的输入是一个整数，输出是二选一的"(True, String)|(False, '')"。
test_fizzbuzzwhizz.py
def test_AND(self):
r1_3 = atom(times(3), tofizz())
r1_5 = atom(times(5), tobuzz())
r1_7 = atom(times(7), towhizz())
and_35 = AND(r1_3, r1_5)
self.assertEquals((False, ''), and_35(3))
self.assertEquals((False, ''), and_35(5))
self.assertEquals((True, 'FizzBuzz'), and_35(15))
self.assertEquals((False, ''), and_35(16))
and_37 = AND(r1_3, r1_7)
self.assertEquals((True, 'FizzWhizz'), and_37(21))
self.assertEquals((False, ''), and_37(2))
and_57 = AND(r1_5, r1_7)
self.assertEquals((True, 'BuzzWhizz'), and_57(35))
self.assertEquals((False, ''), and_57(36))
and_357 = AND3(r1_3, r1_5, r1_7)
self.assertEquals((True, 'FizzBuzzWhizz'), and_357(3*5*7))
self.assertEquals((False, ''), and_357(104))fizzbuzzwhizz.py
def AND(rule1, rule2):
def apply(n):
result1 = rule1(n)
if not result1[0]:
return False, ''
result2 = rule2(n)
if not result2[0]:
return False, ''
return True, ''.join([result1[1], result2[1]])
return apply
def AND3(rule1, rule2, rule3):
return AND(rule1, AND(rule2, rule3))从语言层面来看，AND(rule1, rule2)是一个High-order Function，因为返回的是一个函数。从语义层面来看，AND(rule1, rule2)是一个函数，这个函数的输入是一个整数，输出是二选一的"(True, String)|(False, '')"。
AND(rule1, rule2)是一个构造器，接受两个rule构造出一个新的rule。这里的rule不再是一个对象，而是一个函数。这个函数的输入是一个整数，输出是二选一的"(True, String)|(False, '')"。
对于AND和OR来说，参与计算的rule是原子rule还是组合rule都无所谓，只要实现同样的语义即可。这个语义就是一个函数，函数的输入是一个整数，输出是二选一的"(True, String)|(False, '')"。
AND和OR是组合子。两个rule用AND或OR组合以后还是一个rule，组合后的rule跟原子rule一样还可以和其它的rule再次组合，也就是说，AND和OR组合子在rule的世界里是封闭的，我们称这种性质为闭包性(Closure)。
组合子满足封闭性非常重要，因为只有满足封闭性，组合子才能和其它原子或者组合子再组合……。可以想象，如果一个语言提供的组合手段是能够封闭的，那么它就能够高效地帮助你构建出非常复杂的东西。
在OO实现方式中，通常用“接口”表示“是什么”，接口方法的输入、输出决定了“什么”的特征。用“接口”实现组合子的封闭性，对象只要满足了接口特征就是“什么”。 在Functional实现方式中，通常用“函数”表示“是什么”，函数的输入、输出决定了“什么”的特征。用“函数”实现组合子的封闭性，函数只要满足了输入输出特征就是“什么”。
test_fizzbuzzwhizz.py
def test_spec(self):
s = spec()
self.assertEquals((True, 'Fizz'), s(35))
self.assertEquals((True, 'FizzWhizz'), s(21))
self.assertEquals((True, 'BuzzWhizz'), s(70))
self.assertEquals((True, 'Fizz'), s(9))
self.assertEquals((True, '1'), s(1))fizzbuzzwhizz.py
def spec():
r1_3 = atom(times(3), tofizz())
r1_5 = atom(times(5), tobuzz())
r1_7 = atom(times(7), towhizz())
r1 = OR3(r1_3, r1_5, r1_7)
r2 = OR4(AND3(r1_3, r1_5, r1_7),
AND(r1_3, r1_5),
AND(r1_3, r1_7),
AND(r1_5, r1_7))
r3 = atom(contains(3), tofizz())
rd = atom(alwaystrue(), tostr())
return OR4(r3, r2, r1, rd)可以看到，Functional实现方式里的Specification和OO实现方式里的Specification几乎是一样的。
fizzbuzzwhizz.py
def run():
s = spec()
results = [s(n) for n in range(1, 101)]
output(results)
def output(results):
print [result[1] for result in results]
if __name__ == '__main__':
run()语言能力是一把双刃剑。我们在享受编程语言的强大特性带来的好处的同时，也要警惕它们带来的阴暗面。正面影响是利用语言的强大特性实现起来很快，代码可能看上去会很“酷炫”。但其实负面影响更大，而且往往不容易察觉。语言能力太强大，在设计上就会偷懒，结果就是极大地损害了代码的可理解性，增加了不必要的复杂性。语言能力比较弱，其实是件好事情，会强迫你从问题出发、做出更好的设计，因为就那么点语言特性。
为了避免引起歧义，特别说明两点：
-
这里的“设计”是指课程中一直反复强调的“以语义为核心”的设计过程，不是指使用了接口、继承、OO设计模式或者高阶函数的那些所谓的“设计”。现在大家应该可以理解了，那些都只是语义实现手段。
-
那是不是说我们就不用学习、不使用语言新特性了呢？当然不是。在做好“以语义为核心”的设计的前提下，我们可以尽情享受语言的强大特性快速实现我们的设计。这就更需要我们不断提升自己的思考能力和把控能力。
如果没有接口，没有High-order Function，还能实现吗？如何实现呢？
在OO实现方式和函数式实现方式中，我们将语义的表达和执行解耦了，还存在耦合吗？解耦还不够彻底，还存在不易察觉的耦合。执行还可以再细分为执行方式和执行时机。在OO实现方式和函数式实现方式中，语义的表达和执行时机确实解耦了，Specification只是语义表达，定义Specification的时候并未执行，apply的时候才执行。但语义的表达和执行方式并未解耦。在OO实现方式中，语义的表达和执行方式均定义在了Atom、AND、OR等对象中。在函数式实现方式中，语义的表达和执行方式均定义在了高阶函数中。这也是一种耦合，只是不那么容易被察觉。
举个例子，可以说得更清楚。现在要再实现一个功能——把FizzBuzzWhizz中的整个Rule的关系树打印出来。在OO实现方式和函数式实现方式中，要怎么修改代码呢？
需求变化了，代码就要修改。如果需求变化的复杂性和代码修改的复杂性是线性关系，这个设计就是一个非常好的设计，大部分情况下需求变化。代码修改一团糟，是完全非线性的。
能不能将语义的表达、执行时机和执行方式这三者彻底解耦呢？
代码路径：interpreter
r1_3 = atom(times(3), tofizz())
r1_5 = atom(times(5), tobuzz())
r1_7 = atom(times(7), towhizz())
r1 = OR3(r1_3, r1_5, r1_7)
r2 = OR4(AND3(r1_3, r1_5, r1_7),
AND(r1_3, r1_5),
AND(r1_3, r1_7),
AND(r1_5, r1_7))
r3 = atom(contains(3), tofizz())
rd = atom(alwaystrue(), tostr())
return OR4(r3, r2, r1, rd)无论如何实现，Specification是不变的，语义是核心。Specification中的times|contains|alwaystrue、tofizz|tobuzz|towhizz|tostr、atom|AND|OR都表达了一个个的概念和语义。它们可以是对象，也可以是函数，也可以既不是对象也不是函数，那是什么呢？它们可以只是“数据”，表达语义即可。语义什么时候执行、如何执行是另外一件事情。
通过**“数据”**来表达领域的核心概念、逻辑和关系。
rule.py
def times(base):
return 'TIMES', base
def contains(digit):
return 'CONTAINS', digit
def alwaystrue():
return 'ALWAYSTRUE', Nonetimes()、contains()、alwaystrue()函数不再返回对象或函数，而是返回Tuple类型的数据，Tuple的第0个元素是用于标识Predication类型的字符串，第1个元素是times需要的base、contains需要的digit，alwaystrue本来不需要这个元素，但为了后续写代码方便，用None占一下位。
rule.py
def tofizz():
return 'TOFIZZ'
def tobuzz():
return 'TOBUZZ'
def towhizz():
return 'TOWHIZZ'
def tostr():
return 'TOSTR'tofizz()、tobuzz()、towhizz()、tostr()函数不再返回对象或函数，而是返回用于标识Action类型的字符串。
rule.py
def atom(predication, action):
return 'ATOM', predication, action
def OR(rule1, rule2):
return 'OR', rule1, rule2
def AND(rule1, rule2):
return 'AND', rule1, rule2atom()、OR()、AND()函数不再返回对象或函数，而是返回Tuple类型的数据，Tuple的第0个元素是用于标识Rule类型的字符串，后面的元素是不同类型Rule所需要的参数。
AND和OR还是满足封闭性的。两个Rule用AND或OR组合以后还是一个Rule，组合后的Rule跟原子Rule一样还可以和其它的Rule再次组合，也就是说，AND和OR组合子在Rule的世界里是封闭的。
rule.py
def OR3(rule1, rule2, rule3):
return OR(rule1, OR(rule2, rule3))
def OR4(rule1, rule2, rule3, rule4):
return OR(rule1, OR3(rule2, rule3, rule4))
def AND3(rule1, rule2, rule3):
return AND(rule1, AND(rule2, rule3))
def spec():
r1_3 = atom(times(3), tofizz())
r1_5 = atom(times(5), tobuzz())
r1_7 = atom(times(7), towhizz())
r1 = OR3(r1_3, r1_5, r1_7)
r2 = OR4(AND3(r1_3, r1_5, r1_7),
AND(r1_3, r1_5),
AND(r1_3, r1_7),
AND(r1_5, r1_7))
r3 = atom(contains(3), tofizz())
rd = atom(alwaystrue(), tostr())
return OR4(r3, r2, r1, rd)Specification看上去没变，但其实已经完全数据化了。OO实现方式和函数式实现方式中的Specification既有数据又有代码(行为)。这里的Specification只有数据，更抽象。
数据是声明性的(Declarative)，告诉我们做什么(What)。代码是命令性的(Imperative)，告诉我们如何做(How to)。声明性的语义表达力更强。
这里有个前提：在定义数据的时候，要从语义层面声明性地、精确地表达领域的核心概念、逻辑和关系(What)，而不是从实现层面上定义数据结构(How to)。
这里的Specification其实只是一堆符号，它的语义在于如何去解释。
核心是数据，用数据去捕获领域的核心概念、逻辑和关系。
Specification定义好了，都是纯数据，怎么让它跑起来呢？
对于类似Java的静态语言，写好程序(.java)以后，需要先编译(Compile)成字节码(.class)，再由虚拟机加载执行。
对于类似JavaScript的动态语言，写好程序以后，不需要编译(Compile)，可以直接解释(Interpret)执行。
这些编译器(Compiler)和解释器(Interpreter)都是别人已经写好的，我们直接拿过来用就好。
同理，Specification是用我们自己设计的DSL写的程序，写好程序以后，可以直接解释执行，也可以先编译再执行。
这里的解释器和编译器需要我们自己写。不用害怕，不是那么困难。因为这里的解释器和编译器同样是面向特定领域的。
本次课程里，我们重点讲一下解释器，编译器以后有机会再讲。
interpreter.py
def apply_rule(rule, n):
if rule[0] == 'ATOM':
return apply_atom(rule[1], rule[2], n)
elif rule[0] == 'OR':
return apply_or(rule[1], rule[2], n)
elif rule[0] == 'AND':
return apply_and(rule[1], rule[2], n)
else:
return False, ''test_all.py
import unittest
from tests.test_interpreter import TestInterpreter
if __name__ == '__main__':
unittest.main()test_interpreter.py
import unittest
from rule import *
from interpreter import *
class TestInterpreter(unittest.TestCase):
def test_atom(self):
r1_3 = atom(times(3), tofizz())
self.assertEquals((True, 'Fizz'), apply_rule(r1_3, 6))
self.assertEquals((False, ''), apply_rule(r1_3, 7))
r1_5 = atom(times(5), tobuzz())
self.assertEquals((True, 'Buzz'), apply_rule(r1_5, 10))
self.assertEquals((False, ''), apply_rule(r1_5, 11))
r1_7 = atom(times(7), towhizz())
self.assertEquals((True, 'Whizz'), apply_rule(r1_7, 14))
self.assertEquals((False, ''), apply_rule(r1_7, 13))
r3 = atom(contains(3), tofizz())
self.assertEquals((True, 'Fizz'), apply_rule(r3, 3))
self.assertEquals((True, 'Fizz'), apply_rule(r3, 13))
self.assertEquals((True, 'Fizz'), apply_rule(r3, 31))
self.assertEquals((False, ''), apply_rule(r3, 24))
rd = atom(alwaystrue(), tostr())
self.assertEquals((True, '1'), apply_rule(rd, 1))
self.assertEquals((True, '3'), apply_rule(rd, 3))interpreter.py
def apply_rule(rule, n):
if rule[0] == 'ATOM':
return apply_atom(rule[1], rule[2], n)
else:
return False, ''
def apply_atom(predication, action, n):
if apply_predication(predication, n):
return True, apply_action(action, n)
return False, ''
def apply_predication(predication, n):
if predication[0] == 'TIMES':
return i_times(predication[1], n)
elif predication[0] == 'CONTAINS':
return i_contains(predication[1], n)
elif predication[0] == 'ALWAYSTRUE':
return i_alwaystrue()
else:
return False
def apply_action(action, n):
if action == 'TOFIZZ':
return i_tofizz()
elif action == 'TOBUZZ':
return i_tobuzz()
elif action == 'TOWHIZZ':
return i_towhizz()
elif action == 'TOSTR':
return i_tostr(n)
else:
return ''
def i_times(base, n):
return n % base == 0
def i_contains(digit, n):
return str(digit) in str(n)
def i_alwaystrue():
return True
def i_tofizz():
return 'Fizz'
def i_tobuzz():
return 'Buzz'
def i_towhizz():
return 'Whizz'
def i_tostr(n):
return str(n) 说明：
- 为了避免跟rule模块中的函数重名，interpreter模块中与rule模块函数名类似的函数名都加上"i_"的前缀。
重构，将apply_predication()和apply_action()函数中的if/else换成映射。
interpreter.py
def i_times(base, n):
return n % base == 0
def i_contains(digit, n):
return str(digit) in str(n)
def i_alwaystrue(param, n):
return True
def i_tofizz(n):
return 'Fizz'
def i_tobuzz(n):
return 'Buzz'
def i_towhizz(n):
return 'Whizz'
def i_tostr(n):
return str(n)
PREDICATION_MAP = {'TIMES':i_times, 'CONTAINS':i_contains, 'ALWAYSTRUE':i_alwaystrue}
ACTION_MAP = {'TOFIZZ':i_tofizz, 'TOBUZZ':i_tobuzz, 'TOWHIZZ':i_towhizz, 'TOSTR':i_tostr}
def apply_predication(predication, n):
if predication[0] in PREDICATION_MAP:
return PREDICATION_MAP[predication[0]](predication[1], n)
return False
def apply_action(action, n):
if action in ACTION_MAP:
return ACTION_MAP[action](n)
return ''说明：
- 以"i_"开头的函数定义要放在MAP定义之前。
- i_alwaystrue()函数原来是不带参数的，为了PREDICATION_MAP写起来简单，i_alwaystrue()函数加了param和n两个参数，这样就跟i_times()和i_contains()函数的参数形式一样了。
- i_tofizz()、i_tobuzz()、i_towhizz()函数原来是不带参数的，为了ACTION_MAP写起来简单，都增加了n这个参数，这样就跟i_tostr()函数的参数形式一样了。
test_interpreter.py
def test_OR(self):
r1_3 = atom(times(3), tofizz())
r1_5 = atom(times(5), tobuzz())
r1_7 = atom(times(7), towhizz())
rd = atom(alwaystrue(), tostr())
or_35 = OR(r1_3, r1_5)
self.assertEquals((True, 'Fizz'), apply_rule(or_35, 6))
self.assertEquals((True, 'Buzz'), apply_rule(or_35, 10))
self.assertEquals((True, 'Fizz'), apply_rule(or_35, 15))
self.assertEquals((False, ''), apply_rule(or_35, 7))
or_357 = OR3(r1_3, r1_5, r1_7)
self.assertEquals((True, 'Fizz'), apply_rule(or_357, 6))
self.assertEquals((True, 'Buzz'), apply_rule(or_357, 10))
self.assertEquals((True, 'Whizz'), apply_rule(or_357, 14))
self.assertEquals((False, ''), apply_rule(or_357, 13))
or_357d = OR4(r1_3, r1_5, r1_7, rd)
self.assertEquals((True, 'Fizz'), apply_rule(or_357d, 6))
self.assertEquals((True, 'Buzz'), apply_rule(or_357d, 10))
self.assertEquals((True, 'Whizz'), apply_rule(or_357d, 14))
self.assertEquals((True, '13'), apply_rule(or_357d, 13))interpreter.py
def apply_or(rule1, rule2, n):
result1 = apply_rule(rule1, n)
if result1[0]:
return result1
return apply_rule(rule2, n)test_interpreter.py
def test_AND(self):
r1_3 = atom(times(3), tofizz())
r1_5 = atom(times(5), tobuzz())
r1_7 = atom(times(7), towhizz())
and_35 = AND(r1_3, r1_5)
self.assertEquals((False, ''), apply_rule(and_35, 3))
self.assertEquals((False, ''), apply_rule(and_35, 5))
self.assertEquals((True, 'FizzBuzz'), apply_rule(and_35, 15))
self.assertEquals((False, ''), apply_rule(and_35, 16))
and_37 = AND(r1_3, r1_7)
self.assertEquals((True, 'FizzWhizz'), apply_rule(and_37, 21))
self.assertEquals((False, ''), apply_rule(and_37, 2))
and_57 = AND(r1_5, r1_7)
self.assertEquals((True, 'BuzzWhizz'), apply_rule(and_57, 35))
self.assertEquals((False, ''), apply_rule(and_57, 36))
and_357 = AND3(r1_3, r1_5, r1_7)
self.assertEquals((True, 'FizzBuzzWhizz'), apply_rule(and_357, 3*5*7))
self.assertEquals((False, ''), apply_rule(and_357, 104))interpreter.py
def apply_rule(rule, n):
if rule[0] == 'ATOM':
return apply_atom(rule[1], rule[2], n)
elif rule[0] == 'OR':
return apply_or(rule[1], rule[2], n)
elif rule[0] == 'AND':
return apply_and(rule[1], rule[2], n)
else:
return False, ''
def apply_and(rule1, rule2, n):
result1 = apply_rule(rule1, n)
if not result1[0]:
return False, ''
result2 = apply_rule(rule2, n)
if not result2[0]:
return False, ''
return True, ''.join([result1[1], result2[1]])重构，将apply_rule()函数中的if/else换成映射。
def apply_atom(predication, action, n):
if apply_predication(predication, n):
return True, apply_action(action, n)
return False, ''
def apply_predication(predication, n):
if predication[0] in PREDICATION_MAP:
return PREDICATION_MAP[predication[0]](predication[1], n)
return False
def apply_action(action, n):
if action in ACTION_MAP:
return ACTION_MAP[action](n)
return ''
def apply_or(rule1, rule2, n):
result1 = apply_rule(rule1, n)
if result1[0]:
return result1
return apply_rule(rule2, n)
def apply_and(rule1, rule2, n):
result1 = apply_rule(rule1, n)
if not result1[0]:
return False, ''
result2 = apply_rule(rule2, n)
if not result2[0]:
return False, ''
return True, ''.join([result1[1], result2[1]])
RULE_MAP = {'ATOM':apply_atom, 'OR':apply_or, 'AND':apply_and}
def apply_rule(rule, n):
if rule[0] in RULE_MAP:
return RULE_MAP[rule[0]](rule[1], rule[2], n)
else:
return False, ''说明：
- apply_atom()、apply_or()和apply_and()函数定义要放在MAP定义之前。
test_interpreter.py
def test_spec(self):
s = spec()
self.assertEquals((True, 'Fizz'), apply_rule(s, 35))
self.assertEquals((True, 'FizzWhizz'), apply_rule(s, 21))
self.assertEquals((True, 'BuzzWhizz'), apply_rule(s, 70))
self.assertEquals((True, 'Fizz'), apply_rule(s, 9))
self.assertEquals((True, '1'), apply_rule(s, 1))rule.py
def spec():
r1_3 = atom(times(3), tofizz())
r1_5 = atom(times(5), tobuzz())
r1_7 = atom(times(7), towhizz())
r1 = OR3(r1_3, r1_5, r1_7)
r2 = OR4(AND3(r1_3, r1_5, r1_7),
AND(r1_3, r1_5),
AND(r1_3, r1_7),
AND(r1_5, r1_7))
r3 = atom(contains(3), tofizz())
rd = atom(alwaystrue(), tostr())
return OR4(r3, r2, r1, rd)fizzbuzzwhizz.py
from rule import *
from interpreter import *
def run():
s = spec()
results = [apply_rule(s, n) for n in range(1, 101)]
output(results)
def output(results):
print [result[1] for result in results]
if __name__ == '__main__':
run()- Look at a piece of data.
- Decide what kind of data it represents.
- Extract the components of the datum and do the right thing with them.
在前面的语义实现里，Specification是用我们自己设计的DSL写的程序，Interpreter是我们自己写的解释器，解释执行Specification。没有用到Java或Python语言的高级特性，例如接口、对象、高阶函数等，只用了语言最基本的语言特性。
通过设计来解决问题，而不是用你选择的实现语言的构造来解决问题。先有设计，再选择合适的语言构造来表达，一定要强迫自己使用最简单的语言构造解决问题，除非实在没有办法，再选择高级的语言特性解决问题。要记住：语言越强，复杂性越高，而控制复杂性是软件工程里要解决的唯一问题。
在前面的实现里，语义的表达、执行方式、执行时机三者彻底解耦，实现了计算描述与执行的分离。
计算描述与执行分离这种设计思想非常强大。它带来的好处是：一方面在描述层面可以很自由，可以任意组装，不受限于执行层面；另一方面在执行层面可以做很多优化，比如并发，或者解释成其他的结果，比如把FizzBuzzWhizz中的整个Rule的关系树打印出来，只要再写一个解释器即可，需求变化的复杂性和代码修改的复杂性是线性关系，重要的是还不影响描述层面。
前提是先要有语义，解耦到什么程度，看具体问题和你的选择，但作为设计者要知道可能存在的耦合。
设计模式里最后一个模式是Interpreter模式，但这个模式很少有人提，但其实是最重要的。
switch/case一般会认为是一种bad smell，但switch/case并不总是魔鬼。其实switch/case是一种非常好的语言构造。代码有switch/case不能说好，但好的代码一定存在switch/case，说明程序中存在层次。
解释器的核心就是switch/case，switch/case的上面是Specification，switch/case下面是通用语言(Java/Python/C)，switch/case把两者隔离开了。
所以，如果switch/case是用来解决层次问题的话，就是好的switch/case，千万不要把它改掉。一个好的程序一定是一个语义层次分明的程序，里面一定有switch/case，一层一层的，下层解释上层。
当然把程序写得很糟糕，也会有很多switch/case。
虽然在这次课程里重点讲解了Interpreter，但还是想从整体上将Interpreter和Compiler再给大家介绍一下。
下面从整体来介绍一下Interpreter和Compiler。
对问题领域进行深入分析，设计出其语义与问题领域根本需求相匹配的计算模型，围绕这个计算模型设计出贴合问题领域的DSL。
基于这个DSL设计一套小语言，用这套小语言编写程序(Program)，作为解析器(Parser)的输入。解析器一般包括两个步骤：Tokenizer/Lexical Analysis和Syntax/Grammar。Tokenizer/Lexical Analysis会根据DSL的语法定义将分隔符分隔的每个字段取出，并进行词法分析。Syntax/Grammar会根据语法定义检查语法的合法性。这两个步骤的区分并不是那么严格，有时Tokenizer/Lexical Analysis也可以做一些语法检查。解析器一般不用自己实现，现在有很多开源的第三方工具帮我们做这件事情。
解析器的输出是生成抽象语法树(AST：Abstract Syntax Tree)。这是我们的设计中最核心的部分。这部分只有数据，数据是核心，通过数据和数据结构声明性地表达了领域的核心概念、逻辑和关系。
FizzBuzzWhizz的AST如下：
以上均属于描述层面。
执行层面有两种方式：解释器(Interpreter)和编译器(Compiler)。
- 可以将解释器的作用理解为一台语义执行机器，实现了当前的语义。Interpreter一般都包含switch/case和递归调用。
- 可以将编译器的作用理解为保持语义的等价语法变换。变换成了另外一种语言(比如字节码、机器指令等)，最终都要由解释器(比如虚拟机、硬件等)解释执行。
解释器是一边解释、一边执行。这样的实现方式导致：一方面执行的中间结果没法重用的，另一方面无法做语义上的优化，所以效率相对比较低下，但也更为通用。
编译器是编译一次、可以反复执行。编译时可以针对特定语义进行语义上的优化，所以效率相对比较高，但比较特定。
下面来编写一个从Program到Parser到Interpreter的完整程序。
代码路径：complete.interpreter
为了完整的展示Overview中的过程，基于之前设计的DSL简单设计了一套小语言，并用这套小语言编写了程序“prog_1.fbw”。
prog_1.fbw
r1_3 atom times 3 to_fizz
r1_5 atom times 5 to_buzz
r1_7 atom times 7 to_whizz
r1 or r1_3 r1_5 r1_7
r1_357 and r1_3 r1_5 r1_7
r1_35 and r1_3 r1_5
r1_37 and r1_3 r1_7
r1_57 and r1_5 r1_7
r2 or r1_357 r1_35 r1_37 r1_57
r3 atom contains 3 to_fizz
rd atom always_true to_str
spec or r3 r2 r1 rd
这套小语言的语法非常简单：
- 每行只描述一个规则(Rule)；
- 每个Rule的字段用空格分隔。第1个字段含义固定是Rule的名称，第2个字段含义固定是Rule的类型，根据不同的Rule类型，后续字段的含义会有所不同：
a) 当Rule类型是“atom”时，后续字段的含义依次是Predication类型、Predication参数(可能没有，例如always_true就不需要这个字段)、Action类型； b) 当Rule类型是“or”或“and”时，后续字段的含义是参与or或者and运算的Rule名称。 - 被引用的Rule必须是提前定义好的；
- 全小写；
- 为了能够清晰表述，可以用空行分段，不小心多敲了空格也没关系。
实现解析器，包括以下步骤：
- 不想在Parser中区分“or2|3|4”和“and2|3”，所以新增ORN()、ORN_list()、ANDN()和ANDN_list()函数，并删除OR3()、OR4和AND3()函数。
- 实现解析器Parser。
另外，由于只是练习演示需要，这里的Parser没有实现语法检查功能，只实现了简单的解析功能。
不想在Parser中区分“or2|3|4”和“and2|3”，所以新增ORN()、ORN_list()、ANDN()和ANDN_list()函数，并删除OR3()、OR4和AND3()函数。
test_all.py
import unittest
from tests.test_interpreter import TestInterpreter
if __name__ == '__main__':
unittest.main()test_interpreter.py
import unittest
from rule import *
from interpreter import *
class TestInterpreter(unittest.TestCase):
def test_atom(self):
r1_3 = atom(times(3), tofizz())
self.assertEquals((True, 'Fizz'), apply_rule(r1_3, 6))
self.assertEquals((False, ''), apply_rule(r1_3, 7))
r1_5 = atom(times(5), tobuzz())
self.assertEquals((True, 'Buzz'), apply_rule(r1_5, 10))
self.assertEquals((False, ''), apply_rule(r1_5, 11))
r1_7 = atom(times(7), towhizz())
self.assertEquals((True, 'Whizz'), apply_rule(r1_7, 14))
self.assertEquals((False, ''), apply_rule(r1_7, 13))
r3 = atom(contains(3), tofizz())
self.assertEquals((True, 'Fizz'), apply_rule(r3, 3))
self.assertEquals((True, 'Fizz'), apply_rule(r3, 13))
self.assertEquals((True, 'Fizz'), apply_rule(r3, 31))
self.assertEquals((False, ''), apply_rule(r3, 24))
rd = atom(alwaystrue(), tostr())
self.assertEquals((True, '1'), apply_rule(rd, 1))
self.assertEquals((True, '3'), apply_rule(rd, 3))
def test_OR(self):
r1_3 = atom(times(3), tofizz())
r1_5 = atom(times(5), tobuzz())
r1_7 = atom(times(7), towhizz())
rd = atom(alwaystrue(), tostr())
or_35 = OR(r1_3, r1_5)
self.assertEquals((True, 'Fizz'), apply_rule(or_35, 6))
self.assertEquals((True, 'Buzz'), apply_rule(or_35, 10))
self.assertEquals((True, 'Fizz'), apply_rule(or_35, 15))
self.assertEquals((False, ''), apply_rule(or_35, 7))
or_357 = ORN(r1_3, r1_5, r1_7)
self.assertEquals((True, 'Fizz'), apply_rule(or_357, 6))
self.assertEquals((True, 'Buzz'), apply_rule(or_357, 10))
self.assertEquals((True, 'Whizz'), apply_rule(or_357, 14))
self.assertEquals((False, ''), apply_rule(or_357, 13))
or_357d = ORN(r1_3, r1_5, r1_7, rd)
self.assertEquals((True, 'Fizz'), apply_rule(or_357d, 6))
self.assertEquals((True, 'Buzz'), apply_rule(or_357d, 10))
self.assertEquals((True, 'Whizz'), apply_rule(or_357d, 14))
self.assertEquals((True, '13'), apply_rule(or_357d, 13))
or_357d = ORN(r1_3, r1_5, r1_7, rd)
self.assertEquals((True, 'Fizz'), apply_rule(or_357d, 6))
self.assertEquals((True, 'Buzz'), apply_rule(or_357d, 10))
self.assertEquals((True, 'Whizz'), apply_rule(or_357d, 14))
self.assertEquals((True, '13'), apply_rule(or_357d, 13))
def test_AND(self):
r1_3 = atom(times(3), tofizz())
r1_5 = atom(times(5), tobuzz())
r1_7 = atom(times(7), towhizz())
and_35 = AND(r1_3, r1_5)
self.assertEquals((False, ''), apply_rule(and_35, 3))
self.assertEquals((False, ''), apply_rule(and_35, 5))
self.assertEquals((True, 'FizzBuzz'), apply_rule(and_35, 15))
self.assertEquals((False, ''), apply_rule(and_35, 16))
and_37 = AND(r1_3, r1_7)
self.assertEquals((True, 'FizzWhizz'), apply_rule(and_37, 21))
self.assertEquals((False, ''), apply_rule(and_37, 2))
and_57 = AND(r1_5, r1_7)
self.assertEquals((True, 'BuzzWhizz'), apply_rule(and_57, 35))
self.assertEquals((False, ''), apply_rule(and_57, 36))
and_357 = ANDN(r1_3, r1_5, r1_7)
self.assertEquals((True, 'FizzBuzzWhizz'), apply_rule(and_357, 3*5*7))
self.assertEquals((False, ''), apply_rule(and_357, 104))
def test_spec(self):
s = spec()
self.assertEquals((True, 'Fizz'), apply_rule(s, 35))
self.assertEquals((True, 'FizzWhizz'), apply_rule(s, 21))
self.assertEquals((True, 'BuzzWhizz'), apply_rule(s, 70))
self.assertEquals((True, 'Fizz'), apply_rule(s, 9))
self.assertEquals((True, '1'), apply_rule(s, 1))rule.py
def ORN(*rules):
return ORN_list(list(rules))
def ORN_list(rules):
return _combine(rules, OR)
def ANDN(*rules):
return ANDN_list(list(rules))
def ANDN_list(rules):
return _combine(rules, AND)
def _combine(rules, func):
if len(rules) == 1:
return rules[0]
return func(rules[0], _combine(rules[1:], func))
def spec():
r1_3 = atom(times(3), tofizz())
r1_5 = atom(times(5), tobuzz())
r1_7 = atom(times(7), towhizz())
r1 = ORN(r1_3, r1_5, r1_7)
r2 = ORN(ANDN(r1_3, r1_5, r1_7),
AND(r1_3, r1_5),
AND(r1_3, r1_7),
AND(r1_5, r1_7))
r3 = atom(contains(3), tofizz())
rd = atom(alwaystrue(), tostr())
return ORN(r3, r2, r1, rd)编写tokenize()函数。
从文件读入程序操作的输出是列表(List)，列表的元素是一个规则的描述字符串，作为tokenize()函数的输入。tokenize()函数的输出是列表的列表(List)。内层列表的元素是规格描述字段。外层列表的元素是每一个规则对应的描述字段列表。
tokenize: (List<String> ruleDescs) -> (List<List<String>> tokens)
tokenize操作分为以下几个步骤：
- 过滤空行；
- 规格化每一个规则描述(normalize)：去掉前后空格，字段之间多于一个的空格替换为一个空格；
- 以一个空格为分隔符split每个规格化后的规则描述。
test_all.py
import unittest
from tests.test_interpreter import TestInterpreter
from tests.fbwparser.test_parser import TestParser
if __name__ == '__main__':
unittest.main()说明：
- 在编写Python代码时，要特别小心自己起的模块名字跟Python自己的库模块重名。一般有两种处理方法。方法一，直接换个名字。方法二，把自己的模块放到一个包下，但要注意包名也不能重名。
fbwparser/test_parser.py
import unittest
from fbwparser.parser import *
class TestParser(unittest.TestCase):
RULE_DESCS = ["r1_3 atom times 3 to_fizz",
"r1_5 atom times 5 to_buzz",
"r1_7 atom times 7 to_whizz",
"",
"r1 or r1_3 r1_5 r1_7",
"",
"r1_357 and r1_3 r1_5 r1_7",
"r1_35 and r1_3 r1_5",
"r1_37 and r1_3 r1_7",
"r1_57 and r1_5 r1_7",
"",
"r2 or r1_357 r1_35 r1_37 r1_57",
"",
"r3 atom contains 3 to_fizz",
"",
"rd atom always_true to_str",
" ",
" spec or r3 r2 r1 rd ",
" "]
RULE_TOKENS = [['r1_3', 'atom', 'times', '3', 'to_fizz'],
['r1_5', 'atom', 'times', '5', 'to_buzz'],
['r1_7', 'atom', 'times', '7', 'to_whizz'],
['r1', 'or', 'r1_3', 'r1_5', 'r1_7'],
['r1_357', 'and', 'r1_3', 'r1_5', 'r1_7'],
['r1_35', 'and', 'r1_3', 'r1_5'],
['r1_37', 'and', 'r1_3', 'r1_7'],
['r1_57', 'and', 'r1_5', 'r1_7'],
['r2', 'or', 'r1_357', 'r1_35', 'r1_37', 'r1_57'],
['r3', 'atom', 'contains', '3', 'to_fizz'],
['rd', 'atom', 'always_true', 'to_str'],
['spec', 'or', 'r3', 'r2', 'r1', 'rd']]
def test_tokenize(self):
self.assertEquals(TestParser.RULE_TOKENS, tokenize(TestParser.RULE_DESCS))fbwparser/parser.py
import re
DELIMETER = ' '
def tokenize(rule_descs):
return [_normalize(rule_desc).split(DELIMETER) \
for rule_desc in rule_descs if not _blank(rule_desc)]
def _normalize(line):
return re.sub(r'\s+', DELIMETER, line.strip())
def _blank(line):
return line.strip() == ''编写parse_tokens()函数。
tokenize()的输出(List<List> tokens)是parse_tokens()函数的输入，parse_tokens()方法的输出是最终的Rule数据。
parse_tokens: (List<List<String>> tokens) -> (Rule rule)
在parse_tokens()中，遍历输入列表，列表的每个元素是一个规则的描述字段列表，通过parse_rule_tokens()函数先将这个规则描述解析为atom、and或or的Tuple类型的Rule数据。由于规则之间存在引用，所以用一个Key为Rule名称、Value为Rule数据的Map<String, Rule>保存由每个规则描述解析出的Rule名称和Rule数据。在parse_rule_tokens()中解析出的Rule数据要放入这个Map中。
parse_rule_tokens: (List<String> rule_tokens, Map<String, Rule>) -> void
parse_rule_tokens()内部要区分Rule的类型。
所以，parse_tokens()的实现步骤为：
- parse_atom
- parse_or
- parse_and
- parse_rule_tokens
- parse_tokens
其中，parse_atom()的输入是(List rule_tokens)，但or和and因为引用了其他Rule数据，parse_or()和parse_and()还需要Map作为第二个参数。它们的输出都是Rule数据，当然Rule数据的具体内容是不一样的。
parse_atom: (List<String> rule_tokens) -> (Rule atom_rule)
parse_or: (List<String> rule_tokens, Map<String, Rule> rule_map) -> (Rule or_rule)
parse_and: (List<String> rule_tokens, Map<String, Rule> rule_map) -> (Rule and_rule)
fbwparser/test_parser.py
def test_parse_atom(self):
self.assertEquals(atom(times(3), tofizz()),
parse_atom(['r1_3', 'atom', 'times', '3', 'to_fizz']))
self.assertEquals(atom(times(5), tobuzz()),
parse_atom(['r1_5', 'atom', 'times', '5', 'to_buzz']))
self.assertEquals(atom(times(7), towhizz()),
parse_atom(['r1_7', 'atom', 'times', '7', 'to_whizz']))
self.assertEquals(atom(contains(3), tofizz()),
parse_atom(['r3', 'atom', 'contains', '3', 'to_fizz']))
self.assertEquals(atom(alwaystrue(), tostr()),
parse_atom(['rd', 'atom', 'always_true', 'to_str']))fbwparser/parser.py
from rule import *
PREDICATION_MAP = {'times':lambda param: times(int(param)),
'contains':lambda param: contains(int(param)),
'always_true':lambda param: alwaystrue()}
ACTION_MAP = {'to_fizz':tofizz, 'to_buzz':tobuzz, 'to_whizz':towhizz, 'to_str':tostr}
def parse_atom(rule_tokens, _rule_map):
predication_type = _extract_predication_type(rule_tokens)
predication_param = _extract_predication_param(rule_tokens, predication_type)
action_type = _extract_action_type(rule_tokens, predication_type)
return atom(_parse_predication(predication_type, predication_param), _parse_action(action_type))
def _extract_predication_type(rule_tokens):
return rule_tokens[2]
def _extract_predication_param(rule_tokens, predication_type):
return None if predication_type == 'always_true' else rule_tokens[3]
def _extract_action_type(rule_tokens, predication_type):
return rule_tokens[3] if predication_type == 'always_true' else rule_tokens[4]
def _parse_predication(predication_type, predication_param):
return PREDICATION_MAP[predication_type](predication_param)
def _parse_action(action_type):
return ACTION_MAP[action_type]()fbwparser/test_parser.py
def test_parse_or(self):
r1_3 = atom(times(3), tofizz())
r1_5 = atom(times(5), tobuzz())
r1_7 = atom(times(7), towhizz())
rule_map = {'r1_3':r1_3, 'r1_5':r1_5, 'r1_7':r1_7}
self.assertEquals(ORN(r1_3, r1_5, r1_7),
parse_or(['r1', 'or', 'r1_3', 'r1_5', 'r1_7'], rule_map))fbwparser/parser.py
def parse_or(rule_tokens, rule_map):
ref_rules = [rule_map[rule_name] for rule_name in rule_tokens[2:]]
return ORN_list(ref_rules)fbwparser/test_parser.py
def test_parse_and(self):
r1_3 = atom(times(3), tofizz())
r1_5 = atom(times(5), tobuzz())
r1_7 = atom(times(7), towhizz())
rule_map = {'r1_3':r1_3, 'r1_5':r1_5, 'r1_7':r1_7}
self.assertEquals(ANDN(r1_3, r1_5, r1_7),
parse_and(['r1_357', 'and', 'r1_3', 'r1_5', 'r1_7'], rule_map))fbwparser/parser.py
def parse_and(rule_tokens, rule_map):
ref_rules = [rule_map[rule_name] for rule_name in rule_tokens[2:]]
return ANDN_list(ref_rules)测试代码和产品代码都有重复，重构一下。
fbwparser/test_parser.py
def setUp(self):
self.r1_3 = atom(times(3), tofizz())
self.r1_5 = atom(times(5), tobuzz())
self.r1_7 = atom(times(7), towhizz())
self.rule_map = {'r1_3':self.r1_3, 'r1_5':self.r1_5, 'r1_7':self.r1_7}
def test_parse_or(self):
self.assertEquals(ORN(self.r1_3, self.r1_5, self.r1_7),
parse_or(['r1', 'or', 'r1_3', 'r1_5', 'r1_7'], self.rule_map))
def test_parse_and(self):
self.assertEquals(ANDN(self.r1_3, self.r1_5, self.r1_7),
parse_and(['r1_357', 'and', 'r1_3', 'r1_5', 'r1_7'], self.rule_map))fbwparser/parser.py
def parse_or(rule_tokens, rule_map):
return ORN_list(_parser_ref_rules(rule_tokens, rule_map))
def parse_and(rule_tokens, rule_map):
return ANDN_list(_parser_ref_rules(rule_tokens, rule_map))
def _parser_ref_rules(rule_tokens, rule_map):
return [rule_map[rule_name] for rule_name in rule_tokens[2:]]先来解析atom rule tokens。
fbwparser/test_parser.py
def test_parse_rule_tokens_when_atom(self):
rule_map = {}
parse_rule_tokens(['r1_3', 'atom', 'times', '3', 'to_fizz'], rule_map)
self.assertEquals({'r1_3':self.r1_3}, rule_map)fbwparser/parser.py
def parse_rule_tokens(rule_tokens, rule_map):
rule_name = _extract_rule_name(rule_tokens)
rule_type = _extract_rule_type(rule_tokens)
if rule_type == 'atom':
rule_map[rule_name] = parse_atom(rule_tokens)
def _extract_rule_name(rule_tokens):
return rule_tokens[0]
def _extract_rule_type(rule_tokens):
return rule_tokens[1]再来解析or rule tokens。
fbwparser/test_parser.py
def test_parse_rule_tokens_when_or(self):
rule_map = {}
parse_rule_tokens(['r1_3', 'atom', 'times', '3', 'to_fizz'], rule_map)
parse_rule_tokens(['r1_5', 'atom', 'times', '5', 'to_buzz'], rule_map)
parse_rule_tokens(['r1_7', 'atom', 'times', '7', 'to_whizz'], rule_map)
parse_rule_tokens(['r1', 'or', 'r1_3', 'r1_5', 'r1_7'], rule_map)
self.assertEquals({'r1_3':self.r1_3, 'r1_5':self.r1_5, 'r1_7':self.r1_7,
'r1':ORN(self.r1_3, self.r1_5, self.r1_7)}, rule_map)fbwparser/parser.py
def parse_rule_tokens(rule_tokens, rule_map):
rule_name = _extract_rule_name(rule_tokens)
rule_type = _extract_rule_type(rule_tokens)
rule = None
if rule_type == 'atom':
rule = parse_atom(rule_tokens)
elif rule_type == 'or':
rule = parse_or(rule_tokens, rule_map)
rule_map[rule_name] = rule再来解析and rule tokens。
fbwparser/test_parser.py
def test_parse_rule_tokens_when_and(self):
rule_map = {}
parse_rule_tokens(['r1_3', 'atom', 'times', '3', 'to_fizz'], rule_map)
parse_rule_tokens(['r1_5', 'atom', 'times', '5', 'to_buzz'], rule_map)
parse_rule_tokens(['r1_7', 'atom', 'times', '7', 'to_whizz'], rule_map)
parse_rule_tokens(['r1_357', 'and', 'r1_3', 'r1_5', 'r1_7'], rule_map)
self.assertEquals({'r1_3':self.r1_3, 'r1_5':self.r1_5, 'r1_7':self.r1_7,
'r1_357':ANDN(self.r1_3, self.r1_5, self.r1_7)}, rule_map)fbwparser/parser.py
def parse_rule_tokens(rule_tokens, rule_map):
rule_name = _extract_rule_name(rule_tokens)
rule_type = _extract_rule_type(rule_tokens)
rule = None
if rule_type == 'atom':
rule = parse_atom(rule_tokens)
elif rule_type == 'or':
rule = parse_or(rule_tokens, rule_map)
elif rule_type == 'and':
rule = parse_and(rule_tokens, rule_map)
rule_map[rule_name] = rule重构一下产品代码。
fbwparser/parser.py
def parse_atom(rule_tokens, _rule_map):
predication_type = _extract_predication_type(rule_tokens)
predication_param = _extract_predication_param(rule_tokens, predication_type)
action_type = _extract_action_type(rule_tokens, predication_type)
return atom(parse_predication(predication_type, predication_param), parse_action(action_type))
RULE_TYPE_AND_FUNC_MAP = {'atom':parse_atom, 'or':parse_or, 'and':parse_and}
def parse_rule_tokens(rule_tokens, rule_map):
rule_name = _extract_rule_name(rule_tokens)
rule_type = _extract_rule_type(rule_tokens)
rule_map[rule_name] = RULE_TYPE_AND_FUNC_MAP[rule_type](rule_tokens, rule_map) fbwparser/test_parser.py
def test_parse_atom(self):
rule_map = {}
self.assertEquals(atom(times(3), tofizz()),
parse_atom(['r1_3', 'atom', 'times', '3', 'to_fizz'], rule_map))
self.assertEquals(atom(times(5), tobuzz()),
parse_atom(['r1_5', 'atom', 'times', '5', 'to_buzz'], rule_map))
self.assertEquals(atom(times(7), towhizz()),
parse_atom(['r1_7', 'atom', 'times', '7', 'to_whizz'], rule_map))
self.assertEquals(atom(contains(3), tofizz()),
parse_atom(['r3', 'atom', 'contains', '3', 'to_fizz'], rule_map))
self.assertEquals(atom(alwaystrue(), tostr()),
parse_atom(['rd', 'atom', 'always_true', 'to_str'], rule_map))说明：
- parse_atom()、parse_or()和parse_and()函数定义要放在MAP定义之前。
- parser_atom()函数原来只有一个参数rule_tokens，为了RULE_TYPE_AND_FUNC_MAP写起来简单，parse_atom()函数新增了_rule_map参数，为了标识实际没用，加了_的前缀，这样就跟parse_or()和parse_and()函数的参数形式一样了。受此影响，test_parse_atom()函数中调用的parse_atom()要增加rule_map参数。
最后解析Specification，其实在这之前parse_rule_tokens()的代码就已经写完了，这里只是用完整的Specification测试一下。
fbwparser/test_parser.py
def test_parse_rule_tokens_when_spec(self):
rule_map = {}
for rule_tokens in TestParser.SPEC_TOKENS:
parse_rule_tokens(rule_tokens, rule_map)
expected_rule_map = {
'r1_3':self.r1_3,
'r1_5':self.r1_5,
'r1_7':self.r1_7
}
r1 = ORN(self.r1_3, self.r1_5, self.r1_7)
expected_rule_map['r1'] = r1
r1_357 = ANDN(self.r1_3, self.r1_5, self.r1_7)
expected_rule_map['r1_357'] = r1_357
r1_35 = ANDN(self.r1_3, self.r1_5)
expected_rule_map['r1_35'] = r1_35
r1_37 = ANDN(self.r1_3, self.r1_7)
expected_rule_map['r1_37'] = r1_37
r1_57 = ANDN(self.r1_5, self.r1_7)
expected_rule_map['r1_57'] = r1_57
r2 = ORN(r1_357, r1_35, r1_37, r1_57)
expected_rule_map['r2'] = r2
r3 = atom(contains(3), tofizz())
expected_rule_map['r3'] = r3
rd = atom(alwaystrue(), tostr())
expected_rule_map['rd'] = rd
spec = ORN(r3, r2, r1, rd)
expected_rule_map['spec'] = spec
self.assertEquals(expected_rule_map, rule_map)fbwparser/test_parser.py
def test_parse_tokens(self):
self.assertEquals(spec(), parse_tokens(TestParser.RULE_TOKENS))fbwparser/parser.py
def parse_tokens(tokens):
rule_map = {}
for rule_tokens in tokens:
parse_rule_tokens(rule_tokens, rule_map)
return rule_map.get('spec')fbwparser/test_parser.py
def test_parse_rule_descs(self):
self.assertEquals(spec(), parse_rule_descs(TestParser.RULE_DESCS))fbwparser/parser.py
def parse_rule_descs(rule_descs):
return parse_tokens(tokenize(rule_descs))涉及到读取真实程序文件，不用单元测试保证，集成测试验证一下。
fbwparser/parser.py
def parse(prog_file_full_name):
with open(prog_file_full_name, 'r') as f:
rule = parse_rule_descs(f.readlines())
return rule解释器用的就是之前实现的Interpreter类，没有变化。
为了支持读取程序文件，fizzbuzzwhizz.py需要修改一下。
fizzbuzzwhizz.py
import sys
from fbwparser.parser import *
from interpreter import *
def run(prog_file_name):
prog_file_full_name = ''.join([sys.path[0], '/scripts/', prog_file_name])
_output(_run_spec(parse(prog_file_full_name)))
def _run_spec(s):
return [(n, apply_rule(s, n)) for n in range(1, 101)]
def _output(results):
for result in results:
print ' -> '.join([str(result[0]), result[1][1]])
if __name__ == '__main__':
run('prog_1.fbw')当prog_1.fbw内容如下时：
r1_3 atom times 3 to_fizz
r1_5 atom times 5 to_buzz
r1_7 atom times 7 to_whizz
r1 or r1_3 r1_5 r1_7
r1_357 and r1_3 r1_5 r1_7
r1_35 and r1_3 r1_5
r1_37 and r1_3 r1_7
r1_57 and r1_5 r1_7
r2 or r1_357 r1_35 r1_37 r1_57
r3 atom contains 3 to_fizz
rd atom always_true to_str
spec or r3 r2 r1 rd
FizzBuzzWhizz运行结果如下图所示：
稍微修改一下prog_1.fbw程序，将r3由“contains 3 to_fizz”改为“contains 5 to_buzz”：
r1_3 atom times 3 to_fizz
r1_5 atom times 5 to_buzz
r1_7 atom times 7 to_whizz
r1 or r1_3 r1_5 r1_7
r1_357 and r1_3 r1_5 r1_7
r1_35 and r1_3 r1_5
r1_37 and r1_3 r1_7
r1_57 and r1_5 r1_7
r2 or r1_357 r1_35 r1_37 r1_57
r3 atom contains 5 to_buzz
rd atom always_true to_str
spec or r3 r2 r1 rd
FizzBuzzWhizz运行结果如下图所示：
下面来编写一个从Program到Parser到Compiler的完整程序。
出于练习演示的目的，写了一个编译器，将AST核心数据编译成了函数式实现，以体现出编译器的作用———保持语义的等价语法变换。
函数式实现属于一种Embedded DSL，即利用Python语言支持的函数式特性构造了和AST一一对应的函数式实现模型。
当然也可以将AST核心数据编译成OO实现。OO实现也属于Embedded DSL，即利用Python语言的OO特性构造了和AST一一对应的面向对象实现模型。
在函数式实现和OO实现中均包含了语义接口、语义的语法表现和语义实现。
一般不会实现这种编译器，一般会编译成更底层的语言，并会做一些语义上的优化。
代码路径：
函数式实现：complete.compiler.functional
OO式实现：complete.compiler.oo
跟之前的prog_1.fbw一样，没有变化。
解析器用的就是之前实现的Parser类，没有变化。
test_all.py
import unittest
from tests.fbwparser.test_parser import TestParser
from tests.test_compiler import TestCompiler
if __name__ == '__main__':
unittest.main()test_compiler.py
import unittest
from compiler import *
from rule import *
class TestCompiler(unittest.TestCase):
def test_compile_predication(self):
self.assertTrue(compile_predication(times(3))(3))
self.assertFalse(compile_predication(times(3))(4))
self.assertTrue(compile_predication(contains(3))(3))
self.assertFalse(compile_predication(contains(3))(4))
self.assertTrue(compile_predication(alwaystrue())(-1))compiler.py
from impl import *
PREDICATION_MAP = {'TIMES':i_times, 'CONTAINS':i_contains, 'ALWAYSTRUE':i_alwaystrue}
def compile_predication(predication):
return PREDICATION_MAP[predication[0]](predication[1])impl.py
def i_times(base):
def predicate(n):
return n % base == 0
return predicate
def i_contains(digit):
def predicate(n):
return str(digit) in str(n)
return predicate
def i_alwaystrue(param):
def predicate(n):
return True
return predicate说明：
- impl.py是函数式实现模块。
- i_alwaystrue()本来是不带参数的，但为了PREDICATION_MAP写起来简单，加了一个无用的param占一下位。
test_compiler.py
def test_compile_action(self):
self.assertEquals('Fizz', compile_action(tofizz())(3))
self.assertEquals('Buzz', compile_action(tobuzz())(5))
self.assertEquals('Whizz', compile_action(towhizz())(7))
self.assertEquals('1', compile_action(tostr())(1))compiler.py
ACTION_MAP = {'TOFIZZ':i_tofizz, 'TOBUZZ':i_tobuzz, 'TOWHIZZ':i_towhizz, 'TOSTR':i_tostr}
def compile_action(action):
return ACTION_MAP[action]()impl.py
def i_tofizz():
def act(n):
return 'Fizz'
return act
def i_tobuzz():
def act(n):
return 'Buzz'
return act
def i_towhizz():
def act(n):
return 'Whizz'
return act
def i_tostr():
def act(n):
return str(n)
return acttest_compiler.py
def test_compile_atom(self):
r1_3 = atom(times(3), tofizz())
c_r1_3 = compile_atom(r1_3)
self.assertEquals((True, 'Fizz'), c_r1_3(6))
self.assertEquals((False, ''), c_r1_3(7))
r1_5 = atom(times(5), tobuzz())
c_r1_5 = compile_atom(r1_5)
self.assertEquals((True, 'Buzz'), c_r1_5(10))
self.assertEquals((False, ''), c_r1_5(11))
r1_7 = atom(times(7), towhizz())
c_r1_7 = compile_atom(r1_7)
self.assertEquals((True, 'Whizz'), c_r1_7(14))
self.assertEquals((False, ''), c_r1_7(13))
r3 = atom(contains(3), tofizz())
c_r3 = compile_atom(r3)
self.assertEquals((True, 'Fizz'), c_r3(3))
self.assertEquals((True, 'Fizz'), c_r3(13))
self.assertEquals((True, 'Fizz'), c_r3(31))
self.assertEquals((False, ''), c_r3(24))
rd = atom(alwaystrue(), tostr())
c_rd = compile_atom(rd)
self.assertEquals((True, '6'), c_rd(6))compiler.py
def compile_atom(atom_rule):
return i_atom(compile_predication(atom_rule[1]), compile_action(atom_rule[2]))涉及到递归调用，除了实现compile_or()，还要实现compile()的atom和or分支。
test_compiler.py
def test_compile_or(self):
r1_3 = atom(times(3), tofizz())
r1_5 = atom(times(5), tobuzz())
r1_7 = atom(times(7), towhizz())
or_35 = OR(r1_3, r1_5)
c_or_35 = compile_or(or_35)
self.assertEquals((True, 'Fizz'), c_or_35(6))
self.assertEquals((True, 'Buzz'), c_or_35(10))
self.assertEquals((True, 'Fizz'), c_or_35(15))
self.assertEquals((False, ''), c_or_35(7))
or_357 = ORN(r1_3, r1_5, r1_7)
c_or_357 = compile_or(or_357)
self.assertEquals((True, 'Fizz'), c_or_357(6))
self.assertEquals((True, 'Buzz'), c_or_357(10))
self.assertEquals((True, 'Whizz'), c_or_357(14))
self.assertEquals((False, ''), c_or_357(13))compiler.py
def compile_or(or_rule):
return i_or(compile(or_rule[1]), compile(or_rule[2]))
RULE_MAP = {'ATOM':compile_atom, 'OR':compile_or}
def compile(rule):
return RULE_MAP[rule[0]](rule)impl.py
def i_or(rule1, rule2):
def apply(n):
result1 = rule1(n)
if result1[0]:
return result1
return rule2(n)
return apply测试代码有重复，重构一下。
test_compiler.py
def setUp(self):
self.r1_3 = atom(times(3), tofizz())
self.r1_5 = atom(times(5), tobuzz())
self.r1_7 = atom(times(7), towhizz())
self.r3 = atom(contains(3), tofizz())
self.rd = atom(alwaystrue(), tostr())
def test_compile_atom(self):
c_r1_3 = compile_atom(self.r1_3)
self.assertEquals((True, 'Fizz'), c_r1_3(6))
self.assertEquals((False, ''), c_r1_3(7))
c_r1_5 = compile_atom(self.r1_5)
self.assertEquals((True, 'Buzz'), c_r1_5(10))
self.assertEquals((False, ''), c_r1_5(11))
c_r1_7 = compile_atom(self.r1_7)
self.assertEquals((True, 'Whizz'), c_r1_7(14))
self.assertEquals((False, ''), c_r1_7(13))
c_r3 = compile_atom(self.r3)
self.assertEquals((True, 'Fizz'), c_r3(3))
self.assertEquals((True, 'Fizz'), c_r3(13))
self.assertEquals((True, 'Fizz'), c_r3(31))
self.assertEquals((False, ''), c_r3(24))
c_rd = compile_atom(self.rd)
self.assertEquals((True, '6'), c_rd(6))
def test_compile_or(self):
or_35 = OR(self.r1_3, self.r1_5)
c_or_35 = compile_or(or_35)
self.assertEquals((True, 'Fizz'), c_or_35(6))
self.assertEquals((True, 'Buzz'), c_or_35(10))
self.assertEquals((True, 'Fizz'), c_or_35(15))
self.assertEquals((False, ''), c_or_35(7))
or_357 = ORN(self.r1_3, self.r1_5, self.r1_7)
c_or_357 = compile_or(or_357)
self.assertEquals((True, 'Fizz'), c_or_357(6))
self.assertEquals((True, 'Buzz'), c_or_357(10))
self.assertEquals((True, 'Whizz'), c_or_357(14))
self.assertEquals((False, ''), c_or_357(13))涉及到递归调用，除了实现compile_and()，还要实现compile()的and分支。
test_compiler.py
def test_compile_and(self):
and_35 = AND(self.r1_3, self.r1_5)
c_and_35 = compile_and(and_35)
self.assertEquals((False, ''), c_and_35(3))
self.assertEquals((False, ''), c_and_35(5))
self.assertEquals((True, 'FizzBuzz'), c_and_35(15))
self.assertEquals((False, ''), c_and_35(16))
and_357 = ANDN(self.r1_3, self.r1_5, self.r1_7)
c_and_357 = compile_and(and_357)
self.assertEquals((True, 'FizzBuzzWhizz'), c_and_357(3*5*7))
self.assertEquals((False, ''), c_and_357(104))compiler.py
def compile_and(and_rule):
return i_and(compile(and_rule[1]), compile(and_rule[2]))
RULE_MAP = {'ATOM':compile_atom, 'OR':compile_or, 'AND':compile_and}compile()其实已经完成了，这里用Specification测试用例验证一下。
test_compiler.py
def test_compile_spec(self):
c_spec = compile(spec());
self.assertEquals((True, 'Fizz'), c_spec(35))
self.assertEquals((True, 'FizzWhizz'), c_spec(21))
self.assertEquals((True, 'BuzzWhizz'), c_spec(70))
self.assertEquals((True, 'Fizz'), c_spec(9))
self.assertEquals((True, '1'), c_spec(1))因为要先编译，对比之前Interpreter的fizzbuzzwhizz，Compiler的fizzbuzzwhizz稍有不同。
fizzbuzzwhizz.py
import sys
from fbwparser.parser import *
from compiler import *
def run(prog_file_name):
prog_file_full_name = ''.join([sys.path[0], '/scripts/', prog_file_name])
_output(_run_spec(parse(prog_file_full_name)))
def _run_spec(s):
return [(n, compile(s)(n)) for n in range(1, 101)]
def _output(results):
for result in results:
print ' -> '.join([str(result[0]), result[1][1]])
if __name__ == '__main__':
run('prog_1.fbw')测试过程和结果同Interpreter。
由于编译前后的Predication、Action、Atom、Or和And等类虽然包名不同但类名相同，所以将编译后的Predication、Action、Atom、Or和And等类的类名都加上OO的前缀，并放到complete.compiler.oo.compiled路径下。
tests/test_all.py
import unittest
from tests.fbwparser.test_parser import TestParser
from tests.compiled.test_predication import TestTimes, TestContains, TestAlwaysTrue
from tests.compiled.test_action import TestToFizz, TestToBuzz, TestToWhizz, TestToStr
from tests.compiled.test_rule import TestAtom, TestOR, TestAND, TestRule
if __name__ == '__main__':
unittest.main()tests/compiled/test_predication.py
import unittest
from compiled.predication import *
class TestTimes(unittest.TestCase):
def test_times(self):
times3 = OOTimes(3)
self.assertTrue(times3.predicate(6))
self.assertFalse(times3.predicate(5))
class TestContains(unittest.TestCase):
def test_contains(self):
contains3 = OOContains(3)
self.assertTrue(contains3.predicate(13))
self.assertTrue(contains3.predicate(35))
self.assertTrue(contains3.predicate(300))
self.assertFalse(contains3.predicate(24))
class TestAlwaysTrue(unittest.TestCase):
def test_alwaysTrue(self):
alwaysTrue = OOAlwaysTrue()
self.assertTrue(alwaysTrue.predicate(1))
self.assertTrue(alwaysTrue.predicate(3))
self.assertTrue(alwaysTrue.predicate(5))compiled/predication.py
class OOPredication(object):
def predicate(self, n):
pass
class OOTimes(OOPredication):
def __init__(self, base):
self.base = base
def predicate(self, n):
return n % self.base == 0
class OOContains(OOPredication):
def __init__(self, digit):
self.digit = digit
def predicate(self, n):
return str(self.digit) in str(n)
class OOAlwaysTrue(OOPredication):
def predicate(self, n):
return Truetests/compiled/test_action.py
import unittest
from compiled.action import *
class TestToFizz(unittest.TestCase):
def test_toFizz(self):
toFizz = OOToFizz()
self.assertEquals('Fizz', toFizz.act(3))
class TestToBuzz(unittest.TestCase):
def test_toBuzz(self):
toBuzz = OOToBuzz()
self.assertEquals('Buzz', toBuzz.act(5))
class TestToWhizz(unittest.TestCase):
def test_toWhizz(self):
toWhizz = OOToWhizz()
self.assertEquals('Whizz', toWhizz.act(7))
class TestToStr(unittest.TestCase):
def test_toStr(self):
toStr = OOToStr()
self.assertEquals('1', toStr.act(1))
self.assertEquals('10', toStr.act(10))compiled/action.py
class OOAction(object):
def act(self, n):
pass
class OOToFizz(OOAction):
def act(self, n):
return 'Fizz'
class OOToBuzz(OOAction):
def act(self, n):
return 'Buzz'
class OOToWhizz(OOAction):
def act(self, n):
return 'Whizz'
class OOToStr(OOAction):
def act(self, n):
return str(n)tests/compiled/test_rule.py
import unittest
from compiled.rule import *
from compiled.predication import *
from compiled.action import *
class TestAtom(unittest.TestCase):
def test_atom_rule_1_3(self):
r1_3 = OOAtom(OOTimes(3), OOToFizz())
self.assertEquals((True, 'Fizz'), r1_3.apply(3))
self.assertEquals((False, ''), r1_3.apply(4))
def test_atom_rule_1_5(self):
r1_5 = OOAtom(OOTimes(5), OOToBuzz())
self.assertEquals((True, 'Buzz'), r1_5.apply(10))
self.assertEquals((False, ''), r1_5.apply(11))
def test_atom_rule_1_7(self):
r1_7 = OOAtom(OOTimes(7), OOToWhizz())
self.assertEquals((True, 'Whizz'), r1_7.apply(14))
self.assertEquals((False, ''), r1_7.apply(13))
class TestOR(unittest.TestCase):
def test_or_rule(self):
r1_3 = OOAtom(OOTimes(3), OOToFizz())
r1_5 = OOAtom(OOTimes(5), OOToBuzz())
or_35 = OOOR(r1_3, r1_5)
self.assertEquals((True, 'Fizz'), or_35.apply(6))
self.assertEquals((True, 'Buzz'), or_35.apply(10))
self.assertEquals((True, 'Fizz'), or_35.apply(15))
self.assertEquals((False, ''), or_35.apply(7))
class TestAND(unittest.TestCase):
def test_and_rule(self):
r1_3 = OOAtom(OOTimes(3), OOToFizz())
r1_5 = OOAtom(OOTimes(5), OOToBuzz())
and_35 = OOAND(r1_3, r1_5)
self.assertEquals((False, ''), and_35.apply(3))
self.assertEquals((False, ''), and_35.apply(5))
self.assertEquals((True, 'FizzBuzz'), and_35.apply(15))
self.assertEquals((False, ''), and_35.apply(16))
class TestRule(unittest.TestCase):
def test_rule_1(self):
r1_3 = OOAtom(OOTimes(3), OOToFizz())
r1_5 = OOAtom(OOTimes(5), OOToBuzz())
r1_7 = OOAtom(OOTimes(7), OOToWhizz())
r1 = OOOR3(r1_3, r1_5, r1_7)
self.assertEquals((True, 'Fizz'), r1.apply(6))
self.assertEquals((True, 'Buzz'), r1.apply(10))
self.assertEquals((True, 'Whizz'), r1.apply(14))
self.assertEquals((False, ''), r1.apply(13))
def test_rule_2(self):
r1_3 = OOAtom(OOTimes(3), OOToFizz())
r1_5 = OOAtom(OOTimes(5), OOToBuzz())
r1_7 = OOAtom(OOTimes(7), OOToWhizz())
r2 = OOOR4(OOAND3(r1_3, r1_5, r1_7),
OOAND(r1_3, r1_5),
OOAND(r1_3, r1_7),
OOAND(r1_5, r1_7))
self.assertEquals((False, ''), r2.apply(3))
self.assertEquals((False, ''), r2.apply(5))
self.assertEquals((False, ''), r2.apply(7))
self.assertEquals((True, 'FizzBuzzWhizz'), r2.apply(3*5*7))
self.assertEquals((False, ''), r2.apply(104))
self.assertEquals((True, 'FizzBuzz'), r2.apply(15))
self.assertEquals((False, ''), r2.apply(14))
self.assertEquals((True, 'FizzWhizz'), r2.apply(21))
self.assertEquals((False, ''), r2.apply(22))
self.assertEquals((True, 'BuzzWhizz'), r2.apply(35))
self.assertEquals((False, ''), r2.apply(34))
def test_rule_3(self):
r3 = OOAtom(OOContains(3), OOToFizz())
self.assertEquals((True, 'Fizz'), r3.apply(3))
self.assertEquals((True, 'Fizz'), r3.apply(13))
self.assertEquals((True, 'Fizz'), r3.apply(31))
self.assertEquals((False, ''), r3.apply(24))
def test_default_rule(self):
rd = OOAtom(OOAlwaysTrue(), OOToStr())
self.assertEquals((True, '1'), rd.apply(1))
self.assertEquals((True, '3'), rd.apply(3))
def test_spec(self):
s = spec()
self.assertEquals((True, 'Fizz'), s.apply(35))
self.assertEquals((True, 'FizzBuzz'), s.apply(15))
self.assertEquals((True, 'FizzWhizz'), s.apply(21))
self.assertEquals((True, 'BuzzWhizz'), s.apply(70))
self.assertEquals((True, 'Fizz'), s.apply(9))
self.assertEquals((True, '1'), s.apply(1))compiled/rule.py
class OORule(object):
def apply(self, n):
pass
class OOAtom(OORule):
def __init__(self, predication, action):
self.predication = predication
self.action = action
def apply(self, n):
if self.predication.predicate(n):
return True, self.action.act(n)
return False, ''
class OOOR(OORule):
def __init__(self, rule1, rule2):
self.rule1 = rule1
self.rule2 = rule2
def apply(self, n):
result1 = self.rule1.apply(n)
if result1[0]:
return result1
return self.rule2.apply(n)
class OOAND(OORule):
def __init__(self, rule1, rule2):
self.rule1 = rule1
self.rule2 = rule2
def apply(self, n):
result1 = self.rule1.apply(n)
if not result1[0]:
return False, ''
result2 = self.rule2.apply(n)
if not result2[0]:
return False, ''
return True, ''.join([result1[1], result2[1]])
def OOOR3(rule1, rule2, rule3):
return OOOR(rule1, OOOR(rule2, rule3))
def OOOR4(rule1, rule2, rule3, rule4):
return OOOR(rule1, OOOR3(rule2, rule3, rule4))
def OOAND3(rule1, rule2, rule3):
return OOAND(rule1, OOAND(rule2, rule3))
from compiled.predication import *
from compiled.action import *
def spec():
r1_3 = OOAtom(OOTimes(3), OOToFizz())
r1_5 = OOAtom(OOTimes(5), OOToBuzz())
r1_7 = OOAtom(OOTimes(7), OOToWhizz())
r1 = OOOR3(r1_3, r1_5, r1_7)
r2 = OOOR4(OOAND3(r1_3, r1_5, r1_7),
OOAND(r1_3, r1_5),
OOAND(r1_3, r1_7),
OOAND(r1_5, r1_7))
r3 = OOAtom(OOContains(3), OOToFizz())
rd = OOAtom(OOAlwaysTrue(), OOToStr())
return OOOR4(r3, r2, r1, rd)跟之前的prog_1.fbw一样，没有变化。
解析器用的就是之前实现的Parser类，没有变化。
test_compiler.py
import unittest
from compiler import *
from rule import *
class TestCompiler(unittest.TestCase):
def test_compile_predication(self):
self.assertTrue(compile_predication(times(3)).predicate(3))
self.assertFalse(compile_predication(times(3)).predicate(4))
self.assertTrue(compile_predication(contains(3)).predicate(3))
self.assertFalse(compile_predication(contains(3)).predicate(4))
self.assertTrue(compile_predication(alwaystrue()).predicate(-1))compiler.py
from compiled.predication import *
def c_times(base):
return OOTimes(base)
def c_contains(digit):
return OOContains(digit)
def c_alwaystrue(param):
return OOAlwaysTrue()
PREDICATION_MAP = {'TIMES':c_times, 'CONTAINS':c_contains, 'ALWAYSTRUE':c_alwaystrue}
def compile_predication(predication):
return PREDICATION_MAP[predication[0]](predication[1])test_compile.py
def test_compile_action(self):
self.assertEquals('Fizz', compile_action(tofizz()).act(3))
self.assertEquals('Buzz', compile_action(tobuzz()).act(5))
self.assertEquals('Whizz', compile_action(towhizz()).act(7))
self.assertEquals('1', compile_action(tostr()).act(1))compile.py
from compiled.action import *
def c_tofizz():
return OOToFizz()
def c_tobuzz():
return OOToBuzz()
def c_towhizz():
return OOToWhizz()
def c_tostr():
return OOToStr()
ACTION_MAP = {'TOFIZZ':c_tofizz, 'TOBUZZ':c_tobuzz, 'TOWHIZZ':c_towhizz, 'TOSTR':c_tostr}
def compile_action(action):
return ACTION_MAP[action]()test_compile.py
def setUp(self):
self.r1_3 = atom(times(3), tofizz())
self.r1_5 = atom(times(5), tobuzz())
self.r1_7 = atom(times(7), towhizz())
self.r3 = atom(contains(3), tofizz())
self.rd = atom(alwaystrue(), tostr())
def test_compile_atom(self):
c_r1_3 = compile_atom(self.r1_3)
self.assertEquals((True, 'Fizz'), c_r1_3.apply(6))
self.assertEquals((False, ''), c_r1_3.apply(7))
c_r1_5 = compile_atom(self.r1_5)
self.assertEquals((True, 'Buzz'), c_r1_5.apply(10))
self.assertEquals((False, ''), c_r1_5.apply(11))
c_r1_7 = compile_atom(self.r1_7)
self.assertEquals((True, 'Whizz'), c_r1_7.apply(14))
self.assertEquals((False, ''), c_r1_7.apply(13))
c_r3 = compile_atom(self.r3)
self.assertEquals((True, 'Fizz'), c_r3.apply(3))
self.assertEquals((True, 'Fizz'), c_r3.apply(13))
self.assertEquals((True, 'Fizz'), c_r3.apply(31))
self.assertEquals((False, ''), c_r3.apply(24))
c_rd = compile_atom(self.rd)
self.assertEquals((True, '6'), c_rd.apply(6))compile.py
from compiled.rule import *
def compile_atom(atom_rule):
return OOAtom(compile_predication(atom_rule[1]), compile_action(atom_rule[2]))涉及到递归调用，除了实现compile_or()，还要实现compile()的atom和or分支。
test_compile.py
def test_compile_or(self):
or_35 = OR(self.r1_3, self.r1_5)
c_or_35 = compile_or(or_35)
self.assertEquals((True, 'Fizz'), c_or_35.apply(6))
self.assertEquals((True, 'Buzz'), c_or_35.apply(10))
self.assertEquals((True, 'Fizz'), c_or_35.apply(15))
self.assertEquals((False, ''), c_or_35.apply(7))
or_357 = ORN(self.r1_3, self.r1_5, self.r1_7)
c_or_357 = compile_or(or_357)
self.assertEquals((True, 'Fizz'), c_or_357.apply(6))
self.assertEquals((True, 'Buzz'), c_or_357.apply(10))
self.assertEquals((True, 'Whizz'), c_or_357.apply(14))
self.assertEquals((False, ''), c_or_357.apply(13))compile.py
def compile_or(or_rule):
return OOOR(compile(or_rule[1]), compile(or_rule[2]))
RULE_MAP = {'ATOM':compile_atom, 'OR':compile_or}
def compile(rule):
return RULE_MAP[rule[0]](rule)涉及到递归调用，除了实现compile_and()，还要实现compile()的and分支。
test_compile.py
def test_compile_and(self):
and_35 = AND(self.r1_3, self.r1_5)
c_and_35 = compile_and(and_35)
self.assertEquals((False, ''), c_and_35.apply(3))
self.assertEquals((False, ''), c_and_35.apply(5))
self.assertEquals((True, 'FizzBuzz'), c_and_35.apply(15))
self.assertEquals((False, ''), c_and_35.apply(16))
and_357 = ANDN(self.r1_3, self.r1_5, self.r1_7)
c_and_357 = compile_and(and_357)
self.assertEquals((True, 'FizzBuzzWhizz'), c_and_357.apply(3*5*7))
self.assertEquals((False, ''), c_and_357.apply(104))compile.py
def compile_and(and_rule):
return OOAND(compile(and_rule[1]), compile(and_rule[2]))
RULE_MAP = {'ATOM':compile_atom, 'OR':compile_or, 'AND':compile_and}compile()其实已经完成了，这里用spec测试用例验证一下。
test_compile.py
def test_compile_spec(self):
c_spec = compile(spec());
self.assertEquals((True, 'Fizz'), c_spec.apply(35))
self.assertEquals((True, 'FizzWhizz'), c_spec.apply(21))
self.assertEquals((True, 'BuzzWhizz'), c_spec.apply(70))
self.assertEquals((True, 'Fizz'), c_spec.apply(9))
self.assertEquals((True, '1'), c_spec.apply(1))fizzbuzzwhizz.py
import sys
from fbwparser.parser import *
from compiler import *
def run(prog_file_name):
prog_file_full_name = ''.join([sys.path[0], '/scripts/', prog_file_name])
_output(_run_spec(parse(prog_file_full_name)))
def _run_spec(s):
return [(n, compile(s).apply(n)) for n in range(1, 101)]
def _output(results):
for result in results:
print ' -> '.join([str(result[0]), result[1][1]])
if __name__ == '__main__':
run('prog_1.fbw')测试过程和结果同Interpreter和Compiler Functional。
- 对问题领域进行深入分析，发现问题领域的核心需求；
- 通过核心需求驱动出计算模型和语义；
- 再围绕这个计算模型提供一套语言，给外面的人使用这个计算模型提供一个接口，这个接口可以是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通用语言提供的计算模型(通用计算机器)。
- 【必选】写一个解释器，把FizzBuzzWhizz中的整个Rule的关系树打印出来，测试用例之一如下：
def test_desc_spec(self):
self.assertEquals("{or, {atom, contains_3, to_fizz}, " \
"{or, {or, {and, {atom, times_3, to_fizz}, " \
"{and, {atom, times_5, to_buzz}, " \
"{atom, times_7, to_whizz}}}, " \
"{or, {and, {atom, times_3, to_fizz}, " \
"{atom, times_5, to_buzz}}, " \
"{or, {and, {atom, times_3, to_fizz}, " \
"{atom, times_7, to_whizz}}, " \
"{and, {atom, times_5, to_buzz}, " \
"{atom, times_7, to_whizz}}}}}, " \
"{or, {or, {atom, times_3, to_fizz}, " \
"{or, {atom, times_5, to_buzz}, " \
"{atom, times_7, to_whizz}}}, " \
"{atom, always_true, to_str}}}}",
desc(spec())) -
【可选】用函数式编程实现FizzBuzzWhizz。
-
【可选】写一个编译器，将FizzBuzzWhizz的AST核心数据编译为OO或函数式实现。
写一个解释器，把FizzBuzzWhizz中的整个Rule的关系树打印出来。
代码路径：complete.interpreter.ruledescriber
test_all.py
import unittest
from tests.test_interpreter import TestInterpreter
from tests.fbwparser.test_parser import TestParser
from tests.test_ruledescriber import TestRuleDescriber
if __name__ == '__main__':
unittest.main()test_ruledescriber.py
import unittest
from rule import *
from ruledescriber import *
class TestRuleDescriber(unittest.TestCase):
def test_desc_predication(self):
self.assertEquals("times_3", desc_predication(times(3)))
self.assertEquals("contains_3", desc_predication(contains(3)))
self.assertEquals("always_true", desc_predication(alwaystrue()))ruledescriber.py
def join_predication(typedesc):
def join_typedesc_param(param):
if not param:
return typedesc
return '_'.join([typedesc, str(param)])
return join_typedesc_param
PREDICATION_MAP = {'TIMES':join_predication('times'),
'CONTAINS':join_predication('contains'),
'ALWAYSTRUE':join_predication('always_true')}
def desc_predication(predication):
return PREDICATION_MAP[predication[0]](predication[1])test_ruledescriber.py
def test_desc_action(self):
self.assertEquals("to_fizz", desc_action(tofizz()))
self.assertEquals("to_buzz", desc_action(tobuzz()))
self.assertEquals("to_whizz", desc_action(towhizz()))
self.assertEquals("to_str", desc_action(tostr()))ruledescriber.py
ACTION_MAP = {'TOFIZZ':'to_fizz',
'TOBUZZ':'to_buzz',
'TOWHIZZ':'to_whizz',
'TOSTR':'to_str'}
def desc_action(action):
return ACTION_MAP[action]test_ruledescriber.py
def test_desc_atom(self):
self.assertEquals("{atom, times_3, to_fizz}", desc_atom(atom(times(3), tofizz())))
self.assertEquals("{atom, times_5, to_buzz}", desc_atom(atom(times(5), tobuzz())))
self.assertEquals("{atom, times_7, to_whizz}", desc_atom(atom(times(7), towhizz())))
self.assertEquals("{atom, contains_3, to_fizz}", desc_atom(atom(contains(3), tofizz())))
self.assertEquals("{atom, always_true, to_str}", desc_atom(atom(alwaystrue(), tostr())))ruledescriber.py
def join_rule(typedesc, param1desc, param2desc):
return ', '.join([typedesc, param1desc, param2desc])
def wrap_braces(s):
return '{%s}' % (s)
def desc_atom(atom_rule):
return wrap_braces(join_rule('atom', desc_predication(atom_rule[1]), desc_action(atom_rule[2])))涉及到递归调用，除了实现desc_or()，还要实现desc()的atom和or分支。
test_ruledescriber.py
def test_desc_or(self):
r1_3 = atom(times(3), tofizz())
r1_5 = atom(times(5), tobuzz())
r1_7 = atom(times(7), towhizz())
or_57 = OR(r1_5, r1_7)
self.assertEquals("{or, {atom, times_5, to_buzz}, {atom, times_7, to_whizz}}",
desc_or(or_57))
or_357 = ORN(r1_3, r1_5, r1_7)
self.assertEquals("{or, {atom, times_3, to_fizz}, " \
"{or, {atom, times_5, to_buzz}, " \
"{atom, times_7, to_whizz}}}",
desc_or(or_357))ruledescriber.py
def desc_or(or_rule):
return wrap_braces(join_rule('or', desc(or_rule[1]), desc(or_rule[2])))
RULE_MAP = {'ATOM':desc_atom, 'OR':desc_or}
def desc(rule):
return RULE_MAP[rule[0]](rule)涉及到递归调用，除了实现desc_and()，还要实现desc()的and分支。
test_ruledescriber.py
def test_desc_and(self):
r1_3 = atom(times(3), tofizz())
r1_5 = atom(times(5), tobuzz())
r1_7 = atom(times(7), towhizz())
and_57 = AND(r1_5, r1_7)
self.assertEquals("{and, {atom, times_5, to_buzz}, {atom, times_7, to_whizz}}",
desc_and(and_57))
and_357 = ANDN(r1_3, r1_5, r1_7)
self.assertEquals("{and, {atom, times_3, to_fizz}, " \
"{and, {atom, times_5, to_buzz}, " \
"{atom, times_7, to_whizz}}}",
desc_and(and_357)) ruledescriber.py
def desc_and(and_rule):
return wrap_braces(join_rule('and', desc(and_rule[1]), desc(and_rule[2])))
RULE_MAP = {'ATOM':desc_atom, 'OR':desc_or, 'AND':desc_and}desc()其实已经完成了，这里用Specification测试用例验证一下。
test_ruledescriber.py
def test_desc_spec(self):
self.assertEquals("{or, {atom, contains_3, to_fizz}, " \
"{or, {or, {and, {atom, times_3, to_fizz}, " \
"{and, {atom, times_5, to_buzz}, " \
"{atom, times_7, to_whizz}}}, " \
"{or, {and, {atom, times_3, to_fizz}, " \
"{atom, times_5, to_buzz}}, " \
"{or, {and, {atom, times_3, to_fizz}, " \
"{atom, times_7, to_whizz}}, " \
"{and, {atom, times_5, to_buzz}, " \
"{atom, times_7, to_whizz}}}}}, " \
"{or, {or, {atom, times_3, to_fizz}, " \
"{or, {atom, times_5, to_buzz}, " \
"{atom, times_7, to_whizz}}}, " \
"{atom, always_true, to_str}}}}",
desc(spec())) 用函数式编程实现FizzBuzzWhizz。
可参考代码路径：functional
写一个编译器，将FizzBuzzWhizz的AST核心数据编译为OO或函数式实现。
可参考代码路径：complete.compiler.oo 或 complete.compiler.functional