2020年のEgisonの進捗

去年の12月のAdvent Calendarで、開発中であったEgisonの新しい構文についての記事を書いたのですが、その後の進展などを書いてなかったので書きたいと思います。 また年末が近いので、その他の開発の進捗についても話したいと思います。

構文について

先の記事でも言及していた新しいEgisonの構文をデフォルトにしたversion 4.0を4月ごろにリリースしました。その後もちょっと便利な記法をいくつか追加したので紹介したいと思います。 もともとの構文のデザインと同様、Haskellにアイデアを得ているものが多いです。

ユーザ定義中置演算子

ユーザがプログラム中で自由に中置演算子を定義できるようにしました。 Egisonは式とパターンが別の独立した言語になっているようなものなので、演算子の宣言時も、それが式のためのものなのかパターンのためのものなのか書く仕様にしました。

-- Define a right-associative infix '&&' of priority 5.
infixr expression 5 &&

-- Definition of '&&'.
def (&&) a b := match (a, b) as (eq, eq) with
              | (#True, #True) -> True
              | _              -> False

-- Define a left-associative infix '<>' of priority 7.
infixl pattern 7 <>

def exampleMatcher := matcher
  | $ <> $ as (integer, integer) with
    | $x :: $y :: [] -> [(x, y)]
    | _              -> []

match [1, 2] as exampleMatcher with $x <> $y -> x + y
---> 3

Egisonのパーサの実装にはパーサコンビネータを使っているので、既知の演算子のテーブルを状態として持つStateモナドをパーサーのモナドに加え、パース時に中置演算子の宣言を見たら状態をアップデートするようにするようにしました。そのため中置演算子の宣言文より後にパースされる文の中でないとその演算子を使えないわけですが、現状あまり困ることがないのでそのままにしています。パースの処理を2-passにして、一段階目に演算子の処理を行うようにすれば解決するだろうとは思います。

-- 宣言より前に使うとパースエラー
-- True && False

infixr expression 5 &&

-- ここではOK
True && False

パーサジェネレータだとこういった処理は難しいと思うので、パーサコンビネータの柔軟性が活きる1つの例といえるかもしれません。

2引数関数の中置演算子

Haskellでおなじみの、backquoteで囲むと関数が中置演算子化する機能を追加しました。

> 10 `mod` 4
2
> (`mod` 4) 10
2

これは私が実装したわけではなくて、Hacktoberfest期間中にパッチを送ってくれた方が実装してくれました (#260)。ありがたい...

グローバル定義における def キーワードの追加

v4.0を出した頃はトップレベル宣言の構文はHaskellのそれに似せて、先頭にキーワードを何もつけなくても良いデザインにしようとしていました。

-- v4.0での宣言式の構文
x := 1
f x := x

トップレベルには宣言だけではなく、普通の式も書くことができるため、どちらが来るかわからない状態でどちらもパースできるようにするために工夫する必要があった、というのは1年前のブログでも述べたとおりです。

しかし、インタプリタの機能を拡張していくために構文を色々と足していく中でその工夫が結局立ち行かなくなったため、結局defというキーワードをつけるようにv4.1から変更しました。

-- v4.1以降の宣言式の構文
def x := 1
def f x := x

v4.0で新しくリリースしたばかりの構文をまた変更するのは正直やや心苦しかったですが、今回ばかりは仕方がないかなという気持ちです。 これ以上構文を大きく変更する必要がないことを願いたいです。

カリー化

従来のEgisonには関数の部分適用がなく、引数が足りない場合は実行時エラーになっていました。 ただ簡潔なプログラムを書こうとする上でやはり関数の部分適用はできてほしいので実装しました。 引数が足りなかった場合に新しくクロージャを作ることで実装できます。

-- v4.1以降の挙動
def add x y := x + y
(add 1) 2 -- 3

逆に引数が多かった場合は、必要な分だけ引数をとって関数の本体を評価し、残りの引数を使って関数適用の評価を繰り返し行うようにします。このようにして、関数がまるでカリー化されているかのような挙動を実現することができました。

-- v4.1以降の挙動
def id x := x
id id 3 -- 3

カリー化を導入するにあたって、Egisonの仕様も変更する必要がありました。 それまでEgisonでは、関数に複数の引数が渡された場合、それらを要素とするタプルを作って関数に渡していました*1。 よって次の例で関数fを呼び出す2つの式は等価な挙動をしていました。

-- v4.0での挙動
def f x y := x + y

-- 以下の2つの関数呼び出しは等価
f 1 2    -- 3
f (1, 2) -- 3

また、例えば恒等関数に複数の引数を渡すと、それらがタプルに詰められて返ってくるのが確認できました。

-- v4.0での挙動
def id x := x

id 1 2 3 -- (1, 2, 3)

このような仕様の上に部分適用を足すと奇妙な結果になってしまいます。例えば、2つの引数を受け取って2つ目を返す snd という関数を次のように定義したとします。すると、3行目の呼び出しはエラーになるのに対し、4行目の呼び出しはタプルが返ってきてしまいます。 関数がきちんとカリー化されているならば、4行目のようなカッコがあってもなくても3行目と同じ挙動をすることが期待されるはずですが、そうなっていません。

-- v4.0での挙動
def snd x y := x

snd 1 2 3 4   -- Error: Expected function, but found: 2
(snd 1) 2 3 4 -- (2, 3, 4)

このような奇妙な挙動を防ぐため、カリー化の導入に併せて、関数の複数引数をタプルに詰めて渡す仕様をなくすことになりました。

代数的データ型に対する手軽な分解

前述の「関数の複数引数をタプルに詰めて渡す仕様」をなくしてしまったことにより、関数の引数位置でタプルを手軽に分解することができなくなってしまいました。

-- v4.0での挙動
def snd x y := y
snd (1, 2) -- 2

これでは不便なので、タプル等の代数的データ型に対する簡単な分解が引数位置およびlet式でできるようにしました。「簡単な分解」というのは、matcherを指定して行うEgisonのパターンマッチではなく、HaskellOCamlなどで使えるようなデータコンストラクタに対する単純な分解です。 パターンマッチ式とは異なり、引数位置ではパターンが1つしかかけないため、マッチに失敗したら実行時エラーとなります。

-- v4.1以降での挙動
def snd (_, y) := y
snd (1, 2) -- 2

def fromJust (Just x) := x
fromJust (Just 1) -- 1
fromJust Nothing  -- error

let (_, y) := (1, 2) in y -- 2

let (Just x) := Just 1 in x -- 1

ちなみに最後の例での (Just x) のカッコは今のところ必須にしています。これはEgisonでは大文字始まりのidentifierも変数名として認められるので、次のようにカッコなしでは変数(関数)の宣言と見分けがつかないためです。

let Just x := ...

数式処理周りのパフォーマンス改善

項書き換えのプログラムのHaskell移行

Egisonには数式処理システムが備わっており、数式をシンボリックに評価することが可能になっていました。 また、いくつかの標準的な関数 (三角関数、指数・対数関数、sqrt, rt など) についての知識を使った書き換え規則が登録されており、これらを使った式は簡約できるようになっていました。

> (sin x)^2 + (cos x)^2
1

v4.0までは、この書き換えの部分をEgisonで実装していました。 Egisonのパターンマッチのおかげで、標準形を持たない数式データ構造に対する操作が簡潔に書けていたのですが、インタプリタで実行していたので必然的に遅く、 特に数式処理が絡んだプログラムではパフォーマンスの悪さの原因になっていました。

そこで、EgisonのパターンマッチをHaskellで利用するための新しいライブラリであるsweet-egisonを使って、数式処理の部分のプログラムをインタプリタ本体に実装し直しました。 同種のライブラリとしてminiEgisonもありましたが、sweet-egisonはこれよりもパフォーマンスがかなり改善されており、Haskellのリスト内包表記と比較しても引けをとらない性能になっています。*2

sweet-egisonを用いてインタプリタに実装した結果はこちら。 パターンの構文が数式用に特別に拡張されていた*3Egisonインタプリタと比べればパターンの構文が制限されている分、少しごちゃっとして見えるかもしれませんが、 多重集合についてのcons patternが使えるだけでも、数式中の全ての項を探索するようなループを書かなくて済むので助かります。

数式の書き換えをHaskellに移植した結果、例えばこのリーマン曲率テンソルを計算するプログラムインタプリタでの実行*4が140秒程度から10秒程度へと、かなり速くなりました。

対称なテンソルの添字記法

これは江木さんが10月の「自作プログラミング言語の集い」という勉強会で発表していた内容です。(スライド)

テンソルというのは多次元配列のことで、ベクトル(1次元テンソル)や行列(2次元テンソル)の概念の拡張です。 数学や物理の世界で登場するテンソルは添字の対称性を持つことが多いため、手計算でテンソルを計算する際はこれを利用して計算を省略するそうです。 Egisonでは数学や物理のプログラムを簡潔に書くことも目標の1つとしているため、同様の効率化を行って計算を速くしたいというモチベーションがありました。

結果、次のような新しい構文を導入することで対称性のあるテンソルを宣言できるようになりました。 次のプログラム中で宣言されている R という行列は、R_i_j = R_j_i という関係が任意のi,jについて成り立っており、つまり1つ目と2つ目の添字が対称になっています。 _i_jという2つの添字を{}で括ることによってこれをインタプリタに伝えることができ、行列の上三角部分のみ評価すれば済むようになります。

-- 対称テンソル. (R_i_j = R_j_i)
def R{_i_j} :=
  [| [| 1, 2, 3 |]
   , [| 2, 1, 2 |]
   , [| 3, 2, 1 |] |]

また、テンソルには反対称性という性質を持つものもあります。 次に示す S というテンソルの宣言では、 S_i_j = - S_j_i という関係が全てのi,jについて成り立っており、このように符号の正負が反転する対称性を反対称性と呼びます。 これを表現するためには、該当する添字を[]で囲めば同様の効率化が行われます。

-- 反対称テンソル (S_i_j = - S_j_i)
def S[_i_j] :=
  [| [|  0,  1, 2 |]
   , [| -1,  0, 1 |]
   , [| -2, -1, 0 |] |]

ちなみに、対称性と反対称性は次のように入れ子にして一緒に使うこともできます。

def R{[_a_b][_c_d]} := ...

以上のような対称・反対称テンソルの構文は糖衣構文として実装しています。詳細は Issue #231 をご覧ください。

ドキュメント

Egisonのドキュメントは以前はEgisonの公式Webサイト (ソース) の一部となっていたのですが、 HTMLを直に書くようになっていたので書きづらかったり、サーバ管理者がpullしないと実際のページがアップデートされないので管理しづらいなどの問題がありました。 そこで、頻繁に変更が必要なドキュメントの部分をReadTheDocsに移行し、GitHubのレポジトリにpushした時に自動でページをReSTのドキュメントから生成されるようにしました。

https://egison.readthedocs.io/en/latest/

検索機能もついて便利になったので、是非使ってみてください!

*1:この挙動は、Pythonの可変個の関数引数を *arg で全て受けるのと似ているかもしれません

*2:https://github.com/egison/sweet-egison#miniegison-deep-embedding-vs-sweet-egison-shallow-embedding

*3:例えばapplyパターンなど

*4:-O3つきでコンパイルした結果