記事の案内

「このブログには他にどういう記事があるの?」という方向けの案内です。

がんばったもの

memo88.hatenablog.com

TechRacho さんの週刊Railsウォッチ(20210209後編)で紹介されました。

続き: Rubyで素朴な自作言語のコンパイラを作った

さらに続き: 素朴な自作言語Pricのコンパイラをセルフホストした


memo88.hatenablog.com

ごっこ

いわゆる "Build your own 〜 from scratch" 的なもの、写経したものなど。

カテゴリ別

Ruby

LibreOffice

Emacs

Emacs 関連は一部内容が古くなっている気がします。

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) に変えました。



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 で異なる点として、まず目に付くのが変数の定義・参照まわりの挙動です。

これはふしぎじゃない:

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でかんたんな自作言語のコンパイラを書いた


移植一覧に戻る


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