Haskell: Pugs 6.0.2の評価関数に関するメモ

自分用のメモなので、何をやっているのか気にしないで下さいw。

Pugs 6.0.0におけるレクサとパーサの動作は、大よそわかった。
問題はパーサが出力したASTをevalするやり方。

Pugs 6.0.2から変数とサブルーチンがサポートされた。それによってsrc/Eval.hsに新たにEnv型が用意された。「環境」を表現するためにあるようだ。環境の概念については、岩波講座 ソフトウェア科学 4 プログラミング言語 が参考になる。*1

環境の中に存在するシンボル(sym)の読み込みと上書きをするコードをPugs 6.0.2(リビジョン7)をベースにして書いてみた。以下がそのコード。コードの1行目に「{-# OPTIONS -fglasgow-exts #-}」というプラグマを書いておかないといけないみたい。

% vim symbol.hs
{-# OPTIONS -fglasgow-exts #-}
import Debug.Trace

type VInt = Integer
type VStr = String
type Var  = String

data Val
    = VInt  VInt
    | VStr  VStr
    | VError VStr Exp
    deriving (Show, Eq, Ord)

data Exp
    = Syn String [Exp]
    | Var Var
    | Val Val
    deriving (Show, Eq, Ord)
 
type Symbol = (String, Val)
type Symbols = [Symbol]

--
data Env = Env { sym :: Symbols
               } deriving (Show)
emptyEnv = Env { sym = initSyms
               }

initSyms :: Symbols
initSyms = [("foo", VInt 1), ("greeting", VStr "hello")]

--
addSym :: Env -> [(String, Val)] -> Env
addSym env [] = env
addSym env ((var, val):vs) = env{ sym = (var, val):(sym $ addSym env vs) }

retVal :: Val -> ((Env -> Env), Exp)
retVal val = (id, Val val)

reduce :: Env -> Exp -> ((Env -> Env), Exp)
reduce env@Env{ sym = sym } exp@(Var var)
    | Just val <- lookup var sym
    = retVal val

reduce env exp@(Syn name exps)
    | name == "="
    , [Var var, exp]  <- exps
    , trace ("exp = " ++ show exp) True
    , (fenv, Val val) <- reduce env exp
    , trace ("var = " ++ show var ++ ", val = " ++ show val) True
    = (combineEnv fenv var val, Val val)
    where
    combineEnv f var val env = (f env) `addSym` [(var, val)]

reduce env other = (id, other)

--
evaluate :: Env -> Exp -> Val
evaluate env exp
    | Val v <- val = v
    | otherwise    = VError "Invalid expression" exp
    where
    (env', val) = reduce env exp

ghciで実行すると、以下のようになる。
最初の2つの実行例は、環境の中のシンボルの中にある変数fooと変数greetingからそれらの値を取り出せるかどうか試している。最後の例は、環境の中のシンボルの中にある変数fooの値を更新できるかどうか試している。
evaluate関数の第1引数には、初期の環境を渡している。第2引数にはExp型のASTを渡している。

% ghci symbol.hs
*Main> evaluate emptyEnv (Var "foo")
VInt 1
*Main> evaluate emptyEnv (Var "greeting")
VStr "hello"
*Main> evaluate emptyEnv (Syn "=" [Var "foo", Val(VInt 2)])
exp = Val (VInt 2)
var = "foo", val = VInt 2
VInt 2

感想。
パーサでASTを出力する処理も難しいけれども、ASTをevalする処理の方がもっと難しいと思った。初期リリースのPugsのコードが少しずつ読めるようになってきたので、引き続き頑張ろうと思う。

それにしても、Pugsの進化は凄まじい。バージョンが0.02上がっただけでも、コードを理解するのが凄く大変w。

岩波講座 ソフトウェア科学〈〔基礎〕4〉プログラミング言語

*1:この本はHaskellを勉強してから読むと良い。GoferというHaskellが現在の仕様になる以前の処理系の言語を使って説明されている。一見するとHaskellで書かれていると思うくらいGoferとHaskellの基本的な構文は似ている。