Blog

Scala初心者の新卒が頑張ってLispを作ってみた


この記事はCyberAgentエンジニアAdvent Calendar5日目の記事です。

こんにちは! サイバーエジェント アドテクスタジオ新卒の志村です!!
7月にScala初心者のままScalaを採用しているAMoAdに配属されたのでScala歴5ヶ月くらいです。
Scala歴5ヶ月くらいだと初級者になるのかもしれませんがScalaばかり書いてる訳ではないのでまだScalaは全然書けません。
簡単な言語くらいしか書かないのでScalaが複雑すぎて全然覚えられません(´・ω:;.:…

ということでアドベントカレンダーにかこつけてScalaの勉強をしたいと思います!

学んでいくにはやはり手を動かすのが一番なんですかね (@@;?
何か作ってみます。何を作るのが良いんでしょう。Scalaといえば…チューリング完全(?)な言語らしいですね。
チューリング完全といえばリスプですよね。リスプを作ってみたいと思いますo(((^
^)))o

今回作るリスプを何のひねりもなくscalalispと呼ぶことにします。

AST

まずはASTを作ってみます。ASTは代数的データ型で作るのが一番ですね。Scalaで代数的データ型を作るには

で始めるらしいです。 sealedは同一ファイルから以外の継承を禁止する修飾子らしいです。

そこからASTのデータ型を定義していきます。文字列があると面倒そうなので nil, t, コンスセル、 自然数、 シンボルくらいでいいですかね。試行錯誤してみたらこうなりました

あんまりMLの代数的データ型に似てませんがこれでちゃんと定義出来てるらしいです。不思議…

case classclassを便利にしたやつらしい(?)です。MLのレコードみたく扱えるみたいですね。

パーサ

ところでparserの読みは「パーザ」がイギリス読み、「パーサ」がアメリカ読みですよ(ドヤァ)

リスプの文法は簡単なので手書きでもいいのですがパーサコンビネータが標準ライブラリにあるらしいので折角ですし使ってみます(^o^)。

正式な記法をよく分かってないのですが、 "org.scala-lang.modules" %% "scala-parser-combinators" % "1.0.4"を使います。

から始まります。ワイルドカードインポートが邪悪ですがScalaだとよくやるんですか(・_・)?

ちょっとずつ定義していきます。まず簡単そうな niltから。

簡単でした。まゆげみたいなので変換関数を指定しますo(^^)o。次は自然数とシンボルです。

正規表現も簡単に使えるんですね。

リスト、シンボル、そしてクォートは相互に再帰するのでまとめて書いちゃいますね。

再帰するパーサには型を書かないといけないってScalaさんに怒られました(>_<)。
パースした結果は Parser型になるんですね。

ということでparser.scalaはこうなりました。

これだけでリスプのパーサが書けるなんでScalaすごいですね。

ちょっと遊んでみます

ちゃんと動いてるみたいですね。地味に ()LNil()になってくれてます。foldRightの基底条件ですね〜♪

内部表現

さっきまではASTでした。今度は実行時の表現を作りたいと思います。

さっきと同じように sealed traitから始めます。

どんどん定義していきます

コンスセルはこうなるらしいです。

HTの前に付いてる +は「いい感じにサブタイプ関係を推し量ってくれる」記号らしいです。すみませんよくわかってません><勉強不足ですみません((>_<))。
でも Cons[Nil, Nil]とかはM式に似てて親しみが持てますね。

次は自然数ですね

自然数はチャーチ数で表すんですね♪

因みにこういうことらしいです。

次にシンボルです。シンボルは任意の形をしていますがどう表すのか分からなかったので事前に定義したものだけ許すことにしました。

詳しい方上手いやり方を教えて下さい><。

ASTから実行時の表現への変換はそんなに大したことなさそうなので最後にやることにします。

関数を定義する

足し算とか

まずは足し算からやってみます。チャーチ数の足し算は

ですね。今回は少し変形した

を使います。

まずは足し算トレイトの定義から。

NMを受け取って結果を Outに入れる、と。なんだかPrologみたいですね。
じゃあ実装をしていきます。まずは最初の n + 0 = nから。

そのままですね。ところでトレイトとオブジェクトの名前が被ってますが「インプリシットはコンパニオンオブジェクトからも探される」(?????)らしいので被ってていいそうです。というか同じじゃないといけない(?)。

因みに : Plus[N, Zero] { type Out = N } = new Plus[N, Zero] {type Out = N}と2回も同じことを書いてるのは : Plus[N, Zero] { type Out = N }側は計算結果、 new Plus[N, Zero] {type Out = N}側が計算結果が存在することの証明らしいです。
値は証明!ユニフィケーション!

次に再帰節です。再帰ってどうやるんだって気になりますがここでもインプリシットを使うそうです。

Plus[N, M]が存在する時に Plus[N, Succ[M]]は定義出来て、その結果は Succ[plus.Out]になる」と読めばなんとなく分かりそうです。やっぱりPrologっぽいですね。

と対応とれますね。

一旦様子を見ます。

計算と期待する結果が合っている時には値が返ってきて、間違ってる時にはエラーが出てます。assert成功ですね。

じゃあ、次はかけ算もやってみましょう。チャーチ数のかけ算は次のように定義できます。

n +を関数と思えば足し算とまったく同じ構造をしてますね。ということで実装もほとんど同じです。

自然数の扱いはこの辺までにして次はリストを扱ってみましょう。

リスト操作

リスト(コンスセル)操作の関数基本は自然数と同じです。

ベースとなるトレイトを用意して

実装を書きます。

簡単ですね。同じようにしてcdrも定義出来ます。

一応consも作ります。

余談ですが関数のコンスとデータ型のコンスが混らないようにデータ型の方をコンスセルにしました。

次はappendです。appendはどのように表されるでしょうか。一旦Prologで考えてみましょう。

こうなりますね。これをそのままScalaに書き下します。

prologのbody部分を implicitにすれば良いみたいですね。だんだん慣れてきました。これも少し試してみましょう。

よしよし。

もう少し複雑なことをやってみましょう。

あれ?合ってる筈なのにエラーが出ます。

これは Consの定義を思い出してみると分かります。

Consの型は Consなんですね。なので Carには渡せません。さて……どうしましょうか。

ここでお気付きの方もいるかもしれませんが今まで定義してきたのは「実行時表現を操作する何か」であって実行時表現ではないのです。
M式に似てるので勘違いしやすいのですがscalalispの一部でない。 Car[E]であって ConsCell[Symbol[SCar], ConsCell[E, Nil]]でない。
じゃあどうすればいいかというとS式のインタプリタを書くのです。

eval

S式のインタプリタのことを evalっていいますね。
evalのインターフェースは単純です。

S式を受け取って評価した値を返す。

で、これの実装ですがprologで書くとこうなります。

アトム、スペシャルフォーム、及び提供したい関数全てに対してホーン節を定義してあげる訳です。

ちょっと億劫ですがやっていきましょう。

まずは便利のためにリスト型を用意します。

アトム

アトムは簡単です。

本来ならシンボルはそれが束縛されている値へと評価されるのですが今回値の束縛を用意していないので自身へと評価することにしました。
未束縛でエラーにならないちょっと気持ち悪いですかね。しかしShenのようにそういう評価規則を持つ処理系もあるので大丈夫でしょう。

関数

全部やるとキリがないのでいくつか。carはこうなります。上に挙げたprologそのままですね。

他の関数も同様に定義しますが、例としてappendも出しておきましょう。

prologではこうなります。

そのまんま東ですね。

eval自身を定義することも勿論可能です。

スペシャルフォーム

今回、スペシャルフォームは quoteifを提供することにします。

quoteは簡単ですね。

評価せずに返してあげればよいです。

問題はifです。Scalaだと複雑なので一旦prologで説明します。(なんかカットが必要な気がしますが説明と関係ないので省きます。)

これでnilとそうでない場合の分岐をしているのですが構造は同じですよね?違いは Condを評価した結果を nilとユニフィケーションしているか。

ところでCondの評価値がnilなのに2つ目の節に入った場合、 _で受けているのでユニフィケーションに失敗せずにそのまま Thenが返ってきてしまいますよね。
Prologの場合は 最初に書いたホーン節から 成功するまで試すので問題ありません。しかしScalaのimplicitにはそういう規則がありません。

どうにかしてimplicitの解決に優先順位を与えないといけませんね。そこで継承を使います。implicitは先に自身のimplicitを捜して次に親のimplicitを捜すらしい(?)のでそこで優先順位をつけます。ということで Evalに少し変更が必要です。

優先度の低いホーン節用のトレイトを作ってあげて Evalでそいつを継承します。これで ifを実装出来ました

プリティプリンタ

最後の返り値はやっぱりS式の方が見易いので一瞬evalから離れて文字列化をやります。

を用意してまたimplicitに解決させます。今までと違うのは最後は文字列で欲しいので applyを使っているところですね。

nil/t

やっていきます。 tnil

リスト/コンスセル

次は少々技巧的ですがリスト/コンスセル

リストの開始のコンスセルで "(s"を、リストの中では要素をスペース区切で、リストの最後のコンスセルで "e)"または ". e)"を返します。 toStringListNtoStringConsがコンフリクトしそうな気がしますが何故か通ります。返り値のユニフィケーションしてないから?よく分かってません。

自然数

自然数は一旦数値に変換してから toStringを呼んでやります。

シンボル

シンボルは個別で対応するしかありません。まあ、今回は高々有限個です。

評価機

ToStringが出来たので評価機を作ります。 EvalToString。まあ、 Evalして ToStringするだけです。

貫通

さて、部品が揃いました。あとはS式をパースして型に落として EvalToStringを呼ぶだけですね。コンパイル時にパース関数を走らせるためにマクロを使います。

マクロを使うにはリフレクションライブラリが必要みたいです。 "org.scala-lang" % "scala-reflect" % scalaVersion.value

さて、実行器はそんなに対したことないので一気にソースを載せてしまいます。

run_implでは文字列リテラルのASTから文字列を抜き出して、パースしてASTにして、型に変換して、それを EvalToStringに食わせる形のASTに変換するだけですね

toTではASTを実行時表現にそのまま翻訳します。型なのでquasi quoteが qではなく tqになってますね。

事前に用意してなかったシンボルを nilにするという邪悪なことをしていますがまあ目を瞑って下さい。

それでは遊んでみましょう。

やりましたね! Lispが動いてます。

今回のソースコードはこちらに置いておきます。遊びで作ったので色々雑ですが興味のある方は全体を眺めてみて下さい。

最後に

飛ばし飛ばしでしたが型レベルLispはいかがでしたでしょうか。

心残りなのはチューリング完全に出来なかったことですね。Lispをチューリング完全にする場合、純LISP的アプローチだと (define name value)相当のラベル機能を付けますが、環境を持てない今回では厳しいので見送り。
次はlambdaを実装してしまうものですが、それも中々というかラベル以上に難しいでしょう。クロージャの実装が必要になります。
ド・ブラン・インデックスを使って実装してしまった方もいるようですが、traitをfatにしてtypeを持たせてやるやり方が好みでなかったのでやめました。
一応計画としては文法的にはlambdaをサポート、実行時表現にSKIコンビネータを入れてコンパイラでラムダ計算からSKIコンビネータへの項書き換えをするのが今回の実装に一番適してるかなと思ったのですが中々大変なので間に合いませんでした。
実行時表現にSKIコンビネータを突っ込むだけでもやれば良かった。

ということでκeen(@blackenedgold)がお送りしました!!

Author

アバター
fukuhara

関連記事