Schemeをつくろう(1) アトム再考

id:YasuyukiMiuraさんからツッコミを頂いてアトムについて考え直しました。

アトムは原子であり割り切れない単位であるので、そこにリスト(対)を含めてしまうのは良くない訳ですよ。アトムが割り切れてしまいます。

Schemeの仕様書R5RSには、「アトム」という表現ではなく、「オブジェクト」という表記で書かれてました。ここら辺がLispとの違いなのかもしれません。

Schemeで言うオブジェクトはこんな感じかな。

-オブジェクト---
| アトム-数値
|      -文字
|      -シンボル
| 対
| 手続き
| ...

僕はこう書いちゃった。

アトム-数値
      -文字
      -シンボル
      -対

確かに良くない。対は割り切れちゃうよね。

なので、アトムをオブジェクトと同列に並べることにしました。

-オブジェクト---
| 数値
| 文字
| シンボル
| 対
| 手続き
| ...

オブジェクトなら対を含めても問題ないと思います。

実装すると、

struct object {
    int type;
    union {
        struct cell cell;
        struct symbol symbol;
        struct integer integer;
    } data;
};

名前を変えただけです(汗

名前を変えただけですが、かなり意味が違う気がします。この中にstruct atomを含めても問題ないと思います。

書くぞぉ

もう一度オブジェクトの定義をやり直します。

まずはヘッダ。

list.hとしました。このヘッダは分離されて消えていく予定です。

#include <stdbool.h>

#define list_debug 0

enum { T_CELL, T_SYMBOL, T_INTEGER };

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

struct symbol {
    char *s;
};

struct integer {
    int n;
};

struct object {
    int type;
    union {
        struct cell cell;
        struct symbol symbol;
        struct integer integer;
    } data;
};
typedef struct object object;

object *new_object(void);
void free_object(object *o);
void free_objects(object *o);

object *cons(object *car, object *cdr);
object *car(object *o);
object *cdr(object *o);

object *null(void);
bool is_null(object *o);

object *integer(int n);
bool is_integer(object *o);
int get_integer(object *o);

object *symbol(char *str);
bool is_symbol(object *o);
char *get_symbol(object *o);

void newline(void);
void display (object *o);

実装。

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

#include "list.h"

/* object */
object *new_object(void)
{
    return malloc(sizeof (object));
}
void free_object(object *o)
{
    free(o);
}

void free_objects(object *o)
{
#if list_debug
    display(o);
    newline();
#endif
    if (o->type == T_CELL) {
        if (!is_null(o)) {
            free_objects(car(o));
            free_objects(cdr(o));
        }
#if list_debug
        else {
            printf("- null free\n");
        }
#endif
#if list_debug
        printf("- parent free\n");
#endif
        free(o);
    } else {
        if (o->type == T_SYMBOL) {
#if list_debug
            printf("- symbol free\n");
#endif
            free(get_symbol(o));
        }
#if list_debug
        printf("- child free\n");
#endif
        free(o);
    }
}


/* cell (pairになるかも) */
object *cons(object *car, object *cdr)
{
    object *o= new_object();

    o->type = T_CELL;
    o->data.cell.car = car;
    o->data.cell.cdr = cdr;

    return o;
}

object *car(object *o)
{
    return o->data.cell.car;
}

object *cdr(object *o)
{
    return o->data.cell.cdr;
}

object *null(void)
{
    return cons(NULL, NULL);
}

bool is_null(object *o)
{
    return (o->type == T_CELL && car(o) == NULL && cdr(o) == NULL) ? true : false;
}

bool is_pair(object *o)
{
    return (o->type == T_CELL && !is_null(o))? true: false;
}


/* integer */
object *integer(int n)
{
    object *o = new_object();

    o->type = T_INTEGER;
    o->data.integer.n = n;

    return o;
}

bool is_integer(object *o)
{
    return (o->type == T_INTEGER) ? true : false;
}

int get_integer(object *o)
{
    if (!is_integer(o)) {
        printf("---- error");
        return 0;
    } else {
        return o->data.integer.n;
    }
}

/* symbol */
object *symbol(char *s)
{
    object *o = new_object();

    o->type = T_SYMBOL;

    o->data.symbol.s = malloc((strlen(s) + 1) * sizeof (char));
    strcpy(get_symbol(o), s);
    return o;
}

bool is_symbol(object *o)
{
    return (o->type == T_SYMBOL) ? true : false;
}

char *get_symbol(object *o)
{
    if (!is_symbol(o)) {
        printf("---- error");
        return 0;
    } else {
        return o->data.symbol.s;
    }
}


/* display */
void display(object *o)
{
    switch (o->type) {
    case T_SYMBOL :
        printf("%s", get_symbol(o));
        break;
    case T_INTEGER :
        printf("%d", get_integer(o));
        break;
    case T_CELL :
        if (is_null(o)) {
            printf("()");
        } else {
            printf("(");
            for(;;) {
                display(car(o));
                if (is_null(cdr(o))) {
                    break;
                } else if(!is_pair(cdr(o))) {
                    printf(" . ");
                    display(cdr(o));
                    break;
                }
                printf(" ");
                o = cdr(o);
            }
            printf(")");
        }
        break;
    }
}

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

空リストと、シンボルを追加しました。mainは略。

実行すると。

(1 2 3 4)
(symbol Hello-Scheme-World!!)

おぉぉぉ。リストらしくなってきました。

追記

free_objectとfree_objectsに分けました。