stackvm

なにやら『プログラミング Haskell』で足し算のみ可能なスタック型 VM を実装していたのを見て，普通に関数を与えられるように改良 (?) してみた．なんとなく要領を掴めてきた…はず…!

data Expr = Const Int
          | OP Op
          | OPCODE Opcode

type Op = (Int, [Int] -> Int)
type Opcode = (Op, [Expr])


eval :: Expr -> Int
eval e = eval_1 e [] []

eval_1 :: Expr -> [Expr] -> [Int] -> Int
eval_1 (Const n)             []     _  = n
eval_1 _                     []     [] = 0
eval_1 (Const n)             (e:s1) s2 = eval_1 e s1 (n:s2)    -- Const
eval_1 (OP (argc, f))        (e:s1) s2 = eval_1 e s1 ((f (take argc s2)):(drop argc s2))    -- Op
eval_1 (OP (argc, f))        []     s2 = f (take argc s2)    -- Op
eval_1 (OPCODE (op, a:args)) s1     s2 = eval_1 a (args ++ ((OP op):s1)) s2    -- Opcode