みどりねこ日記

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

東京大学大学院情報理工学系研究科合格しました

無事合格しました。

関係者の皆様、特に研究室のメンバーとアルバイト先の方々、ありがとうございました。

入学した場合は創造情報学専攻の千葉研究室でプログラミング言語の研究などをすると思います。

先月NAISTの窓口に問い合わせたところ、悩む猶予をいただけるとの事だったので、できるだけ早くどちらに入学するかを決めたいと思います。

試験はTOEFLの提出、実技(プログラミング)または数学、筆記試験、面接という感じです。

以下は参考にした本です(といっても一冊しかないのですが……)。

過去問を見た限りだと広い範囲が出題されそうだったので、過去問を解きつつこれをパラパラと見て、ちょいちょい何かを実装して、……という感じで対策?しました。

ピンチだったのはTOEFLで、6月半ばに$200の受験料を払ってTOEFLを受験しにわざわざ新潟まで行ってきたんですが、試験終了後のダイアログメッセージをよく読まずキャンセルボタンを押してしまいました。 これ実は「試験の結果自体をキャンセルしますか」というメッセージだったらしく、$200が泡になる+TOEFL提出が間に合わなくなる事態に陥りました。 結局東京大学で受験できるTOEFL iBTを受験し事なきを得ました。

試験結果をキャンセルしたいひとなんているわけないでしょ!!!

僕は数学ダメマンなので迷わず実技を選びました。 プログラミングコンテストのような問題が出題されたので、Clojureでちまちま解きました(言語自由)。 REPLで出力結果を確認しながら解けるし、全探索書いてもそこそこ速いし、core.match強力だし、なによりメモリ管理気にしなくていいのでこういう試験には便利です。

筆記は全部解けたんじゃないかと思います。 距離測定器について述べよ的な問題が出たのですが、うちの研究室はレーザー屋なので楽勝でした。

面接はやたら早く終わったから落ちたかと思った。

あと苦労したことは合格発表ですね。 書類には掲示板に合否を貼りだすと書いてあったのですが、掲示板どこだよまじファック。 警備員のおじさんに聞いたら本部へ行けと言われたので本部棟に向かったら、本部棟2号へ行けと言われ、本部棟2号のおばさんには「私は知らないですね、管轄じゃないです」みたいなこと言われた。

結局研究科の入試課に問い合わせました。最初からそうすればよかった。

NAIST合格しました

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

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

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

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

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

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

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

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

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

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

やさしく学べる微分積分

やさしく学べる微分積分

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

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

やさしく学べる線形代数

やさしく学べる線形代数

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

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

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

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

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

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

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