G&O - inleveropgave 1

In deze opgave gaan we met ANTLR een parser maken die Haskell data-type definities kan ontleden. De output van de parser is een string die de definitie van een bijbehorende fold-functie voor dat datatype bevat.

Haskell datatype-definities

In Haskell/Hugs kun je binaire bomen met integers in de bladeren definieren door middel van een datatype-definitie zoals:

data Bboom = Blad Int

          | Splits Bboom Bboom

Hiermee wordt een nieuw type "Bboom" gemaakt, en twee bijbehorende constructorfuncties "Blad" en "Splits". De functie Blad maakt van een Int een Bboom, de functie Splits maakt van twee Bboom-objecten een grotere. Datatypes kunnen polymorf zijn door het gebruik van type-variabelen. Zo kun je bijvoorbeeld binaire bomen definieren met bladeren van nog niet nader bepaald type:

data PolyBoom a = Leaf a

                | Branch (PolyBoom a) (PolyBoom a)

De type-parameter a wordt hier dus gebruikt in plaats van de Int in het vorige voorbeeld. Merk op dat de type-parameter ook weer meegegeven moet worden bij het recursieve gebruik bij de parameters van Splits. Constructorfuncties hebben nul of meer parameters. Nul parameters komt bijvoorbeeld voor in als je zelf het type lijst zou willen definieren:

data Lijst a = Nil

            | Cons a (Lijst a)

Ook komt dat voor in opsommings-types zoals

data Richting = Noord | Oost | Zuid | West

Andere voorbeelden zijn het (standaard-)type "Maybe":

data MayBe a = No | Yes a

Er zijn altijd een of meer constructorfuncties. In bovenstaande voorbeelden waren het er steeds twee, behalve bij type "Richting" die vier constructoren had. Een voorbeeld van een zinvol type met een constructorfunctie is een type voor multisplitsende bomen met waardes in de interne knopen:

data MultiBoom a = Node a [MultiBoom a]

En het komt ook wel eens voor dat mensen een type als het ware inpakken. De constructorfunctie speelt dan de rol van een expliciete conversiefunctie:

data Getal = Int2Getal Int

data Inpak a = Verpak a

Al deze voorbeelden waren nog min of meer zinvol. Maar als parser-schrijver moet je natuurlijk ook voorbereid zijn op gebruikers die zich eens lekker uitleven met een type als:

data Raar a b = Een (a,b) (a->b) Int

              | Twee [a] [(a,b)] (MayBe a)

              | Drie (Raar a b) (Raar a b)

              | Vier [(Raar a b)]

              | Vijf (a, Raar a b)

              | Zes (Raar b a)

Dit type heeft twee polymorfe variabelen, gebruikt tupels, lijsten, functies, standaardtypes, en collega-datatypes; het gebruikt zichzelf recursief: in geval Drie tot en met Vijf direct, maar in geval Zes met afwijkende parameters. Moet kunnen.

Fold-functies

Iedereen kent wel de functie "foldr" die werkt op het (ingebouwde) lijst-type. Behalve een lijst-parameter heeft deze functie nog twee extra parameters: een die zegt wat er moet gebeuren in het geval van een lege lijst, en een die zegt wat er in het recursieve geval moet gebeuren:

foldr :: r -> (a->r->r) -> [a] -> r

foldr c f []     = c

foldr c f (x:xs) = f x (foldr c f xs)

Als je zelf het type Lijst hebt gemaakt (zoals in de vorige sectie), dan kun je daarvoor ook zo'n fold-achtige functie schrijven:

foldLijst :: ( r, a->r->r ) -> Lijst a -> r

foldLijst (c,f) Nil         = c

foldLijst (c,f) (Cons x xs) = f x (foldLijst (c,f) xs)

In afwijking tot de ingebouwde functie foldr hebben we hier de twee extra parameters in een tupel gestopt in plaats van ze los mee te geven. En verder is de notatie van de constructorfuncties natuurlijk anders: Cons is een functie, terwijl (:) een operator was. En Nil is een constante, terwijl [] een ingebouwde notatie voor de lege lijst was. Zo'n fold-functie is ook zinvol te definieren op andere datatypes. Bijvoorbeeld voor het hierboven gedefinieerde datatype Bboom (die we hier nog eens herhalen):

data Bboom = Blad Int

          | Splits Bboom Bboom

foldBboom :: (Int->r, r->r->r) -> Bboom -> r

foldBboom (f1,f2) (Blad n)       = f1 n

foldBboom (f1,f2) (Splits b1 b2) = f2 (foldBboom (f1,f2) b1) (foldBboom (f1,f2) b2) 

In het tupel zitten dus net zoveel functies als het datatype constructoren heeft. En als het een constructor zonder parameters is, zit er in het tupel geen functie maar een losse waarde op die plaats. Hier zijn de fold-functies voor de andere gegeven voorbeelden. Voor een PolyBoom is de definitie precies hetzelfde als voor Bboom, alleen het type is anders:

data PolyBoom a = Leaf a

                | Branch (PolyBoom a) (PolyBoom a)

foldPolyBoom :: (a->r, r->r->r) -> PolyBoom a -> r

foldPolyBoom (f1,f2) (Leaf x)       = f1 x

foldPolyBoom (f1,f2) (Branch b1 b2) = f2 (foldPolyBoom (f1,f2) b1) (foldPolyBoom (f1,f2) b2) 

De andere voorbeelden geven aan hoe je met constructoren, recursie en parameters om moet gaan:

data Richting = Noord | Oost | Zuid | West

foldRichting :: (r,r,r,r) -> Richting -> r

foldRichting (c1,c2,c3,c4) Noord = c1

foldRichting (c1,c2,c3,c4) Oost  = c2

foldRichting (c1,c2,c3,c4) Zuid  = c3

foldRichting (c1,c2,c3,c4) West  = c4

data MayBe a = No | Yes a

foldMayBe :: (r,a->r) -> MayBe a -> r

foldMayBe (f1,f2) No      = f1

foldMayBe (f1,f2) (Yes x) = f2 x

data MultiBoom a = Node a [MultiBoom a]

foldMultiBoom :: (a->[r]->r) -> MultiBoom a -> r

foldMultiBoom f (Node x ms) = f x (map (foldMultiBoom f) ms)

data Inpak a = Verpak a

foldInpak :: (a->r) -> (Inpak a) -> r

foldInpak f (Verpak x) = f x

En last but not least:

data Raar a b = Een (a,b) (a->b) Int

              | Twee [a] [(a,b)] (MayBe a)

              | Drie (Raar a b) (Raar a b)

              | Vier [(Raar a b)]

              | Vijf (a, Raar a b)

              | Zes (Raar b a)

              | Zeven (a -> (Raar a b))

foldRaar :: ( (a,b)-> (a->b)  -> Int     -> r

            , [a]  -> [(a,b)] -> MayBe a -> r

            , r    -> r                  -> r

            , [r]                        -> r

            , (a,r)                      -> r 

            , Raar b a                   -> r

            , a-> Raar a b               -> r

            ) -> Raar a b -> r

foldRaar fs@(f1,f2,f3,f4,f5,f6,f7) (Een  x1 x2 x3) = f1 x1 x2 x3

foldRaar fs@(f1,f2,f3,f4,f5,f6,f7) (Twee x1 x2 x3) = f2 x1 x2 x3 

foldRaar fs@(f1,f2,f3,f4,f5,f6,f7) (Drie x1 x2   ) = f3 (foldRaar fs x1) (foldRaar fs x2)

foldRaar fs@(f1,f2,f3,f4,f5,f6,f7) (Vier x1      ) = f4 (map (foldRaar fs) x1)

foldRaar fs@(f1,f2,f3,f4,f5,f6,f7) (Vijf (x1,x2) ) = f5 (x1,foldRaar fs x2)

foldRaar fs@(f1,f2,f3,f4,f5,f6,f7) (Zes x1       ) = f6 x1

foldRaar fs@(f1,f2,f3,f4,f5,f6,f7) (Zeven x1     ) = f7 x1

In dit voorbeeld kun je zien hoe we omgaan met de diverse parametertypes van de constructorfuncties.

1. In geval Een: het maakt eigenlijk niet uit of de parameter een simpele Int is, of een tupel, of een functie, of wat dan ook.
2. In geval Twee: ook een lijst, lijst-van-tupels etc, en andere types hoeven niet speciaal behandeld te worden
3. In geval Drie: maar bij een recursief gebruik van het eigen datatype moet de fold-functie recursief worden aangeroepen
4. In geval Vier: zit het recursieve gebruik verborgen in een lijst, dan is er een "map" nodig vcoor alle recursieve aanroepen
5. In geval Vijf: zit het recursieve gebruik verborgen in een tupel, dan is er een recursieve aanroep nodig voor een deel van het tupel
6. In geval Zes: is het recursieve gebruik van het type niet precies hetzelfde (hier vanwege de verwisselde parameters) dan mag je hem als een vreemd type beschouwen, net als MayBe
7. In geval Zeven: ook als het recursieve gebruik deel verborgen zit in een functie, hoef je het niet speciaal te behandelen (maar als je wilt mag je erover nadenken of hier niet toch iets mee gedaan kan worden)

De Haskell-faciliteit voor as-patterns (fs@...) is hier gebruikt, om bij de recursieve aanroep niet steeds weer dat hele 7-tupel te hoeven opsommen).

Specificatie van de opgave

Kopieer eerst dit startpakket (ANTLR v2 gebruikers kunnen het oude startpakket downloaden). Het bevat de volgende files:

• Een file Hasdat.g met een beginnetje van de grammatica
• Een file Voorbeeld.hs met de voorbeeld-datatypedefinities die de parser zou moeten kunnen inlezen
• Een file Main.java die ervoor zorgt dat de parser wordt aangeroepen met dat voorbeeld als invoer
• Een file Hasdat.java met een Java-klasse waarmee je een Haskell-datatype kunt representeren. Dat type is handig om als resultaat te gebruiken voor diverse parse-functies
• Een JCreator workspace- en projectfile die deze files ordent

De opgave bestaat uit de volgende onderdelen:

1. Schrijf een contextvrije grammatica die de Haskell-datatype-definities beschrijft. De parser hoeft nog niet iets bijzonders op te leveren; void is goed genoeg. Noem deze file hasdat-void.g.
   Hint 1: Types zijn een soort rekenkundige expressies, dus het lijkt op de expressie-term-factor grammatica. Bedenk zelf hoe het zit met de prioriteit van pijltje en komma in functies (a->b) en tupels (a,b).
   Hint 2: Je kunt natuurlijk ook in de Haskell-taaldefinitie kijken; daarin staat de syntax van Haskell (en dus ook van het fragment dat we nodig hebben) met een grammatica gespecificeerd. Maar pas op: er worden links-recursieve grammatica-regels gebruikt en daar kan ANTLR niet tegen. Je zult de grammatica dus nog een beetje moeten transformeren.
2. Breid de parser nu uit zodat er ook echt iets wordt opgeleverd. Voor je eigen nonterminals mag je zelf het type kiezen (maak vooral ook gebruik van de gegeven klasse in Hasdat.java!), voor het startsymbool moet er uiteindelijk een String worden opgeleverd die de bijbehorende fold-functie bevat. Je mag extra methoden schrijven in de Java-file, die je dan in de g-file weer kunt gebruiken.
   Hint: zorg ervoor dat de void-versie goed werkt, voordat je de Java-acties gaat toevoegen!
3. Inleveren: een zip-file met daarin:
• De nieuwe file Hasdat-void.g met de kale grammatica
• De aangepaste file Hasdat.g met daarin de complete parser
• De (waarschijnlijk aangepaste) file Hasdat.java
• De overige files, inclusief de door ANTLR gegenereerde parser (de gegenereerde java-files niet meer zelf editten!)