ClojureのS式のリストに対する再帰

2011年11月08日に質問されました。  ·  閲覧回数 1.8k回  ·  ソース

Paul Evans picture
2011年11月08日

いくつかのコンテキストを設定するために、私はClojureとLisp開発をより一般的に学ぶ過程にあります。 Lispへの道のりで、私は現在、関数型プログラミングと再帰ベースのソリューション解決の基盤を固めるために「Little」シリーズに取り組んでいます。 「TheLittleSchemer」では、多くの演習を行ってきましたが、それらの一部をClojureに変換するのに少し苦労しています。 具体的には、TCOを有効にするために「recur」を使用するように変換するのに苦労しています。 たとえば、S式のリスト内に出現するアトムの出現回数をカウントする「occurs *」関数(Little Schemerから)の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プログラムが使用する一般的なパターンは何でしょうか? 価値のあることとして、「再帰を怠惰に置き換える」に使用されるレイジーシーケンス手法を使用したマルチメソッド(参照用のHallowayの「プログラミングClojure」の151ページ)を見てきましたが、そのパターンを適用する方法がわかりません。この例では、リストを作成するのではなく、単一の整数値を計算しようとしています。

よろしくお願いします。

回答

acfoltzer picture
2011年11月08日
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はここでの本当のスターです。 これにより、自然再帰の明快さでアルゴリズムを定義し、正確性を維持する変換を通じて、単一のループとヒープを持つ任意のホストでアルゴリズムを効率的に表現できます。

amalloy picture
2011年11月08日
7

一定量のメモリではこれを行うことはできません。 スタックまたはヒープを消費できます。 それはあなたが下す決定です。 これをClojureで書いている場合、手動の再帰ではなく、 mapreduceを使用して記述します。

(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)))