Я внедрил CEK-машину.Учитывая результат замыкания из этого алгоритма и знание того, что это замыкание является цифрой, закодированной Церковью, как лучше всего распечатать цифру?
Используя следующие типы:
data Term = Var String | Abs String Term | App Term Term
data Clos = Clos String Term Env
type Env = [(String, Clos)]
РЕДАКТИРОВАТЬ: Чтобы сделать этот расплывчатый вопрос немного яснее: запуск моей машины с (\n f x -> f (n f x)) (\f x -> x) (s z), я получаю:
(\f -> (\x -> (f ((n f) x)))) :: Term
[("n", Clos((\f -> (\x -> x)), []))] :: Env
Это структура данных, представляющая замыкание, представляющее церковьцифра.Как я могу преобразовать эту структуру в число?Должен ли я пройти через окружение замыкания и подставить переменные в Term (звучит неэффективно)?Нужно ли переименование для этого?
РЕДАКТИРОВАТЬ: Фактический код:
data Term = Var String | Abs String Term | App Term Term deriving (Show)
data Clos = Clos String Term Env deriving (Show)
type Env = [(String, Clos)]
data Frame = FArg Term Env | FFun Clos deriving (Show)
data State = State Term Env [Frame] deriving (Show)
step :: State -> Maybe State
step (State (Var x) env k) = fmap (\(Clos y b env') -> State (Abs y b) env' k) $ lookup x env
step (State (App a b) env k) = return $ State a env (FArg b env : k)
step (State (Abs x b) env (FArg t env' : k)) = return $ State t env' (FFun (Clos x b env) : k)
step (State (Abs x b) env (FFun (Clos y b' env') : k)) = return $ State b' ((y, Clos x b env) : env') k
step _ = Nothing
steps :: State -> State
steps st = maybe st steps (step st)
z = Abs "f" $ Abs "x" $ Var "x"
s = Abs "n" $ Abs "f" $ Abs "x" $ App (Var "f") $ App (App (Var "n") (Var "f")) (Var "x")
term = App s z
result = steps $ State term [] []
main = putStrLn $ show result
Результаты в:
State (Abs "f" (Abs "x" (App (Var "f") (App (App (Var "n") (Var "f")) (Var "x"))))) [("n",Clos "f" (Abs "x" (Var "x")) [])] []