Solve this declaratively

[triska]

Dear all,

today I came across a discussion asking for:

Let In = [1,2,-1,4,5,-1,-1,8,9,10] and Replace = [3,6,7,8,9,10], write merge(In, Replace, Out) such that Out = [1,2,3,4,5,6,7,8,9,10] where the predicate replaces -1 elements in turn from the Replace stack.

A Prolog formulation is straight-forward:

:- use_module(library(reif)).

replacement_([], _, []).
replacement_([I|Is], Rs0, [O|Os]) :-
        if_(I = -1,
            Rs0 = [O|Rs],
            (Rs0 = Rs, O = I)),
        replacement_(Is, Rs, Os).

Yielding for example:

?- replacement_([1,2,-1,4,5,-1,-1,8,9,10], [3,6,7,8,9,10], Os).
   Os = [1,2,3,4,5,6,7,8,9,10].

?- replacement_([X,Y], Rs, Os).
   X = -1, Y = -1, Rs = [_A,_B|_C], Os = [_A,_B]
;  X = -1, Rs = [_A|_B], Os = [_A,Y], dif:dif(Y,-1)
;  Y = -1, Rs = [_A|_B], Os = [X,_A], dif:dif(X,-1)
;  Os = [X,Y], dif:dif(X,-1), dif:dif(Y,-1).

In the course of the discussion, I noticed also that the implementation of declarative constructs is brought up. In my opinion, the current implementation of any language construct is not a sensible argument for or against the construct itself. There are constructs that cannot be implemented in Prolog at all without adequate building blocks. An example for this is the SICStus-compatible setup_call_cleanup/3 from library(iso_ext). This predicate must guarantee that Setup is performed protected from interrupts, something that cannot be expressed in pure Prolog. Yet the construct is available, and eminently sensible and useful as a building block for even higher-level constructs such as phrase_from_file/[2,3] in library(pio).

As another example, take library(clpz): There is a lot of room for improvements in the way the library is implemented, see for example the discussions in #2708 and triska/clpz#36 for preliminary observations. Is that a sensible argument against any of the predicates the library exports? In my opinion, no. If it were, then we may as well point for example at the generated binary code of Scryer Prolog and hold it as an argument against Prolog itself. Does the unreadable binary code, or even the produced WAM code, of the Scryer Prolog compiler make any Prolog program worse in any respect? In my opinion, no, because that code does not appear in any way when using the system. In the same way, the implementation of any CLP(ℤ) construct is invisible to Prolog programs that use the library. The point of the library interface is that the implementation can be improved without further notice, and if anyone notices any kind of defect in the implementation, then I hope we can work together to improve it!

Thank you and all the best,
Markus

[hurufu]

It looks like OP wanted to solve it without (explicit) recursion, so here is my attempt:

:- use_module(library(lists)).
:- use_module(library(dif)).

main(R) :-
    replacement([1,2,-1,4,5,-1,-1,8,9,10], [3,6,7,8,9,10], R-_).

replacement(S, P, R-X) :- foldl(repl, R, S, P, X).

repl(P, -1, [P|Ps], Ps).
repl(S, S, Ps, Ps) :- dif(S, -1).

I don't get how recursion isn't declarative though and what's bad about it. At the end everything is running on a CPU which isn't declarative.

[hurufu]

If you want to be really fancy it can be even implemented with this one-liner:

replacement(S, P, R-X) :-
    foldl(\A^B^C^D^if_(-1=B, C=[A|D], (A=B,C=D)), R, S, P, X).

It is very declarative, but I don't consider it a readable code...

[haijinSk]

:- use_module(library(dcgs)).
:- use_module(library(dif)).

replacement([], _) --> [].
replacement([-1|Is], [R|Rs]) --> [R], replacement(Is, Rs).
replacement([I|Is], Rs) --> { dif(I, -1) }, [I], replacement(Is, Rs).

?- phrase(replacement([1,2,-1,4,5,-1,-1,8,9,10], [3,6,7,8,9,10]), Os).
   Os = [1,2,3,4,5,6,7,8,9,10]
;  false.

[haijinSk]

Yes, the recursion... But as @hurufu says, I, too, see it declaratively, here...

[haijinSk]

Speaking of declarativity, Prolog has declarative pointers (a.k.a. logic variables, of course)!

I'm only a very naive Prolog user, but I wanted to use them here (even if in a cumbersome way); I wanted something close to a "Locally defined global identifier" (Michael Hanus) (functional) logic design pattern, I think...

:- use_module(library(dif)).
:- use_module(library(lists)).

repl(-1,_). % -1 will be replaced by "declarative pointer"
repl(N,N) :- dif(N,-1).

uni(WithVars,E) :- memberchk(E,WithVars).

replacement(Is,Rs,Mapped) :-
  maplist(repl,Is,Mapped),
  maplist(uni(Mapped),Rs).

?- replacement([1,2,-1,4,5,-1,-1,8,9,10],[3,6,7,8,9,10],Mapped).
   Mapped = [1,2,3,4,5,6,7,8,9,10]
;  false.

[notoria]

I opened both issues in order to run clpz in a meta-interpreter.

In #2708, the goal is to replace !/0 with (->)/2 and if (->)/2 isn't needed then rewrite the predicate.

In triska/clpz#36, I want to use the directive include/1 to assemble the library.

The end goal is to be able to rewrite clpz from scratch (or at least have a mini-clpz) but for that I need:

• a better understanding of attributed variables and how it's used in clpz.
• a test suite with good coverage of clpz.
• a better understanding of goal/term expansion and how it's used in clpz (all goal expansions have been disable and term expansions are done separately).

And hopefully all the tools around the meta-interpreter get better in relation to goal/term expansion.