みどりねこ日記

よくわからないけど、頑張りますよ。

NAIST合格しました

奈良先端科学技術大学院大学情報科学研究科に合格しました。

みなさんには大変お世話になりました。ありがとうございました。

僕は言語処理とかに興味があったのですが、うちの大学ではそのへんを扱っている研究室はなかったので外部の院を探していたところ、NAISTの中村研究室が面白そうだということで受験しました。

試験は数学、英語(TOEICまたはTOEFL)、面接です。また出願時に小論文を提出します。

小論文は提出期限当日の昼に慌てて書き始めたので、ひどいものでした。 しかし友人と教員が真っ青になりながら深夜まで添削を重ねてくれたおかげで、かなりまともなものになりました。

当日消印有効だったのですが、小論文をイチから書きなおしたりしたため、日付の変わる頃に郵便局に駆け込むなどというギリギリの世界を楽しみました。

数学の過去問は有志の方々が公開されているものがあるので、それを一つの目安として以下の参考書に取り組みました。試験一週間前になるまで出題範囲を勘違いしていたので、実質的な勉強時間はあまりありませんでした。受験される方は、お気をつけ下さい(?)

ちなみに微分積分は大学一年生のときに勉強した程度で、完全に忘れていたので結構ピンチでした。

基本的にはやさしいシリーズをざっと解いて、友人に教えてもらいつつ大学院への数学で出題範囲の演習をしていました。

やさしいシリーズは1日あれば一周できるので本当に役に立ちます。

やさしく学べる微分積分

やさしく学べる微分積分

やさしく学べる微分方程式

やさしく学べる微分方程式

やさしく学べる線形代数

やさしく学べる線形代数

プログラミングのための線形代数

プログラミングのための線形代数

詳解 大学院への数学―理学工学系入試問題集

詳解 大学院への数学―理学工学系入試問題集

TOEICは875点だったので、あんまり心配はしていなかったです。

友人たちにおんぶにだっこな人間性がかいま見える大学院受験となりましたが、これから精進していきたいと思います、うんぬんかんぬん。

何もしていないのに壊れた話

友人のLinux MintのXが急に立ち上がらなくなった。

彼が席を立ってしばらくして戻ってきたらそうなっていたらしい。

彼はとくに心当たりもないとのことだったので、とりあえずはログを読んでみたが特に異常もない。

結果から簡単に言うとcinnamon-screensaverとnemoが入っていなかったようで、

放置して一定時間たったところでスクリーンセーバーがクラッシュしたとか、そういう話だった。

何もしていないのに壊れることもあるんですね。

Clojure内部のメソッド定義について

最近Clojureのコード読んでたんですが、いたるところ(このへんとか)に

public Object invoke() ;

public Object invoke(Object arg1) ;

public Object invoke(Object arg1, Object arg2) ;

public Object invoke(Object arg1, Object arg2, Object arg3) ;

public Object invoke(Object arg1, Object arg2, Object arg3, Object arg4) ;

...といった調子でメソッドが定義されててギョェ〜〜ってなってた。

なんで可変長引数使わないのかよくわからなかったのでIRCに投げてみたところ、可変長引数はコストが大きいんだそうで。だからJVMの速度的な問題でこのような実装になっているとのこと。

うえのinvokeメソッドはClojureの関数を引数に適用するメソッドなわけなのですが、なるほど確かに関数に引数1000個とか渡さないわ。

だったら上の実装が現実的なのね。

instaparseで遊ぶ

この記事はClojure Advent Calendar 2013 - Qiita [キータ]19日目の記事です。

instaparse

本記事ではinstaparseというライブラリを使って遊んでみます。

instaparseはEBNFやABNFで記述された文脈自由文法から自動的にパーサを生成してくれます。 左再帰、右再帰、曖昧性など、いかなる文脈自由文法でも動作します。 生成されたパーサは文字列からenliveまたはhiccup風の木構造を生成します。

今回は型なしラムダ計算を題材にします。

型なしラムダ計算

型なしラムダ計算は、型がない(または型がひとつしかない)ラムダ計算です。

ラムダ計算はとてもシンプルで、すべての計算が関数定義と関数適用だけで実現可能です。

ラムダ計算の構文は以下の3つからなります。

t ::=        項
    x        変数
  | \x . t   ラムダ抽象
  | t t      関数適用

定義くらいはほしいだろう、ということで、今回作るパーサは以下のような拡張をした構文にします。

lang ::= (expr | def)+
def  ::= var '=' expr ';'*
expr ::= (var | app | abs)
     |  '(' app | abs ')' ';'*
var  ::= [a-zA-Z-]+
app  ::= expr expr
abs  ::= '\\' var '->' expr

さて、上の構文を用いてパーサを作ってみます。

(ns lambda.core
  (:require [instaparse.core :as insta]
            [clojure.core.match :as match]))

(def parser
  (insta/parser
    "lang = (expr | def)+
    def = <w> var <'='> expr <';'*> <w>
    <expr> = <w>
    (var | app | abs
         | <'('> (app | abs) <')'>) <w> <';'*>
    var = <w> #'[a-zA-Z-]+' <w>
    app = expr expr
    abs = <'\\\\'> var <arrow> expr
    w = #'[\\n\\s]*'
    arrow = '->'
    "))

簡単に書けました。

実行すると以下のような結果が得られます。

(parser "true = \\x -> \\y -> x;")
; => [:lang [:def [:var "true"] [:abs [:var "x"] [:abs [:var "y"] [:var "x"]]]]]

驚きのお手軽感です。

お分かりかとは思いますが、langやdefなどがキーとなった木(ベクタ)ができています。そして< >で囲まれたexprやwは出力結果にはありません。 < >はパース結果を隠す役割があります。他にも正規表現が使えたりと大変便利なライブラリです。

またパース結果をグラフ化することもできます。

(insta/visualize (parser (slurp "sample.lambda")))

f:id:paprikas:20131217004809p:plain

せっかくパーサができたので評価できるようにします。

実装にあたってはこの辺とかこの辺を参考にしました。

α変換...本来だと条件によって置換しなくてもいいこともある。フムフム〜〜〜。

面倒だし、全部置き換えたところで一緒なので全部置換することにします。

(gensym)でユニークな変数が降ってくるので、\x -> \y -> x yのような形のものを、\unique_symbol -> \y -> \unique_symbol yのように変換します。 そのようにすれば適用する式の中身と変数名がかぶりませんね。

HaskellOCamlみたいなパターンマッチがClojureにもあったらなーと思っていたら、clojure.core.matchがなかなか良さそうなので使ってみました。

(def env (atom {}))

(defn evaluate [expr]
  (match/match
    expr
    [:def v e]
    (do (swap! env conj {v e}) v)

    [:var v]
    (get @env [:var v] [:var v])

    [:app [:var v] n]
    [:app (get @env [:var v] [:var v]) n]

    [:app [:app m n'] n]
    [:app (evaluate [:app m n']) n]

    [:app [:abs [:var v] body] n]
    (clojure.walk/postwalk
      (fn [z] (if (= z [:var v]) n z))
      (evaluate body))

    [:abs [:var v] body]
    (let [v' (str (gensym))]
      [:abs [:var v']
            (clojure.walk/postwalk 
              (fn [z] (if (= z [:var v]) [:var v'] z))
              (evaluate body))])))

(defn show [expr]
  (match/match
    expr
    [:lang & n]
    (reduce str (map show n))
    [:def v e]
    (str (show v) " = " (show e))
    [:var v]
    v
    [:app f x]
    (str "(" (show f) " " (show x) ")")
    [:abs arg e]
    (str "^" (show arg) "." (show e))))

(defn evaluate-all [expr]
  (match/match
    expr
    [:app m n]
    (evaluate-all (evaluate expr))
    :else expr))

(let [code
      (str
        "true = \\x -> \\y -> x;"                ;; "true = ^x.^y.x"
        "false = \\x -> \\y -> y;"               ;; "false = ^x.^y.y"
        "if = \\p -> \\t -> \\f -> ((p t) f);"   ;; "if = ^p.^t.^f.((p t) f)"
        "cons = \\x -> \\y -> \\f -> ((f x) y);" ;; "cons = ^x.^y.^f.((f x) y)"
        "car = \\p -> p true;"                   ;; "car = ^p.(p true)"
        "cdr = \\p -> p false;"                  ;; "cdr = ^p.(p false)"
        "(car ((cons true) false))"              ;; "^x.^y.x"
        "(((if true) false) true)")              ;; "^x.^y.y"
      parsed (parser code)
      results (map evaluate-all (rest parsed))]
 (map show results))

Clojureすごい!instaparseすごい!

というわけで、19日目はこれでおしまいです。

シリコンバレーいってきた

夏のインターンの関係で、シリコンバレー行ってきた。

すごいおいしいみたいな印象があったライスクリスピー、久しぶりに食べたらクッソまずかった。

けど友達にも「美味しいよこれ!!!」って言って買わせた手前、美味しいねこれ!って言いながら食べ続けた。

食事は結構美味しかったんだけど、普段一日一杯ジュース飲むだけみたいな生活送ってたせいかお腹壊した。

しかも3日目くらいに熱が出てつらい目にあった。

GoogleとかFacebookとかEvernoteとか色々訪問したけれど、どの国のどの企業でも開発部門と営業企画部門では雰囲気が全然違うなって。

開発部門は暗い部屋にぼうっとディスプレイの光に照らされたおっさんの顔がたくさんあるし、デスクの周りにおいてあるのは美少女なフィギュア。一方企画側はオフィス内で弓矢を飛ばして遊んでいた。

欧米は欧米はっていう人たちもいるらしいけど、日本は最高の国ですわ。 泊まってたのはヒルトンホテルだったんだけど、数ブロック離れるとあら不思議マリファナの匂い。というかもう道がめちゃくちゃ汚い。

日本サイコー。

まじで。

Clojure:binding と遅延シーケンス

Clojure in Action読んでて、へえってなったのでメモ。

当然と言えば当然なのかもしれないけれど。

(def ^:dynamic *factor* 10)

(defn multiply [x]
  (* x *factor*))

(map multiply [1 2 3])

(binding [*factor* 20]
  (map multiply [1 2 3]))

Clojure の var はbindingで束縛することができる。

しかし直感に反して上のどちらのmapも [10 20 30] を返す。

これはなぜかというと、mapのような関数は遅延シーケンスを返すからで、この遅延シーケンスは必要となるまで評価されない。そして評価が実際に行われたときはすでにbindingフォームの外であるので、 factor も元々の10に戻っている。

これを意図したようにするには

(binding [*factor* 20]
  (doall (map multiply [1 2 3])))

とする必要がある。

どうてきすこーぷ、気をつけよう。

なんかこれ同じようなことをDBでもやったような気がする。

DBのコネクションをラップしたマクロが用意されてて、そいつが返すのは遅延シーケンスだということに気づかず、コネクションを閉じる前に結果を現実化しなかったせいでDBから結果が返ってきてないように見えて慌てたような。

Clojure in Action

Clojure in Action