Reeks 4 : Logisch Programmeren

8.7

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

> (is-planeet ?p)
;;; Query results:
(is-planeet Pluto)
(is-planeet Neptunus)
(is-planeet Uranus)
(is-planeet Saturnus)
(is-planeet Jupiter)
(is-planeet Mars)
(is-planeet Aarde)
(is-planeet Venus)
(is-planeet Mercurius)
done

de namen van alle manen van Jupiter
> (is-maan-van ?maan Jupiter)
;;; Query results:
(is-maan-van Callisto Jupiter)
(is-maan-van Ganymedes Jupiter)
(is-maan-van Europa Jupiter)
(is-maan-van Io Jupiter)
done
alle door Galilei ontdekte hemellichamen
> (is-ontdekt ?lichaam ?jaar Galilei)
;;; Query results:
(is-ontdekt Callisto 1610 Galilei)
(is-ontdekt Ganymedes 1610 Galilei)
(is-ontdekt Europa 1610 Galilei)
(is-ontdekt Io 1610 Galilei)
done
het jaar waarin Deimos werd ontdekt
> (is-ontdekt Deimos ?jaar ?persoon)
;;; Query results:
(is-ontdekt Deimos 1877 Hall)
done
de middellijn van Mars
> (heeft-middellijn Mars ?middellijn)
;;; Query results:
(heeft-middellijn Mars 6790)
done
de rotatietijd van Jupiter
> (heeft-rotatietijd Jupiter ?richting ?tijd)
;;; Query results:
(heeft-rotatietijd Jupiter + 0.41)
done

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.

Formuleer nu zelf een aantal queries om erachter te komen:

Van welke planeet Deimos een maan is en wat de afstand tot de Zon is van deze planeet
> (and (is-maan-van Deimos ?planeet)
(heeft-afstand-tot-zon ?planeet ?afstand))
;;; Query results:
(and (is-maan-van Deimos Mars) (heeft-afstand-tot-zon Mars 1.5237))
done

De afstand tot de Zon, rotatietijd en massa van de planeet Uranus

> (and (heeft-afstand-tot-zon Uranus ?afstand)
(heeft-rotatietijd Uranus ?rotatierichting ?rotatietijd)
(heeft-massa Uranus ?massa))
;;; Query results:
(and (heeft-afstand-tot-zon Uranus 19.1819) (heeft-rotatietijd Uranus - 0.45) (heeft-massa Uranus 14.5))
done

De namen van alle manen van Saturnus en Jupiter, samen met hun ontdekkers

> (and (or (is-maan-van ?maan Saturnus)
(is-maan-van ?maan Jupiter))
(is-ontdekt ?maan ?jaar ?ontdekker))
;;; Query results:
(and (or (is-maan-van Janus Saturnus) (is-maan-van Janus Jupiter)) (is-ontdekt Janus 1966 Dolfus))
(and (or (is-maan-van Callisto Saturnus) (is-maan-van Callisto Jupiter)) (is-ontdekt Callisto 1610 Galilei))
(and (or (is-maan-van Phoebe Saturnus) (is-maan-van Phoebe Jupiter)) (is-ontdekt Phoebe 1898 Pickering))
(and (or (is-maan-van Ganymedes Saturnus) (is-maan-van Ganymedes Jupiter)) (is-ontdekt Ganymedes 1610 Galilei))
(and (or (is-maan-van Japetus Saturnus) (is-maan-van Japetus Jupiter)) (is-ontdekt Japetus 1671 Cassini))
(and (or (is-maan-van Europa Saturnus) (is-maan-van Europa Jupiter)) (is-ontdekt Europa 1610 Galilei))
(and (or (is-maan-van Hyperion Saturnus) (is-maan-van Hyperion Jupiter)) (is-ontdekt Hyperion 1848 Bond))
(and (or (is-maan-van Io Saturnus) (is-maan-van Io Jupiter)) (is-ontdekt Io 1610 Galilei))
(and (or (is-maan-van Titan Saturnus) (is-maan-van Titan Jupiter)) (is-ontdekt Titan 1655 Huygens))
(and (or (is-maan-van Rhea Saturnus) (is-maan-van Rhea Jupiter)) (is-ontdekt Rhea 1672 Cassini))
(and (or (is-maan-van Dione Saturnus) (is-maan-van Dione Jupiter)) (is-ontdekt Dione 1684 Cassini))
(and (or (is-maan-van Tethys Saturnus) (is-maan-van Tethys Jupiter)) (is-ontdekt Tethys 1684 Cassini))
(and (or (is-maan-van Enceladus Saturnus) (is-maan-van Enceladus Jupiter)) (is-ontdekt Enceladus 1789 Herschel))
(and (or (is-maan-van Mimas Saturnus) (is-maan-van Mimas Jupiter)) (is-ontdekt Mimas 1789 Herschel))
done

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

Formuleer nu zelf queries die volgende vragen beantwoorden:

de namen van planeten die geen maan hebben

> (and (is-planeet ?p)
(not (is-maan-van ?maan ?p)))
;;; Query results:
(and (is-planeet Pluto) (not (is-maan-van ?maan Pluto)))
(and (is-planeet Venus) (not (is-maan-van ?maan Venus)))
(and (is-planeet Mercurius) (not (is-maan-van ?maan Mercurius)))
done

de namen van planeten kleiner dan de Aarde

> (and (is-planeet ?p)
       (heeft-middellijn ?p ?middellijn)
       (heeft-middellijn Aarde ?middellijnAarde)
       (lisp-value < ?middellijn ?middellijnAarde))
;;; Query results:
(and (is-planeet Pluto) (heeft-middellijn Pluto 5000) (heeft-middellijn Aarde 12756) (lisp-value < 5000 12756))
(and (is-planeet Mars) (heeft-middellijn Mars 6790) (heeft-middellijn Aarde 12756) (lisp-value < 6790 12756))
(and (is-planeet Venus) (heeft-middellijn Venus 12200) (heeft-middellijn Aarde 12756) (lisp-value < 12200 12756))
(and (is-planeet Mercurius) (heeft-middellijn Mercurius 4840) (heeft-middellijn Aarde 12756) (lisp-value < 4840 12756))
done

de planeet met de grootste massa

> (and (is-planeet ?p)
       (heeft-massa ?p ?m)
       (not (and (is-planeet ?p2)
                 (heeft-massa ?p2 ?m2)
                 (lisp-value > ?m2 ?m))))
;;; Query results:
(and (is-planeet Jupiter) (heeft-massa Jupiter 317.9) (not (and (is-planeet ?p2) (heeft-massa ?p2 ?m2) (lisp-value > ?m2 317.9))))
done

het object (maan of planeet) met de kleinste middellijn in de databank

> (and (or (is-planeet ?object)
           (is-maan-van ?object ?planeet))
       (heeft-middellijn ?object ?m)
       (not (and (or (is-planeet ?object2)
                     (is-maan-van ?object2 ?planeet2))
                 (heeft-middellijn ?object2 ?m2)
                 (lisp-value < ?m2 ?m))))
;;; Query results:
(and (or (is-planeet Deimos) (is-maan-van Deimos Mars)) (heeft-middellijn Deimos 8) (not (and (or (is-planeet ?object2) (is-maan-van ?object2 ?planeet2)) (heeft-middellijn ?object2 ?m2) (lisp-value < ?m2 8))))
done

de manen ontdekt voor 1700 of door Galilei

> (and (is-maan-van ?maan ?planeet)
       (is-ontdekt ?maan ?jaar ?persoon)
       (or (lisp-value < ?jaar 1700)
           (lisp-value equal? ?persoon Galilei)))
;;; Query results:
(and (is-maan-van Japetus Saturnus) (is-ontdekt Japetus 1671 Cassini) (or (lisp-value < 1671 1700) (lisp-value equal? Cassini Galilei)))
(and (is-maan-van Callisto Jupiter) (is-ontdekt Callisto 1610 Galilei) (or (lisp-value < 1610 1700) (lisp-value equal? Galilei Galilei)))
(and (is-maan-van Titan Saturnus) (is-ontdekt Titan 1655 Huygens) (or (lisp-value < 1655 1700) (lisp-value equal? Huygens Galilei)))
(and (is-maan-van Ganymedes Jupiter) (is-ontdekt Ganymedes 1610 Galilei) (or (lisp-value < 1610 1700) (lisp-value equal? Galilei Galilei)))
(and (is-maan-van Rhea Saturnus) (is-ontdekt Rhea 1672 Cassini) (or (lisp-value < 1672 1700) (lisp-value equal? Cassini Galilei)))
(and (is-maan-van Europa Jupiter) (is-ontdekt Europa 1610 Galilei) (or (lisp-value < 1610 1700) (lisp-value equal? Galilei Galilei)))
(and (is-maan-van Dione Saturnus) (is-ontdekt Dione 1684 Cassini) (or (lisp-value < 1684 1700) (lisp-value equal? Cassini Galilei)))
(and (is-maan-van Io Jupiter) (is-ontdekt Io 1610 Galilei) (or (lisp-value < 1610 1700) (lisp-value equal? Galilei Galilei)))
(and (is-maan-van Tethys Saturnus) (is-ontdekt Tethys 1684 Cassini) (or (lisp-value < 1684 1700) (lisp-value equal? Cassini Galilei)))
(and (is-maan-van Callisto Jupiter) (is-ontdekt Callisto 1610 Galilei) (or (lisp-value < 1610 1700) (lisp-value equal? Galilei Galilei)))
(and (is-maan-van Ganymedes Jupiter) (is-ontdekt Ganymedes 1610 Galilei) (or (lisp-value < 1610 1700) (lisp-value equal? Galilei Galilei)))
(and (is-maan-van Europa Jupiter) (is-ontdekt Europa 1610 Galilei) (or (lisp-value < 1610 1700) (lisp-value equal? Galilei Galilei)))
(and (is-maan-van Io Jupiter) (is-ontdekt Io 1610 Galilei) (or (lisp-value < 1610 1700) (lisp-value equal? Galilei Galilei)))
done

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

Voeg nu zelf volgende regels toe:

een regel (is-maan ?x) die bepaalt of ?x een maan is
> (assert! (rule (is-maan ?x)
(is-maan-van ?x ?p)))
Assertion added to data base.
een regel (heeft-maan ?p) die bepaalt of een planeet ?p (één of meerdere) manen heeft
> (assert! (rule (heeft-maan ?p)
(is-maan-van ?maan ?p)))
Assertion added to data base.

een regel (kleiner ?x ?y) die bepaalt of ?x een kleiner hemellichaam is dan ?y

> (assert! (rule (kleiner ?x ?y)
                 (and (heeft-middellijn ?x ?m)
                      (heeft-middellijn ?y ?n)
                      (lisp-value < ?m ?n))))
Assertion added to data base.

2 Logisch Programmeren

2.1 Oefening: Logisch Programmeren

Volgend logisch programma achterhaalt het laatste element van een lijst:

(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.

> (assert! (rule (element ?first (?first . ?rest))))
Assertion added to data base.
> (assert! (rule (element ?el (?first . ?rest))
(element ?el ?rest)))
Assertion added to data base.

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.

> (assert! (rule (selection (?first . ?selectedInRest) (?first . ?rest))
(selection ?selectedInRest ?rest)))
Assertion added to data base.
> (assert! (rule (selection ?selection (?first . ?rest))
(selection ?selection ?rest)))
Assertion added to data base.
> (assert! (rule (selection () ())))
Assertion added to data base.

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.

> (assert! (rule (prefix () ?list)))
Assertion added to data base.
> (assert! (rule (prefix (?first . ?restprefix) (?first . ?rest))
                 (prefix ?restprefix ?rest)))
Assertion added to data base.
Een alternatief is het volgende:
(assert! (rule (append () ?lijst ?lijst)))
(assert! (rule (append (?first . ?rest) ?lijst (?first . ?resultaat))
               (append ?rest ?lijst ?resultaat)))
(assert! (rule (prefix ?li ?list)
               (append ?li ?st ?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.

> (assert! (rule (postfix ?list ?list)))
Assertion added to data base.
> (assert! (rule (postfix ?post (?first . ?rest))
(postfix ?post ?rest)))
Assertion added to data base.
Opnieuw is een alternatief a.d.h.v. append mogelijk:
(assert! (rule (append () ?lijst ?lijst)))
(assert! (rule (append (?first . ?rest) ?lijst (?first . ?resultaat)) (append ?rest ?lijst ?resultaat)))
(assert! (rule (postfix ?st ?list) (append ?li ?st ?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.

> (assert! (rule (sublist ?sub ?list)
(and (prefix ?prefix ?list)
(postfix ?sub ?prefix))))
Assertion added to data base.

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.

> (assert! (rule (extract (?h . ?t) ?h ?t)))
Assertion added to data base.
> (assert! (rule (extract (?h . ?t) ?x (?h . ?l))
(extract ?t ?x ?l)))
Assertion added to data base.
> (assert! (rule (permute () ())))
Assertion added to data base.
> (assert! (rule (permute ?l (?x . ?t))
(and (extract ?l ?x ?s) (permute ?s ?t))))
Assertion added to data base.

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.

We kunnen opnieuw gebruik maken van de append regel:
> (assert! (rule (append () ?lijst ?lijst)))
Assertion added to data base.
> (assert! (rule (append (?first . ?rest) ?lijst (?first . ?resultaat))
                 (append ?rest ?lijst ?resultaat)))
Assertion added to data base.
Aan de hand hiervan is de reverse eenvoudig te schrijven als:
> (assert! (rule (reverse () ())))
Assertion added to data base.
> (assert! (rule (reverse ?reversed (?first . ?rest))
                 (and (reverse ?revrest ?rest)
                      (append ?revrest (?first) ?reversed))))
Assertion added to data base.

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”:

(is-kleur ?kleur)

(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))

(kleur-heeft-helderheid ?kleur ?helderheid)

(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))

(persoon-draagt ?persoon ?kledijlijst)

(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))))

Volgende data dient ingegeven te zijn (of alternatief bovenstaande data als databank-bestand ingelezen):
> (assert! (is-kleur rood))
Assertion added to data base.
> (assert! (is-kleur groen))
Assertion added to data base.
> (assert! (is-kleur beige))
Assertion added to data base.
> (assert! (is-kleur zwart))
Assertion added to data base.
> (assert! (is-kleur geel))
Assertion added to data base.
> (assert! (is-kleur kaki))
Assertion added to data base.
> (assert! (is-kleur paars))
Assertion added to data base.
> (assert! (is-kleur wit))
Assertion added to data base.
> (assert! (kleur-heeft-helderheid rood 333))
Assertion added to data base.
> (assert! (kleur-heeft-helderheid groen 196))
Assertion added to data base.
> (assert! (kleur-heeft-helderheid beige 944))
Assertion added to data base.
> (assert! (kleur-heeft-helderheid zwart 0))
Assertion added to data base.
> (assert! (kleur-heeft-helderheid geel 833))
Assertion added to data base.
> (assert! (kleur-heeft-helderheid kaki 856))
Assertion added to data base.
> (assert! (kleur-heeft-helderheid paars 722))
Assertion added to data base.
> (assert! (kleur-heeft-helderheid wit 1000))
Assertion added to data base.
> (assert! (persoon-draagt ilse ((jurk wit) (tas zwart))))
Assertion added to data base.
> (assert! (persoon-draagt evi ((hemd rood) (riem zwart) (broek zwart))))
Assertion added to data base.
> (assert! (persoon-draagt jan ((hemd wit) (linkersok zwart) (rechtersok zwart))))
Assertion added to data base.

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.

> (assert!
   (rule (kleur-is-donker ?k)
         (and
          (is-kleur ?k)
          (kleur-heeft-helderheid ?k ?h)
          (lisp-value < ?h 500))))
Assertion added to data base.

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).
> (assert!
   (rule (kleur-is-licht ?k)
         (and
          (is-kleur ?k)
          (not (kleur-is-donker ?k)))))
Assertion added to data base.
Bemerk de conjunct (is-kleur ?k), zorg dat je begrijpt waarom deze belangrijk is. Bekijk het verschil tussen de resultaten voor (kleur-is-licht wit) en (kleur-is-licht ?kleur) wanneer deze conjunct weggelaten is om het te begrijpen welke invloed de negation as failure/closed world assumption heeft op de werking van de not.
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.

> (assert!
   (rule (yinyang-persoon ?p)
         (and (persoon-draagt ?p ?kledij)
              (element (?stuk1 ?kleur1) ?kledij)
              (element (?stuk2 ?kleur2) ?kledij)
              (or (and (kleur-is-licht ?kleur1)
                       (kleur-is-donker ?kleur2))
                  (and (kleur-is-licht ?kleur2)
                       (kleur-is-donker ?kleur1))))))
Assertion added to data base.

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.

> (assert!
   (rule (kleur-suggestie ?kleur ?kleur)
         (kleur-is-licht ?kleur)))
Assertion added to data base.
> (assert!
   (rule (kleur-suggestie ?kleur ?lichter)
         (and (kleur-is-donker ?kleur)
              (kleur-is-licht ?lichter))))
Assertion added to data base.
> (assert!
   (rule (lichtere-kledij-voor ?p ?suggestie-kledij)
         (and (persoon-draagt ?p ?kledij)
              (transform-kledij ?kledij ?suggestie-kledij))))
Assertion added to data base.
> (assert!
   (rule (transform-kledij () ())))
Assertion added to data base.
> (assert!
   (rule (transform-kledij ((?stuk ?kleur) . ?rest)
                           ((?stuk ?lichter) . ?restsuggestie))
         (and (kleur-suggestie ?kleur ?lichter)
              (transform-kledij ?rest ?restsuggestie))))
Assertion added to data base.

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.
(and
(product ?naam ?i ?prijs)
(lisp-value > ?prijs 2.5))

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:

> (assert! (rule (lijst-bevat (?e . ?r) ?e)))
Assertion added to data base.
> (assert! (rule (lijst-bevat (?x . ?r) ?e)
                 (lijst-bevat ?r ?e)))
Assertion added to data base.
> (assert! (rule (product-met-allergenen ?p)
                 (and (product ?p ?ingr ?pr)
                      (lijst-bevat ?ingr ?i)
                      (bevat-allergeen ?i ?allergie))))
Assertion added to data base.

> (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:

> (assert! (rule (lijst-langer (?f . ?r) ())))
Assertion added to data base.
> (assert! (rule (lijst-langer (?a . ?b) (?c . ?d))
                 (lijst-langer ?b ?d)))
Assertion added to data base.
> (assert! (rule (product-met-meeste-ingrediënten ?p)
                 (and (product ?p ?i-p ?pr-p)
                      (not (and (product ?o ?i-o ?pr-o)
                                (lijst-langer ?i-o ?i-p))))))
Assertion added to data base.

> (product-met-meeste-ingrediënten ?p)
;;; Query results:
(product-met-meeste-ingrediënten frisdrank)
done