Pure QOI (Quite Ok Image) format implementation

General
21

I see these two options as doing quite different things. Yes, CLP can be used to implement logically pure arithmetic but it primarily supports the incremental addition of multiple co-constraints between multiple variables, and fails immediately whenever the addition of a constraint results in an inconsistency. And yes, that seems to be overkill for the job that you’re interested in here.

A difference of 3 orders of magnitude (1000x) sounds high to me, but I don’t know the details of exactly what’s being compared.

22

Here’s a way of removing most of the overhead of freeze/2 when calling C code , e.g. uint32_codes(Number,Codes), which can convert Number to Codes or Codes to Number): add an output parameter to the C code that indicates whether a freeze is needed

uint32_codes_when(Uint32, Codes) :-
    when((nonvar(Uint32) ; nonvar(Codes)), uint32_codes(Uint32, Codes)).

becomes

uint32_codes_when(Uint32, Codes) :-
    uint32_codes(Uint32, Codes, Freeze),
    (  Freeze = freeze
    -> when((nonvar(Uint32) ; nonvar(Codes)), uint32_codes(Uint32, Codes, _))
    ;  true
    ).
23

Michael Hendricks thought of this and made a pack called delay that tries to do this: "delay" pack for SWI-Prolog

Don’t you think it would be better to do this instead ?

uint32_codes(Uint32, Codes) :-
    (  ground(Uint32)
    -> uint32_to_codes(Uint32, Codes) % C predicate
    ;  ground(Codes)
    -> codes_to_uint32(Codes, Uint32) % C predicate
    ;  when((ground(Uint32) ; ground(Codes)), uint32_codes(Uint32, Codes))
    ).

Do you think that doing the if-then-else in prolog is significantly more expensive than doing the if-then-else in C ?

24

Surely when using nonvar/1 rather than ground/1, the check is really fast. Not that ground on a long code list is expensive and when(ground(List), Goal) is too, in particular if you keep adding (but not closing) the list.

when/2 should probably use goal expansion on the condition if this is known at compile time. It can then generate much more efficient code. Anyone interested in creating a PR?

25

NU-Prolog allowed “delay” declarations on predicates (similar to mode declarations), rather than requiring freeze/2 or wait/2 on the calls. NU-Prolog’s approach is better IMHO (although it could be used to do goal-expansion with wait/2 of course).

The implementation of uint32_to_codes/2 has to check whether the first or second argument is instantiated; and (in this particular situation), the most common situation is that one of them is instantiated, so there is no delay; therefore, checking in the C code is the fastest.

And, in this particular situation, I used “freeze” to avoid having to write two versions of the code:

  ... uint32_codes_when(A,B), some_pred(...)

instead of

  ... (  ( nonvar(A) ; nonvar(B) )
      -> uint32_codes(A,B), some_pred(... )
      ;  some_pred(...), uint32_codes(A,B)
      )

Probably I should have written some kind of goal expansions to do this, but wait/2 already existed. :slight_smile:

26

SICStus has block/1 for that, which is available in the SICStus emulation layer, indeed by using when/2. See block_directive:(block)/1

27

For my situation (and, I suspect, QOI), the full “wait” isn’t needed but instead the following should work:

reorder_when(When, G1, G2) :-
    ( call(When) -> (G1, G2) ; (G2, G1) ).
reorder_when(When, G1, G2) -->
    ( { call(When) } -> (G1, G2) ; (G2, G1) ).

and, for performance, these should be expanded at compile time.

So, my code uint32_codes_when(A,B), some_pred(...) would become

 ... reorder_when((nonvar(A);nonvar(B)), 
                  uint32_codes(A,B), some_pred(...))
1 Like
28

Makes sense. A trivial goal_expansion/2 rule would do a pretty good job. Especially a conditional jump on a single side-effect-free built-in condition is pretty fast.

29

The sparse documentation leaves me none-the-wiser as to how it could work :frowning_face:

30

There is documentation in the form of library code in library(apply_macros).

31

If it helps, this is my solution for reorder_when//2 (note the S=T3 and S=T7 in the “then” and “else” sides of the expansion):

goal_expansion(reorder_when(When, G1, G2, S0, S), Expansion) :-
    reorder_when_expansion(When, G1, G2, S0, S, Expansion).

:- det(reorder_when_expansion/6).
reorder_when_expansion(When, G1, G2, S0, S, Expansion) =>
    Expansion = ( When -> ( G1a, G1b, S=T3 )
                       ;  ( G2b, G2a, S=T7 ) ),
    S0=T1,
    dcg_extend(G1, T1, T2, G1a),
    dcg_extend(G2, T2, T3, G1b),
    S0=T5,
    dcg_extend(G2, T5, T6, G2b),
    dcg_extend(G1, T6, T7, G2a).

dcg_extend(G, S0, S, Gx) :-
    G =.. [Head|Args],
    append(Args, [S0, S], Args2),
    Gx =.. [Head|Args2].

and trying it out:

f(A,B) --> reorder_when((nonvar(A);nonvar(B)), p1(A,B), p2(foo)).

?- listing(f).
f(A, B, C, D) :-
    (   (   nonvar(A)
        ;   nonvar(B)
        )
    ->  p1(A, B, C, E),
        p2(foo, E, F),
        D=F
    ;   p2(foo, C, G),
        p1(A, B, G, H),
        D=H
    ).