2014年9月13日土曜日

Clojureのloop/recurに相当するモノをつくってみた話.

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク
golangを勉強すべく, lisp処理系などを実装し始めたのだが, vmなんて気の利いたモノは実装しないので, 末尾呼び出し最適化など は望むべくもない. しかしながら再帰の使えないlisp処理系などクソである. いろいろ考えた末, Clojureのrecurなら実装できそうなことが分かった. 機能としては限定的だが少ない手数で作れるためちょっとした処理系にはおすすめだろう. ということでどういうモノを作ったのか説明してみる.

末尾呼び出し最適化とは

[SICP]から必要な言葉を引っ張ってくる.

再帰

ここに来る人はこんな説明いらないとは思うのだが, 念のため. 素朴には, 関数を記述するのに関数自身への呼び出しが含まれている, というもので, たとえば階乗n!を計算するfactorialという関数は
(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))
などと書かれる. これは
  • 1!は1である
  • n!は(n-1)!にnをかけたモノである
という階乗n!の定義にしたがったものである. これを計算すると n * (factorial n - 1)がたくさん「積み上がる」ことになる.
もう一つの書き方は,
(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))
  
というもので, [SICP]では線形反復と呼んでいるようだ. 途中の結果とカウンタ, 上限を次々と渡している点が特徴である. 命令的な言語におけるfor-loopのようなモノである.

末尾呼び出し

ものすごくシンプルな例を出すと, 次のようになる.
(define f (n)
  (if (< n 3)
    (f (+ n 1))
    n))
      
"関数の呼び出し"が, fにおける"最後の計算"になっている, その事を末尾呼び出しという.

末尾呼び出し最適化

末尾呼び出し最適化とは, 末尾呼び出しの場合は, 「積み上がり」を生じさせずにloopでかけますよ という事. しかも自動でできる. 具体的には先ほどのfはこんな感じになる.
      fopt(n){
        for ; n < 3 ; {
          n += 1
        }
        return n
      }
  
唐突にgolangに変わってしまって申し訳ないのだが, fが最適化されるとこのようなfopt相当の"振る舞い"を示す. schemeの処理系はこの最適化が必須である([R5RS], [R6RS]等)

forで書きたくない, 作りたくない

lispの処理系を作っている手前, 他の処理系で処理できるコード, 具体的にはsrfiとかのコードを参考にすることにすることなるのだが, 当然再帰を使って書かれている. これを手動でfor構文で書き直す必要がある. その書き換えは確実にできるわけではなく, バグの原因である.
さらにはforを実現する構文を処理系にいれる必要がある. ところが相性が悪い. 具体的にはbreakやreturn, continueを入れる必要があるが, これはjumpでありどこに飛ぶかを制御する必要がある. vmベースでない場合, Eval関数に環境とS式を渡して評価するインタプリタになるが forのEval関数呼び出しまで抜ける必要が出てくるが, Eval呼び出しの 深さがマッチしている保証がどこにもなく, 処理系の実装に用いる言語によっては 困難もしくは適切な記述が難しい(golangでこの目的でpanic/recoverを使うことは邪悪だろう). かといって, stack over flowの可能性のある再帰呼び出しを行う訳にはいかない.

loop/recur

そこでloop/recurの登場となる. これはClojure[clj]の構文である. Clojureに関しての日本語の情報は[stu]が詳しい. JVMの制限上, schemeのような再帰呼び出し最適化が不可能であるため用意された. 具体的なコード例をあげてみよう
(define xs (loop [i 0 xs '()]
             (if (< i 3)
               (recur (+ i 1) (cons i xs))
               xs)))
このコードは
  1. loopの部分でiに0を, xsに'()を束縛し,
  2. i < 3ならば recurの処理を(後述)
  3. そうでないならxsを返す
という処理になっている. loopはxsが返ってくると xsをそのまま返す. ある種のletだと思っていて良い.
recurなのだが loopで作られた束縛に異なる値を束縛した環境を 別途作り, 再びloop内部を先頭から評価するという挙動をする. したがって初回の実行は i = 0, xs = '()なので
  recur 1 (0)
  
となり, loop [i 1 xs (1)]相当で次のloopが開始される.

実装してみる

方針

loopでRecur Objectを作り, recurに束縛, recurがevalされる度に 新たにenvを作るという方針にした. 処理系の束縛は深い束縛である(Scopeがnestする度にEnvironmentが積み重なっていく).
どの辺につっこむか? というイメージを得るために 対象のコードと[SICP]のevalのコードを引用しておく. loopもrecurもapplyされるモノである.
(define xs (loop [i 0 xs '()]
             (if (< i 3)
               (recur (+ i 1) (cons i xs))
               xs)))

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ((begin? exp) 
         (eval-sequence (begin-actions exp) env))
        ((cond? exp) (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) env)))
        (else
         (error "Unknown expression type -- EVAL" exp))))  
  
次にgolang側のloop実装コード. Recur Objectを作るときに内部で環境を作っている. 肝はEvalして返ってきたObjectがRecurならばfor-loopするということだ. これによって, loopの位置に制御が戻る. またRecur Objectが持っている環境がEvalに使われている.
 env.Bind("loop", Closure(func(dynamic Environment, cdr Pair) interface{} {
  r := NewRecur(dynamic, Car(cdr))
  var x interface{}
  for recuring := true; recuring; {
   for _, b := range List2Arr(Body(cdr)) {
    x = Eval(r.Env(), b)
   }
   _, recuring := x.(*Recur)
   if !recuring {
    return x
   }
  }
  panic("never reach")
 }))
  
Eval内部でRecur ObjectがApplyされる近辺.
  • Cdr(expr)で(recur (+ i 1))の(+ i 1)を保持している.
  • r.Updateで, Recur Object内に保持される次のループに使われる環境を作っている.
  r, ok := car.(*Recur)
  if ok {
   xs := make([]interface{}, 0)
   for _, v := range List2Arr(Cdr(expr)) {
    xs = append(xs, Eval(env, v))
   }
   r.Update(xs)
   return r
  }
  

closureとの兼ね合い

loopのなかでclosureを作ったときループ変数を捕捉したらどうなるか?ということだが, recurのUpdateで新たに環境が作られているので問題ない. 次のコードは, 2, 1, 0を出力する. recurによって作られたが参照されていない環境はGarbage Collectされるので 環境が青天井に生成されてメモリが圧迫される心配はない.
(define xs (loop [i 0 xs '()]
             (if (< i 3)
               (recur (+ i 1) (cons (fn [x] i) xs))
               xs)))
((car xs) 'a)
((cadr xs) 'a)
((caddr xs) 'a)
  

さいごに

Clojureのloop/recurの説明は山ほどありますが, わかりにくいことが多いと思います. ここでの実装のようなとらえ方でいればイメージが湧くかと思いますがどうでしょう? closureのある言語でのforって裏でいろいろやってる想像ができますね. loop/recur構文を使った, 末尾再帰呼び出しの手動最適化は, 処理系側の実装コストが小さいので lisp処理系を実装するときは作ってみるといいと思います. ではでは〜

文献

  • [SICP] "計算機プログラムの構造と解釈第二版" 1.2.1 線形再帰と反復, 4.1.1 評価器の中核
  • [R5RS] Revised^5 Report on the Algorithmic Language
  • [R6RS] Revised^6 Report on the Algorithmic Language. 日本語ユーザにとってありがたいのはこの辺.
  • [SRFI-1] SRFI-1 リストライブラリ日本語訳
  • [clj] clojure.org
  • [stu] "プログラミングClojure" Stuart Halloway (著), 川合史朗 (翻訳) Amazon

2014年7月28日月曜日

golangをいじりはじめてintefaceで悩んでみた.

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク
golangをいじりはじめてintefaceで悩んでみた.
「驚き最小原則」という話がありますが, golangをいじっていて一番驚いた(困惑した)話をしたいと思います. 最終的にちょっとした実験の結果, 納得はしたのですが, じゃあ適切に使ってないんでは?と感じ始めてまだ答えが出てません. 知っている方のコメントをいただけると幸いです.

出てきたのは最近でもないけど, twitterTLを見ていてユーザーが劇的に増えた感じもしない (観測範囲の問題かも), golangですが, 個人的には非常に良い言語だと思います. なんせ無駄なモノがない. 覚えることが少なくていい. go getとかも考えが行き届いている感があります. 構文的にもC系の言語を知っているならかなり素早くなじめるでしょう.

で、他の言語であまり見かけない機構でかつgolangを使っていく上で避けて通れない機能がinterfaceです. 参考. intefaceという単語自体は頻出の語彙だと思うのですが, なんか違うらしいです. 他の言語をよく分かっていないので, どう違うかは語りません. 私の理解では, どういうメソッドを持っているか?というメソッドの集合がintefaceで, 気にするモノは
  • 名前
  • 引数(仮引数の名前, 型)
  • 返り値の型
です.
ほかのinterfaceを使って指定することもできます. i.e.
type X interface {
    Foo()
}

type A interface {
    X
}
        
inteface Aが持つメソッドを指定するのに他のinteface Xを指定することでFooを持つことが指定されます. この辺はio.Readerとio.Seekerからio.ReadSeekerが定義されるとかで出てきます.

これだけではなんか手応え無いので, printlnしてみましょう. playgroundで試す.
package main

type X interface{}

type x struct {
 value int
}

func MakeX(value int) X {
 r := &x{value: value}
 println(r)
 return r
}

func main() {
 v := MakeX(1)
 u := MakeX(2)
 println(v)
 println(u)
}
        
fmt.Printlnじゃなくてprintlnなのが味噌で, より低水準なモノをはいてくれるようです. なんだかこんな様なoutputを出してくれる.
0xfeee1f4c
0xfeee1f48
(0x50e20,0xfeee1f4c)
(0x50e20,0xfeee1f48)
    
1つめ, 2つめはMakeXの中でのprintlnの結果で, rが保持するアドレスです. では3つめ, 4つめのは何かというと, これがintefaceの実体(以下inteface値と呼ぶ)で, これは先頭がintefaceを表現する型へのptrで, 後ろがdataへのptrです. 値の一致の仕方から了解いただけると思う. 気になる人は実装でも追っかけてください. 参考: http://research.swtch.com/interfaces"Go Data Structures: Interfaces"

intefaceなんやねんという話からちょっとずれますが, MakeXが*xじゃなくてXなのがポイントで, structの中味と名前xをpackageの外に公開せずに済みます. (参考: go言語のコンストラクタでinterfaceを返す) testで何か標準以外のリッチな機構を使うべきか?という議論はありますが, カプセル化とかそういう話は変わらないはず.

また, inteface値が型とDataへのptrのペアだという理解に立てば, MakeXが*Xを返すのがナンセンスだという事になります. documentには明示的に書かれていないので, 習作ではやらかしました. はい.
同様にintとかの組込型でassertするのもナンセンスだと了解できます. なぜならassertという動的なテストはinteface値が保持している型情報を読み出す操作だから. その場合適切にstruct, inteface, typeでwrap(boxing?)すべし, といえるだろう. 静的に決定可能ならコンパイル時に解決されるはずで, okとか不要でしょ.

最後にinterfaceは名前を気にしない, という話.
package main

type X interface {}

type A interface {
    X
}

type B interface {
    X
}

type a struct {
}

type b struct {
}

func MakeA() A {
    return &a{}
}

func MakeB() B {
    return &b{}
}

func MakeX() X {
    return MakeB()
}

func main() {
    m := MakeX()

    switch m.(type) {
    case A:
        println("A")
    case B:
        println("B")
    case X:
        println("X")
    }
}
    
このコードの実行結果は
A
    
となる. playgroundで試す. また, caseのAとXを入れ替えるとXになるし, caseのBとAを入れ替え, かつMakeXの中味をMakeXAにするとBになる. これはintefaceの名前を見ないで, メソッドの集合のみを見て, マッチした最初のcaseを採用しているからだ. もちろんA, Bに適宜メソッドを追加し, a, b側で実装すれば, 見慣れた継承っぽい挙動をするようになる. 問題は, そのような挙動を得るためにメソッドを追加する行為が設計として正しいか?ということだ. 私にはよく分からないが, たぶん好ましいことではないだろう.

聴いてなかったりします. orz. https://twitter.com/mattn_jp/status/462403160443596800 golang 上達の道は interface 設計と channel の有効活用すね。その辺は lestrrat さんが #rebuildfm で大事さ喋ってるので聴いてない人は聴くべし。

2014年4月19日土曜日

yeoman + bower + grunt

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク
最近流行の環境を作って使うことにした. 情報自体はいっぱいあるのであまりN/S比を悪化させたくない. 自分用メモとありがちなのとちょっと違う部分にふれておく. たとえば
今回の利用目的はcraftyで作っているshogi用のjsの開発. 500行を超えてそろそろいろいろ辛くなってきて, 一方でtestとか書いてもモチベーションを維持できそうな確信が持てたからである.
主にほしいと思ったメリット:
  • パッケージのフォーマット
  • パッケージングの自動化
  • Testのツール
  • Testの自動化
  • コード圧縮ツール
  • あたらしいものさわりたい
といったところ. 想定していなかったけど良かったのはjshintとかかな.
どんな感じでインストールしたか? というと, 環境がScientific Linux(CentOSみたいなもん) なのでsudo yum install npmでまずnpmを入れた. 次にnpmでインストールするのだが, -gは身の毛がよだつようなオプションに感じたので使わないことに. やはり開発環境になにが入っているかはっきりしている方が気分がいい. --saveをいちいち書かないといけないのはどうなのか.
npm i yo yeomanをいれ、 npm i generator-craftyと craftyの開発のテンプレートを生成するgeneratorを入れます. ./node_modules/yo/cli.js craft ./node_modules/yo/cli.js crafty:scene MyScene ./node_modules/yo/cli.js underscore などとたどたどしく入力. これでappの下にbower_componentsとしてcraftyなど依存したモノがインストールされた.
知っている人は「何やってんねん」だろうし, 知らない人は「なんでそんなにタイプするの?面倒じゃない」だろう. npm -gしないのが悪い!という説もあるけど、そこは譲るつもりがない. PATHを通せばよいのです. というわけでpythonのvirtualenvからactivateのスクリプトを持ってきて手を入れました. 部分的に抜き出すとこんな感じ.
deactivate nondestructive

VIRTUAL_ENV="略/shogi-js/node_modules"
export VIRTUAL_ENV
_OLD_VIRTUAL_PATH="$PATH"
PATH="$VIRTUAL_ENV/.bin/:$PATH"
export PATH

# unset PYTHONHOME if set
なにも難しいことはしていません. node_modules/.binにいろいろある、ということです. これでめでたく$ gruntとか実行できるようになりました. 特定のnode_modules/.binしか見ないのですっきりです.
.jshintrcを書く. 最終的に こうなった. .jshintrcはjsonではないらしいです. 仕様がよくわかりません. なにはともあれ、コメントを入れるときに困るので, jsonで書いてjqで処理したモノを.jshintrcとして置いておき, 原本にコメントを一杯入れる方針にしました.
あのさーgeneratorが吐くGruntfile.jsがボコボコなんですけど... ぼこぼこすぎてjshintが途中でさじ投げます. 弱小generatorだと叩く人が少ないからこんなもんなんでしょうか. jshintの勉強だと思って少しずつ直していきたいと思います.
修正後のindex.html 最初は改行コードが統一して無くて吐きそうになった. 弱小テンプレートはよくない. webappだったらあり得ない話でしょう. 無より良いくらいで頑張っていきたいと思います. srcに入っているbower_componentsのpathはもうちょっとすっきりさせる方法が あるらしいのですがまだやってないです. この辺はwebappで作っても同じはず. 構造的にindex.htmlしかなくて, そこでCrafty.initしてsceneを走らせる点では 全く同じでそれ以外作りようがないのでこの辺は迷う余地がなかったです.