Egisonのソースを表示

{{Infobox プログラミング言語
|名前 = Egison
|パラダイム = [[関数型言語]]、[[パターンマッチ指向]]
|logo = 
|設計者 = [https://www.egison.org/~egi/ 江木 聡志]
|開発者 = 
|最新リリース = 
|型付け = 強い[[動的型付け]]
|処理系 = 
|影響を受けた言語 = {{lang|en|[[Scheme]]}}、{{lang|en|[[Haskell]]}}
|影響を与えた言語 = 
|website = https://www.egison.org
}}

{{プログラミング言語}}

'''Egison'''（エギソン）はパターンマッチ指向のプログラミング言語である。2014年にはInfoWorldで「活気のある10のプログラミング言語」の1つに選出されている。<ref>https://www.infoworld.com/article/2606823/application-development/146094-Ten-useful-programming-languages-you-might-not-know-about.html</ref>

Egisonの設計・開発は江木聡志によるもので、2015年には情報処理学会ソフトウェアジャパンアワードと第10回日本OSS奨励賞を受賞している。<ref>[https://www.ipsj.or.jp/award/softwarejapan_award.html ソフトウェアジャパンアワード]</ref><ref>[http://ossforum.jp/ossaward10th2 「第10回 日本OSS貢献者賞・日本OSS奨励賞」]</ref>

== 構文 ==
version 3までは(Lispのような)S式の構文を持っていたが、version 4から中置記法（:=，++，::，+など）をサポートするなど、Haskellのような構文に変わっている。

コードは現行の構文(Ver.4以降)で記した。

== パターンマッチの特徴 ==

Egisonは、効率的でかつ強力な表現力をもつパターンマッチが特徴のプログラミング言語である。
Egisonのパターンマッチは、以下のような特徴をもつ。<ref name="#1">https://arxiv.org/abs/1808.10603</ref>

=== 値パターン ===

<code>#(p + 2)</code>のように<code>#</code>からはじまるパターンは、値パターンと呼ばれる、値の同値性をチェックするパターンである。
パターンマッチのターゲットと、値パターンの中身（この例の場合，<code>#(p + 2)</code>）が同値であった場合にパターンマッチに成功する。

[[双子素数]]のパターンマッチ

<syntaxhighlight lang="haskell">
-- 素数の無限リストから全ての双子素数をパターンマッチにより抽出
def twinPrimes := matchAll primes as list integer with
  | _ ++ $p :: #(p + 2) :: _ -> (p, p + 2)

take 8 twinPrimes
-- [(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73)]
</syntaxhighlight>

=== 述語パターン ===

上記の双子素数のパターンマッチを述語パターンで記述する。

<syntaxhighlight lang="haskell">
def twinPrimes := matchAll primes as list integer with
  | _ ++ $p :: ?(\q -> q = p + 2) :: _ -> (p, p + 2)
</syntaxhighlight>

述語パターンの先頭は、<code>?</code>からはじまり、<code>?</code>のあとには 1 引数の述語が続く。

述語を引数に取り述語パターンにする事も出来る。

<syntaxhighlight lang="haskell">
def filter pred xs := matchAll xs as list something with
  | _ ++ (?pred & $x) :: _ -> x

filter (= 2) [1,2,3,4] -- [2]
</syntaxhighlight>

=== and パターン・or パターン ===
and パターンと or パターンの使用例として、[[三つ子素数]]を抽出するパターンマッチを紹介する。

<syntaxhighlight lang="haskell">
def primeTriples := matchAll primes as list integer with
  | _ ++ $p :: ((#(p + 2) | #(p + 4)) & $m) :: #(p + 6) :: _
  -> (p, m, p + 6)

take 6 primeTriples -- [(5,7,11),(7,11,13),(11,13,17),(13,17,19),(17,19,23),(37,41,43)]
</syntaxhighlight>

or パターン<code>|</code>は、<code>p + 2</code>と<code>p + 4</code>の両方にマッチするために使われている。

and パターン<code>&</code>は、<code>p + 2</code>または<code>p + 4</code>にマッチした場合、その値を<code>$m</code>に束縛するために使われている。

この and パターンの使い方は、Haskell に提供されている as パターンの使い方に似ている。

=== 非線形パターンに対する効率的なバックトラッキング ===

非線形パターン（1つのパターン内で同じ変数が複数現れるパターン）に対するパターンマッチをサポートしている。
また、パターンマッチのよるデータの分解方法が複数ある場合でも、パターンマッチのための探索空間を効率よく[[バックトラッキング]]する。

<syntaxhighlight lang="haskell">
matchAll [1..n] as list integer with _ ++ $x :: _ ++ #x :: _ -> x
-- O(nˆ2) で [] を返す
matchAll [1..n] as list integer with _ ++ $x :: _ ++ #x :: _ ++ #x :: _ -> x
-- O(nˆ2) で [] を返す
</syntaxhighlight>

上記の 2 つのマッチ式は、1 から n までの整数のリストから同じ要素の 2 つ組、3 つ組をそれぞれ抽出する。同じ要素の 2 つ組も 3 つ組もターゲットのリストには含まれていないため、これらの<code>matchAll</code>式は両方とも空リストを返す。2 つ目の <code>matchAll</code>式が評価されるとき、Egison 処理系は 2 つ目の<code>#x</code>のパターンマッチまで行き着かない。1 つ目の<code>#x</code>でパターンマッチが失敗するからである。それゆえ、両方の<code>matchAll</code>式の時間計算量は同じである。

=== パターンの多相性 ===

同じパターンを複数のデータ型に対するパターンマッチで使いまわせる。
リストだけでなく、[[多重集合]]や、[[集合]]のパターンマッチもサポート可能なEgisonでは、同じデータをプログラムの違う箇所で別々のデータ型としてパターンマッチすることがある。
例えば、あるリストデータが、ある場所では多重集合として、別の場所ではリストとして、パターンマッチされることが起こりうる。
そのため、パターンの多相性は、パターン記述のために覚えなければならないパターンコンストラクタの名前の数を減らし、パターンの簡潔な記述に役に立つ。

<syntaxhighlight lang="haskell">
matchAll [1..3] as list integer with $x :: $rs -> (x, rs)
-- [(1, [2, 3])]
matchAll [1..3] as multiset integer with $x :: $rs -> (x, rs)
-- [(1, [2, 3]), (2, [1, 3]), (3, [1, 2])]
matchAll [1..3] as set integer with $x :: $rs -> (x, rs)
-- [(1, [1, 2, 3]), (2, [1, 2, 3]), (3, [1, 2, 3])]
</syntaxhighlight>

パターンコンストラクタだけでなく、値の同値性をチェックする値パターンも多相性を持っている。

<syntaxhighlight lang="haskell">
matchAll [1..3] as list integer with #[2,1,3] -> "Matched"
-- []
matchAll [1..3] as multiset integer with #[2,1,3] -> "Matched"
-- ["Matched"]
</syntaxhighlight>

=== パターンの拡張性 ===

パターンごとのデータの分解アルゴリズムを保持するオブジェクトであるマッチャーを、ユーザーが自身で定義できる。
例えば、リスト、多重集合、集合それぞれに対してパターンマッチの方法をユーザが定義できる。

<syntaxhighlight lang="haskell">
def unorderedPair := matcher
  | pair $ $ as (something, something) with
    | ($x, $y) -> [(x, y), (y, x)]
  | $ as something with
    | $tgt -> [tgt]

matchAll (2, "five") as unorderedPair with pair #"five" $x -> x -- [2]
</syntaxhighlight>

<syntaxhighlight lang="haskell">
def multiset a := matcher
  | [] as () with
    | $tgt -> match tgt as (mutiset a) with
              | [] -> [()]
              | _ -> []
  | $ :: $ as (a, multiset a) with
    | $tgt -> matchAll tgt as list a with
              | $hs ++ $x :: $ts -> (x, hs ++ ts)
  | #$val as () with
    | $tgt -> match (val, tgt) as (list a, multiset a) with
              | ([], []) -> [()]
              | ($x :: $xs, #x :: #xs) -> [()]
              | (_, _) -> []
  | $ as something with
    | $tgt -> [tgt]
</syntaxhighlight>

=== 無限の結果を持つパターンマッチ ===

無限の結果をもつパターンマッチをサポートしている。
パターンマッチの探索空間が無限に大きい場合でも、すべての解を列挙するように、Egisonは設計されている。

<syntaxhighlight lang="haskell">
take 8 $ matchAll nats as set integer with $m :: $n :: _ -> (m, n)
-- [(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), (1, 4), (2, 3)]
</syntaxhighlight>

[[Egison#値パターン|既出]] の [[双子素数]] twinPrimesも参照。

== 中置演算子の定義 ==
Egison はユーザーが新しく中置演算子を定義する機能を提供している．中置演算子を宣言するには，infix，または infixl，infixrを使う．infix，infixl，infixrはそれぞれ結合性のない演算子，左結合の演算子，右結合の演算子を定義するのに使う．infix，infixl，infixrは共通して三つの引数をとる．第一引数には，これから定義する中置演算子が関数であるのか，パターンコンストラクタであるのか指定するために，expressionかpatternというキーワードをとる．第二引数には，これから定義する中置演算子の優先度を整数値でとる．第三引数には，これから定義する中置演算子の名前をとる．

中置演算子として使う関数を定義する例として排他的論理和を<code>|^|</code>として定義する。

<syntaxhighlight lang="haskell">
-- Define a right-associative infix '|^|' of priority 3.
infixr expression 3 |^|
-- Definition of '|^|'.
def (|^|) a b := match (a, b) as (eq, eq) with
              | (#True, #False) -> True
              | (#False, #True) -> True
              | _              -> False
</syntaxhighlight>

中置演算子として使うパターンコンストラクタを定義する例

<syntaxhighlight lang="haskell">
-- 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
</syntaxhighlight>

== 関数のカリー化と部分適用 ==

Haskellと同様に関数は[[カリー化]]されている。
標準ライブラリの<code>filter</code>関数は第一引数に残す要素を判定する関数をとる。

<syntaxhighlight lang="haskell">
filter (> 0) [-4, 5, 0, 3, -1, 9] -- [5, 3, 9]
</syntaxhighlight>

ここで、部分適用を使うと整数のリストから正の値のみを取り出す関数positivesは次のように定義できる。

<syntaxhighlight lang="haskell">
def positives := filter (> 0)
positives [-4, 5, 0, 3, -1, 9] -- [5, 3, 9]
</syntaxhighlight>

== その他の例 ==
[[逆ポーランド記法]]評価器の例

<syntaxhighlight lang="haskell">
def calc ls :=
  let f ls str :=
    match ls as list something with
      | $x :: $y :: $zs ->
        match str as string with
          | #"+" -> y + x :: zs
          | #"-" -> y - x :: zs
          | #"*" -> y * x :: zs
          | #"/" -> y / x :: zs
      | _ -> read str :: ls
  in
  let words := S.split " "
  in
  foldl f [] $ words ls

calc "1 2 / pi *" -- [pi / 2]
</syntaxhighlight>

空リストを初期状態とし、f を使って一語ずつ文字列を解釈していく。f は、注目している語が演算子ならばその演算を実行し、それ以外ならば計算スタックに積んでいる。

== IO 入出力 ==

Haskell と同じような方法で副作用をもつプログラムを記述出来る。

=== Hello world! ===

<syntaxhighlight lang="haskell">
def main args := write "Hello world!\n"
</syntaxhighlight>

Egison でつくったスクリプトをコマンドにしたい場合はシェバン（shebang）を使えばよい。

<syntaxhighlight lang="haskell">
$ cat args.egi
#!/usr/bin/env egison

def main args := write (show args)
$ ./args.egi hello world 1
["hello", "world", "1"]
</syntaxhighlight>

=== do 式 ===

do式は Haskell の do記法に対応している。

<syntaxhighlight lang="haskell">
def main args := repl

def repl := do
  write ">> "
  flush ()
  let line := readLine ()
  print line
  flush ()
  repl
</syntaxhighlight>

Egison は静的型システムを持つ言語ではないため，do式は多相的ではない。

Haskell の do式は、リストモナドや Maybe モナド、State モナド、IO モナドなどさまざまなモナドに対して使うことができるが、Egison のdo式は IO モナドに対してしか使うことができない。

== [[数式処理システム]]としてのEgison ==

[[数式処理システム]]は、<math>x + x \to 2x</math>や<math>(x + y)^2 \to x^2 + 2xy + y^2</math>のようなシンボリックな計算ができる。
Egisonもこのような計算をサポートしている。

=== 未定義変数 = シンボル ===

Egisonは未束縛の変数をシンボルとして扱う。
そのため、未定義の変数をプログラム中で使ってもエラーにならない。
またシンボル同士の足し算や掛け算、冪演算が組み込みで定義されている。

<syntaxhighlight lang="haskell">
x + x -- 2x
(x + y)^2 -- x^2 + 2 * x * y + y^2
</syntaxhighlight>

=== 数式の簡約 ===

<syntaxhighlight lang="haskell">
sqrt x * sqrt x -- x
(sin θ)^2 + (cos θ)^2 -- 1
</syntaxhighlight>

=== 微分 ===

Egisonには微分計算をするための関数<code>d/d</code>がライブラリ関数として実装されている。

<syntaxhighlight lang="haskell">
d/d x x -- 1
d/d (x^2) x -- 2 * x
d/d (exp x) x -- exp x
d/d (log x) x -- 1 / x
d/d (x * log x) x -- log x + 1
d/d (1 / log x) x -- -1 / (x * (log x)ˆ2)
</syntaxhighlight>

=== テンソルの添字記法 ===

Egisonは[[アインシュタインの縮約記法]]を含むテンソルの[[添字表記法]]をサポートしている。<ref>https://arxiv.org/abs/1702.06343</ref><ref>http://www.schemeworkshop.org/2017/Scheme17_egi.pdf</ref>

上添字は<code>~</code>、下添字は<code>_</code>を使ってプログラム上で表現される。

例えば、[[リーマン曲率テンソル]]の公式を以下のようにプログラムとしてそのまま記述できる。

<math>R^i{}_{jkl} = \frac{\partial \Gamma^i{}_{lj}}{\partial x^k}
    - \frac{\partial \Gamma^i{}_{kj}}{\partial x^l}
    + \Gamma^i{}_{km}\Gamma^m{}_{lj}
    - \Gamma^i{}_{lm}\Gamma^m{}_{kj}</math>

<syntaxhighlight lang="haskell">
def R~i_j_k_l := withSymbols [m]
  ∂/∂ Γ~i_j_l x~k - ∂/∂ Γ~i_j_k x~l + Γ~m_j_l . Γ~i_m_k - Γ~m_j_k . Γ~i_m_l
</syntaxhighlight>

==脚注==
{{Reflist}}

==外部リンク==
* [https://www.egison.org egison.org] - 公式サイト

[[Category:プログラミング言語]]
[[Category:関数型プログラミング言語]]