2011/05/21

scheme(gauche)でもsleep-sort

その他のソート

面白いすねー。

ソース

(use gauche.threads)

(define (sleep-sort . nums)
  (let* ((result '())
         (threads (map (^n (thread-start!
                            (make-thread
                             (^ _ (thread-sleep! n)
                                (push! result n)))))
                       nums)))
    (for-each (pa$ thread-join!) threads)
    (reverse result)))

(define-macro (macro-sleep-sort . nums)
  `(list ,@(apply sleep-sort nums)))

実行してみます。
(use math.mt-random)
(use srfi-1)

(define rand
  (let1 m (make <mersenne-twister>)
    (^n (mt-random-integer m n))))

(define (make-rand-list n)
  (list-tabulate n (^ _ (rand n))))

(time
 (apply sleep-sort (make-rand-list 10)))
;; ;(time (apply sleep-sort (make-rand-list 10)))
;; ; real   9.004
;; ; user   0.000
;; ; sys    0.016
;; (0 1 1 4 5 6 7 8 9 9)

(time
 (macro-sleep-sort 9 8 0 7 5 7 2 3 1))
;(time (macro-sleep-sort 9 8 0 7 5 7 2 3 1))
; real   0.000
; user   0.000
; sys    0.000
(0 1 2 3 5 7 7 8 9)

ところで、マクロには apply がないわけですし、可変長引数ではなくリストで受け取るようにしようとするわけです。が、コンパイルタイムに引数を評価してソートまで実行する方法がわからなくてevalしました。こういう時はどうしたら良いんでしょうか。何か良い方法があるんでしょうか。
(define-macro (macro-sleep-sort2 nums)
  (let ((nums (eval nums (current-module))))
    `(list ,@(apply sleep-sort nums))))


(time
 (macro-sleep-sort2 (make-rand-list 10)))
;; ;(time (macro-sleep-sort2 (make-rand-list 10)))
;; ; real   0.000
;; ; user   0.000
;; ; sys    0.000
;; (0 2 3 3 6 6 6 7 8 9)




2 件のコメント:

  1. 引数の式を評価した結果をごにょごにょするマクロなら、evalを使わずに「結果を評価してapplyするような式」に展開するのが定石です。でもそれだと今回の場合、こうなっちゃいます:

    (define-macro (macro-sleep-sort2 num-expr)
    `(apply sleep-sort ,num-expr))

    意図としては、「マクロ展開後には既にソートされている定数リストになってて欲しい」んですよね?

    原則として、マクロはコンパイル時に展開され、普通の式の値は実行時に求められます。コンパイルは実行の前に起きるので、マクロ展開器は「与えられた式の値」を使うことはできません。マクロ展開器に見えるのは「与えられた式そのもの(S式)」だけです。

    で、その原則を破るのがevalってわけです。原則破りなので、色々注意が必要です。例えばvalvallowさんのコードは、macro-sleep-sort2が別のモジュールに定義されててimportして使ってる時にはうまくいきません。current-moduleはコンパイル時のモジュールになるので、常にmacro-sleep-sort2が定義されているモジュールでevalされちゃいます。

    evalを使わない場合は、リスト生成の機能そのものをマクロでできるようにするという手があります。これは任意の式を受け取るようにはできないんですが、num-exprの式が(make-rand-list K) であることを調べてマクロ内で自分でK要素のrandom listを生成するとか、そういう手です。(これを完全に汎用的にしようとすると、自分でevalを作るのと同じことになります)。

    返信削除
  2. shiroさんコメントありがとうございます!

    > 意図としては、「マクロ展開後には既にソートされている定数リストになってて欲しい」んですよね?
    はい、その通りです。

    evalを使う場合とevalを使わない場合の問題がよくわかりました。
    特にevalを使わない場合にどんな手段があるのかわからなかったので勉強になりました。
    ありがとうございます!

    返信削除