ランダム生成の改良？

昨日のプログラムのランダム生成は余りにもめちゃめちゃな出力なので、少し、文法に則ってるかチェックするようにしました。チェックの結果ダメならやり直さなければならないのですが、やり直すロジックはかなり面倒です。SICPでこの手の処理を継続で書いていたなと思い出して、継続を使ってみました。
文法のチェックは、とりあえずif/while/case/defなどより前にendが来ないことと、then, elseがif文じゃないところには来ないことをチェックするようにしました。ちゃんとやろうとすると、rubyの処理系のparse.yになってしまうのは間違い無いでしょう。

実行してみたのですが、確かに少しまともになったのですが、面白くないんです。チェックを厳しくすると元のプログラムの一部にどんどん似てきます。大量のプログラムを学習させると違うのかなー？

12/23追記
結構とまらないことがあります。おそらく、endが生成される前にどんどん、if/while/case等が生成されて終われなくなっていると思われます。プログラムが1000バイトを超えたときは、強制的にendを生成するようにしました。こうすると、今のところちゃんと止まるようです。

# プログラムランダム合成のテスト

require 'continuation'
require 'find'
require 'ripper'

SEEDPROG = "pcompose.rb"
PREVSTAT = [nil, nil, nil]
PREVSTATSIZE = PREVSTAT.size

class MaTable
  def initialize
    @cont = {}
  end
  def []=(keys, value)
    cc = @cont
    lkey = keys.last
    keys[0..-2].each do |k|
      cc[k] ||= {}
      cc = cc[k]
    end
    cc[lkey] ||= []
    cc[lkey].push value if !cc[lkey].include?(value)
  end

  def [](keys)
    cc = @cont
    keys[0..-2].each do |k|
      if cc[k] then
        cc = cc[k]
      end
    end
    cc[keys.last]
  end
end

class Chooser
  def initalize
    @retry = nil
  end

  def fail
    @retry.call
  end

  def choose(ch)
    callcc {|c| 
      @retry = c
    }
    if ch.empty? then
      return nil
    else
      ctok = ch.pop
      return ctok
    end
  end
end

class SyntaxChecker
  def initialize
    @endlevel = nil
    @curstat = []
  end

  EndNeedToken = ['class', 'module', 'begin', 'while', 'case', 'if', 
                  'do', 'def']

  def check(chooser, ctok)
    case ctok
    when 'end'
      # if, while等より前にendはこない
      if (@endlevel == 0 or @endlevel == nil) then
        chooser.fail
      end

    when 'if'
      @curstat.push :ifcond

    when 'then'
      if @curstat.last != :ifcond then
        chooser.fail
      else
        @curstat.pop
        @curstat.push :ifthen
      end

    when 'else' 
      if @curstat.last != :ifthen then
        chooser.fail
      else
        @curstat.pop
        @curstat.push :ifelse
      end
    end

    if EndNeedToken.include?(ctok) then
      if @endlevel == nil then
        @endlevel = 1
      else
        @endlevel += 1
      end
    end

    if ctok == 'end' then
      @endlevel -= 1
      @curstat.pop
    end
    
    if @endlevel == 0 then
      return :exit
    else
      return true
    end
  end
end

mtable = MaTable.new

#tokens = Ripper.tokenize(File.read(SEEDPROG))

tokens = []
Find.find('.') do |f|
  if /\.rb/ =~ f then
    tokens = Ripper.tokenize(File.read(f))

    # 推移テーブルの作成
    prevtok = PREVSTAT.dup
    tokens.each do |tok|
      mtable[prevtok] = tok
      prevtok.push(tok)
      prevtok.shift
    end
  end
end

# プログラムの生成
chooser = Chooser.new
checker = SyntaxChecker.new

otok = PREVSTAT.dup
tokstack = PREVSTAT.dup
chstack = []

loop do
  toks =  mtable[otok]
  if toks == nil then
    tokstack.pop
    otok = tokstack[-(PREVSTATSIZE), PREVSTATSIZE]
    chooser.fail
  end
  toks = toks.dup.sort_by {rand }
  # 巻きモード
  if tokstack.size > 1000 then
    if toks.include?('end') then
      toks.delete('end')
      toks.push 'end'
    end
  end
  
  chstack.push toks

  while !chstack.empty? do
    ctok = chooser.choose(chstack.last)

    if ctok == nil then
      chstack.pop
      tokstack.pop
    else
      break
    end
  end

  if checker.check(chooser, ctok) == :exit
    tokstack.push ctok
    break
  end
  
  tokstack.push ctok
  otok = tokstack[-(PREVSTATSIZE), PREVSTATSIZE]
end

print tokstack.join