Umsetzung der "Letzte" in Prolog

Ich versuche, ein Gefühl für die Prolog-Programmierung durch Ulle Endriss' lecture notes. Wenn meine Lösung zu einer übung verhält sich nicht wie erwartet, ich finde es schwer, eine gute Erklärung. Ich denke, das hat zu tun mit meinem wackeligen verstehen, wie Prolog-Ausdrücke ausgewertet werden.

Übung 2.6 auf Seite 20 Anrufe für eine rekursive Implementierung eines Prädikats last1 verhält sich wie die built-in-Prädikat last. Mein Versuch lautet wie folgt:

last1([_ | Rest], Last) :- last1(Rest, Last).
last1([Last], Last).

Gibt es die richtige Antwort, aber für Listen mit mehr als einem element, die ich habe, um das Semikolon, um die Abfrage zu beenden. Dies macht last1 unterscheidet sich von der integrierten last.

?- last1([1], Last).
Last = 1.

?- last1([1, 2], Last).
Last = 2 ;
false.

Wenn ich schalten Sie die Reihenfolge, in der ich erklärte, die Regel und die Tatsache, dann Brauch ich den Schlüssel in die Semikolon in beiden Fällen.

Ich glaube, ich weiß, warum Prolog denkt, dass last1 vielleicht noch eine weitere Lösung (also das Semikolon). Ich vorstellen, es folgt die Reihenfolge für die Evaluierung

last1([1, 2], Last).
==>  last1([2], Last).
==>  last1([], Last).    OR    Last = 2.
==>  false    OR    Last = 2.

Scheint zu zeigen, dass ich Aussehen sollte für ein Weg, um zu vermeiden matching Rest mit []. Egal, ich habe keine Erklärung, warum die Umschaltung der Reihenfolge der Deklaration hätte irgendeinen Effekt.

Frage 1: Was ist die richtige Erklärung für das Verhalten der last1?

Frage 2: Wie kann ich implementieren Sie ein Prädikat last1 die nicht von der integrierten last?

InformationsquelleAutor Michael Wijaya | 2012-07-31

13

Frage 1:

Prolog-Systeme sind nicht immer in der Lage zu entscheiden, ob oder nicht eine Klausel gelten, die vor der Ausführung. Die genauen Umstände sind implementierungsabhängig. Das heißt, Sie kann sich nicht darauf berufen, dass die Entscheidung im Allgemeinen. Systeme verbessern, hier von release zu release. Betrachten als einfachsten Fall:
```
?- X = 1 ; 1 = 2. 
X = 1 ; 
falsch. 
```
Sehr clever Prolog erkennen könnte, dass 1 = 2 schlägt immer fehl, und so ganz einfach zu beantworten X = 1. statt. Auf der anderen Seite, ist diese "cleverness" ist sehr aufwändig zu implementieren und die Zeit ist besser ausgegeben für die Optimierung der häufigeren Fällen.

Also, warum Prologe zeigen dies überhaupt? Der Hauptgrund ist, zu vermeiden, bittet kleinlaut für eine andere Antwort, wenn der Prolog schon weiß, dass es keine weitere Antwort. Also, bevor Sie zu dieser Verbesserung haben, wurden Sie aufgefordert, eine andere Antwort für alle Anfragen mit Variablen und habe die false oder "Nein" auf jeder Abfrage genau eine Antwort. Dass dies so umständlich, dass viele Programmierer nie gebeten, für die nächste Antwort, und so wurden nicht gewarnt, um unbeabsichtigte Antworten.

Und der sekundäre Grund ist zu halten Sie bewusst die Grenzen der Umsetzung: Wenn der Prolog verlangt nach einer anderen Antwort auf diese Allgemeine Abfrage, dies bedeutet, dass es verwendet immer noch einige Raum, die sich ansammeln könnte, und Essen, bis alle Ihre computing-Ressourcen.

In deinem Beispiel mit last1/2 Sie Begegnung solchen Fall. Und Sie haben bereits etwas sehr, sehr smart, BTW: Sie versucht, das zu minimieren ist die Abfrage zu sehen, das erste auftreten des unerwarteten Verhalten.

In deinem Beispiel-Abfrage last1([1,2],X) das Prolog-system nicht Blick auf die gesamte Liste [1,2] aber sieht nur der AUFTRAGGEBER Funktor. Also für das Prolog-system die Abfrage sieht genauso aus, wie last1([_|_],X) wenn es entscheidet, welche Klauseln anwenden. Dieses Ziel passt jetzt auf beiden Klauseln, und dies ist der Grund, warum der Prolog erinnert sich an die zweite Klausel als alternative ausprobieren.

Aber denken Sie daran: Diese Wahl ist nun möglich, für alle - Elemente, aber das Letzte!!! Das bedeutet, dass Sie zahlen einige Speicher für jedes element! Sie können tatsächlich beobachten, diese durch eine sehr lange Liste. Diese bekomme ich auf meinem kleinen 32-bit-laptop, müssen Sie möglicherweise eine andere null-oder zwei-auf einem größeren system:
```
?- Länge(L,10000000), last1(L,E). 
ERROR: Out of local stack 
```
Auf der anderen Seite, die vordefinierte last/2 reibungslos funktioniert:
```
?- Länge(L,10000000), letztes(L,E). 
L = [_G343, _G346, _G349, _G352, _G355, _G358, _G361, _G364, _G367|...]. 
```
In der Tat, es verwendet Konstante Raum!

Gibt es nun zwei Möglichkeiten, aus dieser:
1. Versuchen, zu optimieren Ihrer definition. Ja, Sie können dies tun, aber Sie müssen sehr schlau zu sein! Die definition von @back_dragon zum Beispiel ist falsch. Es passiert oft, dass Anfänger versuchen Sie zu optimieren, wenn ein Programm in der Tat sind Sie die Zerstörung Ihrer Semantik.
2. Fragen Sie sich, ob Sie tatsächlich der Definition das gleiche Prädikat wie last/2. In der Tat, sind Sie nicht.
Frage 2:

Betrachten:
```
?- last(Xs, X). 
Xs = [X] ; 
Xs = [_G299, X] ; 
Xs = [_G299, _G302, X] ; 
Xs = [_G299, _G302, _G305, X] ; 
Xs = [_G299, _G302, _G305, _G308, X] 
... 
```
und
```
?- last1(Xs, X). 
** Schleifen ** 
```
Also Ihre definition unterscheidet sich in diesem Fall mit SWI-definition. Exchange die Reihenfolge der Klauseln ist.
```
?- Länge(L,10000000), last2(L,E). 
L = [_G343, _G346, _G349, _G352, _G355, _G358, _G361, _G364, _G367|...] ; 
falsch. 
```
Wieder, dieser false! Aber dieses mal, die große Liste funktioniert. Und diese Zeit, die minimal-Abfrage:
```
?- last2([1],E). 
E = 1 ; 
falsch. 
```
Ist, und die situation ist ganz ähnlich: auch in Prolog betrachten Sie die Abfrage in der gleichen Weise wie last2([_|_],E) und schlussfolgern, dass beide Klauseln gelten. Zumindest haben wir nun Konstanten Aufwand anstelle von linearen Aufwand.

Gibt es mehrere Möglichkeiten, um zu überwinden, dass dieser Aufwand in einem sauberen Mode - aber Sie alle hängen stark ab von den Innereien auf eine Umsetzung.
- Die Umsetzung der last ist sicherlich schwieriger, als ich dachte. Ich nahm die Notizen für einen Vortrag vor allem, weil es ist eine kurze Einführung in Prolog, aber jetzt denke ich, dass Die Kunst des Prolog vielleicht die bessere Wahl gewesen. Letztere hat eine bessere Erklärung für das Ausführungsmodell von Prolog.
- Die meisten Prolog-Programmierer würde gerne mit last2/2 schon.
InformationsquelleAutor false
5

SWI-Prolog versucht zu vermeiden, dass weitere Lösungen, wenn es feststellen kann, dass es keine gibt. Ich denke, dass der Dolmetscher untersuchen Sie den Speicher suchen für einige choice point Links, und wenn Sie nicht finden können jedem, einfach die Kündigung. Ansonsten wartet Sie, dass sich die Benutzer Wahl zu bewegen.

Ich würde versuchen, last1 deterministisch auf diese Weise:
```
last1([_,H|Rest], Last) :- !, last1([H|Rest], Last).
last1([Last], Last).
```
aber ich glaube nicht, dass es indistinguishable aus Letzte. Lauern auf den Quellcode der Bibliothek (es ist einfach so ?- edit(last).)
```
%%  last(?List, ?Last)
%
%   Succeeds when Last  is  the  last   element  of  List.  This
%   predicate is =semidet= if List is a  list and =multi= if List is
%   a partial list.
%
%   @compat There is no de-facto standard for the argument order of
%       last/2.  Be careful when porting code or use
%       append(_, [Last], List) as a portable alternative.

last([X|Xs], Last) :-
    last_(Xs, X, Last).

last_([], Last, Last).
last_([X|Xs], _, Last) :-
    last_(Xs, X, Last).
```
können wir schätzen eine gut durchdachte Umsetzung.
- last1(Xs,X) nicht zu einer Antwort
- Ich wusste nicht, über edit. Es wird definitiv in handliches kommen.
- Was ist der Zweck der Liste operator-splitting-Auftritt auf der rechts-hand-Seite in deinem Beispiel ? Meine version wurde nicht wie: last1([_,T], Last) :- !, last1(T, Last). last1([Nachname], Last). Aber wenn ich ersetzen T mit H|Rest, wie Sie tun, es funktioniert.. Warum ?
- Last) entspricht nur eine Liste mit 2 Elementen. Statt der pipe-operator leitet die Rute, D. H. eine Liste, damit kann beliebige Anzahl der Elemente oder leer.
InformationsquelleAutor CapelliC
0

dieser code funktionieren würde:
```
last1([Last], Last).
last1([_ | Rest], Last) :- last1(Rest, Last), !.
```
es ist, weil prolog-Dinge, es könnte sein, mehr Kombinationen, aber mit diesem symbol: !, prolog gewonnen T go back nach erreichen dieses Punktes
- last1(L,N), L = [_,_,_]. erfolgreich sein sollte, aber deine version schlägt.
InformationsquelleAutor Daniel Roca Lopez

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.