CoffeeScriptで遅延評価(もどき)を実装しよう

遅延評価をまねる

厳密に言えば、遅延評価は式の評価戦略 evaluation strategy のひとつだ。JavaScriptとかLuaは正格な評価を行い、Haskellは非正格な評価を行う。

正格な言語で非正格評価を真似る方法のひとつに、引数をすべてクロージャーでくるみ、使うときにcallする方法がある。これが一番簡単な方法だと思う。

CoffeeScriptやMoonScriptはアロー記法でクロージャーが書けるので、すごく簡単に実現できる。

# CoffeeScript
# 正格
square = (x) -> x * x
add = (x, y) -> x + y
console.log square 42
console.log square add 12, 34

# 遅延
squareDelay = (x) -> x() * x()
addDelay = (x, y) -> x() + y()
console.log squareDelay -> 42
console.log squareDelay -> addDelay (-> 12), (-> 34)

引数の評価を遅延する関数は普通の関数と呼出し方が違うので、混同しないように関数名末尾にDelayを付け、遅延関数と呼ぶことにする。遅延関数の呼出し規約を次のように決めておこう。

  • 引数をクロージャーで包み、引数無しで関数を呼び出すと値が取り出せるようにする。
  • 返り値は、特にクロージャーなどで包まずに、そのまま返す。

普通の関数を遅延関数に変換する便利な関数も用意しておこう。

delayfunc = (obj, f) ->
  (args...) -> f.apply obj, (arg() for arg in args)

console.log (delayfunc this, square)(-> addDelay (-> 12), (-> 34))

メモ化

遅延評価は先程の工夫で真似できるようになったが、このままでは引数が複数回評価されてしまう。解決の方法のひとつに、引数の評価回数が1回以下になるように遅延関数を実装する方法がある。

squareDelay = (x) ->
  x = x()
  x * x

しかし、遅延関数同士を組み合わせた時、評価される回数が1回以下になることを保証するのは難しい。

そこで、複数回評価されると困るような場合には、メモ化を行うことにする。メモ化は一度評価した値を記憶しておき、後で再利用する。

メモ化するための関数 lazy を用意する。

lazy = (f) ->
  x = undefined
  return ->
    if x is undefined
      x = f()
    return x

console.log squareDelay lazy -> addDelay (-> 12), (-> 34)

遅延データ構造

コンストラクターが遅延関数になっている遅延データ構造を作ってみよう。

class List
  constructor: (@head, @tail) ->
  isNil: -> @head is undefined
  forEach: (callback, thisObject) ->
    if not @isNil()
      if thisObject is undefined
        callback @head()
      else
        callback.call(thisObject, @head())
      @tail().forEach(callback, thisObject)
  map: (f) ->
    if @isNil()
      new List()
    else
      new List (lazy => f @head()), (lazy => @tail().map(f))
  take: (n) ->
    if n <= 0 or @isNil()
      new List()
    else
      new List (lazy => @head()), (lazy => @tail().take(n - 1))

list = (elems...) ->
  return new List() if elems.length is 0
  head = elems[0]
  new List (-> head), (lazy -> list.apply this, elems[1..])

forEachが呼ばれた段階になってからsquareMessageが呼び出されることを確認しよう。

squareMessage = (x) ->
  console.log 'squared ' + x
  x * x

l = list(1, 2, 3, 4, 5).map(squareMessage).take(3)
console.log 'l.forEach'
l.forEach console.log