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