Leikkauksen (cut) käyttö

Leikkaus '!' on ehkä Prologin hankalimmin sisäistettävä ominaisuus, koska se liittyy läheisesti siihen, miten Prologtulkki suorittaa ohjelmaa. Sen tarkoituksena on antaa ohjelmoijalle mahdollisuus karsia tulkin käyttämää hakupuuta dynaamisesti ajon aikana. Sitä voidaan käyttää estämään ohjelmaa seuraamasta hakupolkuja, jotka ohjelmoija tietää hedelmättömiksi. Näin käytettynä se tehostaa ohjelman toimintaa. Tällaista leikkausta, joka ei muuta ohjelman toimintaa sen löytämien ratkaisujen suhteen, kutsutaan vihreäksi leikkaukseksi. Leikkauksen avulla voidaan myöskin karsia sellaisia hakupolkuja, joiden päästä löytyy ratkaisuja, jolloin saadaan aikaan eräänlainen negaatio. Tällaista leikkauksen käyttöä kutsutaan punaiseksi leikkaukseksi. Punaiset leikkaukset synnyttävät ohjelmaan järjestysriippuvuuden, eikä predikaatin kaavojen keskinäistä järjestystä voi enää vapaasti muuutella.

Leikkauksen vaikutukset

Esimerkki 1

Laadin pienen esimerkkiohjelman leikkauksen vaikutusten selventämiseksi. Se koostuu predikaatista foo(X,Y), joka parittaa kokonaislukuja monimutkaisen mutta deterministisen algoritmin mukaan. Samalla luvulla voi olla useita vaihtoehtoisia pareja:
foo(1,2) :- !.

foo(2,3).

foo(3,4).

foo(X,Y) :-
    0 is X mod 2,
    !,
    X =\= 42,
    Y is X + 2.

foo(X,Y) :-
    Alku is X + 10,
    Loppu is X + 20,
    for(Z, Alku, Loppu),
    !,
    A is Z + 3,
    for(Y, Z, A).

foo(2,5).

foo(3,5).

Ensimmäinen '!'-merkki leikkaa onnistuessaan kaikki loput kaavat, joten kysely foo(1,Y) antaa vain vastauksen Y = 2.

Myös toinen '!'-merkki karsii onnistuessaan kaikki sen alapuolella sijaitsevat kaavat, mistä syystä parilliset kakkosta suuremmat X:n arvot tuottavat vain yhden Y:n arvon. Esimerkiksi kysely foo(4,Y) tuottaa vain vastauksen Y = 6. Kysely foo(42,Y) taas tuottaa vastauksen "no".

Kolmas '!'-merkki on esimerkin kannalta mielenkiintoisin. Se leikkaa onnistuessaan paitsi sen alapuolella sijaitsevat kaavat myös loput ensimmäisen for-predikaatin tuottamista vaihtoehdoista. Toisen for-predikaatin tuottamat vaihtoehdot sen sijaan käydään kokonaisuudessaan läpi. Tässä kohtaa on huomattava, että for-predikaatti ei ole silmukka, kuten C:ssä, vaan se sitoo ensimmäisen parametrinsa arvon vuorotellen kokonaislukuarvoihin [toinen parametri ... kolmas parametri]. Tällöin esimerkiksi kysely foo(3,Y), tuottaa vastaukset Y = 4, Y = 13, Y = 14, Y = 15 ja Y = 16.

Esimerkki 2

Kirjoitettaessa useita vaihtoehtoisia kaavoja (clause) samalle predikaatille on syytä muistaa, että Prologtulkki ei tyydy ensimmäiseen onnistuvaan kaavaan, vaan backtracking-algoritmi menee vielä tarkastamaan loputkin. Tämä saattaa joskus unohtua tai '!'-merkki saattaa muuten vain vahingossa jäädä pois, mistä seuraa tämän tyyppisiä ikäviä virheitä:

% luvun parillisuuden tarkastava predikaatti, joka toimii väärin kun 
% hakualgoritmi peruuttaa
even(X,parillinen) :- 
    0 is X mod 2.
even(X,pariton).
Ensin kyselyyn even(2,X) saadaan oikea vastaus, mutta kun kysytään lisää saadaankin vastaukseksi, että 2 on myös pariton. Kun predikaatin kirjoittaja ei odota predikaatin antavan kuin yhden vastauksen, ei tätä tule välttämättä tarkastettua, ja virhe ilmenee vasta myöhemmin, kun sitä käytetään jossakin toisessa predikaatissa. Tämän voi korjata yksinkertaisesti lisäämällä yhden '!'-merkin:

even(X,parillinen) :- 
    0 is X mod 2, !.
even(X,pariton).

tai hitusen tehottomammin lisäämällä jälkimmäiseen kaavaan ensimmäisen kaavan komplementtitapauksen tarkastuksen. Ero on varsin samanlainen kuin C++:n if:n ja else if:n välillä:

even3(X,parillinen) :- 
    0 is X mod 2.
even3(X,pariton) :-
    1 is X mod 2.

Negaatio

Leikkauksen avulla pystytään tekemään eräänlainen negaatio, negation by failure, eli X:n negaatio on totta, mikäli X ei ole pääteltävissä Prologin tietämyskannasta käsin. Negaatio voidaan tehdä leikkauksen avulla tähän tapaan:

 
not(X) :-
    call(X),
    !,
    fail.
not(X).

Not(X) siis onnistuu, aina kun backtracking-algoritmi ei löydä X:lle yhtään ratkaisua. GNUPrologissa on määritelty vastaava järjestelmäpredikaatti "\+".

Tällä tavoin toteutettuun negaatioon liittyy kuitenkin tiettyjä ongelmia - sen nimittäin taataan toimivan ainoastaan predikaateille, jotka eivät sisällä sitomattomia muuttujia. Tämä on järkeenkäypää, koska äärellisen ratkaisujoukon komplementti on ääretön, jos perusjoukko on ääretön. Kyselyille, joille ratkaisujen joukko on ääretön prologtulkin vastaus on tyypillisesti ei. Tästä seuraa, että järjestyksellä, jolla predikaatit sijoitetaan kaavan vartaloon voi olla merkitystä sen kannalta löydetäänkö ratkaisua lainkaan. Esimerkiksi kysely naimaton_opiskelija(X), tuottaa vastauksen ei, mikäli ohjelma on seuraava:

 
naimaton_opiskelija(X) :-
    \+(naimisissa(X)),
    opiskelija(X).

opiskelija(jussi).
naimisissa(matti).

Kysely antaa kuitenkin meille vastaukseksi 'jussi', mikäli muutamme predikaatin naimaton_opiskelija(X) muotoon:


naimaton_opiskelija(X) :-
    opiskelija(X),
    \+(naimisissa(X)).