はじめに
はじめまして、ABEJA最年少メンバーでリサーチャーをやっている日熊です。
普段は、Deep Learningに関する研究をやっています。
仕事ではPythonを使っていますが、実際はScalaとかRustとかHaskellに最近ハマっています。
本日は趣味で作ったPythonのライブラリについて紹介します。 この記事では主に以下の様なことが起こります。
- PythonでScalaっぽいlambda式を書けるようにした
- どうやってlambda式を実現したのか説明
- 既存ライブラリより高速だった
目次
今回作ったもの
Scalaのようなlambda式をPythonで実現するライブラリを目指して作りました。 Scalaでは以下のようなコードが書けます。
val numbers = Array(1, 2, 3, 4, 5) val sum = numbers.reduceLeft[Int](_+_) println("" + sum)
上のコードで出力が
15
となります。
注目すべき点は
val sum = numbers.reduceLeft[Int](_+_)
です。
_ + _
と書くと2変数を受け取る関数になっています。
Pythonで書くと
numbers = [1, 2, 3, 4, 5] s = reduce(lambda x, y: x + y, numbers) print(s)
となります。
numbers = [1, 2, 3, 4, 5] s = reduce(_ + _, numbers) print(s)
Pythonでもこう書けると気持ちいい。
そう思いませんか？ そう思いますよね！
僕はそう思ったので、このライブラリを作ってしまいました。
試したい方はこちら
pip install pyscalambda
from pyscalambda import _ print((_ + 10 * (_ - 20 ))(1, 30)) print(all(map(_.isdigit(), ["1", "2", "3"])) print(all(map(_.isdigit(), ["1", "2", "3", "a"]))
実行例
101 True False
実際、Pythonで以下のようなライブラリを使いながら、関数型プログラミングっぽいことをするとlambda式が出まくって煩雑に思えてくる場面が多々あります。
- pytoolz( https://toolz.readthedocs.io/en/latest/ )
- more_itertools( https://pypi.python.org/pypi/more-itertools/ )
実装概要紹介
実装方針
実装に当たって以下の3つの指針を建てました。
- 早く作る
- 速く作る
- なるべく、おもしろそうな道を通ってみる (趣味なので)
上の指針に則って以下の様な流れの実装になりました。
- 演算子のhookingをしてオレオレ構文木を作る
- オレオレ構文木で表された式をlambda式コードの文字列に変換
- 引数リストを作る
- 定数辞書を作る
- lambda式コードの文字列をevalすることにより、lambda式に変換
- 出来上がったlambda式を実行する。 (evalを使う辺りがおもしろそうな道ですかね)
また、そのほかの実装上での工夫としては以下があります。 - lambda式のキャッシュ - _を引数に含む関数の呼び出し
ここでは
10 + -_ * 2
という式がいかにして
lambda x: 10 + -x * 2
というラムダ式に変換されるかを追っていくとします。
1. 演算子のhookingをしてオレオレ構文木を作る
演算子のhookingは以下のように行いました。
class Formula(object): def __add__(self, other): return self.do_operator2(other, "+") def __sub__(self, other): return self.do_operator2(other, "-") def __mul__(self, other): return self.do_operator2(other, "*") ... def __pos__(self): return self.do_operator1("+") def __neg__(self): return self.do_operator1("-") def __invert__(self): return self.do_operator1("~") def __getattr__(self, method): return self.do_methodcall(method) def __getitem__(self, key): return self.do_getitem(key)
このようにPythonのclassには演算子のoverloadがついているので、 すべての演算子をoverloadしたようなFormula(式)というclassを作ります。
このFormulaを継承した
- Operator1(単項演算子)
- Operator2(二項演算子)
- Operand(オペランド)
- MethodCall(メソッド呼び出し)
- FunctionCall(関数呼び出し)
- Underscore(引数オペランド)
このFormulaを継承したものがオレオレ構文木の葉(Operand, Underscore)や節(それ以外)になります。
継承関係は以下になってます。
これにより、上のようなpythonの式を下のような構文木のような形に変換します。
10 + -_ * 2
2. オレオレ構文木で表された式をlambda式コードの文字列に変換
オレオレ構文木をtraverseしながら、lambda式の本体部分を作っていきます。
class Operator1(Operator): ... def traverse(self): yield '(' yield self.operator for t in self.value.traverse(): yield t yield ')' # ["(", "演算子", [項のtraverseの結果], ")"] を出力する class Operator2(Operator): ... def traverse(self): yield '(' for t in self.left.traverse(): yield t yield self.operator for t in self.right.traverse(): yield t yield ')' # ["(", [左項のtraverseの結果], "演算子", [右項のtraverseの結果], ")"] を出力する ...
のようにtraverseするので、
"".join((10 + -_ * 2).traverse())
とすることで 以下のようなlambda式の本体部分を受け取ることが出来ます。
((CONST_0)+((-(___ARG1___))*(CONST_1)))
CONST_[NUMBER]と___ARG[NUMBER]___は後半で詳しく説明しますが、定数の置き換えと引数名の置き換えみたいなものです。
3. 引数リストを作る
lambda式本体が出来たので、lambda式引数リスト部分を作っていきます。 こちらはtraverse_argsという関数を作ります。
Underscoreだけ引数名を返すようにします。
class Underscore(Operand): ... def traverse_args(self): yield "___ARG{}___".format(self.id) ...
そして、Underscore以外のtraverse_argsの実装は
class Formula(object): def __init__(self): self.cache_lambda = None self.cache_consts = None self.children = [] ... def traverse_args(self): for child in self.children: for t in child.traverse_args(): yield t ...
という実装にしておきます。これは自分の子ノードの出力だけを返すだけの関数になります。
FormulaとUnderscore以外は以下のようにchildrenを指定しておけば勝手にtraverse_argsは使える状態になっています。
class Operator2(Operator): def __init__(self, operator, left, right): ... self.left = left self.right = right self.children = [self.left, self.right]
このように実装すると、実行したときに
print(dict((10 + -_ * 2).traverse_args()))
["___ARGS1___"]
のような実行結果を得ることが出来ます。
ここをオレオレ構文木のtraverseじゃなくてリストのイテレーションにしてしまうと、_ + 10 * _こういう式のときに引数が入れ替わったりしちゃいます。
また、Underscoreは以下のようにinit時にidを自動的にふっています。
class Underscore(Operand): COUNTER = 1 def __init__(self, id=None): super(Underscore, self).__init__() if id is None: self.id = Underscore.COUNTER Underscore.COUNTER += 1 else: self.id = id
4. 定数辞書を作る
引数リストだけではなくて、式の中に出現する定数を辞書として保存しておきます。 こちらではtraverse_const_valuesという関数を定義していきます。 こちらもほとんど同じでConstOperandだけ
class ConstOperand(Operand): ... def traverse_const_values(self): yield "CONST_{}".format(self.id) ...
のような実装でそれ以外は
class Formula(object): def __init__(self): self.cache_lambda = None self.cache_consts = None self.children = [] ... def traverse_const_values(self): for child in self.children: for t in child.traverse_args(): yield t ...
のような実装にしていると。
print(dict((10 + -_ * 2).traverse_const_values()))
{
"CONST_0": 10,
"CONST_1": 2
}
のような実行結果を得ることが出来ます。
また、ConstOperandもUnderscoreと同じようにinit時にidを自動的にふっています。
class ConstOperand(Operand): COUNTER = 0 def __init__(self, value): super(ConstOperand, self).__init__() self.id = ConstOperand.COUNTER ConstOperand.COUNTER += 1 self.value = value
これをやらないと、evalの中と外ではスコープが違うのでlambda式をevalで定義するときに上手く動いてくれません。
5. lambda式コードの文字列をevalすることにより、lambda式に変換
今まで作ったものをくっつけてevalに渡すことによりlambda式を生成することが出来ます。
binds = self.traverse_const_values() lambda_body = "".join(self.traverse()) lambda_args = ",".join(self.traverse_args()) lambda_string = "lambda {}:{}".format(lambda_args, lambda_body) lambda_function = eval(lambda_string, dict(binds))
evalの第2引数はevalのグローバル変数になります。ここに定数辞書を渡すことによりevalの内部で定数にアクセス出来るようになります。 これを以下のようにFormulaのcallにフックして実行することにより、Scalaのようなlambda構文が実現できます。
class Formula(object): ... def __call__(self, *args): binds = self.traverse_const_values() lambda_body = "".join(self.traverse()) lambda_args = ",".join(self.traverse_args()) lambda_string = "lambda {}:{}".format(lambda_args, lambda_body) lambda_function = eval(lambda_string, dict(binds)) return lambda_function(*args) ...
全体の流れとしては以上になります。
lambda式のキャッシュ
今回ライブラリの速度が早いポイントはここにあります。 5. で書いた以下のコードだと
class Formula(object): ... def __call__(self, *args): binds = self.traverse_const_values() lambda_body = "".join(self.traverse()) lambda_args = ",".join(self.traverse_args()) lambda_string = "lambda {}:{}".format(lambda_args, lambda_body) lambda_function = eval(lambda_string, dict(binds)) return lambda_function(*args) ...
関数呼び出しのたびにlambda式を生成するため構文木のtraverseを何度も行ってしまっているのでかなり効率が悪いです。
def __call__(self, *args): if self.cache_lambda is None: binds = self.traverse_const_values() lambda_string = self.create_lambda_string() self.cache_lambda = eval(lambda_string, dict(binds)) return self.cache_lambda(*args)
のように一度evalして作ったlambda式はcacheしてしまって使いまわすようにすると、効率が良くなります。 cache有りとcache無しで速度を比べてみると以下のようになります。
gist49ee4e1cd8802cb83711c31081c397cd
実行結果
cached_time 0.440841913223 nocached_time 77.7346978188 176.332366517
のように構文木大きさによりますが180倍程度の高速化につながります。
_を引数に含む関数の呼び出し
例えば、関数呼び出しを行うときの引数側に_を含めた場合、
len(_)([1, 2, 3])
実行結果
Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: object of type 'Underscore' has no len()
となってしまいます。 そこで、scalambdable_funcという関数を作りました。
def scalambdable_func(f): @functools.wraps(f) def wraps(*args, **kwargs): if any(map(lambda x: issubclass(x.__class__, Formula), args)) or any(map(lambda x: issubclass(x.__class__, Formula), kwargs.values())): return FunctionCall(f, map(Formula.convert_oprand, args), vmap(Formula.convert_oprand, kwargs)) return f(*args, **kwargs) return wraps SF = scalambdable_func
関数の呼び出しの引数をすべてoperandへ変換し実行します。 これにより、引数にある_を加味した構文木を作成することで関数呼び出しに対応することが出来るようになっています。
SF(len)(_)([1, 2, 3])
実行結果
3
ちなみにこのscalambdable_funcはデコレータとしても使えます
@SF
def test(x):
return x + 1
test(_)(100) # == 101
その他
その他にも色々頑張りました。
1. _以外にも_1, _2, ..., _9を作って複数回変数を利用するlambda式の生成を可能にする
from pyscalambda import _1, _2 (_1 + _2 * _1 * _2)(10, 20) # == 4010
2. Objectのメソッド呼び出しにも対応している
from pyscalambda import _ (_.split("_"))("ABEJA_ABEJA") # == ["ABEJA", "ABEJA"]
3. cacheしないモードも実装している
from pyscalambda import _ (_ + _ + _).nocache()(1, 2, 3) # == 6 (遅い)
4. _と_1, _2, ... , _9を同時に使うとSyntaxErrorにする
(_ + _1)(1, 2) # raise SyntaxError
5. ちゃんとtestを書いていたお陰でいじるとき楽だった
などなど、語りたいことはいっぱいありますが今回はこの辺にしておきます。
競合紹介
作った後に調べたところ、2つほど同じこと(似たこと)を実現しているライブラリを見つけました。
fnpy
特徴
- lambda構文だけではなくPythonで関数型っぽく書く機構を揃えてる(monadとか遅延評価周り)
- lambda構文は表現上は全く一緒
- 中の設計がきれいで頭良く作られている
macropy
特徴
- lambda構文のためではなく、pythonのAST(抽象構文木)に対して関数(Lispで言うマクロ)を適用するライブラリ群
- lambda構文はやりたいことは同じだが構文が違う
- これを使うともはやpythonではなくなる…(すごくイケてるしヤバイ感ある)
比較
比較実験
今回は書き方がまったく一緒である、fnpyとの比較実験を行いました。
比較コードは以下です。
実行結果
pyscalambda_time 0.060153961181640625 fnpy_time 0.32550811767578125 5.41124992073
pyscalambdaの方が5倍程度早いです。
速度比考察
pyscalambdaはlambda式をそのまま作っているのに比べ、fnpyは関数をネストした形で作っています。
_ + 1 + 1
例としてこのような構文を変換したときに
pyscalambdaは
lambda x: x + 1 + 1
というような、lambda式を生成しています。
fnpyはイメージとしては
lambda x: add(add(x, 1), 1)
の様なlambda式を生成しています
2つを比べてみると、pyscalambdaのラムダ式に比べfnpyのlambda式は演算があるたびに関数呼び出し分のオーバーヘッドがあると考えられます。
追加実験
先程の考察を実証するために以下のような比較コードにより実験を行いました。
gist274b8f2a7a0b3f1b44dea35569c3451c
このコードは恣意的にfnpyの関数呼び出しするであろう場所を増やし速度比に変化が起きるかの実験です。
実行結果
pyscalambda_time 0.27565693855285645 fnpy_time 9.234592914581299 33.5003100704
pyscalambdaの方が34倍程度早いという結果となりました。 これにより、関数呼び出しによるオーバヘッドが両者の速度を分かつこととなりました。
考察
evalによりlambda式を文字列から生成しキャッシュする機構を取り入れることによって、 既存のコードよりも通常用途で約4倍、コーナーケースにおいて約34倍程度早くなることがわかりました。 lambda構文は性質上mapの中やfilterの中に取り入れられることが多いため、この速度向上には意味があると考えます。
感想
今回の取り組みについての感想は、趣味プログラミングでこのようなものを作ることで業務をこなしているだけでは身につかない部分に触ることが出来て良かったです。 また、趣味プロジェクトでも
- やりたいことを明確にする
- 既存システムを探す
- 既存システムに対してどのように優位性を作るかの方針を立てる
- 実装
- 評価
という、業務(研究)で身につけたフレームワークが役に立ちました。
このように趣味プログラミングと業務(研究)の間でエコサイクルを回しながらスキルを磨いていくことが楽しんでプログラミングをしていくためには重要だと思いました。
宣伝
ちなみに、ABEJAでは今回の話が「面白い or もっといいもの作れるからくだらない」と思えるイケてるしヤバいエンジニアを募集しています。
ABEJAが発信する最新テクノロジーに興味がある方は、是非ともブログの読者に！
ABEJAという会社に興味が湧いてきた方はWantedlyで会社、事業、人の情報を発信しているので、是非ともフォローを！！ www.wantedly.com
ABEJAの中の人と話ししたい！オフィス見学してみたいも随時受け付けておりますので、気軽にポチッとどうぞ↓↓
