Ephemeron を使ってみる

Ephemeron は SRFI-124で定義されているがどういったものなのか、どういう挙動が期待されるのかというのはなかなかに想像しづらい。ということで、ちょっと触りつつ解説してみる。

まず、 ephemeron とは何か？ものすごく簡単に言えば循環構造を許す弱対といえる。SRFI-124で定義されている ephemeron は一種の鍵対で、鍵が値から参照されてたとしても、その参照のみが生きているのであれば GC 対象になるというもの。日本語は難しいのでコードで説明してみる。

(let* ((key (cons 1 2))
       (value (cons key 1)))
  (make-ephemeron key value))

こんなのが鍵が値から参照されている状態である。この場合だと、鍵は値のみから参照されているので、ephemeron を作った直後に GC が発生すればどちらも回収されるというものである。

さて、実際の挙動を観察してみよう。SRFI-124 によれば ephemeron は MIT Scheme または Racket でサポートされているという（ちなみに、Sagittarius にもなんちゃってはあるが Chibi Scheme と同様のバグを抱えている。っていうか、これ Boehm GC 上で実装できるの？） MIT Scheme は手元にないので Racket を使ってみる。コードは以下の通り：

#lang racket

(define (make-weak v)
  (let* ((a (cons 1 2))
         (b (cons a v)))
    (make-ephemeron a b)))

(define e (make-weak 'a))
(write (ephemeron-value e)) (newline)
(collect-garbage 'major)
(write (ephemeron-value e)) (newline)

出力結果は以下：

Welcome to DrRacket, version 6.3 [3m].
Language: racket; memory limit: 128 MB.
((1 . 2) . a)
#f

GC 後には ephemeron の値が回収されているのがわかる。

ちょっとした追記：

実は既に Racket も使ってみていたのですが、すぐには壊れないみたい (?) なので、色々な事例で (理解のために) 挙動を観察するのに良い方法を模索していたのでした。 pic.twitter.com/jbicifloo7

— 9b96faac591ad05eddec760eed2da2d5 齊藤敦志 (@SaitoAtsushi) 29 March 2018

この挙動と何が違うのか考えて見たのだが、鍵となる a が大域に設定されているのがまずいのかなぁというありきたりな推測。 set! でリセットしているが、内部のどこかでは参照が生きているとかそんなのではないだろうか？流石に Racket の中まではわからないので推測に過ぎないが…

Generatorの勧め

Schemeでリスト処理を書いていると中間リスト(処理の最中に作成されて捨てられるリスト)の存在が気にならないだろうか？ClojureにはTransducersがあるのにSchemeにはないのだろうか？そこでGeneratorである。

Generatorは元もとGaucheに実装されていたもので割と最近SRFIになったもの。これ自体は引数を取らない手続きかつ処理が終了するとEOFを返すというものである。（GaucheのGeneratorも元をたどるとPython辺りからインスパイアされたらしい（要出典）） このGeneratorのSRFIは紆余曲折あって2種類ある。SRFI-121とSRF-158だ。SRFI-158はSRFI-121の上位互換なので、サポートされているのであればそちらを使った方がよい。（ちなみに、Sagittariusは両方サポートしている）

では、これを使って中間リストの削減をしてみる。 まずは以下のような処理を書く。処理自体に特に意味はない。

(filter (lambda (x) (zero? (mod x 3)))                     ;; 最終リスト
        (map cdr                                           ;; 中間リスト
             (filter (lambda (x) (odd? (car x)))           ;; 中間リスト
                     (map (lambda (x) (cons x (square x))) ;; 中間リスト
                          (iota 1000))))))                 ;; 初期リスト

この処理では計3つの中間リストが存在する。iotaで作成されるものも含めると4つになる。Generatorを使うと以下のように減らすことができる。

(generator->list ;; リストの生成はここだけ
 (gfilter (lambda (x) (zero? (mod x 3)))
          (gmap cdr
                (gfilter (lambda (x) (odd? (car x)))
                         (gmap (lambda (x) (cons x (square x)))
                               (make-iota-generator 1000))))))

ここではmake-iota-generatorを使っているが、(list->generator (iota 1000))と書くと、既存の初期リストをGeneratorに変換するような処理になる。

見た目はほぼ同じ（よく目を細めるように）、ならば気になるのは性能だろう。ということでベンチマークを取ってみる。使うスクリプトは以下。

(import (scheme base)
        (scheme write)
        (srfi 1)
        (srfi 158)
        (time))

(define size 1000)
(define (target1)
  (filter (lambda (x) (zero? (mod x 3)))
          (map cdr
               (filter (lambda (x) (odd? (car x)))
                       (map (lambda (x) (cons x (square x)))
                            (iota size))))))


(define (target2)
  (generator->list
   (gfilter (lambda (x) (zero? (mod x 3)))
            (gmap cdr
                  (gfilter (lambda (x) (odd? (car x)))
                           (gmap (lambda (x) (cons x (square x)))
                                 (make-iota-generator size)))))))


(define count 1000)
(define-syntax dotimes
  (syntax-rules ()
    ((_ n expr ...) (do ((c n) (i 0 (+ i 1))) ((= c i)) expr ...))))

;; GCの結果も見るため、交互に計測する
(time (dotimes count (target1))) 
(time (dotimes count (target2)))

結果は以下の通り。

# 中間リスト作成版
$ sash -s test.scm

;;  (dotimes count (target1))
;;  0.385681 real    0.688000 user    0.000000 sys

;; Statistics (*: main thread only):
;;  GC: 21389312bytes heap, 293849719bytes allocated, 49 gc occurred

# Generator版
$ sash -s test.scm

;;  (dotimes count (target2))
;;  0.386407 real    0.480000 user    0.000000 sys

;; Statistics (*: main thread only):
;;  GC: 28368896bytes heap, 198322311bytes allocated, 28 gc occurred

性能に大きな差はないが、GC回数と割り付けられたメモリに大きな差がある。

メモリの圧迫が気になるときに思い出したように使うといいかもしれない。

右回り

スタックオーバーフローにこんなのがあった。
Rotating a list to the right in scheme

真面目に実装するのはだるいなぁと思ったのでこんな風に書いてみた。

(import (rnrs)
        (srfi :1))

(define (rotate-right l)
  (if (null? l)
      l
      (cons (car (last-pair l)) (drop-right l 1))))

(rotate-right '(1 2 3 4 5))
;; -> (5 1 2 3 4)

一応O(N)で動くと言えば動く。SRFI-1にsplit-at-rightみたいなのがあればリストを舐めるのが一回で済みそうではある。

今週はネタも時間もなかったのでこんなので…（そのうちsplit-at-rightを実装してもう少しマシなのを書くかもしれない。）

ファイルタイムスタンプとChicken Scheme

Sagittariusではファイルのタイムスタンプを変更する方法を用意していなかった。それが問題になったことがなかったというのが一番の理由である。が、先日これが問題になったので追加したという話。

問題になったもの
Scheme EnvでChickenのインストーラを作成していたら(archive)で展開したファイル郡をビルドできなかった。もちろんtarで展開してやれば動く。エラーとしては、Chickenが事前ビルドプロセスで生成しているファイルをビルドしようとしているというものだった。（例：library.scmからlibrary.cを生成する） これらは依存関係としてMakefileに記載されている。

原因
（当たり前のことで書くのも憚られるが）Makefileの依存関係の解決はファイルの更新日時に強く影響される。上記の場合だと、library.scmはlibrary.cよりも後に変更が加えられているのでmakeが変更有りとして解決しようとしたというもの。（.scmはアルファベット順で.cより後に来るから、展開順的にそうなった）

解決
change-file-timestamps!という手続きを追加し、(archive)で展開されたファイルのタイムスタンプを変更するようにした。特に何にひねりもない王道とも言える。

どうでもいい捕捉
新たに追加された手続きchange-file-timestamps!はこんな感じで使う。

(change-file-timestamps! file 1 (make-time time-utc 0 0))

fileは文字列で存在するファイル名を指す必要がある。残りの引数はそれぞれ、atimeとmtimeに相当し、最終アクセス日時と最終更新日を変更する。上記の場合だと、最終アクセス日時が現在時間＋1秒になり、最終更新日がUnix時間の開始日（1970年1月1日 0時0分0秒 GMT）になる。更新をしたくない場合は#fを指定し、現在時にしたい場合は#t(時間オブジェクトまたは実数以外の真値）を与える。

これが入ったことで、今まで無理やり実装するしかなかったtouchが簡単にできるようになる。例えばこんな感じ。

(import (rnrs) (sagittarius))

(define (touch file)
  (if (file-exists? file)
      (change-file-timestamps! file #t #t)
      (call-with-output-file file (lambda (out)))))

(touch "foo")

上記はあると便利かもしれないが、今のところ用途がないので、どこのライブラリにも入れてない。要望があれば入れる感じ。