Tips for golfing in Prolog

Question

What general tips do you have for golfing in Prolog? I am looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to Prolog (e.g. one letter variables is not specific to Prolog to reduce the size of programs).

Please indicate in your tips if it is specific to an implementation of Prolog (e.g. SWI-Prolog specific built-ins)

Please post only one tip per answer, or a list of tips that are all closely related to the same main idea.

Answer 1

Use Operators for Predicate Names

It is possible to give predicates operators as names so long as the operator is one of the predefined operators (listed here) and is not already defined as a predicate. This saves a few bytes both when defining and calling the predicate since operator predicates do not need to be written in the normal name(arg1,arg2,etc..) form and can be called as one might expect with operators.

For one and two argument predicates, they can be give the names of unary and binary operators, respectively. For higher arity predicates, we can still avoid parentheses using pattern matching. For example if we have a predicate A+B+C:-..., Prolog will use its operator precedence and associativity rules to transform it into (A+B)+C:-... which is a operator predicate where the first argument is pattern matched to A+B. Or A-B+C*D:-... which becomes (A-B)+(C*D) so its first argument is pattern matched to A-B and its second is pattern matched to C*D.

Examples

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

The output will be X = 5.

Try it Online!

Corollary

Since DCGs are syntactic sugar for predicates they too can be given operators for names. This works as expected when calling them as DCGs either from a DCG or using the phrase predicates or others that are designed to work with DCGs. When calling them as predicates parentheses are required (eg A+B-->... must be called like +(A,B,...)) since DCG predicates take an additional two arguments for their difference lists. For operator named DCGs with more than two arguments using operator pattern matching then it is important to make sure when calling it as a predicate that the pattern matched operators are distributed correctly.

Giving operator names to DCGs that take no additional arguments can be useful if you need to call them within your program since then you can do so without using parentheses. Caution is required because it can be the case that what you save in parentheses you can lose to added spacing required to parse adjacent operators.

Examples

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

Output will be

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

Try it online!

Caveats

With the unary operators + and -, Prolog will interpret +20 or -20 as numbers instead of a call to a +/1 or -/1 predicate. Predicates given unary + or - as names can still be called on number by using parentheses (+(20), -(20)). If avoiding the extra bytes from parentheses is desirable other unary operators such as \, $, etc can be used as names instead.

The combination of pattern matching and operator named predicates is not entirely without flaws. If you have two predicates that have the same operator as their name and with pattern matching one is strictly more general than the other then the more general one may get called first or if the less general one fails (depending on their ordering in the source). For instance in the example above if A-B+C*D fails to match its input then Prolog will try calling X+Y. This will result in an error because length/2 require Y to be an integer which it will not be since it will be in the form C*D. This can be avoided simply by making sure no two predicates have the same operator as their name or if that fails then using cuts and careful ordering of the source.

Answer 2

Try to put every possible case into a single rule

The clean way to program in Prolog is to declare multiple rules for the same predicate. For example, a predicate to reverse a list with an accumulator would look like this:

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

In Code-golf, we can remove the first rule, and add a ; at the end of the second rule to code the recursion end:

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

We know that the first condition r(T,[H|Z],R) will fail if T is empty, i.e. if the recursion need to end and thus we can add our termination as an or clause after it.

The same principle works in a lot of situations. Note however that sometimes it is actually shorter to declare another rule rather than doing this.

Answer 3

One trick that is frequently useful: Use CLP(FD) constraints for integer arithmetic to obtain predicates that can be automatically used in several directions, thus avoiding conditions and dedicated branches and variants.

Use B-Prolog or GNU Prolog, where such constraints are available out of the box, without needing to load any libraries.

Answer 4

Use arithmetic operators as tuple constructors and cons pairs

If you need to pass a single structure consisting of two or more values, the most obvious thing to use is a list, e.g. [A,B]. That's really verbose, though.

There's an alternative. Prolog values can store a pretty much arbitrary nested structure, which isn't evaluated. Here's an example showing how that works:

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

member(A,B) is just a named tuple in this situation, and the outside member (which is a function call) is treating it as such.

Although named tuples are fairly useful in non-golfed Prolog programming, they might seem even more verbose than the list approach. However, we can use pretty much arbitrary characters in the name of the tuple constructor (assuming they're properly quoted); instead of something cute like member or a single character like a, we can do something like this:

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

Here, our tuple constructors are '-' and '/'. And it's interesting to note what the pretty-printer did with them; it's using infix notation for the tuples. This is really terse, and parses the same way that the comparable arithmetic operation would. (This also explains why arithmetic uses is not =; A = 1+2 would unify A with the tuple '+'(1,2), so separate syntax is needed to actually evaluate the unevaluated arithmetic expression.) Because a tuple constructor has to be called something, you may as well use a character that has a terse syntax (and as a bonus, - and / are some of the most common choices in non-golfed code too when they want a quick throwaway tuple constructor rather than something meaningful, in much the same way that i is often used as a loop variable, so they're entirely reasonable to use in your input and output if you happen to want a tuple there for some reason).

'-' and '/' are good choices for tuple constructors because they have well-behaved and useful precedence, allowing you to write tuple literals tersely. However, note that you don't need to worry about precedence when intermediate values are produced inside the program. Prolog keeps the tuples stored as a tree rather than as source code, and pretty-printers can output it unambiguously:

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

Because the tuple syntax is so terse (f(A,B) is no shorter than f(A-B)), you can replace multiple prediccate arguments with tuples at no cost, meaning that if a predicate needs to pass two or more of its arguments to another predicate, you can often form them into a tuple and just pass the tuple (although this will require changing all calls to the predicate, in addition to the predicate itself, to use an appropriate mix of tuple constructors and commas).

Another advantage of this syntax is if you need to use lists internally (rather than to interoperate with standard predicates); a list is basically just a set of nested cons cells, and a cons cell is just a tuple with constructor '.', as can be seen here:

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

If your code uses lists "manually", it can make a lot of sense to use a less bulky tuple constructor than '.'. A common choice for me is to represent a cons cell as '/'(Tail,Head) (because it's about the most readable you can get in debug output without wasting characters). Note that you'll probably want your own [] equivalent too; you could use [] but it's two bytes long, and there are plenty of one-byte atoms (all the lowercase letters) that you can use instead.

So for example, the following list:

[1,2,3]

could be converted into a manual representation in the same number of characters like this:

x/3/2/1

whilst gaining the advantage that [H|T]-style pattern matches can now be written more tersely as T/H, and a test against the empty list as just x rather than the longer []. (Of course, this comes with the obvious disadvantage that member, append, etc., won't work on this representation.)

Answer 5

Shorter syntax for lists of lists and a way to declare maps

You can save bytes on lists of lists. If you have a list [[1,2],[3,4]], you can actually declare it as [1:2,3:4], which saves 4 brackets = 4 bytes. Note that you can use something else than : (for example, ^).

1:2 isn't actually a list in that case (whereas [1,2] was), it is represented internally as :(1,2). Therefore you cannot use predicates that work on lists on those sublists that use colons.

This trick is mainly used to declare maps, i.e. a list of keys with values attached to them. For example, if you want to declare a map M that contains the spelling of a digit in both English and French, you could do something like this:

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

You can then for example retrieve elements of the map with a built-in predicate like member/2. For example, if you want the digit and English word corresponding to 'Quatre' in M, you could do:

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

Answer 6

One neat trick: When you need to fail, use something that is equivalent to false/0, but shorter, such as:

?- repeat, writeln(hi), 0=1.

Answer 7

Shorter stdlib alternatives

These may not apply exactly based on what you are using the predicates for.

• numlist/3 is better to generate numeric range lists than between/3 with bagof.
• bagof/3 is a substitute for findall/3 if you can guarantee the result to be a non-empty list.
• Many string related predicates also use atoms. eg: format(atom(X),Y,R) can be done instead of string(X), saving 2 bytes
• some predicates are good aliases for many uses of foldl:
  • sumlist in place of foldl(plus,...)
  • similarly for max_list, min_list, etc.
• In aggregate_all(X,Y,_)
  • X=count,Y=member(...) case can be replaced with occurrences_of_term(E,S,O)

Answer 8

Reuse a predicate with different calling modes

For example, you can parse and print a structure with the same predicate, once with a variable argument and another time with a ground term. I used this approach in Make the Stretchy Snakes Kiss. This is not possible in all challenges, of course.

Answer 9

Print as a side effect which cannot be undone by backtracking, using backtracking to loop.

Goals like "print the first 1000 integers" can be:

:-findall(X,(between(0,999,X)),Nums),maplist(writeln,Nums).

That can be shortened to:

:-findall(X,(between(0,999,X),writeln(X)),_).

Backtracking can be used to get rid of the findall loop:

:-between(0,999,X),writeln(X),false.

Use a shorter false as per another tip in these answers:

:-between(0,999,X),\+writeln(X).

Answer 10

Some tips for output writing

tab/1 will evaluate arithmetic expressions:

For instance, this will output a, 20 spaces, and then b: write(a),tab(4*5),write(b).

writef/1 will print character codes as characters.

Say X=[72, 101, 108, 108, 111] (the string "Hello"). Instead of:

maplist(put,X).

You can simply write:

writef(X).

Answer 11

Comparison operators will evaluate arithmetic terms without needing is/2 which can save some characters, e.g. before and after:

?- findall(X,(between(1,10,X),Y is X^2,Y>20),Xs).
Xs = [5, 6, 7, 8, 9, 10].

?- findall(X,(between(1,10,X),X^2>20),Xs).
Xs = [5, 6, 7, 8, 9, 10].

[fixed misunderstanding, thanks to @crowproxy]