素朴な自作言語のコンパイラをDartに移植した

vm2gol-v2

移植一覧に戻る

Dart で書いてみました。やっつけなので汚いです。Dart よく知らないけどライフゲームが動いたのでヨシ、というレベルのものです。

github.com

移植元

memo88.hatenablog.com

ベースになっているバージョン: tag:46 のあたり

  • 追記 2021-03-21: Dart のバージョンアップ（2.9.1 => 2.12.0）に合わせて修正
    • null safety まわりを適当に修正
  • 追記 2021-03-21: ステップ56の修正まで適用しました

メモ

  • アセンブラ・VM は移植対象から外しました。Ruby 版のものを使います。
  • トークナイザとパーサを分けてみた
  • テストのステップを細かくした
  • ファイルを直接まじめに読まなくても、 標準入力が読めればあとはシェルスクリプトでラップしてあげたりすればいいので、 もうそれでいいかなという気持ちになった。

Dart でプログラムを書くのは今回初めてでしたが、JavaScript と Java あたりを知っていればかなりスムーズに書き始められるなーという感想でした。引っかかるところがほとんどなかったです（今回書いた範囲では）。適当にググりながら 1日で書けてしまいました。

今回の実験的な要素としては、パーサをいじって set を不要にしてみました。

（追記 2021-03-21: この修正はいったん revert しましたが、一応 trial ブランチに残してあります。）

 func main() {
   var a;
-  set a = 42;
+  a = 42;
 }

文の先頭の set で判別するのをやめて、識別子だったら parseSet_v2() を呼ぶ。 もうちょっとめんどくさいかなと思ってましたが、これだけだったら意外と簡単ですね。

List parseSet_v2() {
  // consume("set"); ... これが不要になる
  final t = peek();
  pos++;
  final varName = t.value;
  consume("=");
  final expr = parseExpr();
  consume(";");
  return ["set", varName, expr];
}

List parseStmt() {
  final t = peek();

  if (t.value == "}") {
    return null;
  }

  if      (t.value == "func"    ) { return parseFunc();      } 
  // ...
  // else if (t.value == "set"     ) { return parseSet();       }
  // ...
  else if (t.value == "_cmt"    ) { return parseVmComment(); }
  else {
    if (t.type == "ident") {
      return parseSet_v2();
    } else {
      throw notYetImpl([ t ]);
    }
  }
}

vm2gol v2 （46） リファクタリング（主にコード生成器）

コード生成器で気になっていた部分を修正しました。

codegen_stmts() まわりの整理

修正前の状況を見てみましょう。 呼び出しの関係が次のようになっています。

呼び出す側    => 呼び出される側
codegen       => codegen_stmts
codegen_case  => codegen_stmts
codegen_while => codegen_stmts

まず codegen_stmts を codegen_top_stmts にリネーム。

リネーム後はこうなります:

codegen       => codegen_top_stmts
codegen_case  => codegen_top_stmts
codegen_while => codegen_top_stmts

codegen => codegen_top_stmts はいいとして、 codegen_case、 codegen_while から codegen_top_smtms を呼んでいるのは変ですね。 これだと、たとえば case 文や while 文の中で関数が定義できてしまいます （できるけどそういうコードを書かないようにしていた、という状態）。

リネームによっておかしなところが目立つようになりました。 おかしいので是正していきます。

まずは codegen_func_def 内で関数の処理本体のコード生成を行っていた部分を 改めて codegen_stmts としてメソッド抽出します。 トップレベル以外の場所にある文の連なりの処理です。

（追記 2020-08-25） テストが通っていたので雑にやってしまいましたが、 lvar_names の扱いがおかしいことに気付きました。あとで修正します……。

def codegen_stmts(fn_arg_names, lvar_names, stmts)
  alines = []

  stmts.each do |stmt|
    stmt_head, *stmt_rest = stmt

    case stmt_head
    when "call"
      alines += codegen_call(fn_arg_names, lvar_names, stmt_rest)
    when "call_set"
      alines += codegen_call_set(fn_arg_names, lvar_names, stmt_rest)
    when "var"
      lvar_names << stmt_rest[0]
      alines << "  sub_sp 1"
      if stmt_rest.size == 2
        alines += codegen_set(fn_arg_names, lvar_names, stmt_rest)
      end
    when "set"
      alines += codegen_set(fn_arg_names, lvar_names, stmt_rest)
    when "eq"
      alines += codegen_exp(fn_arg_names, lvar_names, stmt)
    when "return"
      alines += codegen_return(lvar_names, stmt_rest)
    when "case"
      alines += codegen_case(fn_arg_names, lvar_names, stmt_rest)
    when "while"
      alines += codegen_while(fn_arg_names, lvar_names, stmt_rest)
    when "_cmt"
      alines += codegen_comment(stmt_rest[0])
    else
      raise not_yet_impl("stmt_head", stmt_head)
    end
  end

  alines
end

こうなりました:

codegen          => codegen_top_stmts
codegen_case     => codegen_top_stmts
codegen_while    => codegen_top_stmts
codegen_func_def => codegen_stmts

あとは codegen_case、 codegen_while から codegen_top_smtms ではなく codegen_stmts を呼ぶようにすると、こうなります:

codegen          => codegen_top_stmts
codegen_case     => codegen_stmts
codegen_while    => codegen_stmts
codegen_func_def => codegen_stmts

これで意味的に変だったところがまともになりました。 テストが壊れていないので動作の方も問題なさそうです。 たぶん大丈夫。 ライフゲーム動いてるから。

これで codegen_top_stmts の呼び出し元が codegen だけになりました。 トップレベルに書けるのは今のところ関数定義とコメントだけでよいので、 それ以外の分岐は消してしまいます（上述の修正で不要になったので消してOK）。 これにより引数 fn_arg_names, lvar_names も不要になったのでこれも除去。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -428,7 +428,7 @@ def codegen_func_def(rest)
   alines
 end
 
-def codegen_top_stmts(fn_arg_names, lvar_names, rest)
+def codegen_top_stmts(rest)
   alines = []
 
   rest.each do |stmt|
@@ -436,16 +436,6 @@ def codegen_top_stmts(fn_arg_names, lvar_names, rest)
     case stmt_head
     when "func"
       alines += codegen_func_def(stmt_rest)
-    when "call"
-      alines += codegen_call(fn_arg_names, lvar_names, stmt_rest)
-    when "call_set"
-      alines += codegen_call_set(fn_arg_names, lvar_names, stmt_rest)
-    when "set"
-      alines += codegen_set(fn_arg_names, lvar_names, stmt_rest)
-    when "case"
-      alines += codegen_case(fn_arg_names, lvar_names, stmt_rest)
-    when "while"
-      alines += codegen_while(fn_arg_names, lvar_names, stmt_rest)
     when "_cmt"
       alines += codegen_comment(stmt_rest[0])
     else
@@ -464,7 +454,7 @@ def codegen(tree)
 
   head, *rest = tree
   # assert head == "stmts"
-  alines += codegen_top_stmts([], [], rest)
+  alines += codegen_top_stmts(rest)
 
   alines
 end

第38回 で codegen_stmts() と codegen_func_def() の共通化 について触れたときは、なんか変だなとは思っていたもののこの形がまだ見えていませんでした。 慌てていじらずに寝かせておいてよかった気がします。

codegen_exp()

codegen_exp() が長くて（106行……）ちょっと辛いのと、 二項演算の左右の項をスタックに push する処理が重複していたので、 メソッド抽出して整理して、最終的に次のようになりました。すっきり。

def codegen_exp(fn_arg_names, lvar_names, exp)
  alines = []
  operator, *args = exp

  arg_l = args[0]
  arg_r = args[1]

  alines += _codegen_exp_push(fn_arg_names, lvar_names, arg_l)
  alines += _codegen_exp_push(fn_arg_names, lvar_names, arg_r)

  case operator
  when "+"
    alines += _codegen_exp_add()
  when "*"
    alines += _codegen_exp_mult()
  when "eq"
    alines += _codegen_exp_eq()
  when "neq"
    alines += _codegen_exp_neq()
  else
    raise not_yet_impl("operator", operator)
  end

  alines
end

その他

  • codegen_set(): caseの分岐を他の箇所に揃えた
    • 他の箇所に揃えて、まず型で分岐させる書き方に
  • Vm#copy: 記述位置の移動のみ
  • vgparser.rb: tokenize() の記述位置の移動のみ
    • パーサのコードを調べてるとき、末尾に tokenize() があると邪魔くさかったので

Pythonでシンプルな自作言語のコンパイラを書いた

vm2gol-v2

移植一覧に戻る

Python で書いてみました。やっつけなので汚いです。Python よく知らないけどライフゲームが動いたのでヨシ、という程度の雑なものです。

github.com

移植元

github.com

＜自作言語処理系（Ruby版）の説明用テンプレ＞

自分がコンパイラ実装に入門するために作った素朴なトイ言語とその処理系です。

何ヶ月もかけてCコンパイラを作るのが「100 の労力で 100 を得る」だとしたら、このプロジェクトは「まず 5 の労力で 20 を得よう」みたいな方向性です。得られるものは 100 ではありませんが短期間で完成させることができます。

＜説明用テンプレおわり＞

ベースになっているバージョン: ステップ45 のあたり
（追記 2023-11-19 ステップ66 まで反映しました）

動かし方の例

$ echo '
  func add(a, b) {
    return a + b;
  }

  func main() {
    call add(1, 2);
  }
' | python3 mrcl_lexer.py | python3 mrcl_parser.py | python3 mrcl_codegen.py


# ↓アセンブリが出力される

  call main
  exit

label add
  push bp
  mov bp sp

  # 関数の処理本体
  mov reg_a [bp:2]
  push reg_a
  mov reg_a [bp:3]
  push reg_a
  pop reg_b
  pop reg_a
  add reg_a reg_b

  mov sp bp
  pop bp
  ret

  mov sp bp
  pop bp
  ret

label main
  push bp
  mov bp sp

  # 関数の処理本体
  mov reg_a 2
  push reg_a
  mov reg_a 1
  push reg_a
  _cmt call~~add
  call add
  add sp 2

  mov sp bp
  pop bp
  ret

(snip)

ステージごとに動かしてみる

上記の例ではパイプでつなげてコンパイル処理全体を一気に実行していますが、字句解析・構文解析・コード生成それぞれを単独で実行することもできます。

以下、空の main 関数（ func main() {} ）だけをコンパイルするケースで各ステージの動作例を示します。

字句解析

echo 'func main() {}' | python3 mrcl_lexer.py

出力:

[1, "kw", "func"]
[1, "ident", "main"]
[1, "sym", "("]
[1, "sym", ")"]
[1, "sym", "{"]
[1, "sym", "}"]

func main() {} という単なる文字列をトークンの並びに変換します。ここは簡単。素朴な文字列処理なので mrcl_lexer.py も100行以下に収まっています（2024-04-30 時点）。

文字列処理のプログラミングの経験がある程度ある人なら入出力を見ただけで「こうすればできそうだ」というイメージが湧くのではないでしょうか。

構文解析

echo '
[1, "kw", "func"]
[1, "ident", "main"]
[1, "sym", "("]
[1, "sym", ")"]
[1, "sym", "{"]
[1, "sym", "}"]
' | python3 mrcl_parser.py

出力:

[
  "top_stmts",
  [
    "func",
    "main",
    [],
    []
  ]
]

構文解析ではトークンの並びを入力として受け取り、抽象構文木に変換します。

1次元の情報から構造（木構造）を持つデータへ変換するわけで、やり方を知らないとここはちょっと魔法っぽいですよね。

構文解析処理の実装手法はさまざまありますが、Mini Ruccola ではサードパーティライブラリを使わずなるべく自前で書く方針なので 再帰下降構文解析 という方法を使っています。

知らないと魔法っぽく見えるところですし、「再帰下降構文解析」という名前がちょっと怖そうに聞こえるかもしれませんが、初歩的な部分であれば半日もかからず入門できると思います。別の記事に書きましたのでこちらを参照してください。

qiita.com

基本的な部分が分かってしまえば、あとは肉付けです。肉付けしていけばパーサができあがります。

コード生成

echo '
[
  "top_stmts",
  [
    "func",
    "main",
    [],
    []
  ]
]
' | python3 mrcl_codegen.py

出力:

  call main
  exit

label main
  push bp
  mov bp sp

  # 関数の処理本体

  mov sp bp
  pop bp
  ret

(snip)

コンパイラ実装のコア部分です。 抽象構文木を入力として受け取り、アセンブリコード（Mini Ruccola では機械語コードと大体同じ）を出力します。

コンパイル処理全体を通して眺めると、1次元のデータ（ソースコード）を一度扱いやすい構造（抽象構文木）に変換し、それから目的とする出力の形に合わせて1次元のデータ（機械語と対応する命令の列）に変換する、という流れになっていますね。

ここは詳しく書き始めると長くなるので以下を参照してください。私はこういう流れで入門しました、というメモです。

memo88.hatenablog.com

VM・機械語の初歩

アセンブラ

関数呼び出し

関数の引数・ローカル変数・関数の返り値

ライフゲームをコンパイルして実行

（2024-01-06 追記）

run_game_of_life.sh を追加しました。 ライフゲームのプログラムをコンパイル・アセンブルし、VM で実行します。

他の人によって書かれた Python 版移植

ご興味ある方はぜひどうぞ！

github.com

メモ

アセンブラ・VM は移植対象から外しました。Ruby 版のものを使います。

（2024-01-06 追記）Python で書いたアセンブラ・VM も追加しました。

トークナイザは今のところ大した量もないのでパーサと同じファイルに書いていますが、やっぱり分けようかなという気分になりました。

移植版は今後も継続してメンテするわけではなくババッと作って気が済んだら終わりというものなので、 Ruby 版にそのうち入れるかもしれない修正を気軽に・実験的に試してみようかと。

高水準言語部分の文法をやっぱり Ruby っぽくしようかなと考えていて、今回はそれを一部試してみました。

（2021-06-05 追記: その後の修正を加えるために以下の修正はいったん取り消しましたが、一応 trial ブランチに残してあります。）

func を def に変えて、 { ... } を ... end に変えて、行コメントの開始文字を # に変えて……と修正していって、下記のような怪しい見た目になりました。var や set なんかはまだ残っています。

def calc_next_gen(current_val, count)
  # 注目しているセルの次世代の生死
  var next_val = 0;

  case
  when (current_val == 0)
    case
    when (count == 3)
      set next_val = 1;
    end
  when (0 == 0)
    case
    when (count == 2)
      set next_val = 1;
    when (count == 3)
      set next_val = 1;
    end
  end
  
  return next_val;
end

怪しいですが ruby -c test/*.vg.txt で文法チェックすると OK と出ます。

Ruby で実行するとさすがに何かしらエラーになるだろう……と思って試してみたら正常終了しました。 最初は意外な感じがしましたが、メソッドの定義しかしてない（実行していない）ため実行時エラーも出ない、ということのようです。なるほど。

vm2gol v2 （45） リファクタリング（主にVM）

vm2gol-v2

今回は（主に VM の）リファクタリングです。 テストが用意できたので、安心してサクサクと進められます。

Rubocop 関連

Rubocop の設定が古くなってると言われたので設定を修正して、新たに指摘された箇所を修正。

--- a/vgparser.rb
+++ b/vgparser.rb
@@ -403,7 +403,7 @@ def tokenize(src)
       tokens << Token.new(:int, str.to_i)
       pos += str.size
 
-    when /\A(==|!=|[\(\)\{\}=;\+\*,])/
+    when /\A(==|!=|[(){}=;+*,])/
       str = $1
       tokens << Token.new(:symbol, str)
       pos += str.size

Rubocop の指摘（Style/RedundantRegexpEscape）に従って修正した箇所の例です。 こういうのは調べるのがめんどくさくて「とりあえず怪しいのはエスケープしとくか」 となりがちなので、指摘してもらえるのはありがたいですね。

Vm#num_args_for を改良

（10） ステップ実行 / ダンプ表示の改善 の追記で書いていた件です。

diff を見やすくしたいというのが主な目的だったので今さらな感じはしますが。

class Vm
  # ...

  NUM_ARGS_MAP = {
    "cp"       => 2,
    "set_vram" => 2,
    # ...
    "compare" => 0,
    "mult_ab" => 0
  }

  # ...

  def self.num_args_for(operator)
    NUM_ARGS_MAP.fetch(operator)
  end

reg_c を削除

なんとなく残していましたが、使ってないのでやっぱり消しました。 併せて add_ac 命令も削除。

Vm#execute を整理

この長い case 式の部分です。

  def execute
    # ...

    case op
    when "exit"
      return true

    # ...

    when "cp"
      copy(
        @mem.main[@pc + 1],
        @mem.main[@pc + 2]
      )
      @pc += pc_delta
    when "add_ab"
      add_ab()
      @pc += pc_delta

    # ...

    when "call"
      set_sp(@sp - 1) # スタックポインタを1減らす
      @mem.stack[@sp] = @pc + 2 # 戻り先を記憶
      next_addr = @mem.main[@pc + 1] # ジャンプ先
      @pc = next_addr

    # ...
  • (1) メモリから値を取得して引数でメソッドに渡す
  • (2) 引数なしでメソッドを呼び出し、メソッド内でメモリの値を使う
  • (3) メソッド呼び出ししない

のように各命令の処理がバラバラになっていました。 これはどれに揃えるか、あるいは無理に揃えなくてもいいか……などと考えつつ後回しにしていたところです。

ちょっと悩みましたが、 スタイルが統一されて case 式がスッキリするメリットを取って (2) 引数なしでメソッドを呼び出す方式に統一しました。

# 修正後

    case op
    when "exit"
      return true
    when "set_reg_a"
      set_reg_a()
      @pc += pc_delta
    when "set_reg_b"
      set_reg_b()
      @pc += pc_delta
    when "cp"
      copy()
      @pc += pc_delta

    # ...

    when "label"
      @pc += pc_delta
    when "jump"
      jump()
    when "jump_eq"
      jump_eq()

その他

vm2gol v2 （44） テストの追加

vm2gol-v2

残りのテストをまとめて追加しました。

アセンブラ・コード生成器・パーサについては ひとまずライフゲームのコードを与えて出力が一致するか検証するようにしました。 これで、パース〜アセンブルまでの過程のうちどこが壊れているかが瞬時に分かるようになります。 もっと細かい粒度のテストは必要になったらその都度追加しようかと。

VM については命令レベルのテストを書きました。 最初はなるべく VM のコードをいじらずにテストを書こうとしていたのですが、 いろいろめんどくさかった（直交性が低くテストコードが煩雑になる）ので、純粋に1命令だけを実行した結果を検証できるようにしました。

# vgvm.rb
# before

  def start
    # ...

    loop do
      @step += 1
      op = @mem.main[@pc]
      pc_delta = 1 + Vm.num_args_for(op)

      case op
        when "exit"

        # 以下、case 式が続く

この部分を execute() というメソッドに抽出して、 VM命令のテストではこのメソッドを使うようにしました。

# after

  def execute
    op = @mem.main[@pc]
    pc_delta = 1 + Vm.num_args_for(op)

    case op
    when "exit"

    # ...

    end

    false
  end

  def start
    # ...

    loop do
      @step += 1

      do_exit = execute()
      return if do_exit

      # ...
    end
  end

あとは、VM命令をファイル以外の経路で渡せるようにしたり（これもテストのため）、 細かいリファクタリングなどです。

- refactor: project_path() に抽出 (test)
- refactor: PROJECT_DIR を helper.rb で定義するようにした (test)
- chore: rubocop Metrics/ClassLength: vgvm.rb を除外
- refactor: フラグ値を定数化 (vm)
- Add Vm#load_program()
- rename: load_program => load_program_file (vm)

というわけで、各ステップのテストが（雑ですが）用意できて、 これからいろいろいじっていい感じにしていくための用意ができました 🙌

きしださんのかわいいリレーショナルデータベースをRubyで写経した

Ruby RDB_SQL

nowokay.hatenablog.com

きしださんのかわいいリレーショナルデータベースの最初のバージョンを写経してみました。 この記事、もう8年前なんですね。ついこないだ読んだような気がしていましたが……。

簡単なものだったら自作できないかなと以前から思っていたんですよね。 最近やっと重い腰を上げて着手したのですが、 そこできしださんの記事のことをふと思い出し、 参考のために写経してみました。 そういえば、そもそもリレーショナルデータベース自作について考えるようになったきっかけの1つもきしださんの記事だった気がします。

一度そのまま書いたあと、いろいろいじってみました。 それにより非効率になっている部分もありますが、ひとまず自分にとっての理解のしやすさを優先しました。

以下の kawaii_rdb.rb と test_kawaii_rdb.rb を同じディレクトリに置いて

ruby test_kawaii_rdb.rb

で実行できます。

kawaii_rdb.rb

class Database
  @@tables = {}

  def self.tables
    @@tables
  end
end

class Relation
  attr_reader :columns, :tuples

  def initialize(columns, tuples)
    @columns = columns
    @tuples = tuples
  end

  def valid_index?(index)
    0 <= index && index < @columns.size
  end

  # みつからなかったときは属性数(インデックスからあふれる)を返す
  def column_index(name)
    idx = @columns.index { |column| column.name == name }
    idx || @columns.size
  end

  def to_s
    all_rows = [@columns] + @tuples.map(&:values)

    all_rows.map { |values|
      inner =
        values
          .map { |v| v.nil? ? "null" : v }
          .join(" | ")

      "| #{inner} |\n"
    }.join
  end
end

class Query < Relation
  def self.from(table_name)
    tbl = Database.tables[table_name]

    new_columns =
      tbl.columns.map { |column|
        Column.new(column.name, table_name)
      }

    Query.new(new_columns, tbl.tuples)
  end

  def filter_tuple(tuple, column_names)
    values =
      column_names.map { |column_name|
        idx = column_index(column_name)

        if tuple.valid_index?(idx)
          tuple.values[idx]
        else
          nil
        end
      }

    Tuple.new(values)
  end

  def select(*column_names)
    new_columns =
      column_names.map { |column_name|
        Column.new(column_name)
      }

    new_tpls =
      tuples.map { |tuple|
        filter_tuple(tuple, column_names)
      }

    Query.new(new_columns, new_tpls)
  end

  def join_tuple(tuple_l, tuple_r, num_columns)
    new_tpl = tuple_l.dup

    if tuple_r
      tuple_r.values.each { |v|
        new_tpl.values << v
      }
    else
      while new_tpl.size < num_columns
        new_tpl.values << nil
      end
    end

    new_tpl
  end

  def left_join(table_name, matching_field)
    tbl_r = Database.tables[table_name]

    # 属性の作成
    new_columns =
      @columns +
      tbl_r.columns.map { |column| Column.new(column.name, table_name) }

    # 値の作成
    left_column_idx = column_index(matching_field)
    right_column_idx = tbl_r.column_index(matching_field)

    if valid_index?(left_column_idx) && tbl_r.valid_index?(right_column_idx)
      # 両方に該当フィールドあり
    else
      # 該当フィールドがない場合は値の結合をしない
      return Query.new(new_columns, [])
    end

    # 結合処理
    new_tpls =
      @tuples.map { |tpl_l|
        # 結合対象のフィールドを探す（左）
        left_value = tpl_l.values[left_column_idx]

        # 結合対象のタプルを探す
        tpl_r =
          tbl_r.tuples
            .find { |iter_tpl_r|
              # 結合対象のフィールドを探す（右）
              iter_tpl_r.values[right_column_idx] == left_value
            }

        join_tuple(tpl_l, tpl_r, new_columns.size)
      }

    Query.new(new_columns, new_tpls)
  end

  def less_than(column_name, value)
    idx = column_index(column_name)

    unless valid_index?(idx)
      return Query.new(columns, [])
    end

    new_tpls = tuples.select { |tuple| tuple.values[idx] < value }
    
    Query.new(columns, new_tpls)
  end
end

class Table < Relation
  def initialize(name, columns)
    super(columns, [])
    @name = name
  end

  def self.create(name, column_names)
    columns = column_names.map { |column_name| Column.new(column_name) }
    tbl = Table.new(name, columns)
    Database.tables[name] = tbl
    tbl
  end

  def insert(*values)
    @tuples << Tuple.new(values)
    self
  end
end

class Tuple
  attr_reader :values

  def initialize(values)
    @values = values
  end

  def size
    @values.size
  end

  def valid_index?(index)
    0 <= index && index < size
  end
end

class Column
  attr_reader :name

  def initialize(name, parent = nil)
    @parent = parent
    @name = name
  end

  def to_s
    if @parent
      "#{@parent}.#{@name}"
    else
      @name
    end
  end
end

test_kawaii_rdb.rb

require_relative "./kawaii_rdb"
require "minitest/autorun"

class Test < Minitest::Test
  def setup
    # 商品テーブル
    shohin = Table.create(
      "shohin",
      %w(shohin_id shohin_name kubun_id price)
    )

    shohin
      .insert(1, "りんご"  , 1  , 300)
      .insert(2, "みかん"  , 1  , 130)
      .insert(3, "キャベツ", 2  , 200)
      .insert(4, "わかめ"  , nil, 250) # 区分が null
      .insert(5, "しいたけ", 3  , 180) # 該当区分なし

    # 区分テーブル
    kubun = Table.create(
      "kubun",
      %w(kubun_id kubun_name)
    )

    kubun
      .insert(1, "くだもの")
      .insert(2, "野菜"    )
  end

  # テーブル内容
  def test_table
    expected = <<~EXP
    | shohin_id | shohin_name | kubun_id | price |
    | 1 | りんご | 1 | 300 |
    | 2 | みかん | 1 | 130 |
    | 3 | キャベツ | 2 | 200 |
    | 4 | わかめ | null | 250 |
    | 5 | しいたけ | 3 | 180 |
    EXP

    assert_equal(
      expected,
      Database.tables["shohin"].to_s
    )
  end

  # クエリー経由でテーブル内容
  def test_from
    expected = <<~EXP
    | shohin.shohin_id | shohin.shohin_name | shohin.kubun_id | shohin.price |
    | 1 | りんご | 1 | 300 |
    | 2 | みかん | 1 | 130 |
    | 3 | キャベツ | 2 | 200 |
    | 4 | わかめ | null | 250 |
    | 5 | しいたけ | 3 | 180 |
    EXP

    assert_equal(
      expected,
      Query.from("shohin").to_s
    )
  end

  # 射影
  def test_select
    expected = <<~EXP
    | shohin_name | price |
    | りんご | 300 |
    | みかん | 130 |
    | キャベツ | 200 |
    | わかめ | 250 |
    | しいたけ | 180 |
    EXP

    assert_equal(
      expected,
      Query.from("shohin").select("shohin_name", "price").to_s
    )
  end

  # フィルター
  def test_filter
    expected = <<~EXP
    | shohin.shohin_id | shohin.shohin_name | shohin.kubun_id | shohin.price |
    | 2 | みかん | 1 | 130 |
    | 3 | キャベツ | 2 | 200 |
    | 5 | しいたけ | 3 | 180 |
    EXP

    assert_equal(
      expected,
      Query.from("shohin").less_than("price", 250).to_s
    )
  end

  # 結合
  def test_join
    expected = <<~EXP
    | shohin.shohin_id | shohin.shohin_name | shohin.kubun_id | shohin.price | kubun.kubun_id | kubun.kubun_name |
    | 1 | りんご | 1 | 300 | 1 | くだもの |
    | 2 | みかん | 1 | 130 | 1 | くだもの |
    | 3 | キャベツ | 2 | 200 | 2 | 野菜 |
    | 4 | わかめ | null | 250 | null | null |
    | 5 | しいたけ | 3 | 180 | null | null |
    EXP

    assert_equal(
      expected,
      Query.from("shohin").left_join("kubun", "kubun_id").to_s
    )
  end

  # 全部入り
  def test_all
    expected = <<~EXP
    | shohin_name | kubun_name | price |
    | みかん | くだもの | 130 |
    | しいたけ | null | 180 |
    EXP

    actual =
      Query
        .from("shohin")
        .left_join("kubun", "kubun_id")
        .less_than("price", 200)
        .select("shohin_name", "kubun_name", "price")
        .to_s

    assert_equal(expected, actual)
  end
end

参考

素朴な自作言語のコンパイラをTypeScript（Deno）に移植した

vm2gol-v2 TypeScript Deno

移植一覧に戻る

TypeScript 入門というか、とりあえず何か書いて慣れようと思って書いてみました。やっつけなので汚いです。TypeScript まだよく分からないけどなんか動いたのでヨシ、というレベルのものです。

github.com

移植元

memo88.hatenablog.com

＜自作言語処理系（Ruby版）の説明用テンプレ＞

自分がコンパイラ実装に入門するために作った素朴なトイ言語とその処理系です。

何ヶ月もかけてCコンパイラを作るのが「100 の労力で 100 の成果を得る」だとしたら、このプロジェクトは「まず 5 の労力で 20 の成果を得よう」みたいな方向性です。得られるものは 100 ではありませんが短期間で完成させることができます。

＜説明用テンプレおわり＞

ベースになっているバージョン: tag:45 のあたり

メモ

  • YAML/JSON ライブラリへの依存をなくしてみた
    • vge コードは YAML ではなく簡単な独自フォーマットにして自力でパースするようにした
      • 単に行ごとに読んで文字列か数かを判別できればよい
    • vgt コード（JSON）も自力でパースしてみた
  • Ruby 版で作った出力データがすでにあるので、 それに一致するように未実装部分を潰していくだけ。 ゼロから作っていた Ruby 版のときに比べたら遥かに楽。
  • 今回もなんとなく VM → アセンブラ → コード生成器 → パーサ の順で作ってしまって、インクリメンタルな作り方を試せばかったな……と作り終わってから思った

red-arrow: Arrow::Tableのデータを組み立てる

Ruby

とりあえず最低限の流れが知りたかったので、int32 だけの簡単なデータでやってみました。

require "arrow"

# --------------------------------
# 列1 のデータを用意

builder = Arrow::Int32ArrayBuilder.new
builder.append(1)
builder.append(2)
array1 = builder.finish

p array1

# #<Arrow::Int32Array:0x557fac799a88 ptr=0x557fac442e80 [
#   1,
#   2
# ]>

# --------------------------------
# 列2 のデータを用意

# Arrow::XxxArray.new を使うと簡単
array2 = Arrow::Int32Array.new([11, 12])

p array2

# #<Arrow::Int32Array:0x557fac798ed0 ptr=0x557fac442fa0 [
#   11,
#   12
# ]>

# --------------------------------

col1_f = Arrow::Field.new("col1", :int32) # フィールド名、型
col2_f = Arrow::Field.new("col2", :int32)

fields = [col1_f, col2_f]
schema = Arrow::Schema.new(fields)

# --------------------------------

record_batch = Arrow::RecordBatch.new(
  schema,
  2, # 件数
  [array1, array2]
)

p record_batch

# #<Arrow::RecordBatch:0x557fac791720 ptr=0x557fac6c86b0 col1:   [
#     1,
#     2
#   ]
# col2:   [
#     11,
#     12
#   ]
# >

# --------------------------------
# Arrow::Table に変換

table = record_batch.to_table

p table

# #<Arrow::Table:0x557fac790618 ptr=0x557fac6c87a0>
#         col1    col2
# 0          1      11
# 1          2      12

バージョン:
  Ruby 2.7.1
  red-arrow 1.0.0

参考

consごっこ (2)

Ruby Lisp

前

consのデータをメモリに置くとどうなるのか、というのを軽く試してみるつもりだったのが、 もうちょっと育ってしまいました。

※ C言語云々と言っているところはかなりうろ覚えで適当です。だいぶ忘れてます……。

※ また、既存のよく知られた何かに準拠している訳ではなく、思いつきで作った適当なものです。 実際の Lisp 処理系が以下のようになっているのかよく分かってません。 どうなってるんでしょうか。

  • メモリはただの配列
    • 添字がアドレス
    • 内容は整数（値またはアドレス）
  • 整数は1つのアドレスを占有する
  • consセルは car と cdr で隣接した2つのアドレスを占有する

初期状態:

（アドレス: 内容）
0: nil ... 0番地は nil を表す。変更しない。
1: nil ... 未使用。以下同じ
2: nil
...

assign_int(:a, 11) assign_int(:b, 22) を実行すると、空いている場所に値が入れられ、変数に束縛される。

C言語だと int a = 11; int b = 22; みたいな感じ？

0: nil
1: 11 ... a
2: 22 ... b
3: nil
...

値のアドレスを使って cons セルを作成。

cons セルの car部、cdr部には必ずアドレスを入れる（即値は入れない）。 car と cdr は隣接して配置する（car のアドレスの次の番地が cdr）。

C言語だと cons* c1 = cons(&a, &b); みたいな感じ？

0: nil
1: 11 ... a
2: 22 ... b
3: 1 ... c1 の car
4: 2 ... c1 の cdr
5: nil
...
  • c1 の car のアドレスは 3（内容＝参照先アドレスは 1）
  • c1 の cdr のアドレスは 4（内容＝参照先アドレスは 2）
  • それぞれの参照先アドレスを辿ると aの値=11, bの値=22 が得られる。

……というところから出発して、 ついでに free みたいなこともできる？   変数名の管理が必要？   ついでに GC ぽいものも作れる？   ……などと思いつきでいじってたら以下のようになりました。

  • $env で変数名と型（数またはcons）、アドレスの対応を管理
※ こういうイメージ
$env:
  a:
    type: int
    addr: 1
  b:
    type: int
    addr: 2
  c1:
    type: cons
    addr: 3 ... consセルの先頭アドレス

  • $in_use_flags で各番地ごとの使用・未使用を管理

    • 使用中の場合 true
    • 初期状態では 0 番地のみ true

  • unbind

    • free っぽい何か？
    • unbind(name) では $env からキー（変数名）を削除するだけ

  • sweep

    • GC っぽい何か？
    • 参照されている（＝使われている）アドレスは $env を見るとすべて分かる
    • それ以外のアドレスのフラグを false にする

  • 領域の確保と変数の束縛

    • メモリを先頭から見ていって、必要なサイズの領域が未使用だったらそこを使う
      • 未使用かどうかは $in_use_flags を見て判断
    • 領域確保時に $in_use_flags のフラグを true に更新
    • allocate(size) すると、確保した領域の先頭のアドレスを返す
    • $env に登録（束縛）
class EnvItem
  attr_reader :type, :addr

  def initialize(type, addr)
    @type = type # :int | :cons
    @addr = addr
  end

  def to_s
    "(#{@type} #{@addr})"
  end
end

def all_free?(addrs)
  addrs.all? { |addr| $in_use_flags[addr] == false }
end

def find_free_addr(size)
  addrs =
    (1...$in_use_flags.size)
      .each_cons(size)
      .find { |addrs| all_free?(addrs) }

  if addrs.nil?
    raise "no free space"
  end

  addrs[0]
end

def allocate(size)
  addr = find_free_addr(size)
  (0...size).each { |offset|
    $in_use_flags[addr + offset] = true
  }
  addr
end

def assign_int(name, val)
  addr = allocate(1)
  $mem[addr] = val
  $env[name] = EnvItem.new(:int, addr)
  addr
end

def assign_cons(name, car_addr, cdr_addr)
  addr = allocate(2)
  $mem[addr    ] = car_addr
  $mem[addr + 1] = cdr_addr
  $env[name] = EnvItem.new(:cons, addr)
  addr
end

def unbind(name)
  $env.delete(name)
end

def sweep
  in_use_addrs =
    $env.values
      .flat_map { |item|
        case item.type
        when :int
          [item.addr]
        when :cons
          [item.addr, item.addr + 1]
        end
      }

  (1...$mem.size)
    .reject { |addr| in_use_addrs.include?(addr) }
    .each { |addr| $in_use_flags[addr] = false }
end

def name_to_addr(name)
  $env[name].addr
end

def dump_mem
  $mem.zip($in_use_flags).each_with_index { |x, i|
    val, in_use_flag = x
    puts "% 4d %s %s" % [i, in_use_flag ? "*" : " ", val.inspect]
  }
end

初期化:

MEM_SIZE = 14
$mem = Array.new(MEM_SIZE)
$in_use_flags = Array.new(MEM_SIZE){ false }

NIL_ADDR = 0
$mem[NIL_ADDR] = nil
$in_use_flags[NIL_ADDR] = true

$env = {}

# 変数 a, b, c を assign
assign_int(:a, 11)
assign_int(:b, 22)
assign_int(:c, 33)

unbind(:b) # ... まだフラグは true のままで、$env から消えるだけ
sweep() # ... b のアドレスのフラグが false になる

# b が使っていた場所が空いているので、そこが使われる
assign_int(:d, 44)

変数を使ってリストを作成。

# c1, c2, c3 を assign
assign_cons(:c1, name_to_addr(:a), NIL_ADDR)
assign_cons(:c2, name_to_addr(:d), name_to_addr(:c1))
assign_cons(:c3, name_to_addr(:c), name_to_addr(:c2))

# 変数の場合と同様に unbind/sweep して c3 をなかったことに
unbind(:c3)
sweep()

# c3 が使っていた場所が空いているので、そこが使われる
assign_cons(:c4, name_to_addr(:c), name_to_addr(:c2))

この状態でメモリと使用状況をダンプするとこう（* が付いているものが使用中）:

   0 * nil
   1 * 11 ... a
   2 * 44 ... d
   3 * 33 ... c
   4 * 1  ... c1 の car => a のアドレス
   5 * 0  ... c1 の cdr => nil
   6 * 2  ... c2 の car => d のアドレス
   7 * 4  ... c2 の cdr => c1 の先頭アドレス
   8 * 3  ... c4 の car => c のアドレス
   9 * 6  ... c4 の car => c2 の先頭アドレス
  10   nil
  11   nil
  12   nil
  13   nil

c4 からリストをたどってみる:

def walk_list(addr)
  puts "--------"

  if addr == NIL_ADDR
    puts "リストの終端に達した"
    return
  end

  car_pos = addr
  cdr_pos = addr + 1
  puts "car の位置: #{car_pos}"
  puts "cdr の位置: #{cdr_pos}"

  car_content = $mem[car_pos]
  cdr_content = $mem[cdr_pos]
  puts "car の内容（参照先アドレス）: #{car_content}"
  puts "cdr の内容（参照先アドレス）: #{cdr_content}"

  # car の内容（参照先アドレス）を使った操作
  puts "★ car: #{ $mem[car_content] }"

  # cdr の内容（参照先アドレス）を使った操作
  walk_list(cdr_content)
end

walk_list(name_to_addr(:c4))

結果:

--------
car の位置: (Addr 8)
cdr の位置: (Addr 9)
car の内容（参照先アドレス）: (Addr 3)
cdr の内容（参照先アドレス）: (Addr 6)
★ car: 33
--------
car の位置: (Addr 6)
cdr の位置: (Addr 7)
car の内容（参照先アドレス）: (Addr 2)
cdr の内容（参照先アドレス）: (Addr 4)
★ car: 44
--------
car の位置: (Addr 4)
cdr の位置: (Addr 5)
car の内容（参照先アドレス）: (Addr 1)
cdr の内容（参照先アドレス）: (Addr 0)
★ car: 11
--------
リストの終端に達した

動きますね。

ためしに、unbind のたびに sweep するのをやめて最後に1回だけ sweep を実行した場合:

   0 * nil
   1 * 11
   2   22
   3 * 33
   4 * 44
   5 * 1
   6 * 0
   7 * 4
   8 * 5
   9   3
  10   7
  11 * 3
  12 * 7
  13   nil

歯抜けになりました（これはこれで期待通り）。

ふーむ……こんなんでいいんでしょうか。

consごっこ

Ruby Lisp

次

表面だけ見ると Ruby の Array、 Hash っぽいけど中身は cons セル、というものを書いてみました。

試してみたくなって、なんとなく書いてみた、という感じのものです。 cons セルさえあれば基本的なデータ構造が作れてなんとかなるんだな、という感触がふんわり得られればOK。 なので、効率の悪さは無視します。

あまり調べずに適当に書いたので、一般的な Lisp や Scheme とは命名や動作が微妙に違っている気がします。

まず ConsCell クラスと cons メソッド。

class ConsCell
  attr_reader :car, :cdr

  def initialize(first, rest)
    @car = first
    @cdr = rest
  end

  def _to_s(x)
    x.nil? ? "nil" : x.to_s
  end

  def to_s
    "(#{ _to_s(@car) } . #{ _to_s(@cdr) })"
  end
end

def cons(first, rest)
  ConsCell.new(first, rest)
end

puts cons(1, nil)        #=> (1 . nil)
puts cons(1, 2)          #=> (1 . 2)
puts cons(cons(1, 2), 3) #=> ((1 . 2) . 3)

それから car, cdr, list メソッド。

def car(cell)
  cell.car
end

def cdr(cell)
  cell.cdr
end

def list(*args)
  return nil if args.empty?
  first, *rest = args
  cons(first, list(*rest))
end

puts car(cons(1, 2))          #=> 1
puts cdr(cons(1, 2))          #=> 2
puts cdr(cons(1, cons(2, 3))) #=> (2 . 3)
puts list(1, 2, 3)            #=> (1 . (2 . (3 . nil)))

リスト操作処理をいくつか。

def list_nth(xs, i)
  return car(xs) if i == 0
  list_nth(cdr(xs), i - 1)
end

def list_size(xs, n = 0)
  return n if xs.nil?
  list_size(cdr(xs), n + 1)
end

def list_append(xs, x)
  return cons(x, nil) if xs.nil?

  first = car(xs)
  rest = cdr(xs)
  cons(
    first,
    list_append(rest, x)
  )
end

Ruby の Array っぽく使えるクラスを作ってみます。 起点となる cons セルを @cell に保持しておいて、あとはさっき作った操作用メソッドを呼ぶだけ。

中身は Lisp でガワだけオブジェクト指向っぽく使えるようにした、みたいな感じでしょうか。

class ConsArray
  def initialize(*args)
    @cell = list(*args)
  end

  def size
    list_size(@cell)
  end

  def [](i)
    list_nth(@cell, i)
  end

  def <<(x)
    @cell = list_append(@cell, x)
  end

  def to_s
    @cell.to_s
  end
end

それっぽく動くことがふんわり分かればよいだけなので、とりあえず size [] << だけ作ってみました。

同様に、Ruby の Hash っぽく使えるクラスも作ってみました。 ConsHash という名前が微妙ですね。

def alist_create(args)
  return nil if args.nil?

  first  = car(args)
  second = car(cdr(args))
  rest   = cdr(cdr(args))

  cons(
    cons(first, second),
    alist_create(rest)
  )
end

def alist_get(alist, key)
  return nil if alist.nil?

  pair = car(alist)
  if car(pair) == key
    cdr(pair)
  else
    alist_get(cdr(alist), key)
  end
end

def alist_key?(alist, key)
  return false if alist.nil?

  pair = car(alist)
  if car(pair) == key
    true
  else
    alist_key?(cdr(alist), key)
  end
end

def alist_delete(alist, key)
  return if alist.nil?

  pair = car(alist)
  if car(pair) == key
    cdr(alist)
  else
    cons(
      pair,
      alist_delete(cdr(alist), key)
    )
  end
end

def alist_set(alist, key, val)
  cons(
    cons(key, val),
    alist_delete(alist, key)
  )
end

class ConsHash
  def initialize(*pairs)
    args = pairs.flatten
    @cell = alist_create(list(*args))
  end

  def key?(key)
    alist_key?(@cell, key)
  end

  def [](key)
    alist_get(@cell, key)
  end

  def []=(key, val)
    @cell = alist_set(@cell, key, val)
  end

  def delete(key)
    @cell = alist_delete(@cell, key)
  end

  def to_s
    @cell.to_s
  end
end