1

I'm playing around with Haskell and thought I'd try to create a simple programming language with it. Ignoring the concrete syntax for now; I am concentrating on the abstract syntax and the semantics.

The language currently should consist of integers, integer addition, variable names, and variable binding blocks.

If a variable is used that doesn't exist in the scope it is used, an error is raised.

The following is my current progress:

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

I am using (Runnable a) => Either [String] a as the outcome of run. Left for errors and Right for a valid result.

The following are example expressions and their expected outcome:

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

I am getting the following error from GHCI (version 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.

This error (as far as I can tell) is due to the Block's run function. It doesn't seem to like the call to Map.union.

I'm unsure what I'm doing wrong. Any ideas? Should I be attempting a completely different approach to this project?

Thanks in advance.

3 Answers 3

6

The problem is the way that run is declared.

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

What you probably intended is that the second argument is a Map from String to any runnables, mingled together in the same map. But what this actually means is that the second argument is a Map from String to one particular kind of runnable (it's just not known which it is).

Rather than using a typeclass and disparate types, try using a single type instead.

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

The only change I made to this code was the type declarations and reorganization of the run function.

If you add a dummy Num instance with fromInteger = I then you can also use integer literals as Runnables. Here's a test run with the test cases you supplied, looks like all the expected outputs match: http://ideone.com/9UbC5.

2

I think the problem is with the signature of run.

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

Particularly, run has two different type variables a and d; the only constraint on them is that they are both in Runnable. This means the function has to work for any pair of runnable types a and d. However, for blocks, this does not make sense--you cannot run a Block a with anything but a Map String a since you do your union operation. Thus your implementation for run is not as general as the type signature wants it to be--your implementation implies that the a in Block a is the same as the different variable a1 in Map String a1, but the type of run leaves you no way to enforce this.

You can actually fix this with multi-parameter typeclasses and make the fact that the a in Block a has to be the same as the type of the Map explicit. In fact, this may be a good learning exercise to understand multi-parameter typeclasses (which are exactly what they sound like but also really cool). However, the best solution would be to rewrite your code not to use typeclasses here at all--use an algebraic dtta type to represent your abstract syntax instead. This is the most common and most convenient way to represent abstract syntaxes in Haskell.

2

You miss Show a constraint. If you put your run outside of instance declaration (I renamed it to xrun) like this

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 says that

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

But it's not enough to fix the constraint. Put two types side by side (the one in class declaration and actual type of xrun:

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

The difference is that your class promises that given d your run should work for any runnable a. But xrun doesn't fullfill this requirement: if d is Block Int, it cannot work with arbitrary a, but only with a :: Int.

So as other commenters said you probably need to change your class declaration. One approach could be existential types:

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

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

This is a different contract: now the Map can contain runnables of different types. Here is the full solution:

{-# 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

Test like this:

run (Block (fromList [("a", AnyRunnable 10)]) (Name "a")) Map.empty

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.