2018/12/14


先日、mopp さんが Vim に flatten() を追加するプルリクエストを追加してくれたのだけど、その時の記憶を整理する為に書く自分の為の記事。

add flatten() to flatten list by mopp - Pull Request #3676 - vim/vim - GitHub

I'm a bit confused by the maxdepth argument. I would expect it to specify the maximum depth of the r...

https://github.com/vim/vim/pull/3676

Vim script のリストは以下の様に、異なる型が混在できる。Ruby や他のスクリプト言語でも一般的。そしてスクリプト言語には一般的にリストを平坦化する為の flatten という関数ないしはメソッドが用意されている。

let foo = [12, ["bar"], 3]
Vim本体に組み込み関数を追加するパッチを投げた - Qiita

Vim本体に手を加える 次に本体への修正ですが、大体1週間くらいで出来ました。 しかし、これは私一人の力ではなく、7割りくらい vim-jp のおかげです。 vim-jpは日本のVim開発者(Plug...

https://qiita.com/mopp/items/084abe28681202bda30e

mopp さんが Advent Calendar でその時の様子を書いてくれているんだけど、flatten() ははじめ再帰を使って書かれていた。途中で僕が「ループに直したらこうなる」という感じにコードを貼ってしまったので、後でループに直す実装を楽しみにしていた mopp さんには悪い事をしてしまった。申し訳ない。ぜひ次は flat_map() を実装して下さい。その時考えていたのだけど、flatten() の様な関数を再帰でなくループにするには本来ならばスタックに相当する何かが必要になるはずだろうと踏んでいた。なぜならリストを再帰降下するという事は戻り場所を知っておく必要があり、ループに直すのであればそれ相当のスタック配列が必要だと考えていたからだ。そして一般的にはこのスタック配列の実装がめんどくさいので皆再帰を使ってお茶を濁そうとする。僕もよくやる。

例えば以下の様な簡単なリスト構造を作ってみたとする。

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

typedef enum _type_t {
  INT_T,
  STRING_T,
  LIST_T,
} type_t;

typedef struct _value_t {
  int ref;
  type_t type;
  union {
    int n;
    char *s;
    struct _list_t *l;
  } val;
} value_t;

typedef struct _item_t {
  struct _item_t *next;
  value_t *value;
} item_t;

typedef struct _list_t {
  item_t *first;
} list_t;

static void
free_value(value_t *v) {
  item_t *i;

  if (v->ref-- > 0return;

  switch (v->type) {
  case INT_T:
    break;
  case STRING_T:
    free((void*)v->val.s);
    break;
  case LIST_T:
    i = v->val.l->first;
    while (i != NULL) {
      item_t *next = i->next;
      free_value(i->value);
      free(i);
      i = next;
    }
    free((void*)v->val.l);
    break;
  }
  free((void*)v);
}

static value_t*
new_list_value() {
  value_t *v = malloc(sizeof(value_t));
  v->type = LIST_T;
  v->val.l = malloc(sizeof(list_t));
  v->val.l->first = NULL;
  v->ref = 0;
  return v;
}

item_t*
new_item(value_t *v) {
  item_t *item = malloc(sizeof(item_t));
  item->value = v;
  item->next = NULL;
  ++v->ref;
  return item;
}

static void
list_add_value(list_t *list, value_t *rhs) {
  item_t *i = list->first;

  if (i == NULL) {
    list->first= new_item(rhs);
    return;
  }

  while (i->next != NULL) {
    i = i->next;
  }

  i->next= new_item(rhs);
}

static void
list_insert_value(list_t *list, item_t *before, value_t *value) {
  item_t *next;
  
  if (before == NULL) {
    list->first= new_item(value);
    return;
  }

  next = before->next;

  before->next= new_item(value);
  before->next->next = next;
}

static void
list_remove_item(list_t *list, item_t *item) {
  item_t *i, *before = NULL;
  
  for (i = list->first; i != NULL; i = i->next) {
    if (i == item) {
      if (before == NULL)
        list->first = i->next;
      else
        before->next = i->next;

      free_value(item->value);
      free(item);
      return;
    }
    before = i;
  }
}

static value_t*
new_int_value(int n) {
  value_t *v = malloc(sizeof(value_t));
  v->type = INT_T;
  v->val.n = n;
  v->ref = 0;
  return v;
}

static value_t*
new_string_value(const char* s) {
  value_t *v = malloc(sizeof(value_t));
  v->type = STRING_T;
  v->val.s = strdup(s);
  v->ref = 0;
  return v;
}

static void
print_value(value_t *v) {
  item_t *i;

  switch (v->type) {
  case INT_T:
    printf("%d", v->val.n);
    break;
  case STRING_T:
    /* TODO: escape non-printable */
    printf("\"%s\"", v->val.s);
    break;
  case LIST_T:
    printf("[");
    for (i = v->val.l->first; i != NULL; i = i->next) {
      print_value(i->value);
      if (i->next) printf(", ");
    }
    printf("]");
    break;
  }
}

int
main(int argc, char* argv[]) {
  value_t *list, *sub;

  list = new_list_value();  
  list_add_value(list->val.l, new_int_value(1));
  list_add_value(list->val.l, new_string_value("foo"));

  sub = new_list_value();  
  list_add_value(sub->val.l, new_string_value("bar"));
  list_add_value(list->val.l, sub);

  list_add_value(list->val.l, new_int_value(3));

  print_value(list);
  free_value(list);
  return 0;
}

数値と文字列とリストが扱える物。リストの中にはそのいずれかを混入できる。お気持ち程度の参照カウンタを入れてあるが動くかどうか確認してないし本題はそこじゃない。これを実行すると以下の様に表示される。

[1, "foo", ["bar"], 3]

このリスト関数を使って flatten() を実装する場合、簡単に思い付くのが再帰を使った以下の方法。vital.vim でも再帰を使ってる。

functions:flatten(list, ...) abort
  let limit = a:0 > 0 ? a:1 : -1
  let memo = []
  if limit == 0
    return a:list
  endif
  let limit -= 1
  for Value in a:list
    let memo +=
          \ type(Value) == type([]) ?
          \   s:flatten(Value, limit) :
          \   [Value]
    unlet! Value
  endfor
  return memo
endfunction

上記のリスト関数を使った場合だと以下の様になる。

static void
flatten_list(item_t *before, list_t *list) {
  item_t *i, *j, *prev = NULL;

  for (i = list->first; i != NULL; i = i->next) {
    if (i->value->type == LIST_T) {
      flatten_list(i, i->value->val.l);
      list_remove_item(list, i);
      return;
    }
    if (before != NULL) {
      list_insert_value(list, before, i->value);
      before = before->next;
    }
  }
}

リストを舐めながら要素がリストだったら挿入位置とそのリストを引数に要素を追加する関数(自身)を呼び出す。呼び出したあと元々リストがあった箇所を削除する。この flatten() は再帰を使ってるのでメモリを多く消費するしスタックオーバーフローで突然死してしまう可能性がある。でも良く考えると flatten() は、現在いる要素の子要素がリストの場合、そのリストの中身をすべて現在いる場所に移動し、自身を削除し、そして今と同じ箇所で再検査すればいいだけなのだ。スタックとして覚えておく必要もない。なので実装は以下の様になる。

static void
flatten_list(list_t *list) {
  item_t *i, *j, *prev = NULL;

  for (i = list->first; i != NULL; i = i->next) {
    if (i->value->type == LIST_T) {
      item_t *before = i;
      for (j = i->value->val.l->first; j != NULL; j = j->next) {
        list_insert_value(list, before, j->value);
        before = before->next;
      }

      if (prev == NULL)
        list->first = i->next;

      prev->next = i->next;
      i = prev;
    }
    prev = i;
  }
}

言ってみるならば、自分がネストに降下するんじゃなく、flat にする事でネストがこっちに上がってくるという事。実行すると以下が表示される。

[1, "foo", "bar", 3]

再帰は消え、スタックオーバーフローの心配もなくなり、メモリの消費量も減り、良い事づくめだ。逆に、今まで何度か flatten() は書いた事があるけどなぜ自分はこれまで flatten() を再帰で作ろうと考えてしまったのかと思い起こしたくもなった。

追記 この最適化方は自身のリストが破壊されるから出来る方法なので、flatten 済みのリストをを返す場合には使えないので注意。

Posted at by



2018/11/27


僕のこれまで人生の中で、2日間まるまる Vim の事を考えるなんて事なんて無かったし、今思い返してもとても刺激的な日でした。

まず始めに、VimConf というイベントを産み出してくれた ujihisa さん、kaoriya さん、運営に関わった皆さん、そしてスポンサー頂いた企業の皆様、個人スポンサーをして頂いた皆さん、本当にありがとうございました。

中には参加できないにも関わらず VimConf が上手く行く事を願って個人スポンサーになってくれた方も沢山いました。本当にありがとうございます。

今回 Vim の作者 Bram Moolenaar 氏を VimConf 2018 に呼べたのは皆さんのお力あってこそだと思っています。

これまで VimConf はどちらかというと、こじんまりしたイメージのイベントでしたが、「Bram Moolenaar 氏を呼ぶに相応しい国際会議として開催すべきだ」と決断し、一般社団法人となり、VimConf 2017 を開催しました。それでも海外からの意見では「日本人のイベントだ」と言われた事もありました。幾つか若干悔しい思いをしつつも、今年の初めから Bram Moolenaar 氏にアポイントをし始め、僕らはとうとう Bram Moolenaar 氏を VimConf に呼び寄せる事が出来ました。

Vim を知らない人にはこの凄さが伝わらないかもしれません。また Vim を知っていたとしてもこの高揚感は伝わらないかもしれません。これが普通の話なのは理解しています。ただ僕個人がずっと感じていた悔しさもあり、この嬉しさは人一倍大きな物だったからなのです。

今から10年前、僕は Bram Moolenaar 氏に会う事が出来るチャンスがありました。そしてチャンスを貰いながらもそれを自ら逃してしまいました。10年前のある日、僕と kaoriya さんは Bram Moolenaar 氏からメールを貰いました。「秋に来日して観光する予定だ。東京と京都に行くので都合が合えば会えないか」という内容でした。Bram Moolenaar 氏から直接言ってきてくれたのです。しかし不運な事にその日にどうしても外せない仕事があり、そして会う事が出来なかったのです。たまにこの事を思い出すとずっと残念な気持ちになっていました。無理してでも行ったら良かったかなと毎回考えました。

それから10年後、僕は VimConf 2017 から補助スタッフとして参加し始めました。関西なのでリアルタイムにお手伝い出来ないですがウェブサイトの更新などリモートで出来る細かなお手伝いをしました。今回 VimConf 2018 に Bram Moolenaar 氏を呼ぼうという話が決まった際は、これまでの悔しさがスッと消える思いがしたのと同時に、暫くは信じる事が出来なかったのを覚えています。僕に限らず運営スタッフも暫くは本当に確定なのか?と何度も確認していたのを覚えています。

僕が Vim にコントリビュートし始めたのは 2000 年の1月。今から18年も前の事です。あの頃からずっとメールでやりとりしていた Bram Moolenaar 氏が、VimConf 2018 の当日に目の前に現れて握手をした時には言葉が出ずにただただオロオロとしてしまいました。「I'm grad to see you」としか言えませんでしたが、Bram Moolenaar 氏も同じ言葉で返してくれました。

今回の VimConf 2018 ではキーノートスピーチを任せられました。kaoriya さんからは「Bram Moolenaar 氏に vim-jp がどういう活動をしているか伝えるチャンスでは」とアドバイスを貰いました。Bram Moolenaar 氏の前でどんな話をしようか悩みましたが、敢えて Bram Moolenaar 氏の前で機能提案をするという暴挙に出る事にしました。

内容は、vim-jp の活動報告と見せかけて DRCS Sixel のサポート、ソケットの listen、BLOB (バイト列)型の追加を提案するという物です。

正直、自分が何を喋ったのか良く覚えていませんが、昼休憩の時に Bram Moolenaar 氏に呼び止められこう言われました。

Vim にパッチ送り続けていて良かった!と思いました。一人だけこんな思いしてどうだ羨ましいだろ申し訳ないなとも思いました。

Bram Moolenaar 氏の発表もとても面白い物で、Vim プラグイン作者が欲しいと思っていた機能の幾つかを Bram Moolenaar 氏から提案する物でした。

From hjkl To a platform for plugins

その他のスピーカーの皆さんの発表もとても興味深い物でした。僕が印象に残った物をあげさせて頂くとすると Akin 氏の Onivim の話と rhysd さん(犬さん)の Vim を wasm に移植した話が面白かったです。正直 Onivim の完成度がこれほどまでとは思っていませんでした。また Vim を wasm に移植した話は、Vim のソースを知っているが故、大変さが伝わってきて頷くばかりでした。

朝10時から始まり、一日中 Vim のトークばかりだったのにとても短く感じるほど充実した内容だったと思います。

懇親会の途中、スタッフ特権で Bram Moolenaar 氏と写真を撮りました。思い出に残る一日でした。改めて皆さんにお礼を言いたいです。あと rhysd さんとは gocon で挨拶しかしてなかったので、今回少しだけでも喋れて良かったです。その他、多くの方から挨拶を頂きました。ちなみに声を掛けて頂いたおよそ8割くらいの方が Vim に関しての僕に挨拶に来られ、残り2割くらいの方が Go に関しての僕にに挨拶に来られました。海外の方から「Go のライブラリ使ってる」と言って頂けました。

次の日、VimConf 運営スタッフと日本人 Vim コントリビュータ数名、Bram Moolenaar 氏、Mastering Vim という本を出版した Ruslan Osipov 氏と一緒に Vim ハッカソン「vimthon」を開催しました。

前日、Vim の機能追加投票で上位に来ていながらも Bram Moolenaar 氏に知られていない存在だった LSP (Language Server Protocol) を目の前で見せ、ホワイトボードにどうやって LSP が動いているのかを説明しました。また Bram Moolenaar 氏がスライドの中で言っていた Vim script のコンパイルについても、AST 化が難しいという事を伝えました。帰る時間が決まっていたので少し焦ってしまった所はありましたが。

ちなみに、Bram Moolenaar 氏には前日に「vimthon は何時に来てもいいよ」と伝えてあったのですが、当日なかなか現れない Bram Moolenaar 氏に我々スタッフも少し心配していたのですが、ふと見た GitHub で30分前にコミットが push されているのを見た時は皆で笑いました。ちなみにこの20分後くらいに Bram Moolenaar 氏も現れました。

まるまる2日間 Vim だらけでした。とても濃かったですし、とても楽しかったです。ずっと悔しかった思い出もこれで忘れる事が出来る気がしています。時間の都合で最後まで参加出来ませんでしたが、最後に Bram Moolenaar 氏がこう言われたそうです。

I am amazed to experience the professional level of this conference about one piece of open source software that I happened to start 27 years ago. Thanks to all the organisers and speakers for this exciting conference!

27年前に私が始めたオープンソースソフトウェアの1つに関して、こんなにも専門レベルなカンファレンスを経験することが出来て非常に驚いています。 このエキサイティングな会議の主催者とスピーカーに感謝します。

— Bram Moolenaar, 2018-11-25

この言葉を直接聞けなかったけれど、きっとこの言葉を聞いた運営スタッフは嬉しかっただろうなと帰りの新幹線で一人感動していました。おめでとう運営スタッフ。

Posted at by



2018/11/08


gobrain という Golang だけで実装されたニューラルネットワークを見つけたので遊んでみました。

GitHub - goml/gobrain: Neural Networks written in go
https://github.com/goml/gobrain

作りもシンプルですし、扱い方も簡単なのでちょっとしたサンプルを書くのには向いてると思います。例えば FizzBuzz であればこんな感じ。

package main

import (
    "math/rand"

    "github.com/goml/gobrain"
)

type FizzBuzz []float64

func (fizzbuzz FizzBuzz) Type() int {
    for i := 0; i < len(fizzbuzz); i++ {
        if fizzbuzz[i] > 0.4 {
            return i
        }
    }
    panic("Sorry, I'm wrong")
}

func teacher(n int) []float64 {
    switch {
    case n%15 == 0:
        return []float64{1000}
    case n%3 == 0:
        return []float64{0100}
    case n%5 == 0:
        return []float64{0010}
    default:
        return []float64{0001}
    }
}

func bin(n int) []float64 {
    f := [8]float64{}
    for i := uint(0); i < 8; i++ {
        f[i] = float64((n >> i) & 1)
    }
    return f[:]
}

func main() {
    rand.Seed(0)

    // make patterns
    patterns := [][][]float64{}
    for i := 1; i <= 100; i++ {
        patterns = append(patterns, [][]float64{
            bin(i), teacher(i),
        })
    }

    ff := &gobrain.FeedForward{}

    // 8 inputs, 100 hidden nodes, 4 outputs
    ff.Init(81004)

    // epochs: 1000
    // learning rate: 0.6
    // momentum factor: to 0.4
    ff.Train(patterns, 10000.60.4false)

    for i := 1; i < 100; i++ {
        switch FizzBuzz(ff.Update(bin(i))).Type() {
        case 0:
            println("FizzBuzz")
        case 1:
            println("Fizz")
        case 2:
            println("Buzz")
        case 3:
            println(i)
        }
    }
}

今日はこの gobrain を使って画像分類を作ってみました。特徴抽出やノーマライズはやってないので実用的ではない事に注意下さい。

まず flickr 等から薔薇とユリと向日葵の画像を貰ってきて下さい。

薔薇
薔薇
ユリ
ユリ

刺青混じってませんか...

向日葵
向日葵

各20毎程度で構いません。次に画像を読み込んで3チャネルに分割します。

func decodeImage(fname string) ([]float64error) {
    f, err := os.Open(fname)
    if err != nil {
        return nil, err
    }
    defer f.Close()

    src, _, err := image.Decode(f)
    if err != nil {
        return nil, err
    }

    bounds := src.Bounds()
    w, h := bounds.Dx(), bounds.Dy()
    if w < h {
        w = h
    } else {
        h = w
    }
    bb := make([]float64, w*h*3)
    for y := 0; y < h; y++ {
        for x := 0; x < w; x++ {
            r, g, b, _ := src.At(x, y).RGBA()
            bb[y*w*3+x*3= float64(r) / 255.0
            bb[y*w*3+x*3+1= float64(g) / 255.0
            bb[y*w*3+x*3+2= float64(b) / 255.0
        }
    }
    return bb, nil
}

これで画像データが1次元の float64 配列になりこれが入力となります。これに薔薇やユリや向日葵のラベルを紐づけるためにラベルの添え字番号を使い同じ様に float64 配列にする関数を作ります。

func bin(n int) []float64 {
    f := [8]float64{}
    for i := uint(0); i < 8; i++ {
        f[i] = float64((n >> i) & 1)
    }
    return f[:]
}

func dec(d []float64int {
    n := 0
    for i, v := range d {
        if v > 0.9 {
            n += 1 << uint(i)
        }
    }
    return n
}

あとは gobrain を初期化して学習させれば推論器が出来上がるのですが

ff.Init(len(patterns[0][0]), 40len(patterns[0][1]))
ff.Train(patterns, 10000.60.4false)

gobrain は Pure Go という事もあり struct をそのまま JSON にエンコードしてやればこれがモデルファイルになる事に気付きました。

func loadModel() (*gobrain.FeedForward, []stringerror) {
    f, err := os.Open("labels.txt")
    if err != nil {
        return nilnil, err
    }
    defer f.Close()

    labels := []string{}
    scanner := bufio.NewScanner(f)
    for scanner.Scan() {
        labels = append(labels, scanner.Text())
    }
    if scanner.Err() != nil {
        return nilnil, err
    }

    if len(labels) == 0 {
        return nilnil, errors.New("No labels found")
    }

    f, err = os.Open("model.json")
    if err != nil {
        return nil, labels, nil
    }
    defer f.Close()

    ff := &gobrain.FeedForward{}
    err = json.NewDecoder(f).Decode(ff)
    if err != nil {
        return nil, labels, err
    }
    return ff, labels, nil
}

func makeModel(labels []string) (*gobrain.FeedForward, error) {
    ff := &gobrain.FeedForward{}
    patterns := [][][]float64{}
    for i, category := range labels {
        bset, err := loadImageSet(category)
        if err != nil {
            return nil, err
        }
        for _, b := range bset {
            patterns = append(patterns, [][]float64{b, bin(i)})
        }
    }
    if len(patterns) == 0 || len(patterns[0][0]) == 0 {
        return nil, errors.New("No images found")
    }
    ff.Init(len(patterns[0][0]), 40len(patterns[0][1]))
    ff.Train(patterns, 10000.60.4false)
    return ff, nil
}

func saveModel(ff *gobrain.FeedForward) error {
    f, err := os.Create("model.json")
    if err != nil {
        return err
    }
    defer f.Close()
    return json.NewEncoder(f).Encode(ff)
}

全体のソースは GitHub に置いてあります。

GitHub - mattn/flower-detect
https://github.com/mattn/flower-detect

実際に試してみます。

test

結果は「sunflower」。そうだよ向日葵だよ。

test

結果は「rose」。そうだよ薔薇だよ。

test

結果は「lilium」。そうだよユリだよ。

gobrain を JSON で出力してモデル扱いにするというこの方法を使えば、簡単な画像分類であればインストールが難しい TensorFlow を使わずともポータブルに実行出来ます。特に GPU を使う程ではないといった場合にも便利かなと思います。一応 smartcrop というパッケージを使って画像内で注目される部分で crop する様にしてありますが、いくらかの画像では失敗します。これは画像をノーマライズしていないのでしょうがないですね。学習には10分くらい掛かると思います。

尚 Golang で TensorFlow やりたい人は以前書いた記事の方を参照下さい。

Big Sky :: golang で tensorflow のススメ

tensorflow といえば Python と思っておられる方も多いのではないでしょうか。間違いではないのですが、これは初期に作られた Python 向けのバインディングに研究者達が多く食いついた結...

https://mattn.kaoriya.net/software/lang/go/20180825013735.htm
Go言語による並行処理 Go言語による並行処理
Katherine Cox-Buday, 山口 能迪
オライリージャパン 単行本(ソフトカバー) / ¥3,080 (2018年10月26日)
 
発送可能時間:

Posted at by