Toy VM (15) - SECD マシンでの継続

SECD マシンで継続について（わたしが理解したことを）書こう。

トップレベルの扱いが異なっているため、 gauche と同じ結果になっていない。が、とりあえず。

追記。どうもまだバグがある気がしてきた。

;; debug を nil にして実行
SECD> (secd-eval '(let ((save #f))
                   (write (+ 3 (call/cc (lambda (cc) (set! save cc) 5))))
                   (write (save 10))) :debug nil)
;; 8
;; 13
NIL

;; debug を t にして実行
SECD> (secd-eval '(let ((save #f))
                   (write (+ 3 (call/cc (lambda (cc) (set! save cc) 5))))
                   (write (save 10))) :debug t)
STATE:
 S = S0
 E = E0
 C = (:NIL :LDC :SCHEME-F :CONS :LDF
      (:LDCT (:LDC 3 :+ :WRITE) :LDF
       (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN) :AP :LDC 3 :+ :WRITE :NIL
       :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
      :AP :STOP . C0)
 D = D0
;;; 初期状態。「継続」オブジェクトは、コンパイル時に決まっている。(:LDC 3 :+  :WRITE) で、call/cc の呼び出し後に行う処理になっている。
STATE MATCH (S E (NIL . C) D)  -> ((NIL . S) E C D)
 S = S0
 E = E0
 C = (:LDC :SCHEME-F :CONS :LDF
      (:LDCT (:LDC 3 :+ :WRITE) :LDF
       (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN) :AP :LDC 3 :+ :WRITE :NIL
       :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
      :AP :STOP . C0)
 D = D0
STATE:
 S = (NIL . S0)
 E = E0
 C = (:LDC :SCHEME-F :CONS :LDF
      (:LDCT (:LDC 3 :+ :WRITE) :LDF
       (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN) :AP :LDC 3 :+ :WRITE :NIL
       :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
      :AP :STOP . C0)
 D = D0
;;;
STATE MATCH (S E (LDC X . C) D)  -> ((X . S) E C D)
 S = (NIL . S0)
 E = E0
 X = :SCHEME-F
 C = (:CONS :LDF
      (:LDCT (:LDC 3 :+ :WRITE) :LDF
       (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN) :AP :LDC 3 :+ :WRITE :NIL
       :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
      :AP :STOP . C0)
 D = D0
STATE:
 S = (:SCHEME-F NIL . S0)
 E = E0
 C = (:CONS :LDF
      (:LDCT (:LDC 3 :+ :WRITE) :LDF
       (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN) :AP :LDC 3 :+ :WRITE :NIL
       :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
      :AP :STOP . C0)
 D = D0
;;;
STATE MATCH ((B A . S) E (CONS . C) D)  -> (((B . A) . S) E C D)
 B = :SCHEME-F
 A = NIL
 S = S0
 E = E0
 C = (:LDF
      (:LDCT (:LDC 3 :+ :WRITE) :LDF
       (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN) :AP :LDC 3 :+ :WRITE :NIL
       :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
      :AP :STOP . C0)
 D = D0
STATE:
 S = ((:SCHEME-F) . S0)
 E = E0
 C = (:LDF
      (:LDCT (:LDC 3 :+ :WRITE) :LDF
       (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN) :AP :LDC 3 :+ :WRITE :NIL
       :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
      :AP :STOP . C0)
 D = D0
;;;
STATE MATCH (S E (LDF c' . C) D)  -> (((CLOS c' . E) . S) E C D)
 S = ((:SCHEME-F) . S0)
 E = E0
 c' = (:LDCT (:LDC 3 :+ :WRITE) :LDF
       (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN) :AP :LDC 3 :+ :WRITE :NIL
       :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 C = (:AP :STOP . C0)
 D = D0
STATE:
 S = ((:CLOS
       (:LDCT (:LDC 3 :+ :WRITE) :LDF
        (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN) :AP :LDC 3 :+ :WRITE :NIL
        :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
       . E0)
      (:SCHEME-F) . S0)
 E = E0
 C = (:AP :STOP . C0)
 D = D0
;;;
STATE MATCH (((CLOS c' . e') V . S) E (AP . C) D)  -> (NIL (V . e') c'
                                                       (S E C . D))
 c' = (:LDCT (:LDC 3 :+ :WRITE) :LDF
       (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN) :AP :LDC 3 :+ :WRITE :NIL
       :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 e' = E0
 V = (:SCHEME-F)
 S = S0
 E = E0
 C = (:STOP . C0)
 D = D0
STATE:
 S = NIL
 E = ((:SCHEME-F) . E0)
 C = (:LDCT (:LDC 3 :+ :WRITE) :LDF (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN)
      :AP :LDC 3 :+ :WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
;;;
STATE MATCH (S E (LDCT c' . C) D)  -> ((((CONT S E c' . D)) . S) E C D)
 S = NIL
 E = ((:SCHEME-F) . E0)
 c' = (:LDC 3 :+ :WRITE)
 C = (:LDF (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN) :AP :LDC 3 :+ :WRITE
      :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
STATE:
 S = (((:CONT NIL ((:SCHEME-F) . E0) (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0)
        . D0)))
 E = ((:SCHEME-F) . E0)
 C = (:LDF (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN) :AP :LDC 3 :+ :WRITE
      :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
;;; 継続をスタックに積む。(:CONT s e c' . d)
STATE MATCH (S E (LDF c' . C) D)  -> (((CLOS c' . E) . S) E C D)
 S = (((:CONT NIL ((:SCHEME-F) . E0) (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0)
        . D0)))
 E = ((:SCHEME-F) . E0)
 c' = (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN)
 C = (:AP :LDC 3 :+ :WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
STATE:
 S = ((:CLOS (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN)
       . #1=((:SCHEME-F) . E0))
      ((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)))
 E = ((:SCHEME-F) . E0)
 C = (:AP :LDC 3 :+ :WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
;;;
STATE MATCH (((CLOS c' . e') V . S) E (AP . C) D)  -> (NIL (V . e') c'
                                                       (S E C . D))
 c' = (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN)
 e' = ((:SCHEME-F) . E0)
 V = ((:CONT NIL ((:SCHEME-F) . E0) (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0)
       . D0))
 S = NIL
 E = ((:SCHEME-F) . E0)
 C = (:LDC 3 :+ :WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
STATE:
 S = NIL
 E = (((:CONT NIL #1=((:SCHEME-F) . E0) (:LDC 3 :+ :WRITE) S0 E0
        (:STOP . C0) . D0))
      . #1#)
 C = (:LD (1 . 1) :SET (2 . 1) :LDC 5 :RTN)
 D = (NIL ((:SCHEME-F) . E0)
      (:LDC 3 :+ :WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN) S0
      E0 (:STOP . C0) . D0)
;;;
STATE MATCH (S E (LD (M . N) . C) D)  -> ((X . S) E C D)
 S = NIL
 E = (((:CONT NIL #1=((:SCHEME-F) . E0) (:LDC 3 :+ :WRITE) S0 E0
        (:STOP . C0) . D0))
      . #1#)
 M = 1
 N = 1
 C = (:SET (2 . 1) :LDC 5 :RTN)
 D = (NIL ((:SCHEME-F) . E0)
      (:LDC 3 :+ :WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN) S0
      E0 (:STOP . C0) . D0)
 RHS VAR X = (:CONT NIL ((:SCHEME-F) . E0) (:LDC 3 :+ :WRITE) S0 E0
              (:STOP . C0) . D0)
STATE:
 S = ((:CONT NIL ((:SCHEME-F) . E0) (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0)
       . D0))
 E = (((:CONT NIL #1=((:SCHEME-F) . E0) (:LDC 3 :+ :WRITE) S0 E0
        (:STOP . C0) . D0))
      . #1#)
 C = (:SET (2 . 1) :LDC 5 :RTN)
 D = (NIL ((:SCHEME-F) . E0)
      (:LDC 3 :+ :WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN) S0
      E0 (:STOP . C0) . D0)
;;;
STATE MATCH ((X . S) E (SET (M . N) . C) D)  -> (S e' C D)
 X = #1=(:CONT NIL ((#1#) . E0) (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)
 S = NIL
 E = ((#1=(:CONT NIL #2=((#1#) . E0) (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0)
           . D0))
      . #2#)
 M = 2
 N = 1
 C = (:LDC 5 :RTN)
 D = (NIL
      #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE)
            . #2=(S0 E0 (:STOP . C0) . D0)))
          . E0)
      (:LDC 3 :+ :WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
      . #2#)
 RHS VAR e' = ((#1=(:CONT NIL #2=((#1#) . E0) (:LDC 3 :+ :WRITE) S0 E0
                    (:STOP . C0) . D0))
               . #2#)
STATE:
 S = NIL
 E = ((#1=(:CONT NIL #2=((#1#) . E0) (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0)
           . D0))
      . #2#)
 C = (:LDC 5 :RTN)
 D = (NIL
      #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE)
            . #2=(S0 E0 (:STOP . C0) . D0)))
          . E0)
      (:LDC 3 :+ :WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
      . #2#)
;;;
STATE MATCH (S E (LDC X . C) D)  -> ((X . S) E C D)
 S = NIL
 E = ((#1=(:CONT NIL #2=((#1#) . E0) (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0)
           . D0))
      . #2#)
 X = 5
 C = (:RTN)
 D = (NIL
      #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE)
            . #2=(S0 E0 (:STOP . C0) . D0)))
          . E0)
      (:LDC 3 :+ :WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
      . #2#)
STATE:
 S = (5)
 E = ((#1=(:CONT NIL #2=((#1#) . E0) (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0)
           . D0))
      . #2#)
 C = (:RTN)
 D = (NIL
      #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE)
            . #2=(S0 E0 (:STOP . C0) . D0)))
          . E0)
      (:LDC 3 :+ :WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
      . #2#)
;;;
STATE MATCH ((X . Z) e' (RTN . c') (S E C . D))  -> ((X . S) E C D)
 X = 5
 Z = NIL
 e' = ((#1=(:CONT NIL #2=((#1#) . E0) (:LDC 3 :+ :WRITE) S0 E0
            (:STOP . C0) . D0))
       . #2#)
 c' = NIL
 S = NIL
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:LDC 3 :+ :WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
STATE:
 S = (5)
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:LDC 3 :+ :WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
;;;
STATE MATCH (S E (LDC X . C) D)  -> ((X . S) E C D)
 S = (5)
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 X = 3
 C = (:+ :WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
STATE:
 S = (3 5)
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:+ :WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
;;;
STATE MATCH ((A B . S) E (+ . C) D)  -> ((X . S) E C D)
 A = 3
 B = 5
 S = NIL
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
 RHS VAR X = 8
STATE:
 S = (8)
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:WRITE :NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
;; 8
;;;
STATE MATCH ((X . S) E (WRITE . C) D)  -> (S E C D)
 X = 8
 S = NIL
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
 RHS VAR DUM = NIL
STATE:
 S = NIL
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:NIL :LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
;;;
STATE MATCH (S E (NIL . C) D)  -> ((NIL . S) E C D)
 S = NIL
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
STATE:
 S = (NIL)
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:LDC 10 :CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
;;;
STATE MATCH (S E (LDC X . C) D)  -> ((X . S) E C D)
 S = (NIL)
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 X = 10
 C = (:CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
STATE:
 S = (10 NIL)
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:CONS :LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
;;;
STATE MATCH ((B A . S) E (CONS . C) D)  -> (((B . A) . S) E C D)
 B = 10
 A = NIL
 S = NIL
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
STATE:
 S = ((10))
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:LD (1 . 1) :AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
;;;
STATE MATCH (S E (LD (M . N) . C) D)  -> ((X . S) E C D)
 S = ((10))
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 M = 1
 N = 1
 C = (:AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
 RHS VAR X = #1=(:CONT NIL ((#1#) . E0) (:LDC 3 :+ :WRITE) S0 E0
                 (:STOP . C0) . D0)
STATE:
 S = (#1=(:CONT NIL ((#1#) . E0) (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0)
          . D0)
      (10))
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:AP :WRITE :RTN)
 D = (S0 E0 (:STOP . C0) . D0)
;;;
STATE MATCH (((CONT S E C . D) (V) . s') e' (AP . c') d')  -> ((V . S) E C
                                                               D)
 S = NIL
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:LDC 3 :+ :WRITE)
 D = (S0 E0 (:STOP . C0) . D0)
 V = 10
 s' = NIL
 e' = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0))
          . E0)
 c' = (:WRITE :RTN)
 d' = (S0 E0 (:STOP . C0) . D0)
STATE:
 S = (10)
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:LDC 3 :+ :WRITE)
 D = (S0 E0 (:STOP . C0) . D0)
;;;
STATE MATCH (S E (LDC X . C) D)  -> ((X . S) E C D)
 S = (10)
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 X = 3
 C = (:+ :WRITE)
 D = (S0 E0 (:STOP . C0) . D0)
STATE:
 S = (3 10)
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:+ :WRITE)
 D = (S0 E0 (:STOP . C0) . D0)
;;;
STATE MATCH ((A B . S) E (+ . C) D)  -> ((X . S) E C D)
 A = 3
 B = 10
 S = NIL
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:WRITE)
 D = (S0 E0 (:STOP . C0) . D0)
 RHS VAR X = 13
STATE:
 S = (13)
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = (:WRITE)
 D = (S0 E0 (:STOP . C0) . D0)
;; 13
;;;
STATE MATCH ((X . S) E (WRITE . C) D)  -> (S E C D)
 X = 13
 S = NIL
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = NIL
 D = (S0 E0 (:STOP . C0) . D0)
 RHS VAR DUM = NIL
STATE:
 S = NIL
 E = #1=(((:CONT NIL #1# (:LDC 3 :+ :WRITE) S0 E0 (:STOP . C0) . D0)) . E0)
 C = NIL
 D = (S0 E0 (:STOP . C0) . D0)
NIL