我们可以用 Haskell 来解释 lambda 演算:
data Expr = Var String | Lam String Expr | App Expr Expr
data Value a = V a | F (Value a -> Value a)
interpret :: [(String, Value a)] -> Expr -> Value a
interpret env (Var x) = case lookup x env of
Nothing -> error "undefined variable"
Just v -> v
interpret env (Lam x e) = F (\v -> interpret ((x, v):env) e)
interpret env (App e1 e2) = case interpret env e1 of
V _ -> error "not a function"
F f -> f (interpret env e2)
上述解释器如何扩展到lambda-mu演算 http://en.wikipedia.org/wiki/Lambda-mu_calculus?我的猜测是,它应该使用延续来解释该演算中的附加结构。 (15) 和 (16) 从是我所期望的翻译。
这是可能的,因为 Haskell 是图灵完备的,但如何实现呢?
Hint:请参阅第 197 页上的评论这篇研究论文 http://www.cs.ru.nl/~freek/courses/tt-2011/papers/parigot.pdfmu 绑定器的直观含义。
这是论文中归约规则的无意识音译,使用@user2407038的表示(正如你所看到的,当我说无意识时,我确实是指无意识):
{-# LANGUAGE DataKinds, KindSignatures, GADTs #-}
{-# LANGUAGE StandaloneDeriving #-}
import Control.Monad.Writer
import Control.Applicative
import Data.Monoid
data TermType = Named | Unnamed
type Var = String
type MuVar = String
data Expr (n :: TermType) where
Var :: Var -> Expr Unnamed
Lam :: Var -> Expr Unnamed -> Expr Unnamed
App :: Expr Unnamed -> Expr Unnamed -> Expr Unnamed
Freeze :: MuVar -> Expr Unnamed -> Expr Named
Mu :: MuVar -> Expr Named -> Expr Unnamed
deriving instance Show (Expr n)
substU :: Var -> Expr Unnamed -> Expr n -> Expr n
substU x e = go
where
go :: Expr n -> Expr n
go (Var y) = if y == x then e else Var y
go (Lam y e) = Lam y $ if y == x then e else go e
go (App f e) = App (go f) (go e)
go (Freeze alpha e) = Freeze alpha (go e)
go (Mu alpha u) = Mu alpha (go u)
renameN :: MuVar -> MuVar -> Expr n -> Expr n
renameN beta alpha = go
where
go :: Expr n -> Expr n
go (Var x) = Var x
go (Lam x e) = Lam x (go e)
go (App f e) = App (go f) (go e)
go (Freeze gamma e) = Freeze (if gamma == beta then alpha else gamma) (go e)
go (Mu gamma u) = Mu gamma $ if gamma == beta then u else go u
appN :: MuVar -> Expr Unnamed -> Expr n -> Expr n
appN beta v = go
where
go :: Expr n -> Expr n
go (Var x) = Var x
go (Lam x e) = Lam x (go e)
go (App f e) = App (go f) (go e)
go (Freeze alpha w) = Freeze alpha $ if alpha == beta then App (go w) v else go w
go (Mu alpha u) = Mu alpha $ if alpha /= beta then go u else u
reduceTo :: a -> Writer Any a
reduceTo x = tell (Any True) >> return x
reduce0 :: Expr n -> Writer Any (Expr n)
reduce0 (App (Lam x u) v) = reduceTo $ substU x v u
reduce0 (App (Mu beta u) v) = reduceTo $ Mu beta $ appN beta v u
reduce0 (Freeze alpha (Mu beta u)) = reduceTo $ renameN beta alpha u
reduce0 e = return e
reduce1 :: Expr n -> Writer Any (Expr n)
reduce1 (Var x) = return $ Var x
reduce1 (Lam x e) = reduce0 =<< (Lam x <$> reduce1 e)
reduce1 (App f e) = reduce0 =<< (App <$> reduce1 f <*> reduce1 e)
reduce1 (Freeze alpha e) = reduce0 =<< (Freeze alpha <$> reduce1 e)
reduce1 (Mu alpha u) = reduce0 =<< (Mu alpha <$> reduce1 u)
reduce :: Expr n -> Expr n
reduce e = case runWriter (reduce1 e) of
(e', Any changed) -> if changed then reduce e' else e
它对于论文中的示例“有效”:
example 0 = App (App t (Var "x")) (Var "y")
where
t = Lam "x" $ Lam "y" $ Mu "delta" $ Freeze "phi" $ App (Var "x") (Var "y")
example n = App (example (n-1)) (Var ("z_" ++ show n))
我可以减少example n
达到预期结果:
*Main> reduce (example 10)
Mu "delta" (Freeze "phi" (App (Var "x") (Var "y")))
我在上面的“works”周围加上引号的原因是我对 λμ 演算没有直觉,所以我不知道它应该做什么。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)