Welche allgemeinen Tipps haben Sie zum Golfen in Prolog? Ich bin auf der Suche nach Ideen, die allgemein auf Code-Golf-Probleme angewendet werden können, die zumindest etwas spezifisch für Prolog sind (z. B. sind Ein-Buchstaben-Variablen nicht spezifisch für Prolog, um die Größe von Programmen zu reduzieren).

Bitte geben Sie in Ihren Tipps an, ob es sich um eine spezifische Implementierung von Prolog handelt (z. B. SWI-Prolog-spezifische integrierte Funktionen).

Bitte posten Sie nur einen Tipp pro Antwort oder eine Liste von Tipps, die eng mit derselben Hauptidee zusammenhängen.

Verwenden Sie Operatoren für Prädikatnamen

Es ist möglich, Prädikatenoperatoren als Namen zu vergeben, solange der Operator einer der vordefinierten Operatoren ( hier aufgelistet ) ist und nicht bereits als Prädikat definiert ist. Dies spart sowohl beim Definieren als auch beim Aufrufen des Prädikats einige Bytes, da Operator-Prädikate nicht in der normalen name(arg1,arg2,etc..)Form geschrieben werden müssen und aufgerufen werden können, wie es bei Operatoren zu erwarten ist.

Für Prädikate mit einem oder zwei Argumenten können sie die Namen von unären bzw. binären Operatoren enthalten. Bei Prädikaten mit höherer Arität können Klammern bei der Mustererkennung immer noch vermieden werden. Wenn wir beispielsweise ein Prädikat haben A+B+C:-..., wandelt Prolog es anhand seiner Operatorprioritäts- und Assoziativitätsregeln in (A+B)+C:-...ein Operatorprädikat um, mit dem das erste Argument einem Muster entspricht A+B. Oder A-B+C*D:-...das wird (A-B)+(C*D)so, dass sein erstes Argument mit dem Muster A-Bund sein zweites mit dem Muster übereinstimmt C*D.

Beispiele

_+_+_.
A-B+C*D:-between(A,B,C),C+D.
\X:-X>1,X<10.
X+Y:-length(Y,X),member(X,Y).



5+[10,5,3,2,5],a+b+c,0-20+X*[2,4,6,5,40],\9.

Die Ausgabe wird sein X = 5.

Probieren Sie es online!

Logische Folge

Da DCGs syntaktischer Zucker für Prädikate sind, können ihnen auch Operatoren für Namen gegeben werden. Dies funktioniert wie erwartet, wenn Sie sie als DCGs entweder aus einer DCG aufrufen oder die phrasePrädikate oder andere Prädikate verwenden, die für die Arbeit mit DCGs entwickelt wurden. Wenn Sie sie als Prädikate aufrufen, sind Klammern erforderlich (z. B. A+B-->...müssen sie wie +(A,B,...)folgt aufgerufen werden ), da DCG-Prädikate zwei zusätzliche Argumente für ihre Differenzlisten verwenden. Bei DCGs mit Operatornamen und mehr als zwei Argumenten mit Operatormusterabgleich ist es wichtig, beim Aufrufen als Prädikat sicherzustellen, dass die mit dem Muster übereinstimmenden Operatoren korrekt verteilt sind.

Die Angabe von Bedienernamen für DCGs, für die keine zusätzlichen Argumente erforderlich sind, kann nützlich sein, wenn Sie sie in Ihrem Programm aufrufen müssen, da Sie dies dann ohne Klammern tun können. Vorsicht ist geboten, da das, was Sie in Klammern speichern, durch zusätzlichen Abstand zum Parsen benachbarter Operatoren verloren gehen kann.

Beispiele

/ -->a+b+X,X+d+e.
A+B+C-->[A],[B],[C].


X/[],member(c,X),phrase(f+o+o,Y),+(b+a,r,Z,[]).

Ausgabe wird sein

X = [a, b, c, c, d, e],
Y = [f, o, o],
Z = [b, a, r].

Probieren Sie es online!

Vorbehalte

Mit den unären Operatoren +und -interpretiert Prolog +20oder -20als Zahlen anstelle eines Aufrufs an ein +/1oder ein -/1Prädikat. Prädikate, die unär +oder -als Namen angegeben wurden, können weiterhin in Klammern ( +(20), -(20)) an der Nummer aufgerufen werden . Wenn zu vermeiden , ist das zusätzliche Bytes von Klammern wünschenswert , andere einstellige Operatoren wie \, $usw. kann stattdessen als Name verwendet werden.

Die Kombination aus Pattern Matching und Operator-Prädikaten ist nicht ganz fehlerfrei. Wenn Sie zwei Prädikate haben, die denselben Operator wie ihr Name haben und bei denen eines streng allgemeiner ist als das andere, wird möglicherweise das allgemeinere zuerst aufgerufen, oder das weniger allgemeine schlägt fehl (abhängig von der Reihenfolge in der Quelle). . Wenn beispielsweise im obigen Beispiel A-B+C*Ddie Eingabe nicht übereinstimmt, ruft Prolog auf X+Y. Dies führt zu einem Fehler, da length/2erforderlich ist Y, dass es sich um eine Ganzzahl handelt, was nicht der Fall ist, da sie in der Form vorliegt C*D. Dies kann einfach vermieden werden, indem sichergestellt wird, dass keine zwei Prädikate den gleichen Operator wie ihr Name haben, oder wenn dies fehlschlägt, werden Schnitte und eine sorgfältige Anordnung der Quelle verwendet.

Versuchen Sie, jeden möglichen Fall in eine einzige Regel zu fassen

Die saubere Art, in Prolog zu programmieren, besteht darin, mehrere Regeln für dasselbe Prädikat zu deklarieren. Ein Prädikat zum Umkehren einer Liste mit einem Akkumulator sieht beispielsweise folgendermaßen aus:

r([],Z,Z).
r([H|T],Z,R):-r(T,[H|Z],R).

In Code-Golf können wir die erste Regel entfernen und ;am Ende der zweiten Regel eine hinzufügen, um das Rekursionsende zu codieren:

r([H|T],Z,R):-r(T,[H|Z],R);R=[H|Z].

Wir wissen, dass die erste Bedingung r(T,[H|Z],R)fehlschlägt, wenn T leer ist, dh wenn die Rekursion enden muss, und daher können wir unsere Kündigung als eine oder-Klausel danach hinzufügen.

Das gleiche Prinzip funktioniert in vielen Situationen. Beachten Sie jedoch, dass es manchmal tatsächlich kürzer ist, eine andere Regel zu deklarieren, als dies zu tun.

Ein Trick, der häufig nützlich ist: Verwenden Sie CLP (FD) -Beschränkungen für Ganzzahlarithmetik, um Prädikate zu erhalten, die automatisch in mehrere Richtungen verwendet werden können, wodurch Bedingungen und dedizierte Verzweigungen und Varianten vermieden werden.

Verwenden Sie B-Prolog oder GNU Prolog, wenn solche Einschränkungen sofort verfügbar sind, ohne dass Bibliotheken geladen werden müssen.

Verwenden Sie arithmetische Operatoren als Tupelkonstruktoren und Konsolenpaare

Wenn Sie eine einzelne Struktur übergeben müssen, die aus zwei oder mehr Werten besteht, sollten Sie am besten eine Liste verwenden, z [A,B]. Das ist allerdings sehr ausführlich.

Es gibt eine Alternative. Prolog-Werte können eine ziemlich willkürliche verschachtelte Struktur speichern, die nicht ausgewertet wird. Hier ist ein Beispiel, wie das funktioniert:

| ?- member(member(A,B),C).
C = [member(A,B)|_] ? ;
C = [_,member(A,B)|_] ? ;
(etc.)

member(A,B)ist in dieser Situation nur ein benanntes Tupel, und das Äußere member(das ein Funktionsaufruf ist) behandelt es als solches.

Auch wenn benannte Tupel in der Programmierung mit Prolog ohne Golfspiel ziemlich nützlich sind, scheinen sie möglicherweise noch ausführlicher zu sein als der Listenansatz. Wir können jedoch im Namen des Tupelkonstruktors ziemlich beliebige Zeichen verwenden (vorausgesetzt, sie werden korrekt in Anführungszeichen gesetzt). Anstelle von so etwas Süßem memberoder einem einzelnen Charakter akönnen wir so etwas machen:

| ?- A = '-'('/'(1,2), '/'(3,4)).
A = 1/2-3/4

Hier sind '-'und unsere Tupelkonstrukteure '/'. Und es ist interessant zu sehen, was der hübsche Drucker mit ihnen gemacht hat. Für die Tupel wird die Infixnotation verwendet. Dies ist wirklich knapp und analysiert auf die gleiche Weise wie die vergleichbare arithmetische Operation. (Dies erklärt auch, warum Arithmetik isnicht verwendet wird =; A = 1+2würde sich Amit dem Tupel vereinigen '+'(1,2) , so dass eine separate Syntax erforderlich ist, um den nicht bewerteten arithmetischen Ausdruck tatsächlich auszuwerten.) Da ein Tupelkonstruktor etwas aufgerufen werden muss , können Sie auch ein Zeichen verwenden, das eine Knappheit aufweist Syntax (und als Bonus -und/Dies sind auch einige der am häufigsten verwendeten Optionen in nicht-golfenem Code, wenn ein schneller Tupelkonstruktor anstelle eines aussagekräftigen Konstruktors verwendet werden soll, ähnlich wie dies ihäufig als Schleifenvariable verwendet wird Eingabe und Ausgabe, wenn Sie aus irgendeinem Grund ein Tupel dort haben wollen).

'-'und '/'sind eine gute Wahl für Tupelkonstruktoren, da sie einen guten und nützlichen Vorrang haben und es Ihnen ermöglichen, Tupel-Literale kurz zu schreiben. Beachten Sie jedoch, dass Sie sich keine Gedanken über die Priorität machen müssen, wenn im Programm Zwischenwerte erstellt werden. Prolog speichert die Tupel nicht als Quellcode, sondern als Baum. Hübsche Drucker können sie eindeutig ausgeben:

| ?- A = '-'('-'(1,2), '-'(3,4)).
A = 1-2-(3-4)

Da die Tupelsyntax so kurz f(A,B)ist ( nicht kürzer als f(A-B)), können Sie mehrere Prädikatsargumente kostenlos durch Tupel ersetzen. Wenn also ein Prädikat zwei oder mehr seiner Argumente an ein anderes Prädikat übergeben muss, können Sie sie häufig in Form bringen ein Tupel und übergeben Sie einfach das Tupel (obwohl dies erfordert, dass alle Aufrufe des Prädikats zusätzlich zum Prädikat selbst geändert werden, um eine geeignete Mischung aus Tupelkonstruktoren und Kommas zu verwenden).

Ein weiterer Vorteil dieser Syntax besteht darin, dass Sie Listen intern verwenden müssen (anstatt mit Standardprädikaten zusammenzuarbeiten). Eine Liste besteht im Grunde genommen nur aus verschachtelten Konsolenzellen, und eine Konsolenzelle ist nur ein Tupel mit Konstruktor '.', wie hier zu sehen ist:

| ?- Q = '.'('.'(A,B),'.'(C,D)).
Q = [[A|B],C|D]

Wenn Ihr Code Listen "manuell" verwendet, kann es sehr sinnvoll sein, einen weniger umfangreichen Tupelkonstruktor als zu verwenden '.'. Eine häufige Wahl für mich ist die Darstellung einer Nachteile-Zelle als '/'(Tail,Head)(da es sich um die am besten lesbare handelt, die Sie in der Debug-Ausgabe erhalten können, ohne Zeichen zu verschwenden). Beachten Sie, dass Sie wahrscheinlich auch Ihr eigenes []Äquivalent haben möchten . Sie könnten es verwenden, []aber es ist zwei Bytes lang und es gibt viele Ein-Byte-Atome (alle Kleinbuchstaben), die Sie stattdessen verwenden können.

So zum Beispiel die folgende Liste:

[1,2,3]

könnte in eine manuelle Darstellung mit der gleichen Anzahl von Zeichen wie folgt umgewandelt werden:

x/3/2/1

[H|T]Dies bringt den Vorteil mit sich, dass Übereinstimmungen im Stil von Mustern jetzt enger T/Hund ein Test mit der leeren Liste xeher als mit der längeren Liste geschrieben werden können []. (Natürlich kommt dies mit dem offensichtlichen Nachteil , dass member, appendusw., wird nicht auf dieser Darstellung arbeiten.)

Kürzere Syntax für Listen mit Listen und eine Möglichkeit zum Deklarieren von Karten

Sie können Bytes in Listen von Listen speichern. Wenn Sie eine Liste haben [[1,2],[3,4]], können Sie sie tatsächlich als deklarieren [1:2,3:4], wodurch 4 Klammern = 4 Bytes gespeichert werden. Beachten Sie, dass Sie etwas anderes als :(zum Beispiel ^) verwenden können.

1:2ist in diesem Fall eigentlich keine Liste (während [1,2]war), sondern wird intern als dargestellt :(1,2). Daher können Sie keine Prädikate verwenden, die auf Listen in Unterlisten mit Doppelpunkten funktionieren.

Dieser Trick wird hauptsächlich zum Deklarieren von Maps verwendet, dh einer Liste von Schlüsseln, an die Werte angehängt sind. Wenn Sie beispielsweise eine Karte deklarieren möchten M, die die Schreibweise einer Ziffer in Englisch und Französisch enthält, können Sie Folgendes tun:

M=[0:'Zero':'Zéro',1:'One':'Un',2:'Two':'Deux', ... ]

Sie können dann beispielsweise Elemente der Karte mit einem eingebauten Prädikat wie z. B. abrufen member/2. Zum Beispiel, wenn Sie die Ziffer und englisches Wort entsprechend wollen 'Quatre'in M, könnten Sie tun:

member(Digit:Name:'Quatre',M).

Ein guter Trick: Wenn Sie einen Fehler machen müssen , verwenden Sie etwas, das  false / 0 entspricht , aber kürzer ist, wie zum Beispiel:

? - wiederhole, schreibe (hi), 0 = 1 .

Verwenden Sie ein Prädikat mit verschiedenen Aufrufmodi erneut

Sie können beispielsweise eine Struktur mit demselben Prädikat analysieren und drucken, einmal mit einem variablen Argument und ein anderes Mal mit einem Grundbegriff. Ich habe diesen Ansatz in Make the Stretchy Snakes Kiss verwendet . Dies ist natürlich nicht bei allen Herausforderungen möglich.