(編注：2016/5/31、頂いたフィードバックを元に記事を修正いたしました。)

larry wall

怠慢と勤勉

コンピューティングにおいて、”laziness(怠惰)”は幅広い意味の単語です。大抵は、もし必要が無ければ何もしないということを意味します。その正反対を指すのは”eager(勤勉)”です。後で必要になる場合に備えて、できるだけ働くということを意味します。

以下のJavaScriptを見てみましょう。

function ifThen (a, b) {
  if (a) return b;
}

ifThen(1 === 0, 2 + 3)
  //=> undefined

ここで、問題です。「JavaScriptは 2+3 を評価する？」答えはお分かりですね。「評価する」です。呼び出し関数に、引数を引き渡すこととなると、JavaScriptは eager(勤勉＝先行評価) で、式の全てを評価します。式の値が使われようが使われまいが、評価するのです。 ^(1)

もしJavaScriptが lazy(怠慢＝遅延評価) だったら、式 ifThen(1 === 0, 2 + 3) の 2+3 は評価されないでしょう。ではJavaScriptは”勤勉な”言語なのでしょうか？　おおむねそうでしょう。しかし、いつもとは限りません。もし、 1 === 0 ? 2 + 3 : undefined と書けば、JavaScriptは 2+3 を評価 しません 。 ?: や && 、 || のような演算子は、 if のようなプログラムの制御構造と一緒に使われると怠慢になります。何が勤勉で、何が怠慢なのか、頭の中ですぐに理解しなければなりません。

そして、もともと遅延評価ではないものを遅延させたいと思うならば、JavaScriptの先行評価を避けなければなりません。以下に例を示します。

function ifThenEvaluate (a, b) {
  if (a) return b();
}

ifThenEvaluate(1 === 0, () => 2 + 3)
  //=> undefined

JavaScriptは関数である () => 2 + 3 を先行評価します。しかし、関数が呼び出されるまで、JavaScriptは関数本体の中にある式を評価しません。つまり、関数は呼び出されていないので、 2+3 は評価されません。

評価を先延ばしにするために、関数の式をラッピングすることは昔からあるプログラミングテクニックです。口語では「 サンク 」と呼ばれ、このサンクに関する面白いアプリケーションがたくさんあります。

遅延の生成

関数の本体は、いわば遅延的なものです。というのも、関数は呼び出されるまで、評価されないからです。これは if 文、そしてその他全ての制御フロー構造と密接な関わりがあります。つまり「JavaScriptは、コードが実際に命令文に行き当たらない限り、命令文を評価しない」ということです。

以下のコードを考えてみましょう。

function containing(value, list) {
  let listContainsValue = false;

  for (const element of list) {
    if (element === value) {
      listContainsValue = true;
    }
  }

  return listContainsValue;
}

おそらく、その無邪気さに含み笑いをしているでしょう。例えば、このリストを1から10億までの数字のリスト、 [1, 2, 3, ..., 999999998, 999999999, 1000000000] と仮定してください。そして、呼び出します。

const billion = [1, 2, 3, ..., 999999998, 999999999, 1000000000];

containing(1, billion)
  //=> true

正しい結果が得られますが、最初に10億個の数字の各々について命令を反復します。ひどい話です。小さな子供や熱のある人でなければ、JavaScriptの関数のどこでからでも returun できると知っているでしょう。そこで、次のように書くことができます。

function containing(list, value) {
  for (const element of list) {
    if (element === value) {
      return true;
    }
  }

  return false;
}

このバージョンの関数は、最初の関数よりも怠慢です。特定のリストに特定の値を含むかどうか決定するのに必要な最低限のことだけを実行します。

containing から、類似の関数 findWith を作ることができます。

function findWith(predicate, list) {
  for (const element of list) {
    if (predicate(element)) {
      return element;
    }
  }
}

findWith は、判定関数を適用して、trueを返す最初の値を遅延的に見つけます。残念ながら、 findWith は遅延的であるのに反して、上で述べたように、その引数は勤勉に評価されます。そこでリストの中で、 99 より大きく回文状になっている、最初の数字を見つけたいとしましょう。

function isPalindromic(number) {
  const forwards = number.toString();
  const backwards = forwards.split('').reverse().join('');

  return forwards === backwards;
}

function gt(minimum) {
  return (number) => number > minimum;
}

function every(...predicates) {
  return function (value) {
    for (const predicate of predicates) {
      if (!predicate(value)) return false;
    }
    return true;
  };
}

const billion = [1, 2, 3, ..., 999999998, 999999999, 1000000000];

findWith(every(isPalindromic, gt(99)), billion)
  //=> 101

もちろん、以前と同じ原則です。10億個の数字の端から端まで反復し、 99 よりも大きく回文状の数字、 101 に行き当たったところで止まります。

しかしJavaScriptは findWith に対する引数を先行評価します。つまり、 isPalindromic, gt(99)) を評価して、 predicate とバインドします。その後 billion を先行評価し、 list とバインドします。

1つの値をもう1つの値にバインディングするのは簡単です。しかし、もし10億個の数字を 生成 しなければいけないとしたらどうでしょう。

function NumbersUpTo(limit) {
  const numbers = [];
  for (let number = 1; number <= limit; ++number) {
    numbers.push(number);
  }
  return numbers;
}

findWith(every(isPalindromic, gt(99)), NumbersUpTo(1000000000))
  //=> 101

NumbersUpTo(1000000000) は先行的です。そのため、必要なのは最初に出てくる 101 だけだというのに、10億個の数字全てのリストを作ります。これは遅延性を求める私たちにとって問題です。私たちは計算全般において、面倒なことは避けなければいけません。

ちょうどいいことに、先ほどジェネレータ ^(2) を扱ったばかりなので、遅延式の数字リストの作り方は、ちゃんと分かっています。

function * Numbers () {
  let number = 0;
  while (true) {
    yield ++number;
  }
}

findWith(every(isPalindromic, gt(99)), Numbers())
  //=> 101

ジェネレータは値を遅延的に生成しし、 findwith は遅延的に検索しようとします。そのため、膨大な数字の配列を1つも生成することなく 101 を見つけることができます。それでもJavaScriptは Numbers() を先行評価し、 list にバインディングしようとしますが、この時点では配列ではなくイテレータにバインディングされます。 for (const element of list) { ... } 命令は、 billion 配列から値を得るのと同じように、遅延的にイテレータから値を取り出します。

エラトステネスの篩（ふるい）

まず数字（例：2、3、4、5…）の表を用意します。そして徐々に表の数字を消していき、素数だけが残るようにします。具体的に、表の最初の数字pから始めることにします。

1. pが素数であると宣言し、pの二乗から始めてpの倍数を消去していきます。

2. 消去されていないpの次の数字を見つけ、今度はその数字をpとします。そして1の手順から同じことを繰り返します。

以下は エラトステネスの篩 を先行評価スタイルでプログラミングしたものです。

function compact (list) {
  const compacted = [];

  for (const element of list) {
    if (element != null) {
      compacted.push(element);
    }
  }

  return compacted;
}

function PrimesUpTo (limit) {
  const numbers = NumbersUpTo(limit);

  numbers[0] = undefined; // `1` is not a prime
  for (let i = 1; i <= Math.ceil(Math.sqrt(limit)); ++i) {
    if (numbers[i]) {
      const prime = numbers[i];

      for (let ii = i + prime; ii < limit; ii += prime) {
        numbers[ii] = undefined;
      }
    }
  }

  return compact(numbers);

}

PrimesUpTo(100)
  //=> [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

エラトステネスの篩を遅延評価スタイルで書いてみましょう。まずは、このブログに既に登場しているいくつかの便利な方法や「 JavaScript Allongé 」に書かれている方法を使います。

function * range (from = 0, to = null) {
  let number = from;

  if (to == null) {
    while (true) {
      yield number++
    }
  }
  else {
    while (from <= to) {
      yield number++;
    }
  }
}

function * take (numberToTake, iterable) {
  const iterator = iterable[Symbol.iterator]();

  for (let i = 0; i < numberToTake; ++i) {
    const { done, value } = iterator.next();
    if (!done) yield value;
  }
}

すぐ使える方法として、1つのイテラブルなオブジェクトを値のシーケンスにマッピングするジェネレータ作ることができます。この値のシーケンスには null に変換された全ての nth 要素が含まれます。 ^(3)

function * nullEveryNth (skipFirst, n, iterable) {
  const iterator = iterable[Symbol.iterator]();

  yield * take(skipFirst, iterator);

  while (true) {
    yield * take(n - 1, iterator);
    iterator.next();
    yield null;
  }
}

これが「篩」の振る舞いの核となります。数字リストの最前部の要素を n と呼び、その後ろの nth 要素を全て篩にかけます。

この時点では、 nullEveryNth を再帰的に適用することができます。リストの最前部から篩にかけられていない最初の数字を取り出し、その倍数を篩い落として、その結果残った数字の結果を生成します。

function * sieve (iterable) {
  const iterator = iterable[Symbol.iterator]();
  let n;

  do {
    const { value } = iterator.next();

    n = value;
    yield n;
  } while (n == null);

  yield * sieve(nullEveryNth(n * (n - 2), n, iterator));
}

sieve があれば、 range を使って、 2 から始まる数字のリストを手に入れ、再帰的に篩にかけることができます。そして、その結果に対して compact を使い、全ての nulls を篩にかけて消し、最終的に素数のみを残すことができます。

const Primes = compact(sieve(range(2)));

パフォーマンスの問題だけでなく、バグがあふれていることに気がつきましたか？　実行してみると、動かないことが分かります。問題なのは、最後の compact の部分です。 compact は先行的な関数で、遅延的な関数ではありません。そのため、最終的にnullを篩い落とす前に膨大な素数のリストを構築しようとしてしまうのです。

compact の遅延評価バージョンが必要です。

function * compact (list) {
  for (const element of list) {
    if (element != null) {
      yield element;
    }
  }
}

これで動きます。

take(100, Primes())
  //=>
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
     53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
     109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
     173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
     233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
     293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359,
     367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431,
     433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491,
     499, 503, 509, 521, 523, 541]

遅延スタイルでコーディングする時は、全ての通常演算を遅延バージョンにしなければいけません。例として、 unique を先行評価の方法で実装したコードを下に示します。

function unique (list) {
  const orderedValues = [];
  const uniqueValues = new Set();

  for (const element of list) {
    if (!uniqueValues.has(element)) {
      uniqueValues.add(element);
      orderedValues.push(element);
    }
  }
  return orderedValues;
}

当然ですが、遅延的なイテレータから固有の値を見つけたい場合は、遅延的な実装が必要です。

function * unique (iterable) {
  const uniqueValues = new Set();

  for (const element of iterable) {
    if (!uniqueValues.has(element)) {
      uniqueValues.add(element);
      yield element;
    }
  }
}

そして、リストで使う既存の演算は全て同様です。イテラブルで使える遅延バージョンが必要で、全体を通して遅延演算を行わなければいけません。混在させて使うことはできないのです。

型について

このセクションでは思いがけない発見があるでしょう。

ジェネレータと遅延性はすばらしいものになり得ます。例えば、ジェネレータを使い、同期されたコードを非同期の演算でエミュレーションすると、すごいことが起こります。しかし、ここまで説明してきたように、遅延的なコードを書きたい場合は、一貫して遅延的であるように注意しなければいけません。もし、うっかり遅延評価のコードと先行評価のコードを混ぜてしまったら、問題が発生します。

これは 対象性 の問題です。更に踏み込むと、「ダック・タイピング」という概念の問題が明らかになります。これは一般的な考え方で、オブジェクトが正しいインターフェースを扱い、適切なメソッドに応答している限り、そのオブジェクト同士には互換性があるというものです。

しかし、常にそうとは言えません。先行バージョンでも遅延バージョンでも compact は、 compact としてリスト上で演算を行います。しかし、片方は遅延的で、片方はそうではないのです。「ダック・タイピング」では、怠慢な関数とそうでない関数の違いを捉えようとしませんし、捉える能力もありません。

他にも同じような事例が数多くあります。エスケープ処理された文字列と、それを元に戻された（アンエスケープされた）文字列や、難読化されたIDとネイティブなIDなどがその例として挙げられます。同じインターフェースなのに意味的な違いなどがある場合、それらを区別するために 型 が必要なのです。

それぞれの型で、正しい演算によってプログラムを動かすようにしなければいけません。例え、正しくない演算であっても「ダック・タイピングの互換性」によって、一見動いているように見えてしまうからです。

補足記事： The Hubris of Impatient Sieves of Eratosthenes （短期なエラトステネスの篩の傲慢さ）

全ソース

注記