くりかえしと、止まらない機械

回数を、前もって知らない

コース1の「4 かい くりかえす」は、始まる前から回数が決まっていました。でも、暮らしのくりかえしには別の形があります。「お湯が沸くまで、火にかける」「誰かが出てくるまで、ノックする」——回数ではなく、条件が終わりを決める形です。

今日あなたの言語に教える while は、こちらの形です。何回まわるかは、走らせてみるまで分かりません。これが今日の主役で、あとで起きる事件の犯人でもあります。

読み方は「x < 5 が真であるかぎり、{ } の中を実行しつづけよ」。③の欄に並ぶのは 0 と 5——最初の代入が残した 0 と、最後の行の x の 5 で、while の文そのものは値を残しません。働くだけ働いて、黙っている文です。

実験をひとつ。x + 1 を x + 2 に変えると、x は 4 の次に 6 になり、5 ちょうどを飛びこえます。それでも止まる——条件は「5 になった瞬間」を見張っているのではなく、毎周のはじめに見直されているからです。

ふたつの変数が、いっしょに育つ

{ } の中の文は、ひとつでなくてもかまいません。1 から 10 までの和を言わせてみます。

kazu が 1, 2, 3 と進み、goukei がそれを呑みこんでいって、③のいちばん右が 55。10 を 100 に書きかえれば 5050——プログラムの形は、そのままです。

見覚えがあるはずです。コース1のレッスン9で、あなたはこれとそっくりなJavaScriptを修理しました（1から5までの合計）。あのとき使う側として直した道具を、いまは作る側から見おろしています。

while を、実装する

工程②（木にする）には、もう驚かないはずです。while 条件 { 文… } という並びを読んで、「条件の式」と「本体の文のならび」を持つ節を作るだけです。問題は工程③——「成り立つかぎり」を、どう意味にするか。

手順は、声に出すと一周します。「条件を評価する。真なら本体を実行して、また条件へ戻る。偽なら、おしまい」。

// 「x < 5 のあいだ、x = x + 1」を、工程②が木にしたもの
const stmt = {
  cond: { op: "<", left: "x", right: 5 },
  body: { assign: "x", value: { op: "+", left: "x", right: 1 } },
};

const env = { x: 0 }; // 言語の記憶。レッスン6で作った環境

// 式を畳む：数はその数、名前は環境から、枝は左右を畳んでから
function evalExpr(e, env) {
  if (typeof e === "number") return e;
  if (typeof e === "string") return env[e];
  const l = evalExpr(e.left, env);
  const r = evalExpr(e.right, env);
  if (e.op === "+") return l + r;
  if (e.op === "<") return l < r;
}

// while文を意味にする。今日の主役
function execWhile(stmt, env) {
  while (evalExpr(stmt.cond, env)) {
    env[stmt.body.assign] = evalExpr(stmt.body.value, env);
  }
}

execWhile(stmt, env);
console.log("おわったあとの x:", env.x);

本体は「代入が1つだけ」と簡略化しましたが、骨組みはほんものの評価器と同じです。そして、気づいたでしょうか。あなたの言語の while を作るために、JavaScriptの while を使っています。

インタプリタのくりかえしは、実装言語のくりかえしでできているのです。実はたし算のときからそうでした——レッスン3の evaluate の中の l + r は、JSのたし算です。辞書の説明文がやはり言葉で書かれているように、言語は「すでに動く言語」の上にしか立てられません。

ではJSの while は何でできているのか。たどっていくと、機械語の「指定した場所へ戻れ」という命令に行き着きます。

止まらない機械

さて、ここからが事件です。下の実験室には、終わる条件が永遠に成り立たないくりかえしが、すでに置いてあります。

1 < 2 は、いつ評価しても真です。理屈の上では、このプログラムは永遠に終わりません。なのにブラウザは固まらず、「プログラムがいつまでも とまりませんでした。」という返事が、もう表示されています。

おかしいと思いませんか。あなたの言語の while はJSの while でできているのだから、条件が永遠に真なら、JSの while も永遠にまわって、このページごと凍りつくはずです。しかもこの実験室は打つたびに実行されるので、あなたは閉じかっこを打ち終えた瞬間に、無限ループを解き放っていたことになります。

種明かし——燃料を、払わせる

種を明かします。この実験室の評価器には、**燃料（フューエル）**という仕掛けが足してあります。文をひとつ実行する、式をひとつ畳む——評価の1歩ごとに燃料を1払わせて、10万歩で尽きたら計算を打ち切り、エラーとして報告するのです。

let fuel = 10; // ほんものの実験室では 100000

let x = 0;
while (1 < 2) {    // 永遠に真。本来なら、止まらない
  x = x + 1;
  fuel = fuel - 1; // 1歩すすむごとに、燃料を1はらう
  if (fuel <= 0) { // 燃料が尽きたら、そこでおしまい
    console.log("プログラムがいつまでも とまりませんでした。");
    break;         // くりかえしを、力ずくで抜ける合図
  }
}
console.log("止まったときの x:", x);

つまりさっきの返事の正体は、止まったのではなく、止められたでした。走り出すまえに防げなくても、走り出してからなら安く止められます——評価の一歩一歩が、インタプリタであるあなたの手の中を通るからです。

止め方には、もうひとつの流儀があります。コース1のレッスン9で、終わらないカウントダウンが「実行が2秒を超えたので、止めました」と打ち切られたのを覚えていますか。あれは時計で外から見張る方式で、今日の燃料は歩数を内側で数える方式です。

• 時計（タイムアウト）——どんなプログラムにも、外から付けられる。ただし速い機械は遠くまで走り、遅い機械は手前で止まる。どこで止まるかが、機械しだい
• 燃料——同じプログラムは、どの機械でも必ず同じ1歩めで止まる。ただし、評価のすべてが自分の手を通る、インタプリタの作者にしか選べない

どちらが正しい、ではありません。「止まらないプログラムは書かれうる」と認めたうえで、壊れたときの壊れ方を先に設計しておく——フェイルセーフと呼ばれる考え方です。強い道具を渡すときは、安全装置をいっしょに渡す。

「止まるか」を、先に知ることはできないのか

白状すると、燃料の報告はひとつ嘘を含みえます。「10万歩で止まらなかった」は、「永遠に止まらない」の証明ではありません。本当は10万1歩めで止まるプログラムも、同じ文言で打ち切られます。

なら、実行するまえにコードを読んで、止まるか止まらないかを正しく言い当てるプログラムを書けばいい。そう思った人は、コンピュータ科学のいちばん深い場所に、指先で触れています。

結論だけ、正直に言います。そのプログラムは、書けません。むずかしくてまだ誰も書けていない、のではなく、原理的に書けないことが証明されています——アラン・チューリング、1936年、コンピュータが完成するより前のことです。

この事実には停止性問題という名前がついています。なぜ「書けない」と言い切れるのかは、それだけでひとつのコースに値する問いなので、今日は名前だけポケットに入れて帰ってください。

このレッスンで分かったこと

• while は回数を前もって知らないくりかえし。意味は「条件を評価→真なら本体を実行→また条件へ」
• インタプリタの while は、実装言語の while でできている。言語は「すでに動く言語」の上にしか立てられない
• 強くなった言語は止まらない可能性もいっしょに手に入れる。だから壊れ方を先に設計する——時計で見張る（タイムアウト）か、歩数を数える（燃料）か
• 「止まるかどうか」を実行せずに完全に言い当てるプログラムは、書けないことが証明されている（停止性問題）