参考までに,担当教員のつくったMiniMLコンパイラの参照実装を用いて再帰的な階乗計算プログラムをコンパイルした結果(中間表現とアセンブリコード)をそのまま載せておく.本文中の説明を読むだけではよく分からない場合でも,もしかしたら,これらの出力結果をじっと睨んでいるうちに何かをつかめるかも知れない.
fact.ml
let rec fact = fun n -> if n < 1 then
1
else
n * fact (n+ -1) in
fact 10;;
正規形
let rec fact n =
let _v0 = n < 1 in
if 0 < _v0 then 1
else
let _v1 = n + (-1) in
let _v2 = fact _v1 in
n * _v2 in
fact 10;;
閉じた正規形
let rec _b_fact (fact, n) =
let _v0 = n < 1 in
if 0 < _v0 then 1
else
let _v1 = n + (-1) in
let _r_fact = fact.0 in
let _v2 = _r_fact (fact, _v1) in
n * _v2 in
let fact = (_b_fact) in
let _r_fact = fact.0 in
_r_fact (fact, 10);;
フラット表現
let rec _b_fact (fact, n) =
let _v0 = n < 1 in
if 0 < _v0 then 1
else
let _v1 = n + (-1) in
let _r_fact = fact.0 in
let _v2 =
_r_fact (fact, _v1) in
n * _v2
let rec _toplevel (p0, p1) =
let fact = (#'_b_fact) in
let _r_fact = fact.0 in
_r_fact (fact, 10)
仮想機械コード
proc _b_fact(5) =
lt t1, p1, 1
bif t1, L_b_fact_0
add t2, p1, -1
read t3 #0(p0)
call t4, t3(p0, t2)
mul t0, p1, t4
goto L_b_fact_1
L_b_fact_0:
move t0, 1
L_b_fact_1:
ret t0
proc _toplevel(3) =
new t1 [_b_fact]
read t2 #0(t1)
call t0, t2(t1, 10)
ret t0
ARMアセンブリコード(レジスタ割付けなし)
.text
.align 2
.global _b_fact
_b_fact:
str fp, [sp, #-4]
str lr, [sp, #-8]
sub fp, sp, #4
sub sp, sp, #36
mov v1, a2
mov v2, #1
cmp v1, v2
blt LL_b_fact_0
mov v1, #0
b LL_b_fact_1
LL_b_fact_0:
mov v1, #1
LL_b_fact_1:
str v1, [fp, #-12]
ldr v1, [fp, #-12]
cmp v1, #0
bne L_b_fact_0
mov v1, a2
mov v2, #-1
add v1, v1, v2
str v1, [fp, #-16]
mov v1, a1
ldr v1, [v1, #0]
str v1, [fp, #-20]
str a1, [sp, #0]
str a2, [sp, #4]
ldr a2, [fp, #-16]
ldr v1, [fp, #-20]
blx v1
str a1, [fp, #-24]
ldr a1, [sp, #0]
ldr a2, [sp, #4]
mov v1, a2
ldr v2, [fp, #-24]
mul v1, v1, v2
str v1, [fp, #-8]
b L_b_fact_1
L_b_fact_0:
mov v1, #1
str v1, [fp, #-8]
L_b_fact_1:
ldr a1, [fp, #-8]
b _b_fact_ret
_b_fact_ret:
add sp, fp, #4
ldr lr, [fp, #-4]
ldr fp, [fp, #0]
bx lr
.align 2
.global _toplevel
_toplevel:
str fp, [sp, #-4]
str lr, [sp, #-8]
sub fp, sp, #4
sub sp, sp, #28
str a1, [sp, #0]
str a2, [sp, #4]
mov a1, #1
bl mymalloc
str a1, [fp, #-12]
ldr a1, [sp, #0]
ldr a2, [sp, #4]
ldr v2, [fp, #-12]
ldr v1, =_b_fact
str v1, [v2, #0]
ldr v1, [fp, #-12]
ldr v1, [v1, #0]
str v1, [fp, #-16]
str a1, [sp, #0]
str a2, [sp, #4]
ldr a1, [fp, #-12]
mov a2, #10
ldr v1, [fp, #-16]
blx v1
str a1, [fp, #-8]
ldr a1, [sp, #0]
ldr a2, [sp, #4]
ldr a1, [fp, #-8]
b _toplevel_ret
_toplevel_ret:
add sp, fp, #4
ldr lr, [fp, #-4]
ldr fp, [fp, #0]
bx lr
レジスタ機械コード
proc _b_fact(0) =
lt r0, p1, 1
bif r0, L_b_fact_0
add r1, p1, -1
read r2 #0(p0)
call r3, r2(p0, r1)
mul r0, p1, r3
goto L_b_fact_1
L_b_fact_0:
move r0, 1
L_b_fact_1:
ret r0
proc _toplevel(0) =
new r0 [_b_fact]
read r1 #0(r0)
call r2, r1(r0, 10)
ret r2
ARMアセンブリコード(レジスタ割付けあり)
.text
.align 2
.global _b_fact
_b_fact:
str fp, [sp, #-4]
str lr, [sp, #-8]
sub fp, sp, #4
sub sp, sp, #16
mov a4, #1
cmp a2, a4
blt LL_b_fact_0
mov v1, #0
b LL_b_fact_1
LL_b_fact_0:
mov v1, #1
LL_b_fact_1:
cmp v1, #0
bne L_b_fact_0
mov a4, #-1
add v2, a2, a4
ldr v3, [a1, #0]
str a1, [sp, #0]
str a2, [sp, #4]
mov a2, v2
mov a3, v3
blx a3
mov v4, a1
ldr a1, [sp, #0]
ldr a2, [sp, #4]
mul v1, a2, v4
b L_b_fact_1
L_b_fact_0:
mov v1, #1
L_b_fact_1:
mov a1, v1
b _b_fact_ret
_b_fact_ret:
add sp, fp, #4
ldr lr, [fp, #-4]
ldr fp, [fp, #0]
bx lr
.align 2
.global _toplevel
_toplevel:
str fp, [sp, #-4]
str lr, [sp, #-8]
sub fp, sp, #4
sub sp, sp, #16
str a1, [sp, #0]
str a2, [sp, #4]
mov a1, #1
bl mymalloc
mov ip, a1
ldr a1, [sp, #0]
ldr a2, [sp, #4]
ldr a3, =_b_fact
str a3, [ip, #0]
mov v1, ip
ldr v2, [v1, #0]
str a1, [sp, #0]
str a2, [sp, #4]
mov a1, v1
mov a2, #10
mov a3, v2
blx a3
mov v3, a1
ldr a1, [sp, #0]
ldr a2, [sp, #4]
mov a1, v3
b _toplevel_ret
_toplevel_ret:
add sp, fp, #4
ldr lr, [fp, #-4]
ldr fp, [fp, #0]
bx lr