是否可以将 HOAS 函数转换为连续传递样式？

Question

注意以下Haskell程序：

-- A HOAS term, non-polymorphic for simplicity
data Term
  = Lam (Term -> Term)
  | App Term Term
  | Num Int

-- Doubles every constant in a term
fun0 :: Term -> Term
fun0 (Lam b)   = Lam (\ x -> fun0 (b x))
fun0 (App f x) = App (fun0 f) (fun0 x)
fun0 (Num i)   = Num (i * 2)

-- Same function, using a continuation-passing style
fun1 :: Term -> (Term -> a) -> a
fun1 (Lam b)   cont = undefined
fun1 (App f x) cont = fun1 f (\ f' -> fun1 x (\ x' -> cont (App f' x')))
fun1 (Num i)   cont = cont (Num (i * 2))

-- Sums all nums inside a term
summ :: Term -> Int
summ (Lam b)   = summ (b (Num 0))
summ (App f x) = summ f + summ x
summ (Num i)   = i

-- Example
main :: IO ()
main = do
  let term = Lam $ \ x -> Lam $ \ y -> App (App x (Num 1)) (App y (Num 2))
  print (summ term)                 -- prints 3
  print (summ (fun0 term))          -- prints 6
  print (fun1 term $ \ t -> summ t) -- a.hs: Prelude.undefined

这里，Term 是一个（非多态的）λ-term，带有数值常量，fun0 是一个函数，它将一个项中的所有常量加倍。是否有可能以延续传递的方式重写 fun0？换句话说，是否有可能完成 fun1 函数的 undefined 情况，使其行为与 fun0 相同，并且最后的 print 输出 6?

Answer 1

如果您试图按照通常使用的方式定义 HOAS 中的术语，那您就错了。除了在你的解释器中，你不应该在构造函数上进行模式匹配。 HOAS 中的标识如下所示：

id2 :: Term
id2 = Lam (\x -> x)

事实上，完全禁止模式匹配是很常见的，使用像

这样的接口

class HOAS t where
    lam :: (t -> t) -> t
    app :: t -> t -> t

另请注意缺少 var 大小写——因为变量始终作为 lam.

的参数提供

HOAS 中的技巧是使用 Haskell 的 lambda 来实现目标语言的 lambda，因此您基本上可以用裸 lambda 演算（加上一些额外的语法）来编写术语。

如果您必须回答您的问题，有很多方法可以做到。您的两个身份函数都不是目标语言中 lambda 演算身份函数的 HOAS 实现，而是作用于 Terms 的 Haskell 身份函数的实现。你的第一个 id0 实际上等于

id0' :: Term -> Term
id0' = id

而你的第二个正在形成等于

id1' :: Term -> (Term -> a) -> a
id1' t cont = cont t

（我认为后一种情况的严格程度会有所不同）

注意这些与Term类型无关，所以你只是无缘无故地努力工作。

我认为除了

以外的任何东西都无法填补 id1 缺失的情况

id1 (Lam b) cont = cont (Lam b)

因为 Term -> Term 没有为 a 延续结果类型提供 "escape mechanism" -- a 可能是 Term 无法表示的东西，比如IO ()。

Answer 2

如果要将此函数转换为 CPS，还需要将函数 转换为 数据类型：

data Term' a
  = Lam' (Term' a -> (Term' a -> a) -> a)
  | App' (Term' a) (Term' a)
  | Num' Int

然后你可以相应地写你的fun1：

fun1 :: Term' a -> (Term' a -> a) -> a
fun1 (Lam' b)   cont = cont (Lam' (\ x cont' -> b x cont'))
fun1 (App' f x) cont = fun1 f (\ f' -> fun1 x (\ x' -> cont (App' f' x')))
fun1 (Num' i)   cont = cont (Num' (i * 2))

并适当调整 summ:

summ' :: Term' Int -> Int
summ' (Lam' b)   = b (Num' 0) summ'
summ' (App' f x) = summ' f + summ' x
summ' (Num' i)   = i

还有一个 CPS 术语：

term' = Lam' $ \ x k -> k $ Lam' $ \ y k' -> k' $ App' (App' x (Num' 1)) (App' y (Num' 2))

你可以运行计算就好了：

> fun1 term' summ'
3

是否可以将 HOAS 函数转换为连续传递样式？

Is it possible to convert a HOAS function to continuation passing style?

haskell

continuation-passing