Nullable attribute of a language grammar howto
The following is my first attempt at specifying a language grammar. The method of specification is to define an algebra for the grammar expression. This algebra is GramExpr with constants from enums ArithInp and ArithVar. The functions correspond to the choice and concatenation operators in compiler texts. Specification of grammar worked OK, as shows by the successful compile of all the prints for each expression as well as the successful print of the list of GramProd's. However, when I tried to calculate the Nullable attributes of the expressions, I ran into problems. What I wanted to do was execute a homomorphism from the grammar expressions to another algebra, the GramNull algebra. This GramNull algebra will eventually produce a set of recursive equations corresponding to the grammar productions. The solution of these equations will calculate whether a non-terminal (a member of the enum ArithVar) can derive the empty string. Would someone please let me know what I'm doing wrong or suggest a better way of calculating the Nullable attribute of the non-terminals. Eventually, I'd like to calculate the First and Follow attributes in a similar way. The source file is: <--- gram_alg.hs --- {- Purpose: Algebraic specification of language grammar. -} module Main where data ArithInp = Ident | Plus | Mult | ParenLeft | ParenRight deriving(Enum,Show) data ArithVar = Term | Factor | Expr deriving(Enum,Show) data GramExpr inp_type var_type --Grammar Expresson, i.e. the rhs of a production. = NullExpr --the empty string, i.e. the epsilon in Compiler texts. | InpExpr inp_type --a terminal, i.e. an inp_type, is a Grammar Expression | VarExpr var_type --a non-terminal, i.e. a var_type, is a Grammar Expression | (:|) (GramExpr inp_type var_type) (GramExpr inp_type var_type) {- :| is the choice grammar operator. E.g. input, i, matches x | y if i either matches x or y. -} | (:>>) (GramExpr inp_type var_type) (GramExpr inp_type var_type) {- :>> is the concatenation grammar operator. E.g. input, i, matches x :>> y if i matches x followed by y. -} deriving(Show) data GramProd inp_type var_type = (:==) var_type (GramExpr inp_type var_type) deriving(Show) data GramNull inp_type var_type = OneNull --can derive empty string, | ZeroNull --can't derive empty string. | VarNull var_type --unknow whether var_type can derive empty string | AltNull (GramNull inp_type var_type) (GramNull inp_type var_type) | CatNull (GramNull inp_type var_type) (GramNull inp_type var_type) deriving(Show) expr2null :: (GramExpr inp_type var_type) -> (GramNull inp_type var_type) {- expr2null GramExpr returns a GramNull expression which indicates whether the GramExpr can derive the empty string. -} expr2null NullExpr = OneNull expr2null (InpExpr inp_valu) = ZeroNull::(GramNull inp_type var_type) expr2null (VarExpr var_valu) = (VarNull var_valu)::(GramNull inp_type var_type) main = do { print Ident ; print Expr ; print (InpExpr Ident::GramExpr ArithInp ArithVar) ; print (VarExpr Expr::GramExpr ArithInp ArithVar) ; print ((InpExpr Ident :| VarExpr Factor)::GramExpr ArithInp ArithVar) ; print ((InpExpr Ident :>>VarExpr Factor)::GramExpr ArithInp ArithVar) ; print ((Factor :== InpExpr Ident)::GramProd ArithInp ArithVar) ; print ([ Factor :== ( InpExpr Ident :| ( InpExpr ParenLeft :>> VarExpr Expr :>> InpExpr ParenRight ) ) , Term :== ( VarExpr Factor :>> InpExpr Mult :>> VarExpr Factor ) , Expr :== ( VarExpr Term :>> InpExpr Plus :>> VarExpr Term ) ] ::[GramProd ArithInp ArithVar]) {- The above arg to print is the arithmetic expression grammar. -} ; print ((expr2null (InpExpr Mult))::(GramNull ArithInp ArithVar)) ; print ((expr2null (VarExpr Factor))::(GramNull ArithInp ArithVar)) ;}
--- gram_alg.hs --- The compile output is: <--- gram_alg.compile --- Compilation started at Mon Sep 1 11:02:19
make -k runghc -XMultiParamTypeClasses -XPatternSignatures gram_alg.hs gram_alg.hs:62:40: Couldn't match expected type `var_type1' against inferred type `var_type' `var_type1' is a rigid type variable bound by the polymorphic type `forall inp_type var_type1. GramNull inp_type var_type1' at gram_alg.hs:62:31 `var_type' is a rigid type variable bound by the type signature for `expr2null' at gram_alg.hs:53:32 In the first argument of `VarNull', namely `var_valu' In the expression: (VarNull var_valu) :: GramNull inp_type var_type In the definition of `expr2null': expr2null (VarExpr var_valu) = (VarNull var_valu) :: GramNull inp_type var_type make: *** [all] Error 1
--- gram_alg.compile ---
TIA. -regards, Larry
The bit about a "rigid type variable" is usually a sign that one has been overly zealous in one's type annotations. Removing just two annotations allows the code to compile. -- _jsn |...overly zealous...| http://www.haskell.org/pipermail/haskell-cafe/2008-June/thread.html#44617 |...just two...| --- /Users/jsn/Old.hs 2008-09-01 10:50:22.000000000 -0700 +++ /Users/jsn/New.hs 2008-09-01 10:51:42.000000000 -0700 @@ -58,8 +58,8 @@ -} expr2null NullExpr = OneNull -expr2null (InpExpr inp_valu) = ZeroNull::(GramNull inp_type var_type) -expr2null (VarExpr var_valu) = (VarNull var_valu)::(GramNull inp_type var_type) +expr2null (InpExpr inp_valu) = ZeroNul +expr2null (VarExpr var_valu) = VarNull var_valu main = do print Ident
Jason beat me, but I can elaborate on the matter: Am Montag, 1. September 2008 18:22 schrieb Larry Evans:
expr2null :: (GramExpr inp_type var_type) -> (GramNull inp_type var_type) {- expr2null GramExpr returns a GramNull expression which indicates whether the GramExpr can derive the empty string. -}
expr2null NullExpr = OneNull expr2null (InpExpr inp_valu) = ZeroNull::(GramNull inp_type var_type) expr2null (VarExpr var_valu) = (VarNull var_valu)::(GramNull inp_type var_type)
The type variables from the pattern signatures are NOT those from the type signature of expr2null, they are fresh type variables. So your pattern signatures actually say that expr2null (InpExpr inp_valu) has type GramNull a b, for all types a and b. If you omit the patterns signatures, the type checker determines that they have the correct type. If you want to keep the pattern signatures (superfluous in this case, but there are situations where it's necessary), you must bring the type variables into scope. That is done by the ScopedTypeVariables language extension, best included as a LANGUAGE pragma in the source and the -then- keyword forall: expr2null :: forall inp_type var_type. GramExpr inp_type var_type -> GramNull inp_type var_type Cheers, Daniel
On 09/01/08 13:21, Daniel Fischer wrote:
Jason beat me, but I can elaborate on the matter:
Am Montag, 1. September 2008 18:22 schrieb Larry Evans:
expr2null :: (GramExpr inp_type var_type) -> (GramNull inp_type var_type) {- expr2null GramExpr returns a GramNull expression which indicates whether the GramExpr can derive the empty string. -}
[snip]
expr2null :: forall inp_type var_type. GramExpr inp_type var_type -> GramNull inp_type var_type
Cheers, Daniel
Thanks Jason and Daniel. It works beautifully. Now, I'm trying to figure how to use Functor to define expr2null (renamed to gram2null in 1st attachement). My motivation for this goal is I've read that a Functor as defined in category theory is somewhat like a homomorphism, and gram2null is, AFAICT, a homomorphism between GramExpr adn NullExpr. However, I can't figure how to do it. The 2nd attachment how an example with comments which, I hope, explains where I'm stuck. I've also looked at happy's sources and found no use of Functor; so, maybe haskell's Functor is not similar to category theory's Functor. Any help would be appreciated. -regards, Larry ------------------------------------------------------------------------ {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE PatternSignatures #-} {- Purpose: Algebraic specification of language grammar. -} module Main where data ArithInp -- terminals in grammar. = Ident | Plus | Mult | ParenLeft | ParenRight deriving(Enum,Show) data ArithVar -- non-terminals in grammar. = Term | Factor | Expr deriving(Enum,Show) data GramExpr inp_type var_type --Grammar Expresson, i.e. the rhs of a production. = GramOne --the empty string, i.e. the epsilon in Compiler texts. | GramInp inp_type --a terminal, i.e. an inp_type, is a Grammar Expression | GramVar var_type --a non-terminal, i.e. a var_type, is a Grammar Expression | (:|) (GramExpr inp_type var_type) (GramExpr inp_type var_type) {- :| is the choice grammar operator. E.g. input, i, matches x | y if i either matches x or y. -} | (:>>) (GramExpr inp_type var_type) (GramExpr inp_type var_type) {- :>> is the concatenation grammar operator. E.g. input, i, matches x :>> y if i matches x followed by y. -} deriving(Show) data GramEquation inp_type var_type = (:==) var_type (GramExpr inp_type var_type) deriving(Show) data NullableExpr inp_type var_type = NullableNot --can't derive empty string. | NullableYes --can derive empty string. | NullableVar var_type --unknown whether var_type can derive empty string. | NullableChoice (NullableExpr inp_type var_type) (NullableExpr inp_type var_type) | NullableCat (NullableExpr inp_type var_type) (NullableExpr inp_type var_type) deriving(Show) gram2null :: GramExpr inp_type var_type -> NullableExpr inp_type var_type {- gram2null GramExpr returns a NullableExpr expression which indicates whether the GramExpr can derive the empty string. -} gram2null GramOne = NullableYes gram2null (GramInp inp_valu) = NullableNot gram2null (GramVar var_valu) = NullableVar var_valu gram2null ( left :| right ) = NullableChoice (gram2null left) (gram2null right) gram2null ( left :>> right ) = NullableCat (gram2null left) (gram2null right) null_reduce :: NullableExpr inp_type var_type -> NullableExpr inp_type var_type null_reduce NullableNot = NullableNot null_reduce NullableYes = NullableYes null_reduce (NullableChoice NullableYes nullable_right) = NullableYes null_reduce (NullableChoice nullable_left NullableYes ) = NullableYes --null_reduce (NullableChoice NullableNot nullable_right) = nullable_right --null_reduce (NullableChoice nullable_left NullableNot ) = nullable_left null_reduce (NullableChoice NullableNot NullableNot ) = NullableNot null_reduce (NullableChoice nullable_left nullable_right) = NullableChoice nullable_left nullable_right null_reduce (NullableCat NullableNot nullable_right) = NullableNot null_reduce (NullableCat nullable_left NullableNot ) = NullableNot --null_reduce (NullableCat NullableYes nullable_right) = nullable_right --null_reduce (NullableCat nullable_left NullableYes ) = nullable_left null_reduce (NullableCat nullableYes NullableYes ) = NullableYes null_reduce (NullableCat nullable_left nullable_right) = NullableCat nullable_left nullable_right main = do { print Ident ; print Expr ; print (GramInp Ident::GramExpr ArithInp ArithVar) ; print (GramVar Expr::GramExpr ArithInp ArithVar) ; print ((GramInp Ident :| GramVar Factor)::GramExpr ArithInp ArithVar) ; print ((GramInp Ident :>>GramVar Factor)::GramExpr ArithInp ArithVar) ; print ((Factor :== GramInp Ident)::GramEquation ArithInp ArithVar) ; print ([ Factor :== ( GramInp Ident :| ( GramInp ParenLeft :>> GramVar Expr :>> GramInp ParenRight ) ) , Term :== ( GramVar Factor :>> GramInp Mult :>> GramVar Factor ) , Expr :== ( GramVar Term :>> GramInp Plus :>> GramVar Term ) ] ::[GramEquation ArithInp ArithVar]) {- The above arg to print is the arithmetic expression grammar. -} ; print ((gram2null (GramInp Mult))::(NullableExpr ArithInp ArithVar)) ; print ((gram2null (GramVar Factor))::(NullableExpr ArithInp ArithVar)) ; print ((gram2null (GramVar Factor :| GramOne))::(NullableExpr ArithInp ArithVar)) ; print (null_reduce ((gram2null (GramVar Factor :| GramOne))::(NullableExpr ArithInp ArithVar))) ; print (null_reduce ((gram2null (GramVar Factor :>> GramOne))::(NullableExpr ArithInp ArithVar))) ; print (null_reduce ((gram2null (GramInp Ident :>> GramOne))::(NullableExpr ArithInp ArithVar))) ;} ------------------------------------------------------------------------ {- Purpose: Demonstrate the use of Functor class to define a homomorphism between abstract data types. Motivation: In category theory, a Functor is a map from one category, Src, to another, Target. IOW, a Functor maps Src.objects to Target.objects and Src.morphisms to Target.morphisms. Since this description of Function is similar to that of an algebraic homomorphism, *maybe* a Functor can be used to define the homomorphism. -} data Alg0Type = Alg0_Op0_0 | Alg0_Op0_1 | Alg0_Op1_0 Alg0Type | Alg0_Op2_0 Alg0Type Alg0Type deriving(Show) data Alg1Type = Alg1_Op0_0 | Alg1_Op0_1 | Alg1_Op1_0 Alg1Type | Alg1_Op2_0 Alg1Type Alg1Type deriving(Show) alg0_to_alg1 :: Alg0Type -> Alg1Type --homomorphism alg0_to_alg1 Alg0_Op0_0 = Alg1_Op0_0 alg0_to_alg1 Alg0_Op0_1 = Alg1_Op0_1 alg0_to_alg1 (Alg0_Op1_0 a0) = Alg1_Op1_0 (alg0_to_alg1 a0) alg0_to_alg1 (Alg0_Op2_0 a0 a1) = Alg1_Op2_0 (alg0_to_alg1 a0) (alg0_to_alg1 a1) {- Functor Alg?Type fmap alg0_to_alg1 ? -} main = do { print Alg0_Op0_0 ; print (Alg0_Op1_0 Alg0_Op0_0) ; print (alg0_to_alg1 (Alg0_Op1_0 Alg0_Op0_0)) ; print (alg0_to_alg1 (Alg0_Op2_0 Alg0_Op0_0 Alg0_Op0_1)) }
Am Dienstag, 2. September 2008 18:30 schrieb Larry Evans:
On 09/01/08 13:21, Daniel Fischer wrote:
Jason beat me, but I can elaborate on the matter:
Am Montag, 1. September 2008 18:22 schrieb Larry Evans:
expr2null :: (GramExpr inp_type var_type) -> (GramNull inp_type var_type) {- expr2null GramExpr returns a GramNull expression which indicates whether the GramExpr can derive the empty string. -}
[snip]
expr2null :: forall inp_type var_type. GramExpr inp_type var_type -> GramNull inp_type var_type
Cheers, Daniel
Thanks Jason and Daniel. It works beautifully.
Now, I'm trying to figure how to use Functor to define expr2null (renamed to gram2null in 1st attachement). My motivation for this goal is I've read that a Functor as defined in category theory is somewhat like a homomorphism, and gram2null is, AFAICT, a homomorphism between GramExpr adn NullExpr.
You can't do that :( We have class Functor f where fmap :: (a -> b) -> f a -> f b So a Functor is a type constructor, f, which takes one type, a, as argument and from that constructs another type, f a, in such a way that for any function fun :: a -> b you can define a function (fmap fun) :: f a -> f b (generically, i.e. you can't use any special properties of fun). The type of expr2null is GramExpr a b -> GramNull a b, so there are different type constructors applied to b on the two sides of the arrow, (GramExpr a) on the left and (GramNull a) on the right, while fmap requires the same type constructor applied to possibly different types. You can make (GramExpr inp_type) a Functor like instance Functor (GramExpr i) where fmap _ GramOne = GramOne fmap _ (GramInp i) = GramInp i fmap f (GramVar v) = GramVar (f v) fmap f (a :| b) = (fmap f a) :| (fmap f b) fmap f (a :>> b) = (fmap f a) :>> (fmap f b) analogously for NullableExpr, but that's something entirely different (maybe useful, maybe not).
However, I can't figure how to do it. The 2nd attachment how an example with comments which, I hope, explains where I'm stuck.
Perhaps you're looking for something like data Alg ty = Op0_0 | Op0_1 | Op1_0 ty | Op2_0 (Alg ty) (Alg ty) deriving (Show) instance Functor Alg where fmap _ Op0_0 = Op0_0 fmap _ Op0_1 = Op0_1 fmap f (Op1_0 v) = Op1_0 (f v) fmap f (Op2_0 a b) = Op2_0 (fmap f a) (fmap f b) ?
I've also looked at happy's sources and found no use of Functor; so, maybe haskell's Functor is not similar to category theory's Functor.
It is, with the restriction that Haskell only has Endofunctors, where the source category and the target category are the same, the category of Haskell types where the morphisms are functions between those types (glossing over the fact that this is not quite accurate).
Any help would be appreciated.
-regards, Larry
participants (3)
-
Daniel Fischer -
Jason Dusek -
Larry Evans