Prolog Language
Resonemang om data

Anmärkningar

Rekursion

Prolog har inte iteration, men all iteration kan skrivas om med rekursion. Rekursion visas när ett predikat innehåller ett mål som hänvisar till sig själv. När man skriver sådana predikat i Prolog, har ett standardrekursivt mönster alltid minst två delar:

• Bas- (icke-rekursiv) klausul : Normalt representerar basfallsregeln (erna) de minsta möjliga exemplen på problemet som du försöker lösa - en lista utan medlemmar, eller bara en medlem, eller om du arbetar med en trädstruktur, kan det handla om ett tomt träd eller ett träd med bara en nod i det, etc. Det beskriver icke-rekursivt basen i den rekursiva processen.

• Rekursiv (fortlöpande) klausul : Innehåller all nödvändig logik inklusive ett samtal till sig själv, fortsatt rekursion.

Som ett exempel kommer vi att definiera den välkända predikatbilagan append/3 . På ett deklarativt sätt håller append(L1,L2,L3) när listan L3 är resultatet av bifogade listor L1 och L2 . När vi försöker ta reda på den deklarativa betydelsen av ett predikat försöker vi beskriva lösningar som predikatet innehåller. Svårigheten här ligger i att försöka undvika alla stegvisa återkommande detaljer och samtidigt tänka på det processuella beteende som predikatet bör visa.

% Base case
append([],L,L).

% Recursive clause
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

I basfallet anges deklarativt "alla L som är bifogade till den tomma listan är L". Observera att detta inte säger något om att L är tom - eller till och med att vara en lista (kom ihåg, i Prolog bjuder allt på termer):

?- append(X,some_term(a,b),Z).
X = [],
Z = some_term(a, b).

För att beskriva den rekursiva regeln, även om Prolog utför regler från vänster till höger, utelämnar vi huvudet en sekund och tittar på kroppen först - läser regeln från höger till vänster:

    append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

Nu säger vi att om kroppen håller: "förutsatt att append(L1,L2,L3) gäller"

    append([X|L1],L2,[X|L3]) :-  append(L1,L2,L3). 

Då gör det också huvudet: "då gör det också append([X|L1],L2,[X|L3]) "

På vanlig engelska översätter detta helt enkelt till:

Antagande att L3 är sammankopplingen av L1 och L2, då är [X följt av L3] också sammankopplingen av [X följt av L1] och L2.

I ett praktiskt exempel:

”Förutsatt att [1,2,3] är sammankopplingen av [1] och [2,3], då [a, 1,2,3] är också sammankopplingen av [a, 1] och [2,3]. ”

Låt oss nu titta på några frågor:

Det är alltid en bra idé att först testa ditt predikat med den mest allmänna frågan snarare än att förse den med ett specifikt scenariotestfall. Tänk på det: på grund av Prologs förening behöver vi inte tillhandahålla testdata, vi ger oss bara gratisvariabler!

?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;                                   % Answer #1
L1 = [_G1162],
L3 = [_G1162|L2] ;                          % Answer #2
L1 = [_G1162, _G1168],
L3 = [_G1162, _G1168|L2] ;                  % Answer #3
L1 = [_G1162, _G1168, _G1174],
L3 = [_G1162, _G1168, _G1174|L2] ;          % Answer #4
...

Låt oss ersätta den fria variabeln _G1162 liknande notation med alfabetiska bokstäver för att få en bättre översikt:

?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;                                   % Answer #1
L1 = [_A],
L3 = [_A|L2] ;                              % Answer #2
L1 = [_A, _B],
L3 = [_A, _B|L2] ;                          % Answer #3
L1 = [_A, _B, _C],
L3 = [_A, _B, _C|L2] ;                      % Answer #4
...

I det första svaret matchades basfallet och Prolog instanserade L1 till den tomma listan och förenade L2 och L3 bevisade att L3 är sammanlänkning av den tomma listan och L2.

Vid svar nr 2, genom kronologisk backspårning, kommer den rekursiva klausulen in och Prolog försöker bevisa att något element i huvudet på L1 sammankopplat med L2 är L3 med samma element i listhuvudet. För att göra det förenas en ny gratisvariabel _A med huvudet på L1 och L3 har nu visat sig vara [_A|L2] .

Ett nytt rekursivt samtal ringer, nu med L1 = [_A] . Återigen försöker Prolog att bevisa att något element som är placerat i huvudet på L1 , sammankopplat med L2 är L3 med samma element i huvudet. Lägg märke till att _A redan är chef för L1 , som perfekt matchar regeln, så nu, genom rekursion, sätter Prolog _A framför en ny gratisvariabel och vi får L1 = [_A,_B] och L3 = [_A,_B|L2]

Vi ser tydligt att det rekursiva mönstret upprepar sig och kan lätt se att till exempel resultatet av det 100: e steget i rekursionen skulle se ut:

L1 = [X1,X2,..,X99],
L3 = [X1,X2,..,X99|L2]

Obs: som är typiskt för bra Prolog-kod, ger den rekursiva definitionen av append/3 oss inte bara möjligheten att verifiera om en lista är sammanlänkningen av två andra listor, den genererar också alla möjliga svar som uppfyller de logiska relationerna med endera helt eller delvis instanserade listor.

Åtkomst till listor

Medlem

member/2 har signaturmedlem member(?Elem, ?List) och betecknar true om Elem är medlem i List . Detta predikat kan användas för att komma åt variabler i en lista, där olika lösningar hämtas genom backtracking.

Exempelfrågor:

?- member(X, [1,2,3]).
X = 1 ;
X = 2 ;
X = 3.

?- member(X,[Y]).
X = Y.

?- member(X,Y).
Y = [X|_G969] ;
Y = [_G968, X|_G972] ;
Y = [_G968, _G971, X|_G975] ;
Y = [_G968, _G971, _G974, X|_G978]
...

Mönstermatchning

När de index du behöver för att få tillgång till är små, kan mönstermatchning vara en bra lösning, t.ex.

third([_,_,X|_], X).
fourth([_,_,_,X|_], X).