Haskellライクな構文をEgisonに実装している話

これは言語実装Advent Calendar 2019の2日目の記事です。

私は少し前から、楽天技術研究所でEgisonの開発アルバイトをしています。入社してから初めての大きなプロジェクトとしてEgisonの構文を新しくするというのを担当しているので、その紹介と、設計/実装で悩んだ(でいる)ことなどを書こうと思います。

Egisonとは

Egisonについて聞いたことがないという人はとりあえず公式サイトを見てほしいのですが、概要としては

  • 表現力豊かなパターンマッチ(非線形パターン*1など)
  • (上のパターンマッチを利用して実装された)数式処理システム

を強みとし、プログラムや数式を簡潔に記述できることに重きを置いているプログラミング言語です。

これまでEgisonはS式(Lispのようなカッコが多い文法)の構文を持っていましたが、Lispに習熟している人を除く大抵の人にとってはS式はあまり読み書きしやすいものではありません。また、Egisonでの記号の使われ方はLispから着想を得ているものが多くありましたが、Lispに慣れていない人からすると意味がわかりにくいものも多くあり*2、Egisonの新しいユーザが増えない一因になっていました。 そのため、Egisonの構文を一新し、Lispに慣れていない人にとっても読み書きの障壁が小さいような構文を作ろうということになり、Egisonの実装にも使われているHaskellのような構文を目指して新しいパーサの実装が始まりました。

新しい構文のデザイン

正式な構文の定義はまだまとめていないので構文のテストケースを載せます。

egison/syntax.egi at master · egison/egison · GitHub

双子素数の例で古い構文と比較してみると、次のような感じです。

; 古いS式の構文
(define $twin-primes
  (match-all primes (list integer)
    {[<join _ <cons $p <cons ,(+ p 2) _>>> [p (+ p 2)]]}))
-- 新しい構文
twinPrimes :=
  matchAll primes as list integer with
  | _ ++ $p :: #(p + 2) :: _ -> (p, p + 2)

この他にも、nons-test というディレクトリの下に色々な例があります。

読み方に関して補足すると、

  • -- から始まる行と {- -} で囲まれている部分はコメント
  • 変数定義も普通の式も両方トップレベルに書けるようになっている
    • トップレベルに書かれた式は、Egisonを -t オプションをつけて実行すると上から順に評価結果が出てくるようになっている
-- 変数(someFunction)の定義
someFunction x y z :=
  x + y * z

-- 式
assertEqual "function definition"
  (someFunction 1 2 3)
  7
  • assertassertEqual で始まる式がテストケースになっており、assert は 第2引数の評価結果がTrueなら、 assertEqual は第2引数と第3引数の評価結果が等しければassertionが通る

12月1日現在、新しい構文は最新版のEgisonで -N フラグで試せるようになっています。まだテンソル関係の記法の設計や実装が終わっていませんが、基本的な構文は安定して使えるようになっており、11月のEgison Workshopでの講演・ハンズオンも新しい構文で行いました。

以下に新しい構文のポイントを書いていきます。

Haskellとの差異

何度か述べた通り、新しいパーサは全体的にHaskellに近い雰囲気の構文を目指して開発していますが、異なるところもいくつかあります。

  • パターンマッチはML風に match で書く
  • マッチ節の先頭に | をつけるようになっている (guardではない)
  • 変数束縛(Haskellでは = )が :=
    • Leanの影響を受けているらしい*3
  • 等号(Haskellでは == )が =
  • consは(パターンも関数も) :: で表す
    • Leanに倣っている & joinパターンが ++ なので、同じ2文字にしたかった
    • : は将来Egisonに型システムが入った時に型アノテーションとして使う

Offside ruleとoptional layout

Haskellと同様、offside rule (インデントの深さをパースに利用する) を以下の式で採用しています。

  • 関数適用
    • 引数がどこまで続いているかを判定する
    • 一番最初の項(関数)よりインデントが深ければ引数
  • let
  • do
  • match
  • matcher

offside ruleを程よく導入することでカッコやキーワードに頼らなくても複雑なプログラムを書けるようになるというメリットがありますが、一方でシェル芸など1行でプログラムを書きたいという場合には相性が悪いので困ってしまいます。

そこで、let 式や do 式などは {} で囲んで ; で区切れば改行なしで書けるようにしています。例えばlet式は、次のように2通りの書き方で書くことができます。ちなみにこの構文もHaskellのOptional layoutからアイデアを得たものです。

-- 1行目と2行目の間の改行が必須
let x := 1
    y := 2
 in x + y

-- 上と同じ式を改行なしで書いたもの
let { x := 1; y := 2 } in x + y

match 式についても同様のものを実装する予定です。

Sections

Haskellに特徴的なエレガントな記法の1つであるところの section を中置演算子に対して実装しています。

> (+) 10 1
11
> (+ 1) 10
11
> (10 -) 1
9
> (- 2)     -- これはsectionではない(!)
-2

とても細かい話として、GHCでは曖昧なsectionはパースエラーになります*4が、この挙動も再現しています。

> (/ 2 * 3) 3
Parse error at: egison:1:9:
  |
1 | (/ 2 * 3) 3
  |         ^
The operator '/' [infixl 7] must have lower precedence than '*' [infixl 7]

実装について悩んだ点

ちなみに実装はこちらです:

egison/ParserNonS.hs at master · egison/egison · GitHub

使うライブラリ

最初に悩んだ問題として、パーサの実装にどのライブラリを使うのかということがありました。

実装が始まった当初はhappy(パーサジェネレータ)を使うつもりで、途中までhappyで実装を進めていました。 当時の私はパーサコンビネータを使い慣れていなくて苦手意識があり、それよりも大学の演習などで親しんでいたパーサジェネレータの方が扱いやすいと思っていたことや、GHCのパーサでもhappyが使われているのを目にしていたことが理由です。 しかし、indent-sensitiveな構文を実装する機構がhappyではあまり整っていなかった*5一方、 Haskellのパーサコンビネータライブラリでは充実していたことから、happyの実装を捨ててmegaparsecに乗り換えることにしました。*6

トップレベル表現

Egisonでは、トップレベルの表現において変数宣言も普通の式も出現しうるようになっています。

変数宣言の時に define のようなキーワードを要求するのであればこのような仕様でもパースには全く問題ありませんが、Haskellでは、変数宣言の時に前に何かをつける必要はありません。新しいEgisonの構文でもこれに倣い、定義式の前に何もつけないデザインにしようと思いました。

このため、与えられた文字列が変数宣言なのか式なのかが := を見るまでわからないということになりますが、今回は := の左側に任意個の引数がくることを許しているため、無限の先読みが必要になってしまいます。

-- fという名前の恒等関数を宣言する構文
f x := x

-- 式
assertEqual "f is identity"
  (f 1)
  1

これに対して、 try (パースが失敗したら最初からやり直すことを指示する(mega)parsecの関数) をしながら式のつもりでパースをし、ダメだったら変数宣言のつもりでパースし直す、ということもできますが、Parsec: “try a <|> b” considered harmful で解説されているようにエラーメッセージの質が落ちてしまうのでそれはしたくないという気持ちがありました。

そこで今回の実装では、任意の文字列は式だと思って読み始めて、:= が出てきたらそれまでのパース結果を変換する(パースのやり直しはしない)、という方針にしました。実際ほとんどのケースでは、変数宣言のつもりで書かれたプログラムの := より前の部分(上のf x)は関数適用の式としてパースされているはずで、これをいい感じに変換してあげることはそんなに難しくありません。

なおEgisonでは、次のように引数の前に*%などのprefixをつけることができるので := の前の部分が二項演算の式としてパースされている場合があり、これもややトリッキーですが対応しました。

f *x %y z := ...

match式のインデント基準点

新しい構文でのmatch式はOCamlのそれに似たようなものになっていて、マッチ節の先頭に | を書くようになっています。 Haskellではcase式には | がなく、代わりにguardとして使われますが、マッチ節の先頭に何かしらの記号があった方が見やすいと思うため、またguardはEgisonのパターンマッチで表現できるため、です。

match [1, 2, 3] as list integer with
| #1 :: _ -> True
| #2 :: _ -> False

また、今回のパーサでは、OCamlとは違ってmatch節のパース時にインデントの深さの情報を利用したいという気持ちがありました。 これは、ネストしたmatch式がある時にわざわざ小さい方のmatch式をかっこで括らなくても思った通りに動いてほしいためです。*7

match [1, 2, 3] as list integer with
   | #2 :: $x -> match x as multiset integer with
                 | _ -> False
   | #1 :: $x -> match x as multiset integer with
                 | #1 :: _ -> False
                 | #2 :: _ -> True

ところでOCamlでは最初の|は書かなくても良いため、書かない流派の人が一定数存在するという話があります。

(* EgisonではなくOCamlのプログラム例です *)
match [1, 2, 3] with
  [] -> ...
| x :: xs -> ...

(* マッチ節が1つのみで1行で書きたい時は特に省略しがち *)
match [1, 2, 3] with x :: xs -> ...

こういった事情を踏まえて、最初の | が欠けている可能性がある場合に、インデントガードをどこでとればいいかということにしばらく悩んでいました。最初の|が欠けている可能性があるなら、「全ての|の位置が揃っている」という条件を加えることはできません。一方で「|の次のトークン(パターンの先頭)が揃っている」という条件にすると、次のように|が全部揃っていてもたまたまパターンの先頭が揃っていなかった場合にパースエラーが出ることになってしまい、非直感的だと思いました。

-- | の次のトークンで揃えることにしたらパースエラーになるケース
match [1, 2, 3] as list integer with
| (#2 | #3) :: _ -> False
|  #1 :: _ -> True

結果的に、match節が複数ならば最初の| を必須にする という方向にしようと思っています。

-- OK
match [1, 2, 3] as list integer with $x -> True

-- OK
match [1, 2, 3] as list integer with
  $x :: _ -> True

-- OK
match [1, 2, 3] as list integer with
| #1 :: _ -> True
| #2 :: _ -> False

-- OK  (`|` はmatchキーワードより左側にあっても良い)
match [1, 2, 3] as list integer with
| #1 :: $xs -> match xs with
    | #2 :: _ -> True

-- NG
match [1, 2, 3] as list integer with
  #1 :: _ -> True
| #2 :: _ -> False

-- NG
match [1, 2, 3] as list integer with #1 :: _ -> True
                                   | #2 :: _ -> False

/ の扱い

もともとEgisonでは / をidentifierの一部として扱っており、/を名前に含むようなライブラリ関数が多く定義されていました。

例えばeq?/mは、次のようにmatcherを第1引数にとり、そのmatcherで定義されているvalue patternのequalityについて等しいかどうかを返す関数です。 この場合の /m は with matcherの意味を表しています*8

> ; 従来のS式の構文のEgison
> (eq?/m (multiset integer) {1 2 3} {3 2 1})
#t

また、Egisonの数式処理システムの機能の1つとして提供されている微分を計算する関数d/d/を名前に含みます。

> ; 従来のS式の構文のEgison
> (define $f x^3)  ; f = x^3
> (d/d f x)        ; df/dx = 3 * x^2
(* 3 x^2)

S式のように/を中置演算子として扱う必要がない構文ではこのような命名規則は問題ありませんでしたが、新しい構文では/を中置演算子にしたかったので、扱いに悩みました。

/ をidentifierに使うことを完全に廃止し、/を名前に含んでいた関数群の命名規則を変えることも考えましたが、 d/d の名前はそのまま残しておきたかったということがあり、新しい構文でも / をidentifierの一部とすることにしました。 よって、/を割り算の記号として解釈してほしい(かつ、/の前がアルファベットである)場合は、/の前にスペースを入れてもらうようにすることになります。

x/2    ; 'x/2' というidentifier
x / 2  ; 'x' を2で割る

今後の課題

新しい構文のpretty printer (#96)

Egisonは今まで9年間ほどずっとS式の構文を持っていたため、S式の構文で書かれたサンプルプログラムが沢山ありますし、たくさんある標準ライブラリも全てS式で書かれています。また、新しい構文が安定したら古いS式の構文はサポートをやめる予定なので、今までにEgisonに親しんでくれていたユーザが書いてきたプログラムも実行できなくなってしまいます。

これらを全て手動で新しい構文に翻訳するのはとても大変なので、Egisonの古い構文で書かれたプログラムをパースして新しい構文でpretty printしてくれるプログラムを実装することにし、現在実装中です。 新しい構文のpretty printerが実装できればformatterもできたことになるはずなので一石二鳥...?

標準ライブラリの移行 (#133)

上のpretty printerの箇所でも触れましたが、Egisonの標準ライブラリはまだ古い構文で書かれたものしかなく、新しい構文でEgisonを起動した際もライブラリの読み込みは古いパーサで行なっています。

ところで、古い構文と新しい構文では変数の命名規則が少し異なります。古い構文では、take-while のように語の句切りを - でつなげていましたが、-を中置演算子に持つ新しい構文ではもちろんこれは使えないので takeWhile のようなcamel caseを採用しています。

現在は標準ライブラリで定義されている関数にcamel caseの名前を新しく与えるというワークアラウンドによってライブラリ関数を使えるようにしていますが、古いパーサはそのうちdeprecateしたいことなどを考えると新しい構文でライブラリを書き直す必要があります。 pretty printerが出来上がってきたらそれを使ってやることになると思います...

また、現在のEgisonでは + などの算術演算子は任意個の引数を取れるようになっています。

> (+ 1 2 3)
6

このような関数は現在、b.+ という引数を2個しか取らない加算関数と、 cambda という任意個の引数を取れるラムダ式を組み合わせて実装されていますが、新しい構文では中置演算子+ は引数を2個しか取りえずcambdaを使う意味がないので、このあたりの実装も適切に変える必要がありそうです。

pattern constructorとpattern functionの区別

Egisonで提供されている、パターンに対して名前をつけることができる機能として次の2つがあります:

  • pattern constructor
    • matcher で定義される。listのconsjoinなどもパターンコンストラク
  • pattern function
    • pattern-function で定義される。パターンを受け取ってパターンを返す、文字通りパターンの関数

古い構文では、pattern constructorの適用とpattern functionの適用の区別が次のように構文によってなされていました。

> ; 'snoc' というパターンコンストラクタを使う
> (match {1 2 3} (list integer) {[<snoc $x $xs> [x xs]]})
[3 {1 2}]
>
> ; 'snoc2' というパターン関数を'snoc'を使って定義
> (define $snoc2 (pattern-function [$x $xs] <snoc x xs>))
>
> ; 'snoc2' というパターン関数を使う
> (match {1 2 3} (list integer) {[(snoc2 $x $xs) [x xs]]})
[3 {1 2}]

pattern constructorは <snoc $x $xs> のように < >で囲んでいるのに対し、pattern functionは(snoc2 $x $xs) のように ( ) で囲んでいます。

これら2つを、新しい構文では同じ記法で使えるようにし、2つの区別を処理系本体で行うようにしたいと思っています。

> match [1, 2, 3] as list integer with snoc $x $xs -> (x, xs)
(3, [1, 2])
>
> -- snoc2の定義。(pattern function は `=>` で表すことにしている)
> snoc2 := \x xs => snoc x xs
>
> match [1, 2, 3] as list integer with snoc2 $x $xs -> (x, xs)
(3, [1, 2])

data constructorと変数の扱い

前述のpattern constructorとpattern functionの区別と似た問題ですが、data constructorと変数をどのように区別するかという問題もあります。

古い構文では、

  • < >で囲まれていて、大文字で始まるものはデータコンストラク
  • そうでないものは変数

という区別がなされていました。新しい構文では当初、

  • アルファベットの大文字で始まるものはデータコンストラク
  • アルファベットの小文字、ギリシャ文字、数学記号(∂ 等)で始まるものは変数

としようと思っていましたが、Egisonを数式処理システムとして使う場合を考えると変数名に大文字が使えた方が良い(例えば行列の名前は大文字の方が自然)ということに最近なり、解決策を検討しています...

ユーザ定義中置演算子のパース (#134)

現在、式(expression)やパターンの中置演算子はパーサにビルトインで定義されているものだけが使えますが、将来的にはユーザが自分で定義した中置演算子を式やパターンで使えるようにしたいと思っています。

エディタ拡張のnew syntaxへの対応

Egison用のエディタプラグインVim, Emacs, Atomなど様々なエディタ用に作られていますが、これらを新しい構文に対応させる作業も必要になってきます。

最後に

新しい構文は来年の4月にversion 4.0.0としてリリースすることを目標にしているので、Egisonを今まで使ってきた人もそうでない人も是非楽しみにしていてください!また前述の通り、基本的な構文に対するパースは(pattern-functionの適用以外)割と出来ていて、-N オプションで使うことができるようになっているので、試してみて不具合を見つけた人はIssue等でお知らせいただけると嬉しいです。

Changelog

  • 2019/12/2. Haskellでは | がguardであったことを思い出したのでその辺の追記

*1:あるパターンの中で束縛された変数を同じパターン中で利用できる。これによって例えば双子素数を抽出するパターンが簡潔に書けるようになっている

*2:例えば value pattern では値の前に ',' をつけるようになっており、これはCommon Lispのunquoteに由来するものですが、',' をprefixとして扱うプログラミング言語は少ないため、Lispの素養がない人にはパースが難しい気がします

*3:「らしい」と書いたのは、これが江木さんからのアイデアであり、私自身はLeanを知らないためです

*4:実装するまで知らなかった

*5:GHCではインデントレベルの変化に応じて見えない開きカッコや閉じカッコのトークンを挿入することでオフサイドルールを実現していますが、自分で実装するのがだるかった & 手軽に扱えるライブラリがあるならそれを使った方が良さそうに思えたので

*6:parsecをindentsと組み合わせて使うことなども検討しましたが、結局industrial-strengthであることを主張していてIdrisにも使われているmegaparsecがなんとなく信頼感があり、megaparsecになりました

*7:こういったミスは型がある言語ならコンパイル時の型エラーとして気づけることが多いですが、Egisonには型がまだないので尚更パーサの時点でどうにかした方がいい気がします

*8:call/cc (call with current continuation) から発想を得た命名規則です