closure conversion

テンプレートのなかにリストを展開するような簡単なS式操作は分かっているつもりだけど、Closure Conversion みたいな式の形がだいぶ変わるような変換は初めてだ。再帰的な処理の固まりで難しい。

しかしなんとかどんくさいコードながら実装。このエレガントな変形をいつかアニメーションにしたいくらい。明示的に funcall が必要なのがかっこわるいけどたいした問題ではない、はず。

gosh>  (closure-conversion '(let ((f (lambda (g)
                 (funcall g 2 13))))
               (funcall f (lambda (n m) (* n m)))))
(labels ((G703 (code (g) () (funcall g 2 13))) (G704 (code (n m) () (* n m)))) (let ((f (closure G703))) (funcall f (closure G704))))

gosh> (run-program
               (closure-conversion '(let ((f (lambda (g)
                                                                   (funcall g 2 13))))
                                                        (funcall f (lambda (n m) (* n m))))))
"26\n"

LLVM IR は以下のとおり(ほんとはこの中間にS式がある)。クロージャ。

gosh> (compile-program
       (closure-conversion '(let ((f (lambda (g)
				       (funcall g 2 13))))
			      (funcall f (lambda (n m) (* n m))))))
declare i32 @display_obj(i32)
declare i32 @display_vector(i32)
declare i32 @display_pair(i32)
declare i32 @newline()
declare void @scheme_finalize()
declare void @scheme_initialize()
@ap = external global i32
define i32 @scheme_entry ()  {
entry:
    %ret = alloca i32
    %var121 = load i32* @ap
    %var125 = inttoptr i32 %var121 to i32*
    %var124 = ptrtoint i32 (i32)* @Label_5 to i32
    store i32 %var124, i32* %var125
    %var127 = or i32 6, %var121
    store i32 %var127, i32* %ret
    %var122 = add i32 4, %var121
    store i32 %var122, i32* @ap
    store i32 0, i32* %ret
    %var128 = load i32* %ret
    %var126 = inttoptr i32 %var122 to i32*
    store i32 %var128, i32* %var126
    %var123 = add i32 4, %var122
    store i32 %var123, i32* @ap
    store i32 %var127, i32* %ret
    %sta18 = alloca i32
    %var131 = load i32* %ret
    store i32 %var131, i32* %sta18
    %var133 = load i32* @ap
    %var137 = inttoptr i32 %var133 to i32*
    %var136 = ptrtoint i32 (i32, i32)* @Label_6 to i32
    store i32 %var136, i32* %var137
    %var139 = or i32 6, %var133
    store i32 %var139, i32* %ret
    %var134 = add i32 4, %var133
    store i32 %var134, i32* @ap
    store i32 0, i32* %ret
    %var140 = load i32* %ret
    %var138 = inttoptr i32 %var134 to i32*
    store i32 %var140, i32* %var138
    %var135 = add i32 4, %var134
    store i32 %var135, i32* @ap
    store i32 %var139, i32* %ret
    %var132 = load i32* %ret
    %var150 = load i32* %sta18
    store i32 %var150, i32* %ret
    %var143 = load i32* %ret
    %var144 = sub i32 %var143, 6
    %var145 = inttoptr i32 %var144 to i32*
    %var146 = load i32* %var145
    %var147 = inttoptr i32 %var146 to i32 (i32, i32)*
    %var148 = call i32 %var147(i32 %var132, i32 %var143)
    store i32 %var148, i32* %ret
    %retval = load i32* %ret
    ret i32 %retval
}
define i32 @Label_6 (i32 %arg1, i32 %arg2)  {
entry:
    ; start-define
    %ret = alloca i32
    %sta14 = alloca i32
    store i32 %arg1, i32* %sta14
    %sta15 = alloca i32
    store i32 %arg2, i32* %sta15
    %var119 = load i32* %sta14
    store i32 %var119, i32* %ret
    %sta16 = alloca i32
    %var111 = load i32* %ret
    store i32 %var111, i32* %sta16
    %sta17 = alloca i32
    %var120 = load i32* %sta15
    store i32 %var120, i32* %ret
    %var112 = load i32* %ret
    store i32 %var112, i32* %sta17
    %var113 = load i32* %sta16
    %var114 = load i32* %sta17
    %var115 = sdiv i32 %var113, 4
    %var116 = sdiv i32 %var114, 4
    %var117 = mul i32 %var115, %var116
    %var118 = mul i32 %var117, 4
    store i32 %var118, i32* %ret
    %retval = load i32* %ret
    ret i32 %retval
}
define i32 @Label_5 (i32 %arg1)  {
entry:
    ; start-define
    %ret = alloca i32
    %sta13 = alloca i32
    store i32 %arg1, i32* %sta13
    store i32 8, i32* %ret
    %var101 = load i32* %ret
    store i32 52, i32* %ret
    %var102 = load i32* %ret
    %var110 = load i32* %sta13
    store i32 %var110, i32* %ret
    %var103 = load i32* %ret
    %var104 = sub i32 %var103, 6
    %var105 = inttoptr i32 %var104 to i32*
    %var106 = load i32* %var105
    %var107 = inttoptr i32 %var106 to i32 (i32, i32, i32)*
    %var108 = call i32 %var107(i32 %var101, i32 %var102, i32 %var103)
    store i32 %var108, i32* %ret
    %retval = load i32* %ret
    ret i32 %retval
}
define i32 @main ()  {
entry:
    call void @scheme_initialize()
    %tmp = call i32 @scheme_entry()
    call i32 @display_obj(i32 %tmp)
    call i32 @newline()
    call void @scheme_finalize()
    ret i32 0
}
#<undef>
gosh>