Testing goal expansion of meta-predicate maplist

Question

Q: How can we get rid of maplist overhead—like SWI's apply_macros—in SICStus Prolog?

A: Goal expansion.

First, we define the auxiliary predicates we'll need. In the following we use SICStus Prolog 4.5.0.

:- module(maplist_macros, [maplist/2, maplist/3, maplist/4, maplist/5, maplist/6, maplist/7, maplist/8, maplist/9]).

:- meta_predicate maplist(1,?), maplist(2,?,?), maplist(3,?,?,?), maplist(4,?,?,?,?), maplist(5,?,?,?,?,?), maplist(6,?,?,?,?,?,?), maplist(7,?,?,?,?,?,?,?), maplist(8,?,?,?,?,?,?,?,?).

:- use_module(library(lists), [append/2, same_length/2]).
:- use_module(library(ordsets)).

callable_arglists_appended(C0, New, C1) :-
   C0 =.. Parts0,
   append([Parts0|New], Parts1),
   C1 =.. Parts1.

:- dynamic expand_goal_aux/1.
my_expand_goal(Goal, Expanded) :-
   asserta((expand_goal_aux(Goal) :- Goal)),
   retract((expand_goal_aux(Goal) :- Expanded0)),
   strip_module(Expanded0, _, Expanded).

strip_module(MGoal_0, Module, Goal_0) :-
   aux_strip_module(MGoal_0, Goal_0, lambda, Module). % lambda?!

aux_strip_module(MG_0,G_0, M0,M) :-
   (  nonvar(MG_0),
      MG_0 = (M1:MG1_0)
   -> aux_strip_module(MG1_0,G_0, M1,M)
   ;  MG_0 = G_0,
      M0 = M
   ).

:- dynamic maplist_aux_count/1.
maplist_aux_count(0).

Now on to the goal expansion:

% generate specialized `maplist/N'
goal_expansion(Goal0, _Layout0, FromModule, FromModule:Goal, []) :-
   Goal0 =.. [maplist, Rel0 | Args],
   callable(Rel0),
   Args = [_|_],
   !,
   % get count # of aux preds generated so far and increment it
   retract(maplist_aux_count(C)), 
   C1 is C+1,
   asserta(maplist_aux_count(C1)),

   % build predicate functor `AuxPred'
   number_chars(C, C_chars),
   atom_chars(C_atom, C_chars),
   atom_concat(maplist_aux_, C_atom, AuxPred), % e.g., maplist_aux_3

   % enforce all relevant lists have the same length
   lists:maplist(same_length(Args), [Vars_E,Nils]),
   lists:maplist(lists:cons, Vars_E, Vars_Es, Vars_E_Es),
   lists:maplist(=([]), Nils),

   % expand the goal in the right module (`FromModule')
   strip_module(Rel0, _, Rel1),
   callable_arglists_appended(Rel1, [Vars_E], Rel2),
   my_expand_goal(FromModule:Rel2, Rel),

   % find out which variables need to be threaded through
   term_variables(Rel, Vars_Schema),
   list_to_ord_set(Vars_Schema, VSet_Schema),
   list_to_ord_set(Vars_E,      VSet_E),
   ord_subtract(VSet_Schema, VSet_E, VSet_Actual),

   % build call of new predicate with proper arguments
   callable_arglists_appended(AuxPred, [Args,VSet_Actual], Goal),

   % callee clauses (new predicate)
   callable_arglists_appended(AuxPred, [Nils,     VSet_Actual], Head0), % fact
   callable_arglists_appended(AuxPred, [Vars_E_Es,VSet_Actual], Head1), % rule
   callable_arglists_appended(AuxPred, [Vars_Es,  VSet_Actual], Rec1),  % 

   % dump generated clauses to a file
   atom_concat('/tmp/x', C_atom, FileName), % TODO: get actual tmpfilnam
   open(FileName, write, S),
   portray_clause(S, (Head0 :- true)),
   portray_clause(S, (Head1 :- Rel, Rec1)),
   close(S),

   % compile temporary file in proper module
   compile(FromModule:FileName).

So far so good;) So here's the problem...

How can I ensure that the goal-expanded variant is exactly like the predicates it replaces?

(I have a hunch that it is not, but I can't quite put my finger on it...)

Simple sample use case #1

allequal(Xs) :- maplist(=(_), Xs).

becomes

allequal(A) :- maplist_aux_0(A, _).

maplist_aux_0([], _).
maplist_aux_0([A|B], C) :- C=A, maplist_aux_0(B, C).

looks strange callable_arglists_appended(C0, New, C1) :- C0 =.. Parts0, append([Parts0|New], Parts1), i'd expect append(Parts0, New, Parts).` C1 =.. Parts1.` expected append(Parts0, New, Parts). — Anton Danilov
@AntonDanilov. The code is using append/2 instead of one or more append/3 goals. If you look at its use sites, you can see that callable_arglists_appended/3 usually appends two lists of arguments (e.g., Nils = [[]], VSet_Schema = [_]). — repeat
@AntonDanilov. I get that. To me, append/2 is a bit strange too... — repeat
It's swipl library(apply) out of reach ? Should be funny to port... The core part should be in apply_macros.pl tough — CapelliC
@CapelliC. The devil is in the details... SWI has expand_goal/2 and compile_aux_clauses/1. There are subtle differences in the module system. Plus, this question does not include support for lambdas. — repeat

Per Mildner Per Mildner · Accepted Answer · 2019-02-28T17:41:22

The easiest solution is perhaps to expand to do/2, similar to what library(lists) in SICStus uses for implementing maplist/n.

/* -*- Mode:Prolog; coding:iso-8859-1; indent-tabs-mode:nil; prolog-indent-width:8; prolog-paren-indent:4; tab-width:8; -*- */

/*
   Replacement for maplist from library lists, that inlines the calls when possible.

   In your code, instead of doing:

   :- use_module(library(lists),[maplist/2, maplist/3, ... other non-maplist things ...]).

   Do:

   :- use_module(library(lists),[... other non-maplist things ...]).
   :- use_module(maplist_inliner, [maplist/2,maplist/3]).

 */
:- module(maplist_inliner, [maplist/2,maplist/3]).

% We can not import (and reexport) maplist/2 etc from the module 'lists' (because
% our goal_expansion will only be used from our own predicates, not predicates we reexport).
% Instead we use thin wrappers for those cases where we are unable to inline the calls to maplist.
% However, these will never be used, because we always fallback to expanding to a plain lists:maplist/n call.
:- use_module(library(lists), []).

:- meta_predicate maplist(1, +).
:- meta_predicate maplist(2, +, +).
% TODO: Add more arities

% A thin wrapper around lists:maplist/2. See module documentation for rationale.
maplist(G_1, L1) :-
        lists:maplist(G_1, L1).

% A thin wrapper around lists:maplist/3. See module documentation for rationale.
maplist(G_2, L1, L2) :-
        lists:maplist(G_2, L1, L2).


get_module(X, ModuleContext, G, M) :-
        var(X),
        !,
        G = X,
        M = ModuleContext.
get_module(M1:X, _ModuleContext, G, M) :-
        !,
        get_module(X, M1, G, M).
get_module(X, ModuleContext, G, M) :-
        !,
        G = X,
        M = ModuleContext.

:- if(fail).
goal_expansion(G, Layout0, ModuleContext, Expansion, Layout1) :-
        writeq(goal_expansion(G,Layout0,ModuleContext,Expansion,Layout1)),
        nl,
        fail.
:- endif.

goal_expansion(maplist(G, L1), _Layout0, ModuleContext, Expansion, Layout1) :-
        callable(G),
        get_module(G, ModuleContext, G_1, M),
        callable(G_1),
        atom(M),
        !,
        Layout1 = [],           % No source info
        inline_maplist_2(G_1, M, L1, Expansion).
goal_expansion(maplist(G, L1), _Layout0, ModuleContext, Expansion, Layout1) :-
        !,
        Layout1 = [],           % No source info
        Expansion = lists:maplist(ModuleContext:G,L1).


goal_expansion(maplist(G, L1, L2), _Layout0, ModuleContext, Expansion, Layout1) :-
        callable(G),
        get_module(G, ModuleContext, G_2, M),
        callable(G_2),
        atom(M),
        !,
        Layout1 = [],           % No source info
        inline_maplist_3(G_2, M, L1, L2, Expansion).
goal_expansion(maplist(G, L1, L2), _Layout0, ModuleContext, Expansion, Layout1) :-
        !,
        Layout1 = [],           % No source info
        Expansion = lists:maplist(ModuleContext:G,L1,L2).


inline_maplist_2(G_1, M, L1, Expansion) :-
        G_1 =.. [F|ClosureArgs],
        append([F|ClosureArgs], [X], G_ClosureArgs_X),
        BodyGoal =.. G_ClosureArgs_X,
        Expansion =
        (foreach(X,L1),
         param(G_1)
        do
         M:BodyGoal
        ).

inline_maplist_3(G_2, M, L1, L2, Expansion) :-
        G_2 =.. [F|ClosureArgs],
        append([F|ClosureArgs], [X1,X2], G_ClosureArgs_X1_X2),
        BodyGoal =.. G_ClosureArgs_X1_X2,
        Expansion =
        (foreach(X1,L1),
         foreach(X2,L2),
         param(G_2)
        do
         M:BodyGoal
        ).

Example

/* -*- Mode:Prolog; coding:iso-8859-1; indent-tabs-mode:nil; prolog-indent-width:8; prolog-paren-indent:4; tab-width:8; -*- */

:- use_module(maplist_inline, [maplist/2,maplist/3]).

p_1(X1) :-
        writeq(call(p_1(X1))).

p_2(X1, X2) :-
        writeq(call(p_2(X1,X2))).


p_3(X1, X2, X3) :-
        writeq(call(p_3(X1,X2,X3))).


test(L1) :-
        ClosureArg1 = 'a',
        maplist(p_2(ClosureArg1), L1).


test(L1, L2) :-
        maplist(p_2, L1, L2).


test_1(L1, Arg) :-
        maplist(p_2(Arg), L1).



test_1(L1, L2, Arg) :-
        maplist(p_3(Arg), L1, L2).


test_noinline(L1, L2, Arg) :-
        G_2 = p_3(Arg),         % Inliner will not see this
        maplist(G_2, L1, L2).

Using consult/1 and listing/1 shows what happens:

bash$ /usr/local/sicstus4.5.0/bin/sicstus
SICStus 4.5.0 (x86_64-darwin-17.7.0): Thu Jan 17 17:17:35 CET 2019
Licensed to SICS
| ?- consult(test).
% ...
| ?- listing.
maplist_inliner:maplist(A, B) :-
        lists:maplist(A, B).

maplist_inliner:maplist(A, B, C) :-
        lists:maplist(A, B, C).

p_1(A) :-
        writeq(call(p_1(A))).

p_2(A, B) :-
        writeq(call(p_2(A,B))).

p_3(A, B, C) :-
        writeq(call(p_3(A,B,C))).

test(A) :-
        B=a,
        (   foreach(C, A),
            fromto(B, D, D, _)
        do  p_2(D, C)
        ).

test(A, B) :-
        (   foreach(C, A),
            foreach(D, B)
        do  p_2(C, D)
        ).

test_1(A, B) :-
        (   foreach(C, A),
            fromto(B, D, D, _)
        do  p_2(D, C)
        ).

test_1(A, B, C) :-
        (   foreach(D, A),
            foreach(E, B),
            fromto(C, F, F, _)
        do  p_3(F, D, E)
        ).

test_noinline(A, B, C) :-
        D=p_3(C),
        lists:maplist(user:user:D, A, B).

Beware. I have not tested this more than a few minutes.

Testing goal expansion of meta-predicate maplist

Simple sample use case #1

1 Answers