Prolog DCG: letztes Element finden

Question

Ich versuche, die Verwendung von DCGs besser zu verstehen. Um dies zu tun, habe ich versucht, einige Übungen im LearnPrologNow-Buch in die DCG-Notation zu übersetzen. Ich versage jedoch kläglich.

Ich habe versucht, ein Programm zu schreiben, das einfach das letzte Element in einer Liste benennt. Das ist alles. Ich kann mir einfach nicht die richtige DCG-Syntax vorstellen. Ich denke, dass ich den 'Basisfall' herausgefunden, die sein sollte:

zuletzt -> [X | []].

Wo X ist das letzte Element. Wie mache ich Prolog die Liste rekursiv? Oder denke ich falsch über DCGs nach?

Answer 1

... --> [] | [_], ... . 

list_last(Xs, X) :- 
    phrase((...,[X]), Xs). 

Dies ist eindeutig die "grafische" Definition. Sie können viele Muster mit ... //0 beschreiben.

Grammatiken sind eine Möglichkeit, eine Sprache zu beschreiben. Ihre Frage, wie man Prolog untergehen lässt, ist falsch. Grammatiken machen nichts. Sie, wenn Sie darauf bestehen, Sätze zu generieren.

Für die verfahrenstechnischen Details müssen Sie die Beendigung verstehen, aber nicht mehr als das.

Edit: Und wenn Sie wirklich kümmern sich um Leistung, dann messen Sie es zuerst. Mit SWI erhalte ich Folgendes. Beachten Sie die Verwendung einer zusätzlichen Bibliothek, um die aufrufenden Gemeinkosten für phrase/2 zu entfernen.

 
?- use_module(library(apply_macros)). 
% library(pairs) compiled into pairs 0.00 sec, 22 clauses 
% library(lists) compiled into lists 0.01 sec, 122 clauses 
% library(occurs) compiled into occurs 0.00 sec, 14 clauses 
% library(apply_macros) compiled into apply_macros 0.01 sec, 168 clauses 
true. 

?- [user]. 
**omitted** 
?- listing. 

dcg_last(B, A) :- 
     last(A, B, []). 

list_last(A, C) :- 
     ...(A, B), 
     B=[C]. 

...(A, B) :- 
     ( A=B 
     ; A=[_|C], 
      ...(C, B) 
     ). 

last(A, [_|B], C) :- 
     last(A, B, C). 
last(A, [A|B], B). 

:- thread_local thread_message_hook/3. 
:- dynamic thread_message_hook/3. 
:- volatile thread_message_hook/3. 

true. 

?- length(L,100000), time(list_last(L,E)). 
% 100,000 inferences, 0.018 CPU in 0.030 seconds (60% CPU, 5482960 Lips) 
L = [_G351, _G354, _G357, _G360, _G363, _G366, _G369, _G372, _G375|...] ; 
% 5 inferences, 0.000 CPU in 0.000 seconds (94% CPU, 294066 Lips) 
false. 

?- length(L,100000), time(dcg_last(L,E)). 
% 100,001 inferences, 0.033 CPU in 0.057 seconds (58% CPU, 3061609 Lips) 
L = [_G19, _G22, _G25, _G28, _G31, _G34, _G37, _G40, _G43|...] ; 
% 2 inferences, 0.011 CPU in 0.023 seconds (49% CPU, 175 Lips) 
false. 

So Durchführung beide sind in etwa die gleiche Anzahl von Schlüssen, aber dcg_last/2 ist langsamer, da sie all die nutzlosen Choice anhäufen muss. list_last/2 erstellt die gleiche Anzahl von Auswahlpunkten, sie werden jedoch fast sofort entfernt. Also haben wir 0,018s vs. 0,033s + 0,011s.

Answer 2

Sie vermissen den rekursiven Schritt und machen die Basisklausel komplexer als nötig.

dcg_last(List, E) :- 
    phrase(last(E), List). 

last(E) --> [_], last(E). 
last(E) --> [E]. 

Letzte // 1 überspringt einfach jedes Element, bis zur letzten. Der Schlüssel ist jedoch, wie phrase/2 die Produktionen übersetzt. phrase(last(E), List) entspricht phrase(last(E), List, []), das heißt, die Grammatik muss alle Eingabe verbrauchen.

Answer 3

Dies ist keine Antwort! CapelliC erklärt es. Es sind nur die Kommentare, die für formatierten Code nutzlos sind, und dieser Kommentar gehört zu seiner Antwort:

Wenn Sie die 'Auflistung' verwenden. Prädikat auf seiner Antwort, nachdem sie Beratung, das ist, was Prolog es, neu geschrieben und ausgeführt wird:

last(A, [_|B], C) :- 
    last(A, B, C). 
last(A, [A|B], B). 

dcg_last(B, A) :- 
    phrase(last(A), B). 

So DCGs auf dem regulären Prolog Ausdrücke nur syntaktischen Zucker ist - eine rekursive Schleife wie erläutert - Sie müssen Gehen Sie durch die Liste ('verbrauchen alle Eingabe'), um das Ende zu erreichen.