vm2gol v2 追加機能など

vm2gol-v2

追加機能など

main ブランチにはマージせずにブランチで個別に試しています。

リファクタリング

セルフホスト

いくつか機能を追加するとセルフホストできるようになります。

パーサ

他のターゲット向けに出力

vm2gol v2 （62） case 文の構文を変更 / standardrb に変更

case 文の構文を変更

変更前はこうでした。

case {
  (current_val == 0) {
    case {
      (count == 3) {
        set next_val = 1;
      }
    }
  }
  (0 == 0) {
    case {
      (count == 2) {
        set next_val = 1;
      }
      (count == 3) {
        set next_val = 1;
      }
    }
  }
}

case { ... } の波括弧はなくてもよさそうですね。なくてもパースできそう。外してみましょう。

case
(current_val == 0) {
  case
  (count == 3) {
    set next_val = 1;
  }
}
(0 == 0) {
  case
  (count == 2) {
    set next_val = 1;
  }
  (count == 3) {
    set next_val = 1;
  }
}

ネストが減り、 } がなくなることで行数も減ってすっきりします。

パースの都合としてはこれでも問題ないのですが、各分岐の先頭にキーワードを置いた方が見た目的に落ち着きがいいかも？

when を書くようにしてみます。

case
when (current_val == 0) {
  case
  when (count == 3) {
    set next_val = 1;
  }
}
when (0 == 0) {
  case
  when (count == 2) {
    set next_val = 1;
  }
  when (count == 3) {
    set next_val = 1;
  }
}

ふむ、良いのでは。ということで今回このように変更しました。

ちなみに、なぜ最初からこの形にしていなかったのかというと、 多少冗長でも case { ... } のように波括弧があった方が case 文の範囲が分かりやすくて良いのではないか（パース処理で面倒なことを考える必要が減るのではないか）という、初心者の素朴な直観みたいなものがあったためです。

実用を目指しているわけではなく（自分の）教育用を想定した言語なので、そういう初心者目線の感覚は大事にしたい……という気持ちもあってちょっと悩んだのですが、実装も少しだけシンプルになりますし、変えてしまいました。

パーサの変更はこれだけ:

--- a/vgparser.rb
+++ b/vgparser.rb
@@ -258,6 +258,7 @@ def parse_while
 end
 
 def _parse_when_clause
+  consume "when"
   consume "("
   expr = parse_expr()
   consume ")"
@@ -272,16 +273,12 @@ end
 def parse_case
   consume "case"
 
-  consume "{"
-
   when_clauses = []
 
-  while peek().value != "}"
+  while peek().value == "when"
     when_clauses << _parse_when_clause()
   end
 
-  consume "}"
-
   [:case, *when_clauses]
 end

standardrb に変更

RuboCop を導入したはいいものの、微妙に放置気味でしたし、 この程度の規模のプロジェクトには大げさな感じがして、Standard (standardrb) に変えました。

メモ 2024-01-08 / C++ の try

『コーディングを支える技術――成り立ちから学ぶプログラミング作法』によれば、C++ の try { ... } catch { ... } の try は飾りなのだそうです（p68）。

C++設計者の Bjarne Stroustrup によれば、try はわかりやすくするためのただの飾りだそうです。

詳しくは『C++の設計と進化』を読むと良いようです。

vm2gol v2 （60） stmt をそのまま渡す / (61) リファクタリング

step 60

stmt_rest ではなく stmt を渡す

前々から気にはなっていたけど後回しにしていたものを片付けるシリーズです。

例として gen_call を見てみます。

def gen_call(fn_arg_names, lvar_names, stmt_rest)
  fn_name, *fn_args = stmt_rest
  # ...
end

# 呼び出し側
def gen_stmt(fn_arg_names, lvar_names, stmt)
  stmt_head, *stmt_rest = stmt

  case stmt_head
  when "call"
    gen_call(fn_arg_names, lvar_names, stmt_rest)
  # ...

stmt （文に対応するデータ）の先頭の要素は文の種類を表しているわけですが、 「これは○○文だな」と判断するためにその先頭要素を使っているのは呼び出し側であって、 呼び出した先では不要です。 不要なものは渡さなくていいんじゃないか、という（ぼんやりした）理由により このような作りになっていました。

しかし、だんだん不都合の方が気になってきました。

  • stmt_rest ってなんやねん問題
    • 「先頭の要素を除いた残りです」と説明すれば済むので、大して難しい話ではない。ないんだけど、その説明すらも不要にできれば、より簡素にできて良い。
  • 移植性

というわけで、先頭を除いた残りだけ渡すのをやめ、 文のデータ全体をそのまま渡すようにしました。 渡された側では単純に先頭の要素を無視することに。

def gen_call(fn_arg_names, lvar_names, stmt)
  _, *funcall = stmt
  # ...
end

def gen_stmt(fn_arg_names, lvar_names, stmt)
  case stmt[0]
  when "call"
    gen_call(fn_arg_names, lvar_names, stmt)
  # ...

○○文を処理するメソッドに○○文のデータをそのまま渡すようになりました。やっぱりこの方が単純で分かりやすいように思います。

トップレベルでのVMコメントの廃止

トップレベルで _cmt を使えるようになっていましたが、そうする必要がなかったので廃止。

==, != をそのまま使う

パース時にそれぞれ eq, neq に変換していましたが、 あらためて考えると不要な変換と思えたので +, * と同様に ==, != とするように。

さらにリファクタリングすれば parse_expr_right をコンパクトにできる状態になっていますが、今回の差分が分かりにくくなるので次回に先送りします。

Token#kind にリネーム

Token#type から Token#kind に変更しました。

他の処理系や解説などを見ていると、これは kind という名前にしているものが多いようなんですよね。 いわゆる型と混同しないように type という名前を避けているのか、単に慣習的なものなのか、はたまた英語的に kind の方が適切なのか……みたいな推測をしてますが、はっきりした理由は把握していません。

step 61

気になっていた細かい部分をまとめて修正しました。 リファクタリングのみなのでページを分けずに続けて書きます。

step 61 の差分はこちら

変更後の行数はこんな感じ。

$ LANG=C wc -l vg*.rb
   66 vgasm.rb
  381 vgcodegen.rb
   58 vglexer.rb
  380 vgparser.rb
  447 vgvm.rb
 1332 total

二項演算子まわりの整理

step 60 の変更により変換処理が不要になったので case を削除。

修正前:

def parse_expr
  expr = _parse_expr_factor()

  while binary_op?(peek())
    op =
      case peek().value
      when "+"  then "+"
      when "*"  then "*"
      when "==" then "=="
      when "!=" then "!="
      else
        raise ParseError, "must not happen"
      end
    $pos += 1

    expr_r = _parse_expr_factor()
    expr = [op.to_sym, expr, expr_r]
  end

  expr
end

修正後:

def parse_expr
  expr = _parse_expr_factor()

  while binary_op?(peek())
    op = peek().value
    $pos += 1

    expr_r = _parse_expr_factor()
    expr = [op.to_sym, expr, expr_r]
  end

  expr
end

すっきりしました。

vgcodegen.rb にリネーム

cg という名前を見て code generator の略だとすぐ分かる人はいなさそう、このように略している例を見ない、ということで、一般的ですぐ分かる名前に変更。

変数名・メソッド名などのリネーム、コメントの整理

気になっていた箇所をまとめて修正。

vm2gol v2 （59） while, case の真偽判定の変更 / 予約語の判定の改良

真偽判定の変更（コード生成）

while 文と case 文では 条件式の評価結果を 1 と比較して真偽を判定していました。 疑似コードで書くとこう。

# 修正前

if 条件式の評価結果 == 1
  真と判定 => while_true ラベルにジャンプ
else
  偽と判定 => end_while ラベルにジャンプ（ループを抜ける）
end

label while_true
ループの処理本体

label end_while

この場合、たとえば条件式の評価結果が 2 だった場合も偽になってしまいます。 ちょっと違和感がありますね。

というわけで、次のように 0 と比較する形に変更しました。

# 修正後

if 条件式の評価結果 == 0
  偽と判定 => end_while ラベルにジャンプ（ループを抜ける）
else
  真と判定 => while_true ラベルにジャンプ
end

label while_true
ループの処理本体

label end_while

この方が整数から真偽値へのマッピングのルールとして筋が良い気がします。少なくとも C や JavaScript などに近い挙動にはなります。

さらに、この修正により、真だった場合の while_true ラベルへのジャンプが不要（すぐ次のラベルにジャンプしている）になります。これも消してしまえるので、最終的に次のようになりました。

if 条件式の評価結果 == 0
  偽 => end_while ラベルにジャンプ（ループを抜ける）
end

ループの処理本体

label end_while

コンパイラのコードもコンパイラが生成するコードもちょっとだけコンパクトに。

予約語の判定の改善（レキサ）

予約語と識別子を切り出している箇所（修正前）です。

  while pos < src.size
    rest = src[pos .. -1]

    case rest
    # ...

    # 予約語の判定
    when /\A(func|set|var|call_set|call|return|case|while|_cmt|_debug)[^a-z_]/
      str = $1
      tokens << Token.new(:kw, str)
      pos += str.size
      # ...

    # 識別子の判定
    when /\A([a-z_][a-z0-9_]*)/
      str = $1
      tokens << Token.new(:ident, str)
      pos += str.size
    else
      # ...
    end
  end

この、予約語用の正規表現の [^a-z_] の部分がなんか微妙で、なんとかできないかなという気持ちが前からありました。

そこで、次のように修正しました。

--- a/vglexer.rb
+++ b/vglexer.rb
@@ -1,5 +1,10 @@
 require_relative "./common"
 
+KEYWORDS = [
+  "func", "set", "var", "call_set", "call", "return", "case", "while",
+  "_cmt", "_debug"
+]
+
 def tokenize(src)
   tokens = []
 
@@ -19,10 +24,6 @@ def tokenize(src)
       str = $1
       tokens << Token.new(:str, str)
       pos += str.size + 2
-    when /\A(func|set|var|call_set|call|return|case|while|_cmt|_debug)[^a-z_]/
-      str = $1
-      tokens << Token.new(:kw, str)
-      pos += str.size
     when /\A(-?[0-9]+)/
       str = $1
       tokens << Token.new(:int, str.to_i)
@@ -33,7 +34,8 @@ def tokenize(src)
       pos += str.size
     when /\A([a-z_][a-z0-9_]*)/
       str = $1
-      tokens << Token.new(:ident, str)
+      type = KEYWORDS.include?(str) ? :kw : :ident
+      tokens << Token.new(type, str)
       pos += str.size
     else
       p_e rest[0...100]

曖昧さが減り、安定感のあるコードになったと思います。パターンの考慮漏れについての不安が小さいコードになったというか。

これは正規表現が使えない（標準ライブラリ等に含まれていない）言語に移植していたときに思いついた方法で、それを Ruby 版にフィードバックしたものです。

ちなみに、このように書けるのは 予約語のパターンが識別子のパターンに含まれるためですね。 その前提が崩れるとダメですが、まあ、問題ないでしょう。

その他

  • パーサ: loop を while で書き換え
  • トークンの値を取り出す処理を Token#get_value に抽出

Haskellごっこ: 変数の定義・参照

Haskell

前回「Haskellでかんたんな自作言語のコンパイラを書いた」というのを書きました。これはこれで気が済んだので Haskell の話は切り上げて次に行ってもいいのですが、せっかく読み書きに慣れてきたところですし、もう少し何かやってみようかなと。

※ Haskell 初心者が書いてますので用語が怪しいところなどあると思います

他のメジャーな言語と Haskell で異なる点として、まず目に付くのが変数の定義・参照まわりの挙動です。

これはふしぎじゃない:

x = 123
y = x

main = print y
-- => 123

（手続き型の言語に慣れていると）これはふしぎ:

y = x
x = 123

main = print y
-- => 123

定義の順番に意味がなく、宣言的です。

ちなみに let や where でも同様。

main =
  print (
    let y = x
        x = 123
    in
      y
  )
-- => 123

main =
  print y
  where
    y = x
    x = 123
-- => 123

定義の左辺と右辺に同じ変数がある、次のようなパターンでは無限ループになるようです。

x = x :: Int

main = print x

といった感じで例を見ていると、Haskell の実行モデルみたいなものが想像できてきて、 上に挙げた例だけが動かせるような最低限の小さな処理系なら作れそうな気分になってきました。

Haskell 処理系が実際にどうやっているか確認したわけではなくて完全に憶測なのですが、適当にやってみます。とりあえず表面的に同じ結果になればOK。

雰囲気をつかむために Ruby のコードで動作をなぞってみます。

# sketch_01.rb

defs = {
  :x => 123,
  :y => :x
}

# y の定義を探す
y_def = defs[:y]  #=> :x

# x の定義を探して置き換え
y_def = defs[y_def]  #=> 123

# これ以上は簡約できない

puts y_def
#=> 123

無限ループになるパターン:

# sketch_02.rb

defs = {
  :x => :x
}

# x の定義で置き換え
x_def = defs[:x]  #=> :x

# x のままなのでまだ簡約できる
x_def = defs[:x]  #=> :x

# x のままなのでまだ簡約できる
# → 無限ループ

なんとなく雰囲気はつかめてきた気が。まとめたものを書いてみます。

# haskell_gokko.rb

def reducible?(def_)
  def_.is_a?(Symbol)
end

def run(defs, goal)
  def_ = goal

  while reducible?(def_)
    def_ = defs[def_]
  end

  def_
end

まとめたらこれだけになってしまった……「簡約可能であれば定義を探して置き換え」を繰り返す、というものです。

たったこれだけですが、これでもテストはパスします。

p run(
    { :x => 123 },
    :x
  )
#=> 123

p run(
    {
      :y => :x,
      :x => 123
    },
    :y
  )
#=> 123

p run(
    { :x => :x },
    :x
  )
#=> 無限ループ

こういうプログラム、なんか見覚えあるなーと思ったのですが、 グラフのアルゴリズムくさいですね。

参考（以前やったもの）:

となると、定義のセットが隣接リストに相当する？ ふーむ……。

y => x => 123 と辿る場合はこういうグラフ:

f:id:sonota88:20210703092714p:plain

x => x => ... と辿る場合はこういうグラフ:

f:id:sonota88:20210703092801p:plain

まあ、わざわざ図を描かなくてもいいような例ですが……。

というわけで、ものすごく簡単な Haskell 処理系ごっこをやってみました。 できあがってみると、これはただの「有向グラフを辿るくん」ですね。

繰り返しになりますが、実際の処理系を調べていないオレオレで、無限ループになるパターンとならないパターンの2つだけが動けばよいという適当なものです。コンパイラじゃなくてインタプリタだし。

Haskellでかんたんな自作言語のコンパイラを書いた

vm2gol-v2

移植一覧に戻る

OCaml 版を書いた勢いで Haskell にもババッと移植しました。いつもの通りでライフゲームのコンパイルだけ通ればヨシ、という程度の非常に雑なものです。

github.com

移植元

memo88.hatenablog.com

github.com

ライフゲームのプログラムだけコンパイルできれば OK という、ゆるくて簡単なコンパイラです。Ruby 版だとコンパイラ部分だけで 1000行くらい。

ベースになっているバージョンは ステップ 58 のあたり。

作り方はここに全部書いています（Ruby 版のものですが）: vm2gol v2 製作メモ

メモ

主な部分のサイズ（行数）はこんな感じ。

$ wc -l *.hs lib/{Types,Utils}.hs
  431 codegen.hs
  142 lexer.hs
  377 parser.hs
    7 lib/Types.hs
   27 lib/Utils.hs
  984 合計

Ruby 版、OCaml 版とだいたい同じくらい。

  • Haskell はだいぶ前（メモを見返したら 9 年前だった）に本を 2, 3 冊流し読みしてちょっと手を動かした程度でそれっきり。なので、ほぼ忘れていて、今回はほぼゼロからの再入門……というのはウソで、前回とは違って今回は OCaml 版を作った直後なので、 その分のゲタを履いたところからのスタート。
  • OCaml 版をほとんどそのまま移植する形で済み、3, 4 日（土日含む）で書き終わってしまった
    • そもそも評価戦略が違うし結構いろんなところを書き直す必要がありそう、難航しそうと思っていたので予想外というか拍子抜けというか
  • OCaml 版を割とそのまま移植しているので、あんまり Haskell っぽい書き方になっていないと思います
    • Haskell っぽいかっこいい（？）機能をぜんぜん使ってない。関数合成とかもやってないし、というかただの高階関数ですらちょっとしか使ってない。単に関数を書いて並べましたという、意識が低い感じ。
    • 海原 Haskell 雄山に「このコードを書いたのは誰だあっ!!」って言われそうなできあがり
    • いいんですよ、ライフゲームがコンパイルできれば優勝というレギュレーションだから

OCaml では、ある変数の値を加工して同じ変数に代入しなおすような書き方ができます（実際には値を更新しているのではなく新しい束縛で古いものをマスクしている感じ。たぶん）。

let () =
  print_int (
    let x = 1 in
    let x = x + 1 in
    x
  )

Haskell では評価の仕方が違うのでこれはできなくて、実行時に無限ループになります。

main :: IO ()
main = do
  print (
    let x = 1 in
    let x = x + 1 in
    x
    )

こういうことをやりたい場合は let x' = x + 1 in ... のように別の名前にしないとダメ。

参考: debugging - Haskell program outputs <<loop>> - Stack Overflow

他の言語への移植

記事 リポジトリ 日付
OCaml github 2021-06-26
Pascal github 2021-05-22
Julia github 2021-05-03
Rust github 2021-04-07
Crystal github 2021-03-27
セルフホスト github 2021-02-21
Kotlin github 2021-01-14
Zig github 2021-01-07
LibreOffice Basic github 2020-12-14
Go github 2020-09-25
PHP github 2020-09-18
C♭ github 2020-09-13
Perl github 2020-09-08
C github 2020-09-06
Java github 2020-08-30
Dart github 2020-08-22
Python github 2020-08-19
TypeScript (Deno) github 2020-08-15

OCamlでかんたんな自作言語のコンパイラを書いた

vm2gol-v2

かんたんな自作言語のコンパイラをいろんな言語で書いてみるシリーズ 18番目の言語は OCaml です。 いつもの通りでライフゲームのコンパイルだけ通ればヨシ、という程度の雑なものです。

できたもの

github.com

主な部分のサイズ（行数）はこんな感じ。

$ wc -l *.ml lib/{utils,types}.ml
  401 codegen.ml
  127 lexer.ml
  369 parser.ml
   52 lib/utils.ml
    6 lib/types.ml
  955 合計

Ruby 版と同じくらい。

移植元

memo88.hatenablog.com

github.com

ライフゲームのプログラムだけコンパイルできればOKという簡単なコンパイラです。Ruby 版だとコンパイラ部分だけで 1000行くらい。

ベースになっているバージョンは ステップ 58 のあたり。 （追記 2023-04-15 ステップ 63 まで反映させました）

作り方はここに全部書いています（Ruby 版のものですが）: vm2gol v2 製作メモ

動かし方の例

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

  func main() {
    call add(1, 2);
  }
' | bin/lexer | bin/parser | bin/codegen

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

  call main
  exit
label add
  push bp
  cp sp bp
  cp [bp:2] reg_a
  push reg_a
  cp [bp:3] reg_a
  push reg_a
  pop reg_b
  pop reg_a
  add_ab
  cp bp sp
  pop bp
  ret
label main
  push bp
  cp sp bp
  cp 2 reg_a
  push reg_a
  cp 1 reg_a
  push reg_a
  _cmt call~~add
  call add
  add_sp 2
  cp bp sp
  pop bp
  ret

メモ

  • Lisp が静的型になったみたいな印象（雑な印象）
  • Haskell よりはとっつきやすい
    • Lisp と Haskell の中間みたいな印象
    • 慣れてくると Lisp を書くときと同じような感覚で書ける
    • 純粋でない書き方ができるのと、遅延評価ではないので、メジャーな言語とのギャップが （Haskell に比べれば）小さい
    • オフサイドルールもない
    • Haskell 難しい、よく分からなかったという人は急がば廻れで OCaml を試すとよいかもしれません
  • ref は使わなくても書けた
  • コード生成で関数の引数名のリスト、ローカル変数名のリストに加えて label id も引き回す作りにしているので、ここはレコードでまとめてみた
  • 多少読めるようになってきたので次は Haskell に再チャレンジしたい
  • せっかくなので ocamlyacc を使えるようにしたい。 そして MinCaml を読みたい
    • 今回は ocamlyacc などのライブラリは使っておらず、パーサは手書き

（以下、初心者が書いてますので不正確な記述・間違いなどあるかと思います）

書いていたら意外とすぐ慣れたけど最初よく分からなかった関数適用まわりの書き方について。

まず、1引数の関数しかないというのが前提。 引数なしの関数というのもない（たぶん）。 返り値も必ず1つ（たぶん）。

参考: なぜ関数型言語の関数は必ず値を返すのか - Qiita

引数なしの場合は () を渡す（() に対して関数を適用する）

(* 関数の定義 *)
let f () = print_string "hello\n" in

(* 関数の適用 *)
f ()

これは「関数名に続けて ( ) を書く」という構文なのではなくて、「() という値（unit 型の値、ユニット値）に対して関数 f を適用している」と読む（『プログラミング in OCaml』 p152, 153）。

引数が2個以上の場合は、カリー化関数を使うか、タプルを使う。 （カリー化関数を使うといっても単に下記のように書くだけなので意識することはほとんどありませんでした）

(* カリー化 *)
let add1 a b = a + b in
add1 1 2

(* タプル *)
let add2 (a, b) = a + b in
add2 (1, 2)

使い分けについては

引数が組であることに意味がなければ，カリー化して定義することが推奨されます。 しかも，大抵の場合，カリー化関数のほうが効率良く実行できるようになっています。

（『プログラミング in OCaml』 p62）

とのことです。

ALGOL系の言語だと、関数呼び出しはこう。見慣れた感じ。

foo_func(1, 2)

Ruby では括弧を省略してこう書ける。

foo_func 1, 2

OCaml では引数の区切りのカンマは不要（スペースで区切る）。

foo_func 1 2

次のように括弧で囲んでいる場合、これは一見すると Lisp の関数適用と同じ見た目になっているけど、 中身の foo_func 1 2 の部分が式で、それを括弧で囲んでいる、と読むっぽい。 ALGOL系言語で 1 + 2 を括弧で囲んで (1 + 2) にするのと同じような感覚。

(foo_func 1 2)

↑この例だと括弧を付ける必要はないが、評価結果に対してさらに別の関数を適用する、といった場合は括弧が必要になる（ないと区切りが分からない）。

bar_func (foo_func 1 2)

ここらへんの括弧の付け方が分かってくると普通に読み書きできるようになります。

if 式の then/else で複数の式を間違った形で書くとうまく動かないので、 慣れるまではとりあえず全部括弧で囲んでおけばよい（という感じでやってました）。 慣れてきて、ここは外しても大丈夫そうだな、と判断できるようになってきたら外していく。

if ... then
  (
    ...
  )
else
  (
    ...
  )

match も同様。

match ... with
| 0 ->
  (
    ...
  )
| _ ->
  (
    ...
  )

ちなみに、私はめんどくさくて括弧で書いていましたが

文の並びを囲むときには括弧ではなくて begin/end を使うのが 「よいスタイル」 だと言われて推奨されています。

『プログラミング in OCaml』 p167

とのことです。

追記 2023-04-15

www.saiensu.co.jp

その後『プログラミングの基礎』も読みました。こういうタイトルですが OCaml の入門書でもあります。説明がとても平易で、一番最初に読む OCaml の入門書としておすすめ。

参考: [OCaml]書評「プログラミングの基礎」 - あどけない話

www.coronasha.co.jp

タイトルに OCaml と書かれていませんがこれも OCaml の本です。こちらも後から読みました（といっても図書館で借りてまだざっと目を通した程度）。扱われている内容の難易度的には今の自分にちょうどよさそうという印象で、購入しておこうかと。 ocamllex と ocamlyacc を使い、ターゲットは x64。

参考

この記事を読んだ人は（ひょっとしたら）こちらも読んでいます

memo88.hatenablog.com

memo88.hatenablog.com

memo88.hatenablog.com

qiita.com