That Giant’s Causeway puzzle in Prolog

Tuesday, 13th January, 2015

Chris Lamb published a very nice blog post the other day showing a wooden logic puzzle he’d found, and implementing a solver in Python.

It was such a nice post I thought I’d write one in Prolog. Here it is (and in a gist):

% hex tiles puzzle
% -
% -

:- use_module(library(clpfd)).  %% for all_different/1

%% tile(Name, Colours).

% tiles from picture
% tile(11, [red, blue, black, yellow, green, white]).
% tile(22, [white, black, yellow, green, blue, red]).
% tile(33, [green, blue, black, yellow, red, white]).
% tile(44, [white, black, red, green, blue, yellow]).
% tile(55, [white, blue, green, yellow, black, red]).
% tile(66, [white, yellow, red, blue, black, green]).
% tile(77, [red, yellow, green, black, blue, white]).

% re-jigged a bit
tile(11, [white, black, red, green, blue, yellow]).
tile(22, [white, black, yellow, green, blue, red]).
tile(33, [white, blue, green, yellow, black, red]).
tile(44, [white, green, blue, black, yellow, red]).
tile(55, [white, red, blue, black, yellow, green]).
tile(66, [white, red, yellow, green, black, blue]).
tile(77, [white, yellow, red, blue, black, green]).

%% only six rotations allowed


%% rotate(List1, NStepsAntiClockwise, List2). 

rotate(Cs, 0, Cs).
rotate([A,B,C,D,E,F], 1, [B,C,D,E,F,A]).
rotate([A,B,C,D,E,F], 2, [C,D,E,F,A,B]).
rotate([A,B,C,D,E,F], 3, [D,E,F,A,B,C]).
rotate([A,B,C,D,E,F], 4, [E,F,A,B,C,D]).
rotate([A,B,C,D,E,F], 5, [F,A,B,C,D,E]).

%% colour(Name, Rotation, Position, Colour).

colour(N, R, P, C):-
    tile(N, Cs),
    X is (P + R) mod 6,
    nth0(X, Cs, C).

same_colour(N1, R1, P1, N2, R2, P2):-
    colour(N1, R1, P1, C),
    colour(N2, R2, P2, C).

solve(N1, R1, N2, R2, N3, R3, N4, R4, N5, R5, N6, R6, N7, R7):-
    all_different([N1, N2, N3, N4, N5, N6, N7]),

    same_colour(N1, R1, 3, N2, R2, 0),
    same_colour(N1, R1, 4, N4, R4, 1),
    same_colour(N1, R1, 5, N3, R3, 2),
    same_colour(N2, R2, 4, N5, R5, 1),
    same_colour(N2, R2, 5, N4, R4, 2),
    same_colour(N3, R3, 3, N4, R4, 0),
    same_colour(N3, R3, 4, N6, R6, 1),
    same_colour(N4, R4, 3, N5, R5, 0),
    same_colour(N4, R4, 4, N7, R7, 1),
    same_colour(N4, R4, 5, N6, R6, 2),
    same_colour(N5, R5, 5, N7, R7, 2),
    same_colour(N6, R6, 3, N7, R7, 0).

show(N, R):-
    tile(N, Cs),
    rotate(Cs, R, Rs),
    format("~d    ~w~n", [N, Rs]).

    solve(N1, R1, N2, R2, N3, R3, N4, R4, N5, R5, N6, R6, N7, R7),
    show(N1, R1),
    show(N2, R2),
    show(N3, R3),
    show(N4, R4),
    show(N5, R5),
    show(N6, R6),
    show(N7, R7).

Sergii Dymchenko recently posted a blog showing how a “greater than” sudoku can be solved with constraint logic programming and ECLiPSe CLP.

Sergii’s post inspired me to do the same for answer setprogramming, with clasp/gringo. I’ve uploaded the code to github.

Brief notes on ASP (& Sudoku)

I am just getting started with answer set prolog. Here are some first impressions:

Syntactically, it is very similar to Good Old Fashioned Prolog, with one or two additions. For example:

syntactic sugar

There’s a lot of sugar enabling concise code. e.g.,


expands to


headless predicates

A predicate without a head is known as a constraint. The sense is that the specified conjunction is not true.

:- paint(R, C1, N), paint(R, C2, N), C1 != C2.

In the sudoku code, paint/3 is a fact signifying that a cell at Row and Column has Number. The constraint above states that in a given row, a number can be at most one column.

multi-headed predicates

There seem to be various kinds of multi-headed predicates, with accompanying sugar for concise representation. A common construct is

1 { paint(R, C, P) : number(P) } 1 :- square(R, C).

The part of the head inside brackets is like a set comprehension and expands to

paint(R, C, 1) | paint(R, C, 2) | ... | paint(R, C, 8) | paint(R, C, 9).

Having this kind of disjunction in the head gives a kind of indeterminism: this disjunction is true if the body of the predicate is true.

The numbers to either side of the brackets put lower and upper bounds on the number of facts that this disjunction can introduce. So, in plain English, this predicate says something like “every square should be given exactly one number”.


Semantically there is a difference too. We understand an answer set prolog program as representing a set of states of affairs, where a state of affairs is a set of true facts (i.e., including no facts of the form ‘not P’).

Things like how many states of affairs, and which facts from each state of affairs, are reported to the user are dealt with by declarations (like #show in the sudoku script) and command line arguments.

In practice, this means that instead of passing round a data structure between predicates (e.g., a list of lists for a sudoku grid), statements inside predicates can be made which directly affect the database (i.e., the state of affairs) — e.g., the paint/3 statements scattered about sudoku.lp.

Describing it just now, that sounds scarily like global variables.

Extras for “Greater Than”

As a “Greater Than” Sudoku is just an ordinary sudoku with an extra constraint, I’ve put the required extra predicate lessEqual/4 in a separate script, sudoku_extra_gt.lp

The question grid is just the set of facts that we have initially. With standard sudoku, it’s the cell that have been given numbers, e.g., puzzle_easy.lp:

paint(1, 1, 7).
paint(1, 3, 3).
paint(1, 5, 8).
paint(1, 8, 1).
paint(2, 5, 6).
paint(3, 1, 6).
% ...

QUESTION FOR ASP EXPERTS: at first I tried “positive” constraints with a greaterThan/4 predicate, like this

% ...

but these seemed to be ignored in the answer set. Why? How should I have phrased it?

Running the solver on this Greater Than sudoku shows the paint predicates which are true given all the constraints:

$ clingo 0 puzzle_gt.lp sudoku.lp sudoku_extra_gt.lp
clingo version 4.4.0
Reading from puzzle_gt.lp ...
Answer: 1
paint(8,1,1) paint(2,2,1) paint(6,3,1) paint(5,4,1) paint(9,5,1) paint(3,6,1)
paint(4,7,1) paint(7,8,1) paint(1,9,1) paint(3,1,2) paint(6,2,2) paint(8,3,2)
paint(2,4,2) paint(4,5,2) paint(7,6,2) paint(1,7,2) paint(5,8,2) paint(9,9,2)
paint(6,1,3) paint(1,2,3) paint(7,3,3) paint(4,4,3) paint(2,5,3) paint(8,6,3)
paint(9,7,3) paint(3,8,3) paint(5,9,3) paint(5,1,4) paint(7,2,4) paint(1,3,4)
paint(3,4,4) paint(6,5,4) paint(9,6,4) paint(8,7,4) paint(4,8,4) paint(2,9,4)
paint(9,1,5) paint(4,2,5) paint(2,3,5) paint(7,4,5) paint(3,5,5) paint(5,6,5)
paint(6,7,5) paint(1,8,5) paint(8,9,5) paint(4,1,6) paint(8,2,6) paint(3,3,6)
paint(9,4,6) paint(1,5,6) paint(6,6,6) paint(5,7,6) paint(2,8,6) paint(7,9,6)
paint(7,1,7) paint(3,2,7) paint(4,3,7) paint(8,4,7) paint(5,5,7) paint(1,6,7)
paint(2,7,7) paint(9,8,7) paint(6,9,7) paint(1,1,8) paint(5,2,8) paint(9,3,8)
paint(6,4,8) paint(7,5,8) paint(2,6,8) paint(3,7,8) paint(8,8,8) paint(4,9,8)
paint(2,1,9) paint(9,2,9) paint(5,3,9) paint(1,4,9) paint(8,5,9) paint(4,6,9)
paint(7,7,9) paint(6,8,9) paint(3,9,9)

Models : 1
Calls : 1
Time : 20.837s (Solving: 17.59s 1st Model: 17.45s Unsat: 0.14s)
CPU Time : 20.836s

Open-Source Speech Recognition Toolkits

Tuesday, 26th August, 2014

Here’s a list of FOSS and FOSS-ish ASR toolkits: url, license and rough activity dates, and maybe the odd comment.

Apart from Sphinx4, which is written in The Java Programming Language, all of these are written in C/C++.

Kaldi looks the most interesting and mature. I’d also like to have more of a look at Bavieca, GMTK and TLK.

Have I missed any?

  • Bavieca
    Apache 2.0

  • GMTK
    Open Software License v. 3.0

  • HTK
    Weird license:

    Latest version is 3.4.1, 2009

  • iAtros

    unclear documentation
    unclear if HTK required
    designed for recognition of speech and handwriting

  • Kaldi
    Apache 2.0
    Current (last sf update 2014-08-11)

  • RASR
    Non-commercial use only

    Non-Commercial Use Only

    Free for non-commercial use only; commercial license request & pay

  • Sphinx
    Sphinx4 (java) is current
    Sphinx3 (C/C++) is unmaintained

  • TLK
    Apache 2.0
    2013 & current

MacOSX: telling tmux where libevent is

Friday, 8th August, 2014

tmux depends on libevent but after installing libevent, tmux still won’t configure:

$ ./configure
checking for a BSD-compatible install... /usr/bin/install -c
checking whether build environment is sane... yes
checking for a thread-safe mkdir -p... etc/install-sh -c -d
checking for pkg-config... no
checking for LIBEVENT... no
checking for library containing event_init... no
configure: error: "libevent not found"

You have to tell it where lib event is installed. I did a vanilla configure && make && sudo make install and it seems to have ended up in /usr/local/, so:

$ DIR="/usr/local/"
$ ./configure CFLAGS="-I$DIR/include" LDFLAGS="-L$DIR/lib"
checking for a BSD-compatible install... /usr/bin/install -c
checking whether build environment is sane... yes
checking for a thread-safe mkdir -p... etc/install-sh -c -d
checking that generated files are newer than configure... done
configure: creating ./config.status
config.status: creating Makefile
config.status: executing depfiles commands


Thanks to stackexchange.

Dependent Types in Prolog

Wednesday, 7th May, 2014

or, “Had we but world enough, and time …”

** intro

I’ve been occasionally looking into programming languages with dependent types, when a recent tweet gave me pause:


I got interested in dependent types because SO TOLD ME TO^W^W^W^W they seemed necessary to encode some constraints on types for some toy projects I was thinking of, namely:

  • for a Bayesian network: represent probabilities (positive floating point number less than or equal to 1.0) and discrete probability distributions (a {T, Probability} mapping where the sum of probabilities = 1.0);
  • for fast Fourier transformation: respresent a list whose length must be a power of 2.

Naively, I thought I might be able to do this kind of thing in Haskell. I don’t like the cult hype around Idris. I thought I might try it with ATS, which I like the look of a lot, but it’s proving slow getting into.

** prolog

In the meantime, here are the types represented in Prolog:

% some "dependent" types

%%%% X is a power of 2

    Y is X / 2,

%%%% X is a list whose length is a power of 2

    length(X, L),

%%%% X is a probability

    X >= 0,
    X =< 1.

%%%% X is a discrete probability distribution

    maplist(prob, Y),
    sum_list(Y, 1.0).

%%%% helpers

seconds([], []).
seconds([[_, Y] | Z], [Y | Z2]):-
    seconds(Z, Z2).

tuplist([[_X, _Y] | Z]):-

** next


I might yet try this with ATS.

On the other hand, I might try it with Mercury, which seems to be (among other things perhaps) a typed Prolog.

** p.s.

In case the above is a bit downbeat on ATS: I do think ATS is a very interesting language. If any reader can give a quick sketch of one of the simpler types above in ATS, I am definitely up for having a go at the others.

Building and installing ATS on FreeBSD

Wednesday, 30th April, 2014

ATS is a statically typed functional (eager) programming language with dependent types and linear types. It “can be as efficient as C/C++ both time-wise and memory-wise”.

Building and installing on FreeBSD is mostly straightforwardly following the documentation, but three things tripped me up:

GNU make vs BSD make

The Makefiles assume GNU make and won’t run with BSD make. However, on FreeBSD, “make” is BSD make, and GNU make is “gmake”. The way the Makefiles are written (e.g., make is called explicitly from within the Makefiles) seemed to rule out just aliasing gmake as make, so I (as root) hid (BSD) make and symlinked “make” to gmake.

which compiler

By default the Makefiles compile with gcc, although there is an option to compile with clang. My FreeBSD set up had both, with clang as the default compiler (at cc). However, although gcc was installed, it was at “gcc47” and there was no symlink from “gcc”. I added the symlink.


In the install_files sections of the top-level Makefile, the install commands have a space between the -m flag and the actual mode, e.g.:

    105  install_files_1: bin/patscc ; \
    106    $(INSTALL) -T -m 755 $< $(PATSLIBHOME2)/bin/patscc && echo $<

This tripped up install, which reads that 755 as a separate argument. This is fixed by removing the space, i.e.:

    105  install_files_1: bin/patscc ; \
    106    $(INSTALL) -T -m755 $< $(PATSLIBHOME2)/bin/patscc && echo $<

There are five points which need to be changed.

(n.b.: the Makefile may have been updated by the time you read this.)


With all that done, and a “Hello world!” program compiled and run, I am ready to adventure into dependent and linear types!

Review: Beginning Haskell

Saturday, 26th April, 2014

book details

“Beginning Haskell: A Project-Based Approach”
Alejandro Serrano Mena


This book could have been very good: the author has the enthusiasm, the knowledge, and the focus. Unfortunately he has been very very badly let down by his publisher. As it is, the book is almost unbelievably horrible to try and read.

The comments below are based only on the first four chapters, which was as much as I could stomach. The contents of the remainder look interesting, so I may read on, … but I don’t really think I shall.


The book has all the usual dysfluencies, typos, inaccuracies, errors, which we have become used to in programming language publishing, but very thick and fast.

As well as the author, the book boasts a Lead Editor, an Editorial Board (of twenty people), a Coordinating (sic) Editor, a Copy Editor, an Indexer, and a Technical Reviewer (who is so important he warrants a photograph). That’s at least twenty five people “helping” the author. The editing and indexing in the book is so awful, and the accuracy of the technical content so variable, that I can’t imagine what any of them did for their money. The book could hardly have been worse if they’d conspired together to wreck it on purpose.

The index was actually useless. Of the five terms I looked up, *none* were in the index: case, fold, map, monoid, set.

Most pages are cluttered with dysfluent English, grammatical mistakes and typos. These are so thick they make the text quite difficult to read. Each textual error trips up the reader’s eye. It’s like walking along a street when the pavement is covered in dogshit: you can’t enjoy the scenery, you can’t think about where you’re going, all you can do is pick your way through the shit.

Worst are the code-related errors, some of which beggar belief. Code which is not Haskell:

let name = match companyName client of
	       Just n -> n

As far as I know “match” is not a Haskell keyword. The book does not disabuse me of that impression. Neither does ghci.

There’s code that will not compile, or doesn’t do what the text says it does (in one case the code does the exact opposite of what the text claims it does).

Page 58 has a “wonderful” code example which manages not only to be inconsistent with the text, but also inconsistent with itself. It manages to do this in three lines of code!


The text says the code imports filter and reverse; the code actually imports permutations and subsequence; but the code calls (i.e., expects to have been imported) filter and permutations.

Twenty five editors. And the book has a full page dedicated to praising the Technical Reviewer.

All-in-all reading this book was an unpleasant, even nauseating, experience. Because of the book’s good points (see below) I persevered, and worked through many of the exercises.

The last straw was exercise 4-3 (p. 89).

Earlier the book had introduced a data type Client i, where i is a polymorphous type used as an id (p. 49), and where client can be one of three subtypes (Government, Company or Individual). Exercise 4-3 is to write a function that takes a list of Clients and returns a map from these subtypes to sets of clients, or:

classifyClients :: [Client Integer] -> Map ClientKind (Set (Client Integer))

The exercise has two parts, each suggesting an alternative implementation, and then says:

It’s interesting that you create a very large client list and run the two implementations to compare which one behaves better in speed.

Compare how exactly? Later (p. 122), we are told about how to build a cabal project with profiling options that will profile a Main module.

So let’s just forget about comparison for now and write these two functions.

It turns out that Set (Client Integer) will not work:

  *Main> let  cs = S.fromList [Gov 1, Gov 2, Edu 3, Edu 4, Ind 5, Ind 6]

      No instance for (Ord (Client i0))
        arising from a use of `S.fromList'
      Possible fix: add an instance declaration for (Ord (Client i0))
      In the expression: S.fromList [Gov 1, Gov 2, Edu 3, Edu 4, ....]
      In an equation for `cs':
          cs = S.fromList [Gov 1, Gov 2, Edu 3, ....]

Needless to say none of Ord, Set or deriving are in the index, and nothing in the text on Sets indicates that there is a constraint that members of sets must be of type/class Ord. Type classes, including Ord and Eq and deriving, are introduced a bit further on (p. 97). The Client type is defined with just deriving Show (p. 49).

I could have taken this as an extra challenge — interpret those error messages, fix the data type: I did do both those things after all — and in another book I would have. With this book though, I decided it was just more dogshit, and I decided I just didn’t care any more.

What a horrible book.


All of the textual errors I encountered would have been picked up by an averagely competent editor doing their job. Similarly all of the code errors would have been picked up on a first sweep by an editor with a passing acquaintance with programming languages in general.

The bad points of the book, which make it unusable I think, and certainly unrecommendable, are all down to the publisher and the editorial team.

On the other hand, the author has written something which could have been a very good book, and could certainly have been the best practical introduction to Haskell.

The author’s enthusiasm is palpable and infectious. As well as the exercises, I was motivated to try out code from the text (admittedly, often just to see if it was correct Haskell) and some variations of my own. e.g., inspired by a haskell function for 3x + 7(x + 2) (p. 57), I tried one for ax^2 + bx + c:

  dup x = (x,x)
  f *** g = \ (x,y) -> (f x, g y)

  abc a b c = (uncurry (+)) . (((*a) . (^2)) *** ((+c) . (*b))) . dup

  *Main> let f = abc 1 2 3
  *Main> f 5
  *Main> f 10
  *Main> let f = abc 3 1 2
  *Main> f 5
  *Main> f 10

The author is ambitious and wide-ranging — covering parsing, parallelism, DSLs, Idris(!); the GHCi ecosystem including things like GHC extensions, cabal, Hoogle, Haddock, HUnit, and more — but by tieing everything to a concrete project (the usual web app) keeps things focussed, keeps the pace up, and introduces advanced topics in a natural way.


If this book had the appearance of having been edited competently, it could have become the definitive practical introduction to Haskell: the kind of book a programmer could use for self-study, or a technical manager could give to starting team members.

As it is, I would be embarrassed to recommend this to anybody.

The Fibonacci sequence as an unfold

Wednesday, 9th April, 2014

import Data.List

f :: [Integer]
f = unfoldr ( \x -> case x of
                      (0,0) -> Just (0, (1,0))
                      (a,b) -> Just (a+b, (b, a+b)) ) (0,0)


> head f
> take 5 f
> take 15 f

All the info is on this thread:

gpointing-device-settings is a braindead gui from Gnome. Worst of all, it doesn’t remember your settings, so every time you boot up, you have to fiddle about with the gui again.

The post linked to shows how to use xinput to get/set configurations for peripherals, and how to wrap xinput commands in scripts.

A morning with elixir

Saturday, 1st June, 2013

After reading Joe Armstrong’s recent blog post on elixir, and the ensuing discussion there and on twitter, I’ve thought a bit about why I don’t like the language. I can’t spend a week with elixir, so the three observations below are after a morning’s reading and watching.

My overall impression is that elixir is a language that makes it easy for people with a ruby background to dabble with erlang. However, after a morning I’ve found at least three things about elixir that would make my own programming life less pleasant (see below). Elixir contains apparently powerful new features (e.g., macros and protocols), but the examples I’ve seen (e.g. in José Valim’s Erlang Factory talk) are not very exciting.

word-like forms as delimiters

  # elixir
  [1]  def name ( arglist ) do code end

  % erlang
  [2]  name ( arglist ) -> code .

I fail to see how [1] is an improvement on [2]. [2] is shorter by a handful of characters but, mainly, [1] uses word-like forms as delimiters, which I think is a very bad idea.

A human reader will read those word-like forms as words (e.g., the English words “do” and “end”), which they’re not. The delimiters “def”, “do”, and “end” delimit the function definition in the same way that “(” and “)” delimit the argument list.

Using word-like forms as delimiters will either/both (a) slow down the human reader as they read these forms as words, or/and (b) make the code harder to read, as the human reader must explicitly remember not to interpret certain word-like forms as words.

cf also lc and inlist or inbits used to delimit comprehensions.

n.b.: the same arguments apply to erlang’s use of “end” as a delimiter for fun and case blocks. Presumably erlang’s excuse was that they ran out of delimiters borrowed from English punctuation, and they didn’t want to overload “.”. I wonder whether some kind of list delimiter might be appropriate (for case at least), e.g.:

  R = case f() of
        [this -> 1;
         that -> 2],

The pipeline operator |>

The pipeline operator strikes me as being halfway between useful and troublesome. It would probably be very useful in cases similar to the example Joe gives (repeated below for convenience) — where a series of functions each take and produce a single item of data.

  capitalize_atom(X) ->
    V1 = atom_to_list(X),
    V2 = list_to_binary(V1),
    V3 = capitalize_binary(V2),
    V4 = binary_to_list(V3),

  def capitalize_atom(X) do
    X |> atom_to_list
      |> list_to_binary
      |> capitalize_binary 
      |> binary_to_list
      |> binary_to_atom

However, I think if any of the functions in the series take more than one argument, things could quickly get cumbersome. Witness the discussion on Joe’s blog, Joe’s recent tweets suggesting improvements, and the caveat in the elixir documentation.

The simple case above could be done in erlang with a fold:

  capitalize_atom(X) ->
    lists:foldl(fun(F, Acc) -> F(Acc) end, X, 
                [fun atom_to_list/1, 
                 fun list_to_binary/1,
                 fun capitalize_binary/1,
                 fun binary_to_list/1,
                 fun binary_to_atom/1]

Granted, this is possibly even yuckier than Joe’s version, but using a fold or, more generally, writing a function that walks through a list of funs, gives the possibility of handling errors, using some kind of context dictionary as the passed argument, etc.

I think elixir’s “|>” looks more general than it usefully is.


In erlang, variables must begin with a capital letter; atoms need special marking only if they start with a capital letter, or contain certain characters, in which case the atom is enclosed in single quotes. In erlang, module names and function names are atoms.

In elixir, variables don’t seem to need any special marking. Atoms /sometimes/ need to be marked with an initial colon. Unless the atom is a function or module name. Unless the module/function is from the erlang standard library. I might have that wrong.