Schemeをつくろう(0) まずはリスト

作ってみないとわからないのがSchemeかと。

そんなわけでまったりSchemeを作っていこうと思います。

目的とか

  • Schemeを作る一番の目的はメモリ管理について学ぶこと。
    • OS自作にも大いに役立つかなぁと思うので。
  • なるべく仕様に近い形で
    • R5RSを目標に・・・。
  • 速度よりも柔軟さ
    • あんまり早さに拘らず。
  • 言語はCを選択。
    • なるべくメモリが抽象化されていない所で。

まったりやっていきたいと思います。

ちょっと作ってみた。

字句解析部分を適当に作った所で、ふと気づいた。

「リストが無いと何も出来ん!!」

そんなわけでリストから作っていきます。

方針

対やら、数値やら、文字など、それ以上割り切れないモノを「原子(atom)」と定義します。

struct atom {
    int type;
    union {
        struct integer integer;
        struct cell cell;
    } object;
};

メモリを多めに食うけど、struct cell cellとして構造体の入れ子を作ってます。malloc(sizeof (struct atom))とやれば、対でも数値でも関係なくメモリの確保が出来る仕組みです。お手軽。

atomにはとりあえず対と整数があればいいかな。

書くぞぉ

さて、方針が決まったらバリバリ書くぞぉ

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

#define debug 1

struct cell {
    struct atom *car;
    struct atom *cdr;
};

struct integer {
    int n;
};

enum { T_INTEGER, T_CELL };

struct atom {
    int type;
    union {
        struct integer integer;
        struct cell cell;
    } object;
};
typedef struct atom atom;

atom *new_atom(void);
void free_atom(atom *atom);

atom *cons(atom *car,
           atom *cdr);
atom *car(atom *atom);
atom *cdr(atom *atom);

atom *integer(int n);

void newline(void);
void display (atom *atom);

/* main */
int main(void)
{
    atom *cell = cons(integer(1),
                             cons(integer(2),
                                  integer(3)));

    display(cell);

#if debug
    printf("\n\n-- start free\n");
#endif

    free_atom(cell);

    return EXIT_SUCCESS;
}


/* atom */
atom *new_atom(void)
{
    return malloc(sizeof (atom));
}

void free_atom(atom *a)
{
#if debug
    display(a);
    newline();
#endif
    if (a->type == T_CELL) {
        free_atom(car(a));
        free_atom(cdr(a));
#if debug
        printf("- parent free\n");
#endif
        free(a);
    } else {
#if debug
        printf("- child free\n");
#endif
        free(a);
    }
}


/* list */
atom *cons(atom *car,
           atom *cdr)
{
    atom *a= new_atom();

    a->type = T_CELL;
    a->object.cell.car = car;
    a->object.cell.cdr = cdr;

    return a;
}

atom *car(atom *a)
{
    return a->object.cell.car;
}

atom *cdr(atom *a)
{
    return a->object.cell.cdr;
}


/* integer */
atom *integer(int n)
{
    atom *a = new_atom();

    a->type = T_INTEGER;
    a->object.integer.n = n;

    return a;
}


/* display */
void display (atom *a)
{
    if (a->type == T_INTEGER) {
        printf("%d", a->object.integer.n);
    } else if(a->type == T_CELL) {
        printf("(");
        display(car(a));
        printf(" . ");
        display(cdr(a));
        printf(")");
    }
}

void newline(void)
{
    printf("\n");
}

いきなりナガっ!!

さてさて、実行してみまっす!!

% make
gcc -o list list.c
./list
(1 . (2 . 3))

-- start free
(1 . (2 . 3))
1
- child free
(2 . 3)
2
- child free
3
- child free
- parent free
- parent free

おぉ。リストだぁ〜。

free_atomで親を消したらズラズラ〜とfree出来るようにしました。いきなり再帰ですね・・・。


空リストってどうやって作るんだろう。

追記

id:YasuyukiMiuraさんのツッコミがあったのでちょっと修正。僕は「対」の事をリストと表現してしまいました。「対の並びをリストと呼ぶ」この表現が正しいですね。