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 もなかなか楽しい。

続く。