そもそも、なぜラムダなのか？

と言ってもラムダ計算の話、その名の由来について。

最近ふと気になって調べてみた。すると、いろんな説を見つけた。と言っても大体は同じだ。

見つけた記事の中でも以下の記事が最もまとまっていたので挙げておく。

Why Church chose lambda | Wisdom and Wonder

ただし上記リンクは参照先のリンクが切れているので、リンクは此方から辿るといい。

math.stackexchange.com

さて、リンクを貼っ付けるだけではなんなので、典拠が明記してある “History of λ-calculus and Combinatory Logic” by J. R. Hindley, F. Cardone から、拙いが抄訳して載せておく。なお、出典の脚注は便利なように私が付けたものだ。

ところで、どうしてチャーチは記号として"λ"を選んだんだろう？

[Church, 1964, §2] *1に於いて、 ホワイトヘッドとラッセルによるクラス抽象に使われていた、"x^"の表記が元になっていて、 最初の改良によって"x^"は、クラス抽象から関数抽象を区別するように"^x"となり、 その後"^"は印刷しやすいように"λ"へと変わることになったと、彼は明言している。 この起源は[Rosser, 1984, p.338] *2でも報告されている。

一方で、晩年彼は二人の質問者に対して、 その選択はもっと偶発なもので、記号が必要でλを選んだのはたまたまだったと語っている。

何れにしても、キャレットがその出自であるようだが、そこに何か深い意味があったわけではないようだ。

ところでSchemeの処理系の一つのGaucheでは、lambdaの略として^キャレットが使えるらしい。*3

先祖返りとはこのことか。

*1:A. Church, 7 July 1964. Unpublished letter to Harald Dickson

*2:J. B. Rosser. Highlights of the history of the lambda calculus. Annals of the History of Computing, 6:337–349, 1984.

*3:http://practical-scheme.net/gauche/man/gauche-refj_24.html

Common Lispのラムダリストと末尾再帰最適化

Common Lispを使い始めてからというもの、Common Lispの流儀に慣れるためにと思い、 do系のマクロやloop、或は外部ライブラリのiterator等を使っていてが、ようやく慣れてきた。 それで再帰する関数を余り書く事がなく、今まで気が付かなかったんだけど。 ふと、リストを操作する関数を末尾再帰で定義してみると、面白い事に気づいた。 何気なく引数にoptional変数を使っていたのだ。

特に面白くも無く突っ込みどころのあるリストの長さを返す関数が例だけど、

(defun f (ls &optional (n 0))
  (if (not ls)
      n
      (f (cdr ls) (+ 1 n))))

optional変数を使う事によって、普通ならletやlabelが有ったり二つに分けたりしていた定義が、 スッキリしていて分かりやすいものになっていた。 何より末尾再帰を用いるメリットとは簡便さに有るのだからこれは良いと思う。 また末尾再帰になれない人に取っては、こちらの方が分かりやすいのではないだろうか？ まぁ、上の例のような無用心に引数を晒すという事は行儀がよくないが。

末尾再帰の最適化を確認する

ところで、上に書いた関数は長大なリストになるとスタックオーバーフローしていた。 どうやら最適化はなされていないようである。 こういうときはディスアセンブルして内部を見てみたいが、どうすればいいのだろう？

実はCommon Lispには標準で関数disassembleが用意されているのでこれを使って中身を見ていけば良いだけだ。 この関数、関数単位でdisassemble出来て、もちろんREPLからも扱える。 ついでにSLIMEだとC-c M-dでシンボルを入力すればアセンブリを見ることが出来る。

さてdisassembleして見ると、残念な事にPUSHしている。 だから、オーバーフローしてしまっていたのだ。

それもその筈でScheme等とは違い、他の多くの言語と同じくANSI Common Lispでは末尾再帰の最適化は定められてはいない。 つまりC等と変わらず処理系しだいという事で、処理系ごとに見ていく必要がある。

一寸調べてみると以下のページを見つけた、また見つけることになると思う。 Common Lispの各処理系毎の末尾最適化有無が纏められていて、大変に参考になる。

http://0branch.com/notes/tco-cl.html

それによると、私が今使っている処理系のSBCLではoptimizeすれば良いようである。

試してみたところ適切に末尾呼び出しがジャンプ命令のみになった。 またcondやcase等でもうまくいった。

Schemeの規格だけどR7RSに書かれているような末尾文脈の例の範囲なら適切に処理してくれそうだ。

まとめ

こういうその場しのぎ的な定義の場合は取り敢えず動けばいいので、 最適化を気にする程には使う事もないかもしれないけど。 これに限らず、最適化する方法が残されているところがCommon Lisp的な気がする。 この場合は処理系依存だけど、後で最適化していけばいいかと言うような。

それと、幾度と無く思い知らされるのがREPLとEmacsとSLIMEが自然に融合した開発環境だ。 本当にすばらしいので全人類に使っていただきたい。 もちろんVimmerにも。

はてなでブログを始めた

特に理由は無いがはてなでブログを始めてみることにした。

しかしアカウント作って早々パスワードを忘れてしまい *1、ログインに失敗し過ぎたために制限を受けることになり。 結局一日経った今日、パスワードを変更してようやくログインすることができた。

それはともかく、前に他のサービスでもログイン制限を受けた事があるが、 曖昧な記述でどれほどの長さ制限されるのか、数時間なのか数日単位なのかすら分からないので、そのぐらい分かるように明記してほしいものだ。 大抵一日も待てばまた使えるようになるが。

*1:流石にアカウントを作って間もないので忘れてはいないはずなのだが、覚えていたものとは違ったようだ。