search

triska / the-power-of-prolog

Introduction to modern Prolog
https://www.metalevel.at/prolog
1.21k stars 75 forks source link

Confusing step in DCG left-recursion solution #9

Open jeremy-w opened 5 years ago

jeremy-w commented 5 years ago

We can do this by introducing two additional arguments that let us limit the number of rule applications to the given list's length: (https://www.metalevel.at/prolog/dcg)

As a reader, it’s not clear to me why there are two arguments, or what’s up with the sharing between LS1 in the left/right descents.

I suspect there is one or two intermediate steps to arrive at that solution, that you are able to leap straight past thanks to running across the problem many times before. For a newcomer, though, it leaves a mystery.

If you could elaborate on how this works within the chapter, that would be very helpful!

triska commented 5 years ago

Thank you for this highly appropriate suggestion! The basis for this step is found in the important concept of list differences.

This was so far only briefly mentioned, and I have now added several new paragraphs about it, please have a look:

https://www.metalevel.at/prolog/dcg#leftrecursion

What do you think, does it help?

jeremy-w commented 5 years ago

Yes, it does. I had to read and think on it a bit, but I could follow along. I think this specific example was especially helpful:

We can interpret the difference of these lists as describing the list of elements that are consumed by the first recursive invocation of tree_nodes//3 in this example.

Explaining it to myself, I see the two args as, arg 1 “you have this much list to work with”, arg 2 “and you left this much unused”. Then the flow from the first recursive call to the second makes sense as parceling out the overall list.

I appreciated the further words on list differences vs difference lists. The clarifications throughout the book on what constitutes modern Prolog vs legacy Prolog have been a big help in understanding what Prolog can do today.

triska commented 5 years ago

Explaining it to myself, I see the two args as, arg 1 “you have this much list to work with”, arg 2 “and you left this much unused”

Yes, this is applicable in this case, since it assumes the list is given when the rule is invoked and this is indeed the main point of the example. However, this wording would not completely do justice to the versatility of the actual relation, which also works if the list is not specified in any way. In that case, it yields the number of tokens that are needed for this rule to apply. I am always striving for formulations that encompass all possible usage modes, and so I have worded this in such a way that both cases are subsumed, even though one direction is emphasized much more strongly.

Thank you very much for your kind feedback and for this suggestion!

triska commented 5 years ago

I have created a small video to explain list differences in more detail, please have a look:

https://www.metalevel.at/prolog/videos/list_differences

It's work in progress... however, I hope you find it useful!