13

いくつかのコンテキストを設定するために、私はClojureとLisp開発をより一般的に学ぶ過程にあります。Lispへの道のりで、私は現在、関数型プログラミングと再帰ベースのソリューション解決の基盤を固めるために「Little」シリーズに取り組んでいます。「TheLittleSchemer」では、多くの演習を行ってきましたが、それらの一部をClojureに変換するのに少し苦労しています。具体的には、TCOを有効にするために「recur」を使用するように変換するのに苦労しています。たとえば、S式のリスト内に現れるアトムの出現回数をカウントする「occurs *」関数（LittleSchemerから）のClojureベースの実装を次に示します。

(defn atom? [l]
  (not (list? l)))

(defn occurs [a lst]
  (cond
   (empty? lst) 0
   (atom? (first lst))
    (cond
     (= a (first lst)) (inc (occurs a (rest lst)))
     true (occurs a (rest lst)))
   true (+ (occurs a (first lst))
           (occurs a (rest lst)))))

基本的に、(occurs 'abc '(abc (def abc) (abc (abc def) (def (((((abc)))))))))は5と評価されます。明らかな問題は、この定義がスタックフレームを消費し、S式のリストが深すぎるとスタックを爆破することです。

これで、再帰関数をリファクタリングしてアキュムレータパラメータを使用し、再帰呼び出しをテール位置に配置できるようにするオプションを理解しました（TCOを可能にするため）が、このオプションがこのような状況にも適用できるかどうかに苦労しています。

アキュムレータパラメータを使用して「recur」を使用してこれをリファクタリングしようとすると、次のようになります。

(defn recur-occurs [a lst]
  (letfn [(myoccurs [a lst count]
            (cond
             (empty? lst) 0
             (atom? (first lst))
             (cond
              (= a (first lst)) (recur a (rest lst) (inc count))
              true (recur a (rest lst) count))
             true (+ (recur a (first lst) count)
                     (recur a (rest lst) count))))]
    (myoccurs a lst 0)))

ですから、もうすぐそこにいるような気がしますが、完全ではありません。明らかな問題は、リストの先頭がアトムではない私の「else」句です。概念的には、リストの最初の要素を繰り返した結果と、リストの残りの要素を繰り返した結果を合計したいと思います。繰り返しをテール位置に移動できるように、これをリファクタリングする方法について頭の中で苦労しています。

再帰呼び出しをここで適用する必要があるテール位置に配置するための「アキュムレータ」パターンに追加のテクニックはありますか、それとも単に問題がより「基本的」であり、Clojureベースのクリーンなソリューションがないということです。 JVMにはTCOがないためですか？後者の場合、一般的に言えば、S式のリストを繰り返す必要があるClojureプログラムが使用する一般的なパターンは何でしょうか？価値のあることとして、「再帰を怠惰に置き換える」に使用されるマルチメソッドw / lazy-seq手法（Hallowayの「プログラミングClojure」の151ページを参照）を見てきましたが、そのパターンを適用する方法がわかりません。この例では、リストを作成するのではなく、単一の整数値を計算しようとしています。

よろしくお願いします。

4

2 に答える 2

11

まず、The Little Schemerを通過するときに、スタックオーバーフローなどの実装上の問題についてあまり心配しないようにアドバイスする必要があります。怒りでプログラミングしているときに末尾呼び出しの最適化がないなどの問題に注意するのは良いことですが、この本の主なポイントは、再帰的に考えることを教えることです。例のアキュムレータ通過スタイルを変換することは確かに良い習慣ですが、それは本質的に反復を支持して再帰を捨てることです。

ただし、これの前にスポイラー警告を表示する必要があります。JVMスタックの気まぐれにさらされることなく、同じ再帰アルゴリズムを維持する方法があります。継続渡しスタイルを使用して、追加の無名関数引数の形式で独自のスタックを作成できますk。

(defn occurs-cps [a lst k]
  (cond
   (empty? lst) (k 0) 
   (atom? (first lst))
   (cond
    (= a (first lst)) (occurs-cps a (rest lst)
                                  (fn [v] (k (inc v))))
    :else (occurs-cps a (rest lst) k))
   :else (occurs-cps a (first lst)
                     (fn [fst]
                       (occurs-cps a (rest lst)
                                   (fn [rst] (k (+ fst rst))))))))

非テール関数呼び出しによって暗黙的にスタックが作成される代わりに、への各呼び出しの後に「やるべきこと」をまとめoccursて、次の継続として渡しkます。それを呼び出すとき、私たちkは何もすることが残っていないことを表す、恒等関数から始めます：

scratch.core=> (occurs-cps 'abc 
                           '(abc (def abc) (abc (abc def) (def (((((abc)))))))) 
                           (fn [v] v))
5

TLSの後半の章で説明するため、CPSの実行方法の詳細については詳しく説明しません。ただし、もちろんこれはまだ完全には機能していないことに注意してください。

scratch.core=> (def ls (repeat 20000 'foo))          
#'scratch.core/ls
scratch.core=> (occurs-cps 'foo ls (fn [v] v))       
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

CPSを使用すると、重要なスタック構築呼び出しをすべてテール位置に移動できますが、Clojureでは、それらをrecur次のように置き換えるという追加の手順を実行する必要があります。

(defn occurs-cps-recur [a lst k]
  (cond
   (empty? lst) (k 0)
   (atom? (first lst))
   (cond
    (= a (first lst)) (recur a (rest lst)
                             (fn [v] (k (inc v))))
    :else (recur a (rest lst) k))
   :else (recur a (first lst)
                (fn [fst]
                  (recur a (rest lst) ;; Problem
                         (fn [rst] (k (+ fst rst))))))))

残念ながら、これはうまくいきませんjava.lang.IllegalArgumentException: Mismatched argument count to recur, expected: 1 args, got: 3 (core.clj:39)。最後は実際にはその真上recurを指し、継続を表すために使用しています。ほとんどの場合、それをへの呼び出しにfn変更することで良好な動作を得ることができますが、病理学的にネストされた入力は依然としてスタックをオーバーフローします。recuroccurs-cps-recur

scratch.core=> (occurs-cps-recur 'foo ls (fn [v] v))
20000
scratch.core=> (def nested (reduce (fn [onion _] (list onion)) 
                                   'foo (range 20000)))
#'scratch.core/nested
scratch.core=> (occurs-cps-recur 'foo nested (fn [v] v))
Java.lang.StackOverflowError (NO_SOURCE_FILE:0)

電話をかけて回答を期待する代わりに、occurs-*すぐにサンクを返すようにすることができます。そのサンクを呼び出すと、再帰呼び出しが行われるまで、サンクがオフになり、いくつかの作業が実行されます。再帰呼び出しが行われると、別のサンクが返されます。これはトランポリンスタイルで、サンクを「バウンス」させる機能はですtrampoline。再帰呼び出しを行うたびにサンクを返すと、スタックサイズが一度に1つの呼び出しに制限されるため、唯一の制限はヒープです。

(defn occurs-cps-tramp [a lst k]
  (fn [] 
    (cond
     (empty? lst) (k 0) 
     (atom? (first lst))
     (cond
      (= a (first lst)) (occurs-cps-tramp a (rest lst)
                                          (fn [v] (k (inc v))))
      :else (occurs-cps-tramp a (rest lst) k))
     :else (occurs-cps-tramp a (first lst)
                             (fn [fst]
                               (occurs-cps-tramp a (rest lst)
                                                 (fn [rst] (k (+ fst rst)))))))))

(declare done answer)

(defn my-trampoline [th]
  (if done
    answer
    (recur (th))))

(defn empty-k [v]
  (set! answer v)
  (set! done true))

(defn run []
  (binding [done false answer 'whocares]
    (my-trampoline (occurs-cps-tramp 'foo nested empty-k))))

;; scratch.core=> (run)                             
;; 1

Clojureには組み込みがありますtrampoline（リターンタイプにいくつかの制限があります）。代わりにそれを使用すると、特別なものは必要ありませんempty-k：

scratch.core=> (trampoline (occurs-cps-tramp 'foo nested (fn [v] v)))
1

トランポリンは確かにクールなテクニックですが、プログラムをトランポリンするための前提条件は、末尾呼び出しのみが含まれている必要があることです。CPSはここでの本当のスターです。自然再帰の明快さでアルゴリズムを定義し、正確性を維持する変換を通じて、単一のループとヒープを持つすべてのホストで効率的にアルゴリズムを表現できます。

于 2011-11-08T06:32:23.000 に答える
7

固定量のメモリではこれを行うことはできません。スタックまたはヒープを消費できます。それはあなたが下す決定です。mapこれをClojureで書いているとしたらreduce、手動の再帰ではなく、次のように記述します。

(defn occurs [x coll]
  (if (coll? coll)
    (reduce + (map #(occurs x %) coll))
    (if (= x coll)
      1, 0)))

tree-seqまたはを使用すると、より短い解決策が存在することに注意してくださいflatten。ただし、その時点で問題のほとんどが解消されているため、学ぶことはあまりありません。

編集

これは、スタックを使用せず、代わりにキューをどんどん大きくする（ヒープを使い果たす）バージョンです。

(defn heap-occurs [item coll]
  (loop [count 0, queue coll]
    (if-let [[x & xs] (seq queue)]
      (if (coll? x)
        (recur count (concat x xs))
        (recur (+ (if (= item x) 1, 0)
                  count)
               xs))
      count)))
于 2011-11-08T04:25:27.597 に答える