A Prolog programozási nyelv

Típusok, típuskonstrukciók

A Prolog típustalan nyelv, azonban egy adott paraméter-pozíción értelmes, olyan Prolog kifejezések (amelyekben nem szerepel (behelyettesítetlen) változó) halmazát nevezhetjük típusnak.

A Prologban általában nincs típushiba, csak meghiúsulás, azonban hibajelzést kaphatunk akkor, ha egy beépített eljárást nem megfelelő típusú paraméterrel hívunk. Így a típus implicit módon jelenik csak meg: adatábrázolási döntésünk csak az adatokat felhasználó eljárások alakjában tükröződik.

Tulajdonképpen a Prologban csak két (a hagyományos értelemben vett) elemi típus van, az egész (Integer) és a lebegőpontos (Float). Természetesen - mivel logikai nyelv - implicit módon a logikai típus (Boolean) is "definiált". Ismert továbbá a sztring-típus is. Újabb típusok készítésére az összetett termek (COMPOUND TERM) állnak rendelkezésünkre:

Lista

Csakúgy mint más programozási nyelvekben a Prologban is a listát bizonyos objektumok véges sorozatának ábrázolására használjuk.

[1,eric_cartman,["Hello world",23.45],[],X,]

Érdekesség, hogy a lista elemeinek nem kell azonos típusúnak lenniük (ez persze az eddigiek alapján igazán nem meglepő). Tehát listát szögletes zárójelek között deklarálhatunk, vesszővel elválasztva az elemeit. Ezen felül még hivatkozhatunk egy listára a következőképpen is:

[H|T] [F,S|T]

Az első esetben a listára a fejével és a "maradék rész"-ével hivatkoztunk, a második esetben pedig kikötjük, hogy a listának legyen legalább két eleme. Az üres listára is van egy jelölés, ami többek között egy atom is:

[]

Összhangban az eddigiekkel a listák is tulajdonképpen termek, amelyek speciális szintaxissal bírnak. A [H|T] lista azonos a .(H,T) struktúrával.

Valódi, ill. részleges listák

Vannak valódi, ill. részleges listák. Egy valódi lista lehet üres, vagy nem üres, a nem üres valódi listákat a ’.’/2 függvényszimbólum segítségével építjük fel, kiindulva a [] üres listából. Egy [X|Xs] term pontosan akkor valódi lista, ha Xs valódi lista. Például az [1,2,3] listát a következő alakban írhatjuk fel: .(1,.(2,.(3,[]))) Egy term akkor részleges lista, ha szabad változó, vagy [X|Xs] alakú, ahol Xs részleges lista. Azaz egy term akkor részleges lista, ha nem valódi lista, de megfelelő változóhelyettesítéssel azzá tehető. Tegyük fel például, hogy Xs szabad változó. Ekkor Xs és [1,2|Xs] részleges listák, viszont az [Xs] és [1,2,Xs] valódi listák.

member/2 predikátum
Egy lista elemeit a lista első eleme, és a maradék részben lévő elemek alkotják
% member(X,Xs) :- X eleme az Xs listának member(X,[X|_Xs]). member(X,[_X|Xs]) :- member(X,Xs).
A predikátumhívás előfeltétele, hogy a második paraméter valódi lista legyen, különben a keresési fa végtelen lesz. Valódi listánál azonban a keresési fa végességét garantálja, hogy a rekurzióban a lista hosszának csökkenése. Az itt alkalmazott programozási módszert rekurzív keresésnek nevezzük.
append/3 predikátum
A listaösszefűzés programjánál is két állításunk van. Az egyik arra az esetre vonatkozik, ha a lista üres, ez egy gyakori módszer predikátumok megfogalmazásakor.
% append(Xs,Ys,Zs) :- az Xs és Ys listák összefűzése a Zs lista append([],Ys,Ys). append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).

A második klóz arról az esetről szól, amikor az első lista nem-üres: tekintsük az első lista farkát (Xs) és ezt fűzzük össze rekurzívan a második listával, ennek eredményét jelöljük Zs-es. Ez utóbbi elé helyezve az első lista fejét ([X|Zs]) kapjuk az eredményt.

rev_app/3 predikátum
Ezzel a predikátummal egy lista fordítottját és egy másik listát fűzünk össze.
% rev_app(Xs,Ys,Zs) :- az Xs lista fordítottja és Ys lista összefűzése a Zs rev_app([],Ys,Ys). rev_app([X,Xs],Ys,Zs) :- rev_app(Xs,[X,Ys],Zs).
Ha végiggondoljuk a rekurzió lépéseit, észrevehetjük, hogy az első lista hossza csökken, a második argumentumban lévő lista hossza pedig nő. Ezt az argumentumot nevezzük akkumulátor-argumentumnak, mivel ebben építjük fel az adatszerkezetet alulról fölfelé. A harmadik paraméter az alagút-paraméter, erre az eredmény visszaadásához van szükségünk. A harmadik paraméter a rekurzió végéig változatlan, csak a végén egyesítjük az akkumulátor argumentummal.
reverse/2predikátum
Ez a predikátum az általánosítás módszerére ad példát, azaz a problémát egy általánosabb problémára visszavezetve oldjuk meg.
% reverse(Xs,Ys) :- Az Xs lista fordítottja az Ys reverse(Xs,Ys) :- rev_app(Xs,[],Ys).

Rekord

A rekord-deklaráció formája rekordnév(tag1, tag2, ... tagN). Például egy bináris fát megadhatunk az alábbi formában:

bintree(1, bintree(2, bintree(3, ures, ures), bintree(4, uresm ures)), bintree(5, ures, ures)).

Típusleírások

Általában azt mondják, a Prolog típustalan nyelv. Ennek ellenére az eljárások csak bizonyos adathalmazokon képesek dolgozni, így implicit módon ugyan, de megjelenik a típusfogalom. Ezt érdemes feltüntetni valamilyen formában. Ez egyrészt elősegíti egy Prolog program működésének jobb megértését, másrészt bizonyos Prolog kiterjesztések használnak típusokat, ezért érdemes megismerkedni velük.

Típusleírásnak tömör Prolog kifejezések egy halmazának megadását értjük(egy Prolog kifejezést tömörnek nevezünk, ha nem tartalmaz változót). A típusleírás, nevéhez hűen, egy típust definiál. Alaptípusok leírására használhatjuk az integer, float, number, atom, atomic és any konstansokat. Az első öt típusnév a megfelelő konstanshalmazt jelöli, az any típusnév pedig az összes Prolog kifejezés halmazát. Az alaptípusokból kiindulva definiálhatunk összetett típusokat. Ehhez meg kell adnunk egy struktúranevet, valamint minden argumentumáról meg kell mondanunk, hogy milyen típusú. A struktúranevet és az argumentumok típusait megadó kifejezést kapcsos zárójelbe téve kapunk egy összetett típust leíró kifejezést. Például a {személy(atom,atom,integer)} kifejezés egy típust definiál. Nevezetesen minden olyan Prolog kifejezés, melynek funktora személy/3, első két argumentuma atom és a harmadik egész szám, ilyen típusú. Ezt precízebben és általánosabban úgy írhatjuk le, hogy a { valami(T1, ..., Tn) } halmazkifejezés ekvivalens a { valami(e1, ..., en) | e1 eleme T1, … , en eleme Tn }, n >= 0 kifejezéssel, azaz a halmaz minden olyan valami nevű struktúrát tartalmaz, amelynek argumentumai render T1 , T2 , stb. típusúak.

Egy típust képezhetünk halmazok uniójaként a \/ operator felhasználásával. Például helyes típusdefiníció az alábbi:

{személy(atom,atom,integer) } \/ { atom-atom } \/ atom

Azaz például az alma-alma Prolog kifejezés ilyen típusú, de a személy('Nagy','Béla',24) is.

Azért, hogy hivatkozni tudjunk a típusra el kell neveznünk azt. Ezt az alábbi módon tehetjük meg (Prolog megjegyzésként):

% :- type típusnév = = típusleírás

Lássunk is rögtön két példát! Vegyük észre, hogy a második típust rekurzív módon írtuk fel, a típusleírás hivatkozik ugyanis a típusnévre:

% :- type t1 = = { atom-atom } \/ atom. % :- type ember = = { ember-atom } \/ atom.

Az eddig látott példákban a típusleírásban mindig csak az atom típusnév szerepelt a {} zárójelpáron kívül. Ez nem szükségszerű, tetszőleges típusnév szerepelhet így, olyan is, amelyet mi definiáltunk. Ennek megfelelően az alábbi két (végtelenül egyszerű) példa mindegyike helyes.

% :- type új_típus1 = = ember. % :- type új_típus2 = = { ember }.

A két típus nem egyenlő. Az új_típus1 típus pontosan ugyanazt a halmazt jelöli, mint az ember típus, új_típus2 azonban az egyetlen ember névkonstanst tartalmazó halmazt. (Esetünkben új_típus2 valódi részhalmaza új_típus1-nek.

Egy megkülönböztetett unió csupa különböző funktorú összetett típus uniója. Fontos, hogy nem a struktúranévnek, hanem a funktornak kell különböznie. Azaz nyugodtan lehet két azonos struktúranevű, de különböző argumentumszámú típus. Megkülönböztetett uniót jelölhetünk a szokásos

% :- type T = = { S1 } \/ … \/ { Sn }

helyett így is:

% :- type T ---> S1 ; … ; Sn .

Fontos, hogy a megkülönböztetett unió is típus, csak éppen speciális. Két példa megkülönböztetett unióra:

% :- type ember ---> ember-atom ; semmi. % :- type egészlista ---> [] ; [integer | egészlista]

Paraméteres típusok

Az előzőekben láttuk, hogy hogyan definiálhatunk saját típust. Legutolsó példaként megadtunk egy olyan listát, amely egészeket tartalmaz. Jó lenne, ha megadhatnánk egy lista-mintát is, azaz egy olyan típust, amely tetszőleges (de egyforma) típusú elemek listája lehet. Ugyanígy, bár tudunk definiálni olyan típust, amelyet az atom-atom alakú struktúrák határoznak meg, szükségünk lehet egy olyan típusra, amelyet tetszőleges típusú elemek párjai alkotnak. Erre szolgálnak az ún. Parameters típusok és erre láthatunk példát az alábbiakban.

:- type list(T) ---> [] ; [ T | list(T) ]. % (1) :- type pair( T1 , T2 ) ---> T1 - T2. % (2) :- type assoc_list( KeyT, ValueT ) = = list( pair(KeyT,ValueT). % (3) :- type szótár = = assoc_list( szó, szó ). % (4) :- type szó = = atom. % (5)

(1) T típusú elemekből álló listákat foglal magába, (2) minden olyan '-' nevű kétargumentumú struktúrát, amelynek első argumentuma T1, második T2 típusú. (3) egy olyan típust definiál, amelybe KeyT és ValueT típusú párokból álló listák tartoznak. Végül (4) egy olyan,szótár nevű, típust határoz meg, amelybe ( (5) alapján) atomokból képzett párokból álló listák tartoznak. Ha belegondolunk, ez tényleg felfogható úgy, mint egy szótár.

A típusdeklarációk formális szintaxisa:

típusdeklaráció ::= típuselnevezés | típuskonstrukció
típuselnevezés ::= :- type típusazonosító = = típusleírás
típuskonstrukció ::= :- type típusazonosító ---> megkülönb. unió
megkülönb. unió ::= konstruktor ; …
konstruktor ::= névkonstans | struktúranév( típusleírás, …)
típusleírás ::= típusazonosító | típusváltozó | { konstruktor } | típusleírás \/ típusleírás
típusazonosító ::= típusnév | típusnév( típusváltozó, … )
típusnév ::= névkonstans
típusváltozó ::= változó

Predikátumtípus-deklarációk

Egy predikátumtípus-deklaráció leírja, hogy egy predikátum milyen típusú adatokat képes fogadni, illetve visszaadni az egyes argumentumaiban. Egy ilyen deklaráció általánosan a következőképpen néz ki:

:- pred ( , … )

Lássunk néhány példát az elmondottakra! Az első esetben a member/2 eljárásról jelentjük ki, hogy első argumentuma T típusú, míg a második T típusú elmeket tartalmazó lista. Másodikként az append/3 eljárást írjuk le hasonló módon.

:- pred member( T, list(T) ). :- pred append( list(T), list(T), list(T) ).

Nyilvánvaló, hogy egy predikátumtípus-deklarációban használhatóak ez előzetesen megadott típusleírások. Eljárásokkal kapcsolatban van még egy fontos fogalom, amit predikátummód-deklarációnak hívunk. Egy ilyen deklaráció leírja, hogy az egyes argumentumok kimenő vagy bemenő módban használatosak. Egy eljáráshoz több ilyen móddeklaráció is megadható annak megfelelően, hogy az eljárás milyen különböző módokban képes működni:

:- mode append(in, in, in). % ellenőrzésre :- mode append(in, in, out). % két lista összefűzésére :- mode append(out, out, in). % egy lista szétszedésére

A predikátummód-deklaráció általános felépítése a következő:

:- mode eljárásnév( módazonosító, … )

ahol

módazonosító ::= in | out.

Arra is van lehetőség, hogy egyetlen deklarációba fogjuk össze a típus- és móddeklarációt is, például:

:- pred between(integer::in, integer::in, integer::out).

Ilyen esetben az általános alak:

:- pred eljárásnév( típusazonosító::módazonosító, … )

A SICStus kézikönyv a fentiektől eltérő jelölést használ a bemenő/kimenő argumentumok jelzésére. Az append/3 esetén például:

append (+L1, ?L2, -L3). append (?L1, ?L2, +L3).

Az első jelöli az ellenőrzésre és két lista összefűzésére is alkalmas megvalósítást, míg a második a szétszedésre is használhatót. Ennek megfelelően a +, - és ? jelentése:

+ bemenő argumentum
- kimenő argumentum
? tetszőleges argumentum