Thursday, September 15, 2005

Template legerdermain

Following up on yesterday's post, I worked out how to capture the return value for a continuation, that is, a future computation.

(Aside: This raised a question in my mind: what should be the behavior of asking for the result of a computation which has not yet taken place? In my prototype, I return a default constructed value (e.g., 0 for an int). Another option might be to raise an appropriate exception as it is likely a programming error. Yet another is to provide a sentinal value or a predicate to ask the state of the computation. That last choice is interesting: if the continuation changes to a different context before finishing, the computation could be half-completed or even discarded. Questions for another day.)

The new sample main is:

#include <cstdlib>
#include <iostream>

#include "continuations.h"

static int
increment (int id, int *n)
{
  int m = *n;
  std::cout << id << " thinks: " << *n << std::endl;
  ++*n;
  return m;
}

int
main (void)
{
  int initial_value = 0;

  continuation<void> main_uc;
  // TODO: Why not deduce from the return type of increment?
  continuation<int> inc0_uc (main_uc, increment, 1, &initial_value);
  continuation<int> inc1_uc (inc0_uc, increment, 2, &initial_value);

  std::cout << "1 said: " << static_cast<int> (inc0_uc) << std::endl;
  std::cout << "2 said: " << static_cast<int> (inc1_uc) << std::endl;

  main_uc.switch_to (inc1_uc);

  std::cout << "All done: " << initial_value << std::endl;
  std::cout << "1 says: " << static_cast<int> (inc0_uc) << std::endl;
  std::cout << "2 says: " << static_cast<int> (inc1_uc) << std::endl;

  return EXIT_SUCCESS;
}

The header is somewhat hairy, however:

#ifndef _CONTINUATION_H
#define _CONTINUATION_H

#include <stdexcept>

#include <errno.h>
#include <string.h>
#include <ucontext.h>

#define STACK_SIZE 4096

template <typename R> class continuation;

class continuation_base : public ucontext_t {
  char stack[STACK_SIZE];

protected:
  continuation_base () {
    initialize ();
  }

  template<typename R1>
  continuation_base (continuation<R1> &next) {
    initialize ();
    uc_link = &next;
  }

public:
  template<typename R1>
  int switch_to (continuation<R1> &next) {
    return swapcontext (this, &next);
  }

private:
  void initialize () {
    if (getcontext (this) < 0)
      throw std::runtime_error (strerror (errno));

    uc_stack.ss_sp = stack;
    uc_stack.ss_size = sizeof stack;
  }
};

template<typename R>
void apply (R (*lambda) (), R *r) {
  *r = lambda ();
}

template<typename R, typename T0>
void apply (R (*lambda) (T0), R *r, T0 t0) {
  *r = lambda (t0);
}

template<typename R, typename T0, typename T1>
void apply (R (*lambda) (T0, T1), R *r, T0 t0, T1 t1) {
  *r = lambda (t0, t1);
}

template<typename R>
class continuation : public continuation_base {
  R value;

public:
  continuation () { }

  template<typename R1>
  continuation (continuation<R1> &next, R (*lambda) ())
    : continuation_base (next) {
    void (*fp) (R (*) (), R *) = apply<R>;
    makecontext (this,
                 reinterpret_cast<void (*) (void)> (fp),
                 2, lambda, &value);
  }

  template<typename R1, typename T0>
  continuation (continuation<R1> &next, R (*lambda) (T0), T0 t0)
    : continuation_base (next) {
    void (*fp) (R (*) (T0), R *, T0) = apply<R, T0>;
    makecontext (this,
                 reinterpret_cast<void (*) (void)> (fp),
                 3, lambda, &value, t0);
  }

  template<typename R1, typename T0, typename T1>
  continuation (continuation<R1> &next, R (*lambda) (T0, T1),
                T0 t0, T1 t1)
    : continuation_base (next) {
    void (*fp) (R (*) (T0, T1), R *, T0, T1) = apply<R, T0, T1>;
    makecontext (this,
                 reinterpret_cast<void (*) (void)> (fp),
                 4, lambda, &value, t0, t1);
  }

  operator R () { return value; }
};

template<>
class continuation<void> : public continuation_base
{
public:
  continuation () { }

  template<typename R1>
  continuation (continuation<R1> &next) : continuation_base (next) { }
};

#endif /* _CONTINUATION_H */

Two techniques of note are the specialization for void return and moving non-return value-related code into a shared base class—a common trick when parameterizing return types—, and the use of apply handle the return value from lambda in the continuation.

makecontext takes a void (*) (void) function pointer for the program text of the ucontext_t, which requires a cast of apply. I found that simply:

makecontext (this,
             reinterpret_cast<void (*) (void)> (&apply<int, int, int *>),
             4, lambda, &value, t0, t1);

would not compile with GCC 3.3.5. This is an area of C++ where my fu is insufficient to know at sight if my code is legal—although I presume it is. So I resorted to local variable, fp, for the cast and suddenly GCC was satisfied (see above).

So the short of it is that now I can interrogate my continuation for its computed value.

No comments: