SICP Reading #20 [3.1 ~ 3.2.3] 局所の入れ物としてのフレーム

院試/学会が無事終了したということでSICP勉強会再開.
2章の残りをまとめるのがメンドクサイのでそのまま3章に突入するなど :-p

環境/フレーム

SICPで定義されるScheme処理系では, 式の評価に必要な変数(名前)と値の対応を格納してる環境という構造があり, 環境はさらにフレームで構成される.

たとえば, 式

(define (square x)
        (* x x))

を実行した時の環境を考えてみると.

のような図で説明することができるとのこと(SICP表記とはちょっと変えてるけど).

(define (square x)
  (* x x))

をもうちょっと詳しく考えてみると, これは

(define square
  (lambda (x)
     (* x x)))

の syntax-sugar なので, すなわち.

defineは

現在のフレームに 名前と値 の対応を書き込む.

lambdaは

関数のオブジェクト(クロージャ)を返す. オブジェクトはlambda 実行持の環境の参照を持つ.

lambda 実行時の環境への参照を持つというのがミソで, これがすなわちレキシカルクロージャーってことかな.

内部定義とかでは, このフレームが連鎖してくとのこと.

ここまでわかれば, 問題も楽勝.

問題 3.10

手続き make-withdraw が以下のように与えれた場合.

(define (make-withdraw initial-amount)
  (let ((balance initial-amount))
    (lambda (amount)
      (if (>= balance amount)
          (begin (set! balance (- balance amount))
                 balance)
          "Insufficient founds"))))

次の式を実行した時の環境構造を示せというもの.

(define W1 (make-withdraw 100))
(W1 50)
(define W2 (make-withdraw 100))

まず

make-withdraw の定義文の syntax-sugar を剥ぎ取る!! (わかりやすくね.)

let は ((lambda でクロージャを作って) 適用する) syntax-sugar.

(let ((<var> <exp>)) <body>)

((lambda (<var>) body) <exp>)

また, define の syntax-sugar も剥ぎとると, make-withdraw の定義は

(define make-withdraw
  (lambda (initial-amount)
    ((lambda (balance)
       (lambda (amount)
         (if (>= balance amount)
             (begin
               (set! balance (- balance amount))
               balance)
             "Insufficient funds")))
     initial-amount)))

となる.

(lambda (initial-amount) ~~) が実行されると, 大域環境を環境に持ったクロージャが返る. それに対して defineで make-withdraw という名前で環境に書き込む. この時点での環境構造を図で表すとこんな感じ.

lambda と define のここの役割がわかれば, 簡単.
この調子で問題をといてみる.

W1を定義

微妙に説明してなかったけど, 関数オブジェクトに引数を与えるということは, 引数に対応するフレームを追加し, 関数オブジェクトのコード本体を実行するということなので, initial-amount が載ってるフレームが新規に作成される.

ここで

make-withdraw に対応した関数オブジェクトのコード部分

((lambda (balance)
       (lambda (amount)
             <body>)))
     initial-amount)

では, 度のlambda が実行される. しかも, 1度目のlambda は名前がつけられないまま適用される!! (その結果として評価されるべきlambda 式が返る)

結果を図にしてみる.

ここで,

  • フレームE1は, (make-withdraw 100)という関数実行持に作られたフレーム
  • フレームE2は,名前もつけられないまま実行された (lambda (balance) ) を initial-balance を引数で実行した時に作成されたフレーム
  • (W1 50) を実行してみる

    (W1 50)を実行すると, W1に対応する関数オブジェクトのコード内部で, (set! balance ~) によって balance の値を書き換えるる. ここで, 「balance の値を書き換える」とは, フレームをたどって, balance に対応する値を書き換えるということなので, 結果は

    と, 構造は変わらず, フレームE2の balance の値が変更される.

    W2を定義

    ここで, もうひとつの講座オブジェクト W2 を作るとどうなるのか? と言う問題.

    (define W2 (make-withdraw 100))

    W2を上記の式で定義すると, W1と同様のプロセスを辿る. ここで重要なのは, 生成されるフレーム(環境)は別ということ.

    図で注目する点として,

    1. W1, W2 の関数オブジェクトは, それぞれ異なる環境への参照を持ってる.
    2. W1, W2 の関数オブジェクトは, コード部を共有してる.

    1点目が, W1, W2をそれぞれ別のオブジェクトとして扱える基礎となってるのは言うまでもないですね.
    2点目に関しては, SICP 「処理系の実装による」と注記されていた. (この辺は5章でやるのかな?)

    今回は

    Scheme の実行モデル, クロージャ, 再代入…. いろいろ開眼した気がする.
    *複雑なので図にミスあるかも >< 指摘, 訂正大歓迎です.

Python で Turing-Machine シミュレーター

僕が今読んでいる計算理論の基礎では Turing-Machine が登場してきます.

Turing-Machineによるアルゴリズムは, 非直感的で, 人間が記述や動作のシミュレーションをするのは骨が折れます(まじで). ということで, Turing-Machine のシミュレーターを Python でサクッと実装してみました.

コード

 

動かしてみる

“0” が 2の乗数個分続く文字列(ex: “0”, “00”, “0000”..)を認識するTuring-Machineを作成してみます. 遷移関数は Python の辞書で手抜き :-p

def is_power_of_two_of_0(str, dump):
delta = {'q1':{'_':('qreject','R'),'x':('qreject','R'),'0':('q2','_','R')},
'q2':{'_':('qaccept','R'),'x':('q2','R'),'0':('q3','x','R')},
'q3':{'_':('q5','L'),'x':('q3','R'),'0':('q4','R')},
'q4':{'_':('qreject','R'),'x':('q4','R'),'0':('q3','x','R')},
'q5':{'_':('q2','R'),'x':('q5','L'),'0':('q5','L')}}
turing_machine = TM(delta, 'q1', 'qaccept', 'qreject')
turing_machine.dump = dump
return turing_machine.does_accept(str)

これを実行してみると,

&gt;&gt;&gt; import turing_machine
&gt;&gt;&gt; turing_machine.is_power_of_two_of_0("0000", True)
'q1'0000
_'q2'000
_x'q3'00
_x0'q4'0
_x0x'q3'_
_x0'q5'x_
_x'q5'0x_
_'q5'x0x_
'q5'_x0x_
_'q2'x0x_
_x'q2'0x_
_xx'q3'x_
_xxx'q3'_
_xx'q5'x_
_x'q5'xx_
_'q5'xxx_
'q5'_xxx_
_'q2'xxx_
_x'q2'xx_
_xx'q2'x_
_xxx'q2'_
_xxx_'qaccept'_
True

ちゃんと認識されてますね(良かった).

Twitter の TL上でbrainfu*k処理系を実装するのがが流行ってるっぽいので, 自分も一枚噛んでみようかなぁと思ってたり. とりあえず Turing-Machine シミュレーターから実装してみたのでした.

東工大(院)合格した!

夏休みは

大学院試験や初の学会発表など, 非常に濃ゆい夏休みでした(休みじゃない?).

タイトル通り, 大学院合格しました!! 東京工業大学です! 来年から東京生活です!

ってことで

院試と学会発表という2大タスクが終了したので, SICP勉強会や各種勉強会も力入れていきます.
ブログの更新もね :-p

Pythonで正規表現->DFA変換

CodeZineに

Pythonでの正規表現エンジンの実装講座という記事があったので、実装してみた。
エンジンの仕様は、

  1. DFAによる完全マッチング
  2. 和集合,連結,繰り返しのみをサポートした最小(数学的な)構成
  3. 括弧による演算の優先順位も考慮

のような感じ。

丁寧かつ軽く読みながせる記事なので、実装は記事を参照してほしいです。

使ってみる

SHINYA% python
Python 2.5.1 (r251:54863, Feb  6 2009, 19:02:12)
[GCC 4.0.1 (Apple Inc. build 5465)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from dfareg import *
>>> regexp = Regexp(ur'(A|B)*C')
>>> regexp.matches('AABBC')
True
>>> regexp.matches('C')
True

状態遷移の書き出し

この実装では、状態遷移を辞書(ハッシュ)を持つ(関数)オブジェクトで実装していて、
状態と入力文字を引数とした関数を生成していた。

def transition(state, char): # map is dictionary
    return frozenset(map_.get((state, char), []))

全ての遷移規則がわかるので、この辞書を解析することで完全な状態遷移を書き出す事も少しの変更で可能。
いか記事の実装に付け足したコード。 #CbCは状態遷移言語の意味

# emit CbC-souce, from dfa
def dfa2CbC(dfa, regexp):

    # return state name from set
    def set2name(set_):
        l = list(set_)
        l.sort()
        return '_'.join(str(x) for x in l)

    funcMap = dict()
    funcMap[dfa.start] = set()

    # dfa.map => {(frozenset([1, 15]), 'd'): frozenset([16]), ....}
    #             : frozenset(1, 15) x 'd' -> frozenset([16])

    for v in dfa.map.itervalues():
        funcMap[frozenset(v)] = set()

    for key in dfa.map.iterkeys():
        slot = funcMap.setdefault(key[0], set())
        slot.add(key[1])

    # emit cbc code
    print "#include <stdio.h>\n"
    for k in funcMap.iterkeys():
        print '__code state_' + set2name(k) + "(char* s);"
    print '__code accept();'
    print '__code reject();'
    print """
int main(int argc, char* argv[]) {
\tputs(\"regexp: %s\");
\tputs(\"number of state: %d\");
\tprintf(\"string: %%s\\n\", argv[1]);
\tgoto state_%s(argv[1]);
\treturn 0;
}\n"""
% (regexp, len(funcMap), set2name(dfa.start))

    for k, v in funcMap.iteritems():
        print '__code state_' + set2name(k) + "(char* s) {"
        print "\tswitch(*s++) {"
        for case in v:
            print "\t\tcase '%c': " % (case)
            print "\t\t\tgoto state_%s(s);\n\t\t\tbreak;" % set2name(dfa.map[(frozenset(k), case)])
        if k in dfa.accepts: print "\t\tcase '\\0': goto accept();\n\t\t\tbreak;"
        print "\t\tdefault: goto reject();\n\t}"
        print "}\n"

    print """
__code accept() {
\tprintf(\"\\nstring matches regexp. \\n\\n\");
}\n"""

    print """
__code reject() {
\tprintf(\"\\nstring does not match regexp. \\n\\n\");
}\n"""

__codeは、状態の記述に使う修飾子。
goto (__code)foo(arg);
という記述でfooにargを持って状態遷移を行なう感じ。

これで、実際に'(A|B)*C’を状態遷移に書き下してみる。

#include <stdio.h>

__code state_1_2_3_5_7(char* s);
__code state_1_3_5_6_7(char* s);
__code state_8(char* s);
__code state_1_3_4_5_7(char* s);
__code accept();
__code reject();

int main(int argc, char* argv[]) {
        puts("regexp: (A|B)*C");
        puts("number of state: 4");
        printf("string: %s\n", argv[1]);
        goto state_1_3_5_6_7(argv[1]);
        return 0;
}

__code state_1_2_3_5_7(char* s) {
        switch(*s++) {
                case 'A':
                        goto state_1_2_3_5_7(s);
                        break;
                case 'C':
                        goto state_8(s);
                        break;
                case 'B':
                        goto state_1_3_4_5_7(s);
                        break;
                default: goto reject();
        }
}

__code state_1_3_5_6_7(char* s) {
        switch(*s++) {
                case 'A':
                        goto state_1_2_3_5_7(s);
                        break;
                case 'C':
                        goto state_8(s);
                        break;
                case 'B':
                        goto state_1_3_4_5_7(s);
                        break;
                default: goto reject();
        }
}

__code state_8(char* s) {
        switch(*s++) {
                case '\0': goto accept();
                        break;
                default: goto reject();
        }
}

__code state_1_3_4_5_7(char* s) {
        switch(*s++) {
                case 'A':
                        goto state_1_2_3_5_7(s);
                        break;
                case 'C':
                        goto state_8(s);
                        break;
                case 'B':
                        goto state_1_3_4_5_7(s);
                        break;
                default: goto reject();
        }
}


__code accept() {
        printf("\nstring matches regexp. \n\n");
}


__code reject() {
        printf("\nstring does not match regexp. \n\n");
}

‘(A|B)*C’という正規表現は、4つの状態からなる小さな状態遷移で表現できることが分かる。

CbC

ちなみに、上記生成したC言語チックなコードは、僕の研究室で作られたCbCという言語。
状態遷移の記述に適している言語なので、今回サンプルとして下記だしてみた。
GCCのC-frontendを拡張して既に実装してあるので、上記CbCソースはコンパイルして実行することも可能。
(__code を voidに、 goto foo(args) を foo(args) に変換すればCとして実行できる)

比較とか

生成したソースをコンパイルしてのマッチングと、Python のライブラリとかにある正規表現との比較とかしてみたい。
もっと言えば 生成したソースをJITしてみたりしたい!!

LLVMとかも面白そう。

正規表現エンジンの実装凄く面白いし、最適化とか置くも深いと思う。大学のオートマトンの講義を受けている時にこういうのを触っておけばもっと講義を楽しめたかも ;-)

SICP Reading #19 [2.2.3] 公認インターフェースとしての並び

春休みはSICPガッツリ進めるぜ!と意気込んでいたけど、微妙に時間を割けてない感じで不甲斐ない。。
とりあえず溜まってる更新をサラッと済ませる。

全てはリスト処理

まず例として以下のコード実装を

木を引数にとり、奇数である葉の二乗を返す
(define (sum-odd-squares tree)
  (cond ((null? tree) 0)
        ((not (pair? tree))
         (if (odd? tree) (squares tree) 0))
        (else (+ (sum-odd-squares (car tree))
                 (sum-odd-squares (cdr tree))))))
引数n以下の偶数のFibonacci数のリストを返す
(define (even-fibs n)
  (defien (next k)
    (if (> k n)
        '()
        (let ((f (fib k)))
          (if (even? f)
              (cons f (next (+ k 1)))
              (next (+ k 1)))))))

2つの手続きの実装を見てみると、当然全く違う処理の流れに見える。
(どちらも再帰だけど、木の処理は二重再帰だしね)

だけど、どちらも抽象的に記述すると似通っていて、かつどちらも

  • enumerate (数え上げ)
  • accumulate (リスト演算)
  • map (リスト変換)
  • filter (リストのフィルタ)

という高階な処理で記述できるよね、という感じ。

  • 木の葉を数え上げる[enumerate]
  • 奇数でフィルタ[filter]
  • 選ばれた要素を二乗[map]
  • 要素を0初期値で加算[accumulate]

及び

  • 整数を0からnまで数え上げる[enumerate]
  • それぞれの要素でFibonacci数を計算[map]
  • 偶数でフィルタ[filter]
  • 要素を空リスト初期値でcons[accumulate]

よって

処理なんて全部(?)こんな感じのリスト処理に落とせるじゃん!明白じゃん!
“リスト”というデータ構造の処理に落とし込むことで、プログラミングの各ステージが明瞭だし、独立性が高くなるね(っていうことかな?)。

問題2.33

map, append, lengthの実装穴埋め問題

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) '() sequence))

(map (lambda (x) (* x x)) '(1 2 3 4 5 6 7 8 9 10))
;gosh> (1 4 9 16 25 36 49 64 81 100)

(define (append seq1 seq2)
  (accumulate cons seq2 seq1))

(append '(1 2 3) '(4 5))
;gosh> (1 2 3 4 5)

(define (length sequence)
  (accumulate (lambda (x y) (+ y 1)) 0 sequence))

(length '(1 2 3 4 4 890))
;gosh> 6

問題2.34

hornerの方法を使って、xの多項式の演算をaccumulateで実装する問題

(add-load-path ".")
(load "q2-33")

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms)
                (+ this-coeff (* higher-terms x)))
              0
              coefficient-sequence))

(horner-eval 2 '(1 3 0 5 0 1))
;gosh> 79
;; 実質こういうこと
;; (let1 x 2 (+
;;            1
;;            (* 3 x)
;;            (* 5 (expt x 3))
;;            (expt x 5)))

問題2.35

2.2.2節のcount-leavesをaccumulateで。
提示された条件では、mapを使ってたけど最初に思い浮かんだのは以下な実装

(add-load-path ".")
(load "q2-33")

;;2.2.2の実装は
(define (count-leaves x)
  (cond ((null? x) 0)
        ((not (pair? x)) 1)
        (else (+ (count-leaves (car x))
                 (count-leaves (cdr x))))))

;;accumulate版. map使わない方が自然に思いついた
(define (count-leaves t)
  (accumulate (lambda (x y)
                (+ (if (pair? x) (count-leaves x) 1)
                   y))
              0
              t))

(count-leaves '(1 2 (3 4) (5 6) (7 8 (9 1))))
;gosh> 10

一応、指定通りmapを使ってみた版も

;;map使う場合(提示された条件)
(define (count-leaves t)
  (accumulate (lambda (x y) (+ x y))
              0
              (map (lambda (x) (if (pair? x)
                                   (count-leaves x)
                                   1)) t)))

accumulateに渡すのはリスト!!
ってのが自然だと思うかから、mapの中で再帰して最終的に各部分木の葉の数のリストに変換して一気に処理するほうが見通しがいいかもしれないと思った。

問題2.36

accumulateのmulti-list対応版

(add-load-path ".")
(load "q2-33.scm")

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      '()
      (cons (accumulate op init (map
                                 (lambda (x) (car x))
                                 seqs))
            (accumulate-n op init (map (lambda (x) (cdr x))
                                       seqs)))))

テストしてみないと不安..

(add-load-path ".")
(load "q2-37.scm")

(use gauche.test)
(test-start "accumulate-n")

(define s '((1 2 3) (4 5 6) (7 8 9) (10 11 12)))

(print "s = " s)
(test* "(accumulate-n + 0 s)"
       '(22 26 30)
       (accumulate-n + 0 s))
(test-end)
SHINYA% gosh q2-36.test.scm
Testing accumulate-n ...
s = ((1 2 3) (4 5 6) (7 8 9) (10 11 12))
test (accumulate-n + 0 s), expects (22 26 30) ==> ok
passed.

(テスト少な!!)まぁOK?

問題2.37

ベクトル演算。 ベクトルなんて所詮リストのリストだよね!
小さい手続きから実装していくと、意外に簡単に実装できた。 C++のオブジェクトで実装して結構苦戦した記憶が。。(まぁそっちでは逆行列とかも導出してたわけだけど)

(add-load-path ".")
(load "q2-36")

(define map (with-module gauche map))
(define v1 '(1 2 3))
(define v2 '(4 5 6))
(define m  '((1 2 3) (4 5 6) (7 8 9)))

(define (dot-product v w)
  (accumulate + 0 (map * v w)))

(dot-product v1 v2)
;gosh> 32

(define (matrix-*-vector m v)
  (map (lambda (x) (dot-product x v)) m))

(matrix-*-vector m v1)
;gosh> (14 32 50)

(define (transpose mat)
  (accumulate-n cons '() mat))

m
;gosh> ((1 2 3) (4 5 6) (7 8 9))
(transpose m)
;gosh> ((1 4 7) (2 5 8) (3 6 9))

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (x)
           (map (lambda (y) (dot-product x y))
                cols)) m)))

(define m1 '((1 2) (3 4)))

(matrix-*-matrix m1 m1)
;((7 10) (15 22))

(matrix-*-matrix '((1 2 3)
                   (4 5 6)
                   (7 8 9))
                 '((1 0 0)
                   (0 1 0)
                   (0 0 1)))
;基本行列Eとの掛け算. E*A = A*E = A
;gosh> ((1 2 3) (4 5 6) (7 8 9))

問題2.34

accumulateは要素同士の演算を右から左に行なう。逆に演算したい場合は
再帰で評価を保留しておくべし。

(define (fold-right op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (fold-right op initial (cdr sequence)))))

(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))

この二つのaccumulate実装で、結果が同じとなるような演算opの定義についての問題。
「op: 交換則がなりたつ演算の場合(加算,乗算) fold-right/leftの結果は同値」かな。

;;成り立つ
(fold-right + 0 (list 1 2 3 4 5 6))
;gosh> 21
(fold-left  + 0 (list 1 2 3 4 5 6))
;gosh> 21
(fold-right * 1 (list 1 2 3 4 5 6))
;gosh> 720
(fold-left  * 1 (list 1 2 3 4 5 6))
;gosh> 720

;;成り立たない
(fold-right / 1 (list 1 2 3))
;(/ 1 (/ 2 (/ 3 1))) -> 3/2
(fold-left  / 1 (list 1 2 3))
;(/ (/ (/ 1 1) 2) 3) -> 1/6
(fold-right list '() (list 1 2 3))
;gosh> (1 (2 (3 ())))
(fold-left list '() (list 1 2 3))
;gosh> (((() 1) 2) 3)

問題2.39

実装の穴埋め問題

(add-load-path ".")
(load "q2-38.scm")
;; with fold-right
(define (reverse-fr sequence)
  (fold-right (lambda (x y)
                (append y (list x))) '() sequence))
;(append (append (append '() '(3)) '(2)) '(1))

;; with fold-left
(define (reverse-fl sequence)
  (fold-left (lambda (x y)
               (cons y x)) '() sequence))
;(cons 3 (cons 2 (cons 1 '())))

appendはリストの末尾までたどってポインタを入れ替えるからO(n), consはセルで包むだけなのでO(1) (多分)。
かつfold-rightは再帰ので(null? sequence)という最終条件が来るまで式が展開されるので、再帰が深いとスタックをヒープにコピーする作業でガツンと遅くなる場合がある(らしい)。

(use srfi-1)
(time (begin (reverse-fr (iota 1200 0)) #t))
;gosh> ;(time (begin (reverse-fr (iota 1200 0)) #t))
; real   0.271
; user   0.270
; sys    0.000
;#t

(time (begin (reverse-fl (iota 500000 0)) #t))
;gosh> ;(time (begin (reverse-fl (iota 500000 0)) #t))
; real   0.236
; user   0.240
; sys    0.010
;#t

;;スケールするのは反復的プロセス!!

(time (begin (fold-right * 1 (iota 10000 0)) #t))
(time (begin (fold-left  * 1 (iota 10000 0)) #t))

;append -> O(n)
;cons   -> O(1)

まぁ、appendの遅延なんて取るに足らないと思うけど。

上記の件はid:yamanetoshiさんのブログでshiroさんがコメントしてくれてたり。

goshを-fcollect-starsオプションで起動するとスタックオーバーフローの回数やら時間やらが見れるらしい。使わせてもらいますとも。

 
Better Tag Cloud