Prolog Language
Listy różnic
Szukaj…
Wprowadzenie
Listy różnic w Prologu oznaczają pojęcie znajomości struktury listy do pewnego momentu . Pozostałą część listy można pozostawić niezwiązaną do czasu pełnej oceny predykatu. Lista, której koniec jest nieznany, jest nazywana otwartą listą zakończoną dziurą . Ta technika jest szczególnie przydatna do sprawdzania poprawności złożonych składni lub gramatyk.
Dobrze znane gramatyki określonych klauzul (DCG) używają list różnic do działania pod maską.
Podstawowe użycie
Rozważmy predykat sumDif/2 , zweryfikowany, czy struktura listy odpowiada kilku ograniczeniom. Pierwszy termin reprezentuje listę do analizy, a drugi termin inną listę, która zawiera część pierwszej listy, która jest nieznana naszym ograniczeniom.
Dla celów demonstracyjnych sumDif/2 rozpoznaje wyrażenie arytmetyczne do sumowania n liczb całkowitych.
sumDif([X, +|OpenList], Hole) :-
integer(X),
sumDif(OpenList, Hole).
Wiemy, że pierwszym elementem listy do sprawdzenia poprawności jest liczba całkowita, tutaj zilustrowana przez X , po której następuje symbol dodania ( + ). Pozostała część listy, która musi zostać przetworzona później ( OpenList ), pozostaje nieważna na tym poziomie. Hole reprezentuje tę część listy, której nie musimy weryfikować.
sumDif/2 inną definicję predykatu sumDif/2 aby zakończyć sprawdzanie poprawności wyrażenia arytmetycznego:
sumDif([X|Hole], Hole) :-
integer(X).
Oczekujemy liczby całkowitej o nazwie X bezpośrednio na początku otwartej listy. Co ciekawe, pozostała część listy Hole pozostaje nieznana i to jest cały cel list różnic: struktura listy jest znana do pewnego momentu.
Wreszcie brakujący element pojawia się podczas oceny listy:
?- sumDif([1,+,2,+,3], []).
true
To wtedy, gdy używany jest predykat, wspomniany jest koniec listy, tutaj [] oznacza, że lista nie zawiera dodatkowych elementów.
Oceń wyrażenie arytmetyczne
Zdefiniujmy gramatykę umożliwiającą dodawanie, mnożenie z użyciem nawiasów. Aby dodać więcej wartości do tego przykładu, obliczymy wynik wyrażenia arytmetycznego. Podsumowanie gramatyki:
wyrażenie → czasy
wyrażenie → razy wyrażenie „+”
razy → element
razy → element „*” razy
element → „liczba całkowita”
element → „(„ wyrażenie ”)”
Wszystkie predykaty mają arity 3, ponieważ muszą otworzyć listę, dziurę i wartość wyrażenia arytmetycznego.
expression(Value, OpenList, FinalHole) :-
times(Value, OpenList, FinalHole).
expression(SumValue, OpenList, FinalHole) :-
times(Value1, OpenList, ['+'|Hole1]),
expression(Value2, Hole1, FinalHole),
plus(Value1, Value2, SumValue).
times(Value, OpenList, FinalHole) :-
element(Value, OpenList, FinalHole).
times(TimesValue, OpenList, FinalHole) :-
element(Value1, OpenList, ['*'|Hole1]),
times(Value2, Hole1, FinalHole),
TimesValue is Value1 * Value2.
element(Value, [Value|FinalHole], FinalHole) :-
integer(Value).
element(Value, ['('|OpenList], FinalHole) :-
expression(Value, OpenList, [')'|FinalHole]).
Aby właściwie wyjaśnić zasadę otworów i sposób obliczania wartości, weźmy expression drugiego zdania:
expression(SumValue, OpenList, FinalHole) :-
times(Value1, OpenList, ['+'|Hole1]),
expression(Value2, Hole1, FinalHole),
plus(Value1, Value2, SumValue).
Otwarta lista jest oznaczona predykatem OpenList . Pierwszym elementem do walidacji jest to, co występuje przed symbolem dodawania ( + ) . Po sprawdzeniu pierwszego elementu następuje bezpośrednio po nim symbol dodania i kontynuacja listy o nazwie Hole1 . Wiemy, że Hole1 jest kolejnym elementem do sprawdzenia poprawności i może być innym expression , dlatego Hole1 jest wówczas terminem nadanym dla expression predykatu.
Wartość jest zawsze reprezentowana w pierwszym terminie. W tej klauzuli jest on zdefiniowany przez sumę Value1 (wszystko przed symbolem dodawania) i Value2 (wszystko po symbolu dodawania).
Wreszcie wyrażenie może zostać ocenione.
?- expression(V, [1,+,3,*,'(',5,+,5,')'], []).
V = 31