次の式は 0 に評価されることを意図していると言われていますが、Scheme の多くの実装では 1 と評価されます。
(let ((cont #f))
(letrec ((x (call-with-current-continuation (lambda (c) (set! cont c) 0)))
(y (call-with-current-continuation (lambda (c) (set! cont c) 0))))
(if cont
(let ((c cont))
(set! cont #f)
(set! x 1)
(set! y 1)
(c 0))
(+ x y))))
これをどこから始めればよいかさえ、私にはわからないことを認めなければなりません。継続 と の基本は理解できましたcall/ccが、この表現について詳しく説明してもらえますか？
これは興味深い断片です。私がこの質問に出くわしたのは、 と の正確な違い、およびこれらが異なるバージョンの Scheme レポートと異なる Scheme 実装の間でどのように異なるかについての議論を探していたからletrecですletrec*。このフラグメントを試しながら、いくつかの調査を行ったので、ここで結果を報告します。
このフラグメントの実行を頭の中で考えてみると、次の 2 つの疑問に気付くはずです。
Q1. xおよびの初期化句はどのような順序でy評価されますか?
Q2. すべての初期化句が最初に評価され、その結果がキャッシュされ、その後ですべての代入が実行さxれyますか? それとも、いくつかの初期化句が評価される前に、いくつかの割り当てが行われていますか?
についてletrecは、Scheme のレポートによると、Q1 の回答は「不明」です。実際、ほとんどの実装では、句は左から右の順序で評価されます。しかし、その振る舞いに頼るべきではありません。
スキーム R6RS と R7RS は、letrec*左から右への評価順序を指定する新しいバインディング構造を導入します。また、以下で説明するように、他の点でも とは異なりletrecます。
に戻るとletrec、Scheme は、少なくとも R5RSが Q2 への回答が「代入を行う前にすべての初期化句を評価する」であると指定しているように見える限りさかのぼって報告しています。私が「指定しているように見える」と言ったのは、これが必要であることについて言語がそれほど明示的ではないためです。実際のところ、Scheme の実装の多くはこの要件に準拠していません。そして、これが、フラグメントに関する「意図された」動作と「観察された」動作の違いの原因です。
Q2 を念頭に置いて、フラグメントを見ていきましょう。まず、 と がバインドされる 2 つの「場所」(参照セル) を確保xしyます。次に、初期化句の 1 つを評価します。xそれが の節だとしましょうletrec。この評価の続きを に保存しcontます。この評価の結果は 0 です。ここで、Q2 への回答に応じて、その結果をすぐに に割り当てるかx、後で割り当てを行うためにキャッシュします。次に、他の初期化句を評価します。その続きを に保存しcont、前のものを上書きします。この評価の結果は 0 です。これで、すべての初期化句が評価されました。Q2 への回答に応じて、この時点でキャッシュされた結果 0 を に割り当てることができxます。またはへの割り当てxがすでに行われている可能性があります。どちらの場合でも、 への割り当てはすぐにy行われます。
次に、式の本体の評価を開始し(letrec (...) ...)ます (初めて)。には継続が格納されてcontいるので、それを に取得しc、次に clearcontと とset!のそれぞれxをy1 に取得します。次に、取得した継続を値 0 で呼び出します。これは、最後に評価された初期化句に戻ります。であると仮定しますy。継続に提供する引数は、 の代わりに使用され、(call-with-current-continuation (lambda (c) (set! cont c) 0))に割り当てられyます。Q2 への回答に応じて、xこの時点で 0 の割り当てが (再び) 行われる場合と行われない場合があります。
次に、式の本体の評価を開始し(letrec (...) ...)ます (2 回目)。今contは #f なので、 になり(+ x y)ます。保存された継続を呼び出したときに0 が再割り当てされたかどうかに応じて、どちらかになります(+ 1 0)。(+ 0 0)x
displayたとえば、次のように、いくつかの呼び出しでフラグメントを装飾することで、この動作を追跡できます。
(let ((cont #f))
(letrec ((x (begin (display (list 'xinit x y cont)) (call-with-current-continuation (lambda (c) (set! cont c) 0))))
(y (begin (display (list 'yinit x y cont)) (call-with-current-continuation (lambda (c) (set! cont c) 0)))))
(display (list 'body x y cont))
(if cont
(let ((c cont))
(set! cont #f)
(set! x 1)
(set! y 1)
(c 'new))
(cons x y))))
また、 に置き換え(+ x y)て、 の代わりに(cons x y)引数を使用して継続を呼び出しました。'new0
そのフラグメントを、いくつかの異なる「言語モード」を使用して Racket 5.2 で実行し、Chicken 4.7 でも実行しました。これが結果です。どちらの実装も、x最初に init 句を評価し、 y2 番目に句を評価しましたが、前述したように、この動作は規定されていません。
Racketは Q2 の仕様#lang r5rsに準拠しているため、継続が呼び出されたときに他の変数に#lang r6rs再割り当てするという「意図した」結果が得られます。0(r6rs を試したとき、最終結果がdisplayどうなるかを確認するために、最終結果を a でラップする必要がありました。)
トレース出力は次のとおりです。
(xinit #<undefined> #<undefined> #f)
(yinit #<undefined> #<undefined> #<continuation>)
(body 0 0 #<continuation>)
(body 0 new #f)
(0 . new)
ラケット#lang racketやチキンはそれに準じません。代わりに、各初期化句が評価された後、対応する変数に割り当てられます。したがって、継続が呼び出されると、値が最終値に再割り当てされるだけです。
コメントを追加したトレース出力を次に示します。
(xinit #<undefined> #<undefined> #f)
(yinit 0 #<undefined> #<continuation>) ; note that x has already been assigned
(body 0 0 #<continuation>)
(body 1 new #f) ; so now x is not re-assigned
(1 . new)
さて、Scheme レポートが実際に必要とするものについて。R5RS の関連セクションは次のとおりです。
ライブラリの構文: (letrec <バインディング> <本体>)
構文: <Bindings> は ((<variable1> <init1>) ...) の形式で、<body> は 1 つ以上の式のシーケンスである必要があります。バインドされている変数のリストに <variable> が複数回現れると、エラーになります。
セマンティクス: <variable> は未定義の値を保持する新しい場所にバインドされ、<init> は結果の環境で (不特定の順序で) 評価され、各 <variable> は対応する <init> の結果に割り当てられます。 <body> は結果の環境で評価され、<body> の最後の式の値が返されます。<variable> の各束縛は、その領域として letrec 式全体を持ち、相互に再帰的な手続きを定義することを可能にします。
(letrec ((even? (lambda (n) (if (zero? n) #t (odd? (- n 1))))) (odd? (lambda (n) (if (zero? n) #f (even? (- n 1)))))) (even? 88)) ===> #tletrec に関する 1 つの制限は非常に重要です。<変数>の値を割り当てたり参照したりせずに、各 <init> を評価できる必要があります。この制限に違反すると、エラーになります。この制限が必要なのは、Scheme が引数を名前ではなく値で渡すためです。letrec の最も一般的な使用法では、すべての <init> がラムダ式であり、制限は自動的に満たされます。
「セマンティクス」セクションの最初の文は、すべての初期化句が評価された後にすべての割り当てが行われる必要があるように聞こえます。ただし、前に述べたように、これはそれほど明確ではありません。
R6RS および R7RS では、仕様のこの部分に対する唯一の実質的な変更は、次の要件の追加です。
各 <init> の継続は、複数回呼び出されるべきではありません。
ただし、R6RS と R7RS には別のバインド構造も追加されていますletrec*。これはletrec2 つの点で異なります。まず、左から右への評価順序を指定します。相関的に、上記の「制限」は多少緩和される可能性があります。すでに初期値が割り当てられている変数の値を参照しても問題ありません。
各 <init> は、対応する <variable> の値または <bindings> でそれに続くバインディングの <variable>の値を割り当てたり参照したりせずに評価できる必要があります。
2 つ目の違いは、Q2 に関するものです。ではletrec*、各初期化句が評価された後に割り当てが行われることが仕様で要求されるようになりました。以下は、R7RS (ドラフト 6) の「セマンティクス」の最初の段落です。
セマンティクス: <variable> は新しい場所にバインドされ、各 <variable> は対応する <init> の評価結果に左から右の順序で割り当てられ、 <body> は結果の環境で評価され、 <body> の最後の式の値が返されます。左から右への評価と代入の順序にもかかわらず、 <variable> の各束縛はその領域として letrec* 式全体を持ち、相互に再帰的な手続きを定義することを可能にします。
したがって、Chicken と Racket を使用する#lang racket--- および他の多くの実装 --- は、実際にはletrecs を s として実装しているように見えletrec*ます。
これが1と評価される理由は、のためです(set! x 1)。1ではなくxを0に設定すると、結果はゼロになります。これは、継続を格納している継続変数が、xの後にyの継続に設定されているcontため、実際には継続を格納しているためであり、継続を格納しているためではyありません。x