2014/04/18


このエントリーをはてなブックマークに追加
Big Sky :: プログラミング言語の作り方
Big Sky :: プログラミング言語の作り方(2)
Big Sky :: プログラミング言語の作り方(3)
Big Sky :: プログラミング言語の作り方(4)

本来ならばここらあたりでエラー処理とか例外を入れるべきでしたが、先に以下の実装を行いました。
  • 配列
  • ハッシュ
  • 配列要素へのアクセス
  • ハッシュ要素へのアクセス
  • if
  • while
  • for
  • return
  • break
  • continue
現在のシンタックスは以下の通り。
#define STRUCTURE \
"                                                                       \n" \
"number     : /-?[0-9]+(\\.[0-9]*)?(e[0-9]+)?/ ;                         \n" \
"true       : \"true\" ;                                                 \n" \
"false      : \"false\" ;                                                \n" \
"nil        : \"nil\" ;                                                  \n" \
"factor     : '(' <lexp> ')'                                             \n" \
"           | <number>                                                   \n" \
"           | <string>                                                   \n" \
"           | <array>                                                    \n" \
"           | <hash>                                                     \n" \
"           | <true>                                                     \n" \
"           | <false>                                                    \n" \
"           | <nil>                                                      \n" \
"           | <call>                                                     \n" \
"           | <new>                                                      \n" \
"           | <ident> ;                                                  \n" \
"string     : /\"(\\\\.|[^\"])*\"/ ;                                     \n" \
"item       : <factor> ('[' <lexp> ']')+ ;                               \n" \
"prop       : <factor> ('.' <ident>)+ ;                                  \n" \
"cmp        : <factor>                                                     " \
"         (\"!=\" | \"==\" | \"<=\" | \"<\" | \">=\" | \">\" )             " \
"         <factor> ;                                                     \n" \
"call       : <ident> '(' <lexp>? (',' <lexp>)* ')' ;                    \n" \
"anoncall   : <factor> '(' <lexp>? (',' <lexp>)* ')' ;                   \n" \
"methodcall : <prop> '(' <lexp>? (',' <lexp>)* ')' ;                     \n" \
"array      : '[' <lexp>? (',' <lexp>)* ']' ;                            \n" \
"pair       : <string> ':' <lexp> ;                                      \n" \
"hash       : '{' <pair>? (',' <pair>)* '}' ;                            \n" \
"ident      : /[a-zA-Z_][a-zA-Z0-9_]*/ ;                                  \n" \
"                                                                        \n" \
"term       : (<lambda> | <item> | <methodcall> | <cmp> | <prop>           " \
"         | <anoncall> | <call>                                          \n" \
"         | <factor> (('*' | '/' | '%') <factor>)*) ;                    \n" \
"lexp       : <term> (('+' | '-') <term>)* ;                             \n" \
"let_v      : <ident> '=' <lexp> ';' ;                                   \n" \
"let_a      : <item> '=' <lexp> ';' ;                                    \n" \
"let_p      : <prop> '=' <lexp> ';' ;                                    \n" \
"else_if    : \"else\" \"if\" '(' <lexp> ')' '{' <stmts> '}' ;           \n" \
"else       : \"else\" '{' <stmts> '}' ;                                 \n" \
"if_stmt    : \"if\" '(' <lexp> ')' '{' <stmts> '}' ;                    \n" \
"if         : <if_stmt> <else_if>* <else>? ;                             \n" \
"while      : \"while\" '(' <lexp> ')' '{' <stmts> '}' ;                 \n" \
"for_in     : \"for\" '(' <ident> \"in\" <lexp> ')' '{' <stmts> '}' ;    \n" \
"var        : \"var\" <ident> '=' <lexp> ';' ;                           \n" \
"vararg     : \"...\" ;                                                  \n" \
"stmts      : <stmt>* ;                                                  \n" \
"                                                                        \n" \
"lambda     : \"func\"                                                     " \
"         '(' <ident>? (<vararg> | (',' <ident>)*) ')' '{' <stmts> '}' ; \n" \
"func       : \"func\" <ident>                                             " \
"         '(' <ident>? (<vararg> | (',' <ident>)*) ')' '{' <stmts> '}' ; \n" \
"template   : (<var> | <func>)* ;                                        \n" \
"class      : \"class\" <ident> '{' <template> '}' ;                     \n" \
"new        : \"new\" <ident> '(' <lexp>? (',' <lexp>)* ')' ;            \n" \
"                                                                        \n" \
"break      : \"break\" ';' ;                                            \n" \
"continue   : \"continue\" ';' ;                                         \n" \
"return     : \"return\" <lexp> ';' ;                                    \n" \
"comment    : /#[^\n]*/ ;                                                \n" \
"eof        : /$/ ;                                                      \n" \
"stmt       : (<let_v> | <let_a> | <let_p> | <var> | <if>                  " \
"         | <while> | <for_in>                                             " \
"         | <func> | <class> | <return> | <break>                        \n" \
"         | <continue> | <comment> | (<lexp> ';')) ;                     \n" \
"program    : <stmts> <eof> ;                                            \n"
配列 array は簡単ですね。lexp がカンマ区切りになっているだけです。
"array      : '[' <lexp>? (',' <lexp>)* ']' ;                            \n" \
ハッシュは少し難しくなります。まずキーと値を組にした pair という物を宣言し、それの繰り返しという定義となります。
"pair       : <string> ':' <lexp> ;                                      \n" \
"hash       : '{' <pair>? (',' <pair>)* '}' ;                            \n" \
配列、ハッシュの要素へのアクセスですが、実装方法にもよりますが代入左項を lexp として処理してしまい
a[1] = 2;
値の参照のみを行ってしまうと、実際に要素を変更する a への変更が出来ません。値の出所をリファレンスで持っておくのも良いですが、面倒なので要素代入というステートメントで処理しています。

if、else if、else はそれぞれ AST を処理しやすい様に以下の構造を作りました。
#!ore
if (0) {
  println("foo");
else if (false) {
  println("boo");
else {
  println("zoo");
}
ref array 1 008CB850

  stmts|> 
    stmt|comment|regex:1:1 '#!ore'
    if|> 
      if_stmt|> 
        string:2:1 'if'
        char:2:4 '('
        lexp|term|factor|number|regex:2:5 '0'
        char:2:6 ')'
        char:2:8 '{'
        stmt|> 
          call|> 
            ident|regex:3:3 'println'
            char:3:10 '('
            lexp|term|factor|string|regex:3:11 '"foo"'
            char:3:16 ')'
          char:3:17 ';'
        char:4:1 '}'
      else_if|> 
        string:4:3 'else'
        string:4:8 'if'
        char:4:11 '('
        lexp|term|factor|false|string:4:12 'false'
        char:4:17 ')'
        char:4:19 '{'
        stmt|> 
          call|> 
            ident|regex:5:3 'println'
            char:5:10 '('
            lexp|term|factor|string|regex:5:11 '"boo"'
            char:5:16 ')'
          char:5:17 ';'
        char:6:1 '}'
      else|> 
        string:6:3 'else'
        char:6:8 '{'
        stmt|> 
          call|> 
            ident|regex:7:3 'println'
            char:7:10 '('
            lexp|term|factor|string|regex:7:11 '"zoo"'
            char:7:16 ')'
          char:7:17 ';'
        char:8:1 '}'
  eof|regex 
AST をそのまま保持しておき、条件を実行した結果でどのステートメント群を実行するかを処理します。
if (is_a(t, "if")) {
  ore_value v;
  int i;
  for (i = 0; i < t->children_num; i++) {
    int r = 0;
    mpc_ast_t* f = t->children[i];
    if (is_a(f, "if_stmt")) {
      r = ore_is_true(ore_eval(ore, f->children[2]));
    } else if (is_a(f, "else_if")) {
      r = ore_is_true(ore_eval(ore, f->children[3]));
    } else {
      r = 1;
    }
    if (r)
      return ore_eval(ore, ore_find_statements(f));
  }
  return ore_value_nil();
}
for や while も同様です。要約フィボナッチ数の計算が出来る様になりました。
func fib(n) {
  if (n < 2) {
    return n;
  }
  return fib(n-2) + fib(n-1);
}

println(fib(20));
実はリポジトリ内では既にクラスオブジェクトの生成が出来る様になっています。興味のある方はこちらからどうぞ。
mattn/orelang - GitHub

俺言語

https://github.com/mattn/orelang
さて、今日は本当ならばエラー処理を書きたかったのですが実は使っているパーサの mpc が AST から行番号を取れないという問題を見つけ、問題報告していた為に実装出来ませんでした。

Hope to get code location from mpc_ast_t ・ Issue #4 ・ orangeduck/mpc - GitHub

Hey. This should be added in the newest version. You can use the state member of mpc_ast_t . You can...

https://github.com/orangeduck/mpc/issues/4
報告したら実装してくれましたので、今度はエラー処理を書こうと思います。

実は、言語処理系を実装する上で少し面倒なのが return なのです。return は大域脱出になりえます。
例えば関数の中に if 文があり、その中に for 文があり、その中で return 文があると、その if 文や for 文をキャンセルして戻り値と共に大域脱出する必要があります。この実装に longjmp/setjmp を使う言語処理系もありますが、今回は return をエラーと見立ててあらゆる箇所で中断処理を実行させ、関数処理内に戻ってきたらエラー扱いではなく正しい return として処理させるという方法を使っています。
なので例えば関数内でなければ不正なエラーとなる訳です。逆に都合がいいですね。break や continue も同じ手法を使っています。


2014/04/17


このエントリーをはてなブックマークに追加
これまでは、github_api_url という設定で GitHub Enterprise Edition の API で Gist 出来る様にしていましたが、設定名が変更になり gist_api_url となりました。
Fixes trailing slash problem by tpoisot - Pull Request #154 · mattn/gist-vim · GitHub

Showing 3 changed files with 31 additions and 31 deletions . Show diff stats Hide diff stats 2 ð...

https://github.com/mattn/gist-vim/pull/154
気付かず :Gist してしまうと GitHub 側にポストされてしまいますのでご注意下さい。

2014/04/16


このエントリーをはてなブックマークに追加
FAQ に書いてあります。
Why does Go not have exceptions? - Frequently Asked Questions (FAQ) - The Go Programming Language

We believe that coupling exceptions to a control structure, as in the try-catch-finally idiom, results in convoluted code. It also tends to encourage programmers to label too many ordinary errors, such as failing to open a file, as exceptional.

Go takes a different approach. For plain error handling, Go's multi-value returns make it easy to report an error without overloading the return value. A canonical error type, coupled with Go's other features, makes error handling pleasant but quite different from that in other languages.

Go also has a couple of built-in functions to signal and recover from truly exceptional conditions. The recovery mechanism is executed only as part of a function's state being torn down after an error, which is sufficient to handle catastrophe but requires no extra control structures and, when used well, can result in clean error-handling code.

http://golang.org/doc/faq#exceptions
try-catch-finally イディオムはコードを複雑にするし、たかがファイルのオープンに失敗しただけのエラーに過剰なラベル付を強要する。 golang では複数の値を返す事が出来るので、一般的には戻り値の最後にエラーを付けて返す。

と書いてあります。
何度読んでも「例外が使いこなせません」とは読めません。すいません。複雑になるのは良くないという話はそもそもレイヤの違う話だと思いますよ。まぁ FUD なツィートで人気のある方なので、ディスカッションするつもりもないですが。
バグが発生する多くの問題は、エラーハンドリングが正しくされていない事が原因だったりします。golang の場合は戻り値が複数あった場合、戻り値を得るには必ず全ての戻り値を変数にバインドしないといけない仕様になっています。つまりは戻り値が欲しければ、error も取れという事になりますね。
package main

import (
    "fmt"
)

func doSomething(input int) (result string, err error) {
    switch {
    case input < 0:
        return "", fmt.Errorf("%d is negative value", input)
    case input < 50:
        return "less than 50"nil
    default:
        return "greater than 50"nil
    }
}

func main() {
    if r, err := doSomething(20); err != nil {
        fmt.Println(err)
    } else {
        fmt.Println(r)
    }
}
golang では if の else ブロック内でも if 句内で宣言した変数が参照出来ます。Java の try-catch-finally だと try 内で宣言した変数は catch ブロックでは参照出来ません。それを回避する為に try よりも上部に持っていって... などというのは良くある話ですし、ネストだらけの try-catch-finally も良く見ますね。
golang でも細かいエラーハンドリングは出来ます。この辺はドキュメントを読むと書いてあります。例えば os.Open ならば
func Open - The Go Programming Language

Open opens the named file for reading. If successful, methods on the returned file can be used for reading; the associated file descriptor has mode O_RDONLY. If there is an error, it will be of type *PathError.

http://golang.org/pkg/os/#Open
エラーがあった場合には PathError が返ります。
package main

import (
    "log"
    "os"
    "syscall"
)

func main() {
    f, err := os.Open("not-found-file.txt")
    if err != nil {
        pathErr := err.(*os.PathError)
        errno := pathErr.Err.(syscall.Errno)
        if errno == syscall.ENOENT {
            log.Fatalf("ファイルが見つからなかったんだと思います: %v", pathErr)
        }
        log.Fatalf("良く分からないエラーが発生しました: %v", pathErr)
    }
    f.Close()
}
ラベル付けしないからこそ、エラーは詳細に取れる様に設計されています。別のドキュメントにエラーハンドリングについて詳細に書かれています。
Error handling and Go - The Go Blog

If you have written any Go code you have probably encountered the built-in error type...

http://blog.golang.org/error-handling-and-go


このエントリーをはてなブックマークに追加
Big Sky :: プログラミング言語の作り方
Big Sky :: プログラミング言語の作り方(2)
Big Sky :: プログラミング言語の作り方(3)
本日は関数スコープの実装と関数引数のバインディングを行います。
まず関数スコープを入れるという事は、メモリの破棄が必要になります。

しかし関数が呼び出された後、関数スコープ内のメモリを全て削除してしまうと戻り値に文字列を渡せなくなります。
func foo() {
  return "foo"; // この後スコープが削除される
}

a = foo(); // 壊れたメモリを参照
そこで GC を導入する必要があります。GC の実装には複数あます。詳しくは Wikipedia を参照下さい。
今回はその中の「参照カウント方式」を取ります。
まず ore_value に参照カウンタを付けます。
typedef struct _ore_value {
  ore_type t; // 変数種別
  union {
    int i;    // int の値
    double d; // double の値
    char* s;  // 文字列
    struct {
      void* env;    // 関数宣言時のスコープ
      int num_in;   // 引数の数(現状CFUNCのみ)
      union {
        void* c;    // CFUNCの関数ポインタ
        ore_func o; // ユーザ定義関数のステートメント
      } x;
    } f;     // 関数
  } v;
  int ref; // 参照カウンタ
} ore_value;
そして便利関数として ore_value_ref と ore_value_unref を実装します。
void
ore_value_real_free(ore_value* v) {
  switch (v->t) {
    case ORE_TYPE_STR:
      //printf("free %d, %p, %s\n", v->ref, v->v.s, v->v.s);
      free(v->v.s);
      v->v.s = NULL;
      break;
    case ORE_TYPE_FUNC:
      break;
  }
  v->t = ORE_TYPE_NIL;
}


void
ore_value_free(void *p) {
  ore_value* v = (ore_value*) p;
  ore_value_unref(v);
}

void
ore_value_ref(ore_value *v) {
  v->ref++;
}
参照カウント方式は一般的にコードが複雑になると思われがちですが、用法用量を守って正しく使うとそんなに難しくはありません。
複雑にならない様に env に登録/更新する関数を作ります。
ore_value
ore_get(ore_context* ore, const char* name) {
  if (!ore)
    return ore_value_nil();
  khint_t k;
  while (ore) {
    k = kh_get(ident, ore->env, name);
    if (k != kh_end(ore->env)) {
      return kh_value(ore->env, k);
    }
    ore = ore->parent;
  }
  return ore_value_nil();
}

void
ore_set(ore_context* ore, const char* name, ore_value v) {
  khint_t k;
  int r;
  while (ore) {
    k = kh_get(ident, ore->env, name);
    if (k != kh_end(ore->env)) {
      ore_value old = kh_value(ore->env, k);
      ore_value_unref(&old);
      kh_value(ore->env, k) = v; // update ref
      k = kh_put(ident, ore->env, name, &r);
      ore_value_ref(&v);
      kh_value(ore->env, k) = v;
      return;
    }
    if (ore->parent == NULL) {
      k = kh_put(ident, ore->env, name, &r);
      ore_value_ref(&v);
      kh_value(ore->env, k) = v;
      return;
    }
    ore = ore->parent;
  }
}

ore_value
ore_define(ore_context* ore, const char* name, ore_value v) {
  khint_t k = kh_get(ident, ore->env, name);
  int r;
  if (k != kh_end(ore->env)) {
    ore_value old = kh_value(ore->env, k);
    ore_value_unref(&old);
  }
  k = kh_put(ident, ore->env, name, &r);
  ore_value_ref(&v);
  kh_value(ore->env, k) = v;
}
前回説明した様に関数スコープが作られた後、識別から値を参照するにはグローバル方向に向かって検索する必要があるのでその実装を行いました。見つからなかった場合は nil を返していますが、言語によっては「Undefined Exception」の様なエラーを発生させる事もあります。
これを使って、変数(関数)宣言する時は ore_define、値を設定する時は ore_set、値を取得する時は ore_get を使えば良いです。
関数呼び出し時には、ore_new により新しい環境を作り、そこに引数名と受け渡された値のバインディングを行います。
{
  int num_in = t->children_num / 2 - 1, n = 0, i;
  if (fn.v.f.num_in != -1 && num_in != fn.v.f.num_in) {
    fprintf(stderr"Number of arguments mismatch: %d for %d\n",
      num_in, fn.v.f.num_in);
    ore->err = ORE_ERROR_EXCEPTION;
    return ore_value_nil();
  }
  ore_value* args = (ore_value*) malloc(sizeof(ore_value) * num_in);
  for (i = 2; i < t->children_num - 1; i += 2) {
    args[n++] = ore_eval(ore, t->children[i]);
  }
  ore_context* env = ore_new((ore_context*) fn.v.f.env);
  mpc_ast_t* stmts = NULL;
  mpc_ast_t* f = fn.v.f.x.o;
  n = 0;
  for (i = 2; i < f->children_num; i++) {
    if (is_a(f->children[i], "ident")) {
      if (n < num_in)
        ore_define(env, f->children[i]->contents, args[n++]);
    } else if (stmts == NULL && !is_a(f->children[i], "char")) {
      stmts = f->children[i];
    }
  }
  if (stmts) {
    v = ore_eval(env, stmts);
    if (ore->err != ORE_ERROR_EXCEPTION)
      ore->err = ORE_ERROR_NONE;
    *kl_pushp(ident, ore->unnamed) = v;
  }
  free(args);
  ore_destroy(env);
}
そして気を付けなければならないのが、実行時スコープです。上のコードでは、関数を呼び出したスコープで ore_new を呼び出すのではなく
if (is_a(t, "func")) {
  ore_value v = { ORE_TYPE_FUNC };
  v.v.f.env = ore;
  v.v.f.num_in = -1;
  v.v.f.x.o = t;
  ore_set(ore, t->children[1]->contents, v);
  return v;
}
if (is_a(t, "lambda")) {
  ore_value v = { ORE_TYPE_FUNC };
  v.v.f.env = ore;
  v.v.f.num_in = -1;
  v.v.f.x.o = t;
  return v;
}
関数が宣言された時点での環境を保持しておき、その環境から新しい環境を作る必要があります。こうしないと
#!ore
func counter() {
  var a = 0;
  return func() {
    a = a + 1;
    return a;
  };
}
count = counter();

println(count());
println(count());
この様なコードが動作しなくなります。今回の実装も以下のリポジトリから参照出来ます。
mattn/orelang - GitHub

README.md orelang 俺言語 プログラミング言語の作り方 プログラミング言語の作り方(2) プログラミング言語の作り方(3) Usage # calculation a = 1; a =...

https://github.com/mattn/orelang
そろそろエラー処理を書きたいと思います。