Het vak FP
Web Home

PrologJCU
%TOC%

---++ Waarschuwing
We gebruiken bij deze opdrachten twee verschillende programmeertalen: Prolog en Haskell. Dit zijn beide declaratieve talen, gebruiken beide recursie en hebben boom-achtige data structuren. Probeer bij de opdrachten de taal die we beschrijven (Prolog) en de taal waarmee we de beschrijving geven (Haskell) niet door elkaar te halen.

Een belangrijk verschil is verder dat Haskell een zogenaamde _sterk getypeerde_ taal is; d.w.z. dat de vertaler  een groot aantal fouten in je programma kan vinden, en ook zijn best doet die zo begrijpelijk mogelijk (wat niet altijd lukt) uit te leggen. Prolog daarentegen heeft geen type-systeem  en als de invoer fout is gebeurt er vaak helemaal niets. De interpretator kan gewoon het gevraagde bewijs niet leveren  en geeft gewoon geen antwoord. Wees dus heel precies in je Prolog programma's, bouw ze stapje voor stapje op en test elke functie uitgebreid voordat je aan de volgende begint.

---++ %MAKETEXT{"Resources"}%
   * [[http://www.cs.uu.nl/wiki/bin/viewfile/PrologJCU/WebHome?rev=2;filename=jcu.pdf][Korte Prolog inleiding]]
   * [[http://hackage.haskell.org/platform/][Haskell platform]], om op je eigen computer te installeren.
   * [[http://hackage.haskell.org/package/NanoProlog][De NanoProlog interpreter library]]
   * Op het IRC kanaal [[irc:irc.freenode.net/#jcu]] kun je in principe met elkaar overleggen en vragen stellen. Komt er niet snel antwoord stuur dan even een mail naar:  [[mailto:j.stutterheim@uu.nl][Jurriën Stutterheim]].

---++ Opdrachten
Omdat we niet weten of en zo ja hoe goed jullie kunnen programmeren
hebben we een groot aantal opdrachten verzonnen. Het kan zijn dat ze
te gemakkelijk, maar ook dat ze te moeilijk zijn. _We horen graag van jullie wat jullie er van vinden, zodat we bij het verder uitwerken van deze cursus daar ons voordeel mee kunnen doen_. Vind je het te moeilijk, te makkelijk, te veel, leuk of niet leuk en waarom, etc. 

Probeer bij het vormen van de groepjes zoveel mogelijk _gelijkwaardige_ partners te vinden. Dus niet al ervaren programmeurs bij mensen die nog nooit geprogrammeerd hebben in een groep want binnen de kortste keer doen er dan een of twee niets meer en kijken alleen maar toe hoe anderen het werk doen.

Belangrijk is ook dat je elkaar voortdurend probeert uit te leggen wat er precies aan de hand is als er iets niet werkt, of wat je wilt bereiken; vaak komt degene die uitlegt wat er niet werkt er tijdens dit uitleggen ineens achter waarom er iets niet werkt. Bij het programmeren geldt echt dat als je met z'n tweeën of z'n drieën bent het meer dan twee of drie keer zo snel kan gaan.

Schrijf op wat je doet en waarom; ga niet in het wilde weg allemaal dingen proberen. Ook bij het opschrijven kom je er pas achter wat je nog niet weet of eerst uit moet zoeken.



---+++ Opdrachten zonder Haskell nog nodig te hebben
---++++ Opdrachten met de Prolog server  (Deze opdracht is geschikt voor iedereen om warm te lopen)
Op het adres [[http://vhost0031.zoo.cs.uu.nl/]] hebben we een server
draaien  die je met een webbrowser kunt benaderen; je hoeft hiervoor dus helemaal nog geen software op je computer te installeren en je kunt gelijk aan de slag. 
Je moet je een keer
registreren en daarna kun je van deze interactieve stellingbewijzer
gebruik maken. Rechts kun je regels definiëren en links kun je
bovenin het doel definiëren dat je wilt bewijzen. Door regels naar
lege vakjes links te trekken kun je stap voor stap een bewijsboom
opbouwen (we gebruiken hier het woord _bewijsboom_ om aan te
geven dat bij een doel een aantal subdoelen kunnen horen; bomen in de
Informatica zijn een beetje vreemd: ze groeien i.h.a. van boven naar
beneden).

   * Probeer voor de voorbeelden die we hierboven gegeven hebben de bewijsbomen te construeren.
   * Kun je ook vermenigvuldigen en aftrekken definiëren?
   * Kun je ook een _kleinerdan_ relatie definiëren?
   * Een beroemde manier _Quicksort_ om een lijst getallen te sorteren is om de lijst in twee stukken te knippen: een (_K_) met alle getallen kleiner of gelijk aan de eerste waarde (_X_) hieronder en de tweede lijst met alle waarden groter dan die eerste waarde (_G_), vervolgens deze lijsten zelf te sorteren (resultaten _L_ en _I_), en deze gesorteerde lijsten aan elkaar te hangen, met de |X| er tussenin. Het sorteerprogramma ziet er nu uit als:
<verbatim>
sort(empty,empty).
sort(cons(X,Y),Z) :- split(X,Y,K,G), sort(K,L),sort(G,I),append(L,cons(X,I),Z).
</verbatim>
Geef zelf de definities voor =split= en =append=. Werk stapje voor stapje, en probeer niet alles in een keer goed te doen. Test alles wat je doet telkens terdege. Als de interpretator geen oplossingen kan vinden krijg je geen feedback, en merk je alleen dat er iets niet lukt. Probeer ook eerst zelf een bewijs te leveren met de browserversie.
   * Een alternatieve manier om de voorouder relatie te definiëren is:
<verbatim>
voor(X,Y) :- ouder(X,Y).
voor(X,Y) :- voor(X,Z), voor(Z,Y).
</verbatim>
Leg uit dat deze definitie equivalent is, d.w.z. leg uit hoe de bewijsbomen in de oude en de nieuwe situatie een-op-een op elkaar afgebeeld kunnen worden.
   * Wat gebeurt er als je in het voorbeeld hierboven de regels omdraait? Probeer dit? Zijn de beide definities dan nog steeds gelijk?  Kennelijk is de volgorde waarin de definities gegeven worden van belang. Leg uit waarom er nu wat anders uit komt. Toelichting: we hebben hier een van de nadelen van Prolog te pakken. De volgorde van de definities is van het grootste belang; dit maakt het schijven van Prolog programma's vaak erg moeilijk.

---++++ Logic Puzzles
Prolog kan goed gebruikt worden om zogenaamde [[http://www.anselm.edu/internet/compsci/Faculty_Staff/mmalita/HOMEPAGE/logic/index.html][Logic Puzzles]] op te lossen. Zoek zelf een dergelijke puzzle op (je bent er vast wel eens een tegen het lijf gelopen)en probeer die m.b.v. Prolog op te lossen. Let op: onze interpretator ondersteunt geen ontkenning dus die zal je telkens op een wat omslachtige wijze moeten omzeilen.

---++++ Breadth-first versus Depth-first search
Prolog gebruikt intern een zoekproces om tot een oplossing te komen. Standaard is dat een zogenaamde [[http://en.wikipedia.org/wiki/Depth-first_search][depth-first search]] process; in ons geval wordt er nadat een regel is toegepast eerst geprobeerd de subdoelen van die regel op te lossen, voordat we verder gaan met al bestaande subdoelen. Leg uit waarom de volgorde waarin de regels toegepast worden (en ze dus in de data base staan) hier een verschil kan uitmaken. Kun je aangeven welke programma's bijvoorbeeld nooit met een oplossing aankomen. Zoek op het internet op wat het verschil is tussen een depth-first en een [[http://en.wikipedia.org/wiki/Breadth-first_search][breadth-first search]], en laat zien dat bij het gebruik van die laatste zoekmethode het hiervoor gesignaleerde probleem niet voorkomen.

---+++ Haskell gebaseerd (met name voor de mensen die al een keer iets geprogrammeerd hebben).
Haskell is, ondanks zijn eenvoudige structuur, uiteindelijk een grote taal en deze taal helemaal leren zou te ver gaan voor een pre-thesis; het neemt veel meer dan de 40 uur die beschikbaar is. Toch zou je een deel van de tijd kunnen besteden aan het leren van wat Haskell (en dan demand driven); bijvoorbeeld voldoende om de Prolog interpretator te begrijpen  en eventueel (vraag desnoods wat hulp) aan te passen.

---++++ Learn  You a Haskell for the Great Good
Dit is de titel van een [[http://learnyouahaskell.com/][boek]] dat online beschikbaar is. De eerste 5 hoofdstukken is ongeveer wat je nodig hebt als je de Prolog interpretator wilt begrijpen c.q. aanpassen (ik ben een optimistisch iemand  en waarschijnlijk ook hier weer te optimistisch). Het is een leuk geschreven boek  en door de programma'tjes ook echt uit te voeren terwijl je het boek leest leer je een hoop. Hoofdstuk 9 legt uit hoe in een functionele taal als Haskell de Input/Output plaats vindt. Dit lijkt in eerste instantie nogal omslachtig, maar daar zijn goede redenen voor. Je hebt het waarschijnlijk in eerste instantie niet nodig. Werk de hoofstukken dus door en laat ons weten hoe het gaat.

---++++ Eenvoudige Haskell oefenopgaven
Voor een zomerschool hebben we aantal sets met eenvoudige oefenopagven beschikbaar:
   * [[http://www.cs.uu.nl/wiki/pub/USCS2010/ComputerLab/Intro.pdf][Intro]]
   * [[http://www.cs.uu.nl/wiki/pub/USCS2010/ComputerLab/Lists.pdf][Lijsten]]
   * [[http://www.cs.uu.nl/wiki/pub/USCS2010/ComputerLab/Trees.pdf][Bomen]]

---++++ Uitgebreidere rapportage
In de functie =printSolutions= komt het volgende stukje code voor:
<verbatim>
 show (subst env pr)
</verbatim>
Wat hier gebeurt is dat op de gevonden bewijsboom vlak voordat hij wordt afgedrukt eerst de gevonden substitutie wordt losgelaten. We vullen dus de gevonden oplossing in in het hele bewijs, zodat tussenliggende variabelen hun uiteindelijke waarde krijgen. Het is instructief om dit eens te vervangen door:
<verbatim>
 show pr
</verbatim>
Je zou dit tegelijkertijd kunnen doen met het afdrukken van de substitutie voor alle gebruikte variabelen, en niet alleen de variabelen die in het oorspronkelijke goal voorkomen. Doe dit door in de functie =show'= in de module =Lib.hs= de code:
<verbatim>
             where  showBdg (x, t)  | isGlobVar x =  x ++ " <- "++ showTerm t
                                    | otherwise = ""
</verbatim>
te vervangen door:
<verbatim>
             where  showBdg (x, t)  =   x ++ " <- "++ showTerm t
</verbatim>.
Beschrijf wat je ziet en wat de rol is van de tussenliggende variabelen. Waarom zijn ze genummerd?

---++++ Extra operatoren (niet erg makkeljk; komt veel bij kijken)
De gegeven interpretator is erg simpel, en zal dus ook erg traag zijn als je echt iets gaat uitrekenen. Je zou het data type =Term= uit kunnen breiden met bijvoorbeeld een alternatief waarbij een =Integer=waarde wordt opgeslagen, bijv. =Nat Integer=. Een bepaald aantal functienamen, zoals bijv. =plus= zouden nu efficiënter behandeld kunnen worden. 

---++++ Depth-first versus Breadth-first
De basis-machinery bouwt een waarde op van het data-type =Result=:
<verbatim>
data Result = Done Env
            | ApplyRules [(Rule, Result)]
</verbatim>
Een =Done Env= blad correspondeert met een gevonden oplossing  en de daarbij behorende substitutie (van type =Env=) is ook in dat blad opgeslagen. Een =ApplyRules= knoop heeft een aantal deelbomen als kinderen. Elk van die deelbomen is gelabelled met een =Rule=, de regel die toegepast kon worden in deze knoop. De bijbehorende =Result= waarde beschrijft het verdere verloop van het zoekproces voor deze beslissing.

Een merkwaardige, maar in ons geval heel belangrijke eigenschap van Haskell, is dat een waarde pas uitgerekend wordt als je er om vraagt, d.w.z. de waarde gebruikt in een pattern-match of een case-statement. Dit maakt het mogelijk dat een waarde van het type =Result= oneindig lange paden naar heel ver weg gelegen bladeren heeft. Kom je op zo'n pad terecht en vraag je je af of er aan het eind van zo'n pad nu een =Done= knoop zit of een =ApplyRules []= dan krijg je geen antwoord: de interpretator gaat maar door en door in de hoop je ooit eens een antwoord te kunnen geven.

De functie: 
<verbatim>
enumerateDepthFirst :: [(String, Rule)] -> [String] -> Result -> [([(String, Rule)], Env)]
</verbatim>
maakt van een =Result= een lijst van alle =Done= knopen in dit =Result=. De eerste parameter is de lijst van tot dusverre tegen gekomen regels (de labels uit de =ApplyRules=, samen met =String= die aangeeft op welke plaats in de boom je zit (bijv. =0.2.3.1=). De tweede parameter bevat de prefixen voor de regels waarvan je zeker weet dat die nog komen voordat je een =Done= knoop tegen kan komen.

Bestudeer de code van deze functie en overtuig jezelf ervan dat deze met een zogenaamde _depth-first traversal_ van de resultaatboom overeenkomt. Kun je nu zelf een zogenaamde _breadth-first traversal_ schrijven? Doe dit  en ga na dat je inderdaad meer oplossingen krijgt en dat de volgorde van de regels, waarvan we eerder constateerden dat die er toe deed, er nu veel minder toe doet. De volgorde waarin de oplossingen gevonden worden kan nog wel verschillen, maar elke oplossing die op een eindige diepte zit wordt inderdaad eens gevonden.

---++++ De occurs check
Een van de dingen die onze interpretator niet doet is de zogenaamde _occurs-check_ uitvoeren. Dit is nodig om er voor te zorgen dat in een waarde die we voor een variabele substitueren niet weer die variabele voorkomt. Zoiets ken je uit de rekenkunde als je een vergelijking _x = x + 1_ tegen komt. Als je een dergelijke substitutie hebt is die nooit idempotent te krijgen en het afdrukken van en dergelijke term stopt niet. Breidt de interpretator uit zodat hij deze test doet.

---++++ Cut and Fail
In het artikel [[http://portal.acm.org/citation.cfm?doid=214956.214960][Describing Prolog by its interpretation and compilation]] wordt een iets andere beschrijving van Prolog gegeven. In principe is wat hier gebeurt echter hetzelfde als wat er gebeurt in onze interpretator. In dit artikel worden de operatoren =cut= en =fail= beschreven. Kun je die toevoegen aan onze interpretator?

Vanwege copyright regels mogen we dit artikel niet op de website zetten; wel kan je het zelf downloaden als je op de universiteit bent. Op verzoek stuur ik het je ook graag even toe ([[mailto:doaitse@swierstra.net]]). Ik ben wel een paar dagen wat moeilijk bereikbaar. Vraag eventueel ook Jurriën.

---++ Groepindeling

   * Groep 1
      * Casper
      * Job
      * Roel
   * Groep 2
      * Christiaan
      * Jordy
      * Patrick
   * Groep 3
      * Evrim
      * Lianne
      * Marijne
   * Groep 4
      * Esmée
      * Emma
Topic attachments
I	Attachment	Action	Size	Date	Who	Comment
pdf	jcu.pdf	manage	235.0 K	24 May 2011 - 14:01	JurrienStutterheim