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つだけが動けばよいという適当なものです。コンパイラじゃなくてインタプリタだし。