💎

WhitespaceのインタプリタをRubyで書いた

#tech#Ruby#esolang

2024-1-27

何

年末年始が忙しくて，1月中にブログのネタを1本も書けないのではないかという懸念があったため，雑に生活を破壊してWhitespaceのインタプリタを書いた．

FAQ

Q. 何故Ruby?

A. そういえば自分のGitHubで公開しているリポジトリにRuby製のものが無いなと思ったから

Q. 何故Whitespace?

A. どうせやるならesolang&テストコードが簡単に用意できる[1]

Whitespace

特徴

Whitespaceは，esolang（難解プログラミング言語）の1つであり，ソースコードがコメントを除き全て空白であることが大きな特徴である．

Whitespaceでは，次の3種の文字以外は全てコメントと解釈される．

  • 半角スペース
  • TAB文字
  • 改行文字（LF）

他は全てコメントなので，適当な場所に適当なこの3つに該当しない文字を書いても良い．

言語仕様

Whitespaceはスタック指向の手続き型言語とみなすことができ，各命令はIMP コマンド (引数)のような形式をしている．

IMPには，

  • スタック操作
  • 数値演算
  • ヒープへのアクセス
  • I/O
  • フロー制御

の5種類がある．それぞれは

  • [SP]
  • [TAB][SP]
  • [TAB][TAB]
  • [TAB][LF]
  • [LF]

で表され，各IMPの後にはコマンドと，必要に応じて引数が続く．例を挙げるとスタック操作のコマンドには

  • スタックへのpush（[SP](param)）
  • スタックのトップにある値を複製してpush（[LF][SP]）
  • スタックの上2つの値をswapする（[LF][TAB]）
  • スタックのpop（[TAB][TAB]）
  • スタックの引数番目にある値をコピーしてpush（[TAB][SP](param)）
  • スタックの2番目以降の値を引数の個数だけ削除する（[TAB][LF](param)）

がある．ここでparamで表されている引数は，最初に符号を[SP]=正，[TAB]=負で表してから[SP]=0，[TAB]=1の2進数で表記するようになっている．

他のIMPに属するコマンドも似たようなものなので，これらは割愛する．esolangs.orgによくまとまっている．

実装

トークナイズ

再掲だが各命令はIMP コマンド (引数)のような形をしているので，これらのタプルのリストのようなものを命令列として切り出してやれば良い．これを行うには例えばstrscanのStringScannerを用いて

scanner = StringScanner.new(@code)
while !(scanner.eos?)
    param = nil
    unless scanner.scan(/\A( |\n|\t[ \n\t])/)
    raise Exception, "undefined imp"
    end
    imps = {
    " " => :stack,
    "\t " => :arithmetic,
    "\t\t" => :heap,
    "\n" => :flow,
    "\t\n" => :io,
    }
    imp = imps[scanner[0]]

の様にして，以降はimpに応じてcase-whenすればよい．

例えば，フロー制御を行う:flowについては次のようにする．

when :flow
    unless scanner.scan(/ [ \t\n]|\t[ \t\n]|\n\n/)
        raise Exception, "undefined cmd of flow"
    end
    cmds = {
        "  " => :mark,
        " \t" => :call,
        " \n" => :jmp,
        "\t " => :jz,
        "\t\t" => :jmi,
        "\t\n" => :ret,
        "\n\n" => :exit,
    }
    cmd = cmds[scanner[0]]
    unless (cmd == :ret) || (cmd == :exit)
        unless scanner.scan(/[ \t]+\n/)
        raise Exception, "undefined parammeter of flow"
        end
        param = scanner[0]
    end

:retか:exit以外であれば，その後に引数を取るはずであるので，そのような場合はパラメーターを追加で読み出す．

構文解析

トークナイズが完了した時点でIMP列が取得できているから，あとはやるだけ．仕様に則ってスタックやプログラムカウンタの管理をしっかりとしてやる．

例えばIMP列の要素を1つ取得して，もしスタック関連のIMPであった場合の各操作の内容を示す．

imp, cmd, param = @tokens[pc]
count += 1
case imp
when :stack
pc += 1
case cmd
when :push
    @stack.push(param)
when :duplicate
    @stack.push(@stack.last)
when :swap
    @stack[-1], @stack[-2] = @stack[-2], @stack[-1]
when :discard
    @stack.pop
when :copy
    @stack.push(@stack[-param.to_i(2) - 1])
when :slide
    elm = @stack.pop
    param.to_i(2).times do
    @stack.pop
    end
    @stack.push(elm)
end
脚注

  1. この点，Pietなどを題材にするとめんどい ↩︎