Schemeネタ×2 from はてなダイアリー

はてなダイアリーのSchemeキーワードを眺めていたら、気になる話題があったのでコメントします。

Re: http://d.hatena.ne.jp/brazil/20060131/1138692196

関数型プログラミングとオブジェクト指向プログラミングの比較をしていて、その内容には概ね同意なのですが、ちょっと気になったのが以下の文。

クロージャは、「処理が一つしかないオブジェクト」と考えることもできます。

これはクロージャが引数を取らないなら確かにその通りですが、実際にはクロージャは引数によって振る舞いを変えることができるので処理が一つしかないとは言い切れないと思います。例えば、

(define (make-counter)
  (let ((val 0))
    (define (get) val)
    (define (set n) (set! val n) val)
    (define (inc n) (set! val (+ val n)) val)
    (define (dec n) (set! val (- val n)) val)
    (define (next) (inc 1))
    (define (prev) (dec 1))
    (lambda args
      (if (null? args)
          (next)
          (let ((method (car args)))
            (cond ((eq? method 'next) (next))
                  ((eq? method 'prev) (prev))
                  ((eq? method 'inc) (inc (cadr args)))
                  ((eq? method 'dec) (dec (cadr args)))
                  ((eq? method 'get) (get))
                  ((eq? method 'set) (set (cadr args)))
                  (else (error "No such method"))))))))
==> make-counter

(define counter (make-counter))
==> counter

(counter)
==> 1

(counter)
==> 2

(counter 'next)
==> 3

(counter 'inc 3)
==> 6

(counter 'prev)
==> 5

(counter 'get)
==> 5

(counter 'set 0)
==> 0

こんなこともできます。この場合、クロージャでオブジェクト指向的なメッセージパッシングを実現していることになりますね。

というわけで、クロージャとオブジェクト指向は排他的な考え方ではないです。

最後に、注意したいのはクロージャ＝関数型ではないということです。この例はクロージャを使っていますが、関数型プログラミングとは直接関係ありません。むしろ、こういうクロージャの使い方では代入を多用することになり、関数型プログラミングの考え方から言えば良くないスタイルです（純粋な関数型プログラミングでは代入は滅多に使いません）。

なお、より関数型プログラミングらしいクロージャの使い方（継続渡しスタイル）が次に出てきます（ちょっと難易度が高めですが）。

Re: 末尾再帰のクイックソート - maoeのブログ

偶然にもつい先日私もSchemeでsortを書いたところだったので、便乗してみるテスト。
その時書いたのはこんな関数でした。一部で末尾再帰を使っていますが、完全に末尾再帰にはなっていません。

(define (sort lst cmpfn)
  (let rec ((lst lst))
    (cond ((null? lst) '())
          ((null? (cdr lst)) lst)
          ((null? (cddr lst))
           (if (cmpfn (car lst) (cadr lst))
               lst
               (list (cadr lst) (car lst))))
          (else
           (let ((pibot (car lst)))
             (let loop ((lst (cdr lst)) (smaller '()) (bigger '()))
               (if (null? lst)
                   (append (rec smaller) (list pibot) (rec bigger))
                   (if (cmpfn pibot (car lst))
                       (loop (cdr lst) smaller (cons (car lst) bigger))
                       (loop (cdr lst) (cons (car lst) smaller) bigger)))))))))

クイックソートの場合アルゴリズム自体に再帰性があるので、末尾再帰に変換して本当に効率的なのか分かりませんが、とりあえずやってみます。

この関数の中で末尾再帰でないのは(append (rec smaller) (list pibot) (rec bigger))の部分ですから、ここを何とかしないといけません。ところで、この式は

(let ((v1 (rec smaller)))
  (append v1 (list pibot) (rec bigger)))

と等価です。さらに言えば、以下の式とも等価です。

((lambda (v1)
   (append v1 (list pibot) (rec bigger)))
 (rec smaller))

ここでrecの計算結果を呼び出し元に返すことなく直接(lambda (v1) ...)に放り込んでやれば末尾再帰になります。そのためには関数の引数に「次に値を渡す関数」（これが継続ですね）を与えてあげればいいわけです。ちなみに、こういう関数の形式を継続渡しスタイル(Continuation Passing Style; CPS)といいます。

(rec smaller
     (lambda (v1)
       (append v1 (list pibot) (rec bigger))))

これだとまだ末尾再帰でない呼び出しが残っていますから、さらに変換して

(rec smaller
     (lambda (v1)
       (rec bigger
            (lambda (v2)
              (k (append v1 (list pibot) v2))))))

こうなります。ただしkは元の関数に渡された継続です。最後にkを呼び出すのを忘れないように注意してください。

最終的に、末尾再帰版のsortは以下のようになりました。

(define (sort lst cmpfn)
  (let rec ((lst lst) (k values))
    (cond ((null? lst) (k '()))
          ((null? (cdr lst)) (k lst))
          ((null? (cddr lst))
           (k (if (cmpfn (car lst) (cadr lst))
                  lst
                  (list (cadr lst) (car lst)))))
          (else
           (let ((pibot (car lst)))
             (let loop ((lst (cdr lst)) (smaller '()) (bigger '()))
               (if (null? lst)
                   (rec smaller
                        (lambda (v1)
                          (rec bigger
                               (lambda (v2)
                                 (k (append v1 (list pibot) v2))))))
                   (if (cmpfn pibot (car lst))
                       (loop (cdr lst) smaller (cons (car lst) bigger))
                       (loop (cdr lst) (cons (car lst) smaller) bigger)))))))))

なおこの例でも使っていますが、最初に与える（＝最後に呼び出される）継続は伝統的にはvaluesがよく使われます。