限定反復プログラム
『C言語による計算の理論』.icon特有の単語
必ず停止する
自然数上の全域関数を計算する
変数が負数になることはない
以下の条件を満たすプログラムのこと
while, gotoを使用しない
数式の中に使用してよいのは、変数と自然数定数のみ
普通のデクリメントは使用しない、条件付きデクリメントは使用できる
if (x!=0) x--;
変数はv1, .. ,vmのみ
前半が入力用、後半が作業用
return文はreturn(v1);という文がプログラムの最後に一つだけ存在する
変換手順
『C言語による計算の理論』.icon pp. 80-82
1で二項演算子を省く
こうやって見ると、単純な演算もかなり煩雑になるなmrsekut.icon
3について
ifの原子条件式を全てx > 0の形に変換する
原子条件式は一つ一つの条件
原始条件式を&&か||で結合して、条件節を作る
4のreturnについて
元のコードが以下のような場合を考える
code:before.c
f(x) {
int a;
return (a);
a = x + 1;
...
return (a);
}
限定反復プログラムのreturnは最後に一つだけしか使えないのでこう書き換える
code:after.c
f(x) {
int a, r, e;
r = 0;
e = 0;
if(e == 0) { r = a; e = 1; }
a = x + 1;
...
return (r);
}
このコードのifからreturnまでの処理は無駄に実行されてしまうが、これで良い
５について
関数をインライン展開する
これによって限定反復プログラム中には、すべての関数呼び出しが消える