Supported by a finely woven mesh

[triska]

Dear all,

in the past few days, I tried to improve the speed of format_//2 and related constructs. format_//2 is a DCG nonterminal, and often invoked as part of an argument to phrase/2. For instance, as already mentioned in #2364, it occurs in one of my programs as:

word_hex(Bytes, Hex) :-
        binary_decimal(Bytes, D),
        phrase(("0x",format_("~`0t~16r~8+", [D])), Hex).

In addition, there is also a predicate format/2, which is defined in terms of another, more general predicate called format/3:

format(Fs, Args) :-
        current_output(Stream),
        format(Stream, Fs, Args).

And format/3 in turn is defined in terms of format_//2, wrapped in yet another meta-predicate called phrase_to_stream/2 from library(pio):

format(Stream, Fs, Args) :-
        phrase_to_stream(format_(Fs, Args), Stream),
        flush_output(Stream).

It came as a surprise to me that 3 straight-forward clauses of goal_expansion/2 suffice to improve the running time of each of these constructs in all contexts in which they can arise, even when they are "nested" in completely different constructs as in the examples above, where format_//2 occurs as a direct argument of phrase_to_stream/2 and (',')//2, and as an indirect argument of phrase/2.

For instance,library(format) can, and per #2363 also does, instruct Scryer Prolog to expand every occurrence of a call to format/3 in every application program or library directly to its definition, by defining:

user:goal_expansion(format(Stream, Fs, Args),
                    (   pio:phrase_to_stream(format:format_(Fs, Args), Stream),
                        flush_output(Stream))).

In the resulting expansion, format_//2 is used as an argument to phrase_to_stream/2. I originally thought that any further automated expansion of such an occurrence of format_//2 as an argument to phrase_to_stream/2 in particular would have to be handled as a special case, in addition to cases where it occurs as a direct or indirect argument of phrase/2. However, it turns out that I did not have to do anything special, because phrase_to_stream/2 is declared as a meta-predicate in such a way that Scryer Prolog knows that its first argument is a goal and hence automatically applies goal expansion to this argument even correctly taking into account the additional declared arguments:

:- meta_predicate(phrase_to_stream(2, ?)).

I thus feel safely held in a finely woven mesh that Scryer Prolog provides for me: Because these fundamental building blocks work so reliably, I was able to improve library(format) in ways I originally did not think were possible. With all the latest improvements, the example code above is automatically expanded to:

?- listing(word_hex/2).
word_hex(A,B) :-
   binary_decimal(A,C),
   B=['0',x|D],
   format:format_cells([cell(0,8,[glue('0',E),goal(integer_to_radix(C,16,lowercase,F)),chars(F)])],D,[]).

Note that neither the format string nor the argument list still occur in the resulting code! They have become enmeshed in a list of "instructions" that can be interpreted more efficiently.

Higher-order programming with library(lambda) is another well-known set of constructs that mesh perfectly with the existing meta_predicate/1 directive and other Prolog features.

In the face of such possibilities, I also feel that we have seen nothing yet of what is even possible with Prolog! The efficient string representation of Scryer will make applications possible that nobody thought possible, and today @aarroyoc announced the first Scryer Prolog predicate compiled to native code with cranelift, which was first mentioned a few years ago by @KellerFuchs in #14 (comment). @KellerFuchs, if you are still interested in this, could you please take a look? I would greatly appreciate your help in this area, especially considering the prospect of a natively compiled CLP(B) or CLP(ℤ) on the horizon.

Thank you all for these awesome developments! All these contributions and interactions are themselves like a fine mesh.

All the best,
Markus