1プログラミングEgisonとは

本章では，Egisonがどのような言語であるのか紹介する． Egisonとそれが提唱しているパターンマッチ指向プログラミングについて，その大体のイメージをつかんでもらいたい．

1.1プログラミング言語全体の中でのEgisonの位置づけ

プログラミング言語の機能には大きく分けて2種類ある． コンピュータを含むさまざまな機械の操作を簡潔に記述するための機能と，人間の頭のなかにある抽象的な概念をプログラムとして表現するための機能である． コンピュータは物理的なデバイスであるため，前者の機能は必須である． この機能には，たとえばキャッシュやメモリ管理ための操作を自動化する機能などが含まれる． 後者の機能は，プログラマの頭のなかにあるアルゴリズムの認識を，コンピュータ向けに翻訳することなく記述できるようにすることを目指す． コンピュータに解かせたい問題のなかには，その解法に抽象的な概念が関係する問題が多くある． 人間には簡単に理解できる抽象化でも，コンピュータが理解できる形で表現することは難しいことが多い． Egisonは後者の機能の拡充に注力してつくられている．

アルゴリズムを簡潔に記述することを目指す主流の流派は，関数型プログラミング言語である． 関数型プログラミング言語によるプログラムの記述の大きな特徴は，関数を他の組み込みデータ型と同じようにプログラマが扱えることである． 具体的にいうと，関数を別の関数の引数として渡したり，関数を返す関数を定義することができる． そのおかげで，関数型プログラミング言語以外の言語ではモジュール化がむずかしい処理をモジュール化できることが多々ある． 関数型プログラミングでは，物理的なデバイスであるコンピュータの操作は，多くの場合，コンパイラによってプログラマから隠される．

しかし，関数型プログラミング言語でも，頭のなかのアルゴリズムのイメージを，プログラムとして記述できるように翻訳する必要がある場合がある． 非自由データ型を扱うアルゴリズムは，その典型的な例である． 非自由データ型とは，同じデータにたいして複数の同値な表現形があるデータ型のことをいう． たとえば，多重集合（要素の重複を許す集合）は非自由データ型である． \(\{a, a, b\}\)という多重集合は，\(\{a, b, a\}\)や\(\{b, a ,a\}\)とも表現できるからである． ほかには，グラフや数式なども非自由データ型である．

非自由データ型にたいするパターンマッチを可能にすることによって，簡潔に記述できるアルゴリズムの範囲が広げることを目指してEgisonは開発された． Egisonには非自由データ型のデータをパターンマッチするための機能が実装されている． そして，このパターンマッチを活かしたプログラミング・パラダイムであるパターンマッチ指向プログラミングを提唱している．

また，このパターンマッチ機能を活かしてEgisonの上に数式処理システムが実装されている． 数式処理システムとは，\(x + x = 2 x\)や\((x + y)^2 = x^2 + 2 x y + y^2\)のようにシンボリックな計算ができるプログラミング言語のことをいう． Egisonを使えば数式に対するパターンマッチが簡単に定義できるため，数式処理システムが他の言語にくらべて簡単に実装できる． この数式処理システムの簡潔な実装による拡張性を活かして，Egisonにはいくつか数式処理システムとして新しい機能が実装されている． 特にテンソルについての計算を記述するための機能が発展しており，従来ユーザーが定義することが困難であった微分幾何学の演算子を簡単に定義できるようになっている．

1.2第I部 パターンマッチ指向プログラミング

Egisonが提唱する新しいプログラミング・パラダイムであるパターンマッチ指向プログラミングについて，第I部は解説する．

1.2.1パターンマッチ指向プログラミングとは

本節では，いくつかの例をみることによって，パターンマッチ指向プログラミングとはどのようなプログラミング・パラダイムであるのかそのイメージを紹介する．

パターンマッチ指向プログラミングによってプログラムの記述が直感的になっていることのわかりやすい例にintersect関数の実装がある． intersectは2つのリストを引数にとり，それらのリストに共通する要素のリストを返す関数である． Egisonを使って引数のリストをそれぞれ要素の順序を無視する集合としてパターンマッチすると，2つのリストの共通要素にマッチするパターンを記述することにより，intersectを記述できる． プログラムの読み方は次章以降で紹介する．

def intersect xs ys :=
  matchAllDFS (xs, ys) as (set eq, set eq) with
  | ($x :: _, #x :: _) -> x

対して，Egisonのパターンマッチを使わずに関数型プログラミングのスタイルでHaskellで記述すると，リストに対する関数を組み合わせて共通要素を抜き出すための方法を記述する必要がある．

intersect xs ys =  filter (\x -> any (== x) ys) xs

このプログラムは，リスト内包表記を使って以下のように書き直すこともできる．

intersect xs ys =  [x | x <- xs, any (== x) ys]

Egisonのパターンマッチを使ったプログラムは，2つのリストの共通要素にマッチするパターンを記述しているだけであるのに対し，関数型プログラミングでは，どうやってその共通要素を取り出すかその方法をプログラマが考えて記述する． 前者のように「何を計算したいか（what to do）」を記述するプログラミングスタイルは宣言型プログラミング，後者のように「どうのように計算するか（how to do）」を記述するプログラミングスタイルは手続き型プログラミングと呼ばれている． 「何を計算したいか」から「どのように計算するか」が明らかである場合は，「何を計算したいか」を記述する宣言型プログラミングのほうがプログラムが読みやすく簡潔になる． intersectの例の場合は，Egisonが集合のパターンマッチアルゴリズムをモジュール化できるおかげで，宣言的なプログラミングが可能になっている．

少し毛色の違う例として，concat関数をパターンマッチ指向プログラミングで定義する． リストのリストの要素にマッチするパターンを記述することにより，concatを定義できる．

def concat xss :=
  matchAllDFS xss as list (list something) with
  | _ ++ (_ ++ $x :: _) :: _ -> x

concat [[1,2],[3],[4,5]]
-- [1,2,3,4,5]

さらにもう1つのパターンマッチ指向プログラミングの例として，unique関数を定義する． 後方に自身と同じ値が含まれない要素にマッチするパターンを記述することによりuniqueを定義できる．

def unique xs :=
  matchAllDFS xs as list eq with
  | _ ++ $x :: !(_ ++ #x :: _) -> x

unique [1,2,3,2,4]
-- [1,3,2,4]

次章以降で，上記のプログラムで使われているEgisonの構文や，機能，プログラミングテクニックの解説をしていく．

1.2.2第I部の構成

第I部は可能な限りコンパクトに，パターンマッチ指向プログラミングとそのためのEgisonの機能の解説をまとめることを目指した． そのため，本書は前提知識として，関数型プログラミング（Lisp系言語や，OCaml，Haskellを使ったプログラミング）の知識を仮定している． 既存の関数型言語にも存在する簡単な機能については，登場したときに軽く解説するにとどめた．

第I部の構成は以下の通りである． 第2章では，パターンマッチに関係するEgisonの構文を一通り紹介する． 第3章では，パターンマッチ指向プログラミングで頻出するテクニックを紹介する． 第4章では，Egisonのパターンマッチを活かしたプログラミングスタイルであるパターンマッチ指向プログラミングとはなにか解説する． 第5章では，Egison内部のパターンマッチの仕組みも解説する． 第6章では，ユーザーによるマッチャー定義の方法を説明する． 第7章では，実際にプログラミングするときに便利な，無名パラメータ関数やIO入出力するための機能について解説する． 第8章では，EgisonのパターンマッチをHaskellで使うためのライブラリSweet Egisonの使い方を紹介する．

ユーザーとしてEgisonに興味がある読者は，第2章，第3章，第4章，第5章5.1節，第6章を順に読んでいくのがよい． Egisonの設計・実装に興味がある読者は，第2章の前半部分を読んだ後，第5章，第6章を読むことができる．

1.3第II部 数式処理システムとしてのEgison

数式処理システムとしてEgisonがもつ機能を第II部は紹介する．

1.3.1数式処理システムとしてのEgisonとその特徴

数式処理システムとは，\(x + x = 2 x\)のようにシンボリックな計算ができるプログラミング言語のことである． このようなシンボリックな計算は，我々が日頃おこなっている計算の大きな部分を占める． 実際，中学校以降の数学で現れる計算のほとんどはシンボリックな計算を含む． そのため，シンボリックな計算をできるプログラミング言語を作ることは重要である．

数式処理システムを作ることがむずかしい原因は，シンボリックな変数を含む数式が一つの定まった形を持たない非自由データ型であることである． たとえば，\((x + y)^2\)という数式は，\(x^2 + 2 x y + y^2\)という形の数式とも同値である． Egisonの非自由データ型に対しても適用可能なパターンマッチ機能を使うと数式の書き換え処理を簡潔に実装できるために数式処理システムを，既存のプログラミング言語よりもかなり少ないコード量で実装することができる． このような考えをもとに2016年にEgisonで数式処理システムは実装された． この数式処理システムはEgison処理系と統合されており，Egison上で使うことができる．

この数式処理システムの実装は，ほかの数式処理システムの実装にくらべてシンプルである． そのために機能拡張がしやすいというメリットがある． 実際，このおかげで，Egison独自の重要な特徴であるテンソルの添字記法をプログラミングへの導入についても，簡単に実装することができた． テンソルの添字記法をプログラミング言語に導入する手法は，この数式処理システムを使って微分幾何の計算をするプログラムのサンプルを作っている最中に発案され，数週間で実装された．

プログラミング言語に数式処理システムの機能を実装することには，実用的なものが作りやすいという利点がある． 数式処理システムは，手で計算するより速ければ喜ばれるケースが多く，通常のプログラミング言語とくらべて，実行速度がシビアに求められない． 実行速度よりも，普段手で書いている数学記法をプログラムでも記述できることのほうが数学の研究者にとってはうれしいことが多い． そのため，数式処理システムの実装は，新しい記法のプログラミングへの導入を目指すEgisonにとって格好の課題といえる．

1.3.2第II部の構成

第II部の最初に数式処理システムの使い方について解説したあと，Egisonのもつ数式処理システムとしての機能を解説する．

第II部の構成は以下の通りである． 第9章では，数式処理システムの特徴であるシンボリックな計算の方法と，具体的なプログラムの例を紹介する． 第10章では，Egison内部で数式データがどう表現されているのか解説する． 第11章では，簡約システムの詳細として，簡約規則の宣言，数学関数の宣言，型注釈による正規形の指定，型の昇格タワーとその拡張，商の型を解説する． 第12章では，テンソルの添字記法を使ったプログラムの記述の方法を解説する． 第13章では，関数シンボルについて解説する． 第14章では，ここまで解説した機能の実践的な応用として，微分幾何の計算をするプログラムを紹介する．

この本を別の言語で読む: English, 日本語