2

我已经实现了 CEK 机器。鉴于该算法的闭包结果以及该闭包是 Church 编码数字的知识，打印出数字的最佳方法是什么？

使用以下类型：

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")) [])] []
4

1 回答 1

3

Church 数字是两个参数的函数

type Church a = (a -> a) -> a -> a

第二个参数是零情况，第一个参数是增量情况。因此，您只需将数字应用于合适的几个参数即可获得一些（通常是数字）数据类型：

fromChurch c = c (+ 1) (0 :: Int)
于 2019-04-01T22:54:52.157 回答