Tail Recursion

Discussions related to Visual Prolog
Martin Meyer
VIP Member
Posts: 290
Joined: 14 Nov 2002 0:01

Tail Recursion

Unread post by Martin Meyer » 5 Jan 2017 22:23

Hello Thomas and all,

below code covers some constructions for exploring tail recursion (in VIP7502). There are four different versions of a predicate which devides up an input list into two output lists. The items of the input list come with a flag. The items flagged false are distributed to the 1st output list, items flagged true are distributed to the 2nd output list.

I set a break point at the first clause of each version of the predicate. By repeatedly typing F5 I am stepping through the execution. While doing so, I am watching the Run Stack window. When the stack is growing on each recursive entry to a predicate's version, I conclude that this version is not tail recursive. Whereas when the stack usage stays constant, the version is tail recursive.

The outcome of the test is:
  • 1st version is -as expected clearly- tail recursive.

    2nd version turns out to be also tail recursive. The compiler is doing a clever job here.

    3rd version proves to be not tail recursive. It surprises me that the 3rd version makes a difference to the 2nd version.

    4th version has an entirely unexpected result for me: It is not tail recursive.
So, my question is: How to tell from the code, whether a predicate is tail recursive? The simple rule that the recursive call must be the final action does apparently not tell the whole story. In particular, what counts as an action which has to be completed after a call and thereby precludes it from the tail call optimization?

Code: Select all

class predicates     devideUp1 : (         tuple{string Item, boolean Flag}* FlaggedList,         string_list FlagOffList [out],         string_list FlagOnList [out]). clauses     devideUp1([tuple(Item, true) | RestFlaggedList], RestFlagOffList, [Item | RestFlagOnList]) :-         devideUp1(RestFlaggedList, RestFlagOffList, RestFlagOnList).     devideUp1([tuple(Item, false) | RestFlaggedList], [Item | RestFlagOffList], RestFlagOnList) :-         devideUp1(RestFlaggedList, RestFlagOffList, RestFlagOnList).     devideUp1([], [], []).   class predicates     devideUp2 : (         tuple{string Item, boolean Flag}* FlaggedList,         string_list FlagOffList [out],         string_list FlagOnList [out]). clauses     devideUp2([tuple(Item, Flag) | RestFlaggedList], FlagOffList, FlagOnList) :-         if Flag = true then             devideUp2(RestFlaggedList, FlagOffList, RestFlagOnList),             FlagOnList = [Item | RestFlagOnList]         else             devideUp2(RestFlaggedList, RestFlagOffList, FlagOnList),             FlagOffList = [Item | RestFlagOffList]         end if.     devideUp2([], [], []).   class predicates     devideUp3 : (         tuple{string Item, boolean Flag}* FlaggedList,         string_list FlagOffList [out],         string_list FlagOnList [out]). clauses     devideUp3([tuple(Item, Flag) | RestFlaggedList], FlagOffList, FlagOnList) :-         if Flag = true then             devideUp3(RestFlaggedList, RestFlagOffList, RestFlagOnList),             FlagOffList = RestFlagOffList,             FlagOnList = [Item | RestFlagOnList]         else             devideUp3(RestFlaggedList, RestFlagOffList, RestFlagOnList),             FlagOffList = [Item | RestFlagOffList],             FlagOnList = RestFlagOnList         end if.     devideUp3([], [], []).   class predicates     devideUp4 : (         tuple{string Item, boolean Flag}* FlaggedList,         tuple{string_list FlagOffList, string_list FlagOnList} Result [out])         procedure (i, tuple(o, o)). clauses     devideUp4([tuple(Item, true) | RestFlaggedList], tuple(FlagOffList, [Item | RestFlagOnList])) :-         devideUp4(RestFlaggedList, tuple(FlagOffList, RestFlagOnList)).     devideUp4([tuple(Item, false) | RestFlaggedList], tuple([Item | RestFlagOffList], FlagOnList)) :-         devideUp4(RestFlaggedList, tuple(RestFlagOffList, FlagOnList)).     devideUp4([], tuple([], [])).   clauses     run() :-         FlaggedList = [tuple("pu", true), tuple("com", false), tuple("ter", true)],           devideUp1(FlaggedList, FlagOffList1, FlagOnList1),         stdIO::write(FlagOffList1, FlagOnList1, '\n\n'),           devideUp2(FlaggedList, FlagOffList2, FlagOnList2),         stdIO::write(FlagOffList2, FlagOnList2, '\n\n'),           devideUp3(FlaggedList, FlagOffList3, FlagOnList3),         stdIO::write(FlagOffList3, FlagOnList3, '\n\n'),           devideUp4(FlaggedList, tuple(FlagOffList4, FlagOnList4)),         stdIO::write(FlagOffList4, FlagOnList4, '\n\n').
Regards Martin

User avatar
Thomas Linder Puls
VIP Member
Posts: 1625
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls » 7 Jan 2017 14:00

We will look at case 3 which should be tail recursive, the use of such extra variables should not really affect the generated code.

The other cases behaves as expected.

For case 4 there is a computation after the recursive call has returned: the returned tuple is split and then another tuple is created from the components.

At first look case 1 and 2 may also appear to require a computation after the recursive call, because each of them appears to be creating a list from an existing element and a returned element. But output elements are actually not returned, actually we pass an address to where the result should be placed. Therefore we can allocate the list cell before of the recursive call and pass the address of the tail in that cell as the result location. And then the call is suddenly last.

By the way we don't distinguish between recursive calls and other calls, and therefore we just use the phrase "tail call optimization".
Regards Thomas Linder Puls
PDC

Martin Meyer
VIP Member
Posts: 290
Joined: 14 Nov 2002 0:01

Unread post by Martin Meyer » 7 Jan 2017 18:52

Thomas, thank you for the info!

Does it mean, calls to predicates, which are declared with an output functor flow (and no alternative non-functor output flow), are never tail optimized?

I thought, that the flow tuple(o, o) in the declaration of devideUp4 had the effect, that in calls to devideUp4 the variables supplied in the places of FlagOffList and FlagOnList are treated as two output elements (in contrast to handling tuple(FlagOffList, FlagOnList) as one output element, which needs to be split into components). Is there a reason, why it does not work that way?
Regards Martin

User avatar
Thomas Linder Puls
VIP Member
Posts: 1625
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls » 8 Jan 2017 14:57

All-out functor flows could be treated like that, but we don't. We don't use such flows very often and subsequently we haven't put much effort into such constructions.
Regards Thomas Linder Puls
PDC

Martin Meyer
VIP Member
Posts: 290
Joined: 14 Nov 2002 0:01

Unread post by Martin Meyer » 8 Jan 2017 16:29

Yes, I also use functor flows seldom.

Thanx again for answering.
Regards Martin

Post Reply