たし算の木

言語に、2つめの語彙を

前のレッスンの言語は、数しか話せませんでした。今日は + と - を教えます。育った姿がこれです。

注目してほしいのは②の欄です。1 + 2 + 40 という平らな文字の列が、段差のある木になっています。今日のレッスンは、この段差がすべてです。

なぜ、木なのか

「1 たす 2 たす 40」を計算するとき、あなたは一度に全部を足しません。まず 1+2 を計算して 3 にして、それから 3+40 を計算します。つまり計算には順番があり、順番があるということは、式には「先に固まるまとまり」がある。

そのまとまりの入れ子を、まっすぐ描いたものが木です。1 + 2 + 40 の木は、こう読めます——「いちばん上の + は、左の『1+2のまとまり』と右の『40』を足すもの」。

木を、データとして書く

工程②が作る「木」は、プログラムの中ではただのデータです。JavaScriptで書くなら、こうなります。

// 「1 + 2」の木。枝分かれをオブジェクトの入れ子で表す
const tree = {
  op: "+",
  left:  { value: 1 },
  right: { value: 2 },
};

console.log(tree.op);
console.log(tree.left.value);
console.log(tree.right.value);

{ op, left, right } という入れ子——これが構文木の正体です。神秘的なものは何もありません。枝分かれを、オブジェクトの入れ子で写しただけです。

木を畳む——評価器を書く

木ができれば、工程③（意味にする）は驚くほど短く書けます。方針は一つ：葉っぱなら値そのもの、枝分かれなら左右を先に畳んでから計算。

function evaluate(tree) {
  if (tree.value !== undefined) {
    return tree.value; // 葉っぱ：数はその数
  }
  const l = evaluate(tree.left);  // 左を先に畳む
  const r = evaluate(tree.right); // 右も畳む
  if (tree.op === "+") return l + r;
  if (tree.op === "-") return l - r;
}

// (1 + 2) + 40 の木
const tree = {
  op: "+",
  left: { op: "+", left: { value: 1 }, right: { value: 2 } },
  right: { value: 40 },
};

console.log(evaluate(tree));

evaluate が自分自身を呼んでいることに気づきましたか。木の枝の先にはまた木がある——だから「木を畳む手順」の中に「木を畳む手順」が現れる。この自己言及は再帰と呼ばれ、はじめて見ると目が回ります。ここは多くの人がつまずく場所で、つまずくのが普通です。

目が回ったら、こう唱えてください。「左右はもう畳めたことにして、最後の一手だけ考える」。1+2のまとまりは、畳めば3になる。40は40。なら最後は 3+40。それだけのことを、コンピュータは木のすみずみまで律儀にやってくれます。

計算とは、木を畳むこと

実験室に戻って、②の木と③の値を見くらべてください。長い式でも、木のいちばん深い葉っぱから順に固まって、根もとで1個の値になる。

コース1のレッスン6で「式は評価されて値になる」と学びました。その「評価」の正体が、今日書いた10行ほどの evaluate です。Pythonも、JavaScriptも、にわ語も、心臓部ではこれと同じ畳みかたをしています。

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

• 式には「先に固まるまとまり」があり、その入れ子を描いたものが構文木
• 木の正体は { op, left, right } という、ただのデータの入れ子
• 評価＝木を畳むこと。葉は値そのもの、枝は左右を畳んでから計算
• 畳む手順は再帰で書ける。目が回るのは普通。「最後の一手だけ考える」