Big Sky :: プログラミング言語の作り方
Big Sky :: プログラミング言語の作り方(2)
Big Sky :: プログラミング言語の作り方(4)
Big Sky :: プログラミング言語の作り方(5)
もうちょっと続けてみようと思います。
Big Sky :: プログラミング言語の作り方
github の trending を見てたら面白い物を見つけた。 orangeduck/BuildYourOwnLisp - GitHub Learn C and build your own pr...
http://mattn.kaoriya.net/software/build_your_own_programming_language.htm
Big Sky :: プログラミング言語の作り方(2)
この前の記事がなかなか人気があったので、続きを書いてみます。 Big Sky :: プログラミング言語の作り方 github の trending を見てたら面白い物を見つけた。 orangeduck...
http://mattn.kaoriya.net/software/build_your_own_programming_language2.htm
言語名を決めました。「俺言語」です。
mattn/orelang - GitHub
俺言語
https://github.com/mattn/orelang/
今回は今後を見据えてコードのブラッシュアップを行いたいと思います。
軽微な修正
前回までのコードですと、ステートメントが EOF で終了するという定義が出来ていなかったので、途中でパースエラーが起きても正常に動作してしまっていました。そこで一番外側を stmts ではなく program という識別にして「ステートメントの繰り返しがあり、最後に EOF が来る」という定義にしました。オマケで comment も足しておきました。
comment : /#[^\n]*/ ;
eof : /$/ ;
stmt : (<let> | <call> | <comment>) ;
program : <stmt>* <eof> ;
これで俺言語の中でコメントが打てる様になります。
リファクタリング
次に言語も決まった事なのでリファクタリングを行いました。
全ての関数に
ore プレフィックスを付けました。この辺は好き好きですが付けておくと愛着が湧いたりします(どうでもいいですね)。
また今回の修正で扱える様にする型を増やして以下の様に ore_value (値を格納する構造体) を定義しました。
typedef enum {
ORE_TYPE_NIL,
ORE_TYPE_INT,
ORE_TYPE_FLOAT,
ORE_TYPE_STR,
ORE_TYPE_FUNC,
ORE_TYPE_CFUNC
} ore_type;
typedef mpc_ast_t* ore_func;
typedef struct _ore_value {
ore_type t;
union _v {
int i;
double d;
char* s;
void* c;
ore_func f;
} v;
} ore_value;
ORE_TYPE_CFUNC は前回追加した println の様な「C言語側の関数」を、ORE_TYPE_FUNC は俺言語内で定義した関数を格納します。
便利関数 ore_define_cfunc を用意して、println の様なコア関数の登録を簡単に出来る様にしました。
ore_value
ore_println(ore_context* ore, int num_in, ore_value* args) {
int i;
for (i = 0; i < num_in; i++) {
if (i != 0) printf(", ");
switch (args[i].t) {
case ORE_TYPE_NIL:
printf("nil");
break;
case ORE_TYPE_INT:
printf("%d", args[i].v.i);
break;
case ORE_TYPE_FLOAT:
printf("%f", args[i].v.d);
break;
case ORE_TYPE_STR:
printf("%s", args[i].v.s);
break;
default:
printf("<unkonwn>");
break;
}
}
printf("\n");
return ore_value_nil();
}
この様な関数シグネチャにしておき、以下の様に登録します。
ore_context* ore = ore_new(NULL);
ore_define_cfunc(ore, "println", ore_println);
ore_eval(ore, result.output);
ore_destroy(ore);
今後、配列をサポートした際の
len() 関数等も簡単に作成出来る様になりました。
今後の目論見
上記で説明した ore_println の第一引数に ore_context というのが出てきました。ore_context 構造体は以下の通り。
typedef struct _ore_context {
khash_t(ident)* env;
klist_t(ident)* gc;
struct _ore_context* parent;
} ore_context;
前回グローバル変数で宣言していた env と gc を構造体内部に押しやりました。単純にかっこいいからとかではなく、こうしたのにはちゃんと理由があります。この env は ident で示す識別に対して値を格納する物、つまり「スコープ」の役割を果たします。今後、関数宣言を追加しますがその際にスコープを拘束する必要があるのです。また関数が終了するとメモリの解放が必要になります。
プログラミング言語のスコープには大きく分けて2つあります。
俺言語ではレキシカルスコープを採用する予定なので、関数宣言とその宣言時の環境を抱合せて保持する必要があります。理由は以下のJavaScriptのコードで分かるかと思います。
var count = function() {
var c = 1;
return function() {
return c++;
};
}();
console.log(count());
console.log(count());
まず
c が宣言されるのは関数スコープとなります。また
c の宣言はグローバルスコープを汚す物であってはなりません。
また
c は
count が保持する環境を参照してインクリメンタルする必要があります。
上記、ore_context 構造体で parent を保持しているのにも理由があります。
例えば
c = 1;
と実行される場合、以下の処理を行う必要があります。
- 現在のスコープからグローバルスコープに向かって
c という識別で検索し、見つかれば値を 1 に更新する。
- どこにもなければグローバルスコープに
c という識別で値 1 を保存する。
その為、現在のスコープからグローバルスコープに向かって探索出来る様に parent が必要となります。今回は対応しませんが今後、上記の関数スコープを実装します。その為の準備となります。
浮動小数点のサポート
上記で ore_value に double 型を追加しています。そこで number 識別を認識した際のパース処理を以下の様に修正します。
ore_value
ore_parse_num(ore_context* ore, const char* s) {
ore_value v;
if (!strchr(s, '.')) {
v.t = ORE_TYPE_INT;
v.v.i = atoi(s);
} else {
v.t = ORE_TYPE_FLOAT;
v.v.d = atof(s);
}
return v;
}
横着感が満載ですね。同様に演算部分も修正します。
if (is_a(t, "lexp") || is_a(t, "term")) {
v = ore_eval(ore, t->children[0]);
for (i = 1; i < t->children_num; i += 2) {
char* op = t->children[i]->contents;
ore_value rhs = ore_eval(ore, t->children[i+1]);
switch (v.t) {
case ORE_TYPE_INT:
{
int iv = rhs.t == ORE_TYPE_INT ? rhs.v.i : rhs.t == ORE_TYPE_FLOAT ? (int) rhs.v.d : 0;
if (strcmp(op, "+") == 0) { v.v.i += iv; }
if (strcmp(op, "-") == 0) { v.v.i -= iv; }
if (strcmp(op, "*") == 0) { v.v.i *= iv; }
if (strcmp(op, "/") == 0) { v.v.i /= iv; }
if (strcmp(op, "%") == 0) { v.v.i %= iv; }
}
break;
case ORE_TYPE_FLOAT:
{
double fv = rhs.t == ORE_TYPE_INT ? (double) rhs.v.i : rhs.t == ORE_TYPE_FLOAT ? rhs.v.d : 0;
if (strcmp(op, "+") == 0) { v.v.d += fv; }
if (strcmp(op, "-") == 0) { v.v.d -= fv; }
if (strcmp(op, "*") == 0) { v.v.d *= fv; }
if (strcmp(op, "/") == 0) { v.v.d /= fv; }
if (strcmp(op, "%") == 0) { v.v.d = ((int) v.v.d % (int) fv); }
}
break;
}
}
return v;
}
今後、文字列の足し算で文字列結合する処理も必要になりますね。
関数宣言
今回の修正で yacc 構文を以下の様にしました。
#define STRUCTURE \
" \n" \
"number : /-?[0-9]+(\\.[0-9]*)?(e[0-9]+)?/ ; \n" \
"factor : '(' <lexp> ')' \n" \
" | <number> \n" \
" | <string> \n" \
" | <lambda> \n" \
" | <ident> ; \n" \
"string : /\"[^\"]*\"/ ; \n" \
"ident : /[a-zA-Z][a-zA-Z0-9_]*/ ; \n" \
" \n" \
"term : <factor> (('*' | '/' | '%') <factor>)* ; \n" \
"lexp : <term> (('+' | '-') <term>)* ; \n" \
"let : <ident> '=' <lexp> ';' ; \n" \
" \n" \
"lambda : /func/ " \
" '(' <ident>? (',' <ident>)* ')' '{' <stmt>* '}' ; \n" \
"func : /func/ <ident> " \
" '(' <ident>? (',' <ident>)* ')' '{' <stmt>* '}' ; \n" \
" \n" \
"call : <ident> '(' <lexp>? (',' <lexp>)* ')' ';' ; \n" \
"comment : /#[^\n]*/ ; \n" \
"eof : /$/ ; \n" \
"stmt : (<let> | <call> | <func> | <comment>) ; \n" \
"program : <stmt>* <eof> ; \n"
factor に lambda を、stmt に func を追加しました。引数部は
ident の羅列を受け取ります。
今回は実装していないので引数の受け渡しは動作しませんが、今後「関数スコープ」が実装された際は、関数呼び出し時に新規に env を作成し、ident が示す変数名を登録してあげれば引数が渡される事になります。
最後に全体のコードを載せて置きます。
#include "mpc.h"
#include "khash.h"
#include "klist.h"
#define STRUCTURE \
" \n" \
"number : /-?[0-9]+(\\.[0-9]*)?(e[0-9]+)?/ ; \n" \
"factor : '(' <lexp> ')' \n" \
" | <number> \n" \
" | <string> \n" \
" | <lambda> \n" \
" | <ident> ; \n" \
"string : /\"[^\"]*\"/ ; \n" \
"ident : /[a-zA-Z][a-zA-Z0-9_]*/ ; \n" \
" \n" \
"term : <factor> (('*' | '/' | '%') <factor>)* ; \n" \
"lexp : <term> (('+' | '-') <term>)* ; \n" \
"let : <ident> '=' <lexp> ';' ; \n" \
" \n" \
"lambda : /func/ " \
" '(' <ident>? (',' <ident>)* ')' '{' <stmt>* '}' ; \n" \
"func : /func/ <ident> " \
" '(' <ident>? (',' <ident>)* ')' '{' <stmt>* '}' ; \n" \
" \n" \
"call : <ident> '(' <lexp>? (',' <lexp>)* ')' ';' ; \n" \
"comment : /#[^\n]*/ ; \n" \
"eof : /$/ ; \n" \
"stmt : (<let> | <call> | <func> | <comment>) ; \n" \
"program : <stmt>* <eof> ; \n"
void ore_free(void *p);
#define is_a(t, a) (strstr(t->tag, a) != NULL)
typedef enum {
ORE_TYPE_NIL,
ORE_TYPE_INT,
ORE_TYPE_FLOAT,
ORE_TYPE_STR,
ORE_TYPE_FUNC,
ORE_TYPE_CFUNC
} ore_type;
typedef mpc_ast_t* ore_func;
typedef struct _ore_value {
ore_type t;
union _v {
int i;
double d;
char* s;
void* c;
ore_func f;
} v;
} ore_value;
KHASH_MAP_INIT_STR(ident, ore_value)
KLIST_INIT(ident, ore_value, ore_free)
typedef struct _ore_context {
khash_t(ident)* env;
klist_t(ident)* gc;
struct _ore_context* parent;
} ore_context;
typedef ore_value (*ore_cfunc_t)(ore_context*, int, ore_value*);
ore_value ore_call(ore_context*, mpc_ast_t*);
ore_value ore_eval(ore_context*, mpc_ast_t*);
void
ore_free(void *p) {
ore_value* v = (ore_value*) p;
switch (v->t) {
case ORE_TYPE_STR:
free(v->v.s);
break;
case ORE_TYPE_FUNC:
free(v->v.c);
break;
}
}
ore_value
ore_value_nil() {
ore_value v = { ORE_TYPE_NIL, 0 };
return v;
}
ore_value
ore_parse_num(ore_context* ore, const char* s) {
ore_value v;
if (!strchr(s, '.')) {
v.t = ORE_TYPE_INT;
v.v.i = atoi(s);
} else {
v.t = ORE_TYPE_FLOAT;
v.v.d = atof(s);
}
return v;
}
ore_value
ore_parse_str(ore_context* ore, const char* s) {
ore_value v = { ORE_TYPE_STR };
size_t l = strlen(s) - 2;
v.v.s = calloc(1, l + 1);
strncpy(v.v.s, s + 1, l);
v.v.s[l] = 0;
*kl_pushp(ident, ore->gc) = v;
return v;
}
ore_value
ore_println(ore_context* ore, int num_in, ore_value* args) {
int i;
for (i = 0; i < num_in; i++) {
if (i != 0) printf(", ");
switch (args[i].t) {
case ORE_TYPE_NIL:
printf("nil");
break;
case ORE_TYPE_INT:
printf("%d", args[i].v.i);
break;
case ORE_TYPE_FLOAT:
printf("%f", args[i].v.d);
break;
case ORE_TYPE_STR:
printf("%s", args[i].v.s);
break;
default:
printf("<unkonwn>");
break;
}
}
printf("\n");
return ore_value_nil();
}
ore_value
ore_define_cfunc(ore_context* ore, const char* name, ore_cfunc_t c) {
int r = 0;
khint_t k = kh_put(ident, ore->env, name, &r);
ore_value v = { ORE_TYPE_CFUNC };
v.v.c = c;
kh_value(ore->env, k) = v;
return v;
}
ore_value
ore_call(ore_context* ore, mpc_ast_t *t) {
khint_t k = kh_get(ident, ore->env, t->children[0]->contents);
if (k == kh_end(ore->env)) {
fprintf(stderr, "Unknwn function '%s'\n", t->children[0]->contents);
return ore_value_nil();
}
ore_value fn = kh_value(ore->env, k);
ore_value v = ore_value_nil();
switch (fn.t) {
case ORE_TYPE_CFUNC:
{
int num_in = t->children_num / 2 - 1, n = 0, i;
ore_value* args = (ore_value*) malloc(sizeof(ore_value) * num_in);
for (i = 2; i < t->children_num - 2; i += 2) {
args[n++] = ore_eval(ore, t->children[i]);
}
v = ((ore_cfunc_t)fn.v.c) (ore, num_in, args);
free(args);
}
break;
case ORE_TYPE_FUNC:
TODO
v = ore_eval(ore, fn.v.f);
break;
}
return v;
}
ore_value
ore_eval(ore_context* ore, mpc_ast_t* t) {
int i, r;
ore_value v;
if (is_a(t, "eof") || is_a(t, "comment")) {
return ore_value_nil();
}
if (is_a(t, "number")) {
return ore_parse_num(ore, t->contents);
}
if (is_a(t, "string")) {
return ore_parse_str(ore, t->contents);
}
if (is_a(t, "ident")) {
khint_t k = kh_get(ident, ore->env, t->contents);
if (k == kh_end(ore->env)) {
return ore_value_nil();
}
return kh_value(ore->env, k);
}
if (is_a(t, "factor")) {
return ore_eval(ore, t->children[1]);
}
if (is_a(t, "lexp") || is_a(t, "term")) {
v = ore_eval(ore, t->children[0]);
for (i = 1; i < t->children_num; i += 2) {
char* op = t->children[i]->contents;
ore_value rhs = ore_eval(ore, t->children[i+1]);
switch (v.t) {
case ORE_TYPE_INT:
{
int iv = rhs.t == ORE_TYPE_INT ? rhs.v.i : rhs.t == ORE_TYPE_FLOAT ? (int) rhs.v.d : 0;
if (strcmp(op, "+") == 0) { v.v.i += iv; }
if (strcmp(op, "-") == 0) { v.v.i -= iv; }
if (strcmp(op, "*") == 0) { v.v.i *= iv; }
if (strcmp(op, "/") == 0) { v.v.i /= iv; }
if (strcmp(op, "%") == 0) { v.v.i %= iv; }
}
break;
case ORE_TYPE_FLOAT:
{
double fv = rhs.t == ORE_TYPE_INT ? (double) rhs.v.i : rhs.t == ORE_TYPE_FLOAT ? rhs.v.d : 0;
if (strcmp(op, "+") == 0) { v.v.d += fv; }
if (strcmp(op, "-") == 0) { v.v.d -= fv; }
if (strcmp(op, "*") == 0) { v.v.d *= fv; }
if (strcmp(op, "/") == 0) { v.v.d /= fv; }
if (strcmp(op, "%") == 0) { v.v.d = ((int) v.v.d % (int) fv); }
}
break;
}
}
return v;
}
if (is_a(t, "let")) {
khint_t k = kh_put(ident, ore->env, t->children[0]->contents, &r);
v = ore_eval(ore, t->children[2]);
kh_value(ore->env, k) = v;
return v;
}
if (is_a(t, "func")) {
ore_value v = { ORE_TYPE_FUNC };
v.v.f = t->children[5];
khint_t k = kh_put(ident, ore->env, t->children[1]->contents, &r);
kh_value(ore->env, k) = v;
return v;
}
if (is_a(t, "lambda")) {
ore_value v = { ORE_TYPE_FUNC };
v.v.f = t->children[4];
return v;
}
if (is_a(t, "call")) {
return ore_call(ore, t);
}
if (t->tag[0] == '>') {
for (i = 0; i < t->children_num; i++) {
ore_eval(ore, t->children[i]);
}
return ore_value_nil();
}
fprintf(stderr, "Unknwn operation '%s'\n", t->tag);
return ore_value_nil();
}
ore_context*
ore_new(ore_context* parent) {
ore_context* ore = (ore_context*) malloc(sizeof(ore_context));
ore->env = kh_init(ident);
ore->gc = kl_init(ident);
ore->parent = parent;
return ore;
}
void
ore_destroy(ore_context* ore) {
kl_destroy(ident, ore->gc);
}
int main(int argc, char **argv) {
if (argc != 2) {
fprintf(stderr, "usage of %s: file\n", argv[0]);
exit(0);
}
mpc_parser_t* Number = mpc_new("number");
mpc_parser_t* Factor = mpc_new("factor");
mpc_parser_t* String = mpc_new("string");
mpc_parser_t* Ident = mpc_new("ident");
mpc_parser_t* Term = mpc_new("term");
mpc_parser_t* Lexp = mpc_new("lexp");
mpc_parser_t* Let = mpc_new("let");
mpc_parser_t* Func = mpc_new("func");
mpc_parser_t* Lambda = mpc_new("lambda");
mpc_parser_t* Call = mpc_new("call");
mpc_parser_t* Comment = mpc_new("comment");
mpc_parser_t* Eof = mpc_new("eof");
mpc_parser_t* Stmt = mpc_new("stmt");
mpc_parser_t* Program = mpc_new("program");
mpc_err_t* err = mpca_lang(MPC_LANG_DEFAULT, STRUCTURE,
Number, Factor, String, Ident,
Term, Lexp, Let, Lambda, Func, Call, Comment, Eof,
Stmt, Program);
if (err != NULL) {
mpc_err_print(err);
mpc_err_delete(err);
goto leave;
}
mpc_result_t result;
if (!mpc_parse_contents(argv[1], Program, &result)) {
mpc_err_print(result.error);
mpc_err_delete(result.error);
goto leave;
}
mpc_ast_print(result.output);
ore_context* ore = ore_new(NULL);
ore_define_cfunc(ore, "println", ore_println);
ore_eval(ore, result.output);
ore_destroy(ore);
mpc_ast_delete(result.output);
leave:
mpc_cleanup(11,
Number, Factor, String, Ident,
Term, Lexp, Let, Lambda, Func, Call, Comment, Eof,
Stmt, Program);
return 0;
}
今回の修正で以下の俺スクリプトが動作する様になりました。
a = 1.0;
a = a * 2 + 1;
b = "hello";
println(b, a + 1);
func foo() {
println(1);
}
foo();
c = func(){
println("lambda");
};
c();
次回は
を行う予定です。
