Futoshiki is a logic/number puzzle. Each row and column must contain all the numbers 1-9 (or whatever the size of the grid); the greater-than signs between some cells dictate that the number in one cell should be greater than its neighbour.

Here’s a question and solution from futoshiki.org:

This can be very simply implemented in clingo. Encoding the rules like this:


cell(R, C) :- number(R), number(C).

% each cell has one number
1 { cell_has_number(R, C, N) : number(N) } 1 :- cell(R, C).

% same numbers may not share row or column
:- cell_has_number(R, C1, N), cell_has_number(R, C2, N), C1 != C2.
:- cell_has_number(R1, C, N), cell_has_number(R2, C, N), R1 != R2.

% greater than constraint
A > B :- greater_than(R1,C1, R2,C2),
         cell_has_number(R1,C1, A),
         cell_has_number(R2,C2, B).

#show cell_has_number/3.

Encode for example the question grid above like this:

#const n = 4.
cell_has_number(4,4, 2).
greater_than(1,2, 1,1).
greater_than(1,2, 1,3).
greater_than(3,3, 2,3).
greater_than(3,1, 4,1).
greater_than(4,2, 4,3).

Run like this (output tidied for readability):

$ clingo futoshiki.lp futoshiki-grid4.lp 0
clingo version 5.5.0
Reading from futoshiki.lp ...
Answer: 1






Models       : 1
Calls        : 1
Time         : 0.003s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.003s

Solving a Logic Puzzle with Clingo

Wednesday, 26th August, 2020

I am working through the exercises in Vladimir Lifschitz’ Answer Set Programming (Springer, 2019). Section 3.2 shows a clingo encoding of one of those logic problems:

Each of four men owns a different species of exotic pet. Here is what we know about them:

We would like to find the full name of the person who owns the jackal.

I thought I would try and encode a similar puzzle from a magazine — a puzzle found in the wild! Logic Problems from Puzzler Media is my favourite and this puzzle was from the May issue (No. 429):

The code:

%%%% Boys in the Hood

%%%% The world.
victim(friar_tuck; little_john; maid_marian; much; will_scarlet).
location(inn; dungeon; lodge; gaol; stocks).
disguise(abbot; shepherd; phantom; prince_john; washerwoman).

%% For each Episode, there is one (V,L,D) combination,
%% and the four variables together make a story.
{ story(E, V, L, D) :
  disguise(D) } = 1 :-

%% Each victim, location and disguise appears in one episode only.
E1 = E2 :- story(E1, V, _, _), story(E2, V, _, _).
E1 = E2 :- story(E1, _, L, _), story(E2, _, L, _).
E1 = E2 :- story(E1, _, _, D), story(E2, _, _, D).

%%%% Clue 1
%% "Prince John" rescued a victim from the dungeon, ...
D = prince_john :-
    story(_, _, dungeon, D).

%% ... this was in the next episode after Little John's appearance.
E2 = E1 + 1 :-
    story(E1, little_john, _, _),
    story(E2, _, dungeon, _).

%%%% Clue 2
%% Friar Tuck was rescued from the inn.
L = inn :-
    story(_, friar_tuck, L, _).

%%%% Clue 3
%% The "washerwoman" appeared in episode 2.
D = washerwoman :-
    story(2, _, _, D).

%%%% Clue 4
%% Much the miller's son appeared in a later episode than the "abbot", ...
E1 < E2 :-
    story(E1, _, _, abbot),
    story(E2, much, _, _).

%% ... but an earlier episode than the rescue from the lodge.
E1 < E2 :-
    story(E1, much, _, _),
    story(E2, _, lodge, _).

%%%% Clue 5
%% The "phantom horseman" rescued Will Scarlet, ...
V = will_scarlet :-
    story(_, V, _, phantom).

%% ... in a later episode than the rescue from the gaol.
E1 < E2 :-
    story(E1, _, gaol, _),
    story(E2, will_scarlet, _, _).

%%%% Clue 6
%% The rescue from the stocks was in episode 3, ...
L = stocks :-
    story(3, _, L, _).

%% ... and did not feature Will Scarlet.
:- story(3, will_scarlet, _, _).

%%%% Clue 7
%% The "shepherd" was the rescuer in the episode before Maid Marian's.
E2 = E1 + 1 :-
    story(E1, _, _, shepherd),
    story(E2, maid_marian, _, _).

%% Maid Marian was not the victim in episode 2.
:- story(2, maid_marian, _, _).

#show story/4.

(… and in a gist.)

After describing the four sets, the first constraint involves a set comprehension, or "choice rule" in ASP parlance:

{ story(E, V, L, D) :
  disguise(D) } = 1 :-

The form { p(X, Y) : q(X), r(Y) } describes a set — the set of facts p(X, Y) where q(X), r(Y) is true.

The form { ... } = n asserts that the cardinality of the set described is n.

Perhaps betraying my Prolog background, I initially tried to write things like (for Clue 2) …

story(_, friar_tuck, inn, _).

… which wouldn’t compile (unsafe anonymous variables), or …

story(E, friar_tuck, inn, D) :-

… which didn’t work. Thinking of the clues as constraints rather than facts or predicates was the breakthrough, and the correct (or, at least, working) version, is concise and elegant:

L = inn :-
    story(_, friar_tuck, L, _).

A fun little exercise on "real world" but still relatively tame data. Recommended!

To any Answer Set Programming experts reading: how could this program be improved?

A crossword clue is like a little program

Sunday, 9th February, 2020

Masterpieces from cooks badly overdue (5-7)

masterpieces (from)
"cooks"         : "chefs", synonym of "cooks"
badly "overdue" : jumble letters of "overdue" => "doeuvre"
=> "chefsdoeuvre"

Cook once stuffing spring chickens in here (3,4)

cook "once" : jumble letters of "once"    => "enco"
stuffing    : insert previous into following
"spring"    : "hop", synonym of "spring"  => "h enco op"
-: chickens in here
=> "hencoop"

Hot Finnish sauna ultimately designed to inspire love (2,7)

hot :-
"finnish"          :                             => "finnish"
"sauna" ultimately : last letter of "sauna"      => "s"
designed           : jumble previous             => "infashin"
to inspire         : insert following into previous
"love"             : "o"  # 0, synonym of "love" => "infashi o n"
=> "infashion"

As the programming language and the data to be processed are both English, much of the challenge is deciding which words are data and which code.

A word can represent an instruction (a transformation or function), itself (“raw data”) or a synonym of itself (a zero-argument function). Synonyms do not respect part of speech.

Any word can play any role in any clue. “Hot” is a good candidate for a jumble instruction; “cook” often stands for itself or its synonyms (e.g. “chef”).

(All clues are from recent FT crosswords.)

内观不识因无相 / 外合明知作有形

Thursday, 2nd January, 2020

This couplet from a “testimonial poem” about the Monkey King from Journey to the West struck me:


nèi guān bù shí yīn wū xiàng,
wài hé míng zhī zuò yǒu xíng.

Anthony Yu’s translation is:

Formless inside he yields no image known;
His outward guise coheres in action shown.

A clunky but more literal gloss might be:

The inside view [内观] is not known [不识] because [因] it is without appearance [无相],

The outside whole [外合] is clearly known [明知] through its tangible [有形] work [作].

The couplet is an antithetical couplet with the two lines having exactly the same pattern and contrasting meanings:

内观 不识 无相
nèi guān bù shí yīn wū xiàng
Inside view not know because without appearance
外合 明知 有形
wài hé míng zhī zuò yǒu xíng
outside whole clear know work has form

内观 (nèi guān, “inside view”) is translated by Google (but not by Bing) as “Vipassana”, “one of two qualities of mind which is developed in Buddhist meditation” (according to Wikipedia). See this footnote in the Wikipedia page. There is also a branded form of yoga called “内观流” (Inside Flow) [https://insideflow.yoga/].

Using PropEr with erlang.mk

Sunday, 7th July, 2019

I have started working through Fred Hebert’s excellent Property-Based Testing with PropEr, Erlang, and Elixir (old but free version here). (n.b., PropEr’s own website is here). I plan to add property-based tests to my LIGA project.

Chapter 1 shows how to call PropEr from rebar3 (amd mix for Elixir). However, I prefer erlang.mk for my own projects, so here is a brief note on calling PropEr from erlang.mk.

*** howto

First, add PropEr as a test dependency to your Makefile:

TEST_DEPS = proper

Then …

$ make proper

… will run all the prop_*.erl files in test/

*** book example

For a quick look at usage & output I copied the book’s prop_base.erl into LIGA’s test/ directory.

First, using the failing version of prop_base.erl on p. 25:

$ make proper
GEN test-dir
GEN test-build
GEN proper
Testing prop_base:prop_biggest/0
Failed: After 2 test(s).
An exception was raised: error:function_clause.
Stacktrace: [{prop_base,biggest,[[]],[{file,"test/prop_base.erl"},{line,22}]},

Shrinking (0 time(s))
erlang.mk:6880: recipe for target 'proper' failed
make: *** [proper] Error 1

Second, using the succeeding version of prop_base.erl on p. 27:

$ make proper
GEN test-dir
GEN test-build
GEN proper
Testing prop_base:prop_biggest/0
OK: Passed 100 test(s).

*** next steps

  1. create generators for LIGA data types
  2. create properties for LIGA functions
  3. get them working, make them beautiful, …

Dialyzing legacy code

Wednesday, 3rd July, 2019

** Introduction

Typespecs are handy documentation for erlang functions, but they really come to life when used with Dialyzer []. Dialyzer analyzes a codebase and checks that functions behave according to their typespec. This post runs quickly through using dialyzer on an existing codebase, my own LIGA project.

** Preparation

First, build a PLT (Persistent Lookup Table) for the project. Include a list of erlang apps the project uses, and provide a project-specific location:

$ dialyzer --build_plt --apps kernel stdlib erts eunit --output_plt .liga.plt
  Compiling some key modules to native code... done in 0m25.63s
  Creating PLT .liga.plt ...
Unknown functions:
Unknown types:
 done in 0m24.01s
done (passed successfully)

This will output a dialyzer PLT in a newly-created local file .liga.plt.

More applications can be added after building:

$ dialyzer --add_to_plt --apps compiler crypto --plt .liga.plt

It is possible to run Dialyzer over a whole codebase in one sweep. The simplest way is to give dialyzer a list of directories to analyse, e.g.:

$ dialyzer -r src/ test/ --src

The --src flag tells dialyzer to find and check .erl files (default is to check compiled .beam files).

Build tools like erlang.mk have wrappers too, e.g.:

$ make dialyze

When dialyzing a legacy codebase, the above is likely to produce a lot of warnings, so going module-by-module might be more manageable. Here is a simple workflow:

  1. $ dialyzer src/liga_intmap.erl
  2. [… edit liga_intmap.erl as desired …]
  3. $ make
  4. $ dialyzer --add_to_plt -c ebin/liga_intmap.beam --plt .liga.plt

The last step adds the functions in the module to the PLT. Once the whole codebase has been done for the first time, future checks in batch mode (i.e., after changes to the code) should return with few or no warnings.

When dialyzing a codebase module-by-module, we check each module, make any desired changes, then recompile the code and add the module’s beam file (along with any other updated beam files) to the project’s PLT. Dialyzer will issue warnings for any “unkown functions” (i.e., functions in modules it doesn’t know about). To avoid as many of these as possible, we go through the modules working up the dependency tree, starting at leaf modules (without dependencies).

Grapherl can render a dependency tree of erlang modules as a .png file, e.g.:

$ grapherl -m ebin/ liga.png

LIGA module dependency graph

Here are some example warnings I got when dialyzing LIGA.


$ dialyzer src/liga_labmap.erl
  Checking whether the PLT .liga.plt is up-to-date... yes
  Proceeding with analysis...
liga_labmap.erl:77: The pattern  can never match the type 
 done in 0m0.14s
done (warnings were emitted)

Dialyzer doesn’t see macros (including records). As the line defining ?VERSION as original is commented out, the clause of versioned_weights/3 that matches it appears to be superfluous.


$ dialyzer src/data_server.erl
  Checking whether the PLT .liga.plt is up-to-date... yes
  Proceeding with analysis...
data_server.erl:82: The created fun has no local return
data_server.erl:83: The call data_server:get_with_complement(Lab::any(),Ra::any(),{'nm',_},0) breaks the contract (atom(),any(),pcage(),non_neg_integer() | 'all') -&gt; {[labelled_string()],[labelled_string()]}
 done in 0m0.22s
done (warnings were emitted)

“no local return”
– this can mean that the specified function never returns, in which case the typespec can mark the function’s return type as no_return(). It can also (perhaps more often) mean that dialyzer itself crashed while checking the function. In my experience the next warning gives a clue to the cause of the crash.

“breaks the contract”
– there is a mismatch between type expectations between calling function and function being called. The error might just be in the typespec annotations — or two parts of the codebase might have gotten out of sync. In either case tis is important to resolve.


This warning is from erlang.mk’s ‘make dialyze’.

liga_writer.erl:18: Expression produces a value of type 'true' | {'error','bad_directory'}, but this value is unmatched

The line in question is:


Where the code is using a stdlib function for its side-effects rather than for its return value. The function does return a value though, and the code would be safer and clearer if the expected value was matched:

    true = code:add_path("."),

** Conclusion

Dialyzer is quite simple to use, and helps improve the coherence and clarity of a codebase. As well as the documentation, the Dialyzer chapter of Learn You Some Erlang is worth a read.

Euterpea: setting up audio on linux

Saturday, 3rd November, 2018

Euterpea requires ALSA:

$ apt-get install libasound2-dev

How to install Euterpea & HSoM, repeated from the Euterpea website:

Install the Haskell Platform from https://www.haskell.org/platform/, then:

$ cabal update
$ cabal install Euterpea
$ cabal install HSoM

Audio might work out of the box:

$ gchi
GHCi, version 8.4.3: http://www.haskell.org/ghc/  :? for help
Prelude> import Euterpea
Prelude Euterpea> play $ c 4 qn
Prelude Euterpea> devices  --  Lists audio devices available.

Input devices: 
  InputDeviceID 1       Midi Through Port-0

Output devices: 
  OutputDeviceID 0      Midi Through Port-0

Prelude Euterpea> playDev 0 $ c 4 qn

If either play or playDev (play to device) actually play a middle C out of your speakers, you are done. Hooray!

Otherwise, …

The Euterpea site links to Ted’s Linux MIDI Guide which gave me all the information I needed to set things up. It’s a very interesting article which I encourage you to read. I repeat the bare necessities below for convenience.

Ted provides this script which runs the software synthesizer (or “softsynth”) FluidSynth (so that, e.g., MIDI files can be converted to audio) and the sound server JACK (so that audio applications can communicate with each other).


$ apt-get install fluidsynth jackd2

You’ll have to logout and login again after installing JACK.

The script:


# Script to launch audio servers for music-making.

case $1 in

  start )
    echo Starting JACK...

    # Start JACK
    # As of Ubuntu 12.10, a period of 128 is needed for good fluidsynth
    # timing.  (jackd 1.9.9, fluidsynth 1.1.5)
    # If you aren't running pulseaudio, you can remove the pasuspender line.
    pasuspender -- \
      jackd -d alsa --device hw:0 --rate 44100 --period 128 \
        &>/tmp/jackd.out &

    sleep .5

    echo Starting fluidsynth...

    # Start fluidsynth
    fluidsynth --server --no-shell --audio-driver=jack \
               --connect-jack-outputs --reverb=0 --chorus=0 --gain=0.8 \
               /usr/share/sounds/sf2/FluidR3_GM.sf2 \
               &>/tmp/fluidsynth.out &

    sleep 1

    if pgrep -l jackd && pgrep -l fluidsynth
        echo Audio servers running.
        echo There was a problem starting the audio servers.


  stop )
    killall fluidsynth
    killall jackd
    echo Audio servers stopped.

  * )
    echo Please specify start or stop...


You can call it “audio”, keep it in ~/bin, and use `audio start` and `audio stop` to start and stop the apps.

So now this should work:

$ audio start
$ gchi
GHCi, version 8.4.3: http://www.haskell.org/ghc/  :? for help
Prelude> import Euterpea
Prelude Euterpea> devices

Input devices: 
  InputDeviceID 1       Midi Through Port-0

Output devices: 
  OutputDeviceID 0      Midi Through Port-0
  OutputDeviceID 2      Synth input port (4424:0)
Prelude Euterpea> playDev 2 $ c 4 qn

Functions in Elixir

Sunday, 8th November, 2015

** defined functions

Functions are defined within a module.

Note that definition syntax and usage behaviour is slightly different depending on whether the function has a single argument or several arguments. For example, a space between function name and arguments is acceptable for a single-argument function, but is a syntax error with a multi-argument function:

def clown2a(x) do 5 * x end  # ok

def clown2b (x) do 5 * x end  # ok

def clown2b x do 5 * x end  # ok

def clown3a(x,y) do x + y end  # ok

def clown3b (x,y) do x + y end  # syntax error

def clown3c x,y   do x + y end  # ok

Similarly when using functions:

iex(1)> Drop.clown2a(5)

iex(2)> Drop.clown2a (5)

iex(3)> Drop.clown3a(5,6)

iex(4)> Drop.clown3a (5,6)
** (SyntaxError) iex:81: unexpected parentheses. If you are making
a function call, do not insert spaces between the function name
and the opening parentheses. Syntax error before: '('

There is also an optional short form of function definition which uses the construction “, do:” instead of “do” and omits “end”. This form can be used if the function body fits on one line, e.g.:

[7]  def clown4b(x,y), do: x + y 

[8]  def clown4b(x,y), do:
         x + y

Note that this short form is much stricter about spaces and brackets, but does still allow some creativity and individualism for the programmer:

def clown4d (x,y), do:  x + y  
# syntax error - space after function name

def clown4e x,y,   do:  x + y  
# syntax error - no brackets round arguments

def clown4c(x,y),  do:x + y    
# syntax error - no space after "do:"

def clown4h(x,y) , do : x + y  
# syntax error - space between "do" and ":"

def clown4f(x,y) , do:  x + y  # ok - space around ","

def clown4g(x,y)  ,do:  x + y  # ok - no space after ","

Functions defined above are available in this gist. They are based on code from the O’Reilly book “Introducing Elixir”.

** anonymous functions

In the shell only anonmyous functions can be used, e.g. bound to a variable.

Anonymous functions seem to behave similarly in the shell and in modules.

Anonymous functions do not behave quite the same as “defined” functions.

*** remember the extra dot

When using a bound anonymous function you must add an extra dot between the function name and its arguments:

 iex(1)> ad5 = fn(x) -> 5+x end
 iex(2)> ad5(9)
 ** (CompileError) iex:94: undefined function ad5/1 

 iex(3)> ad5.(9)

*** optional spaces almost everywhere, almost like defined functions

As with defined functions, there are lots of options for adding whitespace — but not quite the same options:

**** one parameter

 iex(4)> a5b = fn (x) -> 5+x end
 iex(5)> a5b.(9)
 iex(6)> a5b. (9)
 iex(7)> a5b. 9
 ** (SyntaxError) iex:7: syntax error before: 9

 # cf:
 iex(8)> :math.sqrt(9)
 iex(9)> :math.sqrt (9)
 iex(10)> :math.sqrt 9

*** two parameters

 iex(11)> sma = fn(x,y) -> x+y end
 iex(12)> smb = fn (x,y) -> x+y end
 iex(13)> smc = fn x,y -> x+y end
 iex(14)> smc.(4,5)
 iex(15)> smc. (4,5)
 iex(16)> smc. 4,5
 ** (SyntaxError) iex:14: syntax error before: 4

cf similar defined functions in a module:

defmodule Clown do

  def clown3a(x,y)  do IO.puts(x+y) end
# def clown3b (x,y) do IO.puts(x+y) end  # syntax error
  def clown3c x,y   do IO.puts(x+y) end


Running this module:

 iex(17)> Drop.clown3a(5,6)
 iex(18)> Drop.clown3a (5,6)
 ** (SyntaxError) iex:81: unexpected parentheses. If you are making a
 function call, do not insert spaces between the function name and
 the opening parentheses. Syntax error before: '('
 iex(19)> Drop.clown3a 5,6

Command #15 is ok but command #18 is a syntax error;
Command #16 is a syntax error but command #19 is ok.

*** short version

There is also a short version of the anonymous function, in which the arity is implicit:

 iex(20)> clownx = &amp;(&amp;1 + &amp;2)
 iex(21)> clownx. (4,5)
 iex(22)> clownx. (4,5,6)
 ** (BadArityError) &amp;:erlang.+/2 with arity 2 called with 3 arguments (4, 5, 6)
 iex(23)> clowny = &amp;(&amp;1 + &amp;3)
 ** (CompileError) iex:3: capture &amp;3 cannot be defined without &amp;2
     (elixir) src/elixir_fn.erl:123: :elixir_fn.validate/4
     (elixir) src/elixir_fn.erl:112: :elixir_fn.do_capture/4

The module compiler does do some of this checking. In the module below, the commented-out function c1a would be blocked by the compiler, but function c1b will not be. At runtime, the running process will crash when it reaches line 10.

 defmodule Anon do
 #  def c1a(x,y,z) do
 #   f = &amp;(&amp;1 + &amp;3)  # syntax error blocked by compiler
 #   f. (x,y,z)
 #  end
   def c1b(x,y,z) do
    f = &amp;(&amp;1 + &amp;2)
    f. (x,y,z)

For example:

 iex(24)> c("anon.ex")
 iex(25)> Anon.c1b(2,3,4)
 ** (BadArityError) &amp;:erlang.+/2 with arity 2 called with 3 arguments (2, 3, 4)
     anon.ex:10: Anon.c1b/3

Erlang and SMTP: a quick round-up

Sunday, 18th October, 2015

[update 20151022: added selectel/pat]

There seem to be three live projects for using SMTP from erlang:

  • Richard Carlsson’s sendmail
  • the smtp module in Yaws
  • Vagabond’s gen_smtp
  • Selectel’s pat

** Richard Carlsson’s sendmail


This is a simple-but-useful wrapper round sendmail. Consequently, it depends on the host OS having sendmail up & running. Also consequently, it can take advantage of sendmail’s other features (e.g., retrying failed sends). As Richard explained on erlang-questions in 2011:

Often, what you want is more than just SMTP. If there are some network
issues (or your mail server is simply down) at the time your program
tries to send the mail, you usually want your program to still be able
to regard the mail as sent and carry on. This means that the mail needs
to be persistently stored on disk in a spool area and that the MTA
regularly tries to send any outgoing mail that’s been spooled, so it
will eventually be on its way once the problem is resolved. That’s why
we like to rely on sendmail instead. But it all depends on the needs of
your application.

Note: although this is a single script, it is a git repo in its own right, so it can be added as a dependency.

However, as it’s a single-script it doesn’t have anything fancy like a Makefile. I’ve created a fork with a Makefile so I can have it in my erlang.mk Makefile as a dependency: https://github.com/llaisdy/sendmail.

** the smtp module in Yaws


This is a single-script smtp client for sending emails. It does not depend on (or use) sendmail.

It seems that, to add this as a dependency to a project, it would be necessary to either add Yaws itself as a dependency, or manually copy the smtp.erl script into your own project.

** Vagabond’s gen_smtp


This is the full Monty: “a generic Erlang SMTP server framework that can be extended via callback modules in the OTP style. A pure Erlang SMTP client is also included.”

** Selectel’s pat


This connects to a downstream SMTP server to send email messages. An email message is represented by an erlang record.

Draggable-Droppable Sortable List

Friday, 18th September, 2015

Here is a demo showing Rubaxa’s Sortable used with React.

The demo is based on a trimmed down version of the React example on the Sortable github page. The extras are:

  • the list items are React classes rather than text;
  • handleEnd shows accessing re-arranged list items on drop;
  • list items have a handle, which means their contents can be assessed and manipulated.

n.b.: in the gist below, the javascript file uses JSX markup so it’ll need to be compiled (e.g. with React’s cli tools or babel).

[github gist]

I like Rubaxa’s Sortable because it (a) works! (b) does not require any silly javascript package managers.