Monthly Archives: April 2013

Zipper lists in Prolog

I’m currently looking into zipper data structures. Searching the web for zippering lists for prolog, the third hit is this old blog post by Daniel Lyons (hi Daniel!):

But I don’t liked the calls to reverse/2 and append/3 and their implied performance hits. So, I just rewrote the code to eliminate the calls (and start list index at 1; this is not C! :-)

% zipper(+Position, +List, -Zip, -Element)
% where Zip = zip(Before, Element, After)
% index starts at 1

zipper(Position, List, Zip, Element) :-
    zipper(Position, List, [], Zip, Element).

zipper(1, [Head|Tail], Acc, zip(Acc,Head,Tail), Head).
zipper(N, [Head|Tail], Acc, zip(Before,Element,After), Element) :-
    N > 1,
    M is N - 1,
    zipper(M, Tail, [Head|Acc], zip(Before,Element,After), Element).

next(zip(Before,Element,[Head|Tail]), zip([Element|Before],Head,Tail)).

previous(X, Y) :-
    next(Y, X).

Some sample queries:

?- [zipper].
% zipper compiled 0,00 sec, 5 clauses

?- zipper(3, [1,2,3,4,5], Zip, X), next(Zip, Next).
Zip = zip([2, 1], 3, [4, 5]),
X = 3,
Next = zip([3, 2, 1], 4, [5]) .

?- zipper(3, [1,2,3,4,5], Zip, X), next(Zip, Next), previous(Next, Zip).
Zip = zip([2, 1], 3, [4, 5]),
X = 3,
Next = zip([3, 2, 1], 4, [5]) .

?- zipper(3, [1,2,3,4,5], Zip, X), previous(Zip, Previous).
Zip = zip([2, 1], 3, [4, 5]),
X = 3,
Previous = zip([1], 2, [3, 4, 5]) .

?- zipper(3, [1,2,3,4,5], Three, X),
   next(Three, Four), next(Four, Five), previous(Five, Four),
   previous(Four, Three), previous(Three, Two), previous(Two, One).
Three = zip([2, 1], 3, [4, 5]),
X = 3,
Four = zip([3, 2, 1], 4, [5]),
Five = zip([4, 3, 2, 1], 5, []),
Two = zip([1], 2, [3, 4, 5]),
One = zip([], 1, [2, 3, 4, 5]) .

I wonder how many curious Prolog programmers wrote a similar solution in the past. A cut can be added to the first clause of zipper/5 to eliminate a choice point. The zipper constructed is not the same (minus the index start) as in Daniel’s solution, however, as we can no longer simply concatenate Before+Element+After to get the original list. On the other hand, my solution follows the list example on the Wikipedia page:

Pros and cons of both solutions from an usage perspective? Still learning but this is fun programming :-) Eventually, I hope to add support for zipper data structures to the Logtalk library.

Structured Message Printing

Logtalk 3.x adds a structured message printing mechanism. This feature gives the programmer full control of message printing, allowing it to filter, rewrite, or redirect any message. The origins of the mechanism for message printing that inspired the Logtalk implementation go back to Quintus Prolog, where it was implemented, apparently, by Dave Bowen (thanks to Richard O’Keefe for the historical bits). This mechanism can also be found currently on e.g. SICStus Prolog, SWI-Prolog, and YAP.

Why a mechanism for printing messages? Consider the different components in a Logtalk application development and execution. At the bottom level, you have the Logtalk compiler and runtime. The Logtalk compiler writes messages related to e.g. compiling and loading files, compiling entities, compilation warnings and errors. The Logtalk runtime writes banner messages and handles execution errors that may result in printing human-level messages. The development environment can be console-based or you may be using a GUI tool such as PDT. In the latter case, PDT needs to intercept the Logtalk compiler and runtime messages to do its magic and present the relevant information using its GUI. Then you have all the other components in a typical application. For example, your own libraries and third-party libraries. The libraries may want to print messages on its own, e.g banners, debugging information, or logging information. As you assemble all your application components, you want to have the final word on which messages are printed, where, an in what conditions.

The Logtalk message printing mechanism provides you with a set of predicates, defined in the logtalk built-in object, and some hook predicates. Two of the most important predicates are logtalk::print_message(Kind, Component, Term), which is used for printing a message, and logtalk::message_hook(Term, Kind, Component, Tokens), a user-defined hook predicate used for intercepting messages. The Kind argument is used to represent the nature of the message being printed. It can be e.g. a logging message, a warning message or an error message, In Logtalk this argument can be either an atom, e.g. error, or a compound term, e.g. information(requested). Using a compound term allows easy partitioning of messages of the same kind in different groups. Messages are represented by atoms or compound terms, handy for machine-processing, and converted into a list of tokens, for human consumption. This conversion is performed using the non-terminal logtalk::message_tokens(Term, Component). A simple example is:

:- multifile(logtalk::message_tokens//2).
:- dynamic(logtalk::message_tokens//2).

logtalk::message_tokens(loaded_settings_file(Path), core) -->
    ['Loaded settings file found on directory ~w'-[Path], nl, nl].

The Component argument is new in the Logtalk implementation and is useful to filter messages belonging to a specific component (e.g. the Logtalk compiler and runtime is identified by the atom core) and also to avoid conflicts when two different components define the same message term (e.g. banner seems to be popular).

There are also predicates for printing a list of tokens, logtalk::print_message_tokens(Stream, Prefix, Tokens), for printing an individual token, logtalk::print_message_token(Stream, Token), and for setting default output stream and message prefixes, logtalk::message_prefix_stream(Kind, Component, Prefix, Stream). For example, the SWI-Prolog adapter file uses the print_message_token/2 hook predicate to enable coloring of messages printed on a console.

Using the message printing mechanism in your applications and libraries is easy. Simply chose a component name for your application, call logtalk::print_message/3 for every message that you may want to print, and define default translations for your message terms using the multifile non-terminal logtalk::message_tokens/2. For a full example, see e.g. the lgtunit tool. Happy coding!