日々の流転

λ. malloc-free な C 言語はチューリング完全

ku-ma-meさんが「malloc-free な C 言語はチューリング完全か」と書いていた。そこでku-ma-meさんも「再帰をうまく使えばできるのかな」と書いているけど、再帰を使って全部スタック上に確保してしまえば良さそうだ。 ヒープがないならスタックを使えばいいじゃない

Brainf*ck

とりあえず、メモリが有界でないBrainf*ckが実装できればチューリング完全だと思うので、実装してみた。

#include <stdio.h>

struct cell {
    struct cell *prev, *next;
    unsigned char value;
};

static void
f(const char *pc, struct cell *p)
{
    struct cell c = { .prev=p, .next=NULL, .value=0 };
    if (p) p->next = &c;
    p = &c;

    while (1)
        switch (*pc++) {
        case '\0': return;
        case '>':
            if (p->next)
                p = p->next;
            else
                return f(pc, p);
            break;
        case '<': p = p->prev; break;
        case '+': p->value++; break;
        case '-': p->value--; break;
        case '.': putchar(p->value); break;
        case ',': p->value = getchar(); break;
        case '[':
            if (!p->value) {
                int lv=1;
                while (lv)
                    switch (*pc++) {
                    case '[': lv++; break;
                    case ']': lv--; break;
                    }
            }
            break;
        case ']':
            {
                int lv=1;
                pc-=2;
                while (lv)
                    switch (*pc--) {
                    case '[': lv--; break;
                    case ']': lv++; break;
                    }
                pc++;
            }
            break;
        }
}

void brainfuck(const char *prog){ f(prog, NULL); }

実行用のコード。

#include <glib.h>
#include <stdio.h>
#include <locale.h>

int main(int argc, char **argv)
{
    GError *err = NULL;
    gchar *prog;
    setlocale(LC_ALL, "");
    g_file_get_contents(argv[1], &prog, NULL, &err);
    if (err) {
        puts(g_locale_from_utf8(err->message, -1, NULL, NULL, NULL));
        return 1;
    } else {
        brainfuck(prog);
        return 0;
    }
}

プログラムを読み込む処理は本質的ではないため、今回はプログラムの読み込み自体はmalloc-freeにはしなかった。というのも、読み込み処理をわざわざCで書かなくても、プログラムを既存の「brainf*ck自身で書かれたbrainf*ck処理系」に固定してしまえば済む話なので。

一般化?

ってか、つきつめて考えると、今のCならプログラムをCPS変換wして、以下のような関数を使えば良いか。しょーもないオチだけど。

void malloc_cps(size_t n, void (*k)(void*, void*), void *user_data)
{
    unsigned char a[n];
    k(a, user_data);
}