Wiki Discussion: LCO

This is a topic to discuss the Wiki

Wiki: LCO

I wonder who invented the hyphen in last call:

Welcome to SWI-Prolog (threaded, 64 bits, version 8.1.22)
?- length(1,X).
ERROR: Type error: `list' expected, found `1' (an integer)
ERROR: [11] throw(error(type_error(list,1),context(...,_2148)))
ERROR: [9] <user>
ERROR: Note: some frames are missing due to last-call optimization.
ERROR: Re-run your program in debug mode (:- debug.) to get more detail.

Well if Princeton writes it like this, then hell it must be correct with hyphen:

The Implementation of Prolog
Chapter 7: Last-Call Optimization

My English is not that good, but “last call optimization” is rather ambiguous. Is this the last time we do call optimization or do we optimize the last call?

I have never found fault with your English :grinning:, but then I do not have a degree in English, so I don’t see a need for it is not that good. I am sure if others did not know it was not your native language, they would not know. My English could be better but my spelling is horrendous.

Truthfully I never though of it as being ambiguous and I have no problem changing it to last-call optimization where it is last call optimization.

I will wait to other have had a chance to read this and reply before possibly making a change.

Well its then correct in the SWI-Prolog error message (with hyphen):

BTW: The Princeton book defines last-call optimization as follows:


Interestingly, when programming with LCO in mind, this might lead
to slower code for non-deterministic calls. Take this example:

permute1([], []).
permute1([X|Rest], L) :-
    permute1(Rest, L1),
    select(X, L, L1).

permute3([], []). 
permute3([H|T], [P|P1]) :- 
    select(P, [H|T], L1), 
    permute3(L1, P1). 

The [H|T] is not the issue, as stack overflow shows. This is
the time measurement of the two variants:

SWI-Prolog (threaded, 64 bits, version 8.3.0)

?- time((permute1([1,2,3,4,5,6,7,8,9,0],_), fail; true)).
% 4,447,038 inferences, 0.523 CPU in 0.526 seconds (99% CPU, 8508651 Lips)

?- time((permute3([1,2,3,4,5,6,7,8,9,0],_), fail; true)).
% 25,963,501 inferences, 1.472 CPU in 1.492 seconds (99% CPU, 17637265 Lips)

Edit 01.06.2020:
The problems are even more drastic in GNU-Prolog:

GNU Prolog 1.4.5 (64 bits)

?- permute1([1,2,3,4,5,6,7,8,9,0],_), fail; true.
(230 ms) yes

?- permute3([1,2,3,4,5,6,7,8,9,0],_), fail; true.
(1269 ms) yes