Prolog DCG: find last element

Question

I am trying to understand the use of DCGs better. In order to do this, I tried to translate some exercises in the LearnPrologNow book to DCG notation. However, I am failing miserably.

What I tried to write a program that simply names the last element in a list. That's all. I just can't think of the right DCG syntax to do this. I think I figured out the 'base case' which should be:

last --> [X|[]].

Where X is the last element. How do I make Prolog go down the list recursively? Or am I thinking about DCGs in a wrong way?

Sipes

Answer 1

... --> [] | [_], ... .

list_last(Xs, X) :-
   phrase((...,[X]), Xs).

This is clearly the most "graphical" definition. You can describe a lot of patterns with ... //0.

Grammars are a way to describe a language. So your question about how to make Prolog go down is malposed. Grammars don't do anything. They if you insist "generate" sentences.

For the procedural details, you need to understand termination, but no more than that.

Edit: And if you really care about performance, then measure it first. With SWI, I obtain the following. Note the usage of an extra library to remove the calling overheads for phrase/2.

?- use_module(library(apply_macros)).
%   library(pairs) compiled into pairs 0.00 sec, 22 clauses
%  library(lists) compiled into lists 0.01 sec, 122 clauses
%  library(occurs) compiled into occurs 0.00 sec, 14 clauses
% library(apply_macros) compiled into apply_macros 0.01 sec, 168 clauses
true.

?- [user].
**omitted**
?- listing.

dcg_last(B, A) :-
        last(A, B, []).

list_last(A, C) :-
        ...(A, B),
        B=[C].

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

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

:- thread_local thread_message_hook/3.
:- dynamic thread_message_hook/3.
:- volatile thread_message_hook/3.

true.

?- length(L,100000), time(list_last(L,E)).
% 100,000 inferences, 0.018 CPU in 0.030 seconds (60% CPU, 5482960 Lips)
L = [_G351, _G354, _G357, _G360, _G363, _G366, _G369, _G372, _G375|...] ;
% 5 inferences, 0.000 CPU in 0.000 seconds (94% CPU, 294066 Lips)
false.

?- length(L,100000), time(dcg_last(L,E)).
% 100,001 inferences, 0.033 CPU in 0.057 seconds (58% CPU, 3061609 Lips)
L = [_G19, _G22, _G25, _G28, _G31, _G34, _G37, _G40, _G43|...] ;
% 2 inferences, 0.011 CPU in 0.023 seconds (49% CPU, 175 Lips)
false.

So both are performing roughly the same number of inferences, but dcg_last/2 is slower, since it has to pile up all those useless choicepoints. list_last/2 creates the same number of choice-points, however, they are almost immediately removed. So we have 0.018s vs. 0.033s+0.011s.

Guardado

Answer 2

You are missing the recursive step, and making the base clause more complex than needed.

dcg_last(List, E) :-
    phrase(last(E), List).

last(E) --> [_], last(E).
last(E) --> [E].

last//1 just skips any element, until to last. The key, however, is how phrase/2 translates productions. phrase(last(E), List) is equivalent to phrase(last(E), List, []), that is, the grammar must consume all input.

Imogene

-1: Your version is consuming space proportional to the length of the list. – Guardado

+1: On the other hand, it takes less than half the number of inferences compared with the version @false. – Surovy

@PauloMoura: How do you count inferences. I get (almost) the same number and a much better runtime. See edit. – Guardado

I did the same experiment as in your edited answer but without using the apply_macros library, which I agree it should be used whenever available (the question is agnostic on the Prolog system). Voting up your proposed solution. – Surovy

Answer 3

This isn't an answer! CapelliC explains it. It's just the comments are useless for formatted code, and this comment belongs below his answer :

If you use the 'listing.' predicate on his answer after consulting it, this is what prolog has rewritten it to, and will execute :

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

dcg_last(B, A) :-
    phrase(last(A), B).

So DCGs are just syntactic sugar on top of regular prolog expressions - a recursive loop as explained - you have to go through the list ('consume all input') to reach the end.

Protectionist