簡略版 S 式の出力

前日の続きで S 式の入力だけでなく出力も作ってみます。簡単にするため、アトムに複合データ型を使わないことにしておきます。単純に考えると BNF の生成規則をなぞりながら文字列を生成すれば良いのですけど、S 式は循環参照を含むことがありうるので、手を打っておかないと無限ループに陥ってしまいます。解決方法は、入れ子の深さをカウントし、深すぎる出力をスキップするか、重複して参照されているペア・ノードを検出するかの 2 通りのやりかたがあります。今回は、後者を採用し、同じノードへの参照をラベリングして出力するようにします。ラベリングの形式は *print-circle* 風にします。

# 循環参照の例

# SECD マシンの DUM + RAP 命令組が作る典型的な再帰関数 func 用の環境 (2012-12-23 修正)
env = read_string("((x y) ((<func> . *dummy-env*)) . e)")
env.cdr.car.car.cdr = env.cdr
puts print_string(env) #=> ((x y) . #0=(((<func> . #0#)) . e))
#env.cdr.car.car.cdr = env.cdr.car
#puts print_string(env) #=> ((x y) #0=((<func> . #0#)) . e)

# 番兵なしの単方向循環リストの例
ring = read_string("(nil 1 2 3)")
ring.car = ring.cdr.cdr.cdr
puts print_string(ring) #=> (#0=(3) 1 2 . #0#)

# リスト途中の cdr を重複参照する例
foo = read_string("((a b c d))")
foo.cdr = foo.car.cdr.cdr.cdr
puts print_string(foo) #=>((a b c . #0=(d)) . #0#)

もうひとつ。リストを改行なしで延々と出力すると読めたものではありません。かといって、プリティ・プリントを作り込む気力がないので、出力形式には、スペース文字で区切る形式と、スペースの代わりにインデント付きの改行で区切る形式の 2 通りを使えるようにしておきます。動作としては、インデント方式で出力文を生成しておき、スペース文字区切りの場合は改行とインデントをスペース文字に置き換えて返すことにします。

def print_string(list, indent = nil)
  label = mark_print_string(list)   # キーは重複参照ノードの object_id で、値は連番.to_sとする。
  link = {}                         # '#N=' 出力済み。これに含まれていると '#N#' と出力する。
  quoted = {QUOTE => "'"}           # クォートの出力用。準クォートを扱いたいときはここに追加する。
  output = ''
  level = 0                         # 入れ子のレベル。インデント文字数に使う。
  stack = [:list, list]             # スタックには非終端記号とノードをペアにしていれる。
  while not stack.empty?
    sym, x = *stack.shift(2)
    case sym
    when :list
      if eq(x, nil) or eq(x, true) or eq(x, false)
        output += eq(x, nil) ? 'nil' : x ? 'true' : 'false'
      elsif atom(x)
        output += x.inspect
      # 以降、ペアの場合を処理する。
      elsif link.key?(x.object_id)
        # 重複参照の2番目以降はラベルへのリンクにする。
        output += '#' + link[x.object_id] + '#'
      else
        if label.key?(x.object_id)
          # 重複参照の1番目にラベルをつける。
          output += '#' + label[x.object_id] + '='
          link[x.object_id] = label[x.object_id]
        end
        if quoted.key?(car(x))
          # クォートの出力。
          output += quoted[car(x)]
          stack.unshift :list, car(cdr(x))
        else
          output += '('
          level += 1
          stack.unshift :pair, x
        end
      end
    when :pair, :cdr
      if eq(x, nil)
        # cdr が nil のときは右括弧で閉じる。
        output += ')'
        level -= 1
      elsif sym == :cdr and atom(x)
        # cdr がアトムのときはドット対で閉じる。
        output += ' . ' + x.inspect + ')'
        level -= 1
      else
        # 2番目以降のリストならスペーサとして改行+インデントを出力する。
        output += "\n" + (' ' * level) if sym == :cdr
        if label.key?(cdr(x).object_id)
          # cdr がラベリングされているときは、ドット対で閉じる。
          stack.unshift :list, car(x), :dot, cdr(x)
        else
          # それ以外は同一レベルで繰り返す。
          stack.unshift :list, car(x), :cdr, cdr(x)
        end
      end
    when :dot
      # ラベリングされているペアをドット対の後に出力し、:cdr, nil で右括弧を加える。
      output += ' . '
      stack.unshift :list, x, :cdr, nil
    end
  end
  # インデント形式でないときは空白に置き換える。
  output.gsub!(/\n[ ]+/msx) { ' ' } if not indent
  output
end

重複参照ノードは深さ優先マーキング法で検出します。

def mark_print_string(list)
  label = {}
  label_number = 0
  mark = {}
  stack = [list]
  while not stack.empty?
    x = stack.shift
    next if atom(x)
    if mark.key?(x.object_id)
      # x は重複参照ノード。ラベリングしていないときは、ラベルを生成する。
      if not label.key?(x.object_id)
        label[x.object_id] = label_number.to_s
        label_number += 1
      end
    else
      mark[x.object_id] = true
      stack.unshift x.car, x.cdr
    end
  end
  label
end

上の2つは、前日の S 式読み込みスクリプトに書き加えて使います。

昨日と同じ例が今度はドット対を使わない S 式で表示できるようになります。

read_string("((a b) . (c d e . nil)) (f g) h") do |e|
  puts print_string(e)
end
#=> ((a b) c d e)
#=> (f g)
#=> h

print_string の 2 番目の引数に偽でない値を与えるとインデント表示をします。

puts print_string(read_string("((a b) . (c d e . nil))", :indent)

インデント・レベルは括弧の深さになります。

((a
  b)
 c
 d
 e)