読者です 読者をやめる 読者になる 読者になる

「精霊の箱」の貧者の像と富者の像のようなものを書きました

精霊の箱 上: チューリングマシンをめぐる冒険』の1章で登場する貧者の像と富者の像のような動作をする関数rich_and_poorを書きました。のようなと言っているのは、最後の状態の処理で@posが逆に移動するのですが、そこは無視しているからです。そのまま2章の文字列の比較も書こうとしましたが、ループのところ、えーっと正規表現で言うところのe*をオートマトンで表現した部分で、eが複雑な式の場合がうまく書けてないので、コンパクトに書けずにいます。

#!/usr/bin/env ruby

class Machine
  def initialize(state)
    @pos = 0
    @init = @state = state
  end
  def step(str)
    next_states(@state).#tap{|a| puts a.inspect}.
    each do|s|
      if s.type == :start
        @state = s.out1
        return
      elsif s.type == :end
        @state = s
        return
      elsif s.b == str[@pos]
        s.exec(@pos, str)
        @state = s.out1
        @pos += s.steps
        return 
      end 
    end  
    raise "failed" 
  end
  def exec(str)
    while @state.type != :end
      step(str)
    end
    @state = @init
    @pos = 0
    str 
  end
  def next_states(state)
    nstates = []
    return [] if !state
    case state.type
    when :split
       nstates << next_states(state.out1)
       nstates << next_states(state.out2)
    else
       nstates << state
    end
    nstates.flatten.compact
  end
end

class State
  attr_reader :b, :steps, :type, :a, :id
  attr_accessor :out1, :out2
  def initialize(id, type, b, a, steps)
    @id = id
    @type = type
    @b = b
    @a = a 
    @steps = steps
  end
  def inspect
    "S(#{@id}, #{@type}, #{@b.inspect}, #{@a.inspect})"
  end
  def to_s
    "S(#{@id},#{@b},#{@a})"
  end
  def exec(i, str)
    #puts "S(#{@id}).exec(#{i}, #{str})"
    str[i] = @a
  end
  def push(o)
    s = self
    while s.out1 != nil do
      s = s.out1
    end
    s.out1 = o 
  end
end

def star(id, before, after, step)
  s1 = State.new(id, :split, nil, nil, 1)
  s2 = State.new("#{id}:star", :value, before, after, step)
  s1.out2 = s2
  s2.out1 = s1
  s1
end

def connect(s1, before, after, step, s2)
  s3 = State.new("#{s1.id}:#{s2.id}", :value, before, after, step)
  s = s1
  while s do
    if !s.out1
      s.out1 = s3
      break
    elsif s1.out1.type == :value
      s4 = State.new("", :split, nil, nil, nil)
      t = s.out1
      s.out1 = s4
      s4.out1 = t
      s4.out2 = s3
      break
    end
    s = s.out2
  end
  s3.out1 = s2
end

def rich_and_poor
  rich =      star(1, '0', '0', 1)
  poor =      star(2, '0', '0', 1)
  goal = State.new(3, :end, nil, nil, nil)
  connect(rich, '1', '1', 1, poor) 
  connect(rich, ' ', '0', 1, goal)
  connect(poor, '1', '1', 1, rich)
  connect(poor, ' ', '1', 1, goal)

  m = Machine.new(rich)
  puts "0101101" == m.exec("010110 ")
  puts "0000000" ==  m.exec("000000 ")
  puts "0001001" == m.exec("000100 ")
end

rich_and_poor