You are here: UUCS>PrologJCU Web>WebHome (24 May 2011, JurrienStutterheim)EditAttach

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.

Resources

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:
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).
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:
voor(X,Y) :- ouder(X,Y).
voor(X,Y) :- voor(X,Z), voor(Z,Y).
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 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 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 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 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:

Uitgebreidere rapportage

In de functie printSolutions komt het volgende stukje code voor:
 show (subst env pr)
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:
 show pr
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:
             where  showBdg (x, t)  | isGlobVar x =  x ++ " <- "++ showTerm t
                                    | otherwise = ""
te vervangen door:
             where  showBdg (x, t)  =   x ++ " <- "++ showTerm t
. 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:
data Result = Done Env
            | ApplyRules [(Rule, Result)]
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:
enumerateDepthFirst :: [(String, Rule)] -> [String] -> Result -> [([(String, Rule)], Env)]
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 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 revision: r13 - 24 May 2011, JurrienStutterheim
 

This site is powered by FoswikiCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UUCS? Send feedback