Tociyuki::Diary RSSフィード

tociyuki による Perl・Ruby・C++・C で書き散らしたコードを中心に、日常雑記も混在 : B  F  twitter  GitHub  CPAN  本館  公開鍵
 

2018年04月21日

[]Turing 言語のコレクション

1980 年代初頭にトロント大学で開発された PASCAL 系列のプログラミング言語 Turing はコレクションと名づけられたおもしろい機能をもっています。 「型 T のコレクションとは、 型 T へのポインタの集合のインスタンスである」として定義してあります。

⇒ R. C. ホルト他著、 湯浅太一他訳 プログラミング言語 Turing 1990、 ISBN 4-7665-1075-5

コレクションは代入したり、 比較したり、 引数として渡したり、 bind したり、 const 宣言によって名前をつけたりすることはできない。 コレクションは副プログラムの中で宣言してはいけない。 (73 ページ)

コレクションはグローバルなシングルトンであり、 その要素の型が一対一で決まっています。 そのため、 コレクションによって要素の型を指定することが可能です。 ポインタ定義にコレクション識別子を使うとき、 ポインタ定義に使うコレクション識別子は、 そのコレクションに結びついている要素の型を表すわけです。

var slist: collection of
            record
              entry: integer
              next: pointer to slist
            end

var first: pointer to slist := nil(slist)

procedure slist_prepend(p: pointer to slist)
    slist(p).next := first
    first := p
end slist_prepend

var item: pointer to slist
new slist, item
slist(item).entry := 1
slist_prepend(item)

2018年04月20日

[]BASE 64/32 を 32/64 ビット回転に改訂

2 年前に C++11 で書いた BASE64 と BASE32 エンコーダのビット回転をワード幅でおこなうように改訂しました。 これまでは、 BASE64 で 24 ビットのビット回転をおこなっていました。 そのため、 コンパイラがビット・シフト命令とビット論理和命令を生成していました。 そこで、 ワード幅のビット回転に変更し、 ビット回転イディオムを認識するコンパイラでは、 ビット回転命令を生成させるようにしました。 さほど実行速度の向上にはつながりませんが、 生成されるコードサイズが若干縮まります。

-        u = (u << 16) | (u1 << 8) | u2;
+        u = (u << 24) | (u1 << 16) | (u2 << 8);
         for (int i = 0; i < n; ++i) {
-            u = (u << 6) | (u >> 18);
+            u = (u << 6) | (u >> 26);
             out.push_back (b64[u & 0x3f]);
         }

2018年04月15日

[][]Chibi Scheme のゴミ集め

Chibi Scheme の組み込み手続きは C 言語の関数で記述してあり、 C 言語の auto 変数をヒープ中の Scheme のセルに束縛しています。 そのため、 ゴミ集め時に C 言語のコール・スタックを調べる必要が生じ、 3 つの方式を処理系のビルド時に選べるようになっています。

  1. Boehm GC による保守なゴミ集め
  2. 組み込みマーク & スイープによる保守なゴミ集め
  3. 組み込みマーク & スイープによる完全なゴミ集め

保守なゴミ集めは、 コール・スタックとプロセッサレジスタの退避値を使えば済みますが、 完全なゴミ集めのためには、 Scheme のセルへのポインタがコール・スタック中のどこにあるのかわかっている必要があります。 この目的のため、 Chibi Scheme は、 auto 変数へのリストを作成します。

struct scheme_root_list {
    scheme_value_t** root;
    struct scheme_root_list* next;
};

void scheme_gc_mark_root_list (scheme_t* ctx)
{
    struct scheme_root_list *list;

    for (list = ctx->root_list; list != NULL; list = list->next)
        scheme_gc_mark_cell (ctx, *(list->root));
}

auto 変数へのリストは C プリプロセッサ・マクロでポインタ・リストで作るようになっています。 それを展開すると、 コール・スタック中にポインタ・リストを作成するコードに展開されます。 概念上は次のようになります。

scheme_value_t* scheme_append2(scheme_t* ctx; scheme_value_t* a, scheme_value_t* b)
{
    scheme_value_t* res = SCHEME_NULL;
    scheme_value_t* p = SCHEME_NULL;
    scheme_value_t* t = SCHEME_NULL;

    // 完全なゴミ集め用のポインタ・リストのセル
    struct scheme_root_list gclist_a;
    struct scheme_root_list gclist_b;
    struct scheme_root_list gclist_res;

    // 完全なゴミ集め用のポインタ・リストに auto 変数を追加
    gclist_a.root   = &a;   gclist_a.next   = ctx->root_list;
    gclist_b.root   = &b;   gclist_b.next   = &gclist_a;
    gclist_res.root = &res; gclist_res.next = &gclist_b;
    ctx->root_list = &gclist_res;

    // append2 本体
    if (scheme_null (ctx, a)) {
        res = b;
    }
    else {
        res = p = scheme_make_pair (ctx);   // ゴミ集めする可能性あり
        scheme_set_car (ctx, p, (scheme_car (ctx, a)));
        a = scheme_cdr (ctx, a);
        while (scheme_pair_ques (ctx, a)) {
            t = scheme_make_pair (ctx);     // ゴミ集めする可能性あり
            scheme_set_car (ctx, t, scheme_car (ctx, a));
            scheme_set_cdr (ctx, p, t);
            a = scheme_cdr (ctx, a);
            p = t;
        }
        if (! scheme_null (ctx, a)) {
            scheme_error_cstr (ctx, "append2 - improper list");
        }
        scheme_set_cdr (ctx, p, b);
    }

    // 完全なゴミ集め用のポインタ・リストから auto 変数を削除
    ctx->root_list = gclist_a.next;

    return res;
}

ポインタ・リストにアドレスを書き込む auto 変数をスタック・メモリに割り当てることを C コンパイラに要求していることになります。 マーク & スイープなので、 ポインタの値をゴミ集めが変更することはないため、 volatile にする必要こそありませんが、 最適化の余地が狭くなる点では、 保守なゴミ集めよりも不利な気がします。