C言語で非決定的計算

http://www.kmonos.net/wlog/96.html#_2319090427

今ある普通の言語の場合、「別に最左である必要はなくて、最大要素のインデックスならどれでもよかった」という実装をすることができません。

「普通の言語」どころか（書いた私が）頭のおかしいコードですが、

> cat max.c
#include <stdio.h>
#include <assert.h>
#include <setjmp.h>

void amb(int x, int y) {
  assert(0);
}

/* longjmpは返値型がvoidなのでint型に合わせる */
int mylongjmp(jmp_buf cont, int ans) {
  longjmp(cont, ans);
  assert(0);
}

/* arrの最大要素(の一つ)のインデックス+1を非決定的に返す */
void find_max_cps(jmp_buf k, double *arr, int len) {
  jmp_buf cont;
  int ans;

  assert(len >= 1);
  if (len == 1) longjmp(k, 1);

  ans = setjmp(cont);
  if (ans == 0) find_max_cps(cont, arr+1, len-1);

  if (arr[0] > arr[ans]) longjmp(k, 1);
  if (arr[0] < arr[ans]) longjmp(k, ans+1);
  amb(mylongjmp(k, 1), mylongjmp(k, ans+1));
}

int find_max(double *arr, int len) {
  jmp_buf cont;
  int ans;
  ans = setjmp(cont);
  if (ans == 0) find_max_cps(cont, arr, len);
  return ans;
}

int main() {
  double a[] = { 0., 1., 2., 3., 1., 2., 3., 2., 3., 3. };
  printf("%d\n", find_max(a, sizeof a / sizeof a[0]));
  return 0;
}
> gcc -O0 max.c
> ./a.out
10
> gcc -O3 max.c
> ./a.out
4
> gcc -v
/usr/lib/gcc/i386-redhat-linux/3.4.6/specs から spec を読み込み中
コンフィグオプション: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --enable-shared --enable-threads=posix --disable-checking --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-java-awt=gtk --host=i386-redhat-linux
スレッドモデル: posix
gcc バージョン 3.4.6 20060404 (Red Hat 3.4.6-10)

…もちろん実用のためではなくネタです。すみません。

Cf. http://www.kmonos.net/wlog/96.html#_2319090427

非決定性プリミティブというと amb オペレータ なんですが

Cの関数引数の評価順序やunstableなsortにも同じ類の非決定性がある

蛇足: 最初、arr[0] > arr[ans]やarr[0] < arr[ans]を素でarr[0] > ansやarr[0] < ansと書いてしまい、コンパイルエラーも警告も出ないのに実行結果が間違っていて１分ぐらい悩みました。ML万歳。（SMLでもOCamlでもOK）

追記: setjmp/longjmpを使っているのは、C言語でreturn文を「文」ではなく、ambの引数に書ける「式」にする方法が（私には）わからなかったためです。setjmp/longjmpを使うかわりに、（ambの実引数の中で）変数への破壊的代入をしても、同じ非決定的計算が書けます。C言語では副作用完了点をまたがない複数の副作用は未定義動作…とか言い出すと少し話がややこしくなりますが。

追記２: http://d.hatena.ne.jp/ku-ma-me/20090427/p3 にまさに「破壊的代入による実装」がありました！　コメント感謝。そういう風に関数呼び出し（副作用完了点の一つ）を跨げば未定義動作にもならないと思います（多分）。