DCG memory performance characteristics vs findall/3?

[jjtolton]

I recently (barely) managed to convert some code that was using findall/3 to DCGs in order to, uh... avoid using findall/3 -- to see if I could do an aggregation without "realizing" the entire list in memory.

The original code fundamentally worked like this:

max_string_nonrepeatsubstring(Max, String, MaxSub) :-
        findall(Substring, string_nonrepeatsubstring(String, Substring), Substrings),
        maxlength(Substrings, MaxSub, Max).

the new code works like this:

string_max_nonrepeatsubstring(String, Max, Best) :-
        phrase(substring(String), Substrings),
        phrase(nonrepeating(Substrings), NonRepeatingSubstrings),
        phrase(max_length(NonRepeatingSubstrings), [0, []], [Max, Best]).

?- string_max_nonrepeatsubstring("abcabcbb", Max, Best).
%@    Max = 3, Best = "abc".

?- string_max_nonrepeatsubstring("bbbbb", Max, Best).
%@    Max = 1, Best = "b".

?- string_max_nonrepeatsubstring("pwwkew", Max, Best).
%@    Max = 3, Best = "wke".

Aside from implementation complexity and verbosity, the second version is better in most respects. However, I'm curious if this actually accomplishes the original intent of capturing the max/best while backtracking instead of pulling the entire thing into memory.

So for instance,

string_max_nonrepeatsubstring(String, Max, Best) :-
        phrase(substring(String), Substrings), % is Substrings fully realized before going to next clause?
        phrase(nonrepeating(Substrings), NonRepeatingSubstrings), % is NonRepeatingSubstrings realized before going to next clause?
        phrase(max_length(NonRepeatingSubstrings), [0, []], [Max, Best]).

Does using phrase/2 and phrase/3 with DCGs offer any benefit over findall/3 in regards to memory performance? Besides asking, is there a way to reason about this question? I've learned about using failure-slices and doing declarative debugging to reason about the "flow", but I'm not sure how to apply that when working with DCGs for profiling purposes.