Prerequisites
- SWI Prolog
- Latest VScode Extention for Prolog
- Scryer - A Prolog rewritten in Rust :)
Installation
I installed both SWI Prolog and Scryer Prolog. They’re not the only implementations out there, but they seemed the most useful for my purposes. SWI Prolog appears to be the standard: for example, the VS Code extension only supports debugging when using SWI.
Scryer was appealing because it’s written in Rust. Unfortunately, it quickly became obvious that it lacks many of the convenient libraries that SWI has (such as reading a file into a string) or even built-ins like length.
Prolog Basics
Prolog works a bit differently from most languages: it’s all about facts and rules. The rules try to infer outcomes based on the facts. Let’s take a quick look at a simple example:
capital(poland, warsaw).
capital(germany, berlin).
Save this in test.pro.
There doesn’t seem to be an official Prolog extension recommendation, but many folks use .pl. I prefer using .pro so it won’t collide with Perl’s .pl.
When Prolog loads the script we can test the facts we’ve declared:
❯ swipl -s day04.pro
Welcome to SWI-Prolog (threaded, 64 bits, version 9.2.9)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.
For online help and background, visit https://www.swi-prolog.org
For built-in help, use ?- help(Topic). or ?- apropos(Word).
?- capital(poland, warsaw).
true.
We can also run inference, for example:
?- capital(warsaw, X).
X = poland
Here, we’re asking Prolog for which values of X the fact capital(warsaw, X) holds. We can even ask for all possible pairs without supplying a known variable:
?- capital(X, Y).
X = poland
Y = warsaw ;
X = germany,
Y = berlin.
Prolog shows you the first result, then waits for a semicolon (;) to give you the next. Under the hood, it essentially brute-forces checks of each fact, but Prolog engines use clever optimizations to make it surprisingly fast.
Usually, Prolog encourages defining facts and rules in a file, but we can also do this in a REPL. To define facts on the fly:
?- [user].
|: :- dynamic(capital/2).
|: capital(poland, warsaw).
|: capital(germany, berlin).
|: ^D% user://1 compiled 0.00s, 2 clauses
Press Ctrl+D to finish, and Prolog compiles these facts for you.
A Fun Easter Egg
I discovered a neat difference between Scryer and SWI. If you query Scryer with a variable it can’t bind, it just fails:
?- Something.
.
error(instantiation_error,repl/0).
But if you do the same in SWI:
?- Something.
% ... 1,000,000 ............ 10,000,000 years later
%
% >> 42 << (last release gives the question)
It’s one of those small, amusing things :)
Reading Files
Initially, to load a file in SWI Prolog, I used the readutil library:
use_module(library(readutil)).
main(Filename) :-
process(Filename).
process(Filename) :-
open(Filename, read, Fd),
read_file_to_string(Filename, Str, []),
close(Fd),
write(Str),
true.
This prints the file’s contents:
?- main('example.txt').
MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX
true.
But to make it work in Scryer, I wrote a pure Prolog version:
read_file(Filename, Lines) :-
open(Filename, read, Stream),
read_lines(Stream, Lines),
close(Stream).
read_lines(Stream, []) :-
at_end_of_stream(Stream).
read_lines(Stream, [Line|Rest]) :-
\+ at_end_of_stream(Stream),
read_line(Stream, Line),
read_lines(Stream, Rest).
read_line(Stream, Line) :-
get_char(Stream, Char),
( Char == end_of_file -> Line = []
; Char == '\n' -> Line = []
; Line = [Char|Rest],
read_line(Stream, Rest)
).
Here are a few interesting bits:
- Variable Binding
We call
read_file('example.txt', Lines)with Lines unbound, and Prolog binds it to the file’s contents. - Negation
The
\+ at_end_of_stream(Stream)checks if we’re NOT at the end of the stream. If that succeeds, we read a line and recurse. - If-Then-Else Syntax
Prolog uses
(Condition -> Then; Else). Due to operator precedence, we typically wrap it in parentheses. For the line reader, if the character is end_of_file or a newline, we return an empty list. Otherwise, we accumulate characters recursively.
The Puzzle
I was working on Advent of Code 2024 Day 4. The goal is to find occurrences of the word XMAS spelled forward or backward, in all directions (horizontal, vertical, diagonal) within a grid of characters.
Let’s start by finding the first letter, X, in every possible cell:
check_letter(Grid, Y, X, Letter) :-
cell(Grid, Y, X, Letter).
find_x(Grid, Occurrences) :-
grid_size(Grid, Height, Width),
findall((X,Y),
( between(1, Height, Y),
between(1, Width, X),
check_letter(Grid, Y, X, 'X')
), Occurrences).
?- read_grid('example.txt', Grid), find_x(Grid, Occurences).
Occurences = [(5, 1), (6, 1), (5, 2), (3, 3), (5, 3), (10, 4), (1, 5), (7, 5), (..., ...)|...]
Prolog’s findall/3 collects all (X,Y) pairs where the letter is X. Behind the scenes, between(1, Width, X) generates possible X values, and similarly for Y, then check_letter checks if the cell matches.
?- between(1, 10, X).
X = 1
; X = 2
; X = 3
; X = 4
; X = 5
; X = 6
; X = 7
; X = 8
; X = 9
; X = 10
; false.
For the full solution, I used a recursive check_word predicate. It checks each subsequent letter in the grid while moving in the specified direction:
directions([ (-1,-1), (-1,0), (-1,1),
( 0 -1), ( 0,1),
( 1,-1), ( 1,0), ( 1,1)]).
check_word(_, _, _, _, _, []).
check_word(Grid, Y, X, MoveY, MoveX, [Letter|Rest]) :-
cell(Grid, Y, X, Letter),
NewY is Y + MoveY,
NewX is X + MoveX,
check_word(Grid, NewY, NewX, MoveY, MoveX, Rest).
part1(Grid, Word, Count) :-
grid_size(Grid, Height, Width),
directions(Directions),
findall(1,
( between(1, Height, Y),
between(1, Width, X),
member((MoveY, MoveX), Directions),
check_word(Grid, Y, X, MoveY, MoveX, Word)
), Occurrences),
length(Occurrences, Count).
For part 2, I just needed to find diagonal placements of smaller substrings (MAS and SAM):
valid_diagonal('M', 'A', 'S').
valid_diagonal('S', 'A', 'M').
part2(Grid, Count) :-
grid_size(Grid, Height, Width),
LowY is 2,
LowX is 2,
HighY is Height - 1,
HighX is Width - 1,
findall(1,
( between(LowY, HighY, Y),
between(LowX, HighX, X),
cell(Grid, Y, X, 'A'),
% Check main diagonal (top–left and bottom–right)
TopLeftY is Y - 1, TopLeftX is X - 1,
BottomRightY is Y + 1, BottomRightX is X + 1,
cell(Grid, TopLeftY, TopLeftX, TopLeftLetter),
cell(Grid, BottomRightY, BottomRightX, BottomRightLetter),
valid_diagonal(TopLeftLetter, 'A', BottomRightLetter),
% Check anti–diagonal (top–right and bottom–left)
TopRightY is Y - 1, TopRightX is X + 1,
BottomLeftY is Y + 1, BottomLeftX is X - 1,
cell(Grid, TopRightY, TopRightX, TopRightLetter),
cell(Grid, BottomLeftY, BottomLeftX, BottomLeftLetter),
valid_diagonal(TopRightLetter, 'A', BottomLeftLetter)
), Occurrences),
length(Occurrences, Count).
And that’s it! When I run:
?- main('example.txt').
Part 1: 16
Part 2: 9
true
I get the final answers. This detour into Prolog felt like a breath of fresh air—very different from C, Rust, or even Lisp. If you’re curious, you can find the full code on my Codeberg repo.
Hope this helps if you’re exploring Prolog or working through Advent of Code with logic programming. Happy hacking!
Comments
Discussion powered by , hop in. if you want.