Haskell中的迷你编程语言

Question

我正在玩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的运行功能.它似乎不喜欢这个号召Map.union.

我不确定我做错了什么.有任何想法吗？我应该尝试一种完全不同的方法来进行这个项目吗？

提前致谢.

Answer 1

问题run是声明的方式.

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

你可能想要的是第二个参数是Map从一个 runnables String到一个 runnables,在同一个map中混合在一起.但是,这实际上意味着,第二个参数是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.