PoprC Runtime Operation Part 4: Alternatives

Every programming language supports some form of branching. A simple form of branching is the C if statement, which evaluates a boolean expression, and then selects a branch based on the value of that expression. This works well if the branching condition can be calculated before choosing a branch, but sometimes a branch can’t be selected until one of the branches has been partially computed. If this is the case, the programmer has to write several nested if statements, one for each decision point, and divide the calculation into incremental fragments, often repeating parts of the same calculation in different branches. Another example of this type of branching is common in error handling, where errors are checked in several places. If an error occurs, the program must jump to an alternate branch which handles the error, often by aborting the calculation and returning an error to the caller, which will continue to propagate upwards until it can be handled reasonably. This is why C++ explicitly supports exceptions, although it is really just a type of branching.

Many pipelined processors handle branching slightly different from the semantics of the if statement. Instead of stalling while waiting for the condition to be fully evaluated, the processors has a branch prediction unit, which just makes a guess and follows a branch. The processor backtracks if it chose the wrong branch. The programming language Prolog takes this even further; every code path is executed exhaustively until the computation is successful. Whenever a branch fails (is determined to be invalid), the program backtracks to the last branch point with an unfollowed branch, and then continues along that branch. This is repeated until the program finds a successful path to a result.

The Popr language is designed with Prolog style backtracking as the only form of branching, because this subsumes other types of conditional statements. Furthermore, since Popr is partially evaluated at compile time, backtracking implements an advanced type system, because the compiler will just try all versions of each function until it can form a program that is well typed.

Branches in Popr are called alternatives, and are created with the alternative function (|). Two fields are present in cell_t to support alternatives. The alt field points to the next alternative path in the graph. The alt_set field is used to determine if two paths are compatible, by making sure that values can’t take conflicting paths. This prevents results such as 2 3 | dup + evaluating to 5; 4 and 6 are the only valid results.

Alternatives are expanded during reduction by a process called splitting; when a function has N arguments having alternatives, 2^N copies are created from all the combinations generated by replacing an argument with its alternative. If any argument has more than one alternative, they will continue to be expanded further when they are reduced later.

cell_t *dup_alt(cell_t *c, unsigned int n, cell_t *b) {
  unsigned int i = 0, in = closure_in(c), out = 0;
  assert(n < in);
  cell_t *a = copy(c);

  // ref args
  for(; i < in; ++i) {
    if(i != n) ref(a->arg[i]);
  }

  // update deps
  for(; i < c->size; ++i) {
    if(a->arg[i]) a->arg[i] = dep(a);
    c->arg[i]->alt =
	  conc_alt(a->arg[i], c->arg[i]->alt);
    ++out;
  }

  a->arg[n] = b;
  a->n = out;
  c->alt = a;
  return a;
}

dup_alt(c, n, b) copies c, with c->arg[n] replaced with b, and assigns c->alt to b; this is the basic operation of creating a new alternative.

void split_arg(cell_t *c, unsigned int n) {
  cell_t
    *a = c->arg[n],
    *p = c,
    **pa;
  if(!a || !a->alt || is_marked(a, 1)) return;
  do {
    pa = &p->arg[n];
    if(*pa == a) {
      // insert a copy with the alt arg
      p = dup_alt(p, n, ref((*pa)->alt))->alt;
      // mark the arg
      *pa = mark_ptr(*pa, 1);
    } else p = p->alt;
  } while(p);
}

split_arg(c, n) splits c on the nth argument. Any alternative of c having the same argument in the same position is split. When a closure is split on an argument n, the new closure has the argument c->arg[n]->alt, but the old one needs a new argument that no longer has an alternative, so that c->arg[n]->alt isn’t split and followed more than once. Rather than make a copy without an alternative, the low bit of the pointer c->arg[n] is set, marking that the alt field should be ignored, as if c->arg[n]->alt was set to 0.

cell_t *closure_split(cell_t *c, unsigned int s) {
  int i;
  for(i = 0; i < s; ++i) {
    split_arg(c, i);
  }
  for(i = 0; i < s; ++i) {
    c->arg[i] = clear_ptr(c->arg[i], 1);
  }
  return c->alt;
}

closure_split(c, s) splits c from c->arg[0] to c->arg[s-1], and then clears the flags set on the arguments of c (so they are ready for reduction), and returns c->alt. This function must generally be called after c->arg[0] to c->arg[s-1] have been reduced for alternatives to work correctly.

An alt_set_t is a bit field indicating which alternatives have been followed to reach a value. Functions for manipulating alt_sets are prefixed with as.

alt_set_t as(unsigned int k, unsigned int v) {
  assert(k < AS_SIZE);
  return ((alt_set_t)1 << (k + AS_SIZE)) |
    (((alt_set_t)v & 1) << k);
}

Each point where an alternative is chosen (| is reduced) has an associated unique identifier. as(k, v) creates an alt_set_t that indicates which alternative was followed at point k. If v is 0, the first alternative was followed; if v is 1, the second alternative was followed.

alt_set_t as_conflict(alt_set_t a, alt_set_t b) {
  return ((a & b) >> AS_SIZE) &
    ((a ^ b) & (((alt_set_t)1<<AS_SIZE)-1));
}

as_conflict(a, b) determines if there are any conflicts between a and b i.e. both alternatives where followed at some point. If two alt_sets do not conflict, they can be combined with bitwise or.

bool entangle(alt_set_t *as, cell_t *c) {
  return !as_conflict(*as, c->alt_set) &&
    (*as |= c->alt_set, true);
}

entangle(&as, c) returns false if c->alt_set conflicts with as, otherwise they are combined and stored in as, and the function returns true. This should be called on all reduced arguments of a function to determine the alt_set of the resulting value. If there are conflicts, the function must fail.

bool reduce_arg(cell_t *c,
		unsigned int n,
		alt_set_t *as,
		type_t t) {
  bool r = reduce(&c->arg[n], t);
  split_arg(c, n);
  return r && entangle(as, clear_ptr(c->arg[n], 1));
}

reduce_arg(c, n, &as, t) combines the reduction of an argument with splitting and entanglement. It reduces c->arg[n] with expected type t and entangling as.

Alternatives in Popr are very powerful, allowing logic programming and a powerful type system. The implementation is complex, but partial evaluation can remove alternatives in many cases.