SECD マシン(Haskell 版)
Haskell のパターンマッチを使って SECD マシンを書く。
Lisp のコンスセルは、任意の Lisp のデータを対にした構造。Haskell のリストと Lisp のコンスセルは(わたしの理解が間違っていなければ)ちょっと違う。型で言うと、以下の通り。
(:) :: a -> [a] -> [a] -- Haskell のコンス head :: [a] -> a tail :: [a] -> [a] Cons :: LispVal -> LispVal -> LispVal -- Lisp のコンス car :: LispVal -> LispVal cdr :: LispVal -> LispVal
で、コンスセルさえできれば、パターンマッチで SECD マシンが書けるはず。以下その途中。
module Main where import System.Environment data LispVal = Symbol String | Nil | Cons LispVal LispVal | Number Integer | String String | Bool Bool deriving (Eq) instance Show LispVal where show (Symbol a) = show a show (Nil) = "()" show (String a) = show a show (Number a) = show a show (Bool a) = case a of True -> "#t" False -> "#f" show (Cons a b) = case b of Nil -> "(" ++ show a ++ ")" otherwise -> "(" ++ show a ++ " . " ++ show b ++ ")" cons a b = Cons a b car (Cons a b) = a cdr (Cons a b) = b add (Number a) (Number b) = (Number (a + b)) sub (Number a) (Number b) = (Number (a - b)) list [] = Nil list (x:xs) = Cons x (list xs) sym a = (Symbol a) ldc x = (cons (sym "LDC") x) -- LDC secd s e (Cons (Cons (Symbol "LDC") n) c) d = secd s' e c d where s' = (Cons n s) -- NIL secd s e (Cons (Symbol "NIL") c) d = secd s' e c d where s' = (Cons Nil s) -- + secd (Cons a (Cons b s)) e (Cons (Symbol "+") c) d = secd s' e c d where s' = (Cons (add a b) s) -- - secd (Cons a (Cons b s)) e (Cons (Symbol "-") c) d = secd s' e c d where s' = (Cons (sub a b) s) -- LD -- TODO -- SEL -- ( (x . s) e (:SEL cT cF . c) d -> s e cX (c . d) where cX = (if x cT cF) ) secd (Cons x s) e (Cons (Symbol "SEL") (Cons ct (Cons cf c))) d = secd s e cx (Cons c d) where cx = case x of Bool True -> ct Bool False -> cf -- base secd s e c d = [s, e, c, d] -- run c = secd Nil Nil (list c) Nil
Cons だらけで読みにくいが、こんな風に動く。
*Main> run [(ldc (Number 3)), (ldc (Number 4)), (Symbol "+")] [(7),(),(),()] *Main> run [(ldc (Number 3)), (ldc (Number 4)), (ldc (Number 12)), (Symbol "+"), (Symbol "+")] [(19),(),(),()]
今のところは CL + パターンマッチで書いた方が簡潔だが、Haskell もなかなか楽しい。
続く。