2015-12-04

Noël de Quatre-Mains - Les Frères

この記事は好きなクリスマスソング Advent Calendar 2015 の4日目の記事です．

毎年12月に入ると必ず聴くアルバムがあります．タイトルにもなっている，Les Frères の Noël de Quatre-Mains です．

Les Frères は横須賀出身のジャズピアニストで，名前の通り実の兄弟です．2人で1つのピアノを使って連弾をします． 'Noël de Quatre-Mains' は 'Christmas of Four-Hands' のフランス語で，'quatre-mains' (4つの手) というのは Les Frères の代名詞にもなっています．

ジャズの中でも Boogie-Woogie 曲やアレンジが多いので，彼らの音楽はとにかく踊れます． (ブギウギはブルースをアップテンポにして踊れるようにしたものだ，とどこかで聞いたような…) このアルバムは，皆さんがこの時期よく聞くであろう様々なクリスマス・ソングを boogie-woogie アレンジしているものです．

さて，このアルバムは素晴らしく幸せになれるのでぜひとも全曲聴いていただきたいのですが，初めての方も多いかと思うのでいくつかピックアップしてみました．

Jingle Bells

とりあえずこのアルバム内ではおそらく最もキャッチーなアレンジ曲です．

youtu.be

(本人たちが弾いているものがなかったのでこちらで…)

こんなに挑発的で悪そうなジングルベルなんて聴いたことないです． 1'54 からの最高音の倦怠感なんかもう本当に素晴らしくて一気に脱力してしまいます．

Noël de Quatre-Mains

アルバムのタイトルにもなっている曲です．

youtu.be

とにかくこの1曲だけでクリスマス・ソングを堪能できてひたすら幸せになれる，そんなメドレー曲です．クリスマスの昼間からホットワイン飲みながら聴いていたい…

Rudolph The Red-Nosed Reindeer

赤鼻のトナカイ．

youtu.be

聴いてる途中で「あ，これ赤鼻のトナカイか！」と毎回気付くくらい boogie になってしまっています．

Boogie Christmas

最後の〆！

youtu.be

最初に紹介した Noël de Quatre-Mains と同様，こちらもクリスマス・ソングメドレーですが，前者よりももっと boogie になっています．本当に楽しい1曲です．

さいごに

今回紹介したのはアルバムの中でも氷山の一角で，本当はもっと聴いてほしい曲がたくさんあるのです… それから，本人たちが演奏している音源が少ない (今回のアルバムに関しては0でした…) のも悲しい…

悔しいので彼らの曲で私が一番好きな曲を最後に貼っておきます．

G Sign

クリスマス全然関係なくてごめんなさい！！！！！でもかっこいいから最後まで聴いてください！！！！！！！

youtu.be

好きなクリスマスソング Advent Calendar2015，次回は taketin さんです．

2015-04-24

CPS というプログラミングスタイルの導入の話

今日 (もう昨日だけど) 大学の授業で CPS というプログラミングスタイルの話を聞きました．これを読んでいる人はきっと CPS が 'Continuation-Passing Style (継続渡し形式)' のことで，それがどのようなスタイルのプログラミング手法なのかも分かっていて，さらに JS を CPS で書いたり継続を限定してみたりしている人ばかりだと思うので，そういう「どう使うか」みたいな話はしません．できません．ケイゾクムズカシイ．

今回は授業で「プログラミング中のどこで CPS という概念に辿り着くか」という 'CPS の導入' の部分を聞いて，それが今まで聞いてきた 'CPS の導入' の話の中で一番しっくりきたので備忘録も兼ねてご紹介します．継続プロの方々には当たり前の話かもしれません．それからできるだけ分かりやすくするために細かい動きなどはあんまり言及していません．Overview だと思っていただければ幸いです．あと OCaml で書きます．

eval 関数

授業で何をしていたかというと，電卓を作っていた，つまり，ユーザが書いた式を評価するインタプリタを作っていたわけです．その '評価する' 関数が eval です．

例えばユーザが

3 + 5

という式をインタプリタにかけて計算しようとしたとき，インタプリタの中でこの式は + が関数，3 が第一引数，5 が第二引数である

+ 3 5

という関数適用の式に変換されてから，各部分式 (+, 3, 5) をそれぞれ eval して，関数適用が行われ，適用の結果がまた eval され，ユーザが求める計算結果 (8) が返ってきます． (ボトムアップのように書きましたが，本当はここは全体を eval するために各部分式を eval していく再帰構造になっています)

評価順序

さてここで先ほどの + 3 5 はどの部分式から評価されるでしょうか？はい，It's up to you です．あなたがもし関数部分 (+) から評価するインタプリタを書きたいと思ってそう開発してあげれば，+ 3 5 は関数である + から評価されます．では引数部分はどうでしょう？インタプリタ内部では各引数はリストに入っています．今回の場合は [3; 5] というぐあいです．このリストの先頭から評価するか，最後尾から評価するか，それもあなたの意思次第です．

で，実は OCaml はこのリストの最後尾から評価していく戦略を取っています．つまり，

+ 3 5

の引数部分は 5 から評価されます．もっと言うと，

3 + 5

は右側の引数から評価されます．よく分からないのですが，OCaml の場合は最後尾から評価した方が後々効率がよいのだそうです．

'式のどこから評価するか' は言語の開発者の意思次第です．普通の計算なら答えが合っていればいいと思う人もいるかもしれません．でも次の場合はどうでしょう？

ここで OCaml のお勉強です．print_string は string 型の値をもらってきたらそれを出力して unit 型の値を返します．unit は () という値しか持たない型で，とりあえず void だと思ってくれればよいです．print_newline はその () をもらってきたら改行を出力して () を返します．

また，; は逐次実行です．; はそれ以前に書いた式が返した値を破棄して次の式の評価へと進みます．上の例の * の左側の引数の場合，まず print_string "left" が返した値 () を捨てて次の式 print_newline (); の評価へと進みます．ところがここでも ; が print_newline () が返した () を捨てて次の式を評価しにいきます．最後に 5 - 3 の評価は最終的に 2 になるので，* の左側の値は最終的には 2 となり返ってきます．

実際に OCaml でこの式を評価してみると

f:id:yuzumikan15:20150424052437p:plain

OCaml は右から評価するので，ちゃんと right から出力されています．

同じような式を他の言語で書いたら，言語によって right と left の出力結果が違ってきます．これは困りものです．同じ式なのに，ユーザが見る画面に書いてあることが違ってきてしまうわけです．

評価順序を統一する

どんな言語で書いても同じ結果になるように，評価戦略によらず評価順序を統一したい．とりあえず OCaml で書くときは let 文を書いて上から順番に評価されるようにします．

let は変数束縛です．ここで束縛した変数は in 以下で使えるようになります．例の場合，n1 に

(print_string "left"; 
 print_newline ();
 5 - 3)

を評価した結果が入り，in 以下で使えるようになります．次に n2 に

(print_string "right";
 print_newline();
 5 + 3)

を評価した結果が入り，in 以下で使えるようになります．最後に，

n1 * n2

を評価した結果がこの例全体の最終的な結果として返ってきます．

ここで重要なのは，let で変数が束縛されるときに = の右側の式は評価される ということです．n1 に

(print_string "left";
 print_newline ();
 5 - 3)

を入れるとき，この式は評価されるので標準出力が行われます．n2 についても同様です．例を実行してみると

f:id:yuzumikan15:20150424054751p:plain

今度は left から出力されました．このように，OCaml だったら let 文を書くことで評価順序を制御できます．

では Haskell はどうでしょう？Haskell の評価戦略は '遅延評価' と呼ばれる戦略です．これは，書いてある通りに評価を行なうのではなく，その式がどこかで本当に使われるときに初めて式の評価を行います．上の例 (と同じことが Haskell で書けたとしましょう) だと，let n1 = ... の時点で ... の部分はまだ評価されずそのままの形で n1 に入ります．n2 についても同じです．そのままの形です．最後に n1 * n2 が出てきたときにやっと，Haskell は「あ，n1 必要じゃん」と思って n1 に入っている式

(print_string "left";
 print_newline ();
 5 - 3)

を評価します (たしか Haskell は素直に左側から評価だった気が…間違ってたらごめんなさい)．この戦略だと，たとえ let を使っても，実際に変数が使われるタイミングによってやっぱり結果が違ってきてしまいます．今回の例ではきっと同じでしょうが，例えば最後を n2 * n1 と引数の順序を逆にするときっと結果が変わってきます．

カプセル化

どんな評価戦略でも評価順序を制御できるような書き方はないものでしょうか？ (反語)

元々評価したい式は

でした．これを必ず左側から評価したいとしましょう．まず，なぜ評価順序がいろいろ変わってしまうかを考えます．それは，左側も右側もどちらも評価できる式になっているから です．どちらもまだ評価できる式になっているのがダメ．ならば，どちらかを評価できない式に変えてあげましょう．今回は左側から評価したいので右側を評価できない式にします．

ここでもうちょっと OCaml のお勉強です．OCaml というかみんなだいすき TAPL のお勉強です．

OCaml で変数をスコープ内に入れる方法は2種類あります．1つはさっき使った let，もう1つは fun 文です．fun 文は要するにラムダ式 (無名関数) のことです．fun x -> x + 1 は λx.x+1 のことで，Haskell で書くと \x -> x + 1 です．これで x をスコープ内に入れて -> 以下で使うことができます．何が違うって束縛した変数が多相型か単相型かの違いですがここでは考えません．

今回評価順序を統一するにあたって fun を使うと嬉しいことがあります．fun は これ以上評価できない式 (= 値) なのです．詳しくは TAPL を読んで下さい．ここではとりあえず fun の中に書いてあることには触れられない，という説明にします．この fun を使って，評価したくない右側の式をまるっと包んでカプセル化してあげます．が，慣れていないのでまずは評価したい左側だけを let で束縛してみます．

次に let ではなく fun で n1 を束縛してみます．このとき n1 を使いたいのは左側の式を評価したあとなので左側の式のあとに fun n1 ->... を書きます (fun n1 -> 左側の式 としてしまうと，fun の中身には触れないので左側の式も評価されなくなってしまいます)．

(capsule1.ml はコピペしても実行できないので注意してください)

これで，fun の中にある右側の式には触れられなくなって，fun の前にある左側の式から評価せざるを得なくなりました．ついでに右側の式も fun を使って束縛してあげましょう．まずは先ほどと同じように let で n2 を束縛してあげます．

次に n2 を fun で束縛してそれ以降に行なう式 n1 * n2 をカプセル化します．カプセルにする fun n2 -> は右側の式を評価したあとだということに注意してください．

この式をどう読むかというと，

(print_string "left";
 print_newline ();
 5 - 3)

を評価し，その結果返ってきた値を n1 に入れて，

(print_string "right";
 print_newline ();
 5 + 3)

を評価し，その結果返ってきた値を n2 に入れて，

n1 * n2

を評価する．と読みます．

c は capsule の c

でもこれはまだ実行可能なプログラムではないですね．完全なプログラムにしてみましょう． capsule3.ml において何がおかしいかというと，左側の式

(print_string "left";
 print_newline ();
 5 - 3)

の値は 2，つまりただの数字なのに，そこに fun n1 -> ... という右側の式を引数のように渡してしまっていることです．というか，本当は 2 は n1 に入ってほしいので，

(fun n1 -> (右側の式)) 2

という関数適用が正しい形のはずです．では，(左側の式) (fun x -> 右側の式) を受け取ったら (fun x -> 右側の式) (左側の式) という関数適用を行なう関数を定義してしまいましょう．

終了です．c は capsule の c です．決して continu(ry

皆さん OCaml くらい書けると思うので説明はいらないかと思いますが，

let capsule x c = ...

は

let capsule = fun x -> fun c -> ...

と同じです．要するに関数 capsule は x と c という2つの引数をもらってきますよ，と読みます．

ではこの capsule を使って実際に capsule3.ml を動かすプログラムを書いてみます．

最初の capsule の第一引数 x に

(print_string "left"
 print_newline ();
 5 - 3)

が入って，第二引数 c に

(fun n1 -> capsule (print_string "right";
                               print_newline ();
                               5 + 3)
                               (fun n2 -> n1 * n2)
 )

が入っていて，capsule x c = c x なので

(fun n1 -> capsule (print_string "right";
                               print_newline ();
                               5 + 3)
                               (fun n2 -> n1 * n2)
 ) (print_string "left"
    print_newline ();
    5 - 3)

が実行されることになります．fun n1 -> ... の中には入れないので置いておいて，引数部分を評価しに行きます．ここで left と改行が出力されて 5 - 3 を評価し，2 が返ってきます．引数がやっと値になったので今度は関数適用が行われ，n1 に 2 が入った状態で fun n1 -> 以降の式を実行しにいきます．

次の capsule についても同様の動きです．n2 には 8 が入り，n1 * n2 が実行されて最終結果は 16 になります．

f:id:yuzumikan15:20150424082633p:plain

c は continuation の c

さて，長かったですがやっとどんな評価戦略であっても評価順序が同じになるプログラムを書くことができました．何をしたかというと，まだ評価してほしくない部分を fun でカプセル化して中を触れないようにし，先に評価してほしい式から返ってきた値を fun で束縛している変数に入れて -> の先の式を評価しに進んでいくのでした．

先に評価してほしい式に対して，あとで評価してほしい式のことを 'continuation, 継続' と呼びます．あとで評価してほしい式は先に評価してほしい式の '継続' になっている，という使い方をします．

そして，あとで評価してほしい式を fun でくるんで継続にして持ち歩くプログラミングスタイルのことを 'Continuation-Passing Style, 継続渡し形式' と呼びます．一般的に，さっき引数で書いた c は k というアルファベットで書きます．これは 'continuation' の 'c' がギリシャ語だかラテン語だかでは k になるからだとかなんとか…？

最後に，授業で紹介された Continuation-Passing Style (CPS) の約束事を書いて終わりにします．

常に (serious な) 関数適用は末尾呼び出しになっている
serious な関数には 'その後の仕事' を表す引数 k が1つ増える (= 継続)
値を返すときには k に渡す

ここで serious な関数というのは '評価順序を気にしたい' 関数 (= CPS で書きたい関数)という意味だそうです．反意語は 'trivial' な関数．例えば + という関数が serious か trivial かはプログラマの意思に依存します．+ の評価順序が左からだろうが右からだろうが関係ないと思えば + は 'trivial' な関数になり，きちんと厳密に評価順序を制御したいと思えば 'serious' な関数になります．

CPS で書くことの特徴として，システムの stack に今後の仕事を積んでいく代わりに，自前で関数の形で作って持ち歩いているということがあります．これによって，例えば評価中のどこかでエラーが発生したときにそのエラーを今後の仕事に propagate していくのではなく，エラーになったら今後の仕事は全部捨ててそのまますぐにエラーを返す，ということができます．無駄を省けます．

今後の授業 (この分野に詳しい人向け)

この授業，情報科の大学院の授業で，数理論理学の人たちと私が所属している研究室 (型理論とか証明とか) の人たちが主な参加者です．もちろん CPS という単語は知っていますし，今までのゼミでも書いたことがある人たちが多いです．ではどうして CPS なんかやったのかというと，授業では big-step semantics と small-step semantics と abstract machine の話をするらしく，今のところの目標として，big-step semantics と small-step semantics を行き来する (変換する) プログラムを書くからのようです．どういうことかというと，big-step と small-step を行き来する道具として，CPS の big-step + α を用いるのだそうです．もうちょっと言うと，big-step semantics の継続が small-step semantics になっている のだそうです．ふむふむ．なんかそんな感じする．

概念だけ聞いてるととても面白いんですけどね，継続…

2015-03-02

OCamler がリクルートのインターンで Python を書いてきました

2月1日〜23日まで，株式会社リクルートホールディングス（以下，リクルートさん）の冬インターンに参加してきました．

http://recruit-jinji.jp/winter-internship2015

実は去年の夏に，リクルートさんとクックパッドさんが共同開催した Joint!! という5日間のインターンに参加していて，予想以上に得られるものが多かった（お金はもらってません）ので今回もぜひ行きたいと応募したインターンでした．15万も美味しかったですし．

ちなみにこの時の私がとても楽しそうだったという理由で研究室の同期は今回応募，参加したらしいです．まだ，ここにない，出会い．素晴らしいです．

選考

Swift アイドルなので普段は iOS 開発をしているのですが，Web の知識をもっとちゃんと付けたいという理由でフロントサイドコースを選びました．

選考は，ES を書いて，AtCoder のプロコンテストがあって，1day job という流れです．

1day job，他のコースは6時間くらいで何かしらがっつり実装する，という内容だったようですが，フロントサイドは15分間の（Web 開発に関する）自慢大会でした．

とりあえず今までやったことを絞り出して，自己紹介でOCaml と Swift と某Y社ハッカソン優勝という単語をしっかり入れてプレゼンしてきました．

時間が余ったので懇親会で選考に来てる学生たちとまだ，ここにない，出会い．をしてました．楽しかったです．

インターン

Joint!! のときは1チーム4人のうち2人がプランナー，2人がエンジニアで，かなり企画重視のインターンでしたが，今回は1チーム3〜4人の全員がエンジニアという構成でした．企画も最初の1週間弱であとはひたすら開発だったのでエンジニアからしたらとてもわくわくするインターンだったのではないかと思います．「この問題を解決するためにどんな技術を使えるか」という，技術的解決のための挑戦をできたのはとても嬉しかったです．

さらに，今回は AWS などの普段は使えないサービスをがっつり使えたのもよい経験でした．

ちなみに，私は夏にがっつりやった Lean Canvas による企画なんかもとても重要だと思っていて，その経験があるからこそ現在趣味開発をできているので，企画をおろそかにしてよいとは全く思っていません．ただ，エンジニアだけのインターンではやっぱり技術や開発重視になっているととても嬉しいのは確かです（正直 Lean ってとても難しいですし，エンジニアとしては開発に入れないフェーズは大変つらいので…）．

'Indeed のうえ'

私たちのチーム（以下，MIT）は「表面上」フロントサイド2人，バックエンド1人の3人構成で，メンターの方が1人付いて下さいました．

5つのテーマから1つを選び，そのテーマに則したサービスを1つ開発する，という課題だったので，MIT は「将来のキャリアに役立つバイト探し」をテーマとして選択，「将来エンジニアを目指す学生のためのエンジニア求人サイト」を作りました．'Indeed のうえ'というサービス名です．よろしくお願い致します．

企画の段階でアンケートを実施して（100人くらい回答が集まりました．ありがとうございました．）その中で多かった（お茶濁し）「探し方が分からなくてエンジニアバイトに応募できない」という問題を解決しようという方向になりました．

で，技術として何を使えるか，ですが，

ネット上にあるあらゆるエンジニア向けの求人情報をスクレイピングして，そのバイトがどんな技術を用いたものなのかをタグ付けしていく，ということをしていました．

工夫したのはタグ付けの部分で，フレームワークから使っている言語を紐付けて親タグとして登録してあげたり，使っている言語によってその仕事が Web 系なのかモバイルアプリ系なのかなどの分類をしていました．

これを見ている方々には自然言語よりも形式的な書式の方が分かりやすいと思うので簡単な BNF もどきでも貼っておきますね．

タグの構成：

Genre = Web | Mobile | [Design] | Other

Web = [(Language, [Framework])]

Mobile = iOS | Android

Design = 'Illustrator' | 'Photoshop' |'Dreamweaver'

Other = IDE | Others

Language = (55個のプログラミング言語おのおの)

Framework = (Language で代表的なフレームワーク)

iOS = [Device]

Android = [Device]

IDE = [(6つの代表的な IDE)]

Others = [(その他，使用する OS や DB など)]

※ あくまで「もどき」なので細かいところ突っ込まないで下さいお願いします恐いです．

それから，なんやかんや自然言語を解析してそのバイトが「初心者向け」なのか「上級者向け」なのかというレベルに分けていましたが，ここは担当の社長が書いてくれるでしょう．

ちなみに 'Indeed のうえ'という名前，ネタでもありますが，私のプログラムだと 'C', 'C++', 'C#', 'Objective-C' を全て別の単語として認識可能なので，そういう意味で 'うえ' です．もちろん 'Java' と 'JAVA' は同じ単語，'JavaScript' は別の単語です．まぁでも最初は完全にネタでした．

使っていた技術とか

Python のコードは，OCaml に書きなおしたものと一緒に後日載せようと思っているので今回はざっくりとした自然言語で．

Cloudsearch2

DB の代わりに AWS の Cloudsearch2 というものを使っていました．細かいことは社長が書いてくれると思うのですが，クエリを投げたときにうまいこと自然言語処理っぽいことをやってくれるのでシソーラスとかその辺のアレがアレで採用しました．この辺のことはメンターさんからの助言が元になっているのでとても感謝しています．ご飯も美味しかったです．ごちそうさまでした．