5

我正在通过为comm语言实现一个简单的解释器来学习如何在 Haskell 中使用 Arrows。

我有一个 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)
4

1 回答 1

4

有两种方法可以解决未终止的问题：

  1. 从A声明data变为newtype声明。

  2. first将和的定义中的模式匹配更改left为惰性，即：

    first ~(A f) = A $ ...same as before...
left ~(A f) = A $ ...same as before...

这两个修复都解决了相同的根本问题。从另一个 StackOverflow 答案：

[使用data声明]，当与值构造函数进行模式匹配时，[thunks] 将至少被评估为弱头范式 (WHNF)。[...] [使用newtype声明，] 当模式匹配值构造函数时，[thunks] 根本不会被评估。

newtype为了继续，我将解释和声明之间的主要区别data，然后我将解释它如何应用于您的案例。

newtype和的严格性质data

以下大部分内容是从HaskellWiki 关于同一主题的文章中转述和改编的。

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 _|_计算结果为_|_（按照惯例，我_|_用来代表非终止计算“底部”）。我们可以用下面的表达式来区分_|_和：T2 _|_

\x -> case x of T2 _ -> ()

将此 lambda 应用于_|_yield _|_，但将此 lambda 应用于T2 _|_yield ()。也就是说，因为构造函数T2可能保存一个非终止值，所以语言可以区分_|_和T2 _|_。

该newtype声明为我们提供了一个可能令人惊讶的属性：T1 (unpack _|_)计算结果为_|_，但case _|_ of T1 _ -> ()计算结果为()！也就是说，由于T1 _|_不打算与 区分，因此在针对值构造函数进行模式匹配时_|_，该语言不会强制评估类型的值。而且，我们很快就会看到，这个属性对于递归定义很重要。T1T1

懒惰的模式

有一种方法可以为声明恢复类似新类型的行为data：使用惰性模式匹配。给定一个函数，如：

f x = case x of ~(T2 y) -> \() -> y

您会发现两者都f (T2 _|_)计算f _|_为一个值（即，一个类型的函数，Unit -> Int一旦应用于参数就会发散）。这是因为惰性模式匹配与函数相同：

f = \x -> case x of t -> \() -> unpack t

因此，对传递的 thunk 的评估x是“延迟的”，因为它仅在评估时unpack t评估，在 lambda 的主体中\() -> unpack t。

您的示例的新类型与数据声明

我现在将对您示例中的箭头符号进行脱糖，然后确定非终止的来源。

为了使箭头符号脱糖，我使用了arrowp程序. 这就是它在您的程序中产生的结果：

$ 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：

[使用数据声明]，当与值构造函数进行模式匹配时，[thunks] 将至少被评估为弱头范式 (WHNF)。

当first eval在 的定义中遇到表达式时eval，thunk foreval尚未计算为 WHNF，因此当first eval尝试将其参数计算为 WHNF 时，它不会终止。

解决此问题的一种方法是更改A​​为newtype声明。（“1.A从data声明变为newtype声明。”）然后，

...当与值构造函数进行模式匹配时，根本不会评估 [thunks]。

解决此问题的另一种方法是first使用惰性模式匹配而不是严格模式匹配（“2. 将定义中的模式匹配更改first为left惰性”）。这将具有使模式匹配行为与 newtype 声明相同的净效果，其中“根本不会评估 thunk”。

可以使用类似的解释来解释为什么|||您的示例没有以惰性方式表现，即使它适用于例如 Arrow 实例(->)。更改left为使用惰性模式匹配将解决此问题，或者仅使用newtype声明就足够了。

于 2019-09-08T15:05:58.587 回答