評価順

.hs

『Jythonプログラミング』の西尾泰和氏のエントリに似ているけど違う話。

最小限 Haskell あるかな？

『プログラミング Haskell』 10.5 仮想マシン

関数型パーサに比べて検索に Hit しない。

今まで Haskell のコードを Groovy で実装していたけどそれは Haskell の評価順は Groovy の評価順でも問題なかったからだ。10.5 は Haskell が Groovy の評価順で処理するという内容だ。*1

Haskell で数式処理は次のように定義できる。

data Expr = Val Int | Add Expr Expr | Mul Expr Expr | Pow Expr Expr

value          :: Expr -> Int
value (Val n)   = n
value (Add x y) = value x + value y
value (Mul x y) = value x * value y
value (Pow x y) = value x ^ value y


value 関数で実行できるのだが Haskell では x から計算するのか y から計算するのか決まっていない。

*Main> value (Add (Mul (Val 1) (Val 1)) (Mul (Val 2) (Val 2)))
5
*Main> value (Pow (Val 2) (Pow (Val 1) (Val 0)))
2


C言語も関数の引数の評価順は決まっていない。

#include <stdio.h>

int add(int a, int b) {
  printf("%d+%d\n", a, b);
  return a + b;
}

int mul(int a, int b) {
  printf("%d*%d\n", a, b);
  return a * b;
}

int main() {
  printf("%d\n", add(mul(1, 1), mul(2, 2)));
}

手元の環境では右から評価された。

2*2
1*1
1+4
5


Java は言語仕様で定められていて左から評価される。

def add(int a, int b) {
  println "$a+$b"
  a + b
}

def mul(int a, int b) {
  println "$a*$b"
  a * b
}

def pow(int a, int b) {
  println "$a^$b"
  a ** b
}

println add(mul(1, 1), mul(2, 2))

1*1
2*2
1+4
5


Haskell でも仮想スタックマシンを使えば Java のように左から評価できる。*2

data Op   = EVALA Expr | EVALM Expr | EVALP Expr | ADD Int | MUL Int | POW Int
type Cont = [Op]

eval            :: Expr -> Cont -> Int
eval (Val n)   c = exec c n
eval (Add x y) c = eval x (EVALA y:c)
eval (Mul x y) c = eval x (EVALM y:c)
eval (Pow x y) c = eval y (EVALP x:c)

exec              :: Cont -> Int -> Int
exec []          n = n
exec (EVALA y:c) n = eval y (ADD n:c)
exec (EVALM y:c) n = eval y (MUL n:c)
exec (EVALP y:c) n = eval y (POW n:c)
exec (ADD   n:c) m = exec c (n + m)
exec (MUL   n:c) m = exec c (n * m)
exec (POW   n:c) m = exec c (m ^ n)


eval で構文木とスタックを渡して実行する。

*Main> eval (Add (Mul (Val 1) (Val 1)) (Mul (Val 2) (Val 2))) []
5
*Main> eval (Pow (Val 2) (Pow (Val 1) (Val 0))) []
2

考え方

  • eval は Expr をどちらに進むか決定する
  • 評価しない方の Expr はスタックに積んでおく
  • 末端まで辿り着いたら exec でスタックから取り出して計算する
    • Expr なら現在の値をスタックに積み eval
    • 値なら計算して現在の値を更新し再び exec
  • スタックが空になったときの値が結果

ここまでは分かるのだが何がトリガーとなって確定しているのかが分からない。
スタックから取り出すより先にスタックに入れなければいけないことは分かる。
しかし現時点ではこの演算というところまで理解できていない。

*1:気づくのに時間がかかった

*2:POW は右から