記事の案内

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

がんばったもの

memo88.hatenablog.com

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

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

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


memo88.hatenablog.com

ごっこ

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

カテゴリ別

Ruby

LibreOffice

Emacs

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

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


移植一覧に戻る


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

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