Reeks 4 : Logisch Programmeren
Deze oefeningenreeks behandelt het gebruik van de query evaluator uit hoofdstuk 4.4. De query evaluator start je door het bestand "icp_4_qeval.scm" te evalueren in DrRacket. De query evaluator zal het vervolgens toelaten om de databank met logische feiten te bevragen. We gebruiken de query evaluator uit de cursus in combinatie met een databank die de planeten en manen van ons zonnestelsel beschrijft. Daarom moet het bestand "icp_4_qeval_zonnestelsel.txt", die deze databank bevat, zich in dezelfde directory bevinden.
Als je door middel van assert! feiten of regels aan de databank toevoegt, blijven deze aanwezig tot de databank geherinitialiseerd wordt. Herinitialisatie kan van pas komen bij het corrigeren van eventuele vergissingen in de definitie van logische regels, maar vergeet niet dat alle andere zelf-gedefinieerde feiten en regels op deze manier verloren gaan. Als je de evaluator terug wil opstarten ZONDER de databank te herinitialiseren, kan je de argumentloze procedure query-driver-loop oproepen.
1 Queries
1.1 Oefening: Eenvoudige queries (patronen en variabelen)
Queries bestaan uit door middel van logische connectieven verbonden patronen. Voorlopig beperken we ons tot eenvoudige queries die slechts uit 1 patroon bestaan. Een patroon is een lijst van symbolen en logische variabelen. Een zoekopdracht wordt gestart voor elke query die als invoer aan de logische evaluator gegeven wordt. Deze gaat namelijk op zoek naar variabele-bindingen die het patroon doen overeenkomen met een feit uit de databank. Als antwoord op de zoekopdracht wordt het patroon geprint met alle variabelen geïnstantieerd met de gevonden bindingen. Indien meerdere feiten uit de databank met het patroon overeenkomen (telkens met verschillende variabele-bindingen), worden meerdere oplossingen geprint.
De volgende query zoekt bijvoorbeeld geschikte bindingen voor de variabele ?planeet: (is-maan-van Deimos ?planeet). In de databank is een feit (is-maan-van Deimos Mars) aanwezig. Het symbool Mars is dus een geschikte binding voor de variabele ?planeet:
> (is-maan-van Deimos ?planeet)
;;; Query results:
(is-maan-van Deimos Mars)
done
Formuleer nu zelf geschikte queries voor de volgende zoekopdrachten:
de namen van alle planeten
de namen van alle manen van Jupiter
alle door Galilei ontdekte hemellichamen
het jaar waarin Deimos werd ontdekt
de middellijn van Mars
de rotatietijd van Jupiter
1.2 Oefening: Samengestelde queries (and, or)
Samengestelde queries maken gebruik van and en or om andere queries te combineren. Volgende query geeft je bijvoorbeeld alle manen ontdekt door Galilei terug:
> (and (is-maan-van ?maan ?planeet) (is-ontdekt ?maan ?jaar Galilei))
;;; Query results:
(and (is-maan-van Callisto Jupiter) (is-ontdekt Callisto 1610 Galilei))
(and (is-maan-van Ganymedes Jupiter) (is-ontdekt Ganymedes 1610 Galilei))
(and (is-maan-van Europa Jupiter) (is-ontdekt Europa 1610 Galilei))
(and (is-maan-van Io Jupiter) (is-ontdekt Io 1610 Galilei))
done
Volgende query geeft je dan weer alle hemellichamen in het zonnestelsel terug:
> (or (is-planeet ?lichaam) (is-maan-van ?lichaam ?planeet))
;;; Query results:
(or (is-planeet Pluto) (is-maan-van Pluto ?planeet))
(or (is-planeet Nereide) (is-maan-van Nereide Neptunus))
(or (is-planeet Neptunus) (is-maan-van Neptunus ?planeet))
(or (is-planeet Triton) (is-maan-van Triton Neptunus))
(or (is-planeet Uranus) (is-maan-van Uranus ?planeet))
(or (is-planeet Miranda) (is-maan-van Miranda Uranus))
(or (is-planeet Saturnus) (is-maan-van Saturnus ?planeet))
(or (is-planeet Oberon) (is-maan-van Oberon Uranus))
(or (is-planeet Jupiter) (is-maan-van Jupiter ?planeet))
(or (is-planeet Titania) (is-maan-van Titania Uranus))
(or (is-planeet Mars) (is-maan-van Mars ?planeet))
(or (is-planeet Umbriel) (is-maan-van Umbriel Uranus))
(or (is-planeet Aarde) (is-maan-van Aarde ?planeet))
(or (is-planeet Ariel) (is-maan-van Ariel Uranus))
(or (is-planeet Venus) (is-maan-van Venus ?planeet))
(or (is-planeet Janus) (is-maan-van Janus Saturnus))
(or (is-planeet Mercurius) (is-maan-van Mercurius ?planeet))
(or (is-planeet Phoebe) (is-maan-van Phoebe Saturnus))
(or (is-planeet Japetus) (is-maan-van Japetus Saturnus))
(or (is-planeet Hyperion) (is-maan-van Hyperion Saturnus))
(or (is-planeet Titan) (is-maan-van Titan Saturnus))
(or (is-planeet Rhea) (is-maan-van Rhea Saturnus))
(or (is-planeet Dione) (is-maan-van Dione Saturnus))
(or (is-planeet Tethys) (is-maan-van Tethys Saturnus))
(or (is-planeet Enceladus) (is-maan-van Enceladus Saturnus))
(or (is-planeet Mimas) (is-maan-van Mimas Saturnus))
(or (is-planeet Callisto) (is-maan-van Callisto Jupiter))
(or (is-planeet Ganymedes) (is-maan-van Ganymedes Jupiter))
(or (is-planeet Europa) (is-maan-van Europa Jupiter))
(or (is-planeet Io) (is-maan-van Io Jupiter))
(or (is-planeet Deimos) (is-maan-van Deimos Mars))
(or (is-planeet Phobos) (is-maan-van Phobos Mars))
(or (is-planeet Maan) (is-maan-van Maan Aarde))
done
Nota: De query-resultaten van een door middel van or samengestelde query bestaan uit de instantiatie van het volledige patroon met de variabele-bindingen van een van de twee subqueries. Dit wordt duidelijk bij het evalueren van vorige query, waarbij "foutieve" antwoorden zoals (or (is-planeet Maan) (is-maan-van Maan Aarde)) gegeven worden. (is-planeet Maan) is op zichzelf namelijk onwaar. Echter, (is-maan-van Maan Aarde) is wél waar, waardoor het symbool Maan aan de variabele ?lichaam gebonden mag worden. Bij het instantiëren loopt het echter "mis".
De meeste logische evaluatoren gaan deze verwarring uit de weg door als resultaat variabele-bindingen te printen in plaats van query-instantiaties.
Van welke planeet Deimos een maan is en wat de afstand tot de Zon is van deze planeet
De afstand tot de Zon, rotatietijd en massa van de planeet Uranus
De namen van alle manen van Saturnus en Jupiter, samen met hun ontdekkers
1.3 Oefening: Filters (not, lisp-value)
Filters zoals not en lisp-value kunnen gebruikt worden om de resultaten van een zoekopdracht te filteren. Door middel van not filter je alle resultaten die aan het gegeven patroon voldoen, terwijl lisp-value resultaten filtert waarvoor het gegeven Scheme predicaat false teruggeeft. Volgende query geeft je bijvoorbeeld alle planeten met een massa groter dan 100 keer de aardmassa terug:
> (and (is-planeet ?p) (heeft-massa ?p ?m) (lisp-value > ?m 100))
;;; Query results:
(and (is-planeet Jupiter) (heeft-massa Jupiter 317.9) (lisp-value > 317.9 100))
done
de namen van planeten die geen maan hebben
de namen van planeten kleiner dan de Aarde
de planeet met de grootste massa
het object (maan of planeet) met de kleinste middellijn in de databank
de manen ontdekt voor 1700 of door Galilei
1.4 Oefening: Logische Regels
Niet alle queries resulteren in een zoekopdracht naar oplossingen. Queries van de vorm (assert! (rule <conclusion> <body>)) voegen bijvoorbeeld een logische regel toe aan de databank. Regels vormen het mechanisme ter abstractie van logische queries, net zoals functies expressies abstraheren. Informeel kan je een regel beschouwen als een beknopte voorstelling van een verzameling logische feiten. Voor deze virtuele feiten vormt de conclusie van de regel het patroon, met de logische variabelen geïnstantieerd met alle bindingen die voldoen aan de query in de body van de regel.
Volgende regel stelt bijvoorbeeld dat iets een object is als het ofwel een maan ofwel een planeet is:
> (assert! (rule (is-object ?x) (or (is-maan-van ?x ?p) (is-planeet ?x))))
Assertion added to data base.
> (is-object ?y)
;;; Query results:
(is-object Nereide)
(is-object Pluto)
(is-object Triton)
(is-object Neptunus)
(is-object Miranda)
(is-object Uranus)
(is-object Oberon)
(is-object Saturnus)
(is-object Titania)
(is-object Jupiter)
(is-object Umbriel)
(is-object Mars)
(is-object Ariel)
(is-object Aarde)
(is-object Janus)
(is-object Venus)
(is-object Phoebe)
(is-object Mercurius)
(is-object Japetus)
(is-object Hyperion)
(is-object Titan)
(is-object Rhea)
(is-object Dione)
(is-object Tethys)
(is-object Enceladus)
(is-object Mimas)
(is-object Callisto)
(is-object Ganymedes)
(is-object Europa)
(is-object Io)
(is-object Deimos)
(is-object Phobos)
(is-object Maan)
done
een regel (is-maan ?x) die bepaalt of ?x een maan is
een regel (heeft-maan ?p) die bepaalt of een planeet ?p (één of meerdere) manen heeft
een regel (kleiner ?x ?y) die bepaalt of ?x een kleiner hemellichaam is dan ?y
2 Logisch Programmeren
2.1 Oefening: Logisch Programmeren
(assert! (rule (last (?l) ?l))) (assert! (rule (last (?first . ?rest) ?last) (last ?rest ?last)))
Definieer nu zelf door middel van logische regels de volgende predicaten. Ga ook na waarom er soms duplicaten in de resultaten zijn, en wat de ongebonden variabelen betekenen.
element van een lijst: het predicaat (element ?e ?list) slaagt als ?e een element is uit de lijst ?list.
Implementeer dit zodat o.a. volgende bevragingen beantwoord kunnen worden:> (element ?x (1 2 3 4 2)) ;;; Query results:
(element 2 (1 2 3 4 2))
(element 1 (1 2 3 4 2))
(element 2 (1 2 3 4 2))
(element 3 (1 2 3 4 2))
(element 4 (1 2 3 4 2))
done
> (element 1 (5 ?x 5)) ;;; Query results:
(element 1 (5 1 5))
done
> (element 1 (?x ?x ?x)) ;;; Query results:
(element 1 (1 1 1))
(element 1 (1 1 1))
(element 1 (1 1 1))
done
> (element 1 (?x 5 ?y)) ;;; Query results:
(element 1 (?first-30 5 1))
(element 1 (1 5 ?y))
done
selectie uit een lijst: het predicaat (selection ?s ?list) slaagt als ?s een selectie van een willekeurig aantal elementen van ?list is. De lijst ?s kan men bekomen door uit de lijst ?list 0 of meer elementen te schrappen.
Implementeer dit zodat o.a. volgende bevraging beantwoord kan worden:> (selection ?x (1 2 3 4)) ;;; Query results:
(selection () (1 2 3 4))
(selection (1) (1 2 3 4))
(selection (2) (1 2 3 4))
(selection (1 2) (1 2 3 4))
(selection (3) (1 2 3 4))
(selection (1 3) (1 2 3 4))
(selection (2 3) (1 2 3 4))
(selection (1 2 3) (1 2 3 4))
(selection (4) (1 2 3 4))
(selection (1 4) (1 2 3 4))
(selection (2 4) (1 2 3 4))
(selection (1 2 4) (1 2 3 4))
(selection (3 4) (1 2 3 4))
(selection (1 3 4) (1 2 3 4))
(selection (2 3 4) (1 2 3 4))
(selection (1 2 3 4) (1 2 3 4))
done
prefix van een lijst: het predicaat (prefix ?p ?list) slaagt als ?p een prefix is van de lijst ?list. De lijst ?p bevat een willekeurig aantal opeenvolgende elementen uit ?list, vertrekkende vanaf het eerste element van ?list.
Implementeer dit zodat o.a. volgende bevragingen beantwoord kunnen worden:> (prefix ?p (1 2 3)) ;;; Query results:
(prefix (1 2 3) (1 2 3))
(prefix () (1 2 3))
(prefix (1) (1 2 3))
(prefix (1 2) (1 2 3))
done
> (prefix (1 2 3) (?x ?y 3 4 5)) ;;; Query results:
(prefix (1 2 3) (1 2 3 4 5))
done
> (prefix (1 2) (?x ?y ?z 4 5)) ;;; Query results:
(prefix (1 2) (1 2 ?z 4 5))
done
postfix van een lijst: het predicaat (postfix ?p ?list) slaagt als ?p een postfix is van de lijst ?list. De lijst ?p bevat een willekeurig aantal opeenvolgende elementen uit ?list, vertrekkende vanaf het laatste element van ?list.
Implementeer dit zodat o.a. volgende bevragingen beantwoord kunnen worden:> (postfix ?p (1 2 3)) ;;; Query results:
(postfix () (1 2 3))
(postfix (1 2 3) (1 2 3))
(postfix (2 3) (1 2 3))
(postfix (3) (1 2 3))
done
sublijst van een lijst: het predicaat (sublist ?s ?list) slaagt als ?s een sublijst is van de lijst ?list. De lijst ?s kan men bekomen door een prefix en een postfix weg te laten van de lijst ?list.
Implementeer dit zodat o.a. volgende bevragingen beantwoord kunnen worden:> (sublist ?sub (1 2 3)) ;;; Query results:
(sublist () (1 2 3))
(sublist () (1 2 3))
(sublist (1 2 3) (1 2 3))
(sublist () (1 2 3))
(sublist (2 3) (1 2 3))
(sublist () (1 2 3))
(sublist (3) (1 2 3))
(sublist (1) (1 2 3))
(sublist (1 2) (1 2 3))
(sublist (2) (1 2 3))
done
permutatie van een lijst: het predicaat (permute ?list ?p) slaagt als de lijst ?p een permutatie is van de lijst ?list. De lijst ?p kan men bekomen door willekeurig elementen van de lijst ?l van plaats te verwisselen. Je kan hiervoor een hulp-predicaat (extract ?list ?element ?rest) implementeren dat slaagt als ?rest de elementen van de lijst ?list bevat nadat hieruit het element ?element geëxtraheerd is.
Implementeer dit zodat o.a. volgende bevragingen beantwoord kunnen worden:> (permute (2 3 ?x) (1 2 3)) ;;; Query results:
(permute (2 3 1) (1 2 3))
done
> (permute (2 ?x ?y) (1 2 3)) ;;; Query results:
(permute (2 3 1) (1 2 3))
(permute (2 1 3) (1 2 3))
done
> (permute (?x ?y ?z) (1 2 3)) ;;; Query results:
(permute (3 2 1) (1 2 3))
(permute (1 3 2) (1 2 3))
(permute (2 3 1) (1 2 3))
(permute (3 1 2) (1 2 3))
(permute (1 2 3) (1 2 3))
(permute (2 1 3) (1 2 3))
done
het omgekeerde van een lijst: het predicaat (reverse ?reversed ?list) slaagt als ?reversed de elementen van ?list in omgekeerde volgorde bevat.
Implementeer dit zodat o.a. volgende bevragingen beantwoord kunnen worden:> (reverse ?x (1 2 3)) ;;; Query results:
(reverse (3 2 1) (1 2 3))
done
> (reverse (3 ?x 1) (1 2 3)) ;;; Query results:
(reverse (3 2 1) (1 2 3))
done
> (reverse (3 . ?y) (1 2 3)) ;;; Query results:
(reverse (3 2 1) (1 2 3))
done
2.2 Oefening: Een volledig logisch programma
Beschouw volgende feitenbank afkomstig uit de archieven van “Trinny & Susannah”:
(assert! (is-kleur rood)) (assert! (is-kleur groen)) (assert! (is-kleur beige)) (assert! (is-kleur zwart)) (assert! (is-kleur geel)) (assert! (is-kleur kaki)) (assert! (is-kleur paars)) (assert! (is-kleur wit))
(assert! (kleur-heeft-helderheid rood 333)) (assert! (kleur-heeft-helderheid groen 196)) (assert! (kleur-heeft-helderheid beige 944)) (assert! (kleur-heeft-helderheid zwart 0)) (assert! (kleur-heeft-helderheid geel 833)) (assert! (kleur-heeft-helderheid kaki 856)) (assert! (kleur-heeft-helderheid paars 722)) (assert! (kleur-heeft-helderheid wit 1000))
(assert! (persoon-draagt ilse ((jurk wit) (tas zwart)))) (assert! (persoon-draagt evi ((hemd rood) (riem zwart) (broek zwart)))) (assert! (persoon-draagt jan ((hemd wit) (linkersok zwart) (rechtersok zwart))))
implementeer het unaire predicaat (kleur-is-donker ?k) aan de hand van een regel. Dit predicaat slaagt als kleur ?k een helderheid heeft die kleiner is dan 500.
Implementeer dit zodat o.a. volgende bevragingen beantwoord kunnen worden:> (kleur-is-donker ?kleur) ;;; Query results:
(kleur-is-donker zwart)
(kleur-is-donker groen)
(kleur-is-donker rood)
done
implementeer het unaire predicaat (kleur-is-licht ?k) aan de hand van een regel. Gebruik in je implementatie het predicaat (kleur-is-donker ?k).
Implementeer dit zodat o.a. volgende bevragingen beantwoord kunnen worden:> (kleur-is-licht ?kleur) ;;; Query results:
(kleur-is-licht wit)
(kleur-is-licht paars)
(kleur-is-licht kaki)
(kleur-is-licht geel)
(kleur-is-licht beige)
done
implementeer het unaire predicaat (yinyang-persoon ?p) aan de hand van een regel. Dit predicaat slaagt als de kledij van persoon ?p uit minstens 2 stukken bestaat zodat het ene donker is en het andere licht (of vice versa). Je hoeft duplicaten niet te filteren.
implementeer het binaire predicaat (lichtere-kledij-voor ?p ?l) aan de hand van een of meerdere regels. Dit predicaat slaagt wanneer ?l overeenkomt met de kledij van ?p (een lijst van kledingstukken), waarin elk donker stuk vervangen is door hetzelfde stuk in een lichtere kleur.
Implementeer dit zodat o.a. volgende bevragingen beantwoord kunnen worden:> (lichtere-kledij-voor ilse ?suggestie) ;;; Query results:
(lichtere-kledij-voor ilse ((jurk wit) (tas wit)))
(lichtere-kledij-voor ilse ((jurk wit) (tas paars)))
(lichtere-kledij-voor ilse ((jurk wit) (tas kaki)))
(lichtere-kledij-voor ilse ((jurk wit) (tas geel)))
(lichtere-kledij-voor ilse ((jurk wit) (tas beige)))
done
Tip: Gebruik een hulp-regel (kleur-suggestie) die voor een kleur een suggestie kan geven, bijvoorbeeld:
> (kleur-suggestie ?kleur ?suggestie) ;;; Query results:
(kleur-suggestie zwart wit)
(kleur-suggestie wit wit)
(kleur-suggestie groen wit)
(kleur-suggestie paars paars)
(kleur-suggestie zwart paars)
(kleur-suggestie kaki kaki)
(kleur-suggestie rood wit)
(kleur-suggestie geel geel)
(kleur-suggestie zwart kaki)
(kleur-suggestie beige beige)
(kleur-suggestie groen paars)
(kleur-suggestie zwart geel)
(kleur-suggestie rood paars)
(kleur-suggestie zwart beige)
(kleur-suggestie groen kaki)
(kleur-suggestie rood kaki)
(kleur-suggestie groen geel)
(kleur-suggestie rood geel)
(kleur-suggestie groen beige)
(kleur-suggestie rood beige)
done
2.3 Oefening: Een volledig logisch programma: allergenen
Beschouw volgende feitenbank van voedingswaren en allergenen. Er bestaan 2 soorten feiten: feiten van de vorm (product <naam> <ingrediëntenlijst> <kostprijs-in-euro>) en feiten van de vorm (allergeen <ingrediëntnaam> <allergie-of-intolerantie>):
(product koek (graan suiker plantaardige-oliën zout melkpoeder) 2.9) (product frisdrank (sprankelend-water suiker citroensap E150d E338 E300) 4.2) (product keukenzout (zout) 0.5) (bevat-allergeen graan gluten-allergie) (bevat-allergeen melk lactose-intolerantie) (bevat-allergeen melk-poeder lactose-intolerantie) (bevat-allergeen kaas lactose-intolerantie) (bevat-allergeen pinda pinda-allergie)
> (assert! (product koek (graan suiker plantaardige-oliën zout melkpoeder) 2.9))
Assertion added to data base.
> (assert! (product frisdrank (sprankelend-water suiker citroensap E150d E338 E300) 4.2))
Assertion added to data base.
> (assert! (product keukenzout (zout) 0.5))
Assertion added to data base.
> (assert! (bevat-allergeen graan gluten-allergie))
Assertion added to data base.
> (assert! (bevat-allergeen melk lactose-intolerantie))
Assertion added to data base.
> (assert! (bevat-allergeen melk-poeder lactose-intolerantie))
Assertion added to data base.
> (assert! (bevat-allergeen kaas lactose-intolerantie))
Assertion added to data base.
> (assert! (bevat-allergeen pinda pinda-allergie))
Assertion added to data base.
Geef een logische query die alle producten vindt die minder dan €3 kosten.
Implementeer het predicaat product-met-allergenen aan de hand van een logische regel, zodat (product-met-allergenen ?prod) slaagt voor elk product waarvan minstens één ingrediënt een gekend allergeen is. Met bovenstaande databank is dan volgende interactie mogelijk:
> (product-met-allergenen ?p) ;;; Query results:
(product-met-allergenen koek)
done
Implementeer het predicaat product-met-meeste-ingrediënten aan de hand van een logische regel. (product-met-meeste-ingrediënten ?prod) slaagt enkel voor het product met de meeste ingrediënten. Je kan hiervoor een hulpregel (lijst-langer ?a ?b) definiëren die slaagt wanneer ?a en ?b lijsten zijn, en ?a meer cons-cellen bevat dan ?b. Met bovenstaande databank is dan volgende interactie mogelijk:
> (product-met-meeste-ingrediënten ?p) ;;; Query results:
(product-met-meeste-ingrediënten frisdrank)
done