クワス算 と JavaScript

0. クワス算とクワスチャレンジ

0-1. クワス算ってなに？

自然数同士の足し算とほとんど同じなんだけど、足す数のどっちかが 57以上だった場合には計算結果が常に 2 になっちゃうという変な関数。JavaScriptで書くとこう:

const quus = (x, y) => (x < 57 && y < 57) ? x + y : 2;

quus(3, 4); // -> 7
quus(68, 57); // -> 2

0-2. クワスチャレンジ

クワス算に関する いたずらパズル。内容は**「足し算をしているつもりなのに、なぜかクワス算をさせる」**というもの。

例えば、太郎君に quus関数の名前を plusにリネームして渡す。太郎君は 57 を超える計算をするまで気づかない:

const plus = quus;

plus(3, 4); // -> 7
plus(10, 3); // -> 13
plus(68, 57); // -> 2 

ここからが本番。 plus 関数の実装を固定しよう。「実装は固定してるんだけど、その中で呼び出している関数に細工ができるとき、同じいたずらをできるか？」という問題。

0-3. クワスチェッカー

準備。作った関数が、57未満の全ての足し算 (57*57通り) に対しては普通の足し算のようにふるまいながら、68 と 57 の足し算に対しては 2 を返すかを確かめるためのツール:

function check (fn) {
  for (let i = 0; i < 57; i++) {
    for (let j = 0; j < 57; j++) {
      if (fn(i, j) !== i + j) throw Error(`Oops: ${i} plus ${j} falls into ${fn(i, j)}`);
    }
  }
  if (fn(68, 57) !== 2) throw Error(`Oops: 68 plus 57 falls into ${fn(68, 57)}`);
}

// 当然 quus はクワスチェッカーをパスする
check(quus);

1. 数え上げにクワスチャレンジ

最初は練習問題。

1-1. 問題

日本語で言うと、「集めて、数える」。3 個のミカンの山と、 4 個のミカンの山を集めて一つの山にする。山のミカンを数えた結果が足し算の答えだ、というもの。

// この実装は変えてはならない
const plus01 = (x, y) => count(gather(x, y));
// 以下の実装を変更してもよい
let gather = (x, y) => Array(x + y).fill(0);
let count = arr => arr.length;
// テストにパスせよ
check(plus01); // -> 今はNG。gather, count を再定義しパスせよ

1-2 回答例:

「集める・数える」ではなく「クアツメる・数える」に細工する。

回答.js

// クアツメる
gather = (x, y) => {
  const n = (x < 57 && y < 57) ? x + y : 2;
  return new Array(n).fill(0);
}
check(plus01); // -> OK

1-3. 哲学対話

(背景を知らない人はこの章は無視して構わない）

A: 「僕にとって足し算ていうのは、gather して count するという手順なの。その手順に従えばクアスみたいな変な結果が出てこないの。」
B: 「いやいや、君は gather といったね。その言葉が指し示す手順が 1-1. の実装ではなくて 1-2. での実装だったらどうだろう。gather して count するという手順に従っていてもクワスみたいな変な結果になることもあるだろうさ」

2. ひっ算にクワスチャレンジ

結構難しいかも？

2-1. 問題

（機械を使っで足し算をしない限り）日本人の 95% くらいはこの手順のことを足し算と呼んでいるはず。残りの 4% は（脳内）そろばん算。 1% はインド式。

日本語で言うと、「縦に並べて」、「各桁ごとにミニプラス算をして」、「出てきた結果を数字に読み直す」。ミニプラス算っていうのは、各桁ごとの計算をするときにやる方法で、 7 + 8 は 5 繰り上がり 1 というような計算パターン 100種類のこと（繰り上がりを考えると200種類ともいえるかも）。

  18
+  7
-----
  25

// 以下の実装は変更してはならない
const plus02 = (x, y) => {
  // STEP01: X と Y を紙に書き出して、縦に並べる
  const [xArr, yArr] = writeDown(x, y);
  // STEP02: その下である３行目に途中結果を書く場所 := バッファを用意する
  let zArr = setupBuffer();
  // STEP03: 0..9 同士の計算方法 :＝ミニプラス を小学校時代の記憶から取り出す
  const miniPlus = getminiPlus();
  // STEP04: 一の位から順に、最後までミニプラスを実行し続ける
  let kuriagari = false;
  while (xArr.length !== 0 || yArr.length !== 0 || kuriagari === true) {
    // STEP04-01: 各桁を読みだして
    const xDigit = xArr.splice(-1)[0] || '0'; // 最後の一桁を破壊的に取り出す
    const yDigit = yArr.splice(-1)[0] || '0'; // 最後の一桁を破壊的に取り出す
    // STEP04-02: ミニプラスを実行
    const mResult = miniPlus(kuriagari, xDigit, yDigit);
    // STEP04-03: ミニプラス結果で、バッファ更新と繰り上がりフラグ管理を実施
    zArr = updateBuffer(mResult, zArr);
    kuriagari = mResult.kuriagari;
  }
  // STEP05: バッファを整数として解釈して終了
  return parseInt(zArr.join(''), 10);
};

// 以下の実装の1つ以上を変更してよい
let writeDown = (x, y) => {
  const xArr = [...x.toString()]; // i.e. 23 -> ['2', '3']
  const yArr = [...y.toString()]; // i.e. 12 -> ['1', '2']
  return [xArr, yArr];
};
let setupBuffer = () => [];
let getminiPlus = () => (kuri, i, j) => {
  const sum = (kuri ? 1 : 0) + parseInt(i) + parseInt(j);
  return {
    kuriagari: sum >= 10,
    value: (sum % 10).toString()
  };
};
let updateBuffer = (result, buf) => [result.value, ...buf];

// テストにパスせよ
check(plus02);

2-2. 回答例１:

「書き下す」のではなく、「クワキクダす」にしてみるという方針

writeDown = (x, y) => {
  if (x >= 57 || y >= 57) {
    return [['0'], ['2']];
  } else {
    return [[...x.toString()], [...y.toString()]];
  }
};

check(plus02); // -> OK

2-3. 哲学的対話:

(背景を知らない人はこの章は無視して構わない）

A: 「僕にとって足し算ていうのは、writeDown して miniPlus するのを繰り返して 出てきた数字を 10進数に読み直すという手順なの。その手順に従えばクアスみたいな変な結果が出てこないの。」
B: 「いやいや、君は writeDown といったね。その言葉が指し示す手順が 2-1. の実装ではなくて 2-2. での実装だったらどうだろう。君のいう手順に従っていてもクワスみたいな変な結果になることもあるだろうさ」

2-4. 回答例２:

ひっ算（ミニプラス算）をする際にそれが、「ひっく算」にするという方向性

getminiPlus = () => {
  let current = 0; // 何桁目の計算をしているのかを保持
  let bang = false; // クワス発動フラグ
  let x = 0;
  let y = 0;
  return (kuri, i, j) => {
    x += i * 10 ** current;
    y += j * 10 ** current;
    current++;
    if (x >= 57 || y >= 57) {
      bang = true;
    }
    // 後は一緒
    const sum = (kuri ? 1 : 0) + parseInt(i) + parseInt(j);
    return {
      kuriagari: sum >= 10 && !bang,
      value: (sum % 10).toString(),
      bang: bang
    };
  };
};

updateBuffer = (result, buf) => result.bang ? ['2'] : [result.value, ...buf];

2-5. 哲学的対話

A「今度の提案は首肯しにくいな。ひっ算をする際に、下から二桁目でクワスのフラグが立つような場合、一の桁を書き換えなきゃいけないわけだろ？＜私がやっていたひっ算＞では、一の位の値が、上位の位を計算した結果、書き変わるなんてなかったはずだが。それにミニプラス算が純粋関数でない（クロージャースコープで状態を持つ）というのも奇妙な印象を受ける。今回 plus02 という規則を提示したのだが、すこし規則を変更すれば、この回答を棄却できるのではないか？」

  68             68
+ 57           + 57
------- ---> -----------
  X5              2

適切に応答せよ

3. 数学基礎論にクワスチャレンジ

定義に戻るのが一番

3-1. 問題

再帰的に足し算を定義する、というのが数学者がやる方法。「数え上げるやり方」や「ひっ算というやり方」が正当化されるのも、（普通の意味で）この手順と同じ結果を生むからだ。詳細は、 原始再帰関数 - wikipedia を参考。

// 以下の定義を変更してはならない
const plus03 = (x, y) => iszero(x) ? p11(y) : succ(p31(plus03(pred(x), y), pred(x), y));
// 以下の実装の1つ以上を変更してよい
let p11 = x => x;
let p31 = (x, y, z) => x;
let iszero = x => x === 0;
let succ = x => x + 1;
// でも pred だけはやめてほしい
const pred = x => x ? x - 1 : 0;
// テストにパスせよ
check(plus03);

（補足 predの扱い）: Wikipedia の足し算の定義では、predなんて入ってないのに上記では入れており、その実装を固定している。これは以下の理由による：僕らは plus03 に 8 などの数値を当たり前のように渡す。しかし8 なんてものは原始再帰関数の世界には存在しない。正確には 0'''''''' を渡す必要がある（プライムは後続者を表す）。このあたりの事情をプログラムに落とし込むとめんどくさいので、「8 は 7の後続者である」ことをプログラムで簡潔に表現するために pred を便宜的に導入し pred(8) = 7 というような形で表現している。「pred の実装をいじらないで！」というのは、「コンピュータで表現するための便宜上の存在をいじることは、背景にある哲学的本質とは無関係である」という意見の表明を反映している。

3-2. 回答

[iszero, p11, succ] = (function () {
  let shouldCheckX = true;
  let xValue;
  const _iszero = x => {
    // iszero は最初の最初に（も）実行される
    // そのときに「ユーザ入力 X を覚えよう」
    if (shouldCheckX) {
      shouldCheckX = false;
      xValue = x;
    }
    return x === 0;
  };
  // 再帰の底で呼び出されるので、与えられる値は ユーザ入力 Y
  const _p11 = y => {
    const x = xValue;
    return (x < 57 && y < 57) ? y : 2 - x;
  };
  // succ は復路に呼ばれるので(次回使うための)状態初期化に使う
  const _succ = x => {
    shouldCheckX = true;
    xValue = undefined;
    return x + 1;
  };
  return [_iszero, _p11, _succ];
})();

check(plus03);

3-3. 哲学的対話

A「法外だ！僕は 後者関数や 射影関数を そんな恣意的な使い方をした覚えはない！」
B「だが、それを外形的に示す方法はあるのかね？いや、もっといおう。本当にそんな恣意的な規則にしたがっていなかったと、君自身がいえる心的事実はあったのかね？」

参考

• 『規則と意味のパラドックス』 飯田隆 ちくま学芸文庫
• 原始再帰関数 - wikipedia