表題

再帰的評価のための rec 特殊フォーム

著者

状態

この SRFI は現在「確定」の状態である。SRFI の各状態の説明についてはここを参照せよ。この SRFI に関する議論についてはメーリングリストのアーカイブを参照せよ。

草案: 2002/05/24-2002/08/24
改訂: 2002/08/12
確定: 2002/12/02

概要

rec という特殊フォームの実装について提案する。このフォームは [Clinger1985] で定義されている rec と named-lambda を結合して一般化したものである。このフォームを使うと、自己参照を行う式を、簡単に非命令的に構築することができる。その重要な用途として、 A. Church の lambda フォームを拡張し、再帰的手続きを直接的に定義することができるようになる。このとき、 let や letrec のような別の特殊フォームを使う必要はないし、 H. B. Curry のコンビネータのような高度な式を使う必要もない。また、define とは異なり、外部環境に変数束縛を導入する必要もない。

論拠

概論

[KCR1998] で定義されている Scheme プログラミング言語には、次のような際立った特徴がある。

構文が単純である。
再帰的定義を推奨している。たとえば、末尾再帰のメモリ効率のよい実装を保証している。
非命令的プログラミングをサポートしている。

そうは言うものの、 Scheme は、次のような性質をもつ、再帰的評価のための構文を提供していない。

可能な限り単純で直観的で数学的記法に近いこと。
再帰を汎用的に記述できること。
非命令的であること。

例

問題 1

階乗を計算する関数を考えてみよう。数学的には次のように表現することができる。

  (F : N |--> 1,            if N = 0;
              N * F(N - 1), otherwise).

この表現は項 (term) であって、定義や命題ではない。

次に、Scheme で階乗関数を表現するための方法を考えてみる。

おそらく最も簡単な方法は、次のような式である。
```
(define (F N)
  (if (zero? N) 1
    (* N (F (- N 1)))))
```
しかし、この式は項ではない。階乗関数を変数 F に束縛している。この式自体は、階乗関数の名前が必要とされている構文コンテキストにおいて記述されることはないだろう。

階乗を関数項として表現するための方法を列挙してみよう。

(let ()
  (define (F N)
    (if (zero? N) 1
        (* N (F (- N 1)))))
    F)

(lambda (N)
  (let F ( (N N) )
       (if (zero? N) 1
	 (* N (F (- N 1))))))

(letrec ( (F (lambda (N)
	       (if (zero? N) 1
		 (* N (F (- N 1)))))) )	F)

((lambda (F)
   (F F))
 (lambda (G)
   (lambda (N)
     (if (zero? N) 1
       (* N ((G G) (- N 1)))))))

これらの式はどれも階乗の無名関数を定義しており、変数には束縛していない。しかし、これらの式はどれも必要以上に冗長であり、期待しているほど直観的ではない。

解法 1

この問題は、すでに [Clinger1985] の named-lambda フォームによって解決されている。それよりも早い時期に、 Kent Dybvig の Chez Scheme では、これとは少し異なる構文により解決されている。この特殊フォームを使えば、階乗関数を次のように簡単に記述できる。

(named-lambda (F N)
              (if (zero? N) 1
                (* N (F (- N 1)))))

この式は関数項であり、階乗が適当な簡潔さで記述されている。

しかし、named-lambda は後のバージョンの Scheme Report からは削除されている。また、Chez Scheme (6.0a) や MIT Scheme (7.7.0) のような最新の処理系にも存在しない (MIT Scheme には named-lambda があるが、別の意味論を持つフォームとなっている)。

問題 2

1 を連続して出力するストリームは次のようにして定義できる。

(define S (cons 1 (delay S)))

再帰的なオブジェクトを定義するためには、階乗の場合と同様に、外部環境に束縛された変数が必要になる。これを改善するために let や letrec を使うと、階乗の場合と同じような問題が発生する。

解法 2

このような自己参照の問題は、 [Clinger1985] で定義されている rec フォームで解決された。このフォームを使うと、次のように記述することができる。

(rec S (cons 1 (delay S)))

この式は非命令的であり、外部の変数束縛を必要としない。

このフォームも後のバージョンの Scheme Report から削除されている。また、我々の観点では、このフォームだけでは、「問題 1」を解決することはできない。「問題 1」に対する解法は次のようになるだろう。

(rec F
     (lambda (N)
       (if (zero? N) 1
	 (* N (F (- N 1))))))

しかしやはり、数学的記法のように、十分に簡潔でも直観的でもない。

提案

以上の理由から、 named-lambda と rec の利点を統合して一般化した rec 特殊フォームを提案する。この特殊フォームを使うと、階乗関数は次のように記述できる。

(rec (F N)
     (if (zero? N) 1
       (* N (F (- N 1)))))

仕様

文法

[KCR1998] に次の文法生成規則を追加する (ここでは非終端記号を踏襲している)。

<derived expression> --> <rec expression>
<rec expression> --> (rec <variable> <expression>)
<rec expression> --> (rec (<variable>+) <body>)

意味論

[KCR1998] のように define-syntax, syntax-rules, letrec, lambda を提供している Scheme 処理系では、以下のようにして rec を実装できるだろう。

(define-syntax rec
  (syntax-rules ()
    ((rec (NAME . VARIABLES) . BODY)
     (letrec ( (NAME (lambda VARIABLES . BODY)) ) NAME))
    ((rec NAME EXPRESSION)
     (letrec ( (NAME EXPRESSION) ) NAME))))

テスト

次のセッションは、 rec が階乗関数の末尾再帰による実装を許していることを示している。

> (define F (rec (F N)
		((rec (G K L)
		   (if (zero? K) L
		     (G (- K 1) (* K L)))) N 1)))
> F
#<procedure>
> (F 0)
1
> (F 10)
3628800

謝辞

Al Petrofsky には、最終的な決定に貢献してくれたことを感謝する。 Hal Abelson, Chris Hanson, およびその他の方々の貢献に感謝する。 SRFI フォーラムのメンテナの方々にも、大きく感謝する。

参考文献

[Clinger1985] EDITOR = {Clinger, W.}, TITLE = {Draft of Report of the October 1984 Workshop on Scheme}, JOURNAL = {Proceedings Brandeis Workshop Oct.~22--23, 1984}, MONTH = {Mar}, YEAR = {1985}, URL = {http://www.swiss.ai.mit.edu/ftpdir/scheme-mail/HTML/rrrs-1985}
[KCR1998] AUTHOR = {Kelsey, R. and Clinger, W. and Rees, J.}, TITLE = {Revised (5) Report on the Algorithmic Language Scheme}, JOURNAL = {Higher-Order and Symbolic Computation}, VOLUME = {11}, NUMBER = {1}, MONTH = {Sep}, YEAR = {1998}

著作権

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

著者: Mirko Luedde

編集者: Francisco Solsona