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.

このエラー（私が知る限り）は、ブロックの実行機能が原因です。への呼び出しが気に入らないようですMap.union。

何が間違っているのかわかりません。何か案は？このプロジェクトに対してまったく異なるアプローチを試みる必要がありますか？

前もって感謝します。

4

3 に答える 3

6

問題は、run宣言される方法です。

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

おそらくあなたが意図したのは、2番目の引数がMapfromStringから任意の実行可能ファイルであり、同じマップ内で混ざり合っているということです。しかし、これが実際に意味するのは、2番目の引数がMapfromStringから1つの特定の種類の実行可能であるということです（それがどれであるかは不明です）。

型クラスや異種の型を使用するのではなく、代わりに単一の型を使用してみてください。

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

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

しかし、制約を修正するだけでは十分ではありません。2つの型を並べて配置します（1つはクラス宣言にあり、実際の型は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 Intaa :: Int

したがって、他のコメント提供者が言ったように、おそらくクラス宣言を変更する必要があります。1つのアプローチは、実存的なタイプである可能性があります。

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 に答える
2

問題はの署名にあると思いますrun。

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

特に、run2つの異なる型変数aとd;があります。それらに対する唯一の制約は、それらが両方ともにあるということですRunnable。これは、関数が実行可能なタイプとの任意のペアに対して機能する必要があることを意味します。ただし、ブロックの場合、これは意味がありません。和集合演算を実行するため、を実行することはできません。したがって、の実装は、型シグネチャが望むほど一般的ではありません。実装は、inがの異なる変数と同じであることを意味しますが、型によってこれを強制する方法はありません。adBlock aMap String arunaBlock aa1Map String a1run

これは実際にはマルチパラメータ型クラスで修正でき、ainは明示的なBlock a型と同じでなければならないという事実を作ることができます。Map実際、これはマルチパラメーター型クラスを理解するための良い学習演習になる可能性があります（これはまさにそのように聞こえますが、本当にクールでもあります）。ただし、最善の解決策は、ここで型クラスをまったく使用しないようにコードを書き直すことです。代わりに、代数のdtta型を使用して抽象構文を表します。これは、Haskellで抽象構文を表現するための最も一般的で最も便利な方法です。

于 2012-09-08T16:15:04.797 に答える