MSPとTagless-finalで作るインタプリタ　実用的なDSL構築のアプローチ

Tagless-finalとは何か

鈴木健一氏（以下、鈴木）：次は、Tagless-finalの話ですね。Tagless-finalはいろいろなところで最近話に出てきていますけれども、Tagless-finalパターンとしての、エフェクトラッパーとしてのTagless-finalの話とはちょっと違って、DSLを構築するところの話ですね。

Tagless-finalが何かと言いますと、DSLを構築するためのアプローチです。Tagless-finalというのが、そもそもDSLを構築するためのテクニックをいろいろかき集めてきて名前を付けたのが、Tagless-finalになっているんですね。

そのため、いろいろなテクニックがまざって本質が掴みにくいところはあると思いますが、その目指すところはDSLを安全に構築するためのアプローチです。

そのかき集めているテクニックの中には、例えば部分評価、partial evaluationですとか、type-preserving interpretationみたいなものが入っています。そういったところで効率的なDSLを書けるというテクニックになっています。

Tagless-finalのメリットは、やっぱり型付けがメタ言語、ホスト言語に帰着するというのが一番大きいかなと思います。ホスト言語と言っているのはScalaとか、OCamlとか、Haskellとか、そういった埋め込む先の言語ですね。

ここに型付けを任せられるので、我々は言語を作りたいんだけれども、その言語の型付けの規則とか型推論のアルゴリズムっていうのは書かなくていいわけですね。

あとはもう1つ、高階抽象構文。これを使うことによって変数束縛をその言語に全部お任せできます。そうすると自分たちが使う言語に対してスコープの安全性というのは気にしなくてよくて、それは全部ホスト言語にお願いできるというのもメリットです。

あとはパーサーを作らなくていいっていうのは地味に楽ですね。関数を組み合わせるだけで目的のプログラムが書けるので、よくプログラム言語の研究者さんとかはいちいちパーサーを書くんじゃなくてTagless-finalで言語を表現して、いろいろ研究したりされるケースもあります。

先ほどの用語の繰り返しになりますが、オブジェクトランゲージと言っているのが対象言語で、我々が作りたい言語です。DSLとかですね。あとメタ言語と言っているのが、対象言語を埋め込む先の言語になります。HaskellとかScalaとかそういった言語になります。

対象言語をどうやってTaglessでエンコーディングするのか

ここで簡単な例で、対象言語をどうやってTaglessでエンコーディングするのかを見ていきたいと思います。ここで考えているのはIntリテラルと足し算しかない単純な言語です。

まずやるのが、言語の構成子、Intリテラルと足し算なので、これを抽出して関数として与えています。このあと、この関数のシグニチャを型付け規則に対応させます。この対象言語の型をRepr、Representationタイプというかたちでラッピングしてあげます。というところが大きなポイントです。

これを型付け規則と一致させないといけなくて、例えばIntリテラルのところですと、Intを返すので、このIntを対象言語の表現型Reprで包んであげます。addの規則も同様に、これはe1がIntで、かつe2がIntであるならば、e1+e2はIntであるということを言っているので。

ここでもまずe1がIntのReprで、e2がIntのReprで、そうすると結論としてIntのReprが返ってくるとというふうに、型付け規則と完全に対応させるかたちでシグニチャを書いていくことが大事です。

次にここで言語の構文と型付け規則が定義できて、その意味論を与えていきます。先ほど書いたものがSymanticsと呼ばれる言語のインターフェース、言語を定義するものになります。そのインターフェースの実装として意味論を与えていくというのがTaglessの特徴です。

このインターフェースに従ったかたちでインタプリタが作られるので、もちろんこのインタプリタはインターフェースに従っている以上、型もちゃんと守られるようになります。

ただここのインタプリタで書いたものというのは、Reprで表現した型になっていますので、そのReprの値を実行・抽出するための評価関数が必要になってきます。これをevalというかたちで書いています。

インタプリタの実装はほぼ型合わせゲーム

Taglessで書いた場合、対象言語のプログラムも全部関数で表現するので、ここでは1+2というのも関数の組み合わせで表現するようになります。単純な、プリミティブな1という値もちゃんとTaglessの世界ではリテラルを作るliftingの関数として定義して、addと組み合わせて使います。

あとちょっとテクニックが必要なところが、λの表現ですね。λみたいなものが言語の中にある場合に、どういうかたちでTaglessにコードをすればいいのかというところなんですけれども。

こちらは高階抽象構文というテクニックを使います。高階抽象構文って何をやっているかと言うと、変数の束縛をホスト言語の束縛にお任せしています。例えばこちら、今カーソルがあるところ、λですね。その型付け規則によっています。

まず変数xがτ1という型を持っていて、そのもとで関数のボディ、本体のほうがτ2という型を持つと。ならば、このλはτ1からτ2の型になるということを言っています。

これをTaglessでエンコードする場合、まずこのxというところが、τ1という型……ちょっとτ1とAって名前が合っていないんですけれども。読み替えていただいて。ここをReprで囲ってあげますと。そのあとこのボディの部分、これもReprで囲って、そこからRepr[A]からRepr[B]の関数、アローとして埋込みを定義する。

その結論として、ここはτ1からτ2という結論が出ているので、それをリターンタイプとしてA=>B（AからB）という関数を定義します。これはもちろん対象言語の世界の話なので、それ全体をReprで囲むというようなかたちで作ります。

ここがAの部分、Reprを一旦囲って、そこからアローを伸ばしているというところがポイントですね。

あとappというのが関数適用なんですが、こちらは右側ですね。e1がいわゆる関数になっていて、e2がその関数のパラメータです。ここはe1は関数なので、その関数の型をReprで囲っている。e2は単純な値なので、それをReprで囲ってあげて、その結論はe2というところを全部Reprで囲ってあげるというかたちです。

あとはこれのインタプリタの実装はほぼ型合わせゲームですね。シグニチャにひたすら従って書いていくだけでいいと。最初ちょっとややこしいんですけれども、慣れてくれば本当にただの型合わせゲームでしかないっていう感じですね。

xを受け取って、それをReprで包み込んであげて。それをfに適用したものを解いてあげて、最終的にはReprの世界にまた戻すみたいな。そんな感じです。

これはちょっとおまけ的なやつですけど、言語のコンポーネントを合成できるというところですね。先ほどのSymantics、あれがインターフェースになっているので単純にインターフェースを組み合わせてあげるだけで言語が構成できるというところです。

オプティマイザーとコード生成するインタプリタを組み合わせられないか

じゃあオプティマイザー、最適化するインタプリタとコード生成するインタプリタ、これを組み合わせられないか。例えばやりたいのが、ユーザーが作ったプログラムがあって、それを最適なかたちに変換して、その最適なかたちになった状態をコード生成するということをやりたいと。

それをTagless-finalのスタイルでどうやるのかというところなんですけれども。まず1つはTagless-finalというのは先ほどのSymanticsが1つの言語としてあって、そのインターフェースに従うインタプリタ、解釈を複数与えられることができます。さらにその解釈というのを複数組み合わせるということができます。

その組み合わせをどうやるのかという話なんですけれども、まずインタプリタをモジュールファンクタとして構成します。そのモジュールのファンクタになったやつは合成できますので、それを組み合わせます。

ただその1個1個のインタプリタってそれぞれ独自の表現型、Reprを持っているので、そこのReprとReprの間をどうやって変換していくかというフレームワークを与えてあげる。そうするとそれぞれのインタプリタでそれぞれの関心ごとの処理を行って組み合わせる。それらを組み合わせることができると。

ちょっと図でお話しします。まずインタプリタがあります。これはユーザーが書いたTermを与えて、それを解釈して結果を返すだけです。これを組み合わせるためには、まずTermを与えて、それを解釈して、その結果が次のインタプリタの入力のTermになるようにするというところが1つポイントです。

通常インタプリタと言うと、Termを与えて、そのTermを全部解釈して値にしちゃいますというところまで簡約すると思うんですね。でもここではインタプリタがすべてのTermを解釈するのではなく、自分の関心のあるオプティマイズのところだけ処理して、それ以外のTermをなにも処理しないで残しておきます。

値として、コードとして残しておいて、次のインタプリタに渡してあげるっていうふうにすると、それぞれインタプリタを組み合わせた時にそれぞれの関心ごとのオプティマイズができるようになる。それを組み合わせられます。

例えば、真ん中のインタプリタで、単位元の削除ですね。1+0の場合、この+0の部分の0って必要ないわけですね。ですから、オプティマイズするときに1は残して+0の部分のTermを削っちゃえばいいわけです。それをやっているのが真ん中のインタプリタです。

このインタプリタはモジュールファンクタみたいなかたちになっているので、前段のインタプリタをパラメータとして受け入れて、連携できるようにしています。さっきの単位元を削除するというのをやっていって、その単位元がなかったらそのまま計算をなにもしないで後ろに回すという処理です。

コード生成したい場合はReprをコードの型として定義する

最後に、コード生成したというお話をしましたが、Tagless-finalだとReprを自由に、それぞれのインタプリタごとに定義できるので、コード生成したい場合はReprをコードの型として定義すればいいわけです。

DottyのQuotation、コード生成ではExprっていう型がコードの型になるので、これをReprの具体的な型として与えてあげます。

そうするとこのコード生成のインタプリタは、例えばIntでnが与えられた時に、そのnを単にブラケットで囲ってあげてコードの型にするというような、そういうインタプリタを作ってあげれば、最終的にコードが生成されるようなインタプリテーションになります。

あとは、最後に出てきたコード生成というのが、表現型がいわゆるコードの型、Exprの型になっています。でもさっきの、前段のオプティマイズするインタプリタのReprはまた別な型なわけですね。なので、型が合わない。ここをうまく変換してあげなきゃいけなくて、そのために利用しているのが、Reflect-reify frameworkというものです。

この中身は単に自然変換をやっているだけです。これを共通モジュールとして置いておいて、各インタプリタのほうで型変換するところでこれを呼び出してあげるという感じですね。

これはオプティマイズした例で、Tagless-finalでTermを表現しているので、そのTermは全部関数になります。一番上の例は1+0ですね。この+0の部分が、先ほど真ん中にいたオプティマイザーが+0の部分を除去してくれて、最終的に1が残って、その1がコードして生成されると。

次に2番目の例が、210ですね。ここは単位元とかぜんぜん現れてこないので、誰もオプティマイズする人がいないため、そのTermがなにもいじられなくて、最終的にそれがコード生成器にかまされて、コード生成器が210っていうのをそのまま出力しているという例になります。

あと最後が、110+0ですね。まず110の1の部分が掛け算の単位元になっているので、その掛け算の単位元を除去するオプティマイザーが働いて、1*の部分が消えて10になります。そこから10+0になりますが、+0の部分が足し算の単位元になるので、0が除去されて、最終的に10が残ります。この10がコード生成器に渡されて、10が生成されるよっていう、そういう流れですね。

発表は以上です。ありがとうございます。

司会者：鈴木健一さん、発表ありがとうございました。みなさん拍手をお送りください。私コメントのチャットのところを見ていたんですけれども、「EffとTagless-finalが似ているね」みたいな意見が書かれていました。

鈴木：そうですね。Effも拡張性というところに重きを置いているかなと思っていて、そこはやっぱりモチベーションというところでけっこう似ているなという気はしますね。

質問者：なるほど。ありがとうございます。質問は大丈夫なようなので、これにてセッションを終了したいと思います。改めまして、鈴木健一さんありがとうございました。

鈴木：ありがとうございました。