为什么Haskell中箭头函数的递归绑定会无限循环？
Why does recursive binding of arrow function in Haskell loop infinitely?
我正在通过为 comm 语言实现一个简单的解释器来学习如何在 Haskell 中使用箭头。
我有一个 eval 函数，可以将表达式计算为一个值，但是在输入任何表达式时 eval 会无限循环。
-- Interp.hs
eval :: A Expr Val
eval = proc e -> case e of
Lit x -> returnA -< Num x
Var s -> do
lookup -< s
Add e1 e2 -> do
v1 <- eval -< e1
v2 <- eval -< e2
case (v1, v2) of
(Num x, Num y) -> returnA -< Num (x + y)
在 GHCI 中执行此操作会导致无限循环
*Interp> unpack eval M.empty (Lit 1)
在 Add 表达式的情况下注释掉 eval 确实会导致表达式给出结果
例如
-- Interp.hs
eval :: A Expr Val
eval = proc e -> case e of
Lit x -> returnA -< Num x
Var s -> do
lookup -< s
Add e1 e2 -> do
returnA -< Num 1
-- v1 <- eval -< e1
-- v2 <- eval -< e2
-- case (v1, v2) of
-- (Num x, Num y) -> returnA -< Num (x + y)
*Interp> unpack eval M.empty (Lit 1)
(Right (Num 1),fromList [])
这是有问题的代码
使用的箭头是一种状态函数，在失败后继续传递上下文。
{-# LANGUAGE Arrows #-}
{-# OPTIONS_GHC -Wall #-}
module Interp where
import Prelude hiding (lookup, fail)
import qualified Data.Map as M
import Control.Arrow
import Control.Category
data Expr
= Lit Int
| Var String
| Add Expr Expr
deriving (Show, Eq)
data Val
= Num Int
deriving (Show, Eq)
type Env = M.Map String Val
data A b c = A { unpack :: (Env -> b -> (Either String c, Env)) }
instance Category A where
id = A (\env b -> (Right b, env))
A g . A f = A $ \env b -> case f env b of
(Left err, env') -> (Left err, env')
(Right c, env') -> g env' c
instance Arrow A where
arr f = A $ \env b -> (Right (f b), env)
first (A f) = A $ \env (b, d) -> case f env b of
(Left err, env') -> (Left err, env')
(Right c, env') -> (Right (c, d), env')
instance ArrowChoice A where
left (A f) = A $ \env e -> case e of
Left b -> case f env b of
(Left err, env') -> (Left err, env')
(Right c, env') -> (Right (Left c), env')
Right d -> (Right (Right d), env)
lookup :: A String Val
lookup = A $ \env k -> case M.lookup k env of
Nothing -> (Left "Variable not bound", env)
Just v -> (Right v, env)
eval :: A Expr Val
eval = proc e -> case e of
Lit x -> returnA -< Num x
Var s -> do
lookup -< s
Add e1 e2 -> do
v1 <- eval -< e1
v2 <- eval -< e2
case (v1, v2) of
(Num x, Num y) -> returnA -< Num (x + y)
有两种方法可以修复未终止：
- 将
A 从 data 声明更改为 newtype 声明。
将first和left定义中的模式匹配改为惰性匹配，即：
first ~(A f) = A $ ...same as before...
left ~(A f) = A $ ...same as before...
这两个修复解决了相同的根本问题。来自 another Whosebug answer:
[With data declarations], when pattern matching against value constructors, [thunks] WILL be evaluated at least to weak head normal form (WHNF). [...] [With newtype declarations,] when pattern matching against value constructors, [thunks] WILL NOT be evaluated at all.
继续，我将解释 newtype 和 data 声明之间的主要区别，然后我将解释它如何适用于您的情况。
newtype 和 data
的严格属性
以下大部分内容转述自 the HaskellWiki article on the same topic。
newtype 旨在引入一种与现有类型完全同构的类型。给定一个声明 newtype T1 = T1 { unpack :: Int }，我们希望 unpack . T1 和 id 在类型 Int -> Int 上相等，同样对于 T1 . unpack 和 id在 T1 -> T1.
类型处相等
但是为什么这不适用于 data T2 = T2 { unpack :: Int }；也就是说，为什么 T2 . unpack 与 id 不同？原因是未终止。 T2 (unpack _|_) 的计算结果为 T2 _|_，但 id _|_ 的计算结果为 _|_（我使用 _|_ 表示非终止计算 "bottom" ，按照惯例）。我们可以用下面的表达式区分_|_和T2 _|_：
\x -> case x of T2 _ -> ()
将此 lambda 应用于 _|_ 会产生 _|_，但将此 lambda 应用于 T2 _|_ 会产生 ()。也就是说，因为构造函数 T2 可能包含一个非终止值，所以该语言可以区分 _|_ 和 T2 _|_.
newtype 声明给了我们一个可能令人惊讶的 属性：T1 (unpack _|_) 的计算结果为 _|_，但 case _|_ of T1 _ -> () 的计算结果为 ()！也就是说，因为 T1 _|_ 无意与 _|_ 区分开来，所以在针对 T1 值构造函数进行模式匹配时，该语言不会强制评估类型 T1 的值。而且，我们很快就会看到，属性 对于递归定义很重要。
惰性模式
有一种方法可以为 data 声明恢复类似新类型的行为：使用惰性模式匹配。给定一个函数，如：
f x = case x of ~(T2 y) -> \() -> y
你会发现 f (T2 _|_) 和 f _|_ 的计算结果都是一个值（即 Unit -> Int 类型的函数一旦应用于参数就会发散） .这是因为惰性模式匹配与函数相同：
f = \x -> case x of t -> \() -> unpack t
因此作为 x 传递的 thunk 的评估是 "deferred" 在某种意义上它仅在评估 unpack t 时评估，在 lambda \() -> unpack t.
您的示例的新类型与数据声明
我现在将对您的示例中的箭头符号进行脱糖处理，然后确定未终止的来源。
为了去除箭头符号的糖分，我使用了 arrowp program。这是它在您的程序中产生的结果：
$ arrowp-ext interp.hs
eval :: A Expr Val
eval
= (arr
(\ e ->
case e of
Lit x -> (Left) (x)
Var s -> (Right) ((Left) (s))
Add e1 e2 -> (Right) ((Right) ((e1, e2))))
>>>
(((arr (\ x -> Num x)) >>> (returnA)) |||
(((arr (\ s -> s)) >>> (lookup)) |||
(((first ((arr (\ e1 -> e1)) >>> (eval))) >>>
(arr (\ (v1, e2) -> (e2, v1))))
>>>
(first ((arr (\ e2 -> e2)) >>> (eval))) >>>
(arr
(\ (v2, v1) ->
case
case (v1, v2) of
(Num x, Num y) -> (x, y)
of
(x, y) -> Num (x + y)))
>>> (returnA)))))
您确定 eval 在应用于参数时不会终止，但问题比这更严重：eval 发散，句号。这可以在 ghci 中观察到：
*Interp> eval `seq` 0
未终止的近端原因是表达式 first ((arr (\ e1 -> e1)) >>> (eval))，与 first eval 相同。 first 定义中的第一个参数涉及与值构造函数 (first (A f)) 的严格模式匹配，而 A 源自数据声明，因此，重新引用 @wonder.mice:
[With data declarations], when pattern matching against value constructors, [thunks] WILL be evaluated at least to weak head normal form (WHNF).
当在 eval 的定义中遇到表达式 first eval 时，eval 的 thunk 尚未计算为 WHNF，因此当 first eval 尝试时评估其对 WHNF 的参数，它不会终止。
解决此问题的一种方法是将 A 更改为 newtype 声明。 （“1. 将 A 从 data 声明更改为 newtype 声明。”）然后，
...when pattern matching against value constructors, [thunks] WILL NOT be evaluated at all.
解决此问题的另一种方法是使 first 使用惰性模式匹配而不是严格模式匹配（“2. 更改 first 和 [=19 的定义中的模式匹配=] 懒惰”）。这将使模式匹配的行为与新类型声明的行为相同，其中 "thunks WILL NOT be evaluated at all".
可以使用类似的解释来解释为什么 ||| 在您的示例中没有以懒惰的方式行事，即使它确实如此。 (->) 的 Arrow 实例。将 left 更改为使用惰性模式匹配将解决此问题，或者仅使用 newtype 声明就足够了。
我正在通过为 comm 语言实现一个简单的解释器来学习如何在 Haskell 中使用箭头。
我有一个 eval 函数，可以将表达式计算为一个值，但是在输入任何表达式时 eval 会无限循环。
-- Interp.hs
eval :: A Expr Val
eval = proc e -> case e of
Lit x -> returnA -< Num x
Var s -> do
lookup -< s
Add e1 e2 -> do
v1 <- eval -< e1
v2 <- eval -< e2
case (v1, v2) of
(Num x, Num y) -> returnA -< Num (x + y)
在 GHCI 中执行此操作会导致无限循环
*Interp> unpack eval M.empty (Lit 1)
在 Add 表达式的情况下注释掉 eval 确实会导致表达式给出结果
例如
-- Interp.hs
eval :: A Expr Val
eval = proc e -> case e of
Lit x -> returnA -< Num x
Var s -> do
lookup -< s
Add e1 e2 -> do
returnA -< Num 1
-- v1 <- eval -< e1
-- v2 <- eval -< e2
-- case (v1, v2) of
-- (Num x, Num y) -> returnA -< Num (x + y)
*Interp> unpack eval M.empty (Lit 1)
(Right (Num 1),fromList [])
这是有问题的代码
使用的箭头是一种状态函数，在失败后继续传递上下文。
{-# LANGUAGE Arrows #-}
{-# OPTIONS_GHC -Wall #-}
module Interp where
import Prelude hiding (lookup, fail)
import qualified Data.Map as M
import Control.Arrow
import Control.Category
data Expr
= Lit Int
| Var String
| Add Expr Expr
deriving (Show, Eq)
data Val
= Num Int
deriving (Show, Eq)
type Env = M.Map String Val
data A b c = A { unpack :: (Env -> b -> (Either String c, Env)) }
instance Category A where
id = A (\env b -> (Right b, env))
A g . A f = A $ \env b -> case f env b of
(Left err, env') -> (Left err, env')
(Right c, env') -> g env' c
instance Arrow A where
arr f = A $ \env b -> (Right (f b), env)
first (A f) = A $ \env (b, d) -> case f env b of
(Left err, env') -> (Left err, env')
(Right c, env') -> (Right (c, d), env')
instance ArrowChoice A where
left (A f) = A $ \env e -> case e of
Left b -> case f env b of
(Left err, env') -> (Left err, env')
(Right c, env') -> (Right (Left c), env')
Right d -> (Right (Right d), env)
lookup :: A String Val
lookup = A $ \env k -> case M.lookup k env of
Nothing -> (Left "Variable not bound", env)
Just v -> (Right v, env)
eval :: A Expr Val
eval = proc e -> case e of
Lit x -> returnA -< Num x
Var s -> do
lookup -< s
Add e1 e2 -> do
v1 <- eval -< e1
v2 <- eval -< e2
case (v1, v2) of
(Num x, Num y) -> returnA -< Num (x + y)
有两种方法可以修复未终止：
- 将
A从data声明更改为newtype声明。 将
first和left定义中的模式匹配改为惰性匹配，即：first ~(A f) = A $ ...same as before... left ~(A f) = A $ ...same as before...
这两个修复解决了相同的根本问题。来自 another Whosebug answer:
[With
datadeclarations], when pattern matching against value constructors, [thunks] WILL be evaluated at least to weak head normal form (WHNF). [...] [Withnewtypedeclarations,] when pattern matching against value constructors, [thunks] WILL NOT be evaluated at all.
继续，我将解释 newtype 和 data 声明之间的主要区别，然后我将解释它如何适用于您的情况。
newtype 和 data
的严格属性
以下大部分内容转述自 the HaskellWiki article on the same topic。
newtype 旨在引入一种与现有类型完全同构的类型。给定一个声明 newtype T1 = T1 { unpack :: Int }，我们希望 unpack . T1 和 id 在类型 Int -> Int 上相等，同样对于 T1 . unpack 和 id在 T1 -> T1.
但是为什么这不适用于 data T2 = T2 { unpack :: Int }；也就是说，为什么 T2 . unpack 与 id 不同？原因是未终止。 T2 (unpack _|_) 的计算结果为 T2 _|_，但 id _|_ 的计算结果为 _|_（我使用 _|_ 表示非终止计算 "bottom" ，按照惯例）。我们可以用下面的表达式区分_|_和T2 _|_：
\x -> case x of T2 _ -> ()
将此 lambda 应用于 _|_ 会产生 _|_，但将此 lambda 应用于 T2 _|_ 会产生 ()。也就是说，因为构造函数 T2 可能包含一个非终止值，所以该语言可以区分 _|_ 和 T2 _|_.
newtype 声明给了我们一个可能令人惊讶的 属性：T1 (unpack _|_) 的计算结果为 _|_，但 case _|_ of T1 _ -> () 的计算结果为 ()！也就是说，因为 T1 _|_ 无意与 _|_ 区分开来，所以在针对 T1 值构造函数进行模式匹配时，该语言不会强制评估类型 T1 的值。而且，我们很快就会看到，属性 对于递归定义很重要。
惰性模式
有一种方法可以为 data 声明恢复类似新类型的行为：使用惰性模式匹配。给定一个函数，如：
f x = case x of ~(T2 y) -> \() -> y
你会发现 f (T2 _|_) 和 f _|_ 的计算结果都是一个值（即 Unit -> Int 类型的函数一旦应用于参数就会发散） .这是因为惰性模式匹配与函数相同：
f = \x -> case x of t -> \() -> unpack t
因此作为 x 传递的 thunk 的评估是 "deferred" 在某种意义上它仅在评估 unpack t 时评估，在 lambda \() -> unpack t.
您的示例的新类型与数据声明
我现在将对您的示例中的箭头符号进行脱糖处理，然后确定未终止的来源。
为了去除箭头符号的糖分，我使用了 arrowp program。这是它在您的程序中产生的结果：
$ arrowp-ext interp.hs
eval :: A Expr Val
eval
= (arr
(\ e ->
case e of
Lit x -> (Left) (x)
Var s -> (Right) ((Left) (s))
Add e1 e2 -> (Right) ((Right) ((e1, e2))))
>>>
(((arr (\ x -> Num x)) >>> (returnA)) |||
(((arr (\ s -> s)) >>> (lookup)) |||
(((first ((arr (\ e1 -> e1)) >>> (eval))) >>>
(arr (\ (v1, e2) -> (e2, v1))))
>>>
(first ((arr (\ e2 -> e2)) >>> (eval))) >>>
(arr
(\ (v2, v1) ->
case
case (v1, v2) of
(Num x, Num y) -> (x, y)
of
(x, y) -> Num (x + y)))
>>> (returnA)))))
您确定 eval 在应用于参数时不会终止，但问题比这更严重：eval 发散，句号。这可以在 ghci 中观察到：
*Interp> eval `seq` 0
未终止的近端原因是表达式 first ((arr (\ e1 -> e1)) >>> (eval))，与 first eval 相同。 first 定义中的第一个参数涉及与值构造函数 (first (A f)) 的严格模式匹配，而 A 源自数据声明，因此，重新引用 @wonder.mice:
[With data declarations], when pattern matching against value constructors, [thunks] WILL be evaluated at least to weak head normal form (WHNF).
当在 eval 的定义中遇到表达式 first eval 时，eval 的 thunk 尚未计算为 WHNF，因此当 first eval 尝试时评估其对 WHNF 的参数，它不会终止。
解决此问题的一种方法是将 A 更改为 newtype 声明。 （“1. 将 A 从 data 声明更改为 newtype 声明。”）然后，
...when pattern matching against value constructors, [thunks] WILL NOT be evaluated at all.
解决此问题的另一种方法是使 first 使用惰性模式匹配而不是严格模式匹配（“2. 更改 first 和 [=19 的定义中的模式匹配=] 懒惰”）。这将使模式匹配的行为与新类型声明的行为相同，其中 "thunks WILL NOT be evaluated at all".
可以使用类似的解释来解释为什么 ||| 在您的示例中没有以懒惰的方式行事，即使它确实如此。 (->) 的 Arrow 实例。将 left 更改为使用惰性模式匹配将解决此问题，或者仅使用 newtype 声明就足够了。