recursion - リトルスキームの偶数のみ*＆co

Question

evens-only*&co145ページのTheLittleSchemerの例で何が起こっているのか理解するのに苦労しています。

コードは次のとおりです。

(define evens-only*&co
 (lambda (l col)
   (cond
    ((null? l)
     (col '() 1 0))
    ((atom? (car l))
     (cond
      ((even? (car l))
       (evens-only*&co (cdr l)
                    (lambda (newl product sum)
                      (col (cons (car l) newl)
                           (opx (car l) product)
                           sum))))
      (else
       (evens-only*&co (cdr l)
                    (lambda (newl product sum)
                      (col newl product (op+ (car l) sum)))))))
    (else
     (evens-only*&co (car l)
                  (lambda (newl product sum)
                    (evens-only*&co (cdr l)
                                    (lambda (dnewl dproduct dsum)
                                      (col (cons newl dnewl)
                                           (opx product dproduct)
                                           (op+ sum dsum))))))))))

イニシャルcolは次のとおりです。

(define evens-results
 (lambda (newl product sum)
   (cons sum (cons product newl))))

私が得ていないのは、lasで、それはasとasで'((1) 2 3)すぐに決勝に進むということです。良いですが、、、から、、、を整理しようとすると、私の心は空白になります。また、ステッパーを実行するためのDrRacket、Chez Scheme、またはMIT-Schemeのセットアップ方法について誰かが私に指導してくれると助かります。else(car l)(1)(cdr l)(2 3)dnewldproductdsumnewlproductsum

しかし、多分私は早すぎます。これを初めて読む初心者は、実際にこの野生の継続を理解することになっていますか？

Answer 1

私もこのセクションを最初に読んだときはわかりにくく、継続と継続渡しのスタイル (これが何であるか) について他の場所で読んだ後で初めて理解し始めました。

すでに得ていることを説明する危険を冒して、私を助けた見方の 1 つは、関数が値を返す通常の方法を置き換えるものとして「コレクター」または「継続」を考えることです。プログラミングの通常のスタイルでは、関数を呼び出し、値を受け取り、呼び出し側でそれを使って何かを行います。たとえば、標準の再帰length関数には、(+ 1 (length (cdr list)))空でない場合の式が含まれています。つまり(length (cdr list))、値が返されると、それが生成する値が何であれ、計算が行われるのを待っているということです。(+ 1 [returned value]). 通常のプログラミングでは、この本の最初の数章でわかるように、インタープリターはこれらの保留中の計算を追跡します。たとえば、リストの長さを再帰的に計算する場合、リストの長さと同じレベルの深さの「待機中の計算」のネストがあります。

継続渡しスタイルでは、関数を呼び出して返された結果を呼び出し元の関数で使用する代わりに、呼び出す「継続」を提供することで、関数が値を生成するときに何をすべきかを関数に伝えます。(これは、非同期 Javascript プログラミングでコールバックを使用する必要があることに似ています。たとえば、 を記述する代わりに、result = someFunction();writesomeFunction(function (result) { ... })を使用すると、使用するすべてのコードがresultコールバック関数内に入ります)。

これは、比較のlengthために、継続渡しスタイルです。継続パラメーターを呼び出しました。returnこれは、ここでどのように機能するかを示しているはずですが、他の変数と同様に、通常の Scheme 変数であることを思い出してください。(多くの場合、継続パラメーターはkこのスタイルで呼び出されます)。

(define (length/k lis return)
  (cond ((null? lis) (return 0))
        (else
         (length/k (cdr lis)
                   (lambda (cdr-len)
                     (return (+ cdr-len 1)))))))

Little Schemerの共著者である Dan Friedmanによる継続に関する記事には、この種のコードを読むための役立つヒントがあります。(8 ページから始まるセクション II-5 を参照してください)。言い換えると、else上記の節の内容は次のとおりです。

length/konを呼び出した結果があると想像し(cdr lis)、それを呼び出してcdr-len、1 つ追加し、この追加の結果を継続 ( return) に渡します。

これは、関数の通常のバージョンで評価する際にインタプリタが行う必要があることとほぼ同じであることに注意してください(+ 1 (length (cdr lis)))(ただし、中間の結果に名前を付ける必要はありません(length (cdr lis))。継続またはコールバックを渡すことによって、インタープリターに追跡させる代わりに、制御フロー (および中間値の名前) を明示的に指定します。

この方法を の各節に適用してみましょうevens-only*&co。この関数は1 つではなく3 つの値を生成するため、ここでは少し複雑です。奇数が削除されたネストされたリスト。偶数の積; そして奇数の和。(car l)これが偶数であることが知られている最初の節です。

(evens-only*&co (cdr l)
                (lambda (newl product sum)
                  (col (cons (car l) newl)
                       (opx (car l) product)
                       sum)))

cdrリストから奇数を削除し、偶数を乗算し、奇数を追加した結果があると想像して、それぞれnewl、product、および と呼びますsum。consリストの先頭newl(偶数であるため、結果に含まれる必要があります); リストの先頭を掛けproductます (偶数の積を計算しているため)。放っておくsum; これらの 3 つの値を待機中の continuation に渡しますcol。

リストの先頭が奇数の場合は次のとおりです。

(evens-only*&co (cdr l)
                (lambda (newl product sum)
                  (col newl product (op+ (car l) sum))))

前と同じですが、奇数を合計しているので、リストの合計と先頭とともにnewlandの同じ値をproduct継続に渡します (つまり、それらを「返す」) 。sum

はネストされた(car l)リストで、二重再帰によって少し複雑になっています。

(evens-only*&co (car l)
                (lambda (newl product sum)
                  (evens-only*&co (cdr l)
                                  (lambda (dnewl dproduct dsum)
                                    (col (cons newl dnewl)
                                         (opx product dproduct)
                                         (op+ sum dsum))))))

の数値を削除、合計、(car l)および加算した結果が得られたと想像してください。次に、 に対して同じことを行った結果が得られたと想像し、それらを、およびと呼びます。待っている続きに、ing andによって生成された値を与えます (リストのリストを生成しているため); 一緒に乗算し 、; と を追加します。newlproductsum(cdr l)dnewldproductdsumconsnewldnewlproductdproductsumdsum

注意: 再帰呼び出しを行うたびに、再帰呼び出しの新しい継続を構築します。これは、引数の現在の値を「閉じる」ものlですcol。より慣習的に書かれた関数の「呼び出しスタック」をモデル化するために、再帰中に構築する継続!

あなたの質問に対する答えの一部を与えることを願っています。私が少しやり過ぎたとしたら、それは、再帰自体に次いで、The Little Schemerとプログラミング全般において、継続が 2 番目に優れた、心を拡張するアイデアであると考えたからです。

Answer 2

Jon O.による回答は、根底にある概念の非常に詳細な説明です。私にとっては (そして願わくば他の人たちにとっても)、このような概念を視覚的に表現すると、理解がはるかに容易になります。

それでmultirember&co、私は2つのフローチャートを用意しました（evens-only*&co

与えられたlものは次のとおりです。

'((9 1 2 8) 3 10 ((9 9) 7 6) 2) 

そしてcol次のとおりです。

(define the-last-friend
    (lambda (newl product sum)
        (cons sum (cons product newl))
    )
)

変数が再帰のさまざまなステップでどのように関係するかを反映する 1 つのフローチャート: 2 番目のフローチャート、渡される実際の値を示す:

私の希望は、この答えが上記のジョンの説明に適切に追加されることです。

Answer 3

How To Design Programs (felleisen et.al.) を読んでいます。ローカル定義を定義するセクションを通過します。ローカル定義を使用して、上記の evens-only&co を実装するコードを作成しました。ここに私が書いたものがあります：

(define (evens-only&co l)
  (local ((define (processing-func sum prod evlst lst)
            (cond ((null? lst) (cons sum (cons prod evlst)))
                  ((atom? (car lst))
                   (cond ((even? (car lst)) (processing-func sum (* prod (car lst)) (append evlst (list (car lst))) (cdr lst)))
                         (else
                          (processing-func (+ sum (car lst)) prod evlst (cdr lst)))))
                  (else
                   (local ((define inner-lst (processing-func sum prod  '() (car lst))))
                   (processing-func (car inner-lst) (cadr inner-lst) (append evlst (list (cddr inner-lst))) (cdr lst)))))))
    (processing-func 0 1 '() l)))

テストのために、 (evens-only&co '((9 1 2 8) 3 10 ((9 9) 7 6) 2)) と入力すると、'(38 1920 (2 8) 10 (() 6) 2) が返されます。リトルスキームで予想通り。しかし、私のコードは 1 つの条件で失敗します。偶数がまったくない場合でも、偶数の積は 1 として表示されます。たとえば、(evens-only&co '((9 1) 3 ((9 9) 7 ))) '(38 1 () (())) を返します。これを修正するには、追加の機能が必要になると思います。@melwasul:ローカルの定義に慣れていない場合は、ここに投稿して申し訳ありません。HTDP も読むことをお勧めします。初心者向けの優れた本です。しかし、スキームの専門家は、私のコードにもコメントを投稿してください。ローカル定義に関する私の理解は正しいですか?