Common Lisp風のLISPを作ってみる（９．ドットリスト）

ドットリスト(dotted list)とは、リストの終端がNILではなくアトムであるものを言います。表記が(1 2 3 . 4)のようにドットを含むのでドットリストと言います。my-lisp2では、ドットリストが入力されると、まずドット記号を含むリストとしてリードし、それを見つけてドットリストに直します。ちなみに(1 2 . 3 4)というようにドットが最後の要素の手前にない場合はエラーとなりますので、そのコードも実装します。
ソースコード

dot.h

dot.h

/*
 * dot.h
 */

#ifndef DOT_H_
#define DOT_H_

void fix_to_dotted_list(void *obj);
int check_single_dot(void *obj);

#endif

dot.c

インクルード文です。

dot.c

/*
 * dot.c
 */

#include <string.h>
#include "../chapter02/type.h"
#include "helper.h"

fix_to_dotted_list関数は、ドット記号を含むリストをドットリストに変換する関数です。

dot.c

/*
 * この関数は、リーダーで得られたオブジェクトに対して適用するので、
 * リストはドッティドリストを含まないことを想定している。
 */
void fix_to_dotted_list(void *obj) {
    if (consp(obj)) {
        /* リスト上の要素全てに再帰を適用する */
        {
            void *p = obj;
            while (p != NIL) {
                fix_to_dotted_list(car(p));
                p = cdr(p);
            }
        }
        /* リストの長さを数える */
        {
            size_t len = 0;
            void *p = obj;
            void *q;
            void *r;
            while (p != NIL) {
                len++;
                p = cdr(p);
            }
            /* 最後から３つ目に移動 */
            if (len < 3) return;
            p = obj;
            for (len -= 3; len != 0; len--) {
                p = cdr(p);
            }
            /* 最後から２つ目がドット(.)のシンボルであるかを調べる */
            q = cdr(p);
            r = cdr(q);
            if (!symbolp(car(q)))
                return;
            if (strcmp(get_symbol_string((SYMBOL *)(car(q))), ".") != 0)
                return;
            /* 最後の要素を３番目のcdrに付け替える */
            rplacd(p, car(r));
        }
    }
}

check_single_dot関数は与えられたフォームの中に.というシンボルがあるかを判別します。

dot.c

/*
 * 非0ならばOK、0ならばNG
 */
int check_single_dot(void *obj) {
    if (symbolp(obj)) {
        SYMBOL *s = (SYMBOL *)obj;
        return strcmp(get_symbol_string(s), ".");
    }
    if (consp(obj)) {
        void *p = obj;
        while (consp(p)) {
            if (!check_single_dot(car(p))) return 0;
            p = cdr(p);
        }
        if (p != NIL && !check_single_dot(p)) return 0;
    }
    return 1;
}

helper.c

symbolp関数はオブジェクトがシンボル型であるかを判別します。

helper.c

int symbolp(void *obj) {
    HEADER *h = (HEADER *)obj;
    return (h->type == TYPE_SYMBOL);
}

test.c

リードとプリントの間にドットリスト関連のルーチンが入っています。

test.c

/*
 * test.c
 */

#include <stdio.h>
#include "../chapter05/state.h"
#include "../chapter08/reader.h"
#include "../chapter07/printer.h"
#include "dot.h"

int main(void) {
    reader_initialize();
    while (1) {
        printf("> ");
        void *obj = reader_read(stdin);
        if (!obj) {
            if (state == STATE_EXIT) {
                reader_free();
                return 0;
            } else if (state == STATE_ERROR) {
                state = STATE_NORMAL;
                continue;
            } else {
                fprintf(stderr, "未実装のコードに到達しました\n");
                continue;
            }
        }
        fix_to_dotted_list(obj);
        if (!check_single_dot(obj)) {
            fprintf(stderr, "ドットをシンボルとして使用することはできません\n");
            continue;
        }
        printer_print(stdout, obj);
        fputc('\n', stdout);
    }
    return 0;
}

動かしてみよう

(1 2 3 . 4)はドットリストなので、内部で変換されています。ただしプリンターもドットリストに対応しているので入力と出力が一致します。間違った位置にドットを配置した場合はエラーが発生します。

> (1 2 3 . 4)
(1 2 3 . 4)
> (1 2 . 3 4)
ドットをシンボルとして使用することはできません
> (1 2 3 4 .)
ドットをシンボルとして使用することはできません