Conseils pour jouer au golf à Prolog

16

Quels conseils avez-vous pour jouer au golf à Prolog? Je recherche des idées qui peuvent être appliquées aux problèmes de golf de code en général qui sont au moins quelque peu spécifiques à Prolog (par exemple, les variables à une lettre ne sont pas spécifiques à Prolog pour réduire la taille des programmes).

Veuillez indiquer dans vos conseils si elle est spécifique à une implémentation de Prolog (par exemple, des modules intégrés spécifiques à SWI-Prolog)

Veuillez ne publier qu'un seul conseil par réponse, ou une liste de conseils qui sont tous étroitement liés à la même idée principale.

Fatalize
la source
1
La prologbalise est un peu inutile. À moins que nous ayons un défi Interpréter Prolog, nous n'en avons pas besoin.
cat

Réponses:

10

Utiliser des opérateurs pour les noms de prédicat

Il est possible de donner aux opérateurs de prédicats des noms tant que l'opérateur est l'un des opérateurs prédéfinis (répertoriés ici ) et n'est pas déjà défini comme prédicat. Cela permet d'économiser quelques octets lors de la définition et de l'appel du prédicat, car les prédicats d'opérateur n'ont pas besoin d'être écrits sous la name(arg1,arg2,etc..)forme normale et peuvent être appelés comme on pourrait s'y attendre avec les opérateurs.

Pour les prédicats à un et deux arguments, ils peuvent respectivement donner les noms des opérateurs unaires et binaires. Pour les prédicats d'arité supérieure, nous pouvons toujours éviter les parenthèses en utilisant la correspondance de motifs. Par exemple, si nous avons un prédicat A+B+C:-..., Prolog utilisera ses règles de priorité d'opérateur et d'associativité pour le transformer en (A+B)+C:-...un prédicat d'opérateur auquel le premier argument correspondra à un modèle A+B. Ou A-B+C*D:-...qui devient (A-B)+(C*D)ainsi son premier argument est mis en correspondance avec le motif A-Bet son second argument est mis en correspondance avec C*D.

Exemples

_+_+_.
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.

La sortie sera X = 5.

Essayez-le en ligne!

Corollaire

Étant donné que les DCG sont du sucre syntaxique pour les prédicats, ils peuvent également recevoir des opérateurs pour les noms. Cela fonctionne comme prévu lorsque vous les appelez en tant que DCG à partir d'un DCG ou en utilisant les phraseprédicats ou autres qui sont conçus pour fonctionner avec les DCG. Lorsque vous les appelez comme des prédicats, des parenthèses sont requises (par exemple A+B-->...doivent être appelées comme +(A,B,...)) car les prédicats DCG prennent deux arguments supplémentaires pour leurs listes de différences. Pour les opérateurs nommés DCG avec plus de deux arguments utilisant la correspondance de modèle d'opérateur, il est important de s'assurer lors de l'appel en tant que prédicat que les opérateurs correspondant au modèle sont distribués correctement.

Donner des noms d'opérateurs aux DCG qui ne prennent pas d'arguments supplémentaires peut être utile si vous devez les appeler dans votre programme, car vous pouvez le faire sans utiliser de parenthèses. La prudence est de mise, car il se peut que ce que vous enregistrez entre parenthèses vous fasse perdre à l'espacement supplémentaire requis pour analyser les opérateurs adjacents.

Exemples

/ -->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,[]).

La sortie sera

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

Essayez-le en ligne!

Avertissements

Avec les opérateurs unaires +et -, Prolog interprétera +20ou -20sous forme de nombres au lieu d'un appel à un +/1ou -/1prédicat. Les prédicats donnés unaires +ou en -tant que noms peuvent toujours être appelés sur le numéro en utilisant des parenthèses ( +(20), -(20)). Si en évitant les octets supplémentaires de parenthèses est souhaitable d' autres opérateurs unaires tels que \, $, etc. peuvent être utilisés comme noms à la place.

La combinaison de la mise en correspondance des modèles et des prédicats nommés par l'opérateur n'est pas entièrement sans défauts. Si vous avez deux prédicats qui ont le même opérateur que leur nom et avec une correspondance de modèle, l'un est strictement plus général que l'autre, alors le plus général peut être appelé en premier ou si le moins général échoue (selon leur ordre dans la source) . Par exemple, dans l'exemple ci-dessus, si A-B+C*Dne correspond pas à son entrée, Prolog essaiera d'appeler X+Y. Cela se traduira par une erreur car length/2nécessite Yd'être un entier qu'il ne sera pas car il sera dans le formulaire C*D. Cela peut être évité simplement en s'assurant que deux prédicats n'ont pas le même opérateur que leur nom ou si cela échoue, en utilisant des coupes et un ordre soigneux de la source.

0 '
la source
3
Il est étonnant de voir à quel point cette astuce est utile pour le golf de code. Je viens de réduire le nombre d'octets d'une réponse de 16% en utilisant cette astuce seule!
DLosc
6

Essayez de mettre tous les cas possibles dans une seule règle

La manière propre de programmer dans Prolog est de déclarer plusieurs règles pour le même prédicat. Par exemple, un prédicat pour inverser une liste avec un accumulateur ressemblerait à ceci:

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

Dans Code-golf, nous pouvons supprimer la première règle et ajouter un ;à la fin de la deuxième règle pour coder la fin de la récursivité:

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

Nous savons que la première condition r(T,[H|Z],R)échouera si T est vide, c'est-à-dire si la récursion doit se terminer et ainsi nous pouvons ajouter notre terminaison comme une clause ou après.

Le même principe fonctionne dans de nombreuses situations. Notez cependant qu'il est parfois plus court de déclarer une autre règle que de le faire.

Fatalize
la source
6

Une astuce souvent utile: utiliser les contraintes CLP (FD) pour l'arithmétique des nombres entiers pour obtenir des prédicats qui peuvent être automatiquement utilisés dans plusieurs directions, évitant ainsi les conditions et les branches et variantes dédiées.

Utilisez B-Prolog ou GNU Prolog, où de telles contraintes sont disponibles, sans avoir à charger de bibliothèques.

tapis
la source
2
C'est toujours quelque chose que je déteste avec SWI-Prolog lorsque je fais des défis ici. L'utilisation de CLPFD rendrait certaines choses beaucoup plus propres et plus courtes, mais vous devez ajouter beaucoup de code supplémentaire pour le faire fonctionner (l'inclusion en soi est beaucoup ...), ce qui ne vaut généralement pas la peine. Je pense que je ne l'ai utilisé que dans cette réponse .
Fatalize
3
Je déteste cela aussi, et il est certain que le moment viendra éventuellement de devenir library(clpfd)une bibliothèque préchargée ou au moins autochargée également dans SWI-Prolog. Cela peut prendre quelques années avant que l'arithmétique déclarative ne soit pleinement comprise et appréciée par tous les utilisateurs, qui ont désormais accumulé des décennies d'expérience avec des fonctionnalités de bas niveau obsolètes. Plus vous utilisez et préconisez CLP (FD), plus tôt nous l'obtiendrons par défaut. Jusque-là, vous pouvez simplement mettre :- use_module(library(clpfd)).votre ~/.swiplrcet simplement déclarer que vous utilisez cette "variante" de SWI-Prolog.
mat
6

Utiliser des opérateurs arithmétiques comme constructeurs de tuple et contre paires

Si vous devez passer une seule structure composée de deux ou plusieurs valeurs, la chose la plus évidente à utiliser est une liste, par exemple [A,B]. C'est vraiment verbeux, cependant.

Il y a une alternative. Les valeurs Prolog peuvent stocker une structure imbriquée à peu près arbitraire, qui n'est pas évaluée. Voici un exemple montrant comment cela fonctionne:

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

member(A,B)est juste un tuple nommé dans cette situation, et l'extérieur member(qui est un appel de fonction) le traite comme tel.

Bien que les tuples nommés soient assez utiles dans la programmation Prolog non-golfée, ils peuvent sembler encore plus verbeux que l'approche par liste. Cependant, nous pouvons utiliser à peu près des caractères arbitraires dans le nom du constructeur de tuple (en supposant qu'ils soient correctement cités); au lieu de quelque chose de mignon memberou d'un personnage unique a, nous pouvons faire quelque chose comme ceci:

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

Ici, nos constructeurs de tuple sont '-'et '/'. Et il est intéressant de noter ce que la jolie imprimante en a fait; il utilise la notation infixe pour les tuples. C'est vraiment concis et analyse de la même manière que le ferait une opération arithmétique comparable. (Cela explique également pourquoi l'arithmétique n'utilise ispas =; A = 1+2s'unifierait Aavec le tuple '+'(1,2) , donc une syntaxe distincte est nécessaire pour évaluer réellement l'expression arithmétique non évaluée.) Parce qu'un constructeur de tuple doit être appelé quelque chose , vous pouvez tout aussi bien utiliser un caractère qui a un lacet syntaxe (et en bonus, -et/sont également parmi les choix les plus courants dans le code non-golfé lorsqu'ils veulent un constructeur de tuple jetable rapide plutôt que quelque chose de significatif, de la même manière qui iest souvent utilisée comme variable de boucle, ils sont donc tout à fait raisonnables à utiliser dans votre entrée et sortie s'il vous arrive d'y vouloir un tuple pour une raison quelconque).

'-'et '/'sont de bons choix pour les constructeurs de tuple car ils ont un bon comportement et une priorité utile, vous permettant d'écrire des littéraux de tuple de manière laconique. Cependant, notez que vous n'avez pas à vous soucier de la priorité lorsque des valeurs intermédiaires sont produites dans le programme. Prolog conserve les tuples stockés sous forme d'arborescence plutôt que sous forme de code source, et les jolies imprimantes peuvent les afficher sans ambiguïté:

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

Parce que la syntaxe de tuple est si concise ( f(A,B)n'est pas plus courte quef(A-B) ), vous pouvez remplacer plusieurs arguments de prédicat par des tuples sans frais, ce qui signifie que si un prédicat doit passer deux ou plusieurs de ses arguments à un autre prédicat, vous pouvez souvent les former en un tuple et passez simplement le tuple (bien que cela nécessite de changer tous les appels au prédicat, en plus du prédicat lui-même, pour utiliser un mélange approprié de constructeurs de tuple et de virgules).

Un autre avantage de cette syntaxe est que vous devez utiliser des listes en interne (plutôt que d'interagir avec des prédicats standard); une liste est fondamentalement juste un ensemble de cellules contre imbriquées, et une cellule contre est juste un tuple avec constructeur '.', comme on peut le voir ici:

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

Si votre code utilise des listes "manuellement", il peut être très judicieux d'utiliser un constructeur de tuple moins volumineux que '.'. Un choix courant pour moi est de représenter une cellule contre comme '/'(Tail,Head)(car il s'agit de la plus lisible que vous puissiez obtenir dans la sortie de débogage sans gaspiller les caractères). Notez que vous voudrez probablement aussi votre propre []équivalent; tu pourrais utiliser[] mais il fait deux octets de long et il y a beaucoup d'atomes d'un octet (toutes les lettres minuscules) que vous pouvez utiliser à la place.

Ainsi, par exemple, la liste suivante:

[1,2,3]

pourrait être converti en une représentation manuelle dans le même nombre de caractères comme celui-ci:

x/3/2/1

tout en gagnant l'avantage que les [H|T]correspondances de modèle de style peuvent maintenant être écrites plus sèchement que T/H, et un test contre la liste vide comme juste xplutôt que plus long []. (Bien sûr, cela vient avec l'inconvénient évident que member, appendetc., ne fonctionnera pas sur cette représentation.)


la source
+1! Il n'y a pas besoin de guillemets simples lors de l'utilisation de -et /. Ce sont déjà des atomes parfaitement normaux.
mat
Et, il n'y a pas besoin de guillemets simples ., à condition que les caractères suivants ne soient ni une %ni une mise en page.
faux
5

Syntaxe plus courte pour les listes de listes et un moyen de déclarer des cartes

Vous pouvez enregistrer des octets sur des listes de listes. Si vous avez une liste [[1,2],[3,4]], vous pouvez la déclarer en tant que [1:2,3:4], ce qui économise 4 crochets = 4 octets. Notez que vous pouvez utiliser autre chose que :(par exemple, ^).

1:2n'est pas réellement une liste dans ce cas (alors qu'elle l' [1,2]était), elle est représentée en interne comme :(1,2). Par conséquent, vous ne pouvez pas utiliser de prédicats qui fonctionnent sur des listes de ces sous-listes qui utilisent des deux-points.

Cette astuce est principalement utilisée pour déclarer des cartes, c'est-à-dire une liste de clés avec des valeurs qui leur sont attachées. Par exemple, si vous souhaitez déclarer une carte Mcontenant l'orthographe d'un chiffre en anglais et en français, vous pouvez faire quelque chose comme ceci:

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

Vous pouvez ensuite par exemple récupérer des éléments de la carte avec un prédicat intégré comme member/2. Par exemple, si vous voulez le chiffre et le mot anglais correspondant à 'Quatre'in M, vous pouvez faire:

member(Digit:Name:'Quatre',M).
Fatalize
la source
1
Vous pouvez généraliser cela. Par exemple, vous pouvez câbler en [[1,2],[3,4]]tant que 1*2+3*4, c'est-à-dire +(*(1,2),*(3,4))utiliser ainsi un seul octet là où vous en auriez autrement besoin de deux, pour ouvrir et fermer des parenthèses.
mat
Les listes de devis doubles sont encore plus courtes: "abc"au lieu de[a,b,c]
faux
5

Une astuce intéressante: lorsque vous devez échouer , utilisez quelque chose qui est équivalent à  false / 0 , mais plus court, tel que:

? - répéter, writeln (salut), 0 = 1 .
tapis
la source
3
Obligatoire La citation de l'Art de Prolog : " Dans la programmation Prolog (contrairement, peut-être, à la vie en général), notre objectif est d'échouer le plus rapidement possible ". Fun fait: vous pouvez également utiliser \+!comme 3 octets façon bizarre à l' échec qui ne déclenche réellement la coupe !(voir ce pour pourquoi ). Je ne pense pas qu'il soit possible d'échouer en moins de 3 octets.
Fatalize
Je pensais aussi à cette citation quand j'ai écrit ceci ;-)
mat
2
Nous avons vraiment besoin des deux versions, des \+!colles à gauche pour les autres caractères graphiques, tandis que des 0=1colles à gauche pour les noms.
faux
5

Réutiliser un prédicat avec différents modes d'appel

Par exemple, vous pouvez analyser et imprimer une structure avec le même prédicat, une fois avec un argument variable et une autre fois avec un terme fondamental. J'ai utilisé cette approche dans Make the Stretchy Snakes Kiss . Ce n'est pas possible dans tous les défis, bien sûr.

coredump
la source