simple prolog explanation of string manipulation

Question

just need a simple explanation.. trying to piece everything still together here.

lastitem([X|Xs],Out) :- lastitem(Xs,Out).

here is trace on: lastitem([a,b,c],X).

[trace] 8 ?- lastitem([a,b,c],X).
   Call: (6) lastitem([a, b, c], _G536) ? creep
   Call: (7) lastitem([b, c], _G536) ? creep
   Call: (8) lastitem([c], _G536) ? creep
   Exit: (8) lastitem([c], c) ? creep
   Exit: (7) lastitem([b, c], c) ? creep

step 1 says if lastitem(something,somethign) exists then listem([X|Xs],Out].. so A is cut out. step 2-3 does the same.. but w/ B and C. now question is what happens w/ the empty list in step 4? why does the empty list not fulfill lastitem(Xs,Out)? or am I solving incorrectly?

Also a verbal explanation of backtracing would help.. because in append I'm really getting twisted. Append has no goals to solve between steps.. yet reverse does not.. nor does my answer above.. if you trace it you can see the X variable is always the same in reverse or this example. in append it changes.

append([],L,L).
append([H|T],L2,[H|L3]) :- append(T,L2,L3).

append([a, b, c], [1, 2, 3], _G518) % <-- variable L3 continues to change
append([b, c], [1, 2, 3], _G587) % <-- same
append([c], [1, 2, 3], _G590) % < -- same
append([], [1, 2, 3], _G593)  % <-- same
append([], [1, 2, 3], [1, 2, 3])
append([c], [1, 2, 3], [c, 1, 2, 3])
append([b, c], [1, 2, 3], [b, c, 1, 2, 3])
append([a, b, c], [1, 2, 3], [a, b, c, 1, 2, 3])

X = [a, b, c, 1, 2, 3]

hugomg hugomg · Accepted Answer · 2011-05-01T16:56:38

Just as you, I'm confused by the absence of a base case in lastitem. Are you sure it wasn't actually defined as

lastitem([X|[]], X).
lastitem([X|Xs],Out):- lastitem(Xs,Out).

or something similar?

As for all the backtraces, try to not think too imperatively when looking at Prolog code. For example, append can be "translated" to a more usual functional definition:

function append(xs, ys) = 
    if xs is [] then
        return ys
    else
        let [H|L] = xs
        return [H | append(L, ys)]

Unterstanding this goes a long way to understanding the Prolog version :)

simple prolog explanation of string manipulation

2 Answers