Have you ever wondered about kay eights? What it is? Where it comes from? and why does it keep showing up everywhere?
Numeronyms are abbreviations that involve (you guessed it) numerals. They come in many forms, but in one common subcategory middle letters are substituted for their length. Let's call these Bookend Numeronyms.
Example: The word 'internationalization' is 20 letters long. The first letter is 'i', the final letter 'n'. So its Bookend Numeronym is 'i18n'.
If you're reading along, you no doubt know where this is going. Like so many who came before, we'll be writing a program to generate these numeronyms. But unlike those who came before us, we'll be writing it in Prolog. If you've never worked with Prolog, this is going to be... different. This isn't a full tutorial, but I hope it contains enough to pique your interest.
If you want, you can skip to the end.
Install
First, let's download SWI Prolog. You can find it on their website. Or just
$ brew install swi-prolog
If you plan on following along, you probably want to checkout the Getting started quickly guide.
Create our Dictionary
In order to expand i18n we need to know 'internationalization' is a word. So
let's grab a dictionary. Download a dictionary of words. To simplify things I downloaded
words_alpha.txt from this handy github page.
Now lets convert that word file into a prolog database. (You may need to delete the carriage return as I've done here.)
tr -d '\r' < words_alpha.txt | sed 's/.*/word(&)./' > words_alpha.pl
Now we can look at our file:
$ head words_alpha.pl
word(a).
word(aa).
word(aaa).
word(aah).
word(aahed).
word(aahing).
word(aahs).
word(aal).
word(aalii).
word(aaliis).
Load our Dictionary
Fire up swipl and 'consult' the file containing our word database.
❯ swipl
Welcome to SWI-Prolog (threaded, 64 bits, version 9.0.4)
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).
?- [words_alpha].
true.
At any point below you can enter the body of the method in the REPL.
Make an Initial Attempt
We want to build a tool to let us understand a given numeronym. Remember the description:
- It starts with the first letter of the word
- The next number is the length of the middle of the word
- It ends with the final letter of the word
To keep this post simple, let's assume the user will provide these parts independently. Here is the contract for our predicate:
% An abbreviation with a first letter F, a middle numver N, and a last letter L
% is a bookend numeronym for the word W.
bookend_numeronym(F, N, L, W) :-
Let's begin the implementation. Keeping it simple. We know W is a word.
word(W)
Next, we can say something about the length of W. It's 2 + N since the number
doesn't include the first and last letters of W.
WLength is N + 2,
atom_length(W, WLength)
We haven't used F and L yet, let's assign their places as bookends. We'll do
this with a predicate that concatenates the first and second atoms to create the
third.
atom_concat(F, _, W),
atom_concat(_, L, W)
Putting it all together:
bookend_numeronym(F, N, L, W) :-
word(W),
WLength is N + 2,
atom_length(W, WLength),
atom_concat(F, _, W),
atom_concat(_, L, W).
Now let's put it to use. Load up the file numeronym.pl containing the
predicate:
?- [numeronym].
Now you can query it. Remember, if there are multiple solutions you can type semicolon to evaluate the next solution. To end the computation type period.
?- bookend_numeronym(i, 18, n, W).
W = institutionalisation ;
W = institutionalization ;
W = intercrystallization ;
W = interdifferentiation ;
W = internationalisation ;
W = internationalization ;
false.
Great! The job's done, right? Not so fast...
Discover a Problem
The thing that makes Prolog different from so many other languages, is that the
'mode' of each parameter is not baked into the definition. That is, there is
no 'return' parameter. All the parameters are solved for. So it is possible to
call our predicate in other ways. Instead of providing F, N, and
L we can provide two of the three.
Let's see how it goes. Here we provide F and N, but leave L and W
unbound. Here we ask for all numeronyms that start with i18 but we don't care
about the ending letter.
?- bookend_numeronym(i, 18, L, W).
L = W, W = incomprehensibleness ;
L = ncomprehensibleness,
W = incomprehensibleness ;
L = comprehensibleness .
% etc.
Huh, that's not right. It seems like L is taking on all sorts of values besides
n. It should only be a single character. Let's add another constraint.
atom_length(L, 1)
Now our code reads:
bookend_numeronym(F, N, L, W) :-
word(W),
WLength is N + 2,
atom_length(W, WLength),
atom_length(L, 1),
atom_concat(F, _, W),
atom_concat(_, L, W).
Alright, trying again....
?- bookend_numeronym(i, 18, L, W).
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR: [11] atom_length(_2524,1)
ERROR: [10] bookend_numeronym(i,18,_2554,abdominohysterectomy) at /Users/hpincket/code/numeronyms/numeronym.pl:15
ERROR: [9] toplevel_call(user:user: ...) at /opt/homebrew/Cellar/swi-prolog/9.0.4/libexec/lib/swipl/boot/toplevel.pl:1173
Crap. Looks like we're not supposed to call atom_length that way.
Reattempt
Let's start again. There seems to be something fishy with our use of
atom_length. Checking the docs, we see it only accepts atom_length(+, -), and we would like
to sometimes provide the length of an atom without yet knowing what it is.
You can learn more about documenting supported modes [here][https://www.swi-prolog.org/pldoc/man?section=modes].
We can solve this by switching out our data type. Instead of atoms, we'll use lists. Lists are a better tool for this problem since we can construct a list of unbound variables, unlike an atom, which is, well, atomic. Begin our rewrite.
First, we should convert our atom, W, to a list. Lucky for us, there's a predicate
for that:
?- atom_chars(cats, WL).
WL = [c, a, t, s].
Now we can make logical statements about the length of WL and thus W.
?- word(W), atom_chars(W, WL), length(WL, 10).
W = aardwolves,
WL = [a, a, r, d, w, o, l, v, e|...]
Since we are dealing with lists, we must swap atom_concat for append:
?- word(W), atom_chars(W, WL), length(WL, 10), append([d], _, WL).
W = dabblingly,
WL = [d, a, b, b, l, i, n, g, l|...]
Note how we wrap d in a list, that's because append expects all of its
arguments to be lists.
With these updates, try to write a predicate bookend_numeronym_2 which will
work for the bookend_numeronym(i, 17, L, W) query from before.
Click to see Implementation of bookend_numeronym_2
bookend_numeronym_2(F, N, L, W) :-
word(W),
WLength is N + 2,
atom_chars(W, WL), length(WL, WLength),
append([F], _, WL),
append(_, [L], WL).
Trying it out
And when we reload and use it:
?- bookend_numeronym_2(i, 18, L, W).
L = s,
W = incomprehensibleness ;
Voila! Ok, let's try this with some other modes.
?- bookend_numeronym_2(F, 18, L, internationalization).
F = i,
L = n .
Awesome.
What about providing W and asking for all the other parameters?
?- bookend_numeronym_2(F, N, L, internationalization).
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR: [10] bookend_numeronym_2(_11438,_11440,_11442,internationalization)
ERROR: [9] toplevel_call(user:user: ...) at /opt/homebrew/Cellar/swi-prolog/9.0.4/libexec/lib/swipl/boot/toplevel.pl:1173
oof! It looks like we've still got a problem with N.
Add Constraints
You can probably guess the line. Something about WLength is L + 2 doesn't work
with an ungrounded L. And that something is is.
But hope is not lost, there is a trick you can pull out to
handle this scenario. Constraint Programming.
Constraint Logic Programming over Finite Domains (clpfd) might be the coolest part of Prolog. The 'Finite Domain' means integers, and by restricting to integers we are able to declare relations which a more advanced solving engine can make deductions where we previously couldn't.
At the top of your file, import clpfd, like so:
:- use_module(library(clpfd)).
And then change WLength is N + 2 to WLength #= N + 2. This sets a
relation between these two integers (docs). Our new predicate looks like so:
bookend_numeronym_3(F, N, L, W) :-
word(W),
WLength #= N + 2,
atom_chars(W, WL), length(WL, WLength),
append([F], _, WL),
append(_, [L], WL).
Now re-load and try again:
?- bookend_numeronym_3(F, N, L, internationalization).
F = i,
N = 18,
L = n ;
false.
Fin
Our final predicate can solve for any combination of numeronym and word parameters. We achieved this by converting our atoms into lists and by sprinkling some constraint programming over our integer math. All of this in 5 terse lines.
bookend_numeronym_3(F, N, L, W) :-
word(W),
WLength #= N + 2,
atom_chars(W, WL), length(WL, WLength),
append([F], _, WL),
append(_, [L], WL).
And most importantly, it can answer the burning question, "What is k8s?!"
?- bookend_numeronym_3(k, 8, s, W).
W = kabbeljaws ;
W = kakidrosis ;
W = kaligenous ;
W = kanephoros ;
W = karyolysis ;
W = karyolysus ;
W = katholikos ;
W = kazatskies ;
W = keennesses ;
Supporting multiple modes allows for predicate re-use across the system. Instead of two or three functions, we've written one. Take this query for example:
% Find a bookend numeronym where the first and last letters are the same,
% And the number is a multiple of 3 and is at least 18 characters long.
?- bookend_numeronym_3(X, N, X, W), N #= 3 * Y, Y #> 5.
X = e,
N = 18,
W = encephalomeningocele,
Y = 6 ;
Not the most practical, but definitely the most fun!