Opgave 5 Equationeel programmeren

Opgave 5 Equationeel programmeren Haskell, Monads en Monad¨ısch parsen

Atze van der Ploeg, J¨org Endrullis December 1, 2009

1

Inleiding Haskell

We gaan nu programmeren in de puur functionele taal Haskell. We gebruiken hiervoor de Glasgow Haskell Compiler, de populairste compiler/interpreter voor Haskell.

1.1

ghc en ghci

Source code files voor Haskell hebben de extentie .hs Om de intepreter op te starten tik je : ghci Om gelijk de functies die in een Haskell file hebt geschreven te laden doe je: ghci De interpreter lijkt een beetje op die van ocaml, maar nu heb je wel lineediting. Enkele belangrijke commando’s voor de interpreter zijn: • :t <expressie> print het type van expressie. • :r herlaad de file die je meegegeven hebt aan ghci. Om een Haskell programma te compileren doe je: ghc -o De file moet dan een functie main hebben, dat is het beginpunt van het programma. Om ervoor te zorgen dat ghc gelijk ook alle files die je importeert compileert doe je: ghc --make -o

1

1.2

Syntactische verschillen met ocaml

De taal Haskell lijkt op het eerste gezicht een beetje op ocaml, maar met wat kleine syntactische verschillen: • In plaats van ; als scheidingsteken in lijsten schrijven we in Haskell ,. Dus bijvoorbeeld de lijst: [ 1 , 3, 5, 9] • In ocaml beginnen typenamen zoals int met een kleine letter, in Haskell beginnen ze met een grote letter, dus bijvoorbeeld Int. • De : betekent in ocaml “heeft het type van”, hiervoor gebruiken we in Haskell :: In ocaml schrijven we dus bijvoorbeeld: 1 : int In Haskell schrijven we: 1 :: Int • In ocaml schrijven we de “Cons” operator voor lijsten als ::, in Haskell schrijven we :. In ocaml schrijven we dus bijvoorbeeld: 1::[3;5;6] In Haskell schrijven we: 1:[3,5,6] • In plaats van match ... with schrijven we in Haskell case ... of: In ocaml schrijven we dus bijvoorbeeld: match lijst with [] -> 0 h::t -> 1 In Haskell schrijven we:

case lijst of [] −> 0 h:t −> 1 • In Haskell schrijven we geen rec voor recursieve functies, de compiler zoekt zelf uit of een functie recursief is. • Als we een top-level functie in Haskell defineren schrijven we er geen let voor. In ocaml schrijven we dus bijvoorbeeld: 2

let plus x y = x + y In Haskell schrijven we: plus x y = x + y Als we in de interpreter een functie willen defini¨eren schrijven we er wel let voor. • Als we in Haskell meerdere let expressies na elkaar doen dan schrijven maar 1 keer let en maar 1 keer in. In ocaml schrijven we dus bijvoorbeeld: let telKwadratenOp x y = let xKwadraat = x * x in let yKwadraat = y * y in xKwadraat + yKwadraat In Haskell schrijven we: telKwadratenOp x y = let xKwadraat = x * x yKwadraat = y * y in xKwadraat + yKwadraat • Waar we in ocaml fun x -> fun y -> fun z -> expressie schrijven, schrijven we in Haskell (\x y z -> expressie). De \ betekent hier een λ. Dit is overigens dezelfde notatie als in lambdamonkey. • In Haskell kunnen we naast let ook where gebruiken. We kunnen het vorige voorbeeld bijvoorbeeld ook zo opschrijven: telKwadratenOp x y = xKwadraat + yKwadraat where xKwadraat = x * x yKwadraat = y * y Let wel op dat where alleen maar in functies met namen werkt, we kunnen dus bijvoorbeeld niet schrijven: (\x y −> x + y where xKwadraat = x * x yKwadraat = y * y ) • In Haskell is whitespace ook code. In de meeste programmeertalen, zoals bijvoorbeeld Java en OCaml, maakt hoever je insprint en waar je newlines zet niet uit. Bijvoorbeeld het volgende Java programmatje: 3

class Test{ public static void main(String[] argv){ if (true) then { System.out.printf("Waar"); } else { System.out.printf("Niet waar"); } } } Hadden we in Java ook zonder whitespace kunnen schrijven: class Test{public static void main(String[] argv){if(true)then{System.out. printf("Waar");}else{System.out.printf("Niet waar");}}} In Haskell maakt het wel uit hoe ver je inspringt en of je een newline ergens zet. Bijvoorbeeld het volgende stukje Haskell code: isEmpty list = case list of [] −> True h:t −> False Dat kunnen we niet zonder whitespace schrijven zoals in Java. De Haskell compiler ziet namelijk waar het volgende case-geval begint door de newline. Het is belangrijk dat je voor het inspringen niet tab-tekens en spaties door elkaar gebruikt. Als we het vorige stukje Haskell code dus bijvoorbeeld als volgt opschrijven: isEmpty list = case list of [] −> True h:t −> False Dan ziet het er in je editor goed uit als de editor 4 spaties voor een tab laat zien. Als je editor een tab als 2 spaties laat zien, dan krijg je dit: isEmpty list = case list of [] −> True h:t −> False Dit gaat dus fout: De Haskell compiler weet immers niet hoeveel spaties een tab-teken betekent, dat is afhankelijk van de editor. De makkelijkste manier om hier mee om te gaan is om je editor zo in te stellen dat hij als je op tab drukt bijvoorbeeld 4 spaties in de file zet in plaats van een tab teken. De Haskell compiler kan je waarschuwen als er tabs in je source file staat door het argument -fwarn-tabs aan ghc of ghci mee te geven. Dus bijvoorbeeld: 4

ghci -fwarn-tabs <jouw file> • In Haskell begint een commentaar van 1 regel met --, dit is hetzelfde als // in java. • Commentaar van meerdere regels begint met {- en eindigt met -}, dit is hetzelfde als /* ... */ in java. • In Haskell kunnen we aan pattern-matching doen. Dat wil zeggen dat we bijvoorbeeld kunnen schrijven: somLijst [] = 0 somLijst (eerste:rest) = eerste + (somLijst rest) De eerste definitie wordt gebruik als de lijst van de vorm [] is. Als de lijst van de vorm (eerst:rest) is dan wordt de tweede definitie gebruikt. Het bovenstaande stukje code is dus hetzelfde als: somLijst lijst = case lijst of [] −> 0 (eerste:rest) −> eerste+(somLijst rest) Als we bijvoorbeeld de definitie van een functie nulNaarEen zo hebben opgeschreven: nulNaarEen 0 = 1 nulNaarEen x = x Als we dan nulNaarEen 0 opschrijven dan zijn dus alle twee de definities van nulNaarEen mogelijk. Haskell zal dan altijd de eerste pakken. Dus de uitkomst van nulNaarEen 0 is 1. Dus als we het andersom opschrijven: nulNaarEen x = x nulNaarEen 0 = 1 Dan is de uitkomst van nulNaarEen 0 dus 0. • In Haskell schrijven we type declaraties iets anders op. Bijvoorbeeld in ocaml: type a’ tree = leaf of a’ | node of tree * int * tree In haskell schrijven we: data Tree a = Leaf a | Node Tree a Tree Een voorbeeldje waar we de bovenstaande verschillen zien: In ocaml schrijven we: 5

let telAantalVoorkomensInLijst element lijst : int->list of int->int= let hulpFunctie lijst aantalVoorkomens = match lijst with [] -> aantalVoorkomens h::t -> let plusAantalVoorkomens = if h == element then then 1 else 0 in let nieuweAantalVoorkomens = aantalVoorkomens + plusAantalVoorkomens in let resultaat = hulpFunctie t nieuweAantalVoorkomens in resultaat in hulpFunctie lijst 0

aantal1en = telAantalVoorkomensInLijst 1 [1;2;3;1;65;2] In Haskell schrijven we: telAantalVoorkomensInLijst :: Int−>[Int]−>Int telAantalVoorkomensInLijst element lijst = hulpFunctie lijst 0 where hulpFunctie [] aantalVoorkomens = aantalVoorkomens hulpFunctie (h:t) aantalVoorkomens = let plusAantalVoorkomens = if h == element then 1 else 0 nieuweAantalVoorkomens = aantalVoorkomens + plusAantalVoorkomens resultaat = hulpFunctie t nieuweAantalVoorkomens in resultaat aantal1en = telAantalVoorkomensInLijst 1 [1,2,3,1,65,2]

Opgave 1 Schrijf nu de volgende functies in Haskell: • lengte, die de lengte van een lijst van geeft. (Deze functie heet length in de standaard library van Haskell) • append, die twee lijsten achter elkaar plakt. (Deze functie heet (++) in de standaard library van Haskell) 6

• pasToeOpElkElement die als input neemt: – Een functie met 1 argument – Een lijst En die als output de lijst geeft waarbij op elk element die functie is toegepast. Dus de uitkomst van bijvoorbeeld pasToeOpElkElement (\x -> x + 2) [2,3,1] moet [4,5,3] zijn. (Deze functie heet map in de standaard library van Haskell) • verwijderAls, die als input neemt: – Een functie met 1 argument met als resultaat een Bool. – Een lijst En die als output de lijst teruggeeft waar elk element waarbij de functie True opleverde er uit gehaald is. De uitkomst van bijvoorbeeld verwijderAls (\x -> x > 5) [10,4,2,6,0] moet dan dus [4,2,0] zijn. • neem, de een getal n en een lijst neemt, en een lijst met de eerste n elementen van de lijst teruggeeft. (Deze functie heet take in de standaard library van Haskell) Het is hierbij niet toegestaan om de functies length,++,map en take te gebruiken. Zet je functies in een file IntroHaskell.hs.

Het grote verschil tussen Haskell en ocaml is dat ocaml een strict (eager) taal is en Haskell een lazy taal is. Dat wil zeggen dat ocaml de call by value reductie strategie gebruikt en Haskell de lazy reductie strategie (dit lijkt op call by need). De call by value en call by need reductie strategie¨en worden uitgelegd in hoofdstuk twee van het dictaat over lambda calculus. Praktisch gezien betekent het dat als we bijvoorbeeld de volgende functie aanroep hebben: telKwadratenOp (10 + 20 * 60) (300^2) Een stricte taal zou dan eerst de twee argumenten (10 + 20 * 60) (300^2) helemaal uitrekenen en dan de functie telKwadratenOp uitvoeren met de berekende argumenten. Dit is overgens ook de manier waarop het in alle imperatieve talen, zoals java, werkt. Een lazy taal onthoudt hoe het de argumenten kan berekenen, maar berekent de argumenten zelf niet, de uitkomst van de argumenten wordt pas berekent als de uitkomsten echt nodig zijn. Een lazy taal is dus lui : het berekent pas iets als het echt niet anders kan. Stel we hebben de functie gooiArgumentenW eg gooiArgumentenWeg x y = 1 Als we dan de volgende functie aanroep hebben: 7

gooiArgumentenWeg (faculteit 210) (60^(60^(60^120))) Dan zou een stricte taal proberen de argumenten uit te rekenen (wat ontzettend lang duurt) en dan de functie gooiArgumentenW eg aanroepen. De argumenten worden dus uitgerekend, maar dat was helemaal niet nodig. Een lazy taal zou alleen maar onthouden hoe hij de argumenten kan uitrekenen, mocht dat nodig zijn, en dat de functie gooiArgumentenW eg aanroepen, er wordt dus niks onnodig uitgerekend. Hierdoor kunnen we in Haskell ook met oneindige structuren rekenen, zoals bijvoorbeeld oneindige lijsten. De oneindige lijst met alleen maar 1en kunnen we bijvoorbeeld zo defini¨eren: oneindigVeel1en = 1:oneindigVeel1en Nu kunnen we bijvoorbeeld het eerste getal van die lijst opvragen: head oneindigVeel1en Een stricte taal zou nu proberen eerst de gehele lijst met oneindig veel 1en uit te rekenen en dan pas de functie head aanroepen. Een lazy taal zoals Haskell onthoud enkel hoe hij die lijst moet berekenen, en roept dan head aan. De functie head heeft dan het eerste van de lijst nodig, dus berekenen we net zo lang in de lijst (en niet langer) todat we weten wat het eerste element is. We kunnen bijvoorbeeld ook de eerste 100 elementen van de oneindige lijst van 1en opvragen. neem 100 oneindigVeel1en

Opgave 2 Schrijf nu de volgende dingen in Haskell: • De oneindige lijst 1, 2, 3, 4, 5, . . . • De oneindige lijst 0, 1, 0, 1, 0, 1, 0, 1, . . . • De oneindige lijst van alle 3-vouden. • De oneindige lijst van alle positieve getallen, behalve alle drievouden (hint: Gebruik verwijderAls en mod). • Een functie alleNVouden, die een getal n als input neemt en de oneindige lijst van alle n vouden teruggeeft. • Een functie allesBehalveAlleNVouden, die een getal n als input neemt en de oneindige lijst van alle positieve getallen behalve alle n vouden teruggeeft. • Een functie zonderAlleNVouden, die een getal n neem en een lijst van getallen en die de lijst zonder alle n vouden teruggeeft. 8

Zet je functies in de file IntroHaskell.hs.

Bij het vak datastructuren en algoritmen heb je al kennis gemaakt met de zeef van Eratosthenes, een algoritme om priemgetallen te berekenen. We gaan nu dit algoritme gebruiken om in Haskell de lijst van alle priemgetallen te maken. De zeef van Eratosthenes werkt als volgt: 1. We beginnen met de oneindige lijst 2, 3, 4, 5, 6, 7, . . . 2. We pakken het eerste getal uit de lijst, dat is een priemgetal, en halen alle veelvouden van dat getal weg uit de rest van de lijst. 3. We doen weer stap 2 met de rest van de lijst.

Opgave 3 Programmeer nu de oneindige lijst van priemgetallen. Zet je functie in de file IntroHaskell.hs.

2

Monads

Met monads kun je sommige dingen handiger en leesbaarder opschrijven in een puur functionele taal. In dit gedeelte leggen we uit hoe dat werkt. We beginnen met het voorbeeld MisschienEen.

2.1

MisschienEen

Bij sommige functies komt uit de functie misschien een resultaat. Voorbeelden van dit soort functies zijn: • De functie gedeeldDoor die als input neemt – Een getal, genoemd de teller. – Een getal, genoemd de noemer en als output geeft: – De teller gedeeld door de noemer. Als de noemer nul is dan het resultaat dus iets van de vorm x0 en dus is de uitkomst geen nummer. Dus deze functie heeft misschien geen resultaat. • Een functie indexV an die als input neemt: – Een lijst van verschillende getallen – Een getal en als output geeft: 9

– De index van dat getal in de lijst. Als het getal niet in de lijst voorkomt dan heeft het natuurlijk geen index. Dan hebben we dus geen resultaat. • De functie restantString die als input neemt: – Een string, genoemd x – Nog een string, genoemd y en als output geeft: – De string y waarbij de karakters uit x aan het begin zijn weggehaald. Als de string y niet begint met de string x, dan is er geen resultaat.

2.2

Het MisschienEen type

In Haskell kunnen we een type defini¨eren voor de output van dit soort functies:1

data MisschienEen resultaatType = GeenResultaat | Resultaat resultaatType hetzelfde type in Ocaml zou zijn: type resultaatType’ misschienEen = GeenResultaat | Resultaat of resultaatType’ Nu kunnen we de bovenstaande voorbeelden in Haskell opschrijven: gedeeldDoor :: Double−>Double−>MisschienEen Double gedeeldDoor teller noemer = if noemer == 0 then GeenResultaat else Resultaat (teller / noemer)

indexVan :: [Int]−>Int−>MisschienEen Int indexVan lijst getal = indexVanHulp lijst 0 where indexVanHulp lijst index = case lijst of [] −> GeenResultaat eersteGetal:restLijst −> if eersteGetal == getal then Resultaat index else indexVanHulp restLijst (n+1) 1 Dit

type is al gedefini¨ eerd in de standaard library van Haskell, daar heet het Maybe.

10

Opgave 4 Programmeer zelf de functie restantString in Haskell. In Haskell is een string een lijst van karakters (chars). Voeg je functie toe aan file MisschienEen.hs waarin het MisschienEen type en de voorbeelden staan.

2.3

Infix functies

In Haskell kunnen we een functie met twee argumenten ook infix maken, zoals +,-,*,/, dus met de naam van de functie tussen de twee argumenten. Een infix functie noemen we meestal een operator We maken nu een operator van gedeeldDoor : teller // noemer = gedeeldDoor teller noemer In plaats van gedeeldDoor 3 2 kunnen we nu dus 3 // 2 schrijven. Als voorbeeld van het gebruik van de // operator gaan we nu de volgende functie implementeren: f (x, y, z) =

x y

z Deze functie levert natuurlijk geen resultaat als y == 0 of z == 0. We programmeren dit als volgt: f :: Double−>Double−>Double−>MisschienEen Double f x y z = case x // y of GeenResultaat −> GeenResultaat Resultaat xGedeeldDoory −> case xGedeeldDoory // z of GeenResultaat −> GeenResultaat Resultaat resultaat −> Resultaat resultaat Dus als x // y geen resultaat heeft, dan heeft de hele functie geen resultaat. En als xGedeeldDoory // z geen resultaat heeft dan ook niet. Aangezien xGedeeldDoory // z zelf al iets van type MisschienEen Double oplevert kunnen we het natuurlijk ook als volgt opschrijven: fKorter :: Double−>Double−>Double−>MisschienEen Double fKorter x y z = case x // y of 11

GeenResultaat −> GeenResultaat Resultaat xGedeeldDoory −> xGedeeldDoory // z Als iets ingewikkelder voorbeeldje van het gebruik van // nemen we de functie : g(x, y, z, s) =

y s x y

+ −

z s x z

Dit implementeren we als volgt: g :: Double−>Double−>Double−>Double−>MisschienEen Double g x y z s = case x // y of GeenResultaat −> GeenResultaat Resultaat xGedeeldDoory −> case y // z of GeenResultaat −> GeenResultaat Resultaat xGedeeldDoorz −> case y // s of GeenResultaat −> GeenResultaat Resultaat yGedeeldDoors −> case z // s of GeenResultaat −> GeenResultaat Resultaat zGedeeldDoors −> let teller = yGedeeldDoors + zGedeeldDoors noemer = xGedeeldDoory − xGedeeldDoorz in teller // noemer

2.4

De >>= operator

Op deze manier zijn de functies f en g niet goed leesbaar. We herhalen telkens hetzelfde patroon , namelijk :

case ... of GeenResultaat −> GeenResultaat Resultaat ... −> ... We kunnen een operator(infix functie), >>= , voor dit patroon maken: (>>=) :: MisschienEen type1−>(type1−>MisschienEen type2)−>MisschienEen type2 linkerResultaat >>= rechterFunctie = case linkerResultaat of GeenResultaat −> GeenResultaat Resultaat nummer −> let resultaat = rechterFunctie nummer in resultaat of dezelfde functie anders opgeschreven met pattern matching:

12

(>>=) :: MisschienEen type1−>(type1−>MisschienEen type2)−>MisschienEen type GeenResultaat >>= rechterFunctie = GeenResultaat (Resultaat nummer) >>= rechterFunctie = rechterFunctie nummer Deze functie krijg een linkerResultaat aan linkerkant van de >>= van het type M isschien Double, dus bijvoorbeeld Resultaat 10.0 of GeenResultaat. type1 en type2 in de type declaratie mogen willekeurige types zijn, dus bijvoorbeeld alletwee Double. Aan de rechterkant van de >>= krijgt het een functie die als input 1 Double neemt en iets van type MisschienEen Double output. Bijvoorbeeld de functie : drieGedeeldDoor x = 3 // x Als het linkerResultaat GeenResultaat is, dan is de uitkomst van de hele functie GeenResultaat en wordt de rechterfunctie helemaal niet gebruikt. Als het van de vorm Resultaat nummer is dan wordt dan nummer als input gegeven aan de rechterfunctie en is het resultaat van de hele functie het resultaat van de rechterF unctienummer. gedeeldDoor3 x = x // 3 Deze operator >>= kunnen we nu gebruiken om f handiger op te schrijven: fBeter :: Double−>Double−>Double−>MisschienEen Double fBeter x y z = (x // y) >>= gedeeldDoorZ where gedeeldDoorZ xGedeeldDoory = xGedeeldDoory // z In plaats van gedeeldDoorZ kunnen we natuurlijk ook een anonieme (lambda) functie gebruiken: fBeterLambda :: Double−>Double−>Double−>MisschienEen Double fBeterLambda x y z = (x // y) >>= (\xGedeeldDoory −> xGedeeldDoory // z ) We kunnen g nu als volgt op schrijven: gBeter :: Double−>Double−>Double−>Double−>(MisschienEen Double) gBeter x y z s = (x // y) >>= (\xGedeeldDoory −> (x // z) >>= 13

(\xGedeeldDoorz −> let noemer = xGedeeldDoory − xGedeeldDoorz in (y // s) >>= (\yGedeeldDoors −> (z // s) >>= (\zGedeeldDoors −> let teller = yGedeeldDoors + zGedeeldDoors in teller // noemer ) ) ) ) Merk hierbij op dat als bijvoorbeeld (x // y) als uitkomst GeenResultaat heeft, dat dan de rest van de functie niet wordt uitgerekend.

2.5

Do notatie

Zo is het nog steeds niet echt leesbaar. Gelukkig heeft Haskell hier een truukje voor: In plaats van : fBeterLambda :: Double−>Double−>Double−>MisschienEen Double fBeterLambda x y z = (x // y) >>= (\xGedeeldDoory −> xGedeeldDoory // z ) kunnen we namelijk schrijven: fNogBeter :: Double−>Double−>Double−>MisschienEen Double fNogBeter x y z = do xGedeeldDoory <− x // y xGedeeldDoory // y Hierbij betekent xGedeeldDoory <- x // y: Reken x // y uit en als er GeenResultaat uitkomt dan stoppen we met verder rekenen en returnen we GeenResultaat voor de hele functie. Als er Resultaat nummer uitkomt, dan slaan we dat nummer op in de variabele xGedeeldDoory en gaan we verder met de rest van de functie. Dus als je een expressie begin met do dan vertaalt de Haskell compiler elke expressie van de vorm x <− y volgendeRegel naar 14

y >>= (\x −> volgendeRegel) Dus voor de Haskell compiler zijn f Beter0 en f N ogBeter hetzelfde. Als we een do expressie van meerdere regels hebben, bijvoorbeeld:

do x <− y p <− z r <− l laatsteRegel Dan vertaalt de Haskell compiler dit als: y >>= (\x −> z >>= (\p −> l >>= (\r −> laatsteRegel) ) )

2.6

let in do

Tussen de operaties waarbij het resultaat een M isschienEen Double is kunnen we ook operaties opschrijven die niet als resultaat een M isschienEen Double hebben. Als we bijvoorbeeld schrijven, merk hierbij op dat als we een let in een do block schrijven dat we dan geen in schrijven.:

do x <− y let r = q p <− z laatsteRegel dan vertaalt de Haskell compiler dit als: y >>= (\x −> let r = q in z >>= (\p −> laatsteRegel) ) ) Nu kunnen we g als volgt opschrijven: gNogBeter :: Double−>Double−>Double−>Double−>(MisschienEen Double) gNogBeter x y z s = do xGedeeldDoory <− x // y 15

xGedeeldDoorz <− y // z let noemer = xGedeeldDoory − xGedeeldDoorz yGedeeldDoors <− y // s zGedeeldDoors <− z // s let teller = yGedeeldDoors + zGedeeldDoors teller // noemer Nu is het eindelijk leesbaar.

2.7

return

Als we bijvoorbeeld hebben geschreven:

do x <− y laatsteRegel dan vertaalt de Haskell compiler dit dus als: y >>= (\x −> laatsteRegel) ) ) Merk hierbij op dat (\x -> laatsteRegel) het type Double -> MisschienEen Double heeft en dus een geldig tweede argument voor >>= is, want >>= heeft het type: MisschienEen Double->(Double->MisschienEen Double)->(MisschienEen Double). De laatste regel moet dus wel iets van type MisschienEen Double hebben. Bij de voorgaande twee voorbeelden f en g was de laatste regel altijd een operatie met als uitkomst een MisschienEen Double. We gaan nu uitleggen hoe de do notatie werkt als dat niet zo is. Als voorbeeld nemen we de volgende functie: p(x, y, z) =

x z + y x

Zonder de do notatie kunnen we die als volgt opschrijven: p :: Double−>Double−>Double−>Double−>(MisschienEen Double) p x y z = (x // y) >>= (\xGedeeldDoory −> (z// x) >>= (\zGedeeldDoorx −> let resultaat = xGedeeldDoory + zGedeeldDoorx in Resultaat resultaat ) ) met de do notatie lukt het nog niet:

16

p :: Double−>Double−>Double−>Double−>(MisschienEen Double) p x y z = do xGedeeldDoory <− x // y zGedeeldDoorx <− z // x let resultaat = xGedeeldDoory + zGedeeldDoorx ? De laatste regel moet immers iets van type M isschienEen Double hebben, en resultaat heeft type Double. We kunnen dit oplossen door te schrijven: pDo :: Double−>Double−>Double−>Double−>(MisschienEen Double) pDo x y z = do xGedeeldDoory <− x // y zGedeeldDoorx <− z // x let resultaat = xGedeeldDoory + zGedeeldDoorx Resultaat resultaat Nu is de laatste regel Resultaat resultaat van het type MisschienEen Double, dus nu werkt het. Om het geheel nog iets leesbaarder te maken defini¨eren we een functie return return :: Double−>MisschienEen Double return waarde = Resultaat waarde dan kunnen we schrijven: pDoReturn :: Double−>Double−>Double−>Double−>(MisschienEen Double) pDoReturn x y z = do xGedeeldDoory <− x // y zGedeeldDoorx <− z // x let resultaat = xGedeeldDoory + zGedeeldDoorx return resultaat We kunnen f en g nu ook nog iets leesbaarder opschrijven: fPerfect :: Double−>Double−>Double−>MisschienEen Double fPerfect x y z = do xGedeeldDoory <− x // y resultaat <− xGedeeldDoory // z return resultaat gPerfect :: Double−>Double−>Double−>Double−>(MisschienEen Double) gPerfect x y z s = do xGedeeldDoory <− x // y xGedeeldDoorz <− y // z let noemer = xGedeeldDoory − xGedeeldDoorz yGedeeldDoors <− y // s 17

zGedeeldDoors <− z // s let teller = yGedeeldDoors + zGedeeldDoors resultaat <− teller // noemer return resultaat

Opgave 5 Programmeer zelf de functie: v(x, y, z, s) =

x y z s

−

y s

y z −( + ) s x

Op alle drie de manieren. Dus met: •

case ... of GeenResultaat->GeenResultaat Resultaat nummer -> ...

• De >>= functie. • De do notatie plus return. Voeg je functie toe aan file MisschienEen.hs.

2.8

If in do

In de do-notatie kunnen we ook if schrijven. Als voorbeeld nemen we de volgende functie: r(x, y, z) = p + q waarin p= ( q=

x y

p<6 p≥6

y z

z

Zonder de do notatie zouden we dit schrijven: r :: Double−>Double−>Double−>(MisschienEen Double) r x y z = (x // y) >>= (\p −> let qMisschien = if p < 6 then (y //z) else Resultaat z in

18

qMisschien >>= (\q −> p + q ) ) Met de do-notatie kunnen we schrijven: r :: Double−>Double−>Double−>(MisschienEen Double) r x y z = do p <− x // y q <− if p < 6 then y // z else Resultaat z let resultaat = p + q return resultaat Of r :: Double−>Double−>Double−>(MisschienEen Double) r x y z = do p <− x // y if p < 6 then do q <− y // z let resultaat = p + q return resultaat else do let resultaat = p + z return resultaat Merk bij dit laatste stukje code op dat als je in de body van then en else weer de do-notatie wil gebruiken dat je dan weer do er voor moet zetten. Merk verder op voor de then en de else een spatie staat. Dit moet als je een if in do-notatie schrijft, anders dan snapt de compiler niet wat je bedoelt. Op exact dezelfde manier kan je ook een case expressie in de notatie gebruiken.

Opgave 6 Programmeer zelf de functie: w(x, y, z, s) = p + waarin

x−y p= z+s ( p > 10 q= p ≤ 10 19

x z z x

q s

Op alle drie de manieren. Dus met: •

case ... of GeenResultaat->GeenResultaat Resultaat nummer -> ...

• De >>= functie. • De do notatie plus return en if. Voeg je functie toe aan file MisschienEen.hs.

2.9

“Toestand”

Bij het voorbeeld van M isschienEen hebben we gezien hoe we de >>= en return functies kunnen gebruiken om niet steeds maar

case ... of GeenResultaat −> GeenResultaat Resultaat ... −> ... te schrijven. We gaan nu zien hoe we deze functies kunnen gebruiken om de toestand (state) van iets bij te houden. Als voorbeeld van “toestand” bekijken we het volgende java programmatje: class Coordinaat { int x,y; Coordinaat(int x,int y){ this.x = x; this.y = y; } void verplaats(int xVerplaats, int yVerplaats){ x += xVerplaats; y += yVerplaats; } } Elk object van het type Coordinaat heeft een “toestand” namelijk de plek waarnaar het Coordinaat object verwijst, dus de waarden van de x en y variabelen. De constructor maakt een object en zet hem in zijn “begintoestand”. Strict gezien kan iets in een puur functionele taal geen toestand hebben. Alles is, met een java-term, immutable. We kunnen wel uit een toestand een nieuwe toestand maken en die de hele tijd door geven. Als voorbeeld hiervan programmeren we het bovenstaande in Haskell:

20

data Coordinaat = Coordinaat Int Int verplaats :: Int−>Int−>Coordinaat−>Coordinaat verplaats xVerplaats yVerplaats (Coordinaat x y) = let nieuweX = x + xVerplaats nieuweY = y + yVerplaats nieuweCoordinaat = Coordinaat nieuweX nieuweY in nieuweCoordinaat We zien hierbij dat we het coordinaat niet veranderen, dat kan immers niet, maar een nieuwe coordinaat maken. Dat nieuwe coordinaat is de nieuwe “toestand” van het oude coordinaat. Als we iets twee keer willen verplaatsen dan tikken we in java: Coordinaat c = new Coordinaat(0,0); c.verplaats(1,0); c.verplaats(0,1); Als we hetzelfde willen doen in haskell dan tikken we:

let beginToestand = Coordinaat 0 0 tweedeToestand = verplaats 1 0 beginToestand derdeToestand = verplaats 0 1 tweedeToestand in derdeToestand Dus je geeft de toestand de hele tijd expliciet door. Soms heb je een functie die `en de toestand veranderd en iets teruggeeft. Bijvoorbeeld de volgende java functie verplaatsEnGaatBuitenBord in de class Coordinaat: static final int BREEDTE = 10, HOOGTE=10; bool verplaatsEnGaatBuitenBord(int verplaatsX, int verplaatsY){ verplaats(verplaatsX,verplaatsY); return isOpBord(); } bool opBord(){ return x >= 0 && x < BREEDTE && y >= 0 && y < HOOGTE; } In Haskell moet we dan expliciet de uitkomst en de nieuwe toestand teruggeven: verplaatsEnGaatBuitenBord :: Int−>Int−>Coordinaat−>(Coordinaat,Bool) verplaatsEnGaatBuitenBord verplaatsX verplaatsY beginCoordinaat= let nieuweCoordinaat = verplaats verplaatsX verplaatsY beginCoordinaat resultaat = opBord nieuweCoordinaat in (nieuweCoordinaat,resultaat) breedte = 10 hoogte = 10 opBord (Coordinaat x y) = x >= 0 && x < breedte && y >= 0 && y < hoogte 21

We gaan nu zien hoe we dit in Haskell kunnen opschrijven zonder telkens expliciet de toestand door te geven. We doen dit met behulp van de >>= en return functies en de do-notatie.

2.10

ToestandFunctie

Om het geheel leesbaarder te maken introduceren we eerst een andere naam voor Coordinaat, namelijk Toestand:

type Toestand = Coordinaat Dit is enkel een andere naam, dus overal waar we in het vervolg Toestand schrijven kunnen we net zo goed Coordinaat schrijven. Een ToestandFunctie is een functie die als input een toestand krijgt en als output de nieuwe toestand en het resultaat van de functie geeft:

data ToestandFunctie resultaatType = ToestandsFunctie (Toestand−>(Toestand,resultaatType)) Waarbij resultaatType een willkeurig ander type kan zijn, bij voorbeeld Int of Double. Iets van bijvoorbeeld het type ToestandFunctie Bool is dus een fuctie van het type Toestand->(Toestand,Bool) met de constructor ToestandFunctie ervoor. Bijvoorbeeld de functie verplaatsNoordEnGaatBuitenBordToestandFunctieTF hieronder het heeft type ToestandFunctie Bool: verplaatsNoordEnGaatBuitenBordTF :: ToestandFunctie Bool verplaatsNoordEnGaatBuitenBordTF = ToestandFunctie verplaatsNoordEnGaatBuitenBord

verplaatsNoordEnGaatBuitenBord :: Toestand−>(Toestand,Bool) verplaatsNoordEnGaatBuitenBord coordinaat = verplaatsEnGaatBuitenBord 0 1 coordinaat We zullen hieronder alle achter de namen van alle functies die toestandfuncties zijn TF zetten. Sommige functies zoals verplaats geven geen uitkomst terug. Daarvoor maken we een aparte waarde GeenUitkomst:

data GeenUitkomst = GeenUitkomst Nu kunnen we de functies verplaats en opBord als ToestandFunctie opschrijven. verplaatsTF:: Int−>Int−>ToestandFunctie GeenUitkomst verplaatsTF xVerplaats yVerplaats = ToestandFunctie (\(Coordinaat x y) −> let nieuweX = x + xVerplaats nieuweY = y + yVerplaats 22

nieuweToestand = Coordinaat nieuweX nieuweY in (nieuweToestand,GeenUitkomst) ) opBordTF :: ToestandFunctie Bool opBordTF = ToestandFunctie (\(Coordinaat x y) −> let resultaat = x >= 0 && x < breedte && y >= 0 && y < hoogte nietGewijzigdeToestand = (Coordinaat x y) in (nietGewijzigdeToestand,resultaat) )

2.11

doeToestandFunctie

De functies verplaats en opBord zijn nu ToestandFuncties. Dus we kunnen bijvoorbeeld niet meer opBord (Coordinaat 10 10) schrijven. Want opBord heeft het type ToestandFunctie Bool en niet Coordinaat->Bool. Om de toestand functies te kunnen uitvoeren defini¨eren we de functie doeT oestandF unctie: doeToestandFunctie :: ToestandFunctie uitkomstType−>Toestand−>(Toestand,uitkomstType) doeToestandFunctie (ToestandFunctie functie) beginToestand = functie beginToestand Dus schrijven we bijvoorbeeld: draaiToestandFunctie opBord (Coordinaat 10 10)

2.12

>>= voor ToestandFuncties

Nu willen we natuurlijk twee van deze ToestandFuncties achter elkaar kunnen uitvoeren. Dus we willen van twee toestands functies 1 nieuwe toestandfunctie maken, die de twee toestandsfuncties achter elkaar uitvoerd. Daarvoor defini¨eren we een implementatie van >>= voor toestand functies: (>>=) :: ToestandFunctie resultaatType1−>(resultaatType1−>ToestandFunctie resultaatType2) −>ToestandFunctie resultaatType2 (ToestandFunctie functieLinks) >>= (toestandFunctieOnthoudResultaatRechts ) = ToestandFunctie (\beginToestand −> let (tweedeToestand,resultaatLinks) = functieLinks beginToestand (ToestandFunctie functieRechts) = toestandFunctieOnthoudResultaatRechts resultaatLinks (derdeToestand,resultaatRechts) = functieRechts tweedeToestand in (derdeToestand,resultaatRechts) )

23

Merk hierbij op dat de uitkomst van de nieuwe samengestelde toestand functie de uitkomst van de tweede toestand functie is. De functie verplaatsEnGaatBuitenBord is een samengestelde functie van verplaats en opBord. Met onze nieuwe >>= implementatie kunnen we dat nu op deze manier op schrijven: verplaatsEnGaatBuitenBordTF :: Int−>Int−>ToestandFunctie Bool verplaatsEnGaatBuitenBordTF xVerplaats yVerplaats = (verplaatsTF xVerplaats yVerplaats) >>= (\geenUitkomst −> opBordTF ) Of in de do notatie: verplaatsEnGaatBuitenBordMetDoTF :: Int−>Int−>ToestandFunctie Bool verplaatsEnGaatBuitenBordMetDoTF xVerplaats yVerplaats = do geenUitkomst <− verplaatsTF xVerplaats yVerplaats opBordTF Om de return voor ToestandFuncties te kunnen gebruiken moeten we die eerst defini¨eren: return :: uitkomstType −> ToestandFunctie uitkomstType return uitkomst = ToestandFunctie (\toestand −> (toestand,uitkomst) ) Dus bijvoorbeeld return True geeft een ToestandsFunctie die de toestand met rust laat en True als uitkomst heeft. Dus bijvoorbeeld x >>= (\uitkomst x -> return True) heeft dat precies het resultaat was we willen: Een ToestandFunctie die eerst x uitvoert en vervolgens altijd True als uitkomst heeft. Nu kunnen we dus schrijven: verplaatsEnGaatBuitenBordBeterTF :: Int−>Int−>ToestandFunctie Bool verplaatsEnGaatBuitenBordBeterTF xVerplaats yVerplaats = do geenUitkomst <− verplaatsTF xVerplaats yVerplaats isOpBord <− opBordTF return isOpBord

2.13

De >> operator

In deze functie maken we een variabele voor de uitkomst van verplaats xVerplaats yVerplaats, maar de uitkomst van deze functie is altijd GeenUitkomst. We willen voor deze uitkomst dus eigenlijk helemaal geen variabele maken. Om dit te kunnen doen introduceren we de >> operator. 24

De >> operator neemt twee ToestandFuncties, voert de eerste uit, gooit zijn resultaat weg, draait de tweede toestand functie en geeft als uitkomst de uitkomst van de tweede ToestandFunctie. (>>) :: ToestandFunctie resultaatType1 −> ToestandFunctie resultaatType2 −> ToestandFunctie resultaatType2 (ToestandFunctie functie1) >> (ToestandFunctie functie2) = ToestandFunctie (\beginToestand −> let (tweedeToestand,weggooiResultaat) = functie1 beginToestand (derdeToestand, resultaat) = functie2 tweedeToestand in (derdeToestand,resultaat) ) Nu kunnen we verplaatsEnGaatBuitenBord beter opschrijven: verplaatsEnGaatBuitenBordPerfectTF :: Int−>Int−>ToestandFunctie Bool verplaatsEnGaatBuitenBordPerfectTF xVerplaats yVerplaats = (verplaatsTF xVerplaats yVerplaats) >> opBordTF De do-notatie vertaalt je do expressie met een >>= als je het resultaat van een regel onthoud, en met een >> als je dat niet doet. Dus kunnen we nu in de do-notatie opschrijven: verplaatsEnGaatBuitenBordMetDoPerfectTF :: Int−>Int−>ToestandFunctie Bool verplaatsEnGaatBuitenBordMetDoPerfectTF xVerplaats yVerplaats = do verplaatsTF xVerplaats yVerplaats isOpBord <− opBordTF return isOpBord Een ander voorbeeld hiervan is de functie verplaatsN oordW est die de coordinaat eerst naar het noorden en dan naar het westen verplaatst en als het coordinaat daarna buiten bord is dan zet hij het coordinaat in het midden van het bord (4,4). Het resultaat van de functie is of het coordinaat buiten het bord ging. verplaatsNoordWestTF :: ToestandFunctie Bool verplaatsNoordWestTF = do verplaatsTF 0 1 verplaatsTF 1 0 isOpBord <− opBordTF if isOpBord then do return GeenUitkomst else do setCoordinaatTF 4 4 return GeenUitkomst return isOpBord 25

setCoordinaatTF :: Int−>Int−>ToestandFunctie GeenUitkomst setCoordinaatTF x y = ToestandFunctie (\beginToestand −> let nieuweToestand = Coordinaat x y in (nieuweToestand,GeenUitkomst) )

Opgave 7 Programmeer zelf de functie gaOONNTF die naar het coordinaat eerst naar het oosten, dan weer naar het oosten, dan naar het noorden en dan weer naar het noorden verplaats. Voordat je een stapje doet moet je eerst kijken of je door dat stapje niet buiten het bord gaat, anders moet je het stapje niet uitvoeren. Op alle drie de manieren. Dus met: • Het steeds expliciet doorgeven van de Toestand. • De >>= en >> functies. • De do notatie plus return en if. Je mag hierbij gebruik maken van de al gedefin¨ıeerde functies zoals verplaats. Voeg dit toe aan de file ToestandFunctie.hs.

2.14

Pure functies

In een puur functionele taal zoals haskell kunnen we alleen maar pure functies opschrijven. Een eigenschap van pure functies is dat elke keer als je hem uitrekent met dezelfde input er altijd dezelfde output uit moet komen. Als voorbeeld van een functie met deze eigenschap nemen we de cosinus. Elke keer als je bijvoorbeeld cos(0) uitrekent komt er 1 uit. Het zou toch erg verwarrend zijn als er soms iets anders uit komt. In imperatieve talen kunnen wel functies opschrijven waarbij met dezelfde input er soms iets anders uitkomt. Enkele voorbeelden in java hiervan zijn: • Scanner.next(), elke keer als je deze aanroept komt er iets anders uit, namelijk de volgende token op de input. • Math.random(), • De java functie verplaatsEnGaatBuitenBord van hierboven. De uitkomst is afhankelijk van de huidige toestand van het Coordinaat object.

26

Een andere eigenschap van een pure-functie is dat hij geen side-effects heeft. Dat wil zeggen dat enkel de uitkomst wordt uitgerekend en er verder niks gebeurt. Als voorbeeld van een functie zonder side-effects nemen we weer de cosinus. Als we deze uitvoeren, berekenen we enkel het resultaat en gebeurt er verder niks. Je zou toch raar staan te kijken als elke keer als je de cosinus uitvoert er nog iets anders gebeurt. In imperatieve talen kunnen wel functies met side-effects opschrijven. Enkele voorbeelden in java hiervan zijn: • printf : Er wordt bij deze functie helemaal geen resultaat uitgerekent maar enkel iets op de output geprint , dat is een side-effect. • variableN aam = waarde, Als we dit opschrijven in java dan is de uitkomst gewoon waarde, daarom kunnen we bijvoorbeeld x = y = waarde opschrijven in java. Er gebeurt echter nog iets: De variable krijgt een nieuwe waarde. • De java functie verplaats en verplaatsEnGaatBuitenBord, het side-effect is hierbij dat het coordinaat verplaatst wordt. • Scanner.next(), als je deze aanroept dan wordt als side-effect de index in de stream gewijzigd. • sleep(tijd), als side-effect wacht je een tijdje.

2.15

IO

Eigenlijk is bijna elke functie in een imperatieve taal zoals java dus onpuur. De vraag is nu: hoe doen we dit soort dingen in een puur functionele taal?

Voor de functies verplaats en verplaatsEnGaatBuitenBord heb je het hierboven al gezien. De oplossing is dat je steeds de toestand meegeeft en dat je de nieuwe toestand met de uitkomst mee geeft.

Voor input/output operaties gebruiken we eigenlijk hetzelfde truukje. De toestand die we dan telkens meegeven is de “toestand van de hele wereld”. Wat voorbeelden hiervan zijn: • Als je schrijfoperatie naar een file doet, dan verander je de toestand van de hele wereld, er staat nu namelijk iets anders op je hardeschijf. • Als je een leesoperatie uit een file doet, dan verander je de toestand van de hele wereld, de arm van je harde schijf staat namelijk anders. • Als je een berichtje stuurt via internet, dan verander je ook de toestand van de hele wereld, er zit nu namelijk een nieuw pakketje ergens in het wereldwijde netwerk. • Als je een opdracht geeft om je CPU-koeler harder laat draaien, dan verander je ook de toestand van de hele wereld, de CPU-koeler draait nu namelijk harder. 27

• Als je een opdracht geeft om je DVD-lade open te doen, dan verander je ook de toestand van de hele wereld, de DVD-lade is nu namelijk open. De toestand van “de hele wereld” modelleren we in Haskell met het IO type, de implementatie hiervan is niet belangrijk:

data IO resultaatType = ... Het type GeenUitkomst is in Haskell al gedefineerd, maar dan heet het ():

data () = () Zo kunnen we dus pure-functies defini¨eren die de toestand van de hele wereld aanpassen op dezelfde manier waarop we eerst de toestand van het coordinaat aanpasten. Wat voorbeelden hiervan zijn: putStrLn :: String −> IO () schrijft een string op de standard output. getLine :: IO String leest een string van de standard input. De functies >> en >>= zijn ook gedefini¨eerd voor het type IO, ze voeren, net als bij ToestandFunctie, eerst het linker argument uit en dan het rechter. Zo kunnen we bijvoorbeeld een functie schrijven die vraagt om je naam, je naam inleest en daarna “Hoi ” print. Deze functie veranderd dus de staat van de hele wereld. hallo :: IO () hallo = (putStrLn "Wat is je naam?") >> ( getLine >>= (\naam −> let hoiString = "Hoi " ++ naam ++ "!" in putStrLn hoiString ) ) of in de do-notatie: halloBeter :: IO () halloBeter = do putStrLn "Wat is je naam?" naam <− getLine let hoiString = "Hoi " ++ naam ++ "!" putStrLn hoiString return ()

28

De main functie, het beginpunt van elk programma, moet ook het type IO () hebben. Dus om bijvoorbeeld het programma te maken dat de functie hallo uitvoerd kunnen we schrijven: main :: IO () main = do halloBeter return ()

Opgave 8 Programmeer zelf de functie hoiOmgekeerd die: • Vraagt om je naam • Vraagt om je titel (bijv. dhr, mvr of BSc.) • Uitprint “Hoi ” <je titel> <je naam omgekeerd> “!!” Op beide manieren. Dus met: • De >>= en >> functies. • De do notatie plus return. Voeg dit toe aan de file Hoi.hs.

2.16

Monads

Na dit lange verhaal vraag je je vast af wat nou eigenlijk een monad is. Gelukkig is dat met je nieuwe kennis makkelijk te beantwoorden: Een monad is een type, hierna genoemd m: • waarin je een ander type kunt doen. Dan krijg je bijvoorbeeld m Bool of m Int. • waarop de operator >>= is gedefini¨eerd.2 De operator >>= heeft het type: (m a)->(a -> (m b))->(m b) waarbij a en b willekeurige andere types zijn. • waarop de functie return is gedefini¨eerd. De functie return heeft het type: a -> (m a) waarbij a een willekeurig ander type is. 2 De

>> operator is niet noodzakelijk, die kan je defini¨ eren aan de hand van >>=

29

Dus bijvoorbeeld: • MisschienEen is een monad want: – Je kan er een ander type in doen, dan krijg je bijvoorbeeld MisschienEen Int of MisschienEen Bool – De >>= operator is gedefini¨eerd voor MisschienEen – De return operator is gedefini¨eerd voor MisschienEen. • ToestandFunctie is een monad want: – Je kan er een ander type in doen, dan krijg je bijvoorbeeld ToestandFunctie Int,ToestandFunctie Bool of ToestandFunctie GeenUitkomst. – De >>= operator is gedefini¨eerd voor ToestandFunctie – De return operator is gedefini¨eerd voor ToestandFunctie. • IO is een monad want: – Je kan er een ander type in doen, dan krijg je bijvoorbeeld IO Int,IO String of IO (). – De >>= operator is gedefini¨eerd voor IO. – De return operator is gedefini¨eerd voor IO. Met een monad kun je dus bijvoorbeeld toestand doorgeven, zoals bij ToestandFunctie en IO, of met uitzonderingen omgaan, zoals bij MisschienEen.

2.17

Monads declareren

Tot nu toe hebben we gedaan alsof we de >>=,>> en return functies gewoon kunnen opschrijven als alle andere fucnties. Om ze met de do-notatie te kunnen gebruiken moeten we echter zeggen dat het type, dus bijvoorbeeld MisschienEen of ToestandFunctie, een instantie van de class Monad is. Dit schrijven we als volgt: Voor MisschienEen:

data MisschienEen resultaatType = GeenResultaat | Resultaat resultaatType instance

Monad MisschienEen where

GeenResultaat >>= rechterFunctie = GeenResultaat (Resultaat nummer) >>= rechterFunctie = rechterFunctie nummer return x = Resultaat x en voor ToestandFunctie

30

data ToestandFunctie resultaatType = ToestandFunctie (Toestand−>(Toestand,resultaatType)) instance Monad ToestandFunctie where (ToestandFunctie functieLinks) >>= (toestandFunctieOnthoudResultaatRechts ) = ToestandFunctie (\beginToestand −> let (tweedeToestand,resultaatLinks) = functieLinks beginToestand (ToestandFunctie functieRechts) = toestandFunctieOnthoudResultaatRechts resultaatLinks (derdeToestand,resultaatRechts) = functieRechts tweedeToestand in (derdeToestand,resultaatRechts) ) return uitkomst = ToestandFunctie (\toestand −> (toestand,uitkomst) )

31

We gaan nu kijken hoe we een monad kunnen maken waarmee we makkelijk kunnen parsen (ontleden). Dit is een monad die zowel met uitzonderingen omgaat als toestand doorgeeft.

An Introduction to Parser Combinators 3

The Library Functions

The standard Haskell distribution includes the library ‘Parsec’, a large and very efficient library of parser combinators. Once you have parsed with Parsec you will refuse to go back to parser libraries for imperative languages like C or Java. However, for the purpose of education we do not use ‘Parsec’ in this course. We implement our own simplistic parser combinator library which we describe in the remainder of this section. We start with a description of the data types. A Parser of type a consists of a function that takes a String and delivers a ParseResult of type a:

data Parser a = Parser (String −> ParseResult a) The ParseResult can either be a Match or NoMatch, corresponding to a successful or non-successful application of the parser, respectively:

data ParseResult a = Match a String | NoMatch String Note that Match has two parameters. The first is of type a, the result of parsing. The second is the string that remains to be parsed. In case of a non-successful parsing (NoMatch) only the remaining string is returned. We now continue with a description of the available parser combinators. These operators are called parser combinators since they combine parsers to new parsers: • (|||) :: Parser a -> Parser a -> Parser a Usage: pa ||| pb Corresponds to ‘|’ (or) in BackusNaur Form (BNF). The operator ‘|||’ combines to parsers to a new parser which first tries pa and if pa fails, then it tries pb. • oneOrMore :: Parser a -> Parser [a] Usage: oneOrMore p Corresponds to ‘+’ in BNF, that is, repeatedly applies the parser p (one or more times). Returns the list of parse results of p. • zeroOrMore :: Parser a -> Parser [a] Usage zeroOrMore p Corresponds to ‘+’ in BNF, that is, repeatedly applies the parser p (one or zero times). Returns the list of parse results of p. 32

• sepBy1 :: Parser a -> Parser b -> Parser [a] Usage: sepBy1 p sep Parses multiple (but at least one) p separated with sep. Returns the list of parse results of p (the results of sep are ignored). • sepBy :: Parser a -> Parser b -> Parser [a] Usage: sepBy p sep Parses multiple p separated with sep. Returns the list of parse results of p (the results of sep are ignored). • char :: Char -> Parser Char Usage char c Tries to parse the character ‘c’; fails if the next character is not ‘c’. • string :: String -> Parser String Usage string s Tries to parse the string s; fails if the string to parse does not start with s. • Monads for combining parsers sequentially: composition = do result1 <− parser1 result2 <− parser2 ... resultN <− parserN return your_function(result1,...,resultN) Most of these combinators are defined within a single line of code; have a look at the source of Parse.hs. While this library contains already quite useful parser combinators, the great thing is that you can easily define your own ones! Thereby your source code not only gets smaller by factor 10, but also much more readable.

4

Implementation of the Combinators

We consider the implementation of two combinators: ||| and the monads for sequential composition are implemented as follows. The combinator ||| is implemented as follows: (Parser pa) ||| (Parser pb) = Parser (\string −> case pa string of NoMatch s −> pb string Match a string −> Match a string )

33

That is, pa ||| pb first applies the parser pa. If pa succeeds, then its result is returned. If pa fails, then pb is started on the same input string and its result is returned.

34

Monads for sequential composition are implemented as follows:

instance Monad Parser where (Parser pa) >>= f = Parser (\string −> case pa string of NoMatch s −> NoMatch s Match a string’ −> let Parser p = f a in p string’ ) return a = Parser (\string −>

Match a string)

The function >>= is of type: (>>=) :: Parser a −> (a −> Parser b) −> Parser b That is, pa >>= f is a parser that, given a string s, first applies the parser pa to the string s. If this application is not successful, then NoMatch s is returned. If the application was successful, then we have a result a and a remaining string s0 . In this case the parser (f a) is applied to s0 and this result is the result of pa >>= f. The function return lifts on object a to a parser returning a as result. That is, return takes an argument a and returns a parser does nothing but leaving returning a as result (and leaving the given string untouched). The do notation: composition = do result1 <− parser1 result2 <− parser2 ... resultN <− parserN return your_function(result1,...,resultN) is a convenient abbreviation of: composition = do parser1 >>= (\result1 −> parser2 >>= (\result2 −> ... parserN >>= (\resultN −> Parser (\s −> Match your_function(result1,...,resultN) s)))) After this dry theory we continue with an example: parsing TRSs.

35

5

Parsing TRSs

We show how to parse a term rewriting system (TRS) given by the following EBNF: trs = whitespace, vars , whitespace, rules, whitespace vars

=

’(’ , ’VAR’, { wordws } , ’)’

rules

=

’(’ , ’RULES’, { rule }+ , ’)’

rule

=

termws ’− >’ ,termws

termws

=

whitespace , term, whitespace

term

=

word , [ ’(’, [subterms] , ’)’ ]

subterms

=

term , { ’,’ , term }

word

=

{ symbol }+

wordws

=

whitespace , word , whitespace

symbol

=

’a’ | ... | ’z’ | ’A’ | ... | ’Z’ | ’0’ | ... | ’9’

whitespace

=

{ ’ ’ | ’\n’ | ’\t’ }

for example: (VAR x y z) (RULES f(x,y) −> g(g(x)) g(x) −> a(f(x,x)) a(z) −> z )

The Data Types First, we define the data types for TRSs, rules and terms.

data TRS = TRS { variables :: [String], rules :: [Rule] } data Rule = Rule { lhs :: Term, rhs :: Term } data Term = Term String [Term] | Var String A TRS consists of a list of variables and a list of rules. A Rule its left-hand side (lhs) and a right-hand side (rhs) which are both terms. A Term is either a symbol with a list of subterms or a variable. The following example illustrates, how the TRS consisting of the single rule f (x, y) → g(x) can be created in Haskell using the above data types: TRS { variables = ["x","y"], rules = [Rule { lhs = Term "f" [Var "x", Var "y"], rhs = Term "g" [Term "g" [Var "x"]] }] } 36

The Parsing First, we define low-level for symbols and words. A symbol is a character ‘a’ or character ‘b’ or . . . In Haskell this can be defined compact using the functions map and foldl1. symbol = foldl1 (|||) $ map char $ [’a’..’z’] ++ [’A’..’Z’] ++ [’0’..’9’] We define a word as a list of symbols: word = oneOrMore symbol We define a parser to parse the spaces, tab’s (\t) or linebreak (\n): whiteSpace = zeroOrMore (char ’ ’ ||| char ’\t’ ||| char ’\n’) Now we define a function ws that takes a parser and returns a parser: ws parser = do whiteSpace r <− parser whiteSpace return r Then ws p behaves as p but allows whiteSpace before and after p. For example wordws behaves as word but allows whiteSpace before and after the word. wordws = ws word We parse terms: we start with parsing a word, then we parse the subterms (parseTerm vars) which are wrapped into parenthesis (paren) and separated by commas (sepBy ... (char ’,’)). That is: parseTerm vars = do f <− wordws subterms <− (paren ( sepBy (parseTerm vars) (char ’,’) ) ) ||| alwaysMatch let result = if f ‘elem‘ vars then (Var f) else (Term f subterms) return result Next, we parse rules (two terms separated by ‘->’): parseRule vars = do l <− ws (parseTerm vars) string "−>" r <− ws (parseTerm vars) return (Rule { lhs = l, rhs = r }) Finally, we parse the whole TRS which consists of first parsing the list of variables and then the list of rules: 37

parseTRS = do vars <− ws parseVars rules <− ws (parseRules vars) return ( TRS { variables = vars, rules = rules } ) where parseVars = paren ( do string "VAR" vars <− zeroOrMore wordws return vars ) parseRules vars = paren ( do string "RULES" rules <− oneOrMore (parseRule vars) return rules ) The source code for parsing TRSs can be found on website of the lecture.

Opgave 9 Schrijf een parser voor de syntax van de “commandotaal” van de tweede opgave van voortgezet programmeren. Die opgave is te vinden op http://www.few.vu.nl/~ds/. De datatypen voor de “commandotaal” zijn al gedefineerd in de file ParseStatement.hs. Zet je parser ook in die file.

Bonus Opgave niet verplicht Maak de gehele tweede opgave van voorgezet programmeren in Haskell. Hiermee kan je 2 punten bovenop je practicumcijfer winnen. (Dus als je een 7.5 hebt voor het practicum, en je hebt deze opgave gemaakt dan krijg je een 9.5 voor je practicum). Om deze opdracht in te leveren mail je je uitwerking naar [email protected].

38