Schemeをつくろう(13) シンボルテーブルづくり

Scheme

僕のSchemeではシンボルは「文字列」という極めて単純な作りになってます。シンボルが文字列だと色々問題点がありそうなので、問題点をピックアップしながら対策を練っていきます。

問題点

シンボルが文字列だと、

  • 重い
    • シンボルの比較が重い
  • メモリ食いまくり
    • シンボルがあった > メモリ確保!!

という感じで、パフォーマンス的にあんまり良くない。速度は重要視していないので「まぁいっか」。となる所ですが大きな問題点があるのです。

「シンボルは一個だけ」

というルールに沿っていないので、僕のSchemeの実装では(eq? 'symbol 'symbol)は#fになってしまいます。strcmpで誤魔化そうと思えばできるのですが、これはちょっとイカン。ということで、シンボルのid化(シンボルテーブル化)に着手します。

シンボルテーブルの作戦を練る

どんなのがいいかなぁ

  • ハッシュ
    • 時間がかかりそうなのでパス。
  • 文字列のリスト
    • これもいいかなぁ。と思ったけど、文字列型が無いのでパス。
  • 配列

ということで、配列で作ってみます。

実装

こんな感じ。

#define SYMBOL_TABLE_SIZE 512

static char symbol_table[SYMBOL_TABLE_SIZE];
static int tail = 0;

char *append_symbol_table(char *symbol)
{
    int i,j;

    /* find symbol */
    for (i = 0; i < tail; i++) {                                  /* next */
        for (j = 0; *(symbol + j) == symbol_table[i + j] ; j++) { /* strcmp */
            if (*(symbol + j) == '\0')
                return symbol_table + i;                          /* found! */
        }
        for(i += j;symbol_table[i] != '\0'; i++)                  /* jump to '\0' */
            ;
    }

    /* not found -> append */
    i = tail;
    for (;*symbol != '\0';symbol++) {
        if (tail < SYMBOL_TABLE_SIZE - 1)
            symbol_table[tail++] = *symbol;
        else {
            fprintf(stderr, "ERROR : symbol table over flow.\n");
            exit(EXIT_FAILURE);
        }
    }
    symbol_table[tail++] = '\0';

    return symbol_table + i;
}

うぅん。シンプル!!

配列でもリストでも感覚が変わらなくなってきた。cdrダウン(symbol_table[i] != '\0')しながら、car(*(symbol + j) == symbol_table[i + j])を見る。どっちもおんなじようなもんだ。

ちょっと覗いてみる

配列の中を覗いてみると。

+ car cdr cons display newline hello world quote define eval if

おぉぉぉ。ユニークに絞られてますね。スンバラシイ!

'\0'区切りでまんま挿入しただけですが(笑

シンボル取得のコストは高いのですが、シンボルの比較はメモリのアドレスを見ればいいだけ。また、idは文字列の先頭アドレスになっているので、そのままprintfに渡してやれば、文字を出力出来ます。APIの変更も殆んど無く移行完了です。


とりあえずシンボルが一個だけになったので目標達成〜。

追記

文字列はユニークになったけどシンボルはユニークに出来なかった。


文字列のリストで実現しました。次をどぞ。