Unlambda インタプリタを書いてみた (改)

Ruby

一年前に Ruby 1.9 で極力シンプルな Unlambda のインタプリタを書いたんですが、yhara さんにメールでバグを指摘されてしまったので、いろいろ修正しました。
まず、d (delay) と入出力のないシンプル版。

require "continuation"

def unlambda_subset(s)
  t = ->(s) do
    c, *s = s
    r = case c
    when ?`; f, s = t[s]; g, s = t[s]; f[g]
    when ?s; ->(f){ ->(g){ ->(x){ f[x][g[x]] } } }
    when ?k; ->(x){ ->(y){ x } }
    when ?i; ->(x){ x }
    when ?c; ->(f){ callcc{|c| f[c] } }
    when ?v; v = ->(x){ v }
    when ?e; ->(x){ exit }
    else t[s]
    end
    [r, s]
  end
  t[s.split(//)]
end

このコードは parse と eval を同時にやってるんですが、parse のときに Array#shift という破壊的な操作をしていて、そのせいで callcc で戻ったときに正しく再開できないのでした (``cii などで変になる) 。しょうがないので c, *s = s で非破壊的に head と tail に分けるようにして解決。

以下は全命令を実装したバージョン。

require "continuation"

def unlambda(s)
  s = s.gsub(/#.*?$/m, "").chars
  b = nil
  a = ->(f, g){ f ? f[g[]] : ->(x){ a[g[], ->{ x }] } }
  o = ->(c){ ->{ ->(x){ print c; x } } }
  i = ->{ ->(x){ x } }
  v = ->{ ->(x){ v[] } }
  t = ->() do
    case s.next
    when ?`; f, g = t[], t[]; ->{ a[f[], g] }
    when ?s; ->{ ->(f, g, x){ a[a[f, ->{ x }], ->{ a[g, ->{ x }] }] }.curry }
    when ?k; ->{ ->(x, y){ x }.curry }
    when ?i; i
    when ?d; ->{ nil }
    when ?c; ->{ ->(f){ callcc {|c| a[f, ->{ c }] } } }
    when ?v; v
    when ?r; o["\n"]
    when ?.; o[s.next]
    when ?e; ->{ ->(x){ exit } }
    when ?@; ->{ ->(x){ b = $stdin.getc; a[x, b ? i : v] } }
    when ??; c = s.next; ->{ ->(x){ a[x, b == c ? i : v] } }
    when ?|; ->{ ->(x){ a[x, b ? o[b] : v] } }
    else t[]
    end
  end
  t[][]
end

修正点は以下のとおり。

  • コメントに対応した。# から行末までがコメントらしい。
  • すべての適用で d が現れる可能性を考慮した (`dd や `cd などで変になってた) 。
  • せっかくなのでリファクタリング。Proc#curry を使うようにしたり、Enumerator#next を使うようにしたり。

ちなみにこっちは parse と eval が分かれている *1 ので、破壊的に Enumerator#next を使ってよい。はず。

まあ直したとは言うけど本当に正しいかは自信ない。とりあえずこんな感じ。ちゃんとしたテストベンチがほしいです。

unlambda("``id`.Xi")       #=> ""
unlambda("``dd`.Xi")       #=> "X"
unlambda("``cd`.Xi")       #=> "XX"
unlambda("``.Y```si.Xdv")  #=> "YX"
unlambda("``.Y```si.Xiv")  #=> "XY"

*1:最後の行の t[ ][ ] のうち、1 つ目の [ ] が parse で、2 つ目の [ ] が eval になってる感じ。