How does backtrack wrapping work?

[AndrewSav]

The algorithmic description of same-line wrapping can be described as
backtrack wrapping. It is more of interest to Funge interpreter
implementers than Funge programmers. However, it does describe exactly
how the wrapping acts in terms that a programmer can understand, so we
will include it here.

When the IP attempts to travel into the whitespace between the code and
the end of known, addressable space, it backtracks. This means that its
delta is reversed and it ignores (skips over without executing) all
instructions. Travelling thus, it finds the other 'edge' of code when
there is again nothing but whitespace in front of it. It is reflected
180 degrees once more (to restore its original delta) and stops ignoring
instructions. Execution then resumes normally - the wrap is complete.

It is easy to see at this point that the IP remains on the same line:
thus the name. (Also note that this never takes any ticks in regards
to multithreading, as would be expected from any wrapping process.)

This above is probably most confusing description I've ever read in a spec. And I've read quite a few specs in my life. Please help me understand it and may be improve it, so it's more accessible for everyone.

First of all it is not clear what is "whitespace" above. This word appears two times in the quoted section, and never again before or after in the specification. Without other guidance, we should assume conventional meaning, which is usually a character that represent horizontal or vertical space. In the context of the spec, my best guess, that this is a cell with a space character ASCII 32. If that's not the case, please clarify.

Next, "line" is mentioned in the quoted text, but I'm not sure how to connect this with the previous discussion of lines in the spec. My best guess is based on the following paragaph:

The source file begins at the origin of Funge-Space. Subsequent columns of characters increment the x coordinate, and subsequent lines increment the y coordinate (if one is present) and reset the x coordinate to zero. Subsequent lines in Unefunge are simply appended to the first, and the end of the source file indicates the end of the (single) line.

So I'm assuming that a line, is everything that has the same y coordinate as IP. If this is wrong, please clarify.

When the IP attempts to travel into the whitespace between the code and the end of known, addressable space, it backtracks.

Let's try to decompose this a bit. When IP "travels" it travels from the current node to the next node as specified by the delta. That next node contains a cell which may or may not contain a whitespace. The specification either assumes that it certainly does, or limits the description to the cases when it does. As far as I can see it, the prime case for wrapping, is when there next node does not exist at all because we reached the edge of addressable space. Similarly, it's not clear why would we want to wrap, if we has not reached the end of addressable space yet, on a white space. May be this too could be clarified?

It is easy to see at this point that the IP remains on the same line: thus the name.

This sound as complete non-sequitur. I can see why this may be true if the delta point along the line IP is currently on, but in any other case I cannot see how this could be true.

I feel that this section may benefit from better definition of terms it's using, and simply from better wording. Also it is very hard to see what the diagram is trying to demonstrate. May be a few words tying it to the text somehow could help?

And a small unrelated to the above suggestion: r seems to refer to "reverse" is some parts of the document and to "reflect" in others. I believe that consistency here, or a clear explanation what the relationship between "reflect" and "reverse" is would make the document less confusing. If "reflect" and "reverse" is the same thing, I would suggest choosing a single term (I would vote for "reverse") and use it through the document, not just as the keyword for r instruction, but as well for concepts explanation.

[cpressey]

This above is probably most confusing description I've ever read in a spec. And I've read quite a few specs in my life.

Yes, it's quite impressive, isn't it?

Please help me understand it and may be improve it, so it's more accessible for everyone.

You seem to be assuming that one of the goals of the Funge-98 project is to have a clear specification. If Funge-98 was a production programming language, that would be a reasonable assumption.

First of all it is not clear what is "whitespace" above.

Some cells in Funge-space contain whitespace, others don't. ASCII 32 is certainly whitespace. The letter "x" certainly isn't.

So I'm assuming that a line, is everything that has the same y coordinate as IP.

In a context where "line" refers to a line of text, as from a source code file, it is true that everything on it has the same y coordinate. But in the context of "same-line wrapping" its meaning is not limited to this. It means the line that the IP is travelling on. For example if the delta is (+1,+1), the line it is travelling on extends from the current position of the IP indefinitely in the southeasterly direction (if you think of the playfield as a map with the usual orientation (north at the top)). Since it is a line and not a ray, it also extends indefinitely in the northwesterly direction.

As far as I can see it, the prime case for wrapping, is when there next node does not exist at all because we reached the edge of addressable space.

That's probably why the sentence you quoted, "When the IP attempts to travel into the whitespace between the code and the end of known, addressable space, it backtracks", mentions the edge of addressable space specifically.

Similarly, it's not clear why would we want to wrap, if we has not reached the end of addressable space yet, on a white space.

I'm not sure why you would expect wrapping to occur when there are still instructions ahead of the IP that it can execute. I'm not certain what inference you made from the statement "When the IP attempts to travel into the whitespace between the code and the end of known, addressable space, it backtracks" that led you to expect this.

This sound as complete non-sequitur.

Why thank you. You're too kind.

Also it is very hard to see what the diagram is trying to demonstrate.

The diagram shows two lines. Initially the IP is travelling east, so it is on an east-west line. Then it executes x with 1 and 1 on the stack, so it begins travelling southeast, on a northwest-southest line. It then wraps to the northwesternmost point on that line. Then it executes x with 0 and 1 on the stack, so that it begins travelling east again, on the east-west line again. It then wraps again, back to the westernmost point on that line, and the whole thing repeats indefinitely.

[AndrewSav]

Thank you for this. It addresses most of the points, but there is still one thing unclear.

When the IP attempts to travel into the whitespace between the code and the end of known, addressable space, it backtracks

Why there should be whitespace between the code and the end of known, addressable space? What if there isn't?

[cwesson]

Why there should be whitespace between the code and the end of known, addressable space? What if there isn't?

By default every space contains a space character. The IP backtracks when it reaches the last non-space character along its vector.

From the spec:

Before load, every cell in Funge-Space contains a space (32) character.

[AndrewSav]

@cwesson Yep, I've seen that. That does not answer the question though, because we are not talking about "before load" we are talking about "during program execution".

[cwesson]

Some of the spaces are overwritten when the program is loaded, but those that are not overwritten do not disappear when the program starts executing. The spaces in every cell always exist until they are overwritten by a non-space character by either loading the program or by executing an instruction that modifies Funge-Space (i.e. p or i).

[AndrewSav]

Okay, I feel we are getting there. Slowly but surely. So if they are overwritten by executing an instruction that modifies Funge-Space (i.e. p or i), it is possible that there could be no whitespace between the code and the end of known, addressable space?

[Nakilon]

If the program is like this

XXXXXXX
X XXXXX
XXXXXXX
XXX+XXX
XXXXXXX
XXXXX+X
XXXXXXX

and we are at (5, 5) with delta (-2, -2) then we'll loop within two cells (5, 5) and (3, 3), right? Will the space at (1, 1) take a tick in case of multithreading?

[cwesson]

@AndrewSav Yes, it is theoretically possible there is no whitespace, this would likely consume a several gigabytes of memory on a 32-bit interpreter, and possibly exabytes on a 64-bit interpreter. Although there are ways to reduce that if you use a large delta, or if your interpreter somehow compresses funge space.

Imagine extending Nakilon's example out to the edge of addressable space in both directions (and replacing the space with +). Something like this:

XXXXXXXX... -2147483648
X+XXXXXX...
XXXXXXXX...
XXX+XXXX...
    .
     .
      .
       .
...XXXXX+XX
...XXXXXXXX
...XXXXXXX+ 2147483647

Assuming a 32-bit funge space, this is 8GB worth of + instructions alone (2147483647 +s, 4 bytes each, not including the overhead of actually keeping track of where those are). You would have a line of + and X extending from (-2147483648, -2147483648) to (2147483647, 2147483647) which the IP would never leave. The IP would execute nothing but + instructions forever.

---

@Nakilon I believe it would loop between (5, 5) and (3, 3) endlessly, I tested this part on my interpreter. Unless I'm misinterpreting the spec, the space at (1, 1) executes in "no time whatsoever", there is no exception for multithreading.