Python: パターンマッチしてみる

なんか、趣味では最近はC言語ばっかりだったりするわけですが。

さて、関数型言語系をカジった人なら誰しも取り付かれる、モノ、それがパターンマッチ。パターンマッチが使えると、とにかく直感的にコードをかけますよね。

つーわけで、Pythonでパターンマッチを実装してみました。機能的には

  • リスト,タプルに対するパターンマッチ
  • パターン変数への束縛
  • ガード条件
  • 任意のオブジェクトに対するパターンマッチ
  • 部分パターンの束縛(Ocamlのas)

あたりを実装してみました。これだけあれば、かなり便利にコードをかけます。できるだけ、手軽に書けるように工夫してみました。こんな感じです。

変数束縛とガード。getattrでごにょごにょしてるので簡単にかけます。

python code
  1. m = Match([1,2,3])
  2. if m.when([1,2,m.var]) and m.var > 2:
  3.   print m.var
  4. # >> 3
  5.  

こう使えば、Pythonに念願のswitchが！

python code
  1. m = Match(10)
  2. if m(9):
  3.   print 1
  4. elif m(10):
  5.   print 2
  6. else:
  7.   False
  8. # >> 2
  9.  

部分パターンを束縛してみます。[1,2,m.var]全体をallというパターン変数に束縛します。

python code
  1. m = Match([1,2,3])
  2. if m.when([1,2,m.var]) and m.var > 5:
  3.   False
  4. elif m.when(m._as_all([1,2,m.var])):
  5.   print m.all
  6.   print m.var
  7. else:
  8.   raise StandardError("")
  9. # >> [1, 2, 3]
  10. # >> 3
  11.  

任意のオブジェクトにも使えます。いわゆるレコードに対するマッチも簡単にできるということです。

python code
  1. class Test(object):
  2.   def __init__(self, v1, v2):
  3.     self.v1 = v1
  4.     self.v2 = v2
  5.   def __repr__(self):
  6.     return "Test(%s, %s)"%(repr(self.v1), repr(self.v2))
  7. m = Match([1, Test(2, 3)])
  8. if m.when([1, m._class(Test, {"v1":2, "v2": m.v2})]):
  9.   print m.v2
  10. else:
  11.   False
  12. # >> 3
  13.  

オブジェクトに対するパターンマッチは__match__メソッドを定義するとカスタマイズできます。ここらのアイデアはScalaからいただきました。

python code
  1. class Test2(Test):
  2.   def __match__(self):
  3.     return {"value": self.v1 + self.v2}
  4. m = Match([1, 2, Test2(3,4)])
  5. if m.when([1,2, m._class(Test2, {"value": m.var})]):
  6.   m.var
  7. else:
  8.   False
  9. # >> 7
  10.  

結構いい感じな気がします。

ダウンロード

patternmatch.py

実装のお話

ソースコードはこんな感じ。

python code
  1. class Match(object):
  2.   class _var(str): pass
  3.   class _class(object):
  4.     def __init__(self, klass, attrs):
  5.       self.klass= klass
  6.       self.attrs= sorted(attrs.iteritems())
  7.     def match(self, m, obj):
  8.       props = getattr(obj, "__match__", lambda: obj.__dict__)()
  9.       return issubclass(obj.__class__, self.klass) and \
  10.             m.when(self.attrs, sorted(props.iteritems()))
  11.   class _as(object):
  12.     def __init__(self, name, pattern = None):
  13.       self.name = name
  14.       self.pattern = pattern
  15.     def __call__(self, pattern):
  16.       self.pattern = pattern
  17.       return self
  18.  
  19.   def __init__(self, obj):
  20.     self.obj = obj
  21.     self.bind = {}
  22.  
  23.   def __getitem__(self, key):
  24.     if not self.bind.has_key(key):
  25.       if key.startswith("_as_"):
  26.         return self._as(self._var(key[4:]))
  27.       return self._var(key)
  28.     return self.bind[key]
  29.   __getattr__ = __getitem__
  30.   __call__ = lambda self, *a, **k : self.when(*a, **k)
  31.  
  32.   def when(self, pattern, obj = None):
  33.     if not obj: obj = self.obj
  34.     if isinstance(pattern, (self._var, self._class, self._as)):
  35.       if isinstance(obj, (list, tuple)):
  36.         pattern = [pattern]
  37.         obj = [obj]
  38.  
  39.     if not isinstance(obj, (list, tuple)) and \
  40.       not isinstance(pattern, (list, tuple)) :
  41.       obj = [obj]
  42.       pattern = [pattern]
  43.  
  44.     if not isinstance(obj, (list, tuple)) or \
  45.       not isinstance(pattern, (list, tuple)) :
  46.       self.bind = {}
  47.       return False
  48.  
  49.     if len(obj) != len(pattern):
  50.       if not ((pattern[-1].__class__ == self._var) and pattern[-1].startswith("__")):
  51.         self.bind = {}
  52.         return False
  53.  
  54.     for i, (value, pat) in enumerate(zip(obj, pattern)):
  55.       if value == pat:
  56.         continue
  57.       elif pat.__class__ == self._var and pat.startswith("__"):
  58.         self.bind[str(pat)] = obj[i:]
  59.         return True
  60.       elif pat.__class__ == self._var:
  61.         self.bind[str(pat)] = value
  62.       elif pat.__class__ == self._class:
  63.         if not pat.match(self, value):
  64.           self.bind ={}
  65.           return False
  66.       elif pat.__class__ == self._as:
  67.         if not self.when(pat.pattern, value):
  68.           self.bind ={}
  69.           return False
  70.         self.bind[str(pat.name)] = value
  71.       elif isinstance(value, (list, tuple)) and isinstance(pat, (list,tuple)):
  72.         if not self.when(pat, value):
  73.           self.bind = {}
  74.           return False
  75.       else:
  76.         self.bind = {}
  77.         return False
  78.  
  79.     return True
  80.  

まぁわりかしシンプルですね。

今年も終わりが近づいてまいりました。年をとると時間がすぎるのが速いナァ･･･と痛感しております。

12.11.08/01am
Posted at:
12.11.08/01am
Tags:
Comments:
0
Permalink

Python: S式パーサライブラリを作りました

前のエントリーで簡易S式パーサをre.Scannerで作ったのですが、まぁ個人的にまとめておいたほうが後々使えるだろう、ということでライブラリにまとめました。ダンパもついているので、S式の読み込みの他、PythonオブジェクトをS式で出力することができます。

実装には引き続きre.Scannerを活用しています。おかげで短い行数でキレイにかけているのではないかと。

ダウンロード

simplesexp.py

ソースはこんな感じ（テストのぞく）。

python code
  1. import re, sys
  2. from unicodedata import east_asian_width
  3.  
  4. try:
  5.   from re import Scanner
  6. except ImportError:
  7.   from sre import Scanner
  8.  
  9. class ParseError(StandardError): pass
  10.  
  11. class Ident(unicode):
  12.   def __repr__(self):
  13.     return "Ident(%s)"%unicode.__repr__(self)
  14.  
  15. class Symbol(unicode):
  16.   def __repr__(self):
  17.     return "Symbol(%s)"%unicode.__repr__(self)
  18.  
  19. class Pair(list):
  20.   def __repr__(self):
  21.     return "Pair(%s)"%list.__repr__(self)
  22.  
  23. class Token(object):
  24.   def __init__(self, value, pos):
  25.     self.value = value
  26.     self.pos = pos
  27.   def __repr__(self):
  28.     return repr(self.value)
  29.  
  30. class Binding(object):
  31.   def __init__(self, dct):
  32.     self.dct = dict(((k, k.__class__), v) for k,v in dct.iteritems())
  33.   __contains__ = lambda self, key: (key, key.__class__) in self.dct
  34.   __getitem__ = lambda self,key: self.dct[(key, key.__class__)]
  35.  
  36. default_binding = {"#t":True, "true":True, "#f":False, "false":False, "nil":None, "dict":Ident(u'alist->hash-table')}
  37.  
  38. class Reader(object):
  39.   PAREN = {"]":"[", ")":"("}
  40.   def __init__(self, binding=None, symbol_marker="'", use_dict=True):
  41.     self.binding = binding or default_binding
  42.     self.symbol_marker = symbol_marker
  43.     self.use_dict = use_dict
  44.  
  45.   def read(self, value):
  46.     self.result = []
  47.     self.paren_stack = []
  48.     self.source = value
  49.     self.pos = 0
  50.     self.scanner = Scanner([
  51.       (r"\s+", self("skip")),
  52.       (r";[^\n]*\n", self("skip")),
  53.       (r""""(((?<=\\)")|[^"])*((?<!\\)")""", self("str")),
  54.       (r"(\(|\[)", self("open")),
  55.       (r"(\)|\])", self("close")),
  56.       (r"(([\d]+|(((\d+)?\.[\d]+)|([\d]+\.)))e[\+\-]?[\d]+)|(((\d+)?\.[\d]+)|([\d]+\.))", self("number")),
  57.       (r"\-?((0x[\da-f]+)|(0[0-7]+)|([1-9][\d]*)|0)[l]?", self("number")),
  58.       (r"""%s([^\(\[\)\]\s"]+)"""%self.symbol_marker, self("symbol")),
  59.       (r"""([^\(\[\)\]\s"]+)""", self("ident")),
  60.       (r"""".*""", self("unterm_str")),
  61.       (r".*", self("unknown_token"))
  62.     ], re.M|re.S|re.I)
  63.     self.scanner.scan(self.source)
  64.     if self.paren_stack:
  65.       self.raise_error("missing closing parenthesis.")
  66.     return self.parse(self.result)
  67.  
  68.   def append(self, v):
  69.     self.last().append(Token(v, self.pos))
  70.  
  71.   def __call__(self, name):
  72.     def _(scanner, s):
  73.       self.pos += len(s)
  74.       return getattr(self, name)(s)
  75.     return _
  76.  
  77.   def unknown_token(self,s): self.raise_error("unknown token: %s"%s)
  78.   def skip(self, _): pass
  79.   def open(self, s):
  80.       new_lst = []
  81.       self.last().append(new_lst)
  82.       self.paren_stack.append([s, new_lst])
  83.   def close(self, s):
  84.       if not self.paren_stack:
  85.         self.raise_error("missing opening parenthesis.")
  86.       if self.PAREN[s] != self.paren_stack.pop()[0]:
  87.         self.raise_error("missing closing parenthesis.")
  88.   def str(self, s): self.append(eval('u""'+s+'""'))
  89.   def unterm_str(self, s): self.raise_error("unterminated string literal.")
  90.   def number(self, s): self.append(eval(s))
  91.   def symbol(self, s): self.append(Symbol(s[1:]))
  92.   def ident(self, s):
  93.     if s in self.binding:
  94.       self.append(self.binding[s])
  95.     else:
  96.       self.append(Ident(s))
  97.  
  98.   def last(self):
  99.     if self.paren_stack:
  100.       return self.paren_stack[-1][1]
  101.     else:
  102.       return self.result
  103.  
  104.   def parse(self, rs):
  105.     def is_ident(value, expected):
  106.       return getattr(value,"value", None) == Ident(expected)
  107.     def is_pair(rs):
  108.       return getattr(rs, "__len__", lambda :0)()==3 and is_ident(rs[1], u".")
  109.  
  110.     if isinstance(rs, list):
  111.       if not len(rs):
  112.         return []
  113.       elif self.use_dict and is_ident(rs[0], u"alist->hash-table"):
  114.         if len(rs) != 2:
  115.           self.raise_error("alist->hash-table: expected 1 arguments, got %d."%(len(rs)-1), rs[0].pos)
  116.         if not all(is_pair(a) for a in rs[1]):
  117.           self.raise_error("alist->hash-table: aruguments must be alist", rs[0].pos)
  118.         return dict((self.parse(i[0]), self.parse(i[2])) for i in rs[1])
  119.       elif len(rs)!=3 and any(is_ident(t, u".") for t in rs):
  120.         self.raise_error('illegal use of "."', rs[0].pos)
  121.       elif is_pair(rs):
  122.         parsed = self.parse(rs[2])
  123.         if not isinstance(rs[2], list):
  124.           return Pair([rs[0].value, parsed])
  125.         if isinstance(parsed, Pair):
  126.           return Pair([rs[0].value, parsed])
  127.         elif isinstance(parsed, list):
  128.           return [rs[0].value]+parsed
  129.         else:
  130.           return [rs[0].value, parsed]
  131.       else:
  132.         return map(self.parse, rs)
  133.     else:
  134.       return rs.value
  135.  
  136.   def raise_error(self, msg="parse error", pos=None, range=3):
  137.     pos = pos or self.pos
  138.     lines = self.source.split("\n")
  139.     curline = self.source[:pos].count("\n")
  140.     linepos = pos - len("\n".join(lines[:curline]))
  141.     buf = ["\n"]
  142.     for i in xrange(max(0, curline-range), curline+1):
  143.       buf.append("% 5d: %s"%(i+1, lines[i]))
  144.     width = 7 + sum(east_asian_width(c) == 'W' and 2 or 1 for c in unicode(lines[i]))
  145.     buf.append("%s~"%(" "*width))
  146.     buf.append("line %d, %d: %s"%(curline+1,linepos, msg))
  147.     raise ParseError(("\n".join(buf)).encode(sys.stderr.encoding))
  148.  
  149. class Dumper(object):
  150.   def __init__(self, binding=None ,symbol_marker="'"):
  151.     binding = binding or default_binding
  152.     self.binding = Binding(dict(zip(binding.values(), binding)))
  153.     self.symbol_marker = symbol_marker
  154.  
  155.   def dump(self, obj):
  156.     result = self.to_sexp(obj, [])
  157.     if isinstance(result, list) and len(result) and result[0]=="(":
  158.       result = result[1:-1]
  159.     return u" ".join(result)
  160.  
  161.   def to_sexp(self, obj, result):
  162.     ap = result.append
  163.     tos = lambda v: self.to_sexp(v, result)
  164.     if isinstance(obj, Pair):
  165.       ap("(")
  166.       tos(obj[0])
  167.       ap(" . ")
  168.       tos(obj[1])
  169.       ap(")")
  170.     elif isinstance(obj, (tuple, list)):
  171.       ap("(")
  172.       map(tos, obj)
  173.       ap(")")
  174.     else:
  175.       if isinstance(obj, dict):
  176.         ap("( alist->hash-table ")
  177.         tos([(k, Ident(u"."), v) for k,v in obj.items()])
  178.         ap(" ) ")
  179.       elif obj in self.binding:
  180.         ap(unicode(Ident(self.binding[obj])))
  181.       elif isinstance(obj, Symbol):
  182.         ap(u"'%s"%unicode(obj))
  183.       elif isinstance(obj, (Ident,int, float, long)):
  184.         ap(unicode(obj))
  185.       else:
  186.         s = unicode(repr(obj)).decode("unicode_escape")
  187.         m = re.match(r"""^[u|r]?["|'](.*)["|']$""", s, re.M|re.S)
  188.         if m:
  189.           s = m.group(1)
  190.         ap("\"%s\""%s.replace('"','\\"').replace("\\'","'"))
  191.     return result
  192.  
  193. dumper = Dumper()
  194. read = Reader().read
  195. dump = dumper.dump
  196.  

概要

特徴は

  • 辞書を定義できる
  • ドット対に対応
  • 識別子に対して、任意のバインディングを指定できる
  • わりとちゃんとエラー表示される
  • シンボル表記、数値表記(python表記)に対応

といった当たりでしょうか。具体的にはテストコードを見てもらうと分かるかと。

 code
  1. (あああ hoge->fuga123 (1 . (2 . 3)) "hoge\\"hoge" ;comment2
  2. foo "aaa" #t <= 'foo
  3. "hogehoge
  4. foo
  5. " (5 . (6 .()))
  6. )
  7. (dict (
  8.   ("いいい" .
  9.     (alist->hash-table (
  10.       ("a-1" . "vvv")
  11.       ("a-2" . (
  12.         hoge foo bar
  13.       ))
  14.     )))
  15. ))
  16. (10 1L -45 010 0x10 -10 -0x10 3.14 10. .001 1e100 3.14e-10 0e0)
  17. ; comment3 ()(
  18.  
  19. """)
  20.  

という感じのS式が

python code
  1.   [
  2.     [Ident(u'あああ'), Ident(u'hoge->fuga123'), Pair([1, Pair([2, 3])]), u'hoge"hoge',
  3.     Ident(u'foo'), u'aaa', True, Ident(u'<='), Symbol(u'foo'),
  4.     u'hogehoge\nfoo\n', [5,6]],
  5.     {u'いいい':
  6.       {u'a-1': u'vvv',
  7.       u'a-2': [Ident(u'hoge'), Ident(u'foo'), Ident(u'bar')]}},
  8.     [10, 1L, -45, 010, 0x10, -10, -0x10, 3.14, 10., .001, 1e100, 3.14e-10, 0e0]
  9.   ]
  10.  

となります。IdentやSymbolはunicodeのサブクラス、Pairはリストのサブクラスになっているので、違和感なく使えると思います。

また、alist->hash-tableで辞書が作れます。デフォルトでdictにalist->hash-tableをバインドしてますので、dictでも辞書が作れます。この機能はオンオフ切り替えも可能です。

その他、#tをTrueなどSchemeっぽくデフォルトバインディングが用意してあります。もちろん、バインディングは変更可能ですのでCLっぽくもできます。

と、こんな感じです。一番便利なのはやっぱり辞書ですかねえ。なので、YAML,JSONで書いてる設定ファイルをS式で置き換え･･･なんてことができるかもしれません。

09.19.08/09pm
Posted at:
09.19.08/05pm
Tags:
Comments:
0
Permalink

Python版Yahooテキスト解析 APIライブラリを日本語係り受け解析に対応させました

ついでに指定形容詞係り先検索にも。

ダウンロード

yahooapi

使い方

python code
  1. from yahooapi import *
  2. client = DAServiceAPI("your_appid")
  3. result = client.parse(sentence=u"うちの庭には二羽鶏がいます。")
  4. for morph in result.Result.ChunkList.Chunk[0].MorphemList.Morphem:
  5.   print morph.Reading
  6. # => うち
  7. # の
  8.  
  9. client = DAServiceSearchAPI("your_appid")
  10. result = client.search(mode=MODE_URESHII)
  11. for word in result.Result.WordList.Word:
  12.   print word.Surface, word.Frequency
  13.  
  14. #クリック 35
  15. #応援 30
  16. #気持ち 26
  17. #金メダル 24
  18. #ホームラン 22
  19. #ニュース 17
  20. #デス 16
  21. # .
  22. # .
  23. # .
  24.  

うむ。

08.22.08/07pm
Posted at:
08.22.08/08pm
Tags:
Comments:
0
Permalink

About

Author:yuin(http://inforno.net/)

文学部文化学科卒という生粋の文系趣味プログラマ。

主にRuby、Javascript、PHP、JAVA,Python,C,Scala,Schemeなどを使っています。今はPythonな感じかもしれない。今後作曲活動なども復活するかもしれない。

Links

Pages

Recently

Tags

DHT1 SF1 activesupport1 api4 binary3 blog1 book1 cltc1 compiler1 craftlaunch2 cui1 development9 drecom1 electronics1 emulator6 erlang1 essay10 fckeditor1 feed1 framework1 gae3 go1 gui2 javascript14 job4 kademlia1 language2 library14 life5 lingr1 linux1 nes5 network1 nicovideo1 nlp1 ocaml1 p2p1 parser6 programing2 prototype_js7 python39 python30001 rayphe1 ruby5 rubyonrails2 scala6 scheme1 scrap1 scriptaculous1 sexp1 tasktools1 template3 text3 tk1 typo2 vim2 webpy2 windows4 wordpress2 xrea2 yahoo4

Monthly Archives