2006-03-28

Cで継続渡し

C Lisp

できた。試行錯誤している内に無駄に凝った作りになってしまった。ここまで来ると完全に手段が目的と化しているな。

fib.h:

#ifndef __FIB_H__
#define __FIB_H__

typedef void (*destructor_t)();

typedef struct object {
    int ref_count;
    size_t size;
    destructor_t destructor;
} *object_t;

void addRef(object_t obj);
void release(object_t obj);
object_t newObject(size_t size, destructor_t destructor);
void deleteObject(object_t obj);

typedef void* (*func_t)();

typedef struct closure {
    // inherited from object_t
    int ref_count;
    size_t size;
    destructor_t destructor;
    // own data
    func_t func;
    int var_num;
    void *vars[0];
} *closure_t;

closure_t newClosure();

#endif /* __FIB_H__ */

fib.c:

#include <stdio.h>
#include <stdlib.h>

#include "fib.h"

void addRef(object_t obj)
{
    obj->ref_count++;
}

void release(object_t obj)
{
    obj->ref_count--;
    if (obj->ref_count <= 0) {
        if (obj->destructor)
            obj->destructor(obj);
        deleteObject(obj);
    }
}

object_t newObject(size_t size, destructor_t destructor)
{
    object_t obj = malloc(size);
#ifdef DEBUG
    fprintf(stderr, "malloc: %p\n", obj);
#endif
    obj->ref_count = 0;
    obj->size = size;
    obj->destructor = destructor;
    addRef(obj);
    return obj;
}

void deleteObject(object_t obj)
{
#ifdef DEBUG
    size_t size = obj->size;
    char *p = (char*) obj;

    // filled by `de ad be ef' ... pattern
    for (int i = 0; i < size / 4; i++) {
        *p++ = '\xde'; *p++ = '\xad';
        *p++ = '\xbe'; *p++ = '\xef';
    }
    switch (size % 4) {
        case 3: p[2] = '\xbe';
        case 2: p[1] = '\xad';
        case 1: p[0] = '\xde';
    }
#endif /* DEBUG */

    free(obj);

#ifdef DEBUG
    fprintf(stderr, "free: %p\n", obj);
#endif
}

closure_t newClosure(int var_num)
{
    size_t size = sizeof(struct closure) + sizeof(void*) * var_num;
    closure_t c = (closure_t) newObject(size, NULL);
    c->var_num = var_num;
    return c;
}

int fib_cps(int n, closure_t k);

static int fib_cps_2(int v2, closure_t k2)
{
    int v1 = (int) k2->vars[1];
    closure_t k = k2->vars[0];
    release((object_t) k2);
    return (int) k->func(v1 + v2, k);
}

static int fib_cps_1(int v1, closure_t k1)
{
    int n = (int) k1->vars[1];
    closure_t c = newClosure(3);
    c->func = (func_t) fib_cps_2;
    c->vars[0] = k1->vars[0];
    c->vars[1] = (void*) v1;
    c->vars[2] = (void*) n;
    release((object_t) k1);
    return (int) fib_cps(n - 2, c);
}

int fib_cps(int n, closure_t k)
{
    if ((n == 1) || (n == 2)) {
        return (int) k->func(1, k);
    } else {
        closure_t c = newClosure(2);
        c->func = (func_t) fib_cps_1;
        c->vars[0] = (void*) k;
        c->vars[1] = (void*) n;
        return fib_cps(n - 1, c);
    }
}

static int fib_cps_0(int n, closure_t k)
{
    release((object_t) k);
    return n;
}

int main(int argc, char *argv[])
{
    closure_t c = newClosure(0);
    c->func = (func_t) fib_cps_0;

    for (int i = 1; i < 10; i++) {
        addRef((object_t) c);
        printf("Fibonacci(%d) = %d\n", i, fib_cps(i, c));
    }

    release((object_t) c);

    return EXIT_SUCCESS;
}

見て分かる通り、参照カウンタを使って自前でオブジェクトの寿命を管理している。ガベージコレクションがない言語でクロージャを使うのがいかに大変かということがよく分かった。

なお、C99で拡張された機能を使っているので、gccでコンパイルする場合は

% gcc -Wall -std=c99 -DDEBUG fib.c

のように-std=c99を付けてコンパイルして下さい。

2006-03-28

読んだ本

Novel

初恋マジカルブリッツ大好きです、あなたにだけは伝えたい! / あすか正太 ISBN:4086302853
WW―記憶師たちの黄昏 / 吉田親司 ISBN:4840232113

未読を消化するために読んだけど、無理して読むこともなかったかな。

2006-03-28

Perlで継続渡し

Lisp Perl

色々な言語で継続渡しを書いてみよう企画。今回はPerlで。

#! /usr/bin/perl

use strict;

sub fib_cps {
    my ($n, $k) = @_;
    if (($n == 1) || ($n == 2)) {
        $k->(1);
    } else {
        &fib_cps($n - 1, sub {
            my $v1 = shift @_;
            my $k = $k;
            &fib_cps($n - 2, sub {
                my $v2 = shift @_;
                $k->($v1 + $v2);
            })
        });
    }
}

sub main {
    for my $i (1..9) {
        printf "Fibonacci(%d)= %d\n", $i, &fib_cps($i, sub { @_ });
    }
}
&main;

Perlは慣れているしクロージャを使うコードもよく見かけるから、今回は楽勝だと思っていたんだけど思わぬところでハマった。それがmy $k = $k;の一文。一見意味がないように見えるが、これがないと正しく動かない。Perlにはlocalとmyの２種類の局所変数があって、たぶん１つ目のクロージャの中で$kを使っていないと暗黙的にlocalとして扱われてしまうためだろう。これってバグに極めて近い仕様じゃないかと思うんだけど…。それ以外は特に難しいこともなく。問題はCで書く場合だよなあ。やり方は何パターンか思いつくけどどれもエレガントとはほど遠い。まあCで書く時点で泥臭くなるのは必然ではあるか。

他の言語と比べると、Perlでは以下のような特徴がある（改めて見るとかなり個性的な言語だ）

returnが不要
これはちょっとLispっぽい
ぶら下がりif文を許さない
閉じ括弧が開き括弧と同じインデントになるので、あまりLispっぽくは書けない
myとlocalの２種類の局所変数がある
それぞれレキシカルスコープとダイナミックスコープになる。他の言語（特にコンパイル方式の言語）ではレキシカルスコープが普通。SchemeやCommon Lispのletはレキシカルスコープだけどダイナミックスコープのfluid-letもある。Emacs Lispのletはダイナミックスコープ
変数の種類によって$や@を付ける（$_と@_は別の変数）
$kにコードのリファレンスが入っているとき、$k->()でコードを呼び出せる
関数呼び出しは先頭に&を付けて表す（付けなくていい場合もある）
関数呼び出しとコードリファレンスの呼び出しで形式が違うのがちょっとスマートじゃないかも
仮引数はない
まとめてリストとして@_で渡されるので、必要に応じて自分で分解する
関数のプロトタイプ宣言はできるけどあまり使われない
プロトタイプ宣言を含めると、例えばsub fib_cps($$) { ... のようになる