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: In:
ERROR: [11] throw(error(type_error(list,1),context(...,_2148)))
ERROR: [9] <user>
ERROR:
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
https://www.amazon.de/dp/069160939X

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:

Unbenannt

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)
true.

?- 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)
true.

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