Using prolog "as intended"

[Sanjuro]

I wanted to share a story and would like to have your opinion on this.
I recently passed my prolog exam at Uni, During which i was asked to write a predicate to invert a list.
I came up with something like this:

rev(A,B):-
    rev(A,B,[]).

rev([],B,B):-!.
rev([X|A],B,C):-
    rev(A,B,[X|C]).

He hated this code and said that writing an accumulator in prolog meant i did not really understand the “soul” of prolog which is purely predicative: he argued that you should be able to read every predicate in a way that makes logical sense such as “rev(A,B) is true if B is the reverse of A” and that rev(A,B,C) simply did not make logical sense.
He asked me to write it without an accumulator and with only two arguments, i panicked and ended up with a very low grade.
What is your opinion on this? Is he right? Or is this an exaggerated scholastic approach to the language?

[Sanjuro]

i just wanted it to find one solution, if i didn’t add the cut the predicate rev(A,[1,2,3]) for example would have looped infinitely after finding the first one

[peter.ludemann]

Accumulators are a classic technique in both logic programming and functional programming, and are related to the notion of passing around state in languages that don’t allow mutable state.

There’s a difference between a program that’s logically correct and one that’s both logically correct and efficient. Otherwise, this would be a fine solution to “sort a list”:

sort_list(Unsorted, Sorted) :-
    permutation(Unsorted, Sorted),
    is_sorted(Sorted).

% permutation/2 - see https://www.swi-prolog.org/pldoc/man?predicate=permutation/2

is_sorted([]).
is_sorted([_]_.
is_sorted([X1,X2|Xs]) :-
    X1 @=< X2,
    is_sorted([X2|Xs]).

which is probably the most inefficient sort program possible. (I wonder what your professor would think of it? And if he thinks it’s fine, you might want to follow up with questions about prime factorization and cryptography)

[Sanjuro]

this is really cool, is there a performance advantage on using this instead of cuts?

[Sanjuro]

@j4n_bur53

But its unlikely that you learn this in University.

meh most of the stuff we learned was on our own mostly because of the pandemic, and that’s why i didn’t know he hated accumulators.

[EricGT]

I think the means your instructor seeks is based on difference list.

See: Prolog difference list. This is not the best explanation of it, but the first one I found. I just don’t feel like writing the code myself and then having to explain it.

The key thing you want to seek when looking for this is rev/2 as done in the example and not use a helper as rev/3 as you did in your initial answer.

---

This begs the question.

Did your instructor teach you about difference list?

[peter.ludemann]

You could implement reverse with DCGs, which have an implicit difference list:

rev(Forward, Backward) :-
    phrase(rev(Forward), Backward).

rev([]) --> [].
rev([X|Xs]) -->
    rev(Xs),
    [X].

The DCG expansion results in this:

rev([], A, A).
rev([X|Xs], A, B) :-
    rev(Xs, A, C),
    C=[X|B].

which simplifies to the original code in this thread. (The accumulator is still there - but hidden by use of DCG).

[EricGT]

Thanks.

I didn’t want to spend the time writing it then checking. Also Sanjuro is probably so lost at this point he could spend many months or more having us sort it all out.

[peter.ludemann]

DCGs are very much in Prolog “as intended”. (I once heard a joke that Colmerauer and Roussel invented DCGs first and generalized them to Prolog.)

As my code demonstrates, DCGs have the concept of accumulator built-in; so, accumulators are also very much part of Prolog “as intended”, whether using difference lists or other techniques.

(And if you like accumulators, you’ll love extended DCGs, which allow multiple accumulators, defined using things other than difference lists.) (Peter Van Roy invented EDCGs when writing a compiler for Prolog.)

[frayser]

Declaratively, the reverse is:

The reverse of the tail followed by the head

as in

rev([H|T],Rev) :-
	rev(T, RevT),
	append(RevT,[H],Rev).
rev([],[]).

[EricGT]

For a different implementation of rev/2 see the SWI-Prolog implementation of reverse/2.

reverse(Xs, Ys) :-
    reverse(Xs, [], Ys, Ys).

reverse([], Ys, Ys, []).
reverse([X|Xs], Rs, Ys, [_|Bound]) :-
    reverse(Xs, [X|Rs], Ys, Bound).

Examples

Welcome to SWI-Prolog (threaded, 64 bits, version 8.3.5-8-ge14460a94)

?- reverse([],[]).
true.

?- reverse([a],[a]).
true.

?- reverse([a,b],[b,a]).
true.

?- reverse([a,b,c],[c,b,a]).
true.

?- reverse([a,b,c],R).
R = [c, b, a].

?- reverse(R,[a,b,c]).
R = [c, b, a] ;
false.

If you want to single step the code in detail use gtrace/0.

[dtonhofer]

@Sanjuro

He hated this code and said that writing an accumulator in prolog meant i did not really understand the “soul” of prolog which is purely predicative: he argued that you should be able to read every predicate in a way that makes logical sense such as “rev(A,B) is true if B is the reverse of A” and that rev(A,B,C) simply did not make logical sense.

Pardon my french but if you supervisor said it like that this is nonsense and he is chasing after a platonic ideal that simply cannot exist. Especially as he’s talking about a helper predicate.

If your code passes the test case (which may exercise it “both ways” … or not) then it’s good (unless it really burns RAM and CPU in unhealthy fashion).

Prolog is for programming, and only in a second degree for modeling in logic (which logic? a fragment of 2-valued constructive positive logic, with negation-as-failure as a bolted-on sidecar giving you nonomotonic behaviour; yes I like it; it’s wild, but I really would like strong negation too. How? I don’t know.).

Prolog is not a theorem prover that tries to suss out mathematical truths. This is made immediately evident by the fact that it never outputs a solution in closed form: {x :: 0<x,x<=4} etc. It only outputs witnesses, one after the other: 1,2,3,4. The semantics are often unclear (does atom(X) mean “enumerate the atoms?” What is a variable `X? Does it stand for an unknown? A receptable for some witness value? Something to be manipulated (awkwardly) by the program maybe? It depends! Look at the builtin predicates many are clearly not “predicates” in any shape: they are transformers between types, queries regarding the state of the computation, some interface to the underlying machine. A predicate “failure” often has nothing to do with a failure in a problem in logic but a failure that has actually to do with computation (“I couldn’t write out to STDOUT; fail!”) etc.

Trying to follow some platonic ideal will:

• Make your burn time trying to solve unnecessary problems to make a function work “both ways” or “multiways” for no good reason. And if you do so you will find out that the two-way predicate decomposes in any case into two one-way predicates which you have to select based on completely non-logical “predicates” like var(X) to examine the input arguments - that’s not a win. Just disallow certain uses of the predicate with assertions and move on.
• Make you avoid using excellent non-logic programming techniques like meta-calls and cuts. (Disclaimer: I like my cuts “green” i.e. removable without change in program meaning)
• Cause you to write weird predicates that become swiss army knifes and are potentially confusing to the next person who reads your code (“where is the input? where is the output? what do you mean it depends?”). For example succ/2 is nice, but is really worth to have have it work both ways instead of just writing pred/2 separately? A lot of coding is making intention clear and in a lot of Prolog code the intention is obscured … you have to scan it slowly to understand the data flow of a specific case.
• Functional programming is simpler that way: You know where the stuff comes out, and I do think that’s a big advantage. Maybe we are making our life harder than it should be? So why Prolog? I don’t know yet! In fact, using functional style mainly and logic style / nondeterminism occassionally sounds like a very good heuristic (actually, is unavoidable). The future may be much more like Curry or some functional language with nondeterminism and the logic modeling part will be clearly identified as modeling. We will see.

All right, enough ranting.

Here’s an old post about the Dangers of Purity in relation to Haskell (Trigger warning: Juvenile humor)

https://www.reddit.com/r/ProgrammerHumor/comments/6csxb0/after_all_youve_tasted_haskell_shes_not_like/

[dtonhofer]

Hating the accumulator is like hating oxygen.

You will feel bad pretty quickly.

Notes on Prolog list processing idioms

[Boris]

Let’s not throw oil on the fire here. University is what it is, and professors are just people. Also, we have no idea what is the stated aim of the course that @Sanjuro is taking. Maybe it is “Prolog programming”, maybe it is “Logic programming”, maybe it is something completely different. I did study “computer science” and learning how to program was not the aim of the whole study at all. You were supposed to learn other things, and learning to program was left to the individual, if they felt they need it.

Yes, I did have to write Prolog in two courses (by the same professor…) and I have a faint memory that at one point I was supposed to “write a predicate” that implements the A* search algorithm, and when I allowed myself to use helper predicates I failed the project and had to do another one, the semester after. Not sure what is the moral of the story.

[GeoffChurch]

EDCGs look like a nice, natural generalization of DCG syntax. Mercury seems to have a similar, but more explicit/verbose solution in the form of state variables.

The two approaches are mentioned in this section on DCG syntax.

It seems like it could be an easy way to naturally transform an imperative language into a relational language, by turning any mutated variables into accumulators. Basically just environment passing but the environment is as tucked-away as possible.

[mcculloch]

I know I’m late to the party here. But, I had a thought about this and wanted to know what others thought about this. Isn’t the accumulator a way to create tail-recursion? I always try to make stuff tail recursive and it almost always needs at least one extra argument in the “work-horse” predicate. So, if the purpose is to make a beautiful solution, maybe minimizing arguments is the right way, but memory efficiency requires extra arguments.

[Boris]

@mcculloch

if the purpose is to make a beautiful solution

Beauty is in the eye of the beholder and so on

I had to attend a course on “scientific writing” once; the teacher was a chemist. His was apparently qualified to teach that course because he was a native speaker (of the English language). Anyway, he was trying to make a point using an analogy, and he asked, rhetorically, “What is more beautiful? A Horse or a Camel?”

What do you think? (about the answer, or about the question…)

[peter.ludemann]

@Boris

“What is more beautiful? A Horse or a Camel?”

As the old joke goes: a camel is a horse designed by a committee.

But I know which I’d prefer when crossing a desert (careful – they spit!).