実験・実装 · 基礎から応用へ

定数畳み込みで変えてよい式を確かめる

定数だけの部分木を計算済みの値へ置き換え、正常な結果だけでなくゼロ除算や未定義名の振る舞いも比較します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 最適化で保つものを先に決める
  2. 子から順に部分木を畳む
  3. 失敗する式を勝手に成功させない
  4. コードで前後の観測結果を比べる
  5. 整数でも演算規則を混ぜない
  6. 試験入力の種類を増やす
  7. 課題は失敗が残る理由を説明する
  8. この記事をロゲイアに質問する理解を確かめる

最適化で保つものを先に決める

定数畳み込みは、実行前に値が分かる部分式を、その値へ置き換える変換です。x + 3 * (4 - 1)なら、xの値は分からなくても右の部分木は9へまとめられます。ただし、木を短くできたこと自体は正しさの証拠ではありません。この実験では、整数が入った同じ環境で得られる値と、発生するエラーの種類を変えないことを目標にします。元の評価器は左から右へ子を評価し、/は床による整数除算です。入力、演算規則、観測する失敗を先に固定することで、変換後の答えが偶然一致しただけという比較を避けます。浮動小数点、関数呼出し、副作用、固定幅整数のオーバーフローは今回の言語にはありません。それらを含む処理系の最適化へ、この条件をそのまま一般化しないでください。

子から順に部分木を畳む

foldは整数と名前の節点をそのまま返します。二項演算なら、左と右の子をそれぞれ変換し、その結果で新しい節点を作ります。両方の子が整数になった場合だけ、その小さな木を評価します。この順序で進むと、最初は4 - 1が3へ変わり、その親の3 * 3が9へ変わります。親だけを先に一度見る処理では、変換前の右の子が減算の木なので、畳める機会を見逃すかもしれません。実験では元の木を直接書き換えず、新しいタプルを返すため、前後の比較に元の表現を残せます。これは必須の最適化方式ではありませんが、小さな検証には見通しのよい設計です。名前を定数とみなして環境から読み取ることはしません。実行ごとにxの値が変わるという契約を守り、変換時の都合で一つの値へ固定しないためです。

失敗する式を勝手に成功させない

0 * (1 / 0)を、外側の0だけを見て0へ変えるとどうなるでしょうか。元の評価器では右側も評価するためゼロ除算になりますが、変換後には正常な値が返ってしまいます。この実験ではそのような代数的な置換を行いません。また、定数だけの部分木でも1 / 0を変換時に評価すれば失敗します。foldはその例外を捕まえ、失敗する演算の節点を残して実行時へ渡します。これにより変換器が起動した時点へエラーを移すのではなく、元の評価で失敗する場所を保つ方針を表します。エラー時点をどこまで保つかは言語やコンパイラの仕様によりますが、この教材では明示的に選びます。数式として同じ値に見えることだけでなく、値が存在しない入力についても、利用者から見える結果を比較する必要があります。

コードで前後の観測結果を比べる

コード全体をfold.pyへ保存し、Python 3.12以降で実行します。字句解析、構文解析、評価のコードも含む独立したファイルです。表示される木ではxへの加算は残り、右の子だけがnumの9になります。x=-10、0、12の三つの環境について元の木と変換後の木を評価し、結果が一致することをassertで確認します。続く二つの入力では、値が返ったか例外になったかも含めた記録を作り、前後を比較します。例外を握りつぶして全てNoneへ変えたのでは、違う失敗を同一と扱ってしまいます。このコードはKeyErrorとZeroDivisionErrorを区別して保存します。実験を成功とする条件は、木が小さくなったこと、示した環境で値が保たれたこと、示した失敗例の種類が保たれたことの三つです。全てのプログラムについて証明したという意味ではありません。

python
import re

def scan(source):
    tokens = []
    i = 0
    while i < len(source):
        if source[i].isspace():
            i += 1
            continue
        match = re.match(r'[0-9]+|[A-Za-z_][A-Za-z_0-9]*|[()+*\-/]', source[i:])
        if not match:
            raise SyntaxError(f'character at {i}')
        word = match.group()
        kind = 'NUM' if word.isdecimal() else 'NAME' if word[0].isalpha() or word[0] == '_' else word
        tokens.append((kind, word, i))
        i += len(word)
    tokens.append(('EOF', '', i))
    return tokens

class Parser:
    def __init__(self, source):
        self.tokens = scan(source)
        self.i = 0
    def take(self, kind):
        token = self.tokens[self.i]
        if token[0] != kind:
            raise SyntaxError(f'expected {kind} at {token[2]}')
        self.i += 1
        return token
    def atom(self):
        kind, word, pos = self.tokens[self.i]
        if kind == 'NUM':
            self.take('NUM')
            return ('num', int(word))
        if kind == 'NAME':
            self.take('NAME')
            return ('name', word)
        if kind == '(':
            self.take('(')
            node = self.expr()
            self.take(')')
            return node
        raise SyntaxError(f'atom at {pos}')
    def term(self):
        left = self.atom()
        while self.tokens[self.i][0] in ('*', '/'):
            op = self.take(self.tokens[self.i][0])[0]
            left = (op, left, self.atom())
        return left
    def expr(self):
        left = self.term()
        while self.tokens[self.i][0] in ('+', '-'):
            op = self.take(self.tokens[self.i][0])[0]
            left = (op, left, self.term())
        return left
    def parse(self):
        tree = self.expr()
        self.take('EOF')
        return tree

def evaluate(node, env):
    kind = node[0]
    if kind == 'num':
        return node[1]
    if kind == 'name':
        return env[node[1]]
    left, right = evaluate(node[1], env), evaluate(node[2], env)
    if kind == '+': return left + right
    if kind == '-': return left - right
    if kind == '*': return left * right
    if kind == '/':
        if right == 0: raise ZeroDivisionError('zero divisor')
        return left // right
    raise ValueError(kind)

def fold(node):
    if node[0] in ('num', 'name'):
        return node
    left, right = fold(node[1]), fold(node[2])
    candidate = (node[0], left, right)
    if left[0] == right[0] == 'num':
        try:
            return ('num', evaluate(candidate, {}))
        except ZeroDivisionError:
            return candidate
    return candidate

tree = Parser("x + 3 * (4 - 1)").parse()
optimized = fold(tree)
assert optimized == ('+', ('name','x'), ('num',9))
for x in [-10, 0, 12]:
    assert evaluate(tree, {'x':x}) == evaluate(optimized, {'x':x})
for source in ['0 * (1 / 0)', 'unknown + (2 * 3)']:
    before, after = Parser(source).parse(), fold(Parser(source).parse())
    outcomes = []
    for node in [before, after]:
        try:
            outcomes.append(('value', evaluate(node, {})))
        except (KeyError, ZeroDivisionError) as error:
            outcomes.append(('error', type(error).__name__))
    assert outcomes[0] == outcomes[1]
print(optimized)

整数でも演算規則を混ぜない

この言語の整数はPythonの整数なので、固定したビット幅から値があふれる規則はありません。例えば非常に大きい二つの整数を足しても、別の符号へ巻き戻るという模型ではありません。固定幅の言語向けに変換を作る場合には、定数を計算する処理も、その言語のオーバーフローや変換の規則と一致させる必要があります。除算も、負数をゼロ方向へ切り捨てる言語と床を取る言語では結果が違います。さらに浮動小数点を追加すると、演算のまとめ方や丸め、NaNなどを考える必要があります。実験で使うPythonに任せれば対象言語の意味も自動で守られる、と考えないでください。今回のように自分で決めた小さな言語でも、変換する側と実行する側が同じ規則を共有していることが重要です。その前提を明記した上で、限定した範囲の正しさを検証します。

試験入力の種類を増やす

次の確認には、完全な定数式、名前だけの式、名前と定数を混ぜた式、定数部分で失敗する式を用意します。それぞれが違う経路を通るため、似た足し算だけを増やすより情報が得られます。例えばx + 2 * 3は右だけを畳めますが、x * yは名前を残します。括弧や結合規則はパーサが既に木へ反映しているので、foldの中で文字列へ戻して再解釈しません。小さな範囲の整数と環境を複数組み合わせて比較する方法も使えますが、有限の試験だけで全入力の同値性を証明したことにはなりません。変換規則ごとに、どの前提の下で正しいかを説明し、その前提を壊す反例も探す姿勢が必要です。計測する場合も、木の節点数と実行時間は別の指標です。木が短いことから、実機で必ず速くなったと断定しないようにします。

課題は失敗が残る理由を説明する

課題として、(2 + 3) * xと0 * unknownを変換した木を予想します。前者では左の部分木が5へ畳まれますが、xは残ります。後者ではunknownが名前なので、外側の乗算も残り、空の環境で実行するとKeyErrorになります。unknownを勝手に読まなくして0を返す変換は、今回の目標に反します。次に(0 - 7) / 3を変換した場合を考えます。両方が定数なので、床による整数除算の結果-3という一つの節点へ置き換わります。自分の予想とコードの結果を照合し、どの部分木が変わったかを木の形で示してください。コードを拡張する場合は、この解答を保存して回帰試験へ加えます。実験は短い文字列と辞書だけを扱うため、終了時に外部資源を解放する作業はありません。次は、状態を持つ関数では置換が難しくなる理由を参照透過性の教材で確認できます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 20

学習コースから次を選ぶ