はじめに
arXivにFeatherweight Goの論文が投稿されていた。この論文ではGo言語から機能を大きく取り去ったモデル言語を作り、それ振る舞いを定義したり型システムを与えている。さらにはFeatherweight Go（FG）にジェネリクスを搭載した_Featherweight Go with Generics (FGG)_というものを定義し、FGGからFGへの変換を与えることでGo言語へのジェネリクス追加が安全であろうことを述べていると思われる。このように、FGは実際のところは型システムなどの議論のために生まれたものであり、処理系などを実装することは恐らく意図されてはいないが、小さくて実装が容易だったのでScalaで実装した。この記事ではまずFeatherweight Goでできることやプログラム例を示し、その後にScala実装について軽く解説する。
また今回の実装は下記のGitHubリポジトリにある。
この記事について、疑問点や誤りなどがあれば気軽にコメントなどで教えてほしい。
発表スライド
この内容を一部社内で発表したが、そのときの資料が下記にある。
Featherweight Goの機能
Featherweight Goは次のようプログラム言語となっている。
-
intなどのプリミティブ型はない - 構造体（
struct）とインターフェース（interface）の定義 - 構造体のフィールドアクセス
- メソッドの定義
- メソッド呼び出し
このように極めて限定された機能しか有しないが、それでも実はそこそこのプログラムを書くことができる。例として下記のプログラムがある2。
package main;
type Nat interface {
plus(a Nat) Nat
}
type Zero struct { }
type Succ struct {
pred Nat
}
func (this Zero) plus(a Nat) Nat {
return a
}
func (this Succ) plus(a Nat) Nat {
return Succ{this.pred.plus(a)}
}
func main() {
_ = Succ{Succ{Zero{}}}.plus(Succ{Succ{Zero{}}})
}
このように、自然数をつくったうえで足し算plusを作り、それで$2 + 2$を計算している。これの結果はSucc{Succ{Succ{Succ{Zero{}}}}} となり、正しく$4$を計算できる。あとはたとえば文字が作りたい場合はこの自然数と文字コードを対応させることができるし、リストを作れば文字列も生み出さる。このようにFeatherweight Goは実用が困難なほど何も搭載していないが、こういうところをいちいち作っていけば同じ表現力になる。
Featherweight Goの実装
ここからは実装について述べていくが、だいたいのところはコードを読んでも分かると思うので、実装上のポイントなどを中心に解説しようと思う。
パーザー
- パーザーは今回の実装で最も苦労した。パージングについてもっと色々な知識があればこうはならなかったのかもしれないが、具象構文から意図したASTが得られるようになるまで色々頭を悩ませた
- 特に型システムを実装したあとで、そのテストのために入力した具象構文がパーズできないなどもあり、相当に時間がかかった
- もしプログラム言語を作りたいけどパーザーに興味がないなら、具象構文をJSONなどにしてしまう（？）という方法もありかもしれない
- ただ、最初からテストを与えながら作ったことはデグレ防止に非常に役だった。複雑な例で壊れるケースを修正したら、その修正で別の部分が壊れているということにすぐ気がつけた
- 特に今回はインタープリターを作ったため、引数から先に評価させるため、そこを優先でパーズするというのも注意しなければならなかった
型チェッカー
- 基本的には論文の型検査ルールをひたすらプログラムしていくだけであり、かなり簡単に実装できた
- また型チェッカーを作ることで生成されるべき型から実はFeatherweight Goの具象構文を勘違いしていたといったところが出てくるなどした
エバリュエーター
- こちらもひたすら論文どおりに実装するだけであった
Scala.jsでWebアプリ化
また、Slackで @xuwei_k さんなどに教えてもらってWebアプリにした。
上記のURLから試してみることができる。
まとめ
実装の解説はあまりしなかったが、Featherweight Goは小さく言語実装にそこまでの手間がかからないのですごく経験が豊富でなくても取り組みやすいと思う。まだやっていないが、いずれはFGGの実装とFGへの変換も着手したい。これらの実装を通して、Go言語にジェネリクスを搭載すると速度が変化するのか？という論争に終止符を打ってほしい。
-
このリポジトリーは現在、著者が改造してしまってGenericsが搭載されたFeatherweight Generics Goとなっている。 ↩
-
https://y-yu.github.io/featherweight_go/ にWeb（Scala.js）の実装があるので、そこで試すことができる。 ↩