#:g1: Lispと中置記法

Posted 2015-12-23 15:00:01 GMT

Lisp Advent Calendar 2015の24日目です。

Lispで中置記法を実現しようという試みは本当に昔から存在します。 今回はそんな『Lispで中置記法を』という試みを年代順に眺めてみたいと思います。

そもそも何故中置記法を導入したいのか

中置記法といえば、二項演算子で、X op Yのような形式ですが、 数学でも、f(x, y)や、f x yのような記法は前置演算子ですし、前置で書く演算子は他にもあるので、中置記法であることが眼目という訳でもないようです。
Lispに中置記法を導入したい、というよりは、慣れ親しんだ数学の記法を導入したい、ということが多いように思われます。

前置記法とは

Lispの前置記法が数学に由来するのかは分かりませんが、前置記法(ポーランド記法)の、出自は数学で、考案者のヤン・ウカシェヴィチ氏がポーランド人であることに由来するようです。
面白いのが、前置にすることで優先順位を表記するための括弧を減らすことを目的としていたようで、parenthesis-free notation などとも表現されています。

1×(2+3)÷4という風に括弧が必要な所を÷ × 1 + 2 3 4のように括弧が省略できますが、中置演算子がデリミタ兼ねている所を別途デリミタ(空白等)を用意して補う必要があります。

この辺りの事情からか、常に括弧を明示するLispの記法は、Cambridge Polish notationと呼ばれることもあるようです。

LISP 1 〜 LISP 1.5 (1959年頃)

大元のMcCarthy先生のLISPですが、プログラムを記述するためのM式と、データとしてのプログラムを表現する形式のS式があります。
しかし、そのままS式を書いてしまえば良いじゃないかというユーザー達の選択により、M式はS式に敗退してしまいます。
中置記法の敗退としては一回目でしょうか。

M式中の中置演算子としては、defineの意味の=位しかありません。
あとは括弧の位置が関数の前に来るか後に来るかの違いしかなく、読み易くもないという印象です。

fib = λ[[n];
        [lessp[n;2]→n;
         T→plus[fib[difference[n;1]];
                 fib[difference[n;2]]]]]

LISP 2 (1965年頃)

S式で書くことが広まってしまったLispですが、Algol記法で書いてS式に変換するLISP 2が登場します。
これは、ほぼそのままAlgolなので、Lispで中置記法を実現するという意味では、この時点で完全なものが出てしまったという感があります。
LISP 2以降に登場する中置記法が大抵独自文法なのに対し、Algolとのソースコード上での互換性を持たせようとしていた、というのも注目すべき点かなと思います。 全く広まらなかったようなので中置記法の敗退としては二回目でしょうか。 

integer function fib(n); integer n;
  if n < 2 
  then n 
  else fib(n - 1) + fib(n - 2);
end;

KLISP (1968)

一般には実用化されなかったとされるM式ですが、日本の中西先生が1968年に作成したKLISPという処理系はM式をベースにしたものでした。

LISP 2のようにS式に変換する方式ですが、これはGLISPと呼ばれ、ソースコードがAlgol互換ではなくM式であったのがLISP 2との違いです。
また、LISP 2がAlgolとの融合を図ったのに対し、KLISPでは、LISP 1.5に忠実で、M式をメインに考えた処理系であったといって良いと思います。
中西先生は、その後の著作や作成した処理系でもM式をベースにされていたようです。

CGOL (1973)

1973年にPlatt氏によって考案されたCGOLですが、主に数学の記法に慣れ親しんだMACSYMAプロジェクトの人達の為に用意されたもののようです。
主にMACSYMAプロジェクト近辺のMACLISPやNILで利用されたようですが、次に紹介するLispマシンと同様リーダーマクロによってLispコードと混ぜて記述することが可能です。

define fib(n);
  if n<2 then
    n
  else
    fib(n-1)+fib(n-2)

INTERLISP — CLISP (1976年頃)

INTERLISP方面は、ちょっと変っていて、DWIM機能が進化し、対話性向上の一環として中置記法が取り入れられました。
これはトランスレータではなく、S式の記法の中に中置的な記法を混ぜることができるというもので、中置演算子や、if、繰り返しのforで利用できます。
Common Lispのloopは、forに由来し、S式の中で中置的な記法を使うという手法が受け継がれています。

define((fib (n)
         (if n<2 
          then n
          else fib(n-1)+fib(n-2))))

MIT Lispマシン界隈 (1984頃)

CGOLからの伝統の継承なのか、MIT系商用Lispマシンでも中置記法がサポートされていました。
CGOLとはまた少し違ったもののようですが、下記のように書けます。

(defun fib (n &optional (a1 1) (a2 0))
  #◊
  if n = 1 then
    a1
  else if zerop(n) then
    a2
  else
    fib(n - 1, a1 + a2, a1)
  ◊)

日本のTAO/ELISでも中置記法はサポートされていたようです。

Dylan (1994)

当初のシンタックスはS式でしたが、早い時期からCかAlgolシンタックスの供給を考えていて、最終的にはAlgolシンタックスになりました。
Dylanでは、Lispの伝統を受け継ぎ識別子に-等の記号が使えるため、中置演算子はデリミタで区切る必要があります。
この辺りはLispっぽいなと思う所です。 また、パタンマッチによる衛生マクロの仕組みがあります。

define function fib(n :: integer) => integer
  if (n < 2)
    n;
  else
    fib(n - 1) + fib(n - 2);
  end;
end;

honu (2011年頃)

最近になると、Lispを中置で書くというよりは、一般的なシンタックスのプログラミング言語にマクロを導入する一環としての試みが多いようです。
Racket方面では、Algol記法で書けたり、JavaScript風のhonu等が開発されていますが、中置記法で衛生マクロというDylanの流れを踏襲しているようです。

function fib (n) {
  if (n < 2) {
    n;
  } else {
    fib(n - 1) + fib(n - 2);
  }
}

Readable Lisp S-expressions Project (2013)

Common LispやSchemeに中置記法を導入し、よみやすくするというプロジェクトですが、この“Readable Lisp s-expressions”以外にも類似のものが何点かあります。

define fib(n)
  if {n < 2}
    n
    {fib{n - 1} + fib{n - 2}}

INTERLISPの流れを汲む、処理系内の半トランスレータという感じですが、それに由来する制限や謎の規則があったりし、全体的に中途半端な感じになることが多いようです。

まとめ

Lispの60年弱の中置記法への取り組みを眺めてみました。
ソースコードのトランスレータ方式は50年前、Lispのリーダー/リーダーマクロでどうにかしてみようというのが40年前、S式の中でどうにかしてみようというのは3、40年前からあることがわかります。
また、20年前位のDylanあたりから別の流れとして、中置記法にLisp的なマクロを導入する試みがあり、最近ではこの辺りが合流したりしている様子。
近頃Lisp的な構文指向のマクロを取り入れる新言語が増えてきているように思えますが、逆方向からのアプローチではあるものの歴史は繰り返す感があり感慨深いです。

Lispでの中置記法について色々な方式や提案はありましたが、S式に埋め込んだ中置記法以外は、ぱっとせずに廃れた所を鑑みるに、入門者向け、数学者向け等のシンタックスを用意しても、結局、Lispを書いていてコードをデータとして扱うようになってしまった人はS式を選択してきたということかなと思います。

■

HTML generated by 3bmd in LispWorks 7.0.0

comments powered by Disqus