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さんのツッコミがあったのでちょっと修正。僕は「対」の事をリストと表現してしまいました。「対の並びをリストと呼ぶ」この表現が正しいですね。