~ $ cd projects/bird-cards && cat README.md

The program that finished before the professor left

Tècniques i Mètodes d'Intel·ligència Artificial, FIB, June 1999. The lab was a parser: a field guide to birds, one card per species written in ordinary Spanish sentences, to be read by a Prolog program and turned into facts a program could ask questions of.

Nombre: Abubilla, Upupa epops.

Identificación: Plumaje pardo-rosado; en vuelo alas y cola blancas y
negras, muy anchas; moño rosado, con puntas negras y largo pico…

becomes

nombre(vulgar([abubilla]), cientifico([upupa, epops]))
identificacion([plumaje([plumaje, pardo-rosado]), vuelo([vuelo]),
                alas([alas]), cola([cola, blancas, y, negras, muy, anchas]), …])

The day it was due, the professor came round with a floppy of test cards, handed it over, and started to walk away, because with everyone else's program the test took ten or twenty minutes to run. We put the disk in, looked at what was on it, ran the program, and called after him before he had reached the door. It was done.

What the code says happened

I remembered the reason as a different kind of grammar. Twenty-seven years later the ten versions are still on a floppy — T1.PL to TF.PL, the eighth to the fourteenth of June — and a classmate's beside them, so it can be checked. Both are the same size and both are DCGs, Prolog's grammar rules. The difference is the shape of the rules.

The other program looks for keys inside a sentence: it walks the words, and at each one asks whether it is a key, or a superkey with keys inside it, or a separator, and on failure it backs up and tries another reading —

s_SuperClave(F)        --> s_LClaves(F, [], Ffin, _), s_SuperClave(Ffin).
s_SuperClave([F|Ffin]) --> t_SuperClave(_, F, Fdins), s_VariasClaves(Fdins, []), s_SuperClave(Ffin).
s_SuperClave(F)        --> s_LPalabras(Lp, Lf), s_SuperClave_F1(F, Lp, Lf).

Three alternatives for the same head, none of which can be told apart without reading ahead, so Prolog tries them in turn and, deep inside a long card, tries them again and again. That is what a twenty-minute run is.

Mine decides at the first word:

s_UnaFicha(F) --> s_Identificacion(F).
s_UnaFicha(F) --> s_Nidificacion(F).
s_UnaFicha(F) --> s_Alimentacion(F).
s_UnaFicha(F) --> s_Habitat(F).
s_UnaFicha(F) --> s_Nombre(F).

s_Nombre(nombre(vulgar(Lv), cientifico(Lc)))
    --> t_Nombre, t_DosPuntos, s_NomPalabras(Lv), s_NomSeparador, s_NomPalabras(Lc), s_Punto_PotserNula.

Every alternative of s_UnaFicha begins with a terminal that no other begins with — Nombre, Identificación, Alimentación — so the first token picks the rule and nothing is ever tried twice. Inside each rule the same holds: lists are read by "one more, or none" pairs that never need to look back, and analisis cuts, with !, at the first parse. A compiler person would say the grammar is LL(1) by construction. I did not know the name; I had rewritten the facts the cards had to become until a grammar that never backtracked could produce them, which is the other half of the trick.

It is the same lesson as the one the thesis taught later about loops: the algorithm was not made faster. It was rewritten so that the machine underneath — here, Prolog's search — had nothing to search.