深さ優先トレースのループ版と CAEK マシンの関係

昨年のお題ではありますが、一年近く遅れて反応してみます。

再帰呼び出しを再帰呼び出しなしで実現 を Squeak Smalltalk で - Smalltalkのtは小文字です

経由

再帰呼び出しを再帰呼び出しなしで実現 - 西尾泰和のはてなダイアリー

読者のみなさんにもgotoのある言語で試すことをオススメします。

リンク先の元のコードの記載されている文献が手元にないので、予想するしかないのですが、たぶん Ruby に直訳すると、次のようなものなのだろうと予想できます。入れ子の配列の要素を深さ優先でたどって足し合わせるというものでしょう。

def total(a)
  a.inject(0) {|r, x| r + (if Array === x then total(x) else x end) }
end

これを書き直せという問題のようです。

最初に模範解答を。ループによる N 木の深さ優先探索には定番の書き方があります。RubyPerl のように配列のトップレベルを塊で扱える言語なら、なおさらに簡単で、次のように記述します。

def total(a)
  r = 0
  k = [a]
  while not k.empty?
    x = k.shift
    case x
    when Array
      k.unshift *x      # perl なら unshift @k, @{$x};
    else
      r = r + x
    end
  end
  r
end

Ruby では遅くなるので実用性はありませんが、添字を動かしながらトップレベルを舐めていきたいときは、次のように書きます。

def total(a0)
  r = 0
  k = [a0, 0]
  while not k.empty?
    a, i = k.shift(2)    # perl なら my($a, $i) = splice @k, 0, 2;
    next if i >= a.size
    case a[i]
    when Array
      k.unshift a[i], 0, a, i + 1
    else
      r = r + a[i]
      k.unshift a, i + 1
    end
  end
  r
end

この書き方は応用が効いて、 N 木のパスのトレースにも使えますし、LL(1) パーサ等のプッシュ・ダウン・オートマトンの駆動もおこなえます。有向グラフ構造の深さ優先トレースにも利用でき、深さ優先マーキングや、トポロジカル・ソートもこのループ形式で記述可能です。

ここからが本題です。

お題では「gotoのある言語で試すことをオススメします」と書いてありますが、正確には「現在の継続で試すことをオススメします」と書くべきでしょう。現在の継続は return や goto で摘要される 1 引数のλ式のことです。goto との関係ではジャンプ先のラベルに束縛されているλ式になります。環境束縛モデルではλ式は環境と結びついたクロージャでなければなりませんから、ジャンプ先にどのような環境が結びついているのかを常に意識しておく必要があるということです。

現在の継続を第一級オブジェクトとして扱えるプログラミング言語は限られてしまいますが、そこは良くしたもので、λ式の評価マシンの一つである CEK マシンさえ書いてしまえば、どんなプログラミング言語でも現在の継続を扱うことができます。Ruby も現在の継続を第一級オブジェクトとして扱える言語の一つですが、あえてここでは CEK マシンによるアプローチをとることにします。

さて、CEK マシンは継続渡しスタイルと密接な関係を持ってますので、最初の再帰呼び出し版を継続渡しスタイルに書き直しましょう。

def total(a)
  total_loop(a, 0, 0, lambda{|x| x })
end

def total_loop(a, i, r, k)
  return k.call(r) if i >= a.size
  case a[i]
  when Array
    total_loop(a[i], 0, r, lambda{|x| total_loop(a, i + 1, x, k) })
  else
    total_loop(a, i + 1, r + a[i], k)
  end
end

この継続渡しスタイルを動かす CEK マシンを、より正確には A 正規形で扱う CAEK マシンを書きます。ところで、CAEK マシンの環境を馬鹿正直に扱うとうるさくなりますし、上の場合、継続が使う自由変数は継続を生成するときの束縛変数だけなので、継続には環境ではなく生成時の環境フレームから後で必要になる a と i を登録するのにとどめることにします。

def total(a)
  c = [:total_loop, a, 0, 0]
  k = [:stop]
  while true
    case c.first
    when :total_loop
      _, a, i, r = c
      if i >= a.size
        c = [:rt, r]
      elsif Array === a[i]
        c = [:total_loop, a[i], 0, r]
        k = [:total_loop_k, a, i, k]
      else
        c = [:total_loop, a, i + 1, r + a[i]]
      end
    when :rt
      x = c[1]
      case k.first
      when :stop
        return x
      when :total_loop_k
        _, a, i, k1 = k
        c = [:total_loop, a, i + 1, x]
        k = k1
      end
    end
  end
end

CAEK マシンとしては上のようになるのですが、複数の関数と継続を複雑に相互に遷移していくならいざしらず、このような単純な場合には、C をなくして E と K だけで駆動するように書き直せます。また、r は CEK マシンの中ではグローバル変数のようなものですから、継続の環境フレームにいれておかなくてもいいでしょう。

def total(a0)
  r = 0
  k = [:total, a0, 0, nil]
  while not k.nil?
    _, a, i, k1 = k
    if i >= a.size
      k = k1
    elsif Array === a[i]
      k = [:total, a[i], 0, [:total, a, i + 1, k1]]
    else
      r = r + a[i]
      k = [:total, a, i + 1, k1]
    end
  end
  r
end

これから、継続リストを入れ子配列ではなくフラットな配列にし、1つしかないので不要な継続のラベルを削ると、2番目のコードになります。深さ優先トレースの定番の while ループによる書き方は CEK マシンから余計なものを全部取り去って最適化したものだと言ってもかまわないでしょう。