Prolog Language
Redeneren over gegevens

Opmerkingen

Herhaling

Prolog heeft geen iteratie, maar alle iteratie kan worden herschreven met behulp van recursie. Recursie verschijnt wanneer een predikaat een doel bevat dat naar zichzelf verwijst. Wanneer u dergelijke predikaten in Prolog schrijft, bestaat een standaard recursief patroon altijd uit ten minste twee delen:

• Basisclausule (niet-recursief) : Meestal vertegenwoordigen de base-case-regel (en) de kleinst mogelijke voorbeelden van het probleem dat u probeert op te lossen - een lijst zonder leden, of slechts één lid, of als u werken met een boomstructuur, het kan een lege boom behandelen, of een boom met slechts één knoop erin, enz. Het beschrijft niet-recursief de basis van het recursieve proces.

• Recursieve (doorlopende) clausule : bevat alle vereiste logica, inclusief een aanroep naar zichzelf, doorlopende recursie.

Als voorbeeld zullen we het bekende predicaat append/3 definiëren. Verklaar bekeken, houdt append(L1,L2,L3) vast wanneer de lijst L3 het resultaat is van de aanhangende lijsten L1 en L2 . Wanneer we proberen de verklarende betekenis van een predicaat te achterhalen, proberen we oplossingen te beschrijven waarvoor het predicaat geldt. De moeilijkheid hier ligt in het proberen om stap voor stap terugkerende details te vermijden en toch rekening te houden met het procedurele gedrag dat het predicaat zou moeten vertonen.

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

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

Het basisscenario verklaart declaratief: "elke L die aan de lege lijst is toegevoegd, is L", merk op dat dit niets zegt over L dat leeg is - of zelfs een lijst is (onthoud, in Prolog komt alles neer op termen):

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

Voor het beschrijven van de recursieve regel, hoewel Prolog regels van links naar rechts uitvoert, laten we het hoofd even weg en kijken we eerst naar het lichaam - de regel lezen van rechts naar links:

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

Nu zeggen we dat als het lichaam vasthoudt: "ervan uitgaande dat append(L1,L2,L3) geldt"

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

Dan doet de kop dat ook: "dan doet append([X|L1],L2,[X|L3]) "

In gewoon Engels betekent dit eenvoudig:

Ervan uitgaande dat L3 de samenvoeging is van L1 en L2, is [X gevolgd door L3] ook de samenvoeging van [X gevolgd door L1] en L2.

In een praktisch voorbeeld:

“Aannemend [1,2,3] is de aaneenschakeling van [1] en [2,3], dan is [a, 1,2,3] ook de aaneenschakeling van [a, 1] en [2,3]. ”

Laten we nu enkele vragen bekijken:

Het is altijd een goed idee om uw predikaat in eerste instantie te testen met de meest algemene query in plaats van het te voorzien van een specifiek scenario-testgeval. Denk eraan: vanwege de unificatie van Prolog zijn we niet verplicht om testgegevens te verstrekken, we geven het gewoon gratis variabelen!

?- 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
...

Laten we de gratis variabele _G1162 achtige notatie vervangen door alfabetische letters om een beter overzicht te krijgen:

?- 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
...

In het eerste antwoord was het basisscenario gematcht en bracht Prolog L1 naar de lege lijst en verenigde L2 en L3 bewees dat L3 de aaneenschakeling is van de lege lijst en L2.

Bij antwoord # 2, door chronologische backtracking, komt de recursieve clausule in het spel en probeert Prolog te bewijzen dat een element in de kop van L1 samengevoegd met L2 L3 met datzelfde element in de lijstkop. Om dit te doen, wordt een nieuwe vrije variabele _A verenigd met het hoofd van L1 en is bewezen dat L3 nu [_A|L2] .

Er wordt een nieuwe recursieve aanroep gedaan, nu met L1 = [_A] . Nogmaals, Prolog probeert te bewijzen dat een element dat in de kop van L1 , samengevoegd met L2 L3 met datzelfde element in zijn kop. Merk op dat _A al het hoofd is van L1 , wat perfect overeenkomt met de regel, dus door recursie plaatst Prolog _A voor een nieuwe vrije variabele en krijgen we L1 = [_A,_B] en L3 = [_A,_B|L2]

We zien duidelijk dat het recursieve patroon zichzelf herhaalt en zien gemakkelijk dat bijvoorbeeld het resultaat van de 100ste stap in recursie eruit zou zien:

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

Opmerking: zoals typisch is voor goede Prolog-code, biedt de recursieve definitie van append/3 ons niet alleen de mogelijkheid om te controleren of een lijst de aaneenschakeling is van twee andere lijsten, het genereert ook alle mogelijke antwoorden die voldoen aan de logische relaties met ofwel volledig of gedeeltelijk geïnstantieerde lijsten.

Toegang tot lijsten

Lid

member/2 heeft handtekeninglid member(?Elem, ?List) en geeft true als Elem lid is van List . Dit predicaat kan worden gebruikt om toegang te krijgen tot variabelen in een lijst, waar verschillende oplossingen worden opgehaald via backtracking.

Voorbeeldvragen:

?- 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]
...

Patroonaanpassing

Wanneer de indices waartoe u toegang moet hebben klein zijn, kan patroonvergelijking een goede oplossing zijn, bijvoorbeeld:

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