Title

Extended LET-syntax for multiple values

Author

Sebastian Egner

This SRFI is currently in ``final'' status. To see an explanation of each status that a SRFI can hold, see here. To provide input on this SRFI, please mailto:srfi-71@srfi.schemers.org. See instructions here to subscribe to the list. You can access the discussion via the archive of the mailing list. You can access post-finalization messages via the archive of the mailing list.

概要

この SRFI は letlet*letrec が多値を受け取るようにする拡張を提案する。この拡張は既存の構文と 完全に互換である。これは、単一の値の束縛、すなわち (let ((var expr)) ...) と、多値の束縛を自由に、 しかも便利に混在できるようにとの意図からである。

新しい構文のいちばん簡単な形式を、例を使って説明する。

(define (quo-rem x y)
  (values (quotient x y) (remainder x y)))

(define (quo x y)
  (let ((q r (quo-rem x y)))
    q))

手続き quo-rem はその継続にふたつの値を渡す。 この値を、手続き quolet 式のなかの qr として受け取る。つまり、let 構文は複数の変数を指定できるように拡張され、式 (quo-rem x y) の返した値を受け取る。

let 構文はさらに、多値の残りの値すべてを残余引き数として 受け取るようにも拡張されている。これもまた例を挙げる。

(let (((values y1 y2 . y3+) (foo x)))
       body)
    

この例で、values は多値を受け取ることを示す 構文的なキーワードで、 y1y2y3+、 は順に (foo x) の返した最初の値、二番目の値、 残りの値を束縛する変数である。この values を使えば、(let (((values . xs) (foo x))) body) のようにしてすべての値を受け取ることもできる。また、 (let (((values) (for-each foo list))) body) のように、値を受け取らない場合を書くこともできる。

多値の束縛は、一般的にデータ構造を構成要素に分解するのに使われる。 この仕組みをもっとも原始的な例で説明する。 (後に定義を挙げる)uncons 手続きは、ペア x を car と cdr に分解し、それをふたつの値として 継続に引き渡す。これを、拡張した let ではこのように受け取ることができる。

(let ((car-x cdr-x (uncons x)))
  (foo car-x cdr-x))

もちろん、ペアに対しては、この手続きは carcdr よりも速くもわかりやすくもない。 しかし、分解時に相当の作業をするようなデータ構造に対しては 話が違ってくる。例えば、プライオリティキューからいちばんプライオリティの 高い要素を取り出し、それと同時に残りの要素から成るキューを作成する、 といったようなことは、それぞれの操作を別個にするよりも 効率よく便利におこなうことができる。 実際、quo-rem 手続きの例は、すでにこの点を 商と剰余は両方とも共通の除算アルゴリズムで計算できる ということで説明している(そして、たいていはこのアルゴリズムを 二回以上実行しないためにキャッシュがもちいられる)。

この SRFI の最後の機能として、多値をヒープに割り当てられるような データ構造に格納する仕組みが規定されている。 values->listvalues->vector は引き数の式を評価して得られたすべての値をリスト(ベクタ)に格納する。 この操作は手続きとしては書けないことに注意してほしい。

論理的根拠

私がこの SRFI を書くに至ったのは、Scheme 多値の現状にうとましさを感じたからであった。 多値は Revised^5 Report on the Algorithmic Language Scheme (R5RS) に必須のものとして規定されてい、 主だった Scheme の実装ではすべて使用可能である。 しかし、これを使おうとすると大抵苦痛に満ちたためらいを感じることになる。

このためらいが起こるのは、多値はほとんど完全に Scheme に組み込まれてはいるものの、それが完全ではないからである (完全というのは例えば、Matlab や Octave、計算器代数システム Magma などの言語で、q, r := quo_rem(x, y); のように関数が多値を返すのがいちばん自然であるようなことを言う)。 しかし、この点についてはかなりの進歩があり、この SRFI は「掉尾を飾る」ちょっとした貢献になると私は思っている。 しかし、まず最初に、この SRFI に関係する範囲で、 Scheme における多値の歴史を説明しておこう。

R5RS では valuescall-with-values を使って、任意の個数の値を 生成側の手続きから消費側の手続きに受け渡すことを規定している。 これが、R5RS にある多値を明示的に扱う唯一の仕組みであり、 多値を扱うものすべてを実装するのに十分な仕組みである。

しかし、John David Stone が SRFI 8 で多値の渡し方を明示的に見せてしまう仕組みに意見を述べた。 「これはあまり面白いものではないね」。 実際 call-with-values は継続が明示的に作られて不格好だった。 SRFI 8(receive <formals> <expression> <body>) という特殊形式を導入して、この状況を改善した。この receive では、式の生成した複数の値を <formals> に指定した変数で受け取り、本体で使用する。

receive の重大な制限は、ひとつの式しか扱えないという ことであった。これは、多値を頻繁に使うプログラムはネストが深くなって しまうということを意味した。そこで、 SRFI 11 では、より多目的な仕組みが導入された。 let-valueslet*-valuesletlet* を真似て作られたが、 <variable> の部分は、引き数リストの <formals> の構文で置き換えられた。 let-values により、多値が Scheme にとって普通のものになったといえるほど便利になった。 しかし、let-values の根本的な短所は、既存の let と互換性がないことであった。 (let-values ((v x)) ...) では x の返した値はすべて(SRFI 11にある通り) v に束縛されるべきだろうか、それとも (let のように)ひとつの値だけが束縛されるべきだろうか。 詳しくは SRFI 11 の discussion archive を参照してほしい。 さらに、let-values には、括弧に耐性がある Scheme ユーザーでさえも括弧の複雑さに悩まされるという問題もあった。

一方、Eli Barzilay の(MzScheme 用の)Swindle ライブラリでは、let を再定義し、多値と内部手続き用の 構文を加えていた。構文上のキーワード values で多値の存在を示し、括弧を加えて(<formals> の構文を使い)右辺の lambda 式を示した。

この SRFI では Eli の方法に従い、構文をわかりやすく (括弧と概念を少なく)したまま、多値を便利に扱う道具を加える。 目標は、Scheme に多値を使いやすいかたちで組み込み、 既存の R5RS の構文と完全に共存することである。 これは、構文をふたつの異なる方法(複数の左辺値と構文上のキーワード)で 拡張することと、(暗默に渡された)値と(第一級の)データ構造を 変換する操作を追加することにより達成される。

最後に、Oscal Waddell らの述べた、 letrec を効率よくコンパイルする方法(Fixing Letrec)と、内部 define の基礎として提案した letrec* についても触れておきたい。 私は、このコンパイル法と letrec* は、この SRFI と完全に互換性があるのではないかと思っているが、 このことを実装によって確かめたわけではない。

仕様

Scheme の構文(R5RS 7.1.3. 節)を既存の構文を置き換えることで拡張する。

<binding spec> --> (<variable> <expression>)

これを以下のみっつで置き換える。

<binding spec> --> ((values <variable>*) <expression>)
<binding spec> --> ((values <variable>* . <variable>) <expression>)
<binding spec> --> (<variable>+ <expression>)

(<variable>+ <expression>) の形式は単純に ((values <variable>+) <expression>) の略記法である。そして、 ここにもともとの R5RS<binding spec> も含まれている。

さいしょのふたつの形式は次のように評価される、 変数が束縛され、式が外側の構文(letlet*letrec のいずれか)にしたがって評価される。 ここで、式は任意の個数の値を継続に引き渡してよく、 この値は指定した変数に格納される。また、. <variable> 形式の場合には残余リストが割り当てられる。

式によって引き渡される値の個数は binding spec に一致しなければならない。 さもなくは、call-with-values の場合と同様にエラーが発生する。これはすなわち、named let の各束縛はちょうどひとつの値を含むということでもある、 named let の束縛は lambda 式の引き数にもなるからである。

標準操作

以下の手続きを標準手続きに追加する。

(define (uncons pair)
  (values (car pair) (cdr pair)))

(define (uncons-2 list)
  (values (car list) (cadr list) (cddr list)))

(define (uncons-3 list)
  (values (car list) (cadr list) (caddr list) (cdddr list)))

(define (uncons-4 list)
  (values (car list) (cadr list) (caddr list) (cadddr list) (cddddr list)))

(define (uncons-cons alist)
  (values (caar alist) (cdar alist) (cdr alist)))

(define (unlist list)
  (apply values list))

(define (unvector vector)
  (apply values (vector->list vector)))

これらの手続きは標準の具体的な構造体(ペア、リスト、ベクタ)を 分解し、構成要素を多値として返す。引き数が予期していたように 分解できない場合にはエラーになる。これらの手続きは上で与えたように 定義する必要はない。

リストを最初のふたつの要素と残りに分解するには (let ((x1 x2 x3+ (uncons-2 x))) body) とし、みっつやよっつの場合も同様にする。これは (let (((values x1 x2 . x3+) (unlist x))) body) 等価ではない。後のものは x3+ に新たに割り当てられた (cddr x) のコピーを束縛する。

最後に、以下のふたつを標準のマクロに追加する。

(values->list   <expression>)
(values->vector <expression>)

これらの操作は引き数の式の返した値を(もしあれば)受け取り 新たに割り当てたリスト(ベクタ)を返す。 values->listlist (引き数をリストにして返す手続き)と同じではないことに注意。

設計原理

構文の設計には、ほかにどんな選択肢を考えましたか?

この SRFI では多値を受け取るのに、キーワード values を使うものと、単純に変数をひとつ以上並べるという、 ふたつの記法を定義しました。 この設計には、いくつもの代替案があり、そのうちいくつかは SRFI 化の議論のなかで提案されました(特に msg00000msg00001msg00002msg00007 を参照)。代替案には以下のようなものがありました。

  1. (let ((x1 x2 expr)) body) のように、単純に変数を並べるだけ(構文上のキーワードなし)
  2. values のようなキーワードだけを使う。例 (let (((values x1 x2 . x3+) expr)) body)
  3. 残余リストをしめすのに dot のようなキーワードを使う。 (let ((x1 x2 dot x3+ expr)) body)
  4. キーワード ... で残余リストをしめす。 (let ((x1 x2 ... x3+ expr)) body)
  5. (let ((x1 x2 (rest x3+) expr)) body) のようにして、キーワード rest で残余リストを示す。
  6. R5RS<formals> の構文を使い (let (((x1 x2 . x3+) expr)) body) のようにする
  7. <formals> のようにするが、 (let ((x1 x2 . x3+ expr)) body) のように括弧を一段階取り除く
  8. 前の同様だが、値のない場合の残余リストだけの場合にだけ 構文を追加する。 (let ((! expr)) body)(let ((xs . expr)) body)

この設計で必要になるのは、既存の let との互換性、 よくあるパターンで使いやすい記法、ありがちな間違いに対するロバストさ、 それと多値を受け取る最大限の柔軟さです。

互換性のためには <binding spec> だけを修正する方法を考えました。ほかの方法で let の構文を変更するものは考えませんでした。 簡潔な記法を考えると、断然便利なのは変数名を並べるものでした。 この表記法は既存の構文にも対応していたので、拡張の基本にも適していました。

しかし、変数名を並べる方法は、残余リストの目印に使いたい "." が、(let ((. xs expr)) body) のように開き括弧のうしろで使えず、また、 (let ((x1 . x2+ expr)) body) のように ふたつの構文要素のうしろに続けることもできないという制限があります。 かといって、この制限を取り除くには、Scheme の構文の無関係な部分に 大幅な変更が必要になり、あまり魅力的ではありません。

変数名を並べる方式のもうひとつの問題点は、変数名がまったくない場合です。 この場合は既存の構文と衝突することはありませんが、 構文のロバストさが深刻なまでにそこなわれます。 (let (((run! foo))) body)(let ((run! foo)) body) はどちらも構文的には正しいのですが、 互いにどちらがどちらなのか混乱しやすくなっています。 このため、変数名を並べる記法は変数名がひとつ以上の場合に制限することに なりました。

これにより、残余引き数と値のない場合をサポートするために 表記を拡張しなければならない問題が残りました。 この問題だけのために ad hoc な方法で解決することもできますし、 すべての場合をカバーするように一般的な記法を追加することもできました。 読みやすさと一貫性(コードを自動処理するときに便利です)の面から 後者を選ぶことにしました。こうして、この SRFI に規定されているような設計になったのです。

値のない場合に values の必要になるのはどうしてですか?

この SRFI では (let (((values) (for-each foo (bar)))) body) という構文で binding spec に束縛される変数のない場合も認めています。 この代わりに binding spec に (<expression>) を認めるようにすることもできました (msg00001 から始まる discussion archive を参照してください)。

この SRFI に規定されている構文は、よくありがちな タイプのまちがい(括弧を忘れる)を静的に検出できるように設計されています。 例えば、(let ((values) (for-each foo (bar))) body) は、この SRFI では認められません。

先に挙げた代わりの構文では (let (((for-each foo (bar)))) body)(let ((for-each foo (bar))) body) も構文的には正しいものになります。 ふたつめの形式が (bar) から引き渡された値を for-eachfoo に束縛するのに対し、 ひとつめのものは (for-each foo (bar)) を実行するだけです。ひとつめの意味のつもりの場合、 (bar) がちょうどふたつの値を返さなかった場合には エラーが通知された方がよいでしょう。そうしないと、foo が呼ばれなかったことにより、もっとあとの方でエラーが明らかになる ことになってしまいます。

この手のあとで高くつく typo を避けるために、この SRFI で提案する構文は必要よりも冗長なものになっています。

手続き用の構文が含まれないのはどうしてですか?

この SRFI では多値を含められるように let 等の構文の拡張を提案しました。これに加えて、局所的な手続き定義を 簡単にするために(例えば、Swindle のように) let の構文を拡張するのも魅力的です。 しかし、この SRFI ではこの機能を含めることはしませんでした。

この SRFI で多値用に構文を制限しなかったのは、 単純さを保つためです。

unlist の名前の由来は?

unlist の命名規則の別の選択肢としては、 list->values というのがあり、こちらの方が逆の操作の values->list とも対称性があります。

しかし、もっと複雑なデータ構造にほかの操作を考えはじめると この対称性にもすぐに限界が見えます。そしてさらに、同じデータ構造に 対してもさまざまな分解操作が用意できることに気づくでしょう。 例えば、deque は先頭部分で分割することも、末尾部分で分割することもできます。 では、この操作のどちらを deque->values という名前にするべきでしょうか。un* という命名規則にすれば、これを自然に解決できます。

データ構造を扱うときの分解手続きの使い方として、 examples.scm の deque の例も参照してください。

どの分解手続きが SRFI に含まれますか?

この SRFI で規定されているリスト分解手続きというのは、 手続きの数を制限することと便利さのトレードオフをあらわしています。

Al Petrofsky は msg00018 の議論のなかで、unlist だけでは、 残余リストがコピーされてしまい不十分であることを指摘しました。 このため、要素の最初の 1, ..., 4 個を分割するのに特化した手続きと、 最初の要素がペアであることを期待する手続きを提供することにしました。 これらの操作がいちばん一般的なもののようです。

実装

リファレンス実装は hygienic マクロを使って R5RS だけで書かれています。しかし、letrec で導入された未初期化の変数へのアクセスをポータブルに検出することは できませんでした。実際の定義は letvalues.scm にあります。この実装では srfi-let/*/rec 等を r5rs-let/*/rec を使って定義しています。 実装者は r5rs-let/*/rec を実装せずに、 let/*/recsrfi-let/*/rec を使って再定義(ないしは再実装)して、これを使ってもかまいません。 r5rs-let/*/rec を実装する効率的な方法は O. Waddell らの Fixing Letrec を参照のこと。

R5RS: この機能を試してみるためのものとして、R5RS の範囲での完全な実装が letvalues-r5rs.scm にあります。ここでは r5rs-let/*/reclambda を使って定義し、srfi-let/*/reclet/*/rec で再定義しています。しかし、これはあまり 効率のよい実装ではないかもしれません。多くの Scheme システムは let 等を特別扱いし、これを lambda に還元するようなことはしません。

PLT 208: PLT のモジュールシステムを使い r5rs-let/*/rec を組み込みの let/*/rec のコピーとして定義し、 srfi-let/*/reclet/*/rec の名前で公開する実装が letvalues-plt.scm にあります。これは効率的です。

これらの新機能を使った例は examples.scm にあります。

参考文献

[R5RS] Richard Kelsey, William Clinger, and Jonathan Rees (eds.): Revised^5 Report on the Algorithmic Language Scheme of 20 February 1998. Higher-Order and Symbolic Computation, Vol. 11, No. 1, September 1998. http://schemers.org/Documents/Standards/R5RS/.
[SRFI 8] John David Stone: Receive: Binding to multiple values. http://srfi.schemers.org/srfi-8/
[SRFI 11] Lars T. Hansen: Syntax for receiving multiple values. http://srfi.schemers.org/srfi-11/
[Swindle] Eli Barzilay: Swindle, documentation for "base.ss" (Swindle Version 20040908.) http://www.cs.cornell.edu/eli/Swindle/base-doc.html#let
[Fix] O. Waddell, D. Sarkar, R. K. Dybvig: Fixing Letrec: A Faithful Yet Efficient Implementation of Scheme's Recursive Binding Construct. To appear, 2005. http://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf

Copyright

Copyright (c) 2005 Sebastian Egner.

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.


Author: Sebastian Egner
Editor: Mike Sperber
Last modified: Sun Sep 11 16:07:38 CEST 2005