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


移植一覧に戻る


いつもの通りでライフゲームコンパイルだけ通ればヨシ、という程度の雑なものです。

github.com

移植元

memo88.hatenablog.com

github.com

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

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

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

メモ

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

$ 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 版と同じくらい。さすがですね。


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

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

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

まず、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

とのことです。

参考

関連

開発用のMySQL Dockerコンテナのメモリ消費が大きくて辛かったのでperformance_schemaを無効にしてどれくらい減るか調べたメモ

Qiita に書きました。

qiita.com

vm2gol v2 (58) _debug でブレークポイントを指定できるようにした



今回はブレークポイントを指定できるようにしたのと、後はリファクタリングです。

_debug でブレークポイントを指定

これまで、プログラムの特定の箇所の動作を観察してデバッグしたい場合次のような手順を踏んでいました。

  • まず適当に実行(最初からステップ実行するなど)して、調べたい場所が何ステップ目あたりかを調べる
  • vgvm.rb を直接書き換え、どのステップまでスキップするか指定する
  • 実行するとそのステップまでスキップされるので、そこからステップ実行する

参考: (30) 生存カウント / VRAM から値を取得 / ステップ数を表示

スキップできなかった状態に比べればこれでもかなりの進歩だったわけですが、 さらに便利になるようにブレークポイントを指定できるようにしました。


ステップ実行を始めたい箇所に _debug(); と書いて実行すると、

func main() {
  var a = 1;
  var b = 10;
  set a = a + 2;
  _debug();      // ここからステップ実行開始
  set a = a + b;
}

指定した箇所までダンプ表示がスキップされ、 次の図のように _debug 命令の箇所で止まります。

あとはこれまで通り Enter キーを押してステップ実行すればOK。

f:id:sonota88:20210504065415p:plain


これ、ほんとにちょっとした修正で済むのでたいへんお買い得です。もっと早くやっておけばよかった。

以下の VM の修正を見ての通り、 _debug 命令が来たら Vm#debug を true にして、 Vm#debug が true になっていたらステップ実行する、それだけ。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -135,6 +135,7 @@ class Vm
     @bp = stack_size - 1 # base pointer
 
     @step = 0
+    @debug = false
   end
 
   def test?
@@ -178,6 +179,7 @@ class Vm
     when "set_vram"  then set_vram()  ; @pc += 1
     when "get_vram"  then get_vram()  ; @pc += 1
     when "_cmt"      then               @pc += 1
+    when "_debug"    then _debug()    ; @pc += 1
     else
       raise "Unknown opcode (#{opcode})"
     end
@@ -199,7 +201,7 @@ class Vm
       return if do_exit
 
       unless test?
-        if ENV.key?("STEP")
+        if ENV.key?("STEP") || @debug
           dump()
           $stdin.gets
           # $stdin.gets if @step >= 600
@@ -432,6 +434,10 @@ class Vm
       raise not_yet_impl("arg2", arg2)
     end
   end
+
+  def _debug
+    @debug = true
+  end
 end
 
 if $PROGRAM_NAME == __FILE__

ほとんどそのまま受け渡すだけなのでコンパイラ部分も少しの修正でOK。

to_fn_arg_disp, to_lvar_disp

lvar_addr = to_lvar_addr(lvar_names, lvar_name)
puts "  cp 0 #{lvar_addr}"

のように使っていたやつです。

この lvar_addr には [bp:-2] のような文字列が入るわけですが、これって「アドレス」なんだっけ?   値をセットする宛先だからアドレスと呼んでもダメじゃなさそうだけど…… 詳しくいえば「宛先アドレスの bp 相対間接参照表現」みたいになるんでしょうか……。

みたいな感じでモヤモヤしていて気になっていました。

そこで、モヤモヤしなくて済むような名前と処理内容に変えました。

[bp:-2] のような文字列を返すのではなく、 displacement の値 -2 だけを返すようにすれば、次のように書けます。

  disp = to_lvar_disp(lvar_names, lvar_name)
  puts "cp 0 [bp:#{disp}]"

displacement という、呼び方が定まっているものを返しているわけですから、返り値を受ける変数名も素直に disp とすればよいと(略しているのは置いといて)。

そもそもは何度も同じような処理を繰り返していて煩雑だから共通化していたわけですが、こういう場合は DRY であることよりも意味が明確でモヤモヤしない方が嬉しいです。

また、修正前は

  • displacement を求める
  • 文字列(間接参照表現)を組み立てる

という2つの処理を行っていたのが、責務も単純になり、その面でも良かったのかなと。

その他の修正

他に気になっていた部分のリファクタリング

  • メソッドの並び順の修正
  • その他細かいの
    • parse_args まわりを簡素化