🎍

Goで直和型風データ構造を生成するDSLをつくってみた

2023/01/03に公開

概要

簡単な文法を持つDSLであるIno^[1]を作りました。Inoは直和型のデータを定義することができ、それをGoのコードに変換できます。これにより、Goの世界で直和型風のデータ構造を操作できるようになります。
この記事では、主にInoの使い方とInoがどのようにしてGoのコードで直和型風のデータ構造を実現しているのかを説明します。

リポジトリ：github.com/nihei9/ino

動機

Ino開発の動機は、趣味で開発したGo用のパーサジェネレータであるvartan^[2]の使い勝手を試したかったからです（が、この記事ではvartanの話はしません）。vartanには構文解析の結果として構文木を出力する機能があるので、単に文法を定義する以外に、構築された構文木を利用して何かする簡単な言語処理系を作ってみたかったのです。

Inoはまだまだbuggyですがせかっくなので（？）この記事で紹介します。

Inoの使い方

インストール

go install github.com/nihei9/ino/cmd/ino@latest

Inoが生成するコードはジェネリクスを使用するため、Go 1.18以上の環境が必要です。動作確認はgo 1.19.4で行っているので、もしお試しの際はgo 1.19.4以上の環境を用意することをお勧めします。

最も簡単な定義

Inoでの定義とGoへの変換

現在のInoにできることはdataキーワードによる直和型の定義のみです。

最も簡単な定義は以下のとおり、data、型名、=、タグ、;の順で配置します。タグは|で区切ることで複数記述できます。

data Color
    = Red
    | Green
    | Blue
    ;

InoではソースコードはUTF-8でエンコードし、.inoという拡張子をもつファイルに保存します。

上記のソースコードをexample.inoとして保存するとします。以下のコマンドを実行することで、カレントディレクトリ内の.inoをまとめてGoのコードに変換します。

ino --package main

--package mainは生成するGoのコードのpacakgeをmainにするための指定です。--packageオプションは省略可で、省略された場合は--package mainが指定された場合と同様のコードを出力しますが、上記はオプションの例示のためにあえて指定しています。

コマンド実行後、以下のファイルが作成されます。

example.go
ino_builtin.go

値の比較

GoでどのようなAPIが利用できるかを以下の実例を見ながら紹介します。

この例ではmain関数内でInoが生成したAPIを利用しています。このコードを上記のInoが生成したファイルと一緒にgo buildするかgo runすることで実行結果を確認できます。

//go:generate ino --package main
package main

import "fmt"

func main() {
	r := Red()   // var r Color
	g := Green() // var g Color
	b := Blue()  // var b Color

	fmt.Println("`r` is Red:", r.Maybe().Red().OK())     // true
	fmt.Println("`r` is Green:", r.Maybe().Green().OK()) // false
	fmt.Println("`r` is Blue:", r.Maybe().Blue().OK())   // false
	fmt.Println("`g` is Green:", g.Maybe().Green().OK()) // true
	fmt.Println("`b` is Blue:", b.Maybe().Blue().OK())   // true

	fmt.Println("`r` = `r`:", r.Eq(r))             // true
	fmt.Println("`r` = another Red:", r.Eq(Red())) // true
	fmt.Println("`r` = `g`:", r.Eq(g))             // false
	fmt.Println("`r` = `b`:", r.Eq(b))             // false
}

dataで定義した型からは同名のinterfaceが、タグからは同名の関数（コンストラクタ）が生成されます。タグに対応するstructも生成されますが、これをユーザーが直接扱うことは想定していません。
上記の例では、data Colorからtype Color interfaceが、Red | Green | Blueからはそれぞれfunc Red() Color、func Green() Color、func Blue() Colorが生成されています。

コンストラクタが生成する値は、r.Maybe().Red().OK()のようにすることで、あるタグの値であるか否かをチェックできます（左記の例ではrがRedであるか否かをチェックしています）。

また、r.Eq(Red())のようにEqメソッドによって等価性をチェックできます。

上記の例を実行すると以下のような結果になります。

`r` is Red: true
`r` is Green: false
`r` is Blue: false
`g` is Green: true
`b` is Blue: true
`r` = `r`: true
`r` = another Red: true
`r` = `g`: false
`r` = `b`: false

パターンマッチ

InoはパターンマッチのためのAPIも生成します。使用例を以下のコードで説明します。

//go:generate ino --package main
package main

import (
	"fmt"
	"os"
)

func main() {
	cases, err := NewColorCaseSet(
		CaseRed(Red(), func() string {
			return "🍎"
		}),
		CaseGreen(Green(), func() string {
			return "🍏"
		}),
		CaseBlue(Blue(), func() string {
			return "I have never seen blue apples"
		}),
	)
	if err != nil {
		fmt.Println(err)
		os.Exit(1)
	}

	apple, _ := cases.Match(Red())
	fmt.Println(apple)

	apple, _ = cases.Match(Green())
	fmt.Println(apple)

	apple, _ = cases.Match(Blue())
	fmt.Println(apple)
}

パターンマッチを利用するには、NewColorCaseSet関数によってパターンマッチのケースを定義し、Matchメソッドによって検査を実行します。
各ケースは、タグに対応する専用の関数、CaseRed、CaseGreen、CaseBlueによって生成します。Case*関数は第一引数に条件値を、第二引数にパターンマッチに成功した際に実行されるコールバック関数を指定します。コールバック関数の戻り値は多相化されているため、任意の型の値を返すことができます（ただし、同一のNew*CaseSet呼び出し内では同じ型に統一される必要があります）。
New*CaseSet関数は、渡されたケース群が網羅的でない場合はerrorを返します。

実行結果は以下のとおりです。

🍎
🍏
I have never seen blue apples

どのパターンにもマッチしない場合をハンドリングするためにCaseColorDefault関数が利用できます。
Case*Default関数は条件値はとらず、コールバック関数のみをとります。また、コールバック関数にはMatchメソッドに渡された検査対象の値が渡されます。Case*Default関数はケース群の末尾で一度だけ利用できます。

//go:generate ino --package main
package main

import (
	"fmt"
	"os"
)

func main() {
	cases, err := NewColorCaseSet(
		CaseRed(Red(), func() string {
			return "🍎"
		}),
		CaseGreen(Green(), func() string {
			return "🍏"
		}),
		CaseColorDefault(func(c Color) string {
			return "Please 🍎 or 🍏"
		}),
	)
	if err != nil {
		fmt.Println(err)
		os.Exit(1)
	}

	apple, _ := cases.Match(Blue())
	fmt.Println(apple)
}

実行結果は以下のとおりです。

Please 🍎 or 🍏

タグ毎の関数実行

値があるタグに対応する場合だけある関数を呼びたいという場合は、パターンマッチではなく、もっと手軽なApplyTo*関数を利用できます。

//go:generate ino --package main
package main

import "fmt"

func main() {
	apple, ok := ApplyToRed(Red(), func() string {
		return "🍎"
	})
	if ok {
		fmt.Println(apple)
	}
}

ApplyToRed関数は、第一引数がRedの場合にのみ、第二引数の関数を実行します。ApplyTo*関数も多相化されているため、第二引数の関数の戻り値は任意の型にできます。また、ApplyTo*関数の第二の戻り値は、関数が実行され場合はtrueに、実行されなかった場合はfalseになります。

実行結果は以下のとおりです。

🍎

パラメータをもつコンストラクタ

コンストラクタはパラメータをとることができます。パラメータはタグに続けてスペース区切りで複数記述できます。

以下の例ではColor型に加えてPen型を定義しています。ボールペンのコンストラクタであるBallpointPenはペン先のサイズを表すInt型^[3]の値と色を表すColor型の値をとります。

IntはInoの組み込み型でGoのintに対応します。他にはString型が利用可能で、これもそのままGoのstringに対応します。残念ながら現在のInoでは他の型は利用できません。

data Color
    = Red
    | Green
    | Blue
    ;

data Pen
    = FountainPen
    | BallpointPen Int Color
    ;

コンストラクタがパラメータをとる場合に生成されるAPIは、パラメータ無しの場合と比べていくつか異なる点があります。

それぞれ例を見ながら説明します。まずは以下の例です。

//go:generate ino --package main
package main

import "fmt"

func main() {
	bR := BallpointPen(1, Red())
	pointSize, color, ok := bR.Maybe().BallpointPen().Fields()
	if ok {
		cases, _ := NewColorCaseSet(
			CaseRed(Red(), func() string { return "Red" }),
			CaseBlue(Blue(), func() string { return "Blue" }),
			CaseGreen(Green(), func() string { return "Green" }),
		)
		c, _ := cases.Match(color)
		fmt.Printf("Ballpoint %vmm %v\n", pointSize, c)
	}
}

コンストラクタがパラメータをとる場合、bR.Maybe().BallpointPen().Fields()のようにFields()メソッドが利用可能です。このメソッドは、コンストラクタに渡された引数を展開します。戻り値の最後のbool値は、bR.Maybe().BallpointPen()としたときにbRがBallpointPenである場合はtrue、そうでない場合はfalseになります。

実行結果は以下のとおりです。変数pointSizeとcolorにパラメータ値が展開されているのがわかります。

Ballpoint 1mm Red

次はパターンマッチの例です。

//go:generate ino --package main
package main

import (
	"fmt"
	"os"
)

func main() {
	bR := BallpointPen(1, Red())
	bG := BallpointPen(1, Blue())
	cases, err := NewPenCaseSet(
		CaseBallpointPen(BallpointPen(1, Red()), func(pointSize Int, color Color) string {
			return fmt.Sprintf("%vmm Red", pointSize)
		}),
		CaseFountainPen(FountainPen(), func() string {
			return "N/A"
		}),
	)
	if err != nil {
		fmt.Println(err)
		os.Exit(1)
	}

	result, err := cases.Match(bR)
	if err != nil {
		fmt.Println("error:", err)
	} else {
		fmt.Println(result)
	}

	result, err = cases.Match(bG)
	if err != nil {
		fmt.Println("error:", err)
	} else {
		fmt.Println(result)
	}
}

CaseBallpointPenケースを生成する際、第二引数のコールバック関数がBallpointPenコンストラクタと同じパラメータをとるようになっています。

実行結果は以下のとおりです。コールバック関数にパラメータが展開されていること、そして1回目のMatch呼び出しは成功して2回目は失敗していることが確認できます。

1mm Red
error: non-exhaustive patterns

コールバック関数がパラメータをとるようになるのは、パターンマッチ用のAPIだけでなく、ApplyTo*関数も同様です。以下の例でそれがわかります。

//go:generate ino --package main
package main

import "fmt"

func main() {
	bR := BallpointPen(1, Red())
	result, ok := ApplyToBallpointPen(bR, func(pointSize Int, color Color) string {
		cases, _ := NewColorCaseSet(
			CaseRed(Red(), func() string { return "Red" }),
			CaseBlue(Blue(), func() string { return "Blue" }),
			CaseGreen(Green(), func() string { return "Green" }),
		)
		c, _ := cases.Match(color)
		return fmt.Sprintf("Ballpoint %vmm %v", pointSize, c)
	})
	if ok {
		fmt.Println(result)
	}
}

実行結果は以下のとおりです。ApplyToBallpointPen関数から呼ばれるコールバック関数にパラメータが展開されていることがわかります。

Ballpoint 1mm Red

多相化されたdata

dataは型名の後ろに型変数を置くことができます。型変数はスペースで区切ることで複数記述できます。この型変数をコンストラクトのパラメータとすることで、多相型を定義することができます。

以下は、多相化された線形リストを定義する例です。パラメータとして多相型をとる場合は、型名と引数の型を(・)で囲んで記述します。

data List a
    = Nil
    | Cons a (List a)
    ;

多相型のコンストラクタでパラメータをとらないものは、以下の例のNil[String]()のように型を明示的に指定することで具体化して利用します。

//go:generate ino --package main
package main

import "fmt"

func main() {
	l := Nil[String]()
	l = Cons("!", l)
	l = Cons("world", l)
	l = Cons("Hello", l)

	for ; !l.Maybe().Nil().OK(); l = tail(l) {
		fmt.Println(head(l))
	}
}

func head[T Eqer](l List[T]) T {
	if e, _, ok := l.Maybe().Cons().Fields(); ok {
		return e
	}
	panic("list is Nil")
}

func tail[T Eqer](l List[T]) List[T] {
	if _, t, ok := l.Maybe().Cons().Fields(); ok {
		return t
	}
	panic("list is Nil")
}

実行結果は以下のとおりです。

Hello
world
!

Goで直和型風のデータ構造を実現する仕組み

要点

ここまでの説明でほぼ説明してしまいましたが、ここではInoが生成するGoコードについて簡単に説明します。要点は以下のとおりです。

型はinterfaceとして表現する。
タグはstructとして表現する。
コンストラクタは関数として表現する。

以下はdata List a = Nil | Cons a (List a);から生成されたGoコードの抜粋です。
型とコンストラクトは単純にList interface、Nil関数、Cons関数に対応することがわかります。また、タグ名を持ったtag_* structも生成されています。tag_* structはコンストラクタに渡されたパラメータを保持します。
コンストラクタの戻り値はtag_*型ではなくList型なので、Goの世界でもコンストラクタが生成する値は例えばList[String]のように、Inoで定義した型と見た目も一致します。

type List[T1 Eqer] interface {
	Eqer
	Maybe() *matcher_List[T1]
	...
}

type tag_List_Nil[T1 Eqer] struct{}

func Nil[T1 Eqer]() List[T1] {
	return &tag_List_Nil[T1]{}
}

type tag_List_Cons[T1 Eqer] struct {
	p1 T1
	p2 List[T1]
}

func Cons[T1 Eqer](p1 T1, p2 List[T1]) List[T1] {
	return &tag_List_Cons[T1]{p1: p1, p2: p2}
}

`Eqer` interface

型制約としてEqerというinterfaceが登場しますが、これはパターンマッチを実現するために導入したもので、Eqer同士の等価性判定のためのEqメソッドを定義します。

type Eqer interface{
	Eq(Eqer) bool
}

Inoが生成したGoのAPIでは、Go組み込みのintやstring型は、Eqerを実装したIntとStringに変換して利用します（単にtype Int intと定義されるだけなので、Int(100)やint(Int(100))のように相互に変換可能です）。

多相化されたパラメータに渡せる値をGoの組み込み型だけに制限するのであれば、型制約としてcomparableを利用できるのですが^[4]、ユーザー定義の任意の型を渡せるようにしたかったので独自のEqer interfaceを導入しました。

`Maybe`メソッドの必要性

ところで、List interfaceはMaybeメソッドを定義しており、値がどのタグに一致するかの確認にはl.Maybe().Nil().OK()のようなやや長い記述が必要です。
List interfaceに直接IsNil() boolのようなメソッドを定義することもできるのですが、この方法だとタグが多い型を定義する際にすべてのtag_* structが他のタグに対応するIs*メソッドを実装する必要があります。つまり、タグ固有の処理を行うメソッドがList interfaceに定義される度にtag_* structにはタグの数の二乗個のメソッドを新たに生成することになります。個人的にこれが嫌でした。そこで、tag_* structにはタグ固有の処理を行う必要のあるメソッドは実装せず、別なstructに任せることにしました。

まとめ

Ino開発の動機であった自作パーサジェネレータの使い勝手を確認するという点では今のところは非常に簡単な文法のDSLを定義しただけなので未達成。

Goで直和型風のデータ操作を実現する点については、さすがにネイティブにサポートする言語のような流暢な表現はできませんが、まあ妥当なAPIに落とし込めたのではないかと思います。パターンマッチは網羅性判定が半端なのでこれじゃあ使えないですね。

脚注

Inoの名前の由来は、ドラマ「孤独のグルメ」の主人公、井之頭五郎です。理由は開発中に孤独のグルメを観ていたからです。最初は五郎の方からもらって「Gorou」にしようと思ったのですが、これはgoroutineの接頭辞であることに気づいたのでなんとなくやめました。 ↩︎
vartanはLALRのパーサジェネレータで、文法定義から字句解析・構文解析の状態遷移表などを言語非依存な中間形式で生成し、その中間形式からGoのコードを生成します。Go以外のコードも出力できるようする目的で中間形式を介していますが、現在はGoにしか対応していません。 ↩︎
小数を表現できる型を用いる方が適切ですが、現在のInoではGoのintとstring相当の型しかサポートしていないため整数型を用いています。 ↩︎
正確にはstructでも条件を満たせばcomparableになることができます。 ↩︎

概要

動機

Inoの使い方

インストール

最も簡単な定義

Inoでの定義とGoへの変換

値の比較

パターンマッチ

タグ毎の関数実行

パラメータをもつコンストラクタ

多相化されたdata

Goで直和型風のデータ構造を実現する仕組み

要点

Eqer interface

Maybeメソッドの必要性

まとめ

Discussion

`Eqer` interface

`Maybe`メソッドの必要性