RE: [xri] Decision on Ref "backtracking" issue

Drummond,

Response to your previous message:

At this point, it is not a matter of “simplicity”, as you mention in your email. I am attempting to judge if your version is programmatically correct – that is, does the flowchart express the correct Ref traversal behavior. (As it stands, the correctness of your flowchart cannot really be determined. I attempt to explain why below.)

> The rule I folowed was that the "Go to Reference Selection" box was no longer a "handoff" but just a "subroutine" that always returned you to the same flowchart so you continued from there.

My question was actually about the "Go to Authority Resolution Flowchart". I wanted to know whether or not you intended that to be on the same stack frame.

It is very much a moot point, anyway, because flowcharts simply cannot express the return being on a separate stack frame. (Nor can they directly represent recursion, since that involves separate stack frames.)

Why does this guy keep harping about the freaking stack?

At this point I need to again regurgitate the reasons why a stack is required (if even just abstractly, as in my approach) to maintain the nested traversal contexts for our Ref graph traversal.

We need to save the previous traversal contexts in order to obtain the “next” Ref from a given context (for the case that sibling refs are to be traversed when a previous one fails.)

We need to save the previous traversal contexts in order to perform the XML bracketing (the output of the XRDS which surrounds inner nested Ref traversals.)

Note that our Ref traversal is really just plain old standard graph traversal. Wikipedia has it right: one cannot perform this type of traversal without using an explicit or implicit stack to push and pop previous traversal contexts. (http://en.wikipedia.org/wiki/Stack_(data_structure).)

Attempting to represent (using a flowchart) an algorithm that performs graph traversal (requiring a stack) can be done. But one must be careful. For example, here are two valid ways.

Represent the stack explicitly. Here is an example that does this: http://www.freepatentsonline.com/6356902.pdf. (By the way, this flowchart IS programmatically correct.)

Do what I did in my version and “abstract out” the entire graph traversal (and thus the stack/recursion) from the flowchart. This is precisely what is done by my box “Get XRD for Ref”. Yes, that box performs a recursive invocation of the entire Authority Resolution phase in order to perform the nested graph traversal. But no more needs to be said about it in the flowchart. That part has been abstracted out. (Note that I do not attempt to “Go to” the start of authority resolution, because that would be attempting to implement graph traversal within the flowchart, and this cannot be done without an explicit stack. More below.)

Your approach to the flowchart falls in neither of two categories above. It attempts to “Go to” the beginning of Authority Resolution in a non-recursive manner (because flowcharts don’t allow recursion) and it attempts to somehow represent the graph traversal logic required by (1) and (2) above without dealing with the concept of nested traversal contexts.

The correctness of your flowchart cannot be evaluated, because statements like: “From the current XRD, get next highest level Ref” have no meaning outside of a traversal context. (At which traversal context does the current XRD exist?) You asked in your previous email if this was an implementation decision. It is not, because what we are talking about here is “can someone follow our intended logic from the flowchart”. The answer is no, because, as I said, the graph traversal logic, by definition, cannot be expressed without the notion of pushing and popping traversal contexts in a stack. (Representing graph traversal without a stack is akin to trying to represent a flow chart without being able to use the conditional box. The algorithm simply cannot be expressed.)

Again, my approach in (b) simplifies the entire issue by entirely abstracting away the graph traversal from the flowchart. Any part of the flowchart always deals with a single traversal context. Here is the most crucial element of my approach: I never attempt to “Go to” the start of authority resolution. The moment that I attempt to do something like that is the moment the flowchart starts trying to implement the graph traversal, and the moment I must explicitly represent a stack in the flowchart.

These are difficult concepts, and we don’t have a whiteboard. It’s hard to get through it, but we will.

~ Steve

From: Drummond Reed [mailto:drummond.reed@gmail.com]
Sent: Saturday, January 21, 2006 6:15 PM
To: Steve Churchill
Cc: drummond.reed@cordance.net
Subject: Re: Updated flowcharts per Steve's recursion point

Steve,

Yes, I am getting rest, and China is pretty awesome. Just wish I had the time to explore it vs. getting all this work done.

Anyway, good questions you ask. Here's my high-level answer: from a SPEC standpoint, I don't think it matters whether the stack frame is implicit or explicit. If I understand you right, that's an implementation decision. The spec merely needs to make the logical flow clear and unambiguous.

The key criteria that I would apply then is simplicity. What's the simplest way to depict the recursive nature of reference processing that produces the nested XRDS documents? What I sent you was the simplest way I could think of to show it. The rule I folowed was that the "Go to Reference Selection" box was no longer a "handoff" but just a "subroutine" that always returned you to the same flowchart so you continued from there. I then followed it with Authority Resolution, which either returns an XRDS document or an error. So that's the recursion.

Does this work now? Or do you think there's a simpler, clearer way to do it?

=Drummond

On 1/20/06, Steve Churchill <steven.churchill@ootao.com> wrote:

Drummond,

I hope that things are going well on your trip. I hope you are managing to get some sleep and rest.

I'm trying to understand where the stack fits in with the current flowcharts.

As correctly pointed out on the wikipedia reference I sent, a stack is *required * for the type of traversal taking place for ref processing. Either it needs to be explicit – by the code managing its own stack structure, or implicit – by the code using the runtime call stack via recursion.

Here's my question: when I see a box in the flowchart that says, for example, "Go to Authority Resolution Flowchart" (as in the Auth-Res flowchart) do you intend that (1) execute as a loop on the existing stack frame or (2) to execute as a procedure call causing a new call stack frame?

I'm asking this, because, in order to understand the Ref traversal of the current flowcharts, I need to understand how the stack is being pushed and popped. Note that (1) above implies that a single procedure (stack frame) has code that is branching back to itself (so an explicit stack structure would be needed to handle the traversal.) In the case of the Auth-Res flowchart saying "Go to Authority Resolution Flowchart" then (2) would imply recursion.

Upon your answer, I will respond with further comments.

Thx,

~ Steve

From: Drummond Reed [mailto: drummond.reed@gmail.com]
Sent: Friday, January 20, 2006 7:55 AM
To: steven.churchill@ootao.com; les.chasen@neustar.biz; William.Tan@neustar.biz; gwachob@visa.com
Cc: drummond.reed@cordance.net
Subject: Updated flowcharts per Steve's recursion point

[I'm sending from my Gmail account because it's clear most of my regular SMTP outgoing email is not getting out from China. Please Reply All so I get the reply via my Cordance account because incoming email seems to work fine.]

Steve and Res editors:

Steve sent me a note pointing out I still didn't get the recursive nature of reference processing correctly in the ED 04 version of the flowcharts (despite him having sent me two corrections to that effect.) My fault. I finally got the time tonight to make the corrections.

Steve, please look over the attached Visio file. The key change was to the Auth-Res page, of course, but in fact all the flowcharts that had a Go To Reference Processing call on them had to be updated because now the recursion loop must be shown on each flowchart that calls for reference processing.

It was well worth doing for another reason -- I caught a flaw in the Default Type Selection flowchart where if you started looking for a Path match but didn't find one and switched over for looking for a default Type match ($res*local or $res*path), and you didn't find that either, so you started reference processing, if you subsequently resolve the Ref and get a new XRD, you need to "start again" checking for a Path match first before switching back to looking for a default type.

I had missed that in the ED 04 flowchart. Fixed now.

Anyway, Steve, let us all know if these updated flowcharts fix the recursion problem (and if not, please modify them until they do, then send them back to me.)

Meanwhile I'll start looking over the comments Gabe sent.

=Drummond

xri message