On Fri, Jun 24, 2011 at 9:27 AM, silviaumiliacchi(a)libero.it <silviaumiliacchi(a)libero.it> wrote:

Good Morning,

I'm a post-graduate student at University of Bologna. For my final thesis, I'm collecting informations about tail call optimization in a Prolog system. I read many articles on the web, and I found in Wikipedia that Ciao implements tail call optimization. My doubt is about  when it is correct to perform this optimization; for example, when the query catch(Goal1, Arg, Goal2)  calls the throw/1 predicate during the execution of Goal1, execution must go back to the catch predicate and proceed with Goal2. So, I think that no stack optimization can be performed in presence of this query and consequently it has to be disabled. I haven't found any documents that confirm my thought and the ISO standard doesn't specify anything on it. Please, can you help me?

Thank you in advance and kind regards, Silvia Umiliacchi

Dear Silvia,

Last call optimization (LCO) removes frame environments when possible, thus transforming some recursions into loops. That optimization is done at compile time when possible. There are many papers in the literature where you can find a more detailed description (H. Ait-Kaci. Warren's Abstract Machine, A Tutorial Reconstruction). Basically, given a clause:

p :- g1, g2, ..., gn1, gn.

the compiler translates it into code (e.g., bytecode) that, between 'gn1' and 'gn', makes sure that all the arguments required for 'gn' live in temporal registers, removes the environment frame, and jumps to 'gn'.

In order to reason about catch/3 and throw/1 you need some detailed description of their semantic. Suppose a clause like:

foo :- ..., catch(bar, ..., ...).

If your question is whether LCO is able to remove the environment created for 'foo' before calling 'bar', the answer is no. At least, you need to 'uninstall' the exception handler when returning from 'bar'. To do that, you need to keep some information in the enviroment. I do not think that it could be optimized (at least I am not aware of any Prolog system which does).

Cheers