読者です 読者をやめる 読者になる 読者になる

みどりねこ日記

よくわからないけど、頑張りますよ。

Pythonを呼べるLispを作った話

この記事はLisp Advent Calendar 2016 5日目の記事です。

Futhonとは

Futhonとは、Pythonが呼べるLispである。 先日作ってみた。 読み方は「ふとん」である。

本記事は、Futhonの内部実装がどうなっているかを簡単に説明する。 すごく小さな実装(ソースコードすべて含んで500行くらい)なので、この記事とコードを合わせて読めば誰でもちょっとしたおもちゃ言語が作れるようになるんじゃないかと思う。

作った動機

最近周りで機械学習がアツい。

Pythonディープラーニング機械学習ライブラリが充実していて、モデルを簡単に作ったり試したりすることができる素晴らしい環境になっている。

一方で、Lispニューラルネットを組もうと思ってもライブラリがなかったり、あってもドキュメントが少なかったりしたのでどうしたものかと悩んでいた。

そこで、ClojureJavaのリソースを利用できるように、Pythonのライブラリを自在に呼び出せるLispを実装して解決しようという考えに至った。 その結果完成した言語がこちらのFuthon言語。 Clojureにはcore.matrixとかあるから自分でそういうライブラリ実装すればいいじゃないかという意見は聞こえない。たぶん言語実装したほうがコスト小さい…。

実装の方針

Pythonのライブラリを自作言語から呼ぶ方法はいくつかある。 そのうちで検討したのは以下の3つである。

まず一つ目は実装がしんどそうな割にあまりメリットもなく思われたので候補から外した。そもそもC++について詳しくないので難航するのは目に見えていた。 二つ目が最有力候補だったけれどREPLの実装の仕方がわからなかったために断念。 というのは、REPLを実装するには順に入力された式を評価しながら何らかの方法でPython側の環境を管理する必要があるが、その仕方が思いつかなかった。 実はPythonにはcode.InteractiveConsoleというクラスが用意されていて、これの継承クラスを書いてやれば簡単にできることをあとあと知った。 結局、最後のメタプログラミングをする方法が実装に手間も時間もかからなさそうだったのでこれを採用した。

実装の大まかな流れ

大きく分けると、インタプリタはだいたい以下の要素で構成されている。

  • トークナイザ
  • パーザ
  • 評価器
  • プリンタ

トークナイザとパーザは、ライブラリによっては一緒に行われる場合もある。 これらを順に実装していくことになる。ここでもその順番に説明していく。

データ型と文法

最初にプログラミング言語のデータ型と構文を決める。 Futhonには以下のデータ型をプリミティブとして持たせることにした。

  • Vector
  • Set
  • HashMap
  • Symbol
  • Keyword
  • Lambda

以下がBNFで表記した文法。

program ::= sexpr

sexpr ::= atom | sequence | quoted

atom ::= string | regex_string | symbol
sequence ::= vector | list | hashmap | set

quoted ::= '\'' sexpr

symbol ::= '[_@\w.\-><\+\-\*\/\?!:=]+'
string ::= '".*?(?<!\\)(\\\\)*?"'
regex_string ::= '\#' string

vector ::= '\[' sexpr* '\]'
list ::= '\(' sexpr* '\)'
hashmap ::= '{' (sexpr sexpr)* '}'
set: '\#{' sexpr* '}'

Futhonプリミティブであるデータ型はFuthonObjectを継承するクラスとして実装する。 そうすると独自の型なのかPython側のオブジェクトなのかがisinstance(x, FuthonObject)するだけで判別できる。 ついでに__repr__のように、あったら便利かもみたいなメソッドをデータ型ごとに追加していく。 これらの詳しい定義はdatatypes.pyを参照のこと。

class Symbol(FuthonObject):
    def __init__(self, name):
        self.name = name
        
    def __repr__(self):
        return self.name

    def __hash__(self):
        return hash(self.name)

    def __eq__(self, other):
        return isinstance(other, Symbol) and self.name == other.name

    def __ne__(self, other):
        return not self.__eq__(self, other)

文法

トークナイザ・パーザ

ソースコードからいきなり実行しようとすると、実装が難しい。 なので、ソースコードからトークンを切り出したり、木構造を生成して後に続く処理を楽にする。 これをするのがトークナイザとパーザ。 パーザの生成にはPlyPlusというパーザジェネレータを使う。 ドキュメントはあまりないがサンプルはあり、BNF表記でLRパーザが生成される点が素敵。 このライブラリを使えばトークナイザを作る必要もないので「とりあえずパーズしたい」という場合には便利だと思う。

start: sexpr;

@sexpr: atom | sequence | quoted;

@atom: string | regex_string | symbol;
@sequence: vector | list | hashmap | set;

quoted: '\'' sexpr;

symbol: '[_@\w.\-><\+\-\*\/\?!:=]+';
string: '".*?(?<!\\)(\\\\)*?"';
regex_string: '\#' string;

vector: '\[' sexpr* '\]';
list: '\(' sexpr* '\)';
hashmap: '{' (sexpr sexpr)* '}';
set: '\#{' sexpr* '}';

WS: '[ \t\n,]+' (%ignore) (%newline);

あとは生成されたLRパーザを呼び出してやって、それぞれ対応するデータ型に変換してやればパージングは終わり。 この辺の実装はfuthon_parser.pyに書かれている。

評価器

式の評価

大抵のプログラミング言語のパーズ結果は抽象構文木である。これはもちろんFuthonでも同様。 そういうわけで、得られた木構造をゴリゴリ評価していく。 Futhonは変数を持つ言語なので、評価する際には変数と値の対応を管理する環境という機構が必要になる。 さらにFuthonからPythonのメソッドなどを呼び出せるようにしたいのでPythonメタプログラミングが必要になる。

環境

環境は変数と値を対応づけるための構造。 Futhonの環境は階層的な構造を持っており、そうすることで変数の局所的な定義などができるようになる。 例えばFuthonでは定義された関数は新しい環境を持つことになるが、同時に生成された時点の環境を上位に持つことで、その時点での環境を関数内から参照できるようになる。

コード上の実装としては上の環境へのリンクを持つ、変数からFuthonObjectへのdict型という感じ。 environment.pyを読めばだいたいわかるはず。

Pythonメタプログラミング

FuthonではPythonのメソッド呼び出しやクラス生成を実行時に行いたいので、これらを実現する方法がホスト言語側に求められる。 幸いPythonにはいくつかそういったものが用意されていて、例えばgetattrを使えばPythonでクラスやメソッドをロードしたり呼び出したりできる。 getattrPythonの組み込み関数で、引数としてPythonのオブジェクトと属性名をあらわす文字列の二つを取り、そのオブジェクトの属性を返す。

class Hello():
    def __init__(self):
        self.hello = "nice to meet you!"

    def greeting(self):
        return self.hello

hi = Hello()
getattr(hi, "hello")
# => "nice to meet you!"
getattr(hi, "greeting")
# => <bound method Hello.greetings of <__main__.Hello object at 0x7febcaf46470>>

getattrで得られたオブジェクトがメソッドなのかはinspect.ismethod()で判別できる。 ただしこれだけではBuilt-in functionなのかどうかまでは分からないので、isinstance(o, types.BuiltinFunctionType)などでチェックする必要がある。 Futhonではメソッド呼び出しと一部のBuilt-in functionのみをサポートしている。

モジュールをインポートする場合はimportlib.import_moduleにモジュール名を渡してやればモジュールオブジェクトが返ってくる。

importlib.import_module("numpy")
# => <module 'numpy' from '/home/delihiros/.pyenv/versions/3.5-dev/lib/python3.5/site-packages/numpy/__init__.py'>

このへんのコードはdynamic.pyにまとめた。

こういうちょっとメタ的な仕様は他にも色々あって、例えばBuilt-in functionであるtypeに3つ引数を与えるとPythonのクラスを新しく生成できたりする。 興味ある人は公式ドキュメントを読んでほしい。 今回は後述する事情により途中で飽きた必要そうでもなかったので取り入れなかった。

以上で評価をするための部品はできた。

評価を行う

あとは実際に抽象構文木の評価を行う。 基本的には抽象構文木の根から葉に向かって深さ優先探索で評価をしていく。 このとき、与えられたノードの型によって評価の仕方を分ける。 例えばFuthonObjectではなくPython側のオブジェクトだったら、そのまま返す。Symbolだったら環境から対応する値を見つけてきて返す、など。 ただし、リストの場合はFuthonの式の可能性があるので特別な評価を行う。 これらの処理はevaluator.pyにある。

def eval(self, expr, env):
    if not datatypes.isFuthonObj(expr):
        if isinstance(expr, list):
            return self.eval_list(expr, env)
        return expr
    elif datatypes.isSymbol(expr):
        return env.get(expr)
    elif datatypes.isKeyword(expr):
        return expr
    elif datatypes.isVector(expr):
        return datatypes.Vector([self.eval(e, env) for e in expr])
    elif datatypes.isSet(expr):
        return datatypes.Set([self.eval(e, env) for e in expr])

リストの場合は、その先頭にあるオブジェクトの型と名前を見て、合致する条件に対応した処理を行う。 例えば、先頭がdefifのように特別な意味を持つSymbolの場合、環境に対して操作を行ったり条件分岐を行ったりする。 先頭が関数やメソッドの場合はそれらを適用する。

def eval_list(self, expr, env):
    if len(expr) == 0:
        return expr
    head = expr[0]
    if datatypes.isSymbol(head):
        if head.name == 'def':
            env.set(expr[1], self.eval(expr[2], env))
            return None
...
    elif datatypes.isLambda(head):
        args = [self.eval(v, env) for v in expr[1:]]
        return self.apply_function(head, args, env)
...

REPL

評価もできるようになったので、あとは外部からプログラムを読み込めるようにすれば終わり。 入力をパースして評価、という処理を繰り返すだけのREPLを実装した。 コードはrepl.pyにある。

(def np (import numpy))
(def chainer (import chainer))

(def l1 (chainer.links.Linear 4 3))
(def l2 (chainer.links.Linear 3 2))

(def my-forward
  (fn [x] (l2 (l1 x))))

(def x (.astype (np.array [[1 2 3 4]]) np.float32))

(.data (my-forward x))
; [[-1.02830815  0.6110245 ]]

これでひとまず大体の機能は備わったので、ChainerやTensorFlowのようなライブラリを使ってニューラルネットLispで書けるようになった。 やったね!!!!!!

オチ

Hyっていう言語があるんでそいつを使いましょう。 実装する前に知りたかった。事前のリサーチは大事。

どうでもいいこと

最初はPalisというオシャレな名前を付けて開発していたが、研究室のメンバーが「FudabaのPythonなんだからFuthonにしなよ」と言ったのでそのようになった。

参考

言語実装資料まとめ

シン・雪女の話

シン・昔話

ある日、おじいさんが山へ芝刈りに行って参りました。

とっぷりと日が暮れたころ、雪が降り始め、村に帰られなくなりました。

すると遠くにぽぅっと灯りがみえるではありませんか。

おじいさんはほっとして、一夜の宿を頼もうと、その一軒家を尋ねました。

「こんこん、こんこん」

「どうしましたか」

戸を開けたのは美しい姉さまです。

中に招き入れ、温かいかゆと寝床を用意してくれました。

夜もふけたころ、ふと目を覚ましたじいさまが、かわやへ行こうと障子を開けたそのときです。

とんとん、と肩を叩くものがいます。

驚いて振り返ると、そこには…

「どこゆきおんな…」

エンジニアライフ始まります(卒業できれば)

日記

来年からエンジニアとして東京で働くことになった.

関東にお住まいのエンジニアの皆様,どうぞよろしくお願いします.

就職活動は大変だった. 明らかに実力不足で落ちたと認識している企業が2社,そして人事面接で落ちた会社数あまた.

テクニカルな面接は概ねポジティブだったと思うけど,お洒落七三分け人事の繰り出す「小学校のころのあなたはどんな人間でしたか?」みたいな質問に弱すぎた.

そんな質問で何が分かるんだよ馬鹿じゃねーのと思ってしまうタイプのクソ人間なので人事面接を乗り越えられない.

あと,ある外資系企業の面接にうっかりパーカーで行ってしまったことがあった. その企業の選考はそのまま進んだけど,別の場所でその企業の面接官をしていた方と話す機会があって,服装について気にするかを聞いたら, 「オレは見てるよ.入社してからならぜんぜん気にしないけどね」という至極まともな回答を得ました. ですので,これから就職活動をされる方はとりあえずスーツを着ておきましょう(当たり前か).

最後に余談ですが,私の場合スーツで受けた会社は全部落ちました!

近況

なぜかはわからないが毎年1月24日に記事を書いていることが判明し,せっかくなので近況報告(という名の研究室紹介).

NAISTでの大学院生生活をはじめてもう少しで1年くらい経つ.

僕はいま知能コミュニケーション研究室というところに所属して自然言語処理の一分野である機械翻訳について研究している(正確には機械翻訳の応用なんだけど).

今やっている研究がどの程度公開していいのかわからないので,去年の研究だけ紹介すると,プログラムのソースコードから英語や日本語の説明文を生成したり,それを応用する研究をしていた. デモはこちらIPSJ-ONEでも紹介されるらしい

NAIST自然言語処理というと松本研究室が有名だと思う.しかし実は僕の所属する中村研究室もとても頑張っている.

入学前は知能コミュニケーション研究室という名前がなんだかダサいなあなんて失礼なことを考えていたが,所属する今はこの名前がとてもしっくりきている. というのは,知能コミュニケーション研究室では音声合成音声認識,対話,認知,そして翻訳とコミュニケーション全般について取り扱っていて,これらすべてを網羅するような名前を思いつかないからだ. 昨年あたりからビッグデータを取り扱う研究班もできたので,今後はコミュニケーション以外についても分野を広げていくのかもしれない.

研究室のメンバーはみんな研究に対して真剣で,ただの雑談をしていても鋭利で刺さる意見が飛んできたりして楽しい. 環境もよく,クラスタマシンやGPUマシンがいくつもあって自由に使える.

個人的に学部時代と大きく変わったのは,読む対象だ. 学部時代はプログラミング言語についての技術書を延々とエッセイのようなノリで読んでいた. 意味がないわけではなかったと思いたいが,果たしてどの程度還元されているのかは今なお謎である.

大学院に入ったとたん,怪物みたいな人たちに囲まれてしまい,焦って慌てて論文や勉強会で使われる本を読むようになった. 今まで論文をきちんと読んでいなかった自分が恥ずかしくなったが,論文を読む楽しみを見つけた. わからないことがあっても隣の人に聞いたり相談したりできる今の環境をとても気に入っている.

NAISTでの生活の不満といえば食事くらいだろうか.でも僕は普段の食事にそれほど味を求めないのであんまり関係なかったりする. 食堂がおいしくないという意見を良く聞くが,腐ってないし異臭もしない.最高.

研究関係以外だと,絵を描くようになったのが約1年前. でも正直あんまり進歩を感じない.つらい.

一年前.

今日.

YANSに参加してきました

日記

大体上に書いてあるとおりなんですが、そういうわけにもいかないので絞り出しました。

YANSとはNLP若手の会の別名らしく、その名のとおり若い自然言語処理erが集まってワイワイ発表とかをする会です(たぶん)。

まずなんですけれど、これが初参加です。

実は昨年も参加登録して楽しみにしてたんですけど、そのときにインターンしていた研究所でのシンチョクが出ておらず、泣く泣くキャンセルしたという過去があります。

今回は他の学会と日程がかぶってしまったので、2日目から参加しました。

2日目のポスター発表でおもしろいなと思ったのは、機械翻訳向け前編集に有効な書き換えルールに関する調査でした。

機械翻訳の精度向上の手段の一つとして、原文が機械翻訳されやすい文を入力するというものがあります。 ただこの機械翻訳されやすい文というのが何なのか、またどうしたらそういった文を得られるかなどというのが分かっていなかったのですが、この研究はそれを調査しています。

手法自体はすごく地道で、英語、日本語どちらにも精通した被験者に文とそれに対応する機械翻訳結果を見せて、うまく機械翻訳されるまで意味が保たれる範囲で文を書き換えてもらう、というのを繰り返し行うものでした。

これによって得られた改変履歴から、どのような性質を持った文が機械翻訳されやすいかまで分析していてかっこいいなあと思いました。

この改変履歴を使って文の書き換えを自動で行えたりするとさらにおもしろそうだなあ…などと思って見てました。

夜になると旅館の一室が飲み会会場になり、お酒をグビグビ飲みました。結果、誰と飲んだのかすら、うっすらとしか覚えていません。

朝起きたらちゃんと自分の部屋で布団にくるまって寝ていたので本当によかったです。 なにか粗相をしてしまったのではないかとビクビクして一日過ごしましたので、お酒はほどほどにがいいですね…。

3日目にポスター発表を行いました。 僕の発表は自然言語からプログラミング言語ソースコードを生成する手法についての検討で、奨励賞をいただきました。 僕の発表と同じ時間に発表されていたいくつかのおもしろそうな発表が見れなかったのは残念です。

金沢駅でラーメンを食べて帰りました。

「迷子になったら動くな」を検証してみた

日記

今日友達とホームセンターに行ったら迷子になってしまった。

いや、はぐれちゃっただけなんだけど、僕は携帯を持ってなかったし、この年で迷子センターに行くのもなーってことでしばらくウロウロして探した。

そこでふと幼い頃「迷子になったらそこから動くな、探される方がウロウロしてしまうと見つけにくくなるから」とママンに言われたのを思い出したんだけど、これって本当だろうかと思って検証してみた。

コードはgistにある。

動作させるとこんな感じ

迷子になったホームセンターを模したマップを作って、それに対して人を2人だけ用意してランダムに配置し、見つけられるまでに行動した回数をカウントする。

「双方動いた場合」っていうのと「ママンだけが動いた場合」っていう2つの状況を100,000回ずつ試して、その行動回数の分布を見てみる。

このシミュレーションでは、ひとはステップごとに移動と向きを変えることができて、向いている方向に対象の人がいたら見つけたことになる。

結果はこんな感じ。 横軸が試行回数、縦軸がその試行回数で発見できた回数。 試行回数の最高値は16,811なんだけど、双方動いた場合の最高値は1,995なのでこのグラフは全体の一部だけの表示。

f:id:paprikas:20150206034033p:plain

双方動いたときの平均試行回数が131.15286であるのに対し、動かなかったときの平均回数が536.75194。 ちなみに分散はそれぞれ27,592.7712938と692,246.087266。

双方動いたほうが圧倒的に早い!!!!!!!!!!

真面目に考察するなら、「ここにはいなかったからきっとあっちだ」っていう予想をAIがするようになれば、移動しないほうが探索回数の上限が決まるので早いと思う。

無限の大きさを持つホームセンターならどうなるんだろう。

簡単に人の顔に泥を塗る方法

日記

僕は人の顔に泥を塗るのを得意とするのですが、泥を塗るのにも労力がかかるんですよ。 なので常日頃からこの作業を自動化できないかと思っていたので、論文の息抜きにやってみました。

import sys, cv2, random

imagefilename = sys.argv[1]

image = cv2.imread(imagefilename)
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
gray = cv2.equalizeHist(gray)

faceCascade = cv2.CascadeClassifier("./lbpcascade_animeface.xml")
faces = faceCascade.detectMultiScale(gray)

for (x, y, w, h) in faces:
    points = []
    for i in range(1, 8):
        points.append((x+x/4+random.randint(-w/20,w/20), y+i*h/8+random.randint(-h/20,h/20)))
        points.append((x+w-x/4+random.randint(-w/20,w/20), y+i*h/8+random.randint(-h/20,h/20)))
    for i in range(1, len(points)):
        cv2.line(image, points[i-1], points[i], (64, 122, 170), 40)

cv2.imwrite("mud_"+imagefilename, image)

f:id:paprikas:20150204223231j:plain

これであなたも人の顔に泥をぬれる!!!!!!!!

lbpcascade_animeface.xmlはこちらからいただきました。