Re: ambってCでも書けるのかな

ref: http://mono.kmc.gr.jp/~yhara/d/?date=20071229#p01
C + setjmp + longjmp で amb が実装できるかという話題。

CPS 変換すればできそうですけど、CPS 変換すれば setjmp + longjmp がなくてもできそう *1 で面白くないので、無理矢理以下が動くように書いてみました。

void test() {
  int i = amb(3,  4, 6, 7);
  int j = amb(3,  5, 8, 11);
  if(prime(i + j)) printf("(%d, %d)\n", i, j);
  amb(0);
}

うちの環境 (Debian etch / x86 / gcc 4.1.2) では (6, 5) と (6, 11) が出力されます。まじめに書いてないので環境選びまくりです。というか C 言語準拠じゃないので、厳密な意味では C + setjmp + longjmp じゃないです。

以下ソース。

#include <stdio.h>
#include <setjmp.h>
#include <string.h>
#include <stdlib.h>
#include <stdarg.h>

struct env {
  jmp_buf jbuf;
  char *stack;
  int stack_len;
} *cur_env;
char *stack_bottom;

void set_sp(char **p) {
  char c;
  *p = &c;
}

int save() {
  struct env *env = malloc(sizeof(struct env));
  char *p;
  set_sp(&p);
  env->stack_len = stack_bottom - p;
  env->stack = malloc(sizeof(char) * env->stack_len);
  memcpy(env->stack, p, sizeof(char) * env->stack_len);
  if(setjmp(env->jbuf) == 0) {
    cur_env = env;
    return 0;
  }
  free(env->stack);
  free(env);
  return 1;
}

void restore() {
  char *p;
  set_sp(&p);
  if(p < stack_bottom - cur_env->stack_len) {
    p = stack_bottom - cur_env->stack_len;
    memcpy(p, cur_env->stack, sizeof(char) * cur_env->stack_len);
    longjmp(cur_env->jbuf, 1);
  }
  else {
    void *dummy[1024];
    dummy[0] = dummy; /* dummy assignment */
    restore();
  }
  /* not reached */
}

int amb(int argc, ...) {
  int i, x;
  struct env *prev_env;
  va_list ap;

  if(argc > 0) {
    prev_env = cur_env;

    va_start(ap, argc);
    for(i = 0; i < argc; i++) {
      x = va_arg(ap, int);
      if(save() == 0) return x;
    }
    va_end(ap);

    cur_env = prev_env;
  }

  restore(0);

  /* not reached */
  return 0;
}

int prime(int x) {
  int i;
  for(i = 2; i < x; i++) if(x % i == 0) return 0;
  return 1;
}

void test() {
  int i = amb(3,  4, 6, 7);
  int j = amb(3,  5, 8, 11);
  if(prime(i + j)) printf("(%d, %d)\n", i, j);
  amb(0);
}

int main(int argc, char *argv[]) {
  struct env first_env;
  set_sp(&stack_bottom);
  cur_env = &first_env;
  first_env.stack = NULL;
  first_env.stack_len = 0;
  if(setjmp(first_env.jbuf) == 0) test();
  return 0;
}

種明かしすると、ruby の callcc を再実装してみただけです。C のスタックをまるごと memcpy で待避・復元するんですねえ。

*1:末尾呼び出し最適化がないとスタック溢れるかもだけど。