Tociyuki::Diary RSSフィード

tociyuki による Perl・Ruby・C++・C で書き散らしたコードを中心に、日常雑記も混在 : B  F  twitter  GitHub  CPAN  本館  公開鍵
 | 

2017年12月19日

[]ヒープベースなディスプレイ・クロージャでも letrec

VM レベル letrec サポートをディスプレイ・クロージャのその 2 の方でやってみます。 その 2 はフラット・クロージャを真似て、 クロージャごとに自由変数部分のディスプレイをコピーして作り直していました。 このとき、 作り直すのはクロージャのトップレベルだけで、 トップレベルが参照している各レベルのフレームは同一レキシカル・スコープから作られたすべてのクロージャで共用しています。 なお、 以後の状態遷移では、 スタックベース VM との対比を考慮してレジスタを r を x の直後にして、 a x r f c s の順に並べ替えてあります。

(let ((x1 a1) (x2 a2)) e)  ⇒  (<a2> (arg 1 (<a1> (arg 0 (close <e> apply)))))

                   a x                       r        f                    c s
==================== ================ ======== ======== ==================== =
                   A (<a2> (arg 1 _)) #(#f #f)       F1    #(n' x' F2 F3...) S
                  A2 (<a1> (arg 0 _)) #(#f A2)       F1    #(n' x' F2 F3...) S
                  A1 (close 2 <e> _)  #(A1 A2)       F1    #(n' x' F2 F3...) S
#(2 <e> F1 F2 F3...) (apply)          #(A1 A2)       F1    #(n' x' F2 F3...) S
#(2 <e> F1 F2 F3...) <e>                    () #(A1 A2) #(2 <e> F1 F2 F3...) S

letrec のためにダミー・フレームを作る遷移を考えてみます。 close-dummy 命令で f レジスタと c レジスタを合わせたディスプレイ・クロージャを作成して c レジスタに置くと同時に、 f レジスタに引数分のダミー・フレームを作ります。 この f レジスタに作ったダミー・フレームは、 実引数評価中に close 命令でディスプレイ・クロージャへ取り込まれていきます。 一方、 frame 命令で r レジスタに実引数を作ります。 実引数の評価を終えると、 close-rec 命令で実引数を束縛変数へ vector-copy! で上書きし、 f レジスタを共用している 2 つのクロージャ A1 と A2 のフレームも同時に上書きされます。

(letrec ((x1 a1) (x2 a2)) e)  ⇒  (close-dummy 2 (frame 2 (<a2> (arg 1 (<a1> (arg 0 (close-rec <e>)))))))

                   a x                         r        f                   c s
==================== ================== ======== ======== =================== =
                   A (close-dummy 2 _)         R       F1   #(n' x' F2 F3...) S
                   A (frame 2 _)               R #(#f #f) #(2 () F1 F2 F3...) S
                   A (<a2> (arg 1 _))   #(#f #f) #(#f #f) #(2 () F1 F2 F3...) S
A2=#(n <a2> #(#f #f) F1 F2 F3...)
                  A2 (<a1> (arg 0 _))   #(#f A2) #(#f #f) #(2 () F1 F2 F3...) S
A1=#(n <a1> #(#f #f) F1 F2 F3...)
                  A1 (close-rec <e>)    #(A1 A2) #(#f #f) #(2 () F1 F2 F3...) S
A2=#(n <a2> #(A1 A2) F1 F2 F3...)
A1=#(n <a1> #(A1 A2) F1 F2 F3...)
                  A1 <e>                #(A1 A2) #(A1 A2) #(2 () F1 F2 F3...) S

上記の説明に従い、 close-dummy 命令と close-rec 命令を VM に追加します。

(define (VM a x f c r s)
 (match x
  (('halt)               a)
  (('constant obj x1)    (VM obj x1 f c r s))
  (('test x1 x2)         (VM a (if a x1 x2) f c r s))
  (('refer-local i x1)   (VM (vector-ref f i) x1 f c r s))
  (('refer-free j i x1)  (VM (vector-ref (vector-ref c (+ j 2)) i) x1 f c r s))
  (('close n fn x1)      (VM (closure n fn f c) x1 f c r s))
  (('assign-local i x1)  (vector-set! f i a)
                         (VM a x1 f c r s))
  (('assign-free j i x1) (vector-set! (vector-ref c (+ j 2)) i a)
                         (VM a x1 f c r s))
  (('conti x1)           (VM `#(1 (nuate ,s 0) ()) x1 f c r s))
  (('nuate s1 i)         (VM (vector-ref f i) '(return) f c r s1))
  (('push x1 x2)         (VM a x1 f c r (list x2 f c r s)))
  (('frame n1 x1)        (VM a x1 f c (make-vector n1) s))
  (('argument i x1)      (vector-set! r i a)
                         (VM a x1 f c r s))
  (('apply n2) (match a
   (#(n1 x1 _ ...)       (or (= n1 n2) (error "VM APPLY -- ARGUMENT?" n1 n2))
                         (VM a x1 r a '() s))
   ((? procedure? fn) (match s ((x1 f1 c1 r1 s1)
                         (VM (apply fn (vector->list r)) x1 f1 c1 r1 s1))))))
  (('close-dummy n1 x1)  (VM a x1 (make-vector n1) (closure 0 '() f c) r s))
  (('close-rec x1)       (vector-copy! f 0 r)
                         (VM a x1 f c r s))
  (('return) (match s ((x1 f1 c1 r1 s1)
                         (VM a x1 f1 c1 r1 s1))))))

closure 手続きは既存のディスプレイ・クロージャから、 一段スコープが深いディスプレイ・クロージャを作ります。

 ; n x f1 #(n' fn' f2 f3...)  -->  #(n x f1 f2 f3...)
 (define (closure n x f1 c)
  ;(vector-append (vector n x f1) (vector-copy c 2)))
  (let ((v (make-vector (+ (vector-length c) 1))))
   (vector-set! v 0 n)
   (vector-set! v 1 x)
   (vector-set! v 2 f1)
   (vector-copy! v 3 c 2)
   v))

コンパイラに letrec のコンパイル部を追加します。 実引数のコンパイル部を compile-arg へ切り出して使いまわすことにします。

 (define (compile exp env next)
  (match exp
   (('letrec ((vars args) ...) . body)
    (let ((env-extended (compile-extend env vars)))
     (compile-push
      `(close-dummy ,(length vars)
        (frame ,(length vars) ,(compile-arg args env-extended `(close-rec
         ,(compile-seq body env-extended `(return))))))
      next)))
   ((fn . args)
    (compile-push
     `(frame ,(length args) ,(compile-arg args env
       (compile fn env `(apply ,(length args)))))
     next)) ))

 (define (compile-arg args env next)
  (fold-with-index (lambda (i arg x) (compile arg env `(argument ,i ,x)))
   next args))

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/tociyuki/20171219/1513689728
 |