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

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

かんたんな自作言語のコンパイラをいろんな言語で書いてみるシリーズ 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 よりはとっつきやすい
    • LispHaskell の中間みたいな印象
    • 慣れてくると 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

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 まわりを簡素化

Reline.readmultiline ちょっと調べたメモ

Reline を使うと複数行編集ができるようなので、自分が使いそうな基本的な部分について調べてみました。

このリッチなのが標準で使えるの嬉しいですよね。ありがたや……。

RUBY_VERSION    #=> 3.0.0
Reline::VERSION #=> 0.2.5

最初の雛形

ブロックは必須。

require "reline"

PROMPT = "> "

loop do
  text =
    Reline.readmultiline(PROMPT) do |_|
      # このブロックについては後述
      true
    end

  # 編集が完了した複数行文字列を使った処理
  puts "text (#{text})"
end

これだけだとまだ複数行編集できないんですが、デバッグ用のログと履歴まわりを準備しておくと捗るので先にそっちを片付けます。

挙動確認のためのデバッグログ出力

デバッグ用の表示を同じターミナルに出力すると混ざって分かりにくいので、 ファイルに出力して別ターミナルで tail -F することに。

$log = File.open("debug.log", "a")

def debug(*args)
  $log.puts *args
  $log.flush
end

履歴の保存・復元

同じ入力を繰り返すのは面倒なので履歴まわりを用意しておきます。

Reline.readmultiline の第2引数 add_hist を true にすると Reline が履歴を覚えてくれて、カーソルキー上下や ctrl-n ctrl-p で履歴を辿れるようになります。

  text = Reline.readmultiline(PROMPT, true) do |input| ...

一度終了して次回実行したときに前回までの履歴が復元されてほしいので、シリアライズしてファイルに保存します。とりあえず JSON で適当に。

require "json"

HISTORY_FILE = "history"

def add_history(text)
  File.open(HISTORY_FILE, "a") { |f| f.puts JSON.generate(text) }
end

def load_history
  return unless File.exist?(HISTORY_FILE)

  File.read(HISTORY_FILE).each_line do |json|
    Reline::HISTORY << JSON.parse(json)
  end
end

Reline.readmultiline のブロック

  text =
    Reline.readmultiline(PROMPT, true) do |input|
      debug ""
      debug "-->> readmultiline block"
      debug input.inspect
      true
    end

こんな感じでデバッグ出力して動作を見てみると、 Enter キーが押されたタイミングでこのブロックが呼び出されているようだぞ、ということが確認できます。

11 Enter 22 Enter と入力したときのデバッグ出力:

-->> readmultiline block
"11\n"

-->> readmultiline block
"22\n"

このブロックは LineEditor#confirm_multiline_termination_proc にセットされ、

ed_newline
=> confirm_multiline_termination
=> @confirm_multiline_termination_proc

という流れで呼び出されるようです。 ed_newline という名前のメソッドから呼ばれているので、改行の入力がトリガーになっていると考えて良さそうな雰囲気です。

ブロックの呼び出しはこのようになっていて、

@confirm_multiline_termination_proc.(temp_buffer.join("\n") + "\n")

各行の末尾に LF の付いた文字列がブロックの引数に渡ってくることが分かります。


ブロックの評価値の扱いも見てみます。

class Reline::LineEditor
  # ...
  private def ed_newline(key)
    # ...
          if confirm_multiline_termination
            finish
          else
            key_newline(key)
          end

真だったら編集完了、偽だったら編集継続となるようです(見た感じでは)。


というわけで、

  1. 編集中の複数行文字列が引数としてブロックに渡ってくる
  2. 編集が完了しているかを判断し、完了している場合はブロックの評価値を真にする。途中だったら偽にする。

というあたりを踏まえて、ブロックの中身を修正します。 例として、末尾が ; になっていたら編集完了というルールにします。

  text =
    Reline.readmultiline(PROMPT, true) do |input|
      debug ""
      debug "--> readmultiline block"
      debug input.inspect

      finished = input.strip.end_with?(";")
      debug "finished (#{finished})"
      finished
    end

11 Enter ;22 Enter ; Enter と入力したときのデバッグ出力:

-->> readmultiline block
"11\n"
finished (false)       ... まだ編集の途中

-->> readmultiline block
"11\n;22\n"
finished (false)       ... まだ編集の途中

-->> readmultiline block
"11\n;22\n;\n"
finished (true)        ... 末尾が ; なので編集が完了したと判断

なるほど。基本的なことがやりたいだけであればこのくらい分かっていれば良さそうですね。

プロンプトをカスタマイズする

たとえば、最初の行とそれ以外で異なるプロンプトを表示したいといった場合、 Reline.prompt_proc に Proc オブジェクトをセットすることでカスタマイズできるようです。

PROMPT = "> "

Reline.prompt_proc =
  Proc.new do |lines|
    lines.each_with_index.map do |line, i|
      i == 0 ? PROMPT : "| "
    end
  end
$ ruby sample.rb 
> 11
| 22
| ;
text (11
22
;)
> 

この場合、Reline.prompt_proc で生成したプロンプト文字列が優先して使われ、Reline.readmultiline の第一引数で渡したプロンプト文字列は使われなくなるようです(表面的な挙動を見た感じでは)。

ただし、Reline.readmultiline の第一引数で渡したプロンプト文字列と長さが異なっていると履歴を移動した際にカーソル位置がずれるので、とりあえず同じ長さにしておくと良いようです。

まとめたもの

require "reline"
require "json"

HISTORY_FILE = "history"
PROMPT = "> "

$log = File.open("debug.log", "a")

def debug(*args)
  $log.puts *args
  $log.flush
end

def add_history(text)
  File.open(HISTORY_FILE, "a") { |f| f.puts JSON.generate(text) }
end

def load_history
  return unless File.exist?(HISTORY_FILE)

  File.read(HISTORY_FILE).each_line do |json|
    Reline::HISTORY << JSON.parse(json)
  end
end

def finished?(input)
  stripped = input.strip
  return true if stripped == "exit"
  return true if stripped.end_with?(";")

  false
end

Reline.prompt_proc =
  Proc.new do |lines|
    lines.each_with_index.map do |line, i|
      i == 0 ? PROMPT : "| "
    end
  end

load_history

loop do
  text =
    Reline.readmultiline(PROMPT, true) do |input|
      debug ""
      debug "-->> readmultiline block"
      debug input.inspect

      finished = finished?(input)
      debug "finished (#{finished})"
      finished
    end

  add_history text

  # 編集が完了した複数行文字列を使った処理
  puts "text (#{text})"

  break if text == "exit"
end

メモ

参考

関連