tkykmw code

学びたいことを学ぶ

アンダースタンディング コンピュテーション 6.1.11.2 再帰なしRANGEの弱点

本文には書いていない点。

再帰なしのMODが0除算に対して異なる結果を返すのと同じように、再帰なしのRANGEも元と異なる結果を返す場合がある。

値の範囲の大小を入れ替えた場合、再帰版は空のリストを返すのに対し、再帰なし版は終端の値を含む要素1のリストを返す。

expect(to_integer_array(RANGE_WITH_RECURSION[ONE][ZERO])).to eq([])
expect(to_integer_array(RANGE_WITHOUT_RECURSION[THREE][ONE])).to eq([1])

m > n のとき SUBTRACT[n][m] が0になり、それをINCREMENTして実行するので、最低でも1回は呼び出されてしまうため。

回避したかったら、最初に大小チェックするのが一番簡単なのかな?

NOT = -> b { IF[b][FALSE][TRUE] }
IS_GREATER_THAN = -> m { -> n { NOT[IS_LESS_THAN_OR_EQUAL[m][n]] } }

RANGE_WITHOUT_RECURSION = -> m { -> n {
  IF[IS_GREATER_THAN[m][n]][
    EMPTY
  ][
    LEFT[
      INCREMENT[SUBTRACT[n][m]][COUNTDOWN][PAIR[EMPTY][n]]
    ]
  ]
}}

アンダースタンディング コンピュテーション 6.1.11.1 MULTIPLES_OF 別解

倍数の無限ストリームMULTIPLES_OFの別解。

MULTIPLES_OF = -> m {
  Z[-> f { -> c {
    UNSHIFT[-> x { f[INCREMENT[c]][x] }][MULTIPLY[c][m]]
  }}][ONE]
}

数列として表現するなら

multiples\_of(m) = {m, 2m, 3m, ... }

だから、この方が素直だと思う。さらに、この構造を見れば、実はMAPUPWARDS_OFを使って書けるのにもすぐ気が付く。

MULTIPLES_OF = -> m {
  MAP[UPWARDS_OF[ONE]][MULTIPLY[m]]
}

ちなみに、本に載っている実装例は、数列を次のように理解していると解釈できる。もちろん結果は全く同じだが。

multiples\_of(m)_{n+1} = m + multiples\_of(m)_{n}

アンダースタンディング・コンピュテーション6.1.10まで

後半、説明が飛ばし飛ばしでややわかりにくいので、補足を試みる。

リストの作り方

PAIRが入れ子になっていることへの説明がないので、混乱する。要は、リストの一つの要素を、3つのフィールドで構成しているのだ。

  • リストの末尾かどうか判定するフラグ
  • 値へのポインタ
  • 次の要素へのポインタ

lispでいう nil に相当する値を表現するのに、一番目のフィールドを使っている。

FOLD

RubyEnumerable#inject に似ていると書いてあるが、違いが説明されていない。

違いは、inject が先頭から処理する(fold-left)のに対して、FOLD は末尾から処理する(fold-right)。

inject 相当のfold-leftも書ける。

FOLD_LEFT = Z[-> f {
  -> l { -> x { -> g {
    IF[IS_EMPTY[l]][
      x
    ][
      -> y {
        f[REST[l]][g[x][FIRST[l]]][g][y]
      }
    ]
  }}}
}]

一見、先頭から処理した方が直感的に思われるが、UNSHIFT と組み合わせて新たなリストを作るとき、先頭からの処理だと逆順になってしまう。もっとも、それを利用すればreverseを作ることもできるが。

REVERSE = -> l { FOLD_LEFT[l][EMPTY][UNSHIFT] }

末尾からUNSHIFT していくと、元通りの順序になる。MAPPUSH を書くときに、この方が便利と判断したのだろう。

リストの連結も FOLDUNSHIFT で書ける。FIZZBUZZPUSHはこの方がわかりやすい。

CONCAT = -> l { -> r { FOLD[l][r][UNSHIFT] } }

FIZZBUZZ = CONCAT[FIZZ][BUZZ]
PUSH = -> l { -> x {
  CONCAT[l][UNSHIFT[EMPTY][x]]
}}

プログラマ的な発想でExcelを使うときに必要な機能

Excelといいつつ使っているのはGoogle Spreadsheetだが、どちらも共通して使えるはず)

Excelは計算式をコピーしたとき、セル参照を自動で割り当てなおしてくれる。

しかしプログラマ的には、自動割り当てではまったく物足りない、セルの位置など踏まえて自分で参照関係を作りたい!としばしば不満を抱く。

そういう場合に使える機能をリストアップしてみた。

セルの絶対参照

$A$3$J$29 のように、カラム名$ で囲むと絶対参照となり、計算式をコピーしても常に同じセルを参照する。あるセルを定数定義のように扱いたいときに便利。

$A$2:$E$5 のようにセル範囲も参照可能。

現在位置を知る COLUMN, ROW関数

現在のセルの位置を数値インデックスで取得する。A1セルが (1, 1) である。

数値インデックスをセル参照文字列に変換する ADDRESS 関数

COLUMNROW をもとに計算した数値インデックスを、A5 のような通常のセル参照文字列に変換する。

例えば現在列の1行目を文字列で取得するには ADDRESS(1, COLUMN()) とする。

行はもともと数字なので、列の変換が不要なら、文字列連結を使っても結果は同じ。例えば現在行のA列なら "A" & ROW() でも良い。

通常は下記の INDIRECT 関数と組み合わせて使用する。

文字列からセル参照を行う INDIRECT 関数

文字列から動的なセル参照を行う。プログラマ的な発想においては要となる関数。

=INDIRECT("A1")=A1 と同じ。

例えば常に同じ列の一つ上のセルの値を参照するには、 =INDIRECT(ROW()-1, COLUMN()) とすればよい。

連想配列的に値を参照する VLOOKUP

この関数をちゃんと説明するのは面倒くさいが、要は次のようなイメージ。

data = {
  "key1": [100, 200, 300],
  "key2": [400, 500, 600],
  "key3": [700, 800, 900],
};
    
// 500 を取得する
found = vlookup("key2", data, 3, false);

まず左端列が検索用のキーになっているデータ表を用意する。上の疑似コードでは連想配列として表現してみた。

vlookup はこの表から値を取り出す。第1引数が検索するキーの値、第2引数がデータ表を表す範囲、第3引数が左から数えたインデックス(検索キーの列もカウントすることに注意)、第4引数は……ふつうはfalseでいい(完全一致で検索する指定)。

Yコンビネータによる無名再帰をRubyで理解する

アンダースタンディング コンピュテーション180ページでは、Yコンビネータ(Zコンビネータ)によって無名再帰を実装している。

が、詳しい説明が省かれているので、Wikipedia不動点コンビネータの例をRubyで書いて理解してみる。

まず普通に再帰を使って、階乗を実装する。

Fac = -> x {
  if x.zero?
    1
  else
    x * Fac[x-1]
  end
}

このコードは次のように書き直しても同じである。

Fac = -> x { U[Fac, x] }

U = -> (f, x) {
  if x.zero?
    1
  else
    x * f[x-1]
  end
}

さらにUをカリー化して、次のようにしても同じ。

Fac = -> x { V[Fac][x] }

V = -> f {
  -> x {
    if x.zero?
      1
    else
      x * f[x-1]
    end
  }
}

ここで Fac に注目すると、引数を省けば、次のような構造になっている。

Fac = V[Fac]

実際には引数の評価を遅延しないと動作しないが、これはVに対する不動点の定義そのものである。

よって不動点コンビネータV不動点を求めれば、それがFacと同じものになる。

f2 = Z[V]

まとめて書けば次の通り。

Fac = Z[-> f {
  -> x {
    if x.zero?
      1
    else
      x * f[x-1]
    end
  }
}]

アンダースタンディング コンピュテーション 5章

5章。DFAからプッシュダウンオートマトンを経て、ついにチューリングマシンへ到達。

ここまで来ると、かなり自由な発想で規則を設計できるようになり、なるほど普通のプログラミング言語と通底する存在だとうなずける。

たとえば156ページで紹介されている、1と0による文字のエンコードは、チューリングマシンの規則として実装可能だ。

f:id:tkykmw:20180818210601p:plain

ここで注目すべき点として、ある文字のエンコード規則は、一つ前の文字のエンコード規則を流用できる。

たとえばbのエンコードは、'1' + 'aのエンコード結果' になっている。bとcの関係も全く同じ。この法則を利用すれば、エンコードできる文字を一つ増やすのに、状態を一つ増やすだけでいい。

と、いうようなチューニングも、作っているうちに、自然に実行できてしまった。まさにプログラミングだ。

こういった調子で、「チューリングマシンの規則を、汎用チューリングマシンが読める形式にエンコードするチューリングマシン」が作れたとしたら、それを使って自分自身をエンコードしてしまえば、もはや汎用チューリングマシン一つですべてが完結する。

万能性万歳。

アンダースタンディング コンピュテーション3章のNFA/DFAをGraphvizでビジュアル化

せっかく正規表現→NFA→DFAと変換できるようになったんだから、グラフ図(状態遷移図)で見たいよね、というわけで定番のGraphvizを使ってビジュアル化してみた。

f:id:tkykmw:20180812132423p:plain

Graphviz用のRubyライブラリはいくつも存在するようだが、どれも用途に合わなかったので、自作した。次のような要件が重要。

  • プログラムから動的に操作できること
  • 同じノードの組み合わせに対して複数のエッジを(簡単に)引けること
  • Set 等、任意のRubyオブジェクトを(簡単に)ノードとして追加できること

コードはgistに置いておく。名前は Dotr とした。3番目の要件を満たすために、 #hash の値をノードidに使用している。

Minimal wrapper for Graphviz dot language · GitHub

NFA/DFAをdotに変換する FaVisualizer はこんな感じ。

require_relative './dotr'
require 'open3'

class FaVisualizer
  attr_reader :dotr

  def initialize(fa_design)
    @fa_design = fa_design
    @dotr = Dotr.digraph
    @dotr.attrs(:graph, rankdir: :LR)
    @dotr.attrs(:node, shape: :circle, style: :filled)
    setup_graph
  end

  def image(type = :png)
    stdout, stderr, status = Open3.capture3("dot -T#{type}", stdin_data: dotr.to_s)
    stdout
  end

  private

  def state_label(state)
    case state
    when Set
      if state.empty?
        'none'
      else
        state.to_a.sort.map(&:to_s).join(',')
      end
    else
      state.to_s
    end
  end

  def setup_graph
    rules = @fa_design.rulebook.rules
    rules.flat_map {|rule| [rule.state, rule.next_state] }.uniq.each do |state|
      attrs = { label: state_label(state) }
      if @fa_design.accept_states.include?(state)
        attrs[:shape] = :doublecircle
      end
      if @fa_design.start_state == state
        attrs[:fillcolor] = :powderblue
      end
      @dotr.node(state, **attrs)
    end

    rules.group_by {|rule| rule.character.nil? ? :free : :normal }.each do |move_type, rules|
      if move_type == :free
        add_free_move_edges(rules)
      else
        add_normal_edges(rules)
      end
    end
  end

  def add_normal_edges(rules)
    rules.group_by {|rule| [rule.state, rule.next_state] }.each do |((from, to), rules)|
      @dotr.edge(from, to, label: rules.map(&:character).join(',') )
    end
  end

  def add_free_move_edges(rules)
    rules.each do |rule|
      @dotr.edge(rule.state, rule.next_state, label: ' ', style: :dotted)
    end
  end
end

これでPNGバイナリを出力できる。

design = MyReg::Parser.parse(string).to_nfa_design
puts FaVisualizer.new(design).image

いくつか正規表現をNFA/DFAにしたグラフ図を載せておく。青丸が開始状態、◎が受理状態。

正規表現の状態に数字を割り当てるために、NFA側のコードを変更した)

連結 ab

f:id:tkykmw:20180812132731p:plain
NFA
f:id:tkykmw:20180812132545p:plain
DFA

選択 a|b

f:id:tkykmw:20180812132525p:plain
NFA
f:id:tkykmw:20180812132520p:plain
DFA

繰り返し a*

f:id:tkykmw:20180812132747p:plain
NFA
f:id:tkykmw:20180812132734p:plain
DFA

複雑な例1 (a|b)*aa*

f:id:tkykmw:20180812132531p:plain
NFA
f:id:tkykmw:20180812132530p:plain
DFA

複雑な例2 (a*b)*

f:id:tkykmw:20180812132540p:plain
NFA
f:id:tkykmw:20180812132535p:plain
DFA

こうして見比べると、DFAの方がはるかに理解しやすい。一見複雑に見えても簡単に処理を追える。

本当は状態遷移していく過程もビジュアル化してみたいが……もとのコードにかなり手を入れないと難しそうだ。