forked from jerrypnz/moonranger.github.com
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathpython-pattern-matching.html
277 lines (239 loc) · 10.1 KB
/
python-pattern-matching.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<link rel="Stylesheet" type="text/css" href="css/style.css" />
<title>Jerry的个人维基</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
</head>
<body>
<div id="navbar">
<ul>
<li> <a href="http://jerrypeng.me">Blog</a> </li>
<li> <a class="activated" href="index.html">WIKI</a> </li>
<li> <a href="https://github.com/moonranger">Github</a> </li>
<li> <a href="about.html">About</a> </li>
<li class="search">
<form action="http://www.google.com/search" method="get">
<input name="sitesearch" value="http://wiki.jerrypeng.me/" type="hidden" />
<input name="hl" value="zh-CN" type="hidden" />
<input name="ie" value="UTF-8" type="hidden" />
<input size="25" name="q" id="query" value="Search..." type="text"
onfocus="if( this.value=='Search...') {this.value='' };"
onblur="if( this.value=='') {this.value='Search...' };" />
</form>
</li>
</ul>
</div>
<div id="content">
<h1 id="toc_1"> Python Pattern Matching</h1>
<h2 id="toc_1.1">1. Intro</h2>
<p>
最近在做的项目，是一个用Python实现的代理程序，服务端程序是另一个同事用Erlang实现的。
虽然我对Erlang了解不多，但对其必杀特性之一模式匹配（Pattern Matching）早有耳闻，因此花了点时间了解了一下。
模式匹配是Erlang语言的核心特性之一，在case, receive等语句中都可以使用，但这篇文章只考虑函数定义中的模式匹配，
因为我试图用Python去山寨的也是这一特性。
</p>
<p>
在函数定义中用模式匹配是为了用声明式的风格来替代本来需要用一连串的if...else...才能表达的逻辑，方便维护和修改。
下面这段从learnyousomeerlang网站上找到的代码是一个很好的例子（原文:<a href="http://learnyousomeerlang.com/syntax-in-functions">http://learnyousomeerlang.com/syntax-in-functions</a>)：
</p>
<p>
通常的if...else...式写法：
</p>
<pre class="brush: erlang;">
function greet(Gender,Name)
if Gender == male then
print("Hello, Mr. %s!", Name)
else if Gender == female then
print("Hello, Mrs. %s!", Name)
else
print("Hello, %s!", Name)
end
</pre>
<p>
使用模式匹配的写法：
</p>
<pre class="brush: erlang;">
greet(male, Name) ->
io:format("Hello, Mr. ~s!", [Name]);
greet(female, Name) ->
io:format("Hello, Mrs. ~s!", [Name]);
greet(_, Name) ->
io:format("Hello, ~s!", [Name]).
</pre>
<p>
基于函数的模式匹配乍一看有点像Java，C++里函数重载，但函数重载是静态语言的编译时特性，模式匹配则完全是运行时行为。
模式匹配的更多细节可以参考Erlang的教程、文章，这里不再详述。
</p>
<p>
下面要说的是如何用Python实现一个最简单的模式匹配功能，在这个过程中介绍一下decorator的用法。
</p>
<h2 id="toc_1.2">2. What Does It Look Like?</h2>
<p>
第一个要考虑的问题是如何用Python已有的语言特性来表达模式匹配。因为Python的函数不支持这种特性，所以必须要将函数强化一下才有可能实现模式匹配。
毫无疑问，decorator必然会派上用场的。decorator本身是支持参数化构造的——这意味着用decorator的参数来表达模式最合适不过了。
顺着这个思路，上面那段函数定义的等价Python实现可以出炉了：
</p>
<pre class="brush: python;">
@match("male")
def greet(male, name):
print "Hello, Mr. %s" % name
@match("female")
def greet(female, name):
print "Hello, Mrs. %s" % name
@match()
def greet(_, name):
print "Hello, %s" % name
</pre>
<p>
match这个装饰器的目的就是为对应的函数描述其需要满足的Pattern，match的参数和函数本身的参数对应，但可能少于函数实际参数的个数，
因为并不是每一个参数都需要做模式匹配。比如上面头两个greet函数都只匹配第一个参数的值。关于这一点，看函数调用的写法就能明白了：
</p>
<pre class="brush: python;">
greet('male', 'Cooper')
greet('female', 'Geller')
greet('', 'Drizzt')
</pre>
<p>
运行结果：
</p>
<pre class="brush: plain;">
Hello, Mr. Cooper
Hello, Mrs. Geller
Hello, Drizzt
</pre>
<p>
现在的问题是如何实现match这个decorator了。
</p>
<h2 id="toc_1.3">3. How It Is Implemented?</h2>
<p>
基本的思路是这样的：
</p>
<ol>
<li>
按函数名将一组函数及其pattern组织到一起
</li>
<li>
将这些函数替换成一个统一的入口函数
</li>
<li>
入口函数根据参数去寻找最匹配的实现函数并调用
</li>
</ol>
<p>
下面是对应的代码：
</p>
<pre class="brush: python;">
class PatternError(Exception):
pass
class _PatternGroup(object):
"""match matching for python"""
patterns_matchers = {}
def __init__(self):
super(_PatternGroup, self).__init__()
self._rules = []
def _add_pattern(self, fn, *args, **kwargs):
self._rules.append(((args, kwargs), fn))
return self._run
def _run(self, *args, **kwargs):
retval = None
for rule, fn in self._rules:
if self._match(rule, (args, kwargs)):
retval = fn(*args, **kwargs)
break
else:
raise PatternError("No match found")
return retval
def _match(self, rule, val):
pargs, pkwargs = rule
args, kwargs = val
for actual, expected in itertools.izip(args, pargs):
if actual != expected:
return False
for key, expectedval in pkwargs.iteritems():
if not key in kwargs or kwargs[key] != expectedval:
return False
return True
def match(*args, **kwargs):
def _do_match(fn):
fname = fn.__name__ #FIXME Problem 1: Should not only use function name as the key
if fname in _PatternGroup.patterns_matchers:
return _PatternGroup.patterns_matchers[fname]._add_pattern(fn, *args, **kwargs)
else:
matcher = _PatternGroup()
_PatternGroup.patterns_matchers[fname] = matcher
return matcher._add_pattern(fn, *args, **kwargs)
return _do_match
</pre>
<p>
非常简陋，还有很多问题：
</p>
<ol>
<li>
用函数的名称来当作一组pattern的key是很不靠谱的，一旦有不同模块的同名函数就有问题
</li>
<li>
因为self的缘故，不支持class的instance method
</li>
<li>
match的算法很简陋，找到第一个能匹配上的就返回了，实际应该找到最匹配的函数
</li>
</ol>
<p>
实现完以后发现这个东西没有太多实用价值，只能当作玩具而已，因此是否要写这篇文章我也犹豫了好几天。
想来想去还是记录下来，当作分享自己探索以及玩乐的过程罢了，不必较真。
</p>
<h2 id="toc_1.4">4. What Others Have Done</h2>
<p>
在实现完自己的简单Pattern Matching后，我也在Google上搜索了一番，还真有人跟我做了同样的事情，
而且比我的要成熟得多，有兴趣的话可以看看人家的实现。
</p>
<p>
Python Pattern Matching
<a href="http://svn.colorstudy.com/home/ianb/recipes/patmatch.py">http://svn.colorstudy.com/home/ianb/recipes/patmatch.py</a>
</p>
<p>
Thoughts About the Erlang Runtime
<a href="http://blog.ianbicking.org/2008/06/09/thoughts-about-the-erlang-runtime/">http://blog.ianbicking.org/2008/06/09/thoughts-about-the-erlang-runtime/</a>
</p>
</div>
<!--
<div id="disqus_thread"></div>
<script type="text/javascript">
/* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */
var disqus_shortname = 'moonranger'; // required: replace example with your forum shortname
/* * * DON'T EDIT BELOW THIS LINE * * */
(function() {
var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
dsq.src = 'http://' + disqus_shortname + '.disqus.com/embed.js';
(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>
<noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
<a href="http://disqus.com" class="dsq-brlink">blog comments powered by <span class="logo-disqus">Disqus</span></a>
-->
</body>
<script type="text/javascript" src="scripts/shCore.js"></script>
<script type="text/javascript" src="scripts/shBrushJScript.js"></script>
<script type="text/javascript" src="scripts/shBrushBash.js"></script>
<script type="text/javascript" src="scripts/shBrushCpp.js"></script>
<script type="text/javascript" src="scripts/shBrushCSharp.js"></script>
<script type="text/javascript" src="scripts/shBrushCss.js"></script>
<script type="text/javascript" src="scripts/shBrushDiff.js"></script>
<script type="text/javascript" src="scripts/shBrushErlang.js"></script>
<script type="text/javascript" src="scripts/shBrushGroovy.js"></script>
<script type="text/javascript" src="scripts/shBrushJava.js"></script>
<script type="text/javascript" src="scripts/shBrushJScript.js"></script>
<script type="text/javascript" src="scripts/shBrushPerl.js"></script>
<script type="text/javascript" src="scripts/shBrushPhp.js"></script>
<script type="text/javascript" src="scripts/shBrushPlain.js"></script>
<script type="text/javascript" src="scripts/shBrushPython.js"></script>
<script type="text/javascript" src="scripts/shBrushRuby.js"></script>
<script type="text/javascript" src="scripts/shBrushScala.js"></script>
<script type="text/javascript" src="scripts/shBrushSql.js"></script>
<script type="text/javascript" src="scripts/shBrushXml.js"></script>
<script type="text/javascript" src="scripts/shBrushClojure.js"></script>
<link type="text/css" rel="stylesheet" href="styles/shCoreDefault.css"/>
<link type="text/css" rel="stylesheet" href="styles/shThemeRDark.css"/>
<script type="text/javascript">SyntaxHighlighter.all();</script>
</html>