ネストされたループのLispマクロ(または関数)

2012年04月15日に質問されました。  ·  閲覧回数 2.6k回  ·  ソース

mmj picture
2012年04月15日

次元と変数のリスト、(反復の)本体を取り、リストで指定された数のネストされたループで構成されるコードを作成するCommon Lispマクロを作成することは可能ですか?

つまり、次のようなものです。

(nested-loops '(2 5 3) '(i j k) whatever_loop_body)

に拡張する必要があります

(loop for i from 0 below 2 do
  (loop for j from 0 below 5 do
    (loop for k from 0 below 3 do
      whatever_loop_body)))

ファローアップ

huaiyuanが正しく指摘したように、コンパイル時にマクロに渡すパラメーターを知っている必要があります。 私のように実際に機能が必要な場合は、以下をご覧ください。

あなたがマクロで大丈夫なら、6502の再帰的解決策に行きなさい、素晴らしいです。

回答

huaiyuan picture
2012年04月16日
8

とにかくコンパイル時に次元と変数を知る必要があるため、引用符は必要ありません。

(defmacro nested-loops (dimensions variables &body body)
  (loop for range in (reverse dimensions)
        for index in (reverse variables)
        for x = body then (list y)
        for y = `(loop for ,index from 0 to ,range do ,@x)
        finally (return y)))

編集:

コンパイル時に寸法を決定できない場合は、関数が必要です

(defun nested-map (fn dimensions)
  (labels ((gn (args dimensions)
             (if dimensions
               (loop for i from 0 to (car dimensions) do
                 (gn (cons i args) (cdr dimensions)))
               (apply fn (reverse args)))))
    (gn nil dimensions)))

呼び出し時に本体をラムダでラップします。

CL-USER> (nested-map (lambda (&rest indexes) (print indexes)) '(2 3 4))

(0 0 0) 
(0 0 1) 
(0 0 2) 
(0 0 3) 
(0 0 4) 
(0 1 0) 
(0 1 1) 
(0 1 2) 
(0 1 3) 
(0 1 4) 
(0 2 0) 
(0 2 1) 
...

編集(2012-04-16):

上記のバージョンのnested-mapは、元の問題ステートメントをより厳密に反映するように作成されています。 mmjがコメントで述べたように、インデックスの範囲を0からn-1にするのがおそらくより自然であり、行優先の反復順序を主張しない場合は、反転を内側のループの外に移動すると効率が向上するはずです。 また、ランクに依存しないように、入力関数に個々のインデックスではなくタプルを受け入れさせる方がおそらく賢明です。 記載されている変更を加えた新しいバージョンは次のとおりです。

(defun nested-map (fn dimensions)
  (labels ((gn (args dimensions)
             (if dimensions
               (loop for i below (car dimensions) do
                 (gn (cons i args) (cdr dimensions)))
               (funcall fn args))))
    (gn nil (reverse dimensions))))

それで、

CL-USER> (nested-map #'print '(2 3 4))
6502 picture
2012年04月16日
7

場合によっては、再帰マクロ、つまり、ケースが直接解決できるほど単純でない限り、同じマクロの別の呼び出しを含むコードを生成するマクロを作成することが有用なアプローチです。

(defmacro nested-loops (max-values vars &rest body)
  (if vars
      `(loop for ,(first vars) from 0 to ,(first max-values) do
          (nested-loops ,(rest max-values) ,(rest vars) ,@body))
      `(progn ,@body)))

(nested-loops (2 3 4) (i j k)
  (print (list i j k)))

変数リストの場合は、上記で特に生成されたコードであり、本体フォームに直接、マクロ膨張が空である(loop...)別含む第一の変数に(nested-loops ...)部分行うに呼び出し。

マクロは、関数に使用される通常の意味では再帰的ではありませんが(それ自体を直接呼び出すことはありません)、マクロ拡張ロジックは、コード生成が完了するまで、内部部分に対して同じマクロを呼び出します。

内側のループで使用される最大値の形式は、外側のループの反復ごとに再評価されることに注意してください。 テストケースのようにフォームが実際に数値である場合は違いはありませんが、たとえば関数呼び出しの場合は異なります。

Dirk picture
2012年04月16日
2

うーん。 これは、CommonLispでのそのようなマクロの例です。 ただし、これが実際には良い考えであるかどうかはわかりません。 でもここはみんな大人ですよね?

(defmacro nested-loop (control &body body)
  (let ((variables ())
        (lower-bounds ())
        (upper-bounds ()))
    (loop
       :for ctl :in (reverse control)
       :do (destructuring-bind (variable bound1 &optional (bound2 nil got-bound2)) ctl
             (push variable variables)
             (push (if got-bound2 bound1 0) lower-bounds)
             (push (if got-bound2 bound2 bound1) upper-bounds)))
    (labels ((recurr (vars lowers uppers)
               (if (null vars)
                   `(progn ,@body)
                   `(loop 
                       :for ,(car vars) :upfrom ,(car lowers) :to ,(car uppers)
                       :do ,(recurr (cdr vars) (cdr lowers) (cdr uppers))))))
      (recurr variables lower-bounds upper-bounds))))

構文は提案とは少し異なります。

(nested-loop ((i 0 10) (j 15) (k 15 20)) 
    (format t "~D ~D ~D~%" i j k))

に拡大します

(loop :for i :upfrom 0 :to 10
  :do (loop :for j :upfrom 0 :to 15
            :do (loop :for k :upfrom 15 :to 20
                      :do (progn (format t "~d ~d ~d~%" i j k)))))

マクロの最初の引数は、フォームのリストのリストです。

(variable upper-bound)

(下限が0であることを意味します)または

(variable lower-bound upper-bounds)

もう少し愛を魔術師にすると、

(nested-loop ((i :upfrom 10 :below 20) (j :downfrom 100 :to 1)) ...)

しかし、 loopにこれらすべての機能がすでに備わっているのに、なぜわざわざするのでしょうか。