Circular Programming
This page goes into the nitty gritty of how loops work behind the scenes. I recommend reading the intro page's section on looping and circular programming first. For the more information on syntax of loops see > matching.
Foldr
Foldl (haskell terminology) is the same as doing a scan and then taking the last element. Iogii provides a builtin called foldr that works similarly to iterate but from right to left and then taking the first element. The advantage of this as opposed to foldl is you could actually compute the answer without considering all elements, using laziness. Suppose you wanted to inefficiently find the square root of a number. You could look for the first element such that (x+1) squared is greater than the target. Normally I would just filter and then take the first, but for this example let's do it without filter.
26 wholes 1+ dup * < not 0 foldr wholes ifElse > → 5
It computes the answer even though we are essentially folding on an infinite list (the initial value, 0, is not used).
How Foldr Works
We have seen how iterate is a circular program using cons to put the initial value at the front and subsequent values are then calculated from left to right. foldr works by adding the initial value to the end and calculating right to left (and since it is a fold instead of a scan, taking only the first element as the result).
Note, you don't need to understand how foldr works to use it effectively, so long as you know it works right to left. But this information could be useful to you if you wish to use these techniques in Haskell, or implement something like a scanr in iogii (since there is no built-in op for that).
If we try to foldr manually it doesn't work. Why?
ans 0 append tail 1,2,3 + set ans head → stack level too deep
The reason is that vectorization of a binary op (zipWith in Haskell), terminates when either arg is empty. So is the first arg to + empty? That depends on the result of append and it would check the first arg of append for emptiness first to answer that, so is that empty? That would depend on if ans is empty. But the reason we were asking this question in the first place is to determine if there should be even one elment in the result of + (which is ans). So we have created direct circular dependency that will loop forever.
iterate doesn't have this problem because we are adding elements to the left first, so we know it isn't empty, and when we calculate more values, we know the list doesn't end there either.
But what if our vectorization, aka zipWith only checked the second arg for emptiness? Then it wouldn't create a direct circular dependency. Actually building iogii like that would be a bad idea, because what if we wanted the circular arg be the second one instead? But we can achieve the effect by padding our unknown length arg to infinite length, thus allowing the emptiness check to always immediately return false. There are ops that can do this for you: pad and padDefault which append an infinite amount of default values or specified values.
1,2,3 padDefault → [1,2,3,0,0,0,0,0,0...
So let's try it:
ans 0 append padDefault tail 1,2,3 + set ans head → 6
It worked! Note, it may seem that pad is the same as appending a repeated value, but that wouldn't have worked.
ans 0 append 0 repeat append tail 1,2,3 + set ans head → stack level too deep
The reason is the same as our initial problem. We know the list is infinite through our reasoning, but iogii (and Haskell) check for emptiness mechanically, they don't reason. append will check the first arg for emptiness first, which is what caused the problem. It is not smart enough to look at the second arg instead (which can know immediately that it is not empty).
pad will need to know where its first arg ends in order to know when the padded values begin, but it is implemented in such a way that it does not need to even look at the first arg to answer the question, "is this result of the pad empty?".
This makes pad sound special, but it could have been written in Haskell as:
pad a v = h : pad t v
where
~(h,t) =
if null a
then (v,[])
else (head a,tail a)
Or in iogii as:
1,2,3 Iterate tail > head → [1,2,3,0,0,0,0...
Technically foldr is implemented with pad rather than append + padDefault because that effectively puts the desired value at the end and pads it in a single op.
Again, you don't really need to know about this but I find it very beautiful that all of computation can be built off of just a few simple vectorized primitives, cons, head, tail, if, nil. It would be worth writing more about this in a context outside of iogii.
Superpad
There is one last gotcha that can happen if you try to use these techniques manually or in Haskell. Iogii loop ops take care of this for you, so again you don't actually need to know.
Let's return to our iterate / foldl example of summing a list of numbers and how that is manually implemented:
ans 1,2,3 + 0 cons set ans → [0,1,3,6]
Great, but what if we wanted to sum the rows of a 2d list? That should be no problem right?
ans 1,2,3,,5,6,7 + 0,0 cons set ans → [stack level too deep
Why didn't this work?
How many rows should the result be? We know it is 2, but how would iogii / Haskell know that?
num rows of ans = min num rows of 0,0 and result of +
num rows of + = min num rows of 1,2,3,,5,6,7 and ans.
That's another direct circular dependency.
Atlas Solves this problem by detecting self dependencies at run time and then having "faith" that the result will not be empty. But since iogii has dedicated ops for folding we can do this statically which allows for compilation to Haskell.
All we need to do is short circuit that emptiness check again, since if we said the num rows of ans is infinite, the num rows of + would still be 2 since that is the length of the other (shorter arg). Technically iogii doesn't look at lengths, just emptiness at each step of the calculation (but it is easier for us to think in terms of length for many examples).
ans PadDefault 1,2,3,,5,6,7 + 0,0 cons set ans → [[0,1,3,6],[0,5,11,18]]
We would need to pad each dimension that is being circularly vectorized over. So a rank 3 list summation would need PadDefault, PadDefault, etc. (note the , on the first pad).
So this is all that superpad is, an op that pads all ranks down to the specified rank. (superpad pads down to rank 1, SuperPad pads down to rank 2, etc). You can actually use the superpad op to experiment, but if you actually need to use this technique manually you'd be better off (in terms of code size) by just using the correct amount of padDefaults.
Here's an example with a rank 3 list:
ans PadDefault, PadDefault 1,2,3,,5,6,7,,,10,11 + 0,0,,0 cons set ans → [[[0,1,3,6],[0,5,11,18]],[[0,10,21]]]
This generates the same IR that superpad would:
ans superpad 1,2,3,,5,6,7,,,10,11 + 0,0,,0 cons set ans → [[[0,1,3,6],[0,5,11,18]],[[0,10,21]]]
Which is exactly what iterate does:
0,0,,0 iterate 1,2,3,,5,6,7,,,10,11 + → [[[0,1,3,6],[0,5,11,18]],[[0,10,21]]]
All this isn't necessary to use iogii, but now you know exactly how loop ops are transformed to ordinary operations on plain values.
Loop Ops Actual Implementations
[initial] iterate [fn] is
ans superpad [fn] [initial] cons set ans
expand [fn] is
ans consDefault superpad [fn] set ans
[initial] foldr [fn] is
ans superpad [initial] pad tail [fn] set ans head
meld [fn] is
ans superpad padDefault tail [fn] set ans head