leah blogs

A few months ago I found an article on how to organize your training plan using logic programming, which used Haskell to implement a logic language.

At first, I thought this is a good problem to solve in Prolog, but there’s a difficulty: Prolog makes it quite hard to specify models that have multiple possible outcomes (yes, you can work with backtracking, but it gets tricky when you start to combine multiple predicates or fiddle around with bagof).

An alternative to classic Prolog is the concept of Answer Set Programming, based on the Stable Model Semantics by Gelfond and Lifschitz (1988). Here, the idea is that the logical formulas specify models, and the goal of Answer Set Programming is to compute the Answer Sets, i.e. a set of models fulfilling the formulas.

I can’t do a full introduction to Answer Set Programming here, but I can recommend the overview article Answer set programming at a glance by Brewka et. al., as well as the short article What Is Answer Set Programming? and the book Answer Set Programming by Lifschitz.

So what is a stable model?

Essentially, we can think of a stable model as a maximal set of atoms that are true (derivable from the rules) without being in conflict to other propositions. If we don’t use negation, that pretty boring

However, consider this logic program:

q :- not p.
p :- not q.

Contrary to what you may expect, it has two models: {p} and {q}. This is because ASP uses default negation, which means “not A” is assumed to hold unless A is derived. Both cannot be true at the same time, but likewise the empty set is not a model because it can be extended to {p} or {q}.

The program p :- not not p. has two models, {} and {p}.

Let’s do a small problem first so we get a feel for the tooling. I chose to use clingo, which is the most advanced open source implementation of Answer Set Programming.

If your distribution doesn’t include it, you can run it from Nix:

nix shell nixpkgs#clingo

Let’s model a directed graph with four nodes:

edge(a,b).
edge(a,c).
edge(b,d).
edge(c,d).

Our problem is to find paths from a to d. We can define a relation step, which either means “we can step from X to d” or “we can step from X to Y when there’s an edge from X to Y and another step from Y”:

0 { step(X,E) } 1 :- edge(X,E), E = d.
0 { step(X,Y) } 1 :- edge(X,Y), step(Y,_).

The 0 { ... } 1 decoration means that each step can be taken at most once.

Finally, we need to specify our goal, which in tradition of logic programming, is written as a negation:

:- not step(a,_).
#show step/2.

This means “it is not the case that there’s no step starting from a”.

The #show instructions limits clingo to only output the binary step relation. Let’s run it:

% gringo graph.pl | clasp    
clasp version 3.3.10
Reading from stdin
Solving...
Answer: 1
step(b,d) step(a,b)
SATISFIABLE

Models       : 1+
Calls        : 1
Time         : 0.001s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

Clingo has found a solution. We can go from a to b and from b to d.

We can also ask for all solutions, by passing -n0:

% gringo graph.pl | clasp -n0
clasp version 3.3.10
Reading from stdin
Solving...
Answer: 1
step(b,d) step(a,b)
Answer: 2
step(c,d) step(b,d) step(a,b)
Answer: 3
step(c,d) step(a,c)
Answer: 4
step(c,d) step(b,d) step(a,c)
Answer: 5
step(c,d) step(b,d) step(a,b) step(a,c)
SATISFIABLE

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

Here we see there are five possible models of this system (but every model except the first and the third has superflous steps).

To see why the 0 { ... } 1 matters, here’s what happens without it:

Answer: 1
step(b,d) step(c,d) step(a,b) step(a,c)
SATISFIABLE

Now there is only one model, but it contains all paths. Cardinality bounds are implemented using negation internally.

Planning Weekly Workouts in 30 lines of ASP

Back to the original task: Planning Weekly Workouts in 100 lines of Haskell.

The goal is to create a weekly plan of training exercises according to some specific rules.

First, we need some definitions related to weekdays:

weekday(1..7).

n_weekday(D, DD)  :- weekday(D), weekday(DD), (D+1) \ 7 == DD \ 7.
nn_weekday(D, DD) :- weekday(D), weekday(DD), (D+2) \ 7 == DD \ 7.

two_weekday(D, DD) :- n_weekday(D, DD).
two_weekday(D, DD) :- nn_weekday(D, DD).
two_weekday(D, DD) :- two_weekday(DD, D).

This is a bit more complicated because we later need “day after” and “within two days”. (\ means modulo.)

Now, let’s define workout and running exercises:

workout(push; pull; leg; none).
running(long; short; none).

To the plan: each weekday has one workout and one running exercise:

{ plan(D,W,R) : workout(W), running(R) } = 1 :- weekday(D).

We then add the constraints:

% No running on leg day
plan(D, leg, none) :- plan(D, leg, _).

% Short intervals run is after an outdoor pull/push workout
:- plan(_, none, short).

% Workout on Monday outdoors always, not legs
:- plan(1, none, _).
:- plan(1, leg, _).

% Pull day during the week?
:- plan(6..7, pull, _).

% One long run, one short run
{ plan(D,W,long) : weekday(D), workout(W) } = 1.
{ plan(D,W,short) : weekday(D), workout(W) } = 1.

% Two push, two pull, two leg
:- not { plan(D,push,R) } = 2.
:- not { plan(D,pull,R) } = 2.
:- not { plan(D,leg,R) } = 2.

% Long run on weekend
{ plan(6..7,W,long) : workout(W) } = 1.

% Run spaced out at least 2 days
:- plan(D,_,short), plan(DD,_,long), two_weekday(D, DD).

% Space out workouts at least 2 days
:- plan(D,W,_), plan(DD,W,_), W != none, two_weekday(D, DD).

% No leg day before short run
% No leg day before a long run
{ plan(D,W,R) : running(R), R != none, workout(W), plan(DD,leg,_), n_weekday(D, DD) } = 1.

#show plan/3.

clingo generates the same three plans as the Haskell program:

Solving...
Answer: 1
plan(5,leg,none) plan(2,leg,none) plan(1,pull,none) plan(3,push,none) plan(4,pull,short) plan(6,push,none) plan(7,none,long)
Answer: 2
plan(5,leg,none) plan(2,leg,none) plan(1,pull,none) plan(3,push,none) plan(4,pull,short) plan(6,none,none) plan(7,push,long)
Answer: 3
plan(7,leg,none) plan(4,leg,none) plan(1,pull,none) plan(2,push,short) plan(3,none,none) plan(5,pull,none) plan(6,push,long)
SATISFIABLE

Answer Set Programming against heteronormativity

The next problem I solved using ASP was a silly exercise from a statistics book (Lehn, Wegmann, Rettig: Aufgabensammlung zur Einführung in die Statistik), translation mine:

Exercise 11c) Ten French married couples bid goodbye to each other: the men with the men by shaking hands, the women with the women by kisses on both cheeks, and women with the men likewise by kisses on both cheeks. How many kisses and how many handshakes take place?

The implicit assumption of the exercise is that all married couples consist of a man and a woman, but it’s more fun to solve it in a generic way. So let’s do that using ASP.

First, we model the people and their fixed binary gender (more assumptions, but else the exercise is truly underspecified):

person(0..19).
gender(man; woman).
{ gender(P, G) : gender(G) } = 1 :- person(P).

I decided to model a couple using an even and odd numbered person:

couple(A, B) :- person(A), person(B), A != B, A/2 == B/2.

Next, we model the handshakes. Two people shake hands if they are not part of the same couple, and both are men:

handshake(A, B) :- person(A), person(B), A < B, not couple(A, B), gender(A, man), gender(B, man).

The A < B ensures we only count one handshake between two men, as handshaking is a symmetric act.

We also count the handshakes:

handshakes(N) :- N = #count { handshakes(A, B) : handshake(A, B) }.

Likewise, two kisses happen between two persons not in the same couple where one is a woman. Note that kisses are asymmetric since they go from mouth to cheek (this cost me an hour of debugging…):

kiss(A, B) :- person(A), person(B), not A == B, not couple(A, B), gender(A, woman).
kiss(A, B) :- person(A), person(B), not A == B, not couple(A, B), gender(B, woman).
kisses(N) :- H = #count { kisses(A, B) : kiss(A, B) }, N = H * 2.

Finally, we also count men and women for reporting purposes:

men(N) :- N = #count { g(P) : gender(P, man) }.
women(N) :- N = #count { g(P) : gender(P, woman) }.

#show handshakes/1.
#show kisses/1.
#show men/1.
#show women/1.

Thanks to clingo’s parallelization support, we can compute all possible 2²⁰ solutions very quickly:

Solving...
Answer: 1
women(0) men(20) kisses(0) handshakes(180)
Answer: 2
women(1) men(19) kisses(72) handshakes(162)
Answer: 3
women(1) men(19) kisses(72) handshakes(162)
...
Answer: 1048576
women(12) men(8) kisses(616) handshakes(26)
SATISFIABLE

Models       : 1048576
Calls        : 1
Time         : 51.163s (Solving: 51.00s 1st Model: 0.10s Unsat: 0.01s)
CPU Time     : 463.811s
Threads      : 16       (Winner: 0)

We can also specialize the model to have only hetero couples:

:- Z = 0..9, not gender(2*Z, man).
:- Z = 0..9, not gender(2*Z+1, woman).

Then we get the unique solution:

Solving...
Answer: 1
women(10) men(10) kisses(540) handshakes(45)
SATISFIABLE

I hope this post could interest you in how Answer Set Programming can be used. Some more interesting programs can be found on Hakan Kjellerstrand’s blog.

Thanks to the xz backdoor, many people are now talking about the state of Linux packaging tools, and in particular build systems. As a maintainer of Void Linux and packager of many things, I have my five cents to add, so today I’ll be the contrarian and argue what autoconf got right. This is not an apology for GNU autotools; we are all well familiar with the issues they bring—yet some prospective replacements manage to be worse in certain aspects.

It provides a standardized interface.

This is of course the hardest point to tackle for any new contestor that has not reached a critical mass.

In Void Linux, the GNU configure build style is the most popular; roughly 2250 of about 14300 package template use it, and an additional 120 use the generic configure build style, which works similarily.

As a packager, the worst thing is to find a custom made build system that behaves totally different from what we know—if you decide to write your own ./configure scripts, please stick to the conventions! We packagers really have better things to do than figure out yet another homebrew build system that’s used exactly once.

These conventions are standardized as part of the GNU Coding Standards and they specify many features that packagers expect, but developers without own packaging experience are likely to miss. One example is support for staged installation, i.e. DESTDIR. This is essential for building packages that only contain the files that package actually ships. And no, support for --prefix is not enough to make up for this (if you wonder why, please read up the standards).

It is based on checking features.

People who have been staring at ./configure output for too long may want to disagree, but let me make my point: check-based configuration is the only way to write software that will continue to work properly in the future. If you instead keep a table of broken systems and workarounds, it a) will not be updated for future systems, b) doesn’t detect if the system was actually fixed (either by patching a bug, or adding a missing feature). It’s also very unlikely the software builds on an system unknown to the build system, even if it’s standards-compliant otherwise.

Of course, the checks should be reasonable (and in practice, often are excessive). If your code assumes a C99 environment, you don’t need to check whether all C99 functions you use are available. Likewise, if you don’t need macros for certain sizeof values, you don’t need to check for them, either. And you never need to check if sizeof char is actually 1—it literally can’t be anything else. Also, checking for functions can be done incorrectly.

Overrides are possible.

While checks are good, sometimes they are broken or a certain configuration needs special override, because a feature can’t be checked (for example, when cross-compiling). In this case, autoconf scripts provide options to override checks with a predetermined result; usually you can set an environment variable like gt_cv_func_printf_posix=yes.

Likewise, if a library is installed at a special location, it’s also easy to tell configure to use it.

The config.log tells what happened.

Many other systems do checks, but only tell that something has failed. Debugging this can be difficult. Autoconf writes what it does into a config.log file, which is sometimes helpful to debug a check.

There is support for cross-compiling and for host/target separation.

Cross-compilation is a build system feature that is often put in second place, but as a maintainer of a system that heavily makes use of it, I have a fair share of experience and can say that autotools are one of the best systems to support cross-compilation. Especially custom-made build systems are often very lacking. Cross-compilation of C programs is not particularly hard in principle, but your build system needs to know which code is going to run on the target, and that programs which need to run during compilation (e.g. to precompute tables or something) need to be compiled for the host (with different CFLAGS and so on).

It has few runtime dependencies.

This is also a defining feature of autoconf, as usually a basic POSIX shell environment (or, say, something busybox) is enough to run the configure scripts. This is in particular important for packages needed for bootstrapping. If your build system needs Python, well, then you need to compile Python first; but to compile Python, you need to compile all of its dependencies, which hopefully don’t need Python then themselves to build…

However, for packages not directly relevant to bootstrapping a system this is not such an essential feature.

NP: Policy of 3—Let It Build

It is well known that a Scheme function definition is merely defining a lambda function to a variable:

(define (hypot a b)
  (sqrt (+ (* a a) (* b b))))

This function could be written just as well:

(define hypot
  (lambda (a b)
    (sqrt (+ (* a a) (* b b)))))

Occasionally, we need this explicit style when a function needs to keep around some internal state:

(define generate-id
  (let ((i 0))
    (lambda ()
      (set! i (+ i 1))
      i)))

(generate-id) ;=> 1
(generate-id) ;=> 2
(generate-id) ;=> 3

A problem arises when we need multiple functions to share the state, let’s say we also want a reset-id function:

(define i 0)

(define (generate-id)
  (set! i (+ i 1))
  i)

(define (reset-id)
  (set! i 0))

(generate-id) ;=> 1
(generate-id) ;=> 2
(generate-id) ;=> 3
(reset-id)
(generate-id) ;=> 1
(generate-id) ;=> 2

Here, I had to make i a global variable to allow two toplevel functions to access it. This is ugly, of course. When you did deeper into the scheme specs, you may find define-values, which lets us write:

(define-values (generate-id reset-id)
  (let ((i 0))
    (values
      (lambda ()
        (set! i (+ i 1))
        i)
      (lambda ()
        (set! i 0)))))

This hides i successfully from the outer world, but at what cost. The programming language Standard ML has a nice feature to write this idiomatically, namely local:

local
    val i = ref 0
in
    fun generate_id() = (i := !i + 1; !i)
    fun reset_id() = i := 0
end

Here, the binding of i is not visible to the outer world as well. It would be nice to have this in Scheme too, I thought. Racket provides it, but the implementation is quite hairy. Since I mostly use Gerbil Scheme these days, I thought perhaps I can reuse the module system. In Gerbil, we could also write:

(module ids
  (export generate-id reset-id)
  (def i 0)
  (def (generate-id)
    (set! i (+ i 1))
    i)
  (def (reset-id)
    (set! i 0)))

It is used like this:

(import ids)
(generate-id) ;=> 1
(generate-id) ;=> 2
(generate-id) ;=> 3
(reset-id)
(generate-id) ;=> 1
(generate-id) ;=> 2

So, let’s use the module system of Gerbil (which supports nested modules) to implement local. As a first step, we need to write a macro to define a new module and immediately import it. Since all Gerbil modules need to have a name, we’ll make up new names using gensym:

(import :std/sugar)
(defrule (local-module body ...)
  (with-id ((mod (gensym 'mod)))
    (begin
      (module mod
        body ...)
      (import mod))))

Here, we use the with-id macro to transform mod into a freshly generated symbol. defrule is just a shortcut for regular Scheme syntax-rules, which guarantees a hygienic macro. We can use the identifier mod inside the body without problems:

> (local-module (export mod) (def (mod) 42))
> (mod)
42
> mod
#<procedure #27 mod378#mod>

The internal representation of the function shows us it was defined in a generated module. Re-running local-module verifies that fresh modules are generated.

Now to the second step. We want a macro that takes local bindings and a body and only exports the definitions of the body. Using the Gerbil export modifier except-out, we can export everything but the local bindings; this is good enough for us.

Thanks to the power of syntax-rules, this is now straight forward to state:

(defrule (local ((var val) ...) body ...)
  (local-module
    (export (except-out #t var ...))
    (def var val) ...
    body ...))

We rewrite all let-style binding pairs into definitions as well, but we make sure not to export their names.

Now, we can write our running example like this:

(local ((i 0))
  (def (generate-id)
    (set! i (+ i 1))
    i)
  (def (reset-id)
    (set! i 0)))

(generate-id) ;=> 1
(generate-id) ;=> 2
(generate-id) ;=> 3
(reset-id)
(generate-id) ;=> 1
(generate-id) ;=> 2

But perhaps you prefer the slightly less magical way of using modules directly (which is also what many recommend to do in Standard ML). Still, creating modules by macros for fine-grained scoping is a good trick to have up your sleeve.

[Addendum 2024-01-28:] Drew Crampsie showed me another trick with nested modules that will help improve the local macro: when you import a module into another, the bindings are not re-exported by (export #t) (which means “export all defined identifiers”). (You can use (export (import: module)) if you really wanted this.) This means we don’t need the except-out trick, but we can just use two nested modules instead:

(defrule (local ((var val) ...) body ...)
  (local-module
    (local-module
      (export #t)
      (def var val) ...)
   (export #t)
   body ...))

The inner module contains all the local bindings, the outer one the visible bindings made in the body. Now, definitions in the body can also shadow local bindings (not that this is very useful):

(local ((var 5))
  (def (get)
    var)
  (def var 6))

(get) ;=> 6

NP: Dead Moon—Play With Fire

The Christmas Duck Song

Frohe Weihnachten, ein schönes Fest, und einen guten Rutsch ins neue Jahr wünscht euch
Leah Neukirchen

Merry Christmas and a Happy New Year!

NP: ANOHNI and the Johnsons—You Be Free

I drafted this article in Feburary for a blog project that never came to realization, but as it’s a nice little article so I’ll just post it here:

I was thoroughly nerdsniped by a recent post on The Unix Heritage Society mailing list, where this anecdote was mentioned by Noel Chiappa:

Steve Ward told another oral story which I’m pretty sure is true, though. They ask the candidate to design a state machine (or digital logic, I forget which) which can tell if a number is divisible by three (I think I have the details correct, but I’m not absolutely certain). So they describe one – and then point out that you can feed the number in from either end (most or least significant end first) – and proves that it will work either way! The committee was blown away.

Since this sounded like an interesting statement, I tried to find a proof myself and found two solutions, one using automata theory and one using ordinary math.

Read as a PDF: On division by three.

NP: Lightning Bolt—No Rest for the Obsessed

Ein Entwurfsmuster für kollektiv verwaltete Räume. (Entworfen um 2011 von Leah Neukirchen.)

DAS PUNKTESYSTEM

Kontext: Verschiedene Waren sollen gegen ein Entgelt zur Verfügung gestellt werden können.

Problem: Die Waren haben unterschiedliche Preise, der Verkauf soll zudem keinen Verlust erzeugen.

Verwandte Muster:

• STRICHLISTE, falls alles die gleichen Preise hat.
• KASSE DES VERTRAUENS, falls keine Vorzahlung erwünscht ist.

Lösung: Die Einführung eines PUNKTESYSTEMS. Dies besteht aus einem zentral angebrachten Blatt Papier auf dem jeder Nutzende eine Zeile belegt (Stammnutzer können eine Zeile in der Vorlage vorgedruckt bekommen).

Jede Zeile besteht aus z.B. drei Kästchen übereinander. Es wird ein Preis pro Kästchen spezifiziert (z.B. 33ct). Nutzende können nun in eine KASSE DES VERTRAUENS einzahlen, und die vorbezahlten Kästchen mit einem Stift markieren. Bei der Entnahme von Waren wird bezahlt, in dem man die entsprechende Anzahl Kästchen ausmalt. Dank der Vorkasse können Waren auf Vorrat eingekauft werden. Es ist darauf zu achten, dass niemand bei der Kasse Schulden macht.

Sind sehr viele Zeilen gefüllt, so wird ein neues Blatt ausgedruckt, und die geleisteten Vorzahlungen werden in neue Zeilen übertragen.

NP: Mrs. Piss—You Took Everything

You probably have seen ISO 8601 timestamps with fractional seconds, such as this one:

% date --iso-8601=ns 
2023-04-20T18:45:11,094052607+02:00

However, many people don’t know ISO 8601 also allows for fractional minutes and hours!

According to the standard, these timestamps are equivalent (rounded to a second):

2023-04-20T18:45:11
2023-04-20T18:45,18333
2023-04-20T18,75305

Note that in contrast to common scientific usage, the decimal part is recommended to be separated by a comma and not a full stop, although the latter is permitted too.

However, the standard does not specify the obvious next generalization, that is, allowing fractional days. I thus propose to extend ISO 8601 in the following way, which does not change the meaning of valid existing representations:

The local time representation (after the optional time designator) may consist of only a decimal fraction, which then is interpreted as a multiple of 24 hours.

Thus, we can write the above timestamp also like this:

2023-04-20T,78137
2023-04-20,78137

Now, why would one want this? Essentially, there are three reasons:

First, it’s cute and an obvious extension of the existing format.

Second, it allows representing times of the French Republican Calendar in a natural way, which uses a decimal system as well: in this calendar, the day is divided into 10 hours of 100 minutes and 100 seconds each. Thus, the digits align directly to a decimal fraction of the whole day. The above timestamp is then (computed using fdate):

Primidi, 1 Floréal CCXXXI (231) 7:81:37

Note that we use local time here, not Paris time. If you insist on using Paris solar time, you need to offset 9 ISO minutes and 21 ISO seconds, which can be approximated as

2023-04-20T,77350+0009

Note that ISO 8601 does not allow for specifying offsets from UTC in seconds (another obvious oversight).

Finally, the mechanism also supports the use of Swatch Internet Time, a late 90s decimal time system. Here, the day is divided into 1000 beats, and the offset is fixed UTC+1 (for the Swatch headquarters in Biel):

2023-04-20T,739+0100

This is a bit more verbose than @739 but at least it’s an international standard already!

NP: Tristan Brusch feat. Annett Louisan—Kein Problem

Frohe Weihnachten, ein schönes Fest, und einen guten Rutsch ins neue Jahr wünscht euch
Leah Neukirchen

Merry Christmas and a Happy New Year!

NP: First Aid Kit—Fallen Snow

I was happily typesetting a book with ConTeXt and its new engine LMTX when I decided to print a few pages to see if I got the sizes right. Since I despise printer daemons, I directly print stuff over the network using a little script.

To my surprise, I just got a blank page out.

As the title of this post suggests, it won’t be the only blank page. This is the story of me debugging PDF generation in LMTX.

Giving it a closer look, the page wasn’t entirely blank. I could see the cutmarks I added to indicate the page size. During creation, I used MuPDF as a previewer—it’s lightweight and stays out of my way. But apparently the PDF was broken, so I tried a few other previewers. Evince and Firefox pdf.js rendered it fine. I looked at Okular and xpdf, and it came out nicely as well. At a later point, I even installed ancient Acrobat 7(!) and it would display as intended.

I tried the other printer in our university office. Another blank page.

Two different vendors, yet they both fail to print a simple PDF?

I secretly hoped some previewer would also render a blank page. Then I could just compile its source code on my machine and throw all kinds of debugging tools at it… but they all worked.

I tried converting the PDF to PDF with Ghostscript, and then it printed fine. So the PDF couldn’t be too wrong. But I wanted to fix it directly.

So how do you debug a PDF that gets printed wrongly but seems to be fine else?

My first intuition was to make a PDF that works, and then look at the differences. So I created a simple document and ran it through the previous ConTeXt version, called MKIV. This version uses LuaTeX as an engine. It printed fine. (No nobody’s surprise—I would have discovered this years ago else.)

I put both PDFs through various PDF validators, but they all said both where good.

Time to dig deeper. I disabled PDF compression and looked at both PDF files in a text editor. Sure, there were a lot of little differences. But fundamentally? Pretty much the same.

… I looked at the first printout again. Not only the page marks were printed, but actually the tiny page numbers inside them were too! I checked the PDF, and saw it uses two fonts (using pdffonts):

NSOLKP+TeXGyreSchola-Regular         CID Type 0C       Identity-H       yes yes yes      4  0
FFMARX+DejaVuSansMono                CID TrueType      Identity-H       yes yes yes      5  0

The page numbers use the DejaVu Sans font, which is supplied in TrueType format. I changed the main font of my test document to DejaVu Sans, and voilà: it printed fine. I was very happy about this, as it meant LMTX can generate printable PDF files in principle. But for its default font (Latin Roman) and the font I wanted to print in (TeX Gyre Schola), there apprently was an issue.

I knew the basics of PDF from decades ago when I wrote a PDF generator from scratch. (I never got around doing more than putting a few characters on a page, though.) Now it was time to learn about the PDF font formats.

Both the MKIV and the LMTX engine use the “CID Type 0C” font format these days, which embeds only the actually used glyphs from an OpenType font into the PDF. I pulled out the CID fonts from the PDF (using mutool extract). While file didn’t recognize the file format, luckily FontForge could open it fine. (As I learned later, FontForge can open the PDF directly and import its fonts.)

I noticed a first difference: while MKIV (and thus LuaTeX) spread out the glyphs over the positions, LMTX nicely arranged the used glyphs starting from code point 1. I had already contacted Hans Hagen, the main developer behind ConTeXt, and we wondered whether starting the glyphs from 31 would help… again it rendered nicely on all previewers, but still printed blank pages.

I had the strong suspicion that the font embedding was the problem. To verify this hypothesis, I manually fiddled the LMTX font into the MKIV document (this was easy because it was smaller, so I just had to add some padding to make the document be valid again), adjusted some code points in the PDF, and it would render glyphs on the screen. But it would not print. So now I was fairly sure that the font stream was the culprit, and not some other part of the PDF.

After more research, I found a tool to dump a CID font in a readable format: CFFDump. This small Java program turned out to be essential for tracking down the bug.

It generates a dump that looks like this:

% CFF Dump Output
% File: font-0008.cid


--------------------------------------------------------------------------------

Header (0x00000000):
    major: 1
    minor: 0
    hdrSize: 4
    offSize: 4

--------------------------------------------------------------------------------

Name INDEX (0x00000004):
  count: 1, offSize: 1
    [0]: (CLLXEY+LMRoman12-Regular)

--------------------------------------------------------------------------------

Top DICT INDEX (0x00000021):
  count: 1, offSize: 1
  [0] (0x00000026):
  <<
    /ROS << /Registry (Adobe) /Ordering (Identity) /Supplement 0 >>
    /CIDCount 15
    /FamilyName (LMRoman12)  % SID 392
    /FullName (LMRoman12-Regular)  % SID 393
    /Weight (Normal)  % SID 394
    /FontBBox [-422 -280 1394 1127]
    /isFixedPitch false
    /ItalicAngle 0
    /UnderlinePosition -175
    /UnderlineThickness 44
    /CharstringType 2
    /FontMatrix [0.001 0 0 0.001 0 0]
    /StrokeWidth 0
    /CharStrings 257  % offset
    /charset 220  % offset
    /FDArray 1751  % offset
    /FDSelect 249  % offset
    /Private [23 1728]  % [size offset]
    % ----- Following entries are missing, so they get default values: -----
    /PaintType 0  % default
    /CIDFontVersion 0  % default
    /CIDFontRevision 0  % default
    /CIDFontType 0  % default
  >>

And it goes on and on, detailing all the things specified in the font.

Inevitably, I had to dig into the internals of CFF fonts, that is Adobe’s Technical Note #5176.

I carefully compared the dump of the working MKIV font with the broken LMTX font… and didn’t find substantial differences. Sure, one copied a few more metadata fields, and the other had more font fields set, but mostly to values that were the default anyway. Nothing that seemed to be related to our bug. And also, the various PDF viewers rendered the document fine, so there couldn’t have been a major mistake there.

By now I had learned about the design of LMTX, and luckily I saw that all parts of this font embedding were written in quite straight-forward Lua code that I could easily modify, so experiments were easy. Unfortunately, I didn’t have a printer at home so I had to annoy some of my friends to do test prints for me. They printed a lot of blank pages…

But I just couldn’t track down the problem. A reasonable person would have given up ages ago and just fed the PDF through Ghostscript before printing, but I wanted to get to the bottom of the thing; and I also wanted this new TeX engine to produce working documents out of the box.

In my time as a software developer, one thing I learned about debugging is that if a thing takes a long time to debug, it can be for two reasons: either the cause is much more simple than you thought, or it’s much more complicated.

I chose violence. I corrupted the CID font in various ways… the printer would stop working and printed an error message instead. Some printers have an internal error log, but before these experiments it was empty.

Perhaps the document wasn’t wrong, but the printer software was? But by now we could reproduce the issue with a bunch of printers—how can they all have the same issue?

After some wrong attempts related to font hinting, I was out of ideas and decided to kill all fields one by one and check if it made any difference.

I deleted the /FontMatrix entry and… suddenly it printed nicely.

Now, the font matrix is a feature of CFF fonts to encode their scaling and shearing factors. It’s a 2x3 matrix that encodes an affine transformation (perhaps you know this from SVG). The details don’t matter, but in practice you only have two values set and they determine the font size relative to the sizes used in the font drawing instructions. By default, the font matrix is [0.001 0 0 0.001 0 0], meaning that moving by 1000 units will move by 1 PostScript point on paper.

I was happy, but I also was very confused: of all things, why exactly did that fix it? I noticed earlier that the MKIV document didn’t have the font matrix set, but I also looked at the Ghostscript output and there it worked fine. Even more so, LMTX set the font matrix to its default value! It shouldn’t make a difference at all!

Gone this far, I wasn’t satisfied without a real answer. I wondered if LMTX encoded the font matrix the wrong way, but after digging into the spec for that (Technical Note #5177) and double checking, it seemed fine. The working Ghostscript PDF used exactly the same byte sequence to encode the font matrix.

Staring some more at CFFDump output, I finally noticed what Ghostscript did differently: the CFF had two font matrices defined! CFF allows defining a font matrix in the “Top DICT INDEX” as well as the “Font DICT INDEX”.

And while the “Top DICT INDEX” was the same that we used, [0.001 0 0 0.001 0 0], the one in the “Font DICT INDEX” was [1 0 0 1 0 0], i.e. the identity matrix. I added this matrix to LMTX output, and finally the PDF printed properly.

Still, this was a surprise. Why would explicitly setting the font matrix to its default value change the behavior? It turns out the reason for this is an interaction between both of these default values. Unfortunately, it seems to be not specified by Adobe. I found a similar bug in Ghostscript that explains the reasonable thing to do:

1) If both Top DICT and Font DICT does _not_ have FontMatrix, then Top DICT = [0.001 0 0 0.001 0 0], Font DICT 
= [1 0 0 1 0 0].  (Or, Top DICT = (absent), Font DICT = [0.001 0 0 0.001 0 0] then let '/CIDFont defineresource' 
make Top DICT = [0.001 0 0 0.001 0 0], Font DICT = [1 0 0 1 0 0].)

2) If Top DICT has FontMatrix and Font DICT doesn't, then Top DICT = (supplied matrix), Font DICT = [1 0 0 1 0 0].

3) If Top DICT does not have FontMatrix but Font DICT does, then Top DICT = [1 0 0 1 0 0], Font DICT = 
(supplied matrix).  (Or, Top DICT = (absent), Font DICT = (supplied matrix) then let '/CIDFont defineresource' 
make Top DICT = [0.001 0 0 0.001 0 0], Font DICT = (supplied matrix 1000 times larger). I think this is better.)

4) If both Top DICT and Font DICT _does_ have FontMatrix, then Top DICT = (supplied matrix), Font DICT = 
(supplied matrix).

All previewers seem to have adapted this algorithm. But certain older printers botched step 2. They end up with two font matrices [0.001 0 0 0.001 0 0] that are multiplied together, which ends up printing your document at a thousandth of its size; i.e. you get a blank page. But note that it’s a perfectly valid PDF!

We thus had two ways to fix the bug: write no font matrix at all, or write both of them. I was first learning towards the latter, and do it as Ghostscript does, but we found an issue with FontForge that it will render the fonts internally at 1000x the size and thus consume a lot more memory. Since we did not find a need to use a non-default font matrix, we decided to go with the former: no font matrix at all. After all, it worked fine for LuaTeX all those years, too.

(Why did this issue not affect the TrueType font? It’s embedded in a different format that only has a single scaling factor and has no concept of a font matrix.)

A trial print of the PDF on many printers is on-going but seems to be very promising so far, so that this fix (essentially, deletion of one line of code) will be shipped soon in a ConTeXT snapshot for general availability.

I would like to thank Hans Hagen for not giving up on helping me with this, and all my friends that test-printed some page for me and/or had to hear me talking about nothing else for a week or so.

NP: Rites of Spring—All Through A Life

Prelude and Motivation

After trying out and fiddling with a plethora of existing and self-written software to organize my notes, I have decided I need to stop experimentation and choose a solution that is sufficient, but most importantly, one that I actually will use and have migrated all my existing notes to. Note taking systems are not an end unto themselves.

Roughly speaking, my essential requirements are:

• Something that works with plain text, and ideally supports Markdown as that is the syntax I publish most things in and I am most familiar with.
• Something that can be used from Emacs, because that’s where I do most my text editing and writing.
• Something that stores a note per file. This has just proved to be the most future-proof way.
• Some basic means of connecting notes.

I found I don’t need these things:

• Support for direct HTML publishing, as I realized that most of my notes are written for myself and I’ll put them up somewhere else for publishing. (This usually involves prior editing anyway.)
• Having a fancy UI and graph displays. I consider these goodies I can easily go without.
• Specialized productivity features like to-do lists, date scheduling or time tracking. These are out of scope for my use: I use a regular calendar for things with a deadline (which I’m blessed to have very few of) and will stick to simple to-do lists for my personal projects.

Many people would recommend me org-mode now, but I’ve never been a fan of its clunky syntax and I really don’t need most of the features. org-roam at first looked promising but linking between notes is quite complicated and the database dependency seems to be overkill for a personal note taking system on modern hardware.

I decided to settle on howm, an Emacs mode that is not very well-known in the Western world but has gained a certain following in Japan.

It’s a roughly 20-year-old Emacs mode that’s still being used and maintained by its original author Kazuyuki Hiraoka, so I have confidence it will be around for some more time. You can format notes however you like, so I can use Markdown as I prefer. Notes are one file per note by default (but see below). It actually has features for date scheduling and to-do lists, but I won’t go deeper into them for now. Its code is reasonable simple and well structured, so I was able to extend it in a few ways easily, as I’ll detail at the end of this post.

What really sold me was this quote I found on the mailing list:

I cannot show a good general guide because I’m lazy, loose, and bad at tidying. I’ve already given up well-ordered notes. Howm may be suitable for those who are tired from strict systems.
— Kazuyuki Hiraoka

Such an undogmatic system is just right for my purposes.

How howm works

Since there are very few resources in English that explain howm (apart from this 2006 article that got lost in time), I shall give a quick introduction for the interested reader:

howm is short for “Hitori Otegaru Wiki Modoki”, which roughly translates to “Single-user Easy Wiki Mode”.

The basic feature set of howm is very simple, and can be condensed into the mantra “write fragmentarily and read collectively”. Essentially, howm provides an Emacs minor mode for marking text to trigger certain searches. Since it is a minor mode, you can use whatever major mode you like to use for your writing (e.g., I currently use markdown-mode).

Howm notes are kept in a directory hierarchy that you can organize how you wish; by default a date-based system is used and filenames include the current timestamp at creation. This provides unique and sensible note identifiers, so I stick to it. You also can create explicitly named note files, but I haven’t found a use for them yet.

There are two essential kinds of markup howm cares about: note titles and links. By default, titles are marked up by putting a ‘=’ at the beginning of the line, but this can be configured (and must be done so before loading howm-mode(!)). The benefit of adding a title to a note is that you can have the summary buffer show titles instead of matching lines, which can be helpful to get a better overview of search results. (The creator of howm is sceptical of titling all notes, I think it very much depends the average length of your notes. There is no requirement to use titles.)

There are two kinds of links supported by howm, namely goto and come-from (in a nod to INTERCAL). goto links are forward references and written like this:

>>> howm

Pressing return on this line when howm-mode is enabled will show a list of all occurences of the word howm in your notes directory.

In contrast, a come-from link is written like this:

<<< howm

And this will cause the word howm in any howm-mode buffer to be underlined and trigger a search where the buffer with <<< howm will appear first.

Thus, compared to most contemporary hypertext systems, we not only have a means of explicitly linking to other notes, but also for creating implicit contextual links—which can help you find connections between your notes that you didn’t see yet…

It is straightforward to implement something like #tags or WikiWords using these features, if you wish to do so.

Additionally, howm provides an inline link syntax [[...]] that works like >>> but can appear within a line. I make a suggestion below how to turn it into a direct link to the first page with the given title; but for now I decided not to use this very much.

The line-based nature of the >>> syntax prevents usage for “inline” links. After giving it some thought, I consider it a strength for a note-taking system to make forward links related to a paragraph and not part of a sentence. Additionally, it also makes the plain text easier to read as the link target is not interleaved into the text. (Compare with the use of reference-style links in Markdown.)

An aside: howm actually supports multiple notes per file by having multiple title lines in a file. The search summary will always show the title directly before the matching line. You can use C-c , C to create a new note in the current buffer. I don’t use this much, but I think it could be useful for glossary files that contain many short notes. Some people also use this for keeping multiple daily notes in a single file.

Using howm

Howm provides two main features to access notes: the menu and the summary buffer. The howm menu (shown with C-c , ,) provides a very customizable view into your howm notes. By default it shows your schedule, recent notes, and random notes. You can access many howm features with a single keypress from the menu. Since I don’t use the scheduling feature, I mostly access howm from the summary buffer instead.

The howm summary buffer shows the result of a search (C-c , g), a list of recent notes (C-c , l), or an overview of all notes (C-c , a). It is very convenient to see the matches and you get a preview of the note when you move the cursor to a search result. Typing RET will open the note for editing. Typing T will toggle between displaying matching lines or the titles of notes with matches.

In the summary buffer, you can also type @ and read all matching notes in a concatenated way, so you get the full context of all notes at once.

Setting up and customizing howm

Basic setup is reasonably well documented in English, but I’ll summarize it here. You can get howm from ELPA these days, so installing is very easy. You should set some variables to configure it according to your needs:

;; Directory configuration
(setq howm-home-directory "~/prj/howm/")
(setq howm-directory "~/prj/howm/")
(setq howm-keyword-file (expand-file-name ".howm-keys" howm-home-directory))
(setq howm-history-file (expand-file-name ".howm-history" howm-home-directory))
(setq howm-file-name-format "%Y/%m/%Y-%m-%d-%H%M%S.md")

Here, we decide that ~/prj/howm is the base directory for our howm notes, and we also put the two auxiliary files howm uses there. Additionally, we change the default name format to end with .md (which also turns on markdown-mode by default).

Next, we want to use ripgrep for searching howm. For my usage, plain GNU grep would be sufficient, but I want to use ripgrep in the next step too, so for consistency let’s use it for all searches:

;; Use ripgrep as grep
(setq howm-view-use-grep t)
(setq howm-view-grep-command "rg")
(setq howm-view-grep-option "-nH --no-heading --color never")
(setq howm-view-grep-extended-option nil)
(setq howm-view-grep-fixed-option "-F")
(setq howm-view-grep-expr-option nil)
(setq howm-view-grep-file-stdin-option nil)

The next addition is interactive search with ripgrep (C-c , r). This is the most useful feature I added to howm myself. I think it provides a great way to interact with your notes, as you get instant feedback from your search terms, and can stop searching as soon as you found what you were looking for. I used counsel-rg as an inspiration for this, and we turn the ripgrep matches into a regular howm summary buffer for further consumption.

;; counsel-rg for howm
(defun howm-list--counsel-rg (match)
  (if (string= match "")
  (howm-list-all)
(if (or (null ivy--old-cands)
	(equal ivy--old-cands '("No matches found")))
        (message "No match")
  (let ((howm-view-use-grep
	 #'(lambda (str file-list &optional fixed-p force-case-fold)
                 (mapcar
                  (lambda (cand)
		(if (string-match "\\`\\(.*\\):\\([0-9]+\\):\\(.*\\)\\'" cand)
                        (let ((file (match-string-no-properties 1 cand))
			  (line (match-string-no-properties 2 cand))
			  (match-line (match-string-no-properties 3 cand)))
                          (list (expand-file-name file howm-directory)
                                (string-to-number line)
                                match-line))))
                  ivy--old-cands))))
        (howm-search ivy--old-re t)
        (riffle-set-place
     (1+ (cl-position match ivy--old-cands :test 'string=)))))))

(defun howm-counsel-rg ()
  "Interactively grep for a string in your howm notes using rg."
  (interactive)
  (let ((default-directory howm-directory)
        (counsel-ag-base-command counsel-rg-base-command)
        (counsel-ag-command (counsel--format-ag-command "--glob=!*~" "%s")))
    (ivy-read "Search all (rg): "
	      #'counsel-ag-function
	      :dynamic-collection t
	      :keymap counsel-ag-map
	      :action #'howm-list--counsel-rg
	      :require-match t
	      :caller 'counsel-rg)))

(define-key global-map (concat howm-prefix "r") 'howm-counsel-rg))

Next, I tweak some sorting settings. I want the “recent” view to list files by mtime (so that recently edited files appear on top), but the “all” view should be sorted by creation date.

;; Default recent to sorting by mtime
(advice-add 'howm-list-recent :after #'howm-view-sort-by-mtime)
;; Default all to sorting by creation, newest first
(advice-add 'howm-list-all :after #'(lambda () (howm-view-sort-by-date t)))

A great usability enhancement is buffer renaming: since howm file names are a bit unwieldy (like ~/prj/howm/2022/03/2022-03-25-162227.md) you can use these two lines to rename note buffers according to their title, which makes switching between multiple notes more convenient.

;; Rename buffers to their title
(add-hook 'howm-mode-hook 'howm-mode-set-buffer-name)
(add-hook 'after-save-hook 'howm-mode-set-buffer-name)

Another personal preference is enabling orgalist-mode, which I like for shuffling around Markdown lists.

(add-hook 'howm-mode-hook 'orgalist-mode)

Finally we fix an anti-feature in howm: by default, it binds C-h to the same binding as backspace, but this is only useful on legacy terminals (and even then Emacs does the translation). I wouldn’t really mind, but it breaks the Emacs help feature, so we unbind C-h for the modes:

(define-key howm-menu-mode-map "\C-h" nil)
(define-key riffle-summary-mode-map "\C-h" nil)
(define-key howm-view-contents-mode-map "\C-h" nil)

My configuration ends with three definitions of action-lock, the howm mechanism for marking text active and do something on RET. Two of them are related to the reference management software Zotero, which I use for organizing papers, and enable me to link to articles in my Zotero database by URL or BibTeX identifier:

;; zotero://
(add-to-list 'action-lock-default-rules
             (list "\\<zotero://\\S +" (lambda (&optional dummy)
                                         (browse-url (match-string-no-properties 0)))))
;; @bibtex
(add-to-list 'action-lock-default-rules
             (list "\\s-\\(@\\([a-zA-Z0-9:-]+\\)\\)\\>"
                   (lambda (&optional dummy)
                     (browse-url (concat "zotero://select/items/bbt:"
                                         (match-string-no-properties 2))))
                   1))

Finally, as mentioned above, this is how to make [[...]] wiki-links directly point to the first page with that title, skipping the summary buffer:

;; make wiki-links jump to single title hit if possible
(add-to-list 'action-lock-default-rules
             (list howm-wiki-regexp
                   (lambda (&optional dummy)
                     (let ((s (match-string-no-properties howm-wiki-regexp-pos)))
                       ;; letting create-p be nil here, howm-keyword-search-subr
                       ;; should check create-p after open-unique-p
                       (howm-keyword-search (concat "= " s) nil t)))
                   howm-wiki-regexp-hilit-pos))

The whole configuration is part of my .emacs file.

Future ideas

One thing I want to implement but didn’t yet get around to is support for searching notes using ugrep, which has a nifty boolean search mode that applies to whole files, so you can do searches that are not limited to a line context (e.g. hoge|fuga -piyo finds all notes that mention hoge or fuga, but don’t contain piyo).

I may also look into the scheduling features of howm, but I direct you to the terse README for now, if you’re curious.

Anyway, I hope this was interesting and perhaps encourages you to look into howm, an Emacs mode that I feel doesn’t receive the attention it deserves.

NP: Bob Dylan—What Was It You Wanted