Pythonを呼べるLispを作った話

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

Futhonとは

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

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

作った動機

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

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

• SciPy
• scikit-learn
• Caffe
• Chainer
• TensorFlow

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

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

実装の方針

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

• C++で言語を実装して、Boost.Pythonなどから呼び出す
• PythonのソースコードをAST経由で生成するトランスレータを書く
• Pythonでメタプログラミングして動的にメソッドやクラスを生成・呼び出し

まず一つ目は実装がしんどそうな割にあまりメリットもなく思われたので候補から外した。そもそも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でクラスやメソッドをロードしたり呼び出したりできる。 getattrはPythonの組み込み関数で、引数として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に３つ引数を与えると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])

リストの場合は、その先頭にあるオブジェクトの型と名前を見て、合致する条件に対応した処理を行う。 例えば、先頭がdefやifのように特別な意味を持つ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にしなよ」と言ったのでそのようになった。

参考

言語実装資料まとめ

instaparseで遊ぶ

この記事はClojure Advent Calendar 2013 - Qiita [キータ]１９日目の記事です。

instaparse

本記事ではinstaparseというライブラリを使って遊んでみます。

instaparseはEBNFやABNFで記述された文脈自由文法から自動的にパーサを生成してくれます。 左再帰、右再帰、曖昧性など、いかなる文脈自由文法でも動作します。 生成されたパーサは文字列からenliveまたはhiccup風の木構造を生成します。

今回は型なしラムダ計算を題材にします。

型なしラムダ計算

型なしラムダ計算は、型がない（または型がひとつしかない）ラムダ計算です。

ラムダ計算はとてもシンプルで、すべての計算が関数定義と関数適用だけで実現可能です。

ラムダ計算の構文は以下の３つからなります。

t ::=        項
    x        変数
  | \x . t   ラムダ抽象
  | t t      関数適用

定義くらいはほしいだろう、ということで、今回作るパーサは以下のような拡張をした構文にします。

lang ::= (expr | def)+
def  ::= var '=' expr ';'*
expr ::= (var | app | abs)
     |  '(' app | abs ')' ';'*
var  ::= [a-zA-Z-]+
app  ::= expr expr
abs  ::= '\\' var '->' expr

さて、上の構文を用いてパーサを作ってみます。

(ns lambda.core
  (:require [instaparse.core :as insta]
            [clojure.core.match :as match]))

(def parser
  (insta/parser
    "lang = (expr | def)+
    def = <w> var <'='> expr <';'*> <w>
    <expr> = <w>
    (var | app | abs
         | <'('> (app | abs) <')'>) <w> <';'*>
    var = <w> #'[a-zA-Z-]+' <w>
    app = expr expr
    abs = <'\\\\'> var <arrow> expr
    w = #'[\\n\\s]*'
    arrow = '->'
    "))

簡単に書けました。

実行すると以下のような結果が得られます。

(parser "true = \\x -> \\y -> x;")
; => [:lang [:def [:var "true"] [:abs [:var "x"] [:abs [:var "y"] [:var "x"]]]]]

驚きのお手軽感です。

お分かりかとは思いますが、langやdefなどがキーとなった木（ベクタ）ができています。そして< >で囲まれたexprやwは出力結果にはありません。 < >はパース結果を隠す役割があります。他にも正規表現が使えたりと大変便利なライブラリです。

またパース結果をグラフ化することもできます。

(insta/visualize (parser (slurp "sample.lambda")))

せっかくパーサができたので評価できるようにします。

実装にあたってはこの辺とかこの辺を参考にしました。

α変換．．．本来だと条件によって置換しなくてもいいこともある。ﾌﾑﾌﾑ〜〜〜。

面倒だし、全部置き換えたところで一緒なので全部置換することにします。

(gensym)でユニークな変数が降ってくるので、\x -> \y -> x yのような形のものを、\unique_symbol -> \y -> \unique_symbol yのように変換します。 そのようにすれば適用する式の中身と変数名がかぶりませんね。

HaskellやOCamlみたいなパターンマッチがClojureにもあったらなーと思っていたら、clojure.core.matchがなかなか良さそうなので使ってみました。

(def env (atom {}))

(defn evaluate [expr]
  (match/match
    expr
    [:def v e]
    (do (swap! env conj {v e}) v)

    [:var v]
    (get @env [:var v] [:var v])

    [:app [:var v] n]
    [:app (get @env [:var v] [:var v]) n]

    [:app [:app m n'] n]
    [:app (evaluate [:app m n']) n]

    [:app [:abs [:var v] body] n]
    (clojure.walk/postwalk
      (fn [z] (if (= z [:var v]) n z))
      (evaluate body))

    [:abs [:var v] body]
    (let [v' (str (gensym))]
      [:abs [:var v']
            (clojure.walk/postwalk 
              (fn [z] (if (= z [:var v]) [:var v'] z))
              (evaluate body))])))

(defn show [expr]
  (match/match
    expr
    [:lang & n]
    (reduce str (map show n))
    [:def v e]
    (str (show v) " = " (show e))
    [:var v]
    v
    [:app f x]
    (str "(" (show f) " " (show x) ")")
    [:abs arg e]
    (str "^" (show arg) "." (show e))))

(defn evaluate-all [expr]
  (match/match
    expr
    [:app m n]
    (evaluate-all (evaluate expr))
    :else expr))

(let [code
      (str
        "true = \\x -> \\y -> x;"                ;; "true = ^x.^y.x"
        "false = \\x -> \\y -> y;"               ;; "false = ^x.^y.y"
        "if = \\p -> \\t -> \\f -> ((p t) f);"   ;; "if = ^p.^t.^f.((p t) f)"
        "cons = \\x -> \\y -> \\f -> ((f x) y);" ;; "cons = ^x.^y.^f.((f x) y)"
        "car = \\p -> p true;"                   ;; "car = ^p.(p true)"
        "cdr = \\p -> p false;"                  ;; "cdr = ^p.(p false)"
        "(car ((cons true) false))"              ;; "^x.^y.x"
        "(((if true) false) true)")              ;; "^x.^y.y"
      parsed (parser code)
      results (map evaluate-all (rest parsed))]
 (map show results))

Clojureすごい！instaparseすごい！

というわけで、１９日目はこれでおしまいです。

構文メモ

関数型言語

<ラムダ式> ::= <変数> | <ラムダ式> <ラムダ式> | λ <変数> . <ラムダ式> | ( <ラムダ式> )
<関数定義> ::= ( <関数名> <ラムダ式> )

論理型言語

<論理式> ::= <リテラル> | <論理式> -> <論理式> | <論理式> ∧ <論理式> | <論理式> ∨ <論理式> | ∀ <変数> <論理式> | ∃ <変数> <論理式>
<リテラル> ::= <述語> | ¬ <述語>
<述語> ::= <述語名> ( <項> {, <項> }* )
<項> ::= <定数> | <変数名> | <関数名> ( <項> {, <項> }* )
<節> ::= { ∀ <変数名> }* <リテラル> { ∀ <リテラル> }*

命令型言語

<文> ::= <代入文> | <制御文> | <名前> : <文> | begin <文>* end
<制御文> ::= <条件文> | <繰り返し文> | <ジャンプ文>

<if 文> ::= if <式> <文>
<if-else 文> ::= if-else <式> <文> <文>
<while 文> ::= while <式> <文>
<for 文> ::= for ( <式> ; <式> ; <式> ) <文>