Removing list items: Part 2

After tossing the ideas from my previous post around with Murphy, we refined the concept a bit.  Items:

1. The focus is now on discarding dead items with “removeCurrent varname” rather than keeping live ones.
2. Instead of a separate “removeEach” loop, the removal feature will use the regular forEach.  If the body of the forEach contains a removeCurrent command, the extra framework will be added.
3. The list structure basically becomes corrupted during the iteration and is fixed at the end.  A return command or an exception being thrown would normally prevent the list from performing that final clean-up.  Code needs to be adjusted to accommodate that.
4. Regular forEach loops can be called on iterable objects or iterator objects.  The forEach-remove variant could only be called on iterable lists – meaning also that we can use indicies to control the loop progression instead of creating an iterator.

Here’s an example of how it would all work under the hood.  This Slag code:

  forEach (mob in monsters)
    mob.update
    if (mob.dead) removeCurrent mob
  endForEach

would be transformed into this:

  local var list = monsters
  local var limit = list.count
  local Boolean kept = false
  local Int32 save_pos = 0
  local Int32 read_pos = 0
  try
    while (read_pos < limit)
      if (kept) save_pos++
      else kept = true
      local var mob = list[read_pos]
      monsters[save_pos] = mob
      read_pos++

      # user code
      mob.update
      if (mob.dead) kept = false

    endWhile

    if (kept) save_pos++
    list.discard(save_pos,read_pos-1)

  catch (Exception err)
    if (kept) save_pos++
    list.discard(save_pos,read_pos-1)
    throw err
  endTry

Removing list items during iteration

The problem

There’s a classic problem that comes along with forEach loops: how do you handle removing list items as you iterate – both from a language design standpoint and from an algorithmic standpoint?

The naive approach is to not worry about it and let people add and remove things to and from lists while iterating through them.  But then several common situations would introduce subtle errors – for example, removing an item from the beginning of a list during the middle of iteration would cause the iterator to skip over the next item (since item i it was on just became item i-1), and you definitely don’t want to worry about randomly skipping things you might be looking for.

So first you want to prevent programmers from modifying the list in the naive way and then you want to figure out how to let them do it a different way.

ETC-to-C cross-compiler

I just finished the major work on the ETC-to-C cross-compiler I’ve been working on!

ETC (Execution-Tree Code) is the bytecode that Slag compiles to.  A couple of months ago I made an initial quick ‘n’ dirty cross-compiler that converted ETC code into “Hybrid VM” code, where the organization was the essentially the same as in the VM and the only difference was that the commands that had been called via function pointers were now listed out in contiguous blocks.

As I’m now working on Doc Fuzzle for the iPhone, I needed to improve my cross-compiler.  I had three goals: