out_parameter_tail_rec.c

/* input: (some strict language with haskell-like syntax)
    a ++ b = case a of
      []      -> b
      x :: a' -> x :: (a' ++ b)
 */

// -- direct compilation to C -->

list* append(list* a, list* b) {
  switch (a->tag) {
    case NIL: {
      return b;
    }
    case CONS: {
      list* ab = append(a->tl, b);
      return alloc_cons(a->hd, ab);
    }
  }
}

// -- alternative: out parameter -->

void append(list* a, list* b, list** out) {
  switch (a->tag) {
    case NIL: {
      *out = b;
      return;
    }
    case CONS: {
      list* ab;
      append(a->tl, b, &ab);
      *out = alloc_cons(a->hd, ab);
      return;
    }
  }
}

// -- another change: allocate before recursive call -->

void append(list* a, list* b, list** out) {
  switch (a->tag) {
    case NIL: {
      *out = b;
      return;
    }
    case CONS: {
      *out = alloc_cons(a->hd, nil);
      append(a->tl, b, &(*out)->tl);
      return;
    }
  }
}

// -- turn tail recursion into loop -->

void append(list* a, list* b, list** out) {
  while (1) {
    switch (a->tag) {
      case NIL: {
        *out = b;
        return;
      }
      case CONS: {
        *out = alloc_cons(a->hd, nil);
        a = a->tl;
        out = &(*out)->tl;
        break;
      }
    }
  }
}