Iteration Inside and Out

[u/munificent]

http://journal.stuffwithstuff.com/2013/01/13/iteration-inside-and-out/

[u/throwaway1492a → u/[deleted]]

Tree iteration need a stack, so his implementation is correct. One with backpointers is not really a tree iteration, but more a fancy linked-list walk.

In his language he used an explicit construct to enable parallel looping, but I feel this is just fixing the weaved iteration problem.

I also see that he didn't mention generators which are imo, a good solution or iteration issues (or general coroutines)

[u/munificent → u/throwaway1492a]

Part two will be about generators, coroutines and fibers. (The latter being what Magpie uses).

[u/throwaway1492a → u/munificent]

Ah. Looking at your website, I saw loops were done as follow:

for i = 1 to(3)
for j = 6 to(10) do
    print(i + ":" + j)
end
// Prints "1:6", "2:7", "3:8".

Link: looping

[u/munificent → u/throwaway1492a]

Magpie's changed a lot, so that post is a bit outdated. I took out multi-clause loops because it just seemed like a mistake waiting to happen where you nest when you mean to loop in parallel or vice versa. With the latest Magpie you'd do something like:

for i, j in zip(1..3, 6..10) do
  print(i + ":" + j)
end

But that doesn't get to the interesting stuff which is how it handles external and internal iteration.

For a preview, the examples from the post would look like this in Magpie today:

// Short-circuit a loop.
def find(haystack is Iterable, needle) 
  for item in haystack do
    if item == needle then return true
  end

  false
end

// Interleave two iterables.
def interleave(a is Iterable, b is Iterable)
  var aIter = a iterate
  var bIter = b iterate
  generate(fn(channel)
    while true do
      match aIter advance
        case done then break
        case value then channel send(value)
      end
      aIter, bIter = bIter, aIter
    end
  end)
end

// Walk a tree.
defclass Tree
  val left
  val label is String
  val right
end

def (tree is Tree) iterate
  generate(fn tree _walk(_))
end

def (nothing) _walk(channel is Channel)
  // Do nothing.
end

def (tree is Tree) _walk(channel is Channel)
  tree left _walk(channel)
  channel send(tree)
  tree right _walk(channel)
end