1

我正在玩 Haskell，并认为我会尝试用它创建一种简单的编程语言。现在忽略具体的语法；我专注于抽象语法和语义。

当前的语言应该由整数、整数加法、变量名和变量绑定块组成。

如果使用的变量在其使用的范围内不存在，则会引发错误。

以下是我目前的进展：

module ProgLang where
import Data.Map as Map

--  Classes
class Runnable d where
  run :: (Runnable a) => d -> Map String a -> Either [String] Integer

--  Data
data Name = Name String
  deriving (Eq, Ord, Show)

data Add a b = Add a b
  deriving (Eq, Ord, Show)

data Block a = Block (Map String a) a
  deriving (Eq, Ord, Show)

--  Instances
--  Integers resolve to Right Integer
instance Runnable Integer where
  run v _ = Right v

--  For Names
--    look up their expression in the scope, then evaluate
--    if name is out of scope, raise an error
instance Runnable Name where
  run (Name n) s = which (Map.lookup n s) where
    which Nothing = Left ["Variable not in scope: " ++ n]
    which (Just v) = run v s

--  For Addition
--    Run a, Run b, Add their results
--    Raise appropriate errors where necessary
instance (Runnable a, Show a, Runnable b, Show b) => Runnable (Add a b) where
  run (Add a b) s = geta (run a s) where
    geta (Left es) = Left (es ++ ["In lhs of expression: " ++ show (Add a b)])
    geta (Right a') = getb a' (run b s)
    getb _ (Left es) = Left (es ++ ["In rhs of expression: " ++ show (Add a b)])
    getb a' (Right b') = Right (a' + b')

--  For Blocks
--    Run the block's expression under a new scope
--      (merging the current with the block's scope definition)
instance Runnable a => Runnable (Block a) where
  run (Block s' e) s = result $ run e (Map.union s' s) where
    result (Left es) = Left (es ++ ["In block: " ++ show (Block s' e)])
    result (Right v) = Right v

我正在(Runnable a) => Either [String] a使用run. Left对于错误和Right有效结果。

以下是示例表达式及其预期结果：

--  run 5 Map.empty
--  => Right 5

--  run (Name "a") Map.empty
--  => Left ["Variable not in scope: a"]

--  run (Name "a") (fromList [("a", 6)])
--  => Right 6

--  run (Add 6 3) Map.empty
--  => Right 9

--  run (Add (Name "a") 7) (fromList [("a", 10)])
--  => Right 17

--  run (Block (fromList [("a", 10)]) (Name "a")) Map.empty
--  => Right 10

我从 GHCI（版本 7.4.1）收到以下错误：

progLang.hs:45:53:
    Could not deduce (a1 ~ a)
    from the context (Runnable a)
      bound by the instance declaration at progLang.hs:44:10-41
    or from (Runnable a1)
      bound by the type signature for
                 run :: Runnable a1 =>
                        Block a -> Map String a1 -> Either [String] Integer
      at progLang.hs:(45,3)-(47,30)
      `a1' is a rigid type variable bound by
           the type signature for
             run :: Runnable a1 =>
                    Block a -> Map String a1 -> Either [String] Integer
           at progLang.hs:45:3
      `a' is a rigid type variable bound by
          the instance declaration at progLang.hs:44:19
    Expected type: Map String a1
      Actual type: Map String a
    In the second argument of `union', namely `s'
    In the second argument of `run', namely `(union s' s)'
Failed, modules loaded: none.

这个错误（据我所知）是由于 Block 的 run 功能造成的。它似乎不喜欢调用Map.union.

我不确定我做错了什么。有任何想法吗？我应该尝试对这个项目采用完全不同的方法吗？

提前致谢。

4

3 回答 3

6

问题是run声明的方式。

run :: (Runnable a) => d -> Map String a -> Either [String] Integer

您可能想要的是第二个参数是Map从String到任何可运行文件，在同一个地图中混合在一起。但这实际上意味着第二个参数是Map从String到一种特定类型的可运行文件（只是不知道它是哪一种）。

不要使用类型类和不同的类型，而是尝试使用单一类型。

module ProgLang where
import Data.Map as Map

data Runnable
  = Name String
  | Add Runnable Runnable
  | Block (Map String Runnable) Runnable
  | I Integer
  deriving (Eq, Ord, Show)

run :: Runnable -> Map String Runnable -> Either [String] Integer
--  Instances
--  Integers resolve to Right Integer
run (I v) _ = Right v
--  For Names
--    look up their expression in the scope, then evaluate
--    if name is out of scope, raise an error
run (Name n) s = which (Map.lookup n s) where
  which Nothing = Left ["Variable not in scope: " ++ n]
  which (Just v) = run v s
--  For Addition
--    Run a, Run b, Add their results
--    Raise appropriate errors where necessary
run (Add a b) s = geta (run a s) where
  geta (Left es) = Left (es ++ ["In lhs of expression: " ++ show (Add a b)])
  geta (Right a') = getb a' (run b s)
  getb _ (Left es) = Left (es ++ ["In rhs of expression: " ++ show (Add a b)])
  getb a' (Right b') = Right (a' + b')
--  For Blocks
--    Run the block's expression under a new scope
--      (merging the current with the block's scope definition)
run (Block s' e) s = result $ run e (Map.union s' s) where
  result (Left es) = Left (es ++ ["In block: " ++ show (Block s' e)])
  result (Right v) = Right v

我对这段代码所做的唯一更改是run函数的类型声明和重组。

如果您添加一个虚拟Num实例，fromInteger = I那么您也可以将整数文字用作Runnables。这是您提供的测试用例的测试运行，看起来所有预期的输出都匹配：http: //ideone.com/9UbC5。

于 2012-09-08T16:12:05.283 回答
2

我认为问题出在run.

class Runnable d where
  run :: Runnable a => d -> Map String a -> Either [String] Integer

特别是，run有两个不同的类型变量a和d；对它们的唯一限制是它们都在Runnable. 这意味着该函数必须适用于任何一对可运行类型a和d. 但是，对于块，这没有意义——Block a除了 a 之外，您不能运行 a ，Map String a因为您执行联合操作。因此，您的实现run并不像类型签名所希望的那样通用——您的实现意味着ain与in的不同变量Block a相同，但类型使您无法强制执行此操作。a1Map String a1run

实际上，您可以使用多参数类型类来解决这个问题，并使ainBlock a必须与Map显式类型相同。事实上，这可能是理解多参数类型类的一个很好的学习练习（这正是它们听起来的样子，但也很酷）。但是，最好的解决方案是重写您的代码以完全不使用类型类——使用代数 dtta 类型来表示您的抽象语法。这是在 Haskell 中表示抽象语法的最常见和最方便的方式。

于 2012-09-08T16:15:04.797 回答
2

你错过了Show a约束。如果你把你的run外部实例声明（我将它重命名为xrun）像这样

xrun (Block s' e) s = result $ run e (Map.union s' s) where
    result (Left es) = Left (es ++ ["In block: " ++ show (Block s' e)])
    result (Right v) = Right v

ghci说

*ProgLang> :t xrun
xrun
  :: (Show a, Runnable a) =>
     Block a -> Map String a -> Either [[Char]] Integer

但仅仅修复约束是不够的。并排放置两种类型（类声明中的一种和实际类型xrun：

 run ::         (Runnable a) => d       -> Map String a -> Either [String] Integer
xrun :: (Show a, Runnable a) => Block a -> Map String a -> Either [String] Integer

不同之处在于，您的班级承诺d您run应该为任何可运行的a. 但xrun不能满足这个要求：如果d是Block Int，它不能与任意一起使用a，而只能与a :: Int.

因此，正如其他评论者所说，您可能需要更改您的类声明。一种方法可能是存在类型：

data AnyRunnable = forall a . (Runnable a) => AnyRunnable a 

class Runnable d where
    run :: d -> Map String AnyRunnable -> Either [String] Integer

这是一个不同的合约：现在Map可以包含不同类型的可运行文件。这是完整的解决方案：

{-# LANGUAGE ExistentialQuantification #-}
module ProgLang where
import Data.Map as Map

data AnyRunnable = forall a . (Runnable a) => AnyRunnable a 

instance Show AnyRunnable where
    show (AnyRunnable a) = show a

instance Runnable AnyRunnable where
    run (AnyRunnable a) = run a

--  Classes
class Show d => Runnable d where
   run :: d -> Map String AnyRunnable -> Either [String] Integer

--  Data
data Name = Name String
  deriving (Show)

data Add a b = Add a b
  deriving (Show)

data Block a = Block (Map String AnyRunnable) a
  deriving (Show)

--  Instances
--  Integers resolve to Right Integer
instance Runnable Integer where
  run v _ = Right v


--  For Names
--    look up their expression in the scope, then evaluate
--    if name is out of scope, raise an error
instance Runnable Name where
  run (Name n) s = which (Map.lookup n s) where
    which Nothing = Left ["Variable not in scope: " ++ n]
    which (Just v) = run v s

--  For Addition
--    Run a, Run b, Add their results
--    Raise appropriate errors where necessary
instance (Runnable a, Show a, Runnable b, Show b) => Runnable (Add a b) where
  run (Add a b) s = geta (run a s) where
    geta (Left es) = Left (es ++ ["In lhs of expression: " ++ show (Add a b)])
    geta (Right a') = getb a' (run b s)
    getb _ (Left es) = Left (es ++ ["In rhs of expression: " ++ show (Add a b)])
    getb a' (Right b') = Right (a' + b')

--  For Blocks
--    Run the block's expression under a new scope
--      (merging the current with the block's scope definition)
instance Runnable a => Runnable (Block a) where
  run (Block s' e) s = result $ run e (Map.union s' s) where
    result (Left es) = Left (es ++ ["In block: " ++ show (Block s' e)])
    result (Right v) = Right v

像这样测试：

run (Block (fromList [("a", AnyRunnable 10)]) (Name "a")) Map.empty
于 2012-09-08T16:01:05.997 回答