FAQFAQ   SearchSearch   MemberlistMemberlist   RegisterRegister   ProfileProfile   Log inLog in 


Tail Recursion

Post new topic   Reply to topic    discuss.visual-prolog.com Forum Index -> Visual Prolog
View previous topic :: View next topic  
Author Message
Martin Meyer



Frankfurt a.M., Germany
Joined: 14 Nov 2002
Posts: 210

PostPosted: 5 Jan 2017 22:23    Post subject: Tail Recursion Reply with quote

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?

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
Back to top
View user's profile Send private message
Thomas Linder Puls



Copenhagen, Denmark
Joined: 28 Feb 2000
Posts: 3077

PostPosted: 7 Jan 2017 14:00    Post subject: Reply with quote

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
Prolog Development Center
Back to top
View user's profile Send private message
Martin Meyer



Frankfurt a.M., Germany
Joined: 14 Nov 2002
Posts: 210

PostPosted: 7 Jan 2017 18:52    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
Thomas Linder Puls



Copenhagen, Denmark
Joined: 28 Feb 2000
Posts: 3077

PostPosted: 8 Jan 2017 14:57    Post subject: Reply with quote

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
Prolog Development Center
Back to top
View user's profile Send private message
Martin Meyer



Frankfurt a.M., Germany
Joined: 14 Nov 2002
Posts: 210

PostPosted: 8 Jan 2017 16:29    Post subject: Reply with quote

Yes, I also use functor flows seldom.

Thanx again for answering.

_________________
Regards Martin
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    discuss.visual-prolog.com Forum Index -> Visual Prolog All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum