►Reeks 5 :   De Query Evaluator
Reeks 5 :   De Query Evaluator
1 Oefening:   Tracen van expressies
2 Oefening:   Enkel de eerste oplossing
3 Oefening:   Duplicaten uit oplossingen verwijderen
4 Oefening:   Unieke oplossingen
8.9

Reeks 5 : De Query Evaluator

Deze oefeningenreeks behandelt de implementatie van de query evaluator uit hoofdstuk 4.4. De query evaluator is nog steeds te vinden in het bestand "icp_4_qeval.scm". Opnieuw moet het bestand "icp_4_qeval_zonnestelsel.txt" zich in dezelfde directory bevinden.

1 Oefening: Tracen van expressies

Voeg de special form (trace <query>) toe aan de query evaluator. Deze special form gedraagt zich precies hetzelfde als wanneer gewoon <query> gebruikt wordt, maar toont de oplossingsframes voor de query op scherm. Deze special form neemt steeds precies één argument.

Bijvoorbeeld:
> (and (trace (is-planeet ?p)) (trace (is-maan-van ?m ?p)))

;;; Query results:

TRACING {?p = Pluto}

TRACING {?p = Neptunus}

TRACING {?m = Nereide, ?p = Neptunus}

(and (trace (is-planeet Neptunus)) (trace (is-maan-van Nereide Neptunus)))

TRACING {?p = Uranus}

TRACING {?m = Miranda, ?p = Uranus}

(and (trace (is-planeet Uranus)) (trace (is-maan-van Miranda Uranus)))

TRACING {?m = Triton, ?p = Neptunus}

(and (trace (is-planeet Neptunus)) (trace (is-maan-van Triton Neptunus)))

TRACING {?p = Saturnus}

TRACING {?m = Janus, ?p = Saturnus}

(and (trace (is-planeet Saturnus)) (trace (is-maan-van Janus Saturnus)))

TRACING {?m = Oberon, ?p = Uranus}

(and (trace (is-planeet Uranus)) (trace (is-maan-van Oberon Uranus)))

TRACING {?p = Jupiter}

TRACING {?m = Callisto, ?p = Jupiter}

(and (trace (is-planeet Jupiter)) (trace (is-maan-van Callisto Jupiter)))

TRACING {?m = Titania, ?p = Uranus}

(and (trace (is-planeet Uranus)) (trace (is-maan-van Titania Uranus)))

TRACING {?m = Phoebe, ?p = Saturnus}

(and (trace (is-planeet Saturnus)) (trace (is-maan-van Phoebe Saturnus)))

TRACING {?m = Umbriel, ?p = Uranus}

(and (trace (is-planeet Uranus)) (trace (is-maan-van Umbriel Uranus)))

TRACING {?p = Mars}

TRACING {?m = Deimos, ?p = Mars}

(and (trace (is-planeet Mars)) (trace (is-maan-van Deimos Mars)))

TRACING {?m = Ariel, ?p = Uranus}

(and (trace (is-planeet Uranus)) (trace (is-maan-van Ariel Uranus)))

TRACING {?m = Japetus, ?p = Saturnus}

(and (trace (is-planeet Saturnus)) (trace (is-maan-van Japetus Saturnus)))

TRACING {?m = Ganymedes, ?p = Jupiter}

(and (trace (is-planeet Jupiter)) (trace (is-maan-van Ganymedes Jupiter)))

TRACING {?m = Hyperion, ?p = Saturnus}

(and (trace (is-planeet Saturnus)) (trace (is-maan-van Hyperion Saturnus)))

TRACING {?p = Aarde}

TRACING {?m = Maan, ?p = Aarde}

(and (trace (is-planeet Aarde)) (trace (is-maan-van Maan Aarde)))

TRACING {?m = Titan, ?p = Saturnus}

(and (trace (is-planeet Saturnus)) (trace (is-maan-van Titan Saturnus)))

TRACING {?m = Europa, ?p = Jupiter}

(and (trace (is-planeet Jupiter)) (trace (is-maan-van Europa Jupiter)))

TRACING {?m = Rhea, ?p = Saturnus}

(and (trace (is-planeet Saturnus)) (trace (is-maan-van Rhea Saturnus)))

TRACING {?m = Phobos, ?p = Mars}

(and (trace (is-planeet Mars)) (trace (is-maan-van Phobos Mars)))

TRACING {?m = Dione, ?p = Saturnus}

(and (trace (is-planeet Saturnus)) (trace (is-maan-van Dione Saturnus)))

TRACING {?m = Io, ?p = Jupiter}

(and (trace (is-planeet Jupiter)) (trace (is-maan-van Io Jupiter)))

TRACING {?m = Tethys, ?p = Saturnus}

(and (trace (is-planeet Saturnus)) (trace (is-maan-van Tethys Saturnus)))

TRACING {?p = Venus}

TRACING {?p = Mercurius}

TRACING {?m = Enceladus, ?p = Saturnus}

(and (trace (is-planeet Saturnus)) (trace (is-maan-van Enceladus Saturnus)))

TRACING {?m = Mimas, ?p = Saturnus}

(and (trace (is-planeet Saturnus)) (trace (is-maan-van Mimas Saturnus)))

done

Onderneem volgende stappen voor deze oefening:

  1. Alle special forms van de query evaluator (zoals and, or, not, of lisp-value) worden op een data-directed manier beheerd. Nieuwe special forms kunnen gedefinieerd worden met de procedure put en later opgevraagd worden met de procedure get. De initialisatie van de special forms is ondergebracht in de procedure initialize-data-base. Introduceer nu de nieuwe special form trace en associeer deze aan de (vooralsnog niet-geïmplementeerde) procedure trace.

  2. Implementeer nu de procedure trace. Deze procedure heef twee argumenten: args (d.i. een lijst die de argumenten van de trace-expressie bevat) en frame-stream (d.i. een framestream met reeds gemaakte bindingen). Voorzie de nodige controle-structuren die nagaan of trace met een correct aantal argumenten wordt opgeroepen. Voorzie daarnaast extra abstracties indien nodig.

(define (trace args frame-stream)
        ...)

Opgepast!

  • Let op dat de uitgestelde evaluatie van de stream van frames niet wordt beïnvloed. Gebruik daarom stream-map.

  • De return-waarde van de procedure trace dient dezelfde te zijn als van een gewone query. Immers:

    • De query in kwestie kan een subquery zijn van een omliggende query. In dat geval moet de resulterende framestream van de subquery doorgepropageerd worden naar de omliggende query.

    • Het kan gaan om een top-niveau query. In dat geval is de framestream nodig zodat de driver-loop de resultaten op het scherm kan zetten.

2 Oefening: Enkel de eerste oplossing

Voeg een special form (first <query>) toe die enkel de eerstgevonden oplossing voor <query> teruggeeft.

Bijvoorbeeld:

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

> (first (is-planeet ?p))

;;; Query results:

(first (is-planeet Pluto))

done

De special form first is bijvoorbeeld interessant voor het definiëren van het predicaat (heeft-maan ?p) dat al mag slagen van zodra er een maan voor de planeet ?p gevonden is:

> (assert! (rule (heeft-maan ?p)
                 (and (is-planeet ?p)
                      (first (is-maan-van ?m ?p)))))

Assertion added to data base.

> (heeft-maan ?p)

;;; Query results:

(heeft-maan Neptunus)

(heeft-maan Uranus)

(heeft-maan Saturnus)

(heeft-maan Jupiter)

(heeft-maan Mars)

(heeft-maan Aarde)

done

3 Oefening: Duplicaten uit oplossingen verwijderen

Misschien heb je al gemerkt dat de oplossingenstream voor bepaalde queries duplicaten bevat. Dit is bijvoorbeeld het geval voor de volgende query:

> (or (is-planeet ?p) (is-planeet ?p))

;;; Query results:

(or (is-planeet Pluto) (is-planeet Pluto))

(or (is-planeet Pluto) (is-planeet Pluto))

(or (is-planeet Neptunus) (is-planeet Neptunus))

(or (is-planeet Neptunus) (is-planeet Neptunus))

(or (is-planeet Uranus) (is-planeet Uranus))

(or (is-planeet Uranus) (is-planeet Uranus))

(or (is-planeet Saturnus) (is-planeet Saturnus))

(or (is-planeet Saturnus) (is-planeet Saturnus))

(or (is-planeet Jupiter) (is-planeet Jupiter))

(or (is-planeet Jupiter) (is-planeet Jupiter))

(or (is-planeet Mars) (is-planeet Mars))

(or (is-planeet Mars) (is-planeet Mars))

(or (is-planeet Aarde) (is-planeet Aarde))

(or (is-planeet Aarde) (is-planeet Aarde))

(or (is-planeet Venus) (is-planeet Venus))

(or (is-planeet Venus) (is-planeet Venus))

(or (is-planeet Mercurius) (is-planeet Mercurius))

(or (is-planeet Mercurius) (is-planeet Mercurius))

done

Voeg een special form (nodup <patroon>) toe die duplicaten voor <patroon> uit de binnenkomende stream filtert. Voor bovenstaand voorbeeld dient nodup als volgt gebruikt te worden:

> (and (or (is-planeet ?p)
           (is-planeet ?p))
       (nodup ?p))

;;; Query results:

(and (or (is-planeet Pluto) (is-planeet Pluto)) (nodup Pluto))

(and (or (is-planeet Neptunus) (is-planeet Neptunus)) (nodup Neptunus))

(and (or (is-planeet Uranus) (is-planeet Uranus)) (nodup Uranus))

(and (or (is-planeet Saturnus) (is-planeet Saturnus)) (nodup Saturnus))

(and (or (is-planeet Jupiter) (is-planeet Jupiter)) (nodup Jupiter))

(and (or (is-planeet Mars) (is-planeet Mars)) (nodup Mars))

(and (or (is-planeet Aarde) (is-planeet Aarde)) (nodup Aarde))

(and (or (is-planeet Venus) (is-planeet Venus)) (nodup Venus))

(and (or (is-planeet Mercurius) (is-planeet Mercurius)) (nodup Mercurius))

done

Deze special form is een filter, net zoals lisp-value en not. De binnenkomende stream van frames wordt gefilterd zodanig dat alle duplicate instanties van <patroon> worden verwijderd. Het argument van nodup is een patroon dat voor elke binnenkomende frame wordt geïnstantieerd. Als deze instantie voor verschillende frames hetzelfde resultaat oplevert (bv. verschillende frames met eenzelfde binding voor ?p), dan wordt enkel de eerste van deze frames behouden.

Hint Je kan door de resultatenstream wandelen en een verzameling opbouwen van de patroon-instanties die je tegenkomt. Op basis van deze verzameling kan je testen op duplicaten.

Verklaar het verschil in oplossingen voor volgende queries:
> (and (or (is-planeet ?p)
           (is-planeet ?p))
       (is-planeet ?m)
       (nodup ?p))

;;; Query results:

(and (or (is-planeet Pluto) (is-planeet Pluto)) (is-planeet Pluto) (nodup Pluto))

(and (or (is-planeet Neptunus) (is-planeet Neptunus)) (is-planeet Pluto) (nodup Neptunus))

(and (or (is-planeet Uranus) (is-planeet Uranus)) (is-planeet Pluto) (nodup Uranus))

(and (or (is-planeet Saturnus) (is-planeet Saturnus)) (is-planeet Pluto) (nodup Saturnus))

(and (or (is-planeet Jupiter) (is-planeet Jupiter)) (is-planeet Pluto) (nodup Jupiter))

(and (or (is-planeet Mars) (is-planeet Mars)) (is-planeet Pluto) (nodup Mars))

(and (or (is-planeet Aarde) (is-planeet Aarde)) (is-planeet Pluto) (nodup Aarde))

(and (or (is-planeet Venus) (is-planeet Venus)) (is-planeet Pluto) (nodup Venus))

(and (or (is-planeet Mercurius) (is-planeet Mercurius)) (is-planeet Pluto) (nodup Mercurius))

done

> (and (or (is-planeet ?p)
           (is-planeet ?p))
       (nodup ?p)
       (is-planeet ?m))

;;; Query results:

(and (or (is-planeet Pluto) (is-planeet Pluto)) (nodup Pluto) (is-planeet Pluto))

(and (or (is-planeet Neptunus) (is-planeet Neptunus)) (nodup Neptunus) (is-planeet Pluto))

(and (or (is-planeet Pluto) (is-planeet Pluto)) (nodup Pluto) (is-planeet Neptunus))

(and (or (is-planeet Uranus) (is-planeet Uranus)) (nodup Uranus) (is-planeet Pluto))

(and (or (is-planeet Pluto) (is-planeet Pluto)) (nodup Pluto) (is-planeet Uranus))

(and (or (is-planeet Neptunus) (is-planeet Neptunus)) (nodup Neptunus) (is-planeet Neptunus))

(and (or (is-planeet Pluto) (is-planeet Pluto)) (nodup Pluto) (is-planeet Saturnus))

(and (or (is-planeet Saturnus) (is-planeet Saturnus)) (nodup Saturnus) (is-planeet Pluto))

(and (or (is-planeet Pluto) (is-planeet Pluto)) (nodup Pluto) (is-planeet Jupiter))

(and (or (is-planeet Neptunus) (is-planeet Neptunus)) (nodup Neptunus) (is-planeet Uranus))

(and (or (is-planeet Pluto) (is-planeet Pluto)) (nodup Pluto) (is-planeet Mars))

(and (or (is-planeet Uranus) (is-planeet Uranus)) (nodup Uranus) (is-planeet Neptunus))

(and (or (is-planeet Pluto) (is-planeet Pluto)) (nodup Pluto) (is-planeet Aarde))

(and (or (is-planeet Neptunus) (is-planeet Neptunus)) (nodup Neptunus) (is-planeet Saturnus))

(and (or (is-planeet Pluto) (is-planeet Pluto)) (nodup Pluto) (is-planeet Venus))

(and (or (is-planeet Jupiter) (is-planeet Jupiter)) (nodup Jupiter) (is-planeet Pluto))

(and (or (is-planeet Pluto) (is-planeet Pluto)) (nodup Pluto) (is-planeet Mercurius))

(and (or (is-planeet Neptunus) (is-planeet Neptunus)) (nodup Neptunus) (is-planeet Jupiter))

(and (or (is-planeet Uranus) (is-planeet Uranus)) (nodup Uranus) (is-planeet Uranus))

(and (or (is-planeet Neptunus) (is-planeet Neptunus)) (nodup Neptunus) (is-planeet Mars))

(and (or (is-planeet Saturnus) (is-planeet Saturnus)) (nodup Saturnus) (is-planeet Neptunus))

(and (or (is-planeet Neptunus) (is-planeet Neptunus)) (nodup Neptunus) (is-planeet Aarde))

(and (or (is-planeet Uranus) (is-planeet Uranus)) (nodup Uranus) (is-planeet Saturnus))

(and (or (is-planeet Neptunus) (is-planeet Neptunus)) (nodup Neptunus) (is-planeet Venus))

(and (or (is-planeet Mars) (is-planeet Mars)) (nodup Mars) (is-planeet Pluto))

(and (or (is-planeet Neptunus) (is-planeet Neptunus)) (nodup Neptunus) (is-planeet Mercurius))

(and (or (is-planeet Uranus) (is-planeet Uranus)) (nodup Uranus) (is-planeet Jupiter))

(and (or (is-planeet Saturnus) (is-planeet Saturnus)) (nodup Saturnus) (is-planeet Uranus))

(and (or (is-planeet Uranus) (is-planeet Uranus)) (nodup Uranus) (is-planeet Mars))

(and (or (is-planeet Jupiter) (is-planeet Jupiter)) (nodup Jupiter) (is-planeet Neptunus))

(and (or (is-planeet Uranus) (is-planeet Uranus)) (nodup Uranus) (is-planeet Aarde))

(and (or (is-planeet Saturnus) (is-planeet Saturnus)) (nodup Saturnus) (is-planeet Saturnus))

(and (or (is-planeet Uranus) (is-planeet Uranus)) (nodup Uranus) (is-planeet Venus))

(and (or (is-planeet Aarde) (is-planeet Aarde)) (nodup Aarde) (is-planeet Pluto))

(and (or (is-planeet Uranus) (is-planeet Uranus)) (nodup Uranus) (is-planeet Mercurius))

(and (or (is-planeet Saturnus) (is-planeet Saturnus)) (nodup Saturnus) (is-planeet Jupiter))

(and (or (is-planeet Jupiter) (is-planeet Jupiter)) (nodup Jupiter) (is-planeet Uranus))

(and (or (is-planeet Saturnus) (is-planeet Saturnus)) (nodup Saturnus) (is-planeet Mars))

(and (or (is-planeet Mars) (is-planeet Mars)) (nodup Mars) (is-planeet Neptunus))

(and (or (is-planeet Saturnus) (is-planeet Saturnus)) (nodup Saturnus) (is-planeet Aarde))

(and (or (is-planeet Jupiter) (is-planeet Jupiter)) (nodup Jupiter) (is-planeet Saturnus))

(and (or (is-planeet Saturnus) (is-planeet Saturnus)) (nodup Saturnus) (is-planeet Venus))

(and (or (is-planeet Venus) (is-planeet Venus)) (nodup Venus) (is-planeet Pluto))

(and (or (is-planeet Saturnus) (is-planeet Saturnus)) (nodup Saturnus) (is-planeet Mercurius))

(and (or (is-planeet Jupiter) (is-planeet Jupiter)) (nodup Jupiter) (is-planeet Jupiter))

(and (or (is-planeet Mars) (is-planeet Mars)) (nodup Mars) (is-planeet Uranus))

(and (or (is-planeet Jupiter) (is-planeet Jupiter)) (nodup Jupiter) (is-planeet Mars))

(and (or (is-planeet Aarde) (is-planeet Aarde)) (nodup Aarde) (is-planeet Neptunus))

(and (or (is-planeet Jupiter) (is-planeet Jupiter)) (nodup Jupiter) (is-planeet Aarde))

(and (or (is-planeet Mars) (is-planeet Mars)) (nodup Mars) (is-planeet Saturnus))

(and (or (is-planeet Jupiter) (is-planeet Jupiter)) (nodup Jupiter) (is-planeet Venus))

(and (or (is-planeet Mercurius) (is-planeet Mercurius)) (nodup Mercurius) (is-planeet Pluto))

(and (or (is-planeet Jupiter) (is-planeet Jupiter)) (nodup Jupiter) (is-planeet Mercurius))

(and (or (is-planeet Mars) (is-planeet Mars)) (nodup Mars) (is-planeet Jupiter))

(and (or (is-planeet Aarde) (is-planeet Aarde)) (nodup Aarde) (is-planeet Uranus))

(and (or (is-planeet Mars) (is-planeet Mars)) (nodup Mars) (is-planeet Mars))

(and (or (is-planeet Venus) (is-planeet Venus)) (nodup Venus) (is-planeet Neptunus))

(and (or (is-planeet Mars) (is-planeet Mars)) (nodup Mars) (is-planeet Aarde))

(and (or (is-planeet Aarde) (is-planeet Aarde)) (nodup Aarde) (is-planeet Saturnus))

(and (or (is-planeet Mars) (is-planeet Mars)) (nodup Mars) (is-planeet Venus))

(and (or (is-planeet Mercurius) (is-planeet Mercurius)) (nodup Mercurius) (is-planeet Neptunus))

(and (or (is-planeet Mars) (is-planeet Mars)) (nodup Mars) (is-planeet Mercurius))

(and (or (is-planeet Aarde) (is-planeet Aarde)) (nodup Aarde) (is-planeet Jupiter))

(and (or (is-planeet Venus) (is-planeet Venus)) (nodup Venus) (is-planeet Uranus))

(and (or (is-planeet Aarde) (is-planeet Aarde)) (nodup Aarde) (is-planeet Mars))

(and (or (is-planeet Mercurius) (is-planeet Mercurius)) (nodup Mercurius) (is-planeet Uranus))

(and (or (is-planeet Aarde) (is-planeet Aarde)) (nodup Aarde) (is-planeet Aarde))

(and (or (is-planeet Venus) (is-planeet Venus)) (nodup Venus) (is-planeet Saturnus))

(and (or (is-planeet Aarde) (is-planeet Aarde)) (nodup Aarde) (is-planeet Venus))

(and (or (is-planeet Mercurius) (is-planeet Mercurius)) (nodup Mercurius) (is-planeet Saturnus))

(and (or (is-planeet Aarde) (is-planeet Aarde)) (nodup Aarde) (is-planeet Mercurius))

(and (or (is-planeet Venus) (is-planeet Venus)) (nodup Venus) (is-planeet Jupiter))

(and (or (is-planeet Mercurius) (is-planeet Mercurius)) (nodup Mercurius) (is-planeet Jupiter))

(and (or (is-planeet Venus) (is-planeet Venus)) (nodup Venus) (is-planeet Mars))

(and (or (is-planeet Mercurius) (is-planeet Mercurius)) (nodup Mercurius) (is-planeet Mars))

(and (or (is-planeet Venus) (is-planeet Venus)) (nodup Venus) (is-planeet Aarde))

(and (or (is-planeet Mercurius) (is-planeet Mercurius)) (nodup Mercurius) (is-planeet Aarde))

(and (or (is-planeet Venus) (is-planeet Venus)) (nodup Venus) (is-planeet Venus))

(and (or (is-planeet Mercurius) (is-planeet Mercurius)) (nodup Mercurius) (is-planeet Venus))

(and (or (is-planeet Venus) (is-planeet Venus)) (nodup Venus) (is-planeet Mercurius))

(and (or (is-planeet Mercurius) (is-planeet Mercurius)) (nodup Mercurius) (is-planeet Mercurius))

done

4 Oefening: Unieke oplossingen

Voeg de special form (unique <query>) toe aan de query evaluator. Deze special form slaagt alleen wanneer <query> precies één oplossing heeft.

Bijvoorbeeld:
> (unique (is-maan-van ?m Aarde))

;;; Query results:

(unique (is-maan-van Maan Aarde))

done

> (unique (is-maan-van ?m Jupiter))

;;; Query results:

done

> (and (is-planeet ?p)
       (unique (is-maan-van ?m ?p)))

;;; Query results:

(and (is-planeet Aarde) (unique (is-maan-van Maan Aarde)))

done