Mikä on WikiWiki?
nettipäiväkirja
koko wiki (etsi)
viime muutokset
Mitä kauempana ohjelmointikielen ajattelutaso on siitä, miten ohjelman suoritus varsinaisesti etenee, sitä helpommin siinä kirjoittaa vahingossa tehottomia ohjelmamäärittelyitä. Ohjelma on tehoton, mikäli sen kompleksisuus suhteessa syötteeseen on korkeaa luokkaa. Itse asiassa tämä ei ole mikään ongelma, koska on paljon helpompaa korjata toimiva mutta tehoton ohjelma tehokkaaksi ja toimivaksi ohjelmaksi kuin korjata "tehokas" mutta toimimaton ohjelma sellaiseksi.
Jos tarkastellaan ohjelmointikieliä sen perusteella, kuinka kaukana niiden ajatusmalli on suoritusvuon etenemisestä, Prolog on aika ääripäästä. Yhdessä laiskojen kielten (kuten Haskellin, katso evaluointijärjestykset) kanssa se on yksi monimutkaisimman suoritusvuon kielistä. Näissä kielissä yleensä ohjelmoijan ei ole tarkoituskaan "laskeutua" pohtimaan, miten suoritus etenee, vaan yksinkertaisesti todistamaan, että määrittely tuottaa virheettömän tuloksen. Ohjelmointikielen toteutuksen vaivaksi jää huolehtia, että algoritmin kuvauksesta saadaan muodostetuksi jokin toimintatapa, joka vastaa kuvattua toimintaa.
Prolog kuuluu logiikkaohjelmointikieliin. Jotkin muut logiikkaohjelmointikielet (kuten Mercury) tekevät yksinkertaisesti mahdottomaksi selvittää suoritusjärjestyksen jättämällä sen määrittelemättä. Tällöin jää myös kokonaan toteutuksen harteille muodostaa ohjelmalle tehokas suoritustapa. Prologissa taas suoritusjärjestys vaikuttaa sivuvaikutusten lopputulokseen, joten Prolog-toteutusten pitää taata tietty ohjelmien suoritusjärjestys, vaikka se onkin monimutkainen. Tällöin jää ohjelmoijan ongelmaksi huolehtia siitä, että ohjelmien suoritusjärjestys on järkevä.
Yhteistä logiikkaohjelmointikielille, ja ilmeinen syy algoritmien suuriin kompleksisuuksiin, on indeterminismi. Tämä tarkoittaa, että on helppoa kirjoittaa ohjelmia, jotka etenevät tiettyä suorituspolkua, joka ei johdakaan tulokseen. Tällöin suoritus hyppää takaisin toiseen mahdolliseen suorituspolkuun. Juuri tämä ympäriinsä hyppiminen tekee Prologin suoritusvuosta hankalan ja useimmiten suorastaan hyödyttömän seurata. Jos ohjelma on järjestetty siten, että se generoi paljon umpisuorituspolkuja ennen ratkaisun löytymistä, siitä tulee erittäin tehoton.
Mutta on myös toinen, vähemmän ilmeinen syy Prolog-ohjelmien vahingossa suuriin kompleksisuuksiin. Suuria kompleksisuuksia saa ylipäänsä aikaiseksi moninkertaisilla rekursioilla. Esimerkiksi funktio, joka kutsuu itseään, on yleensä kompleksisuudeltaan O(n). Funktio, joka kutsuu O(n)-funktiota ja itseään, on yleensä kompleksisuudeltaan O(n^2). Nämä funktiot vielä pystyy kuvaamaan (sisäkkäisillä) silmukoilla, ja niinpä polynomiset kompleksisuudet ovat tuttuja myös ei-funktionaalisilla kielillä ohjelmoiville.
Funktio, joka kutsuu itseään kahdesti, on tyypillisesti kompleksisuudeltaan O(2^n) eli eksponentiaalinen. Mutta nämä ovat vain primitiivirekursiivisia funktioita. Funktio, joka tekee toisen tai korkeamman asteen rekursioita, on tyypillisesti kompleksisuudeltaan yli kaikkien tavallisesti matematiikassa käytettyjen funktioiden. (Tämä johtuu siitä, että kaikilla matematiikassa tavallisilla funktioilla on primitiivirekursiivinen määritelmä.) Ackermannin funktio on esimerkki toisen asteen rekursiosta; se kykenee saamaan ällistyttäviä arvoja yksinkertaisesti siitä syystä, että se sisältää kahden rekursiivisen kutsun komposition (ts. yhden palautusarvo annetaan toiselle argumentiksi).
Funktionaalisissa ohjelmointikielissä korkeamman asteen rekursiot on helppoa nähdä syntaktisesti: mikäli rekursiivisen kutsun "sisällä" (ts. argumenttilistassa) on toinen rekursiivinen kutsu, kyse on korkeamman asteen rekursiosta. Logiikkaohjelmointikielissä kuitenkin kompositiot esitetään "littanassa" muodossa, jolloin korkeamman asteen rekursioita voi syntyä vahingossa. Luulisin, että niitä voi jopa esiintyä vain tietyille suoritussuunnille, mutta tästä en ole varma.