Arantium Maestum

プログラミング、囲碁、読書の話題

関数型プログラミング言語における関数適用構文の歴史的経緯についてのメモ

プログラミング言語

先日こういうツイートがあった：

「見にくくは無いですか？」と聞かれると、個人的には「全然大丈夫です」と答えざるを得ないのだが、次のツイートに関しては考えさせられた：

確かに現在の関数型言語の二大巨頭（異論は認める・・・）であるHaskellとML（OCaml・SML）のどちらでも「関数適用にカッコがいらない」という構文が採用された歴史的経緯はあまり知らない。面白そうなので調べてみる。

ちなみに構文の妥当性に関しては大変興味深い話題だとは思うのだが、多分論じるのに必要なHCI的な素養を持っていないので言及は控える。ごく個人的な趣味としてはカッコのない構文は好ましく感じるが、関数適用にカッコを使う言語も好きだし、至るところにカッコだらけの言語も好きだ。

当初の推測

当てずっぽうの推測としては、MLのほうが古くからある言語なので、MLの構文がHaskellに影響を与えた可能性はあるだろうなと思った（ただしSMLはHaskellとほぼ同時に制定、OCamlはその数年後）。まあHaskellの構文はモナド以外ではMirandaに似通っているので、どちらかというとML->Miranda->Haskellの流れか。

あとはラムダ計算に慣れ親しんでいれば、まあこういう感想が自然だよな、と：

ISWIM

とりあえず関数型プログラミング言語のルーツを調べるときはまずLandinのISWIMにあたることにしている。

1966年に書かれたThe Next 700 ProgrammingLanguagesで提唱されたISWIM言語は、実用的な実装はされなかったがその後出てきた関数型言語に多大な影響を与えた。

そのLandinの論文を読むとこういうプログラム例が出てくる：

f(b+2c) + f(2b-c)
where f(x) = x(x-t-a)

上記のように、関数適用にはカッコがついている。

この論文に

ISWIM is thus part. programming language and part program for research. A possible first step in the research program is 1700 doctoral theses called "A Correspondence between x and Church's λ-notation. ''

と書いてあるとおり、プログラミング言語をラムダ計算に対応させることに非常に意識的ではあるのだけど、関数適用の構文は一般的な数学の記法（あるいはFORTRANなどの既存のプログラミング言語）に倣っていたようだ。

Lisp

ISWIMよりさらに前の「プロト関数型言語」ともいうべきLispは、もちろん関数呼び出しにカッコを使う（ただしカッコの位置はALGOL系言語と違うが）。

McCarthyがLispを打ち出した1960年の論文Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part Iには

It is usual in mathematics—outside of mathematical logic—to use the word “function” imprecisely and to apply it to forms such as y2 + x. Because we shall later compute with expressions for functions, we need a distinction between functions and forms and a notation for express- ing this distinction. This distinction and a notation for describing it, from which we deviate trivially, is given by Church

とあり、基本的にラムダ計算に忠実でありたいという意思はあったようだ。

ただし「機械的に評価できる形のラムダ式」であるS式における関数適用の構文は以下のとおり：

An example of an allowed expression is (TIMES, X, (PLUS, X, A), Y), the conventional algebraic notation for which is X(X + A)Y.

そして「意図の伝達のためのメタ表現」であるM式における関数適用は：

We also use brackets and semicolons, instead of parentheses and commas, for denoting the application of functions to their arguments. Thus we write

car[x]

car[cons[(A · B); x]]

となっている。

LCF/ML

SML、OCamlの源流であるMLは元々はLCFという自動定理証明系を操作するためのメタ言語である。MLを搭載したEdinburgh LCFは1973年以降に開発されている。

LCF/MLの関数適用構文に関しては別途記事を書くつもりだが、かいつまんでいうと「本来関数呼び出しの構文はf(x)、ただし省略記法としてf xも許容されていた」ということのようだ。

SMLやOCamlは1990年以降になって登場した比較的新しい言語なので（Haskellと同時かそれ以降）、f xといった構文に統一されたのは他の言語の影響もありそうである。

SASL

HaskellはML系と言えなくもないが、どちらかというともっとも直接影響を受けているのはMirandaという関数型プログラミング言語だろう。Mirandaは構文もHaskellに非常に近く、また遅延評価ベースになっているのも合致している。

Mirandaの作者であるDavid TurnerがSome History of Functional Programming Languagesという文書を出している。MLの話はほとんどないのが面白い点。

TurnerはMirandaを作る前に1972年以降にSASLという言語を作っている。最終的に遅延評価になるこの言語は構文的にはHaskellやMirandaに非常に近く、最大の違いは動的型付けだったことのようだ（Hindley Milner型推論がまだ開発されていなかったため）。

SASLに関しては：

As a medium for teaching functional programing, SASL worked better than LISP because:

...

(b) following Church (1941), function application was denoted by juxtaposition and was left associative, making curried functions easy to define and use

という記述があった。SASLの関数適用の構文は直接チャーチのラムダ計算記法から来ているのか？とも思ってこういうツイートをした：

しかしよく読むとSASLの始まりは

During that course I introduced a simple DL based on the applicative subset of PAL. This was at first intended only as a blackboard notation but my colleague Tony Davie surprised me by implementing it in LISP over the weekend!

だと書いてある。さらに

I was given the PAL tape from MIT when I started my PhD studies at Oxford in 1969.

とも。

PAL

Some History of Functional Programming LanguagesにはPALの構文については言及がない。Wikipediaの記事)も非常に簡潔でサンプルコードがない。ACM Digital Library（最近会員になった）で1968年に出たPAL—a language designed for teaching programming linguisticsを読んでみたところ

There are several ways available to the programmer to indicate the application of a function to arguments. The most obvious is the case where the application is explicit. That is, the programmer writes both the function and its argument(s) in the usual form. For example, writing Add (2, 3) means the application of the function Add to the arguments 2 and 3. Parentheses are not needed to indicate functional application--only to indicate grouping.

という記述があった。ちなみにSome History of Functional Programming Languagesに出てくるもう一つのISWIM系言語であるJohn ReynoldsのGEDANKENは1970年に出てきており、さらに論文にPALに関する記述がある。

GEDANKENも

Since function designators have a right-associative syntax, the usual composition of functions may be written without parentheses; e.g. F(G(X)) may be written as F G X.

とのことだが、この構文はPALのほうが先だと見て間違いなさそうである。

PALの論文で出てくるプログラミング言語はISWIM、LISP、ALGOL、BCPL、PL/Iでいずれもこの関数適用の記法は取っていないので、少なくとも関数型プログラミング言語でこの記法の源流はPALだろう。

ラムダ計算

余談だが大元のラムダ計算も関数適用の記法は実は多少の歴史的経緯がある。

というのも初出であるChurchのAn Unsolvable Problem of Elementary Number Theoryではλa.a(λc.b(c))のような表記になっていて、関数適用にはカッコが必ず使われている。

それが1941年に出たThe Calculi of Lambda-Conversionを見ると

Thus if f denotes a particular !'unction of two variables, the notation ((f a) b) -- which we shall frequently abbreviate as (f a b) or f a b -- represents the value of f for the arguments a, b. The notation (f a) -- which we shell frequently abbreviate as f a -- represents a function of one variable, whose value for any argument x is f a x.

とあってf xという記法が打ち出されている。SASLに関してTurnerが"following Church (1941)"と明示的に指しているのにもこういう記法の整理の歴史が背景にあったようだ。

APL/Forth/Smalltalk

さらに余談だがカッコなしの関数適用のある言語でいえばAPLやForth、そしてSmalltalkがある（後者は関数というのかどうか定かではないが）。それぞれ原案は1957年、1968年、1971年に初出となっており、ForthやSmalltalkはPALとほぼ同時、APLに至ってはPALの10年前にIversonによって記法が発表されている。ただ、これらは全般的にクセのある文法となっており、一連の関数型言語の構文に大きく影響を与えたとは思えない。

というわけでやはり現代の関数型プログラミング言語に見る関数適用の構文の成立過程としては

Lambda Calculus (1941) -> Lisp (1960) -> ISWIM (1966) -> 
PAL (1968nプログラミング言語でのf x構文の初出) -> 
GEDANKEN (1970)/SASL (1972)/LCF ML (1972 ただし省略記法として採用) -> 
Miranda (1985) -> Haskell/SML/OCaml (1990以降)

が正しいようだ。