为什么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
data
declarations], when pattern matching against value constructors, [thunks] WILL be evaluated at least to weak head normal form (WHNF). [...] [Withnewtype
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
声明就足够了。