作者別: Jun Mukai

SHA1衝突とバージョン管理システム

SHA1については https://www.slideshare.net/herumi/googlesha1 を読んでフムフムーと勉強していた。わかりやすい。

ところでwebkitがテスト用に入れてみたところ(ブラウザキャッシュをハッシュで管理しているから衝突時のテストをしたかったようだ)、subversion自体が発狂するという珍事件が発生したらしい: https://bugs.webkit.org/show_bug.cgi?id=168774&comment=c27#c27

これはひどいwって思うわけだけど、実際なんでこんなことが起こるんですかね? 誰か詳しい人に教えて欲しい。実際、

$ cd /tmp
$ mkdir svntest
$ cd svntest
$ mkdir repo
$ cd repo
$ svnadmin create .
$ cd ..
$ mkdir co1
$ cd co1
$ svn co file:///tmp/svntest/repo
Checked out revision 0.
$ cd repo
$ cp ~/shattered-* .
$ svn add shattered-*
A (bin) shattered-1.pdf
A (bin) shattered-2.pdf
$ svn commit -m 'test'
Adding (bin) shattered-1.pdf
Adding (bin) shattered-2.pdf
Transmitting file data ..done
Committing transaction...
Committed revision 1.
$ cd ../..
$ mkdir co2
$ cd co2
$ svn co file:///tmp/svntest/repo
A repo/shattered-1.pdf
svn: E200014: Checksum mismatch for '/tmp/svntest/co2/repo/shattered-2.pdf':
 expected: 5bd9d8cabc46041579a311230539b8d1
 actual: ee4aa52b139d925f8d8884402b0a750c
$ svn --version
svn, version 1.9.3 (r1718519)
 compiled Mar 14 2016, 07:39:01 on x86_64-pc-linux-gnu

などとなる。ここで”actual”は正しいSHA1ハッシュを計算できているので、なぜかサーバが提供するexpectedなハッシュが狂っているということになる。でもsvnadmin dumpすると正しいハッシュ値なんだよな。謎だ。

git

gitにおいてファイルコミットはgitオブジェクトを作ることに相当し、gitオブジェクトはざっくりいうとSHA1ハッシュ値で識別される。ので、同じような理由により衝突の懸念がある。

ただ実際には https://git-scm.com/book/en/v2/Git-Internals-Git-Objects で詳しく解説されているようにヘッダ情報(ファイル長などの情報)とファイルの中身で構成されている。のでファイルの中身のSHA1ハッシュが一緒でもヘッダが先頭についているため、オブジェクトのハッシュ値は異なったものになるはず。

もっとも↑の解説スライドを読む限り、同じ手法により同じ長さの2つの相異なるPDFファイルをコミットすることにより、同じハッシュ値を持つgitオブジェクトが生成することは可能という気がする。その場合、その2つのファイル自体の中身は今回と全然異なるものになる。ファイルの中身自体のSHA1ハッシュも同じでかつgitのハッシュ値も同じになるというのは、今回の話とは関係なく、遥かに難しい問題であるように思う。

そもそもgitではハッシュは識別にしか使っていないだろうから、その場合でもcloneしたら2つのファイルの中身が同じになってしまうという意味では異常だけども、エラーを引き起こすようなことはない気がするけれど。

Mercurial

Mercurialではハッシュ値はグローバルな名前空間ではない。ファイルごとにそれぞれ履歴データを持っていて履歴をハッシュで管理するスタイルになっている。したがってそもそも違うファイルで同じハッシュ値となっても根本的に問題ないはず。

じゃあ同じファイル内の変更履歴でハッシュ値が衝突するとどうなるかというと、これは確かに問題になるかもしれない。ただし、ハッシュ値の計算には親のハッシュ値等を含むヘッダ情報が使われるため、このアプローチが正しいとすると通用しない(ヘッダ部分が共通でないため)。ただこれがどのような問題を引き起こすのかはわからない。ともあれこんなに簡単に壊れるような構造にはなっていないように思われる。

他のバージョン管理システム

知らんし調べてないけど問題ないんじゃないかなあ。

ベイエリアのポケ丼

ランチにポケ丼(poke bowl)を食べた。

IMG_20170116_131648.jpg

それにしても最近シリコンバレー界隈では、poke barとかを名乗るポケ専門店があちこちに開店しているなあ……と思って検索して見つけたのが San Jose Mercury 紙の http://www.mercurynews.com/2016/09/13/bay-area-poke-not-pokemon-trend/ 。

やっぱりとにかく増えているらしくて、2015年初からの約2年で20店舗以上が開店しているのだそうだ。増えたもんな。

ほかにもいろんなトレンドが紹介されているんだけど、これってようするに、ハワイのもともとのポケにどんどんアレンジを加えて、この辺の人好みのテイストの料理に変質させていっている、ということなのね。 Go Fish Poke Bar という店舗を作ったジェローム・イトウさんがポケにアメリカン・スシのテイストを導入したらしく、これが受けたのが一つの流れになっているのでは、とぼくは読んだ。

そもそもポケっていうのはハワイの料理で、(ぼくの理解では)角に切った生魚の切り身を醤油とかのソースでマリネしたものだ。ヅケとかに近い。ハワイとかではスーパーの惣菜でよく売ってる(ベイエリアにもわりとある)。でもいまベイエリアで流行ってるpoke barのはけっこういろいろ違う気がする。ハワイのことはよく知らないけれど。

いまベイエリアの典型的な poke というと、まず丼メニューになっていてご飯のうえにのっている(これはまあハワイにもあると思う)。魚はソースに漬けられてなくてナマのままになってて、魚を何種類か選んで、ソースもいくつかある中から選ぶと、お店の人がその場で和えてくれる。で、いくつかあるトッピングも選んで全部をあわせて完成。トッピングは店によっていろいろだけど、ガーリックとかネギとかカニとか、あとトビコ(マサゴ)とかが典型的。ご飯も玄米か白米か、みたいなので選べるし、ソースも醤油ベースなものからスパイシーなものから各種ある。でもまあ概ねアジアンテイスト。

で、これってなんか、ポケと海鮮丼(あるいはちらし寿司?)の中間みたいな、不思議なアレンジの食べ物だなって思ってる。なかなか美味しいし、コッテリにもあっさりにもできる。トッピングとかいろいろ選べるあたりはこの辺の人の好みに合っている。まあよくできてますよ。

これだけ新規開店したら過当競争化してクオリティが下がってやばい店も増える気もするけど、今のところ味は一定で安定している(逆に、どこの店が特別に美味い、とかはあまりなくて、どこでもまあまあ同じような感じ)。アメリカンスシの店みたいな感じで、このまま定着していくんだろうか。

Arrival、メッセージ、あるいはあなたの人生の物語

テッド・チャンの傑作短編「あなたの人生の物語」映画化、見てきましたよ。タイトルArrival、邦題は『メッセージ』だったっけ?

IMG_20161120_165339.jpg

とうぜんみなさんも原作は既読だと思いますが、結論から言うとこれはよい映画化の成功例。なにもかも原作通りということでもなく、しかし原作の基本的な方向性とエッセンスをそのまま、うまく映画のかたちに構成している。これ映画にしてどうするの?と思ってたけれど、なんとびっくり、あれもこれもある。

見終わった後、これは再読せねばと思い読み返してみたところ、基本的なエッセンスだけじゃなくてかなりいろいろ原作のネタを拾って映画として再構成していたなあ、ということがわかって再度感心。カンガルーの語源の俗説とか、そういう小ネタもきちんと原作に出てきたものを拾っているのかーと思ったりしました。

ちょっと意外だったのは変分原理の話が(たぶん)出てこなかったところ。というかやはり、映画では細かい設定について一つ一つ説明したりはできないわけで、結果的にあれとか超能力めいてしまっているのだけれど……まあこれはこれでよいのかもなあ。

まあ俺みたいな小うるさい原作厨でもこれは良かったですよ。ヒットするような作品ではないと思いますが、ぼくの友達とかには当然おすすめ。個人的には実はちょっと序盤はちょっと展開がかったるいので眠くなってしまいましたが、最終的には楽しめる作品になっていましたので、飽きっぽい人間の皆様も頑張って起きてください。


それにしてもタイトルのArrival、ちょっと意味わからないのですが。邦題の『メッセージ』のほうがなんとなく意味が通じる気もしないでもないこともないでもない。

 

『シン・ゴジラ』北米初日に観た

img_20161011_191255

10月11日から一週間だけ北米で上映中の『シン・ゴジラ』をようやく観ました。

ともかく、満足。大満足。よかったよかった。観られてよかった。

内容や感想はともかく周辺状況を記録しておくと。

私のいったところはモール内の映画館でしたが、客の入りは4割ぐらいかな……。平日の夜だし、まあこんなもんじゃね?という気がします。日本人はぼくら以外いたのかなあ、普通に地元の人々が大多数でした。もちろん、地元といってもそういうのが好きなコアな人々が見に来たというところでしょう。

意外とアメリカネタのセリフがありましたが、そのたびに客席がいちいちウケていたのも面白かった。客層が、日本のものが好きな人々だからってのはあるのでしょうけれど。もともとのセリフでは「あちらさん」とか婉曲表現だったものが字幕ではほぼそのものズバリ The US とか America とか大変直裁的表現になっていたのもあったのがまたちょっと面白い、というのがあるかもしれないですが。

北米では不評、というニュースをいくつか目にしますが、現時点で Rotten Tomatoes は 78%、 IMdb では10点満点で7.7というスコアは決して悪いものではない……というかそれなりに高い評価だと言えると思います。もちろん今スコアをつけているのは相当コアなマニアたちなので、これから点数がどう推移していくかはわかりませんが、不評ということではないのでは。……とはいえ北米ではわずか一週間のみの公開、しかも上映は各館一日一回だけ、というスケジュールなので、これはまあ届くべきマニアに届けることを考えたものであるのもまた間違いないことでしょう。

てなわけで、当然ながら北米の配信はマニア向けでありまして、その当初の目論見どおりごく一部のマニアに届く感じになっていたということではないかなと思います。

はーそれにしてもこれでようやくネットの情報に触れることができるな。

TypeScriptのStructural Subtypingの話2

前回の記事ではNode.JSのCモジュールなどTypeScriptの世界だけで完結しない話について型システムがどう扱うか、ということを書いた。

今回は近いところでちょっと違う話。

前回の話を考えているとき、TypeScript自体のソースコードをちょっと調べていて気づいたパターンがある。それはたとえば https://github.com/Microsoft/TypeScript/blob/master/src/compiler/types.ts#L13 などに特有なのだが、 brand という特殊なフィールドを持つ型が何箇所かで定義されている。

この例では

export type Path = string & { __pathBrand: any };

という定義で、これはPathという型を定義しているのだけど、実質的にはPathはstring(文字列)だということを言っている。Node.JSではパスに対しては文字列が使われているという現状からそのようになっている。

そしてTypeScriptはインタフェースさえ合っていれば同じように引数に渡せるため、この型システムではPathとstringを区別することはできない(なぜなら同じ型だから!)。引数の順番を間違えたとか、そういうケアレスミスによって間違った文字列が渡されても間違いが検出できない。

そこで __pathBrand というフィールドを Path 型の定義に追加している。ただの文字列にはこのフィールドはない。またPath型を返す関数は文字列をType assertion (キャストのようなもの)によって変換しているため、実際のコードには __pathBrand は出現しない。

これによって全く同じ型の値をそのまま扱いつつ、些細なミスをコンパイラが検出してくれるようになる。

似たような仕組みは構文木にも現れていて、特定の構文要素をグルーピングするのにこのようなbrandのようなものを使い、間違ったものを渡すようなケアレスミスを防いでいる。

もちろんこのテクニックは完全ではなくて、やろうと思えば適当に __pathBrand のようなフィールドを追加してやることでチェックを迂回できる。でもいかにも意味のありげな名前だし、コメントにも明記されている(vscodeなどではこういうコメントも付随して定義されているし)。そして何よりこのテクニックは正確に検証するというよりはケアレスミスを減らすためのテクニックなので、意図的に回避したい人を止めるものではない、っていうところだろう。


こういうことをやりたければ、ふつうの関数型言語であれば新しい型を定義したり、 phantom type を使ったりするところだと思う。

Go言語であれば普通に新しい型を定義して元の型と互換性をなくすといったところかな。

こんな具合に「構造上は全く同じだが何らかの事情で処理系上は区別したい型」というのは、現実のプログラミングでは意外とほしくなることがあり、インタフェースの一致だけに限定したシステムだけではこういう区別はできない。そういう事情でTypeScriptにはこんなテクニックが使われている、という話でした。

Ruby 3ではこういう問題をどう扱うのかな、というのは気になっています。

TypeScriptのStructural subtypingがうまくいかない場合

少し前にTypeScriptを勉強していて、この型システムだと実装を隠蔽した型というものをうまく表現できてないな、と思ったことがあったのでメモしておく。

TypeScriptはJavaScriptに型情報を与えられるように拡張した(それ以外にもいろいろ拡張のある)言語だけど、JSらしいゆるさを残した仕様になっていて、基本的には構造の同じものは全て受け入れるようになっている(Structural subtypingという)。

interfaceという定義がGoのinterfaceのような感じになっていて、継承関係は全くなくても同じインタフェースのオブジェクト(ようは特定のフィールドを持つオブジェクト)であればコンパイラは通してくれる。

interface Foo {
  foo: string;
}

function foo(f: Foo) {
  console.log(f.foo);
}

foo({foo: 'foo'});  // OK
foo({foo: 1});      // NG: foo is not string
foo({bar: 'foo'});  // NG: interface mismatch

で、世の中には実装を隠蔽したいことがあるのと、TypeScriptだけではうまく完結しないものがある。ある種のファクトリーから生成されるオブジェクトだけを受け入れたい、とか。Node.JSのCモジュールが関連するオブジェクトなので内部実装がJS/TSでは表現不可能だとか。

こういう状況をTypeScriptではうまく表現できないように思える。

内部的なデータ構造は表現できないので、

interface Foo {
}

のように書くと、Foo型の変数にはおおむねどんな値でも代入できてしまう(指定されている構造に一致するため)。そこで本当には存在しないけれども、内部的に何らかのものを持っていますよ、ということを意味する適当なフィールドを入れてみる。

interface Foo {
  _impl: ...
}

だがこの場合でも、_implの型はなんであれ、その値を適当に作って _impl に入れることで簡単にこのインタフェースを実現できてしまう。

まあ実用上はコメントでも書いておけばよいのだろうけれど……。

なお、TypeScriptにはクラスもあるが、クラスもインタフェースが一致していれば通すためこの目的には合致しない。

class Foo {
  foo() {
    console.log('foo');
  }
}

function fooer(f: Foo) {
  f.foo();
}

class Bar {
  foo() {
    console.log('bar');
  }
}

fooer(new Foo());  // No problem
fooer(new Bar());  // OK, Bar is compatible with Foo

ただ、プライベートなフィールドを勝手に設定すると、この問題は解消できる。

class Foo {
  private _impl: any;
  foo() {
    console.log('foo');
  }
}

function fooer(f: Foo) {
  f.foo();
}

class Bar {
  private _impl: any;
  foo() {
    console.log('bar');
  }
}

fooer(new Foo());  // No problem
fooer(new Bar());  // NG

これはTypeScriptではprivateなフィールドは互換でないと判断されるからだ。

ただしこの手法の場合でも、Fooに相当するクラスが(TypeScriptレベルでは)実在してしまうため、通常のクラス操作であるnewもできるし、Fooを継承したサブクラスも定義できる。Cモジュールなどから得られるデータ型はたいてい何らかのファクトリー関数から生成されるので、データ構造がうまくあわなくなることがある。けっきょく、こういう状況をTypeScriptで表現するのは難しい、ということだ。


……という理解だったのだけど、この記事の草稿を書いてから今に至るまでにTypeScript 2.0がリリースされて、この問題は解決された。

どういうことかというと、TypeScript 2.0からprivateなconstructorを作れるようになった。これにより、外からnewできないクラスというものが定義できるようになった。そしてprivateなconstructorを持つクラスは継承できないとされた。

class Foo {
  private foo: any;
  private constructor() {}
  static create(): Foo { return new Foo(); }
}

function foo(f: Foo) {
  console.log(f);
}

foo(Foo.create()); // OK
foo(new Foo());    // NG: private constructor
foo({foo: 1});     // NG: 'foo' should be private

// NG: cannot extend a class with private constructor.
class Bar extends Foo {}

というわけで、こういうクラス宣言により、うえで書いたような状況はうまく表現できるようになった。現実にはd.tsファイルにこういう定義を書いておき、内部実装はJSとCモジュールに適宜実装されることになる。

それにしてもプライベートなコンストラクタというのは、コンパイルされるとどうなるのだろうか。クラス名が手に入ればJSレベルではnewできるんだけど…………と思ったのだけど、どうもTypeScriptコンパイラは可視性の情報を落とすだけなようなので、JSからは普通にnewできるクラスに見えるらしい。まあそりゃそっか、という話であるし、それでいいよなという話でもあるのだった。

guildっぽい単語

http://rebuild.fm/158/ を聞いてて、 guild でも別にいいし、この辺の単語は一通り検討されてる気がするけれどなんとなく思いついたものを書いてみる。


Rubyの “guild” についてはどういうものかというのは http://www.atdot.net/~ko1/activities/2016_rubykaigi.pdf に書いてあるが、互いに参照関係にないオブジェクトのグループ分けを行うことで、異なる「ギルド」に所属するスレッド同士は独立して(パラレルに)動作できる、という仕組み。

パラレル・コンカレント系の用語なのでスレッドナントカ、とか系の単語がいいのかも、と思ったけれど、話を聞いた感じではどちらかというと概念的にはオブジェクトの所属関係を意味するものなのか、という印象を受けた。

そうすると集団を意味する単語系のtribe、clan、caravan、群れ系のhorde、troop、bandなど、あるいはregiment(連隊)、battalion(大隊)、company(中隊)などの単語はどうかなぁ。

あとは所属関係を地理的なアナロジーでとらえて、continent、planet、universe、world、galaxyとかみたいな単語とか。

あんまりいい案ではないかな……。まあとりあえずそんなかんじ。

ところでスレッドをたばねる単語としたら日本的には「板」(board)なのではないでしょうか、などと言ってみるテスト。

 

tensorflowの型付け

http://shinh.skr.jp/m/?date=20160912#p01

はいその通りです。というか前者の意味なんだとすると、それはなんというかその、一般的に動的言語は全部ダメという結論になってしまうように思うのですけどどうでしょうか。あと変数名typoはJSなら “use strict” で防げたりする、といったこともあるので、型というよりは処理系や言語仕様の話じゃないかなぁという気も。


で、tensorのサイズの型付けなんですが、理論的には依存型(dependent types)で解決済の話題という気もする。確かリストのサイズを型レベルで覚えておいて、空リストへのheadをコンパイルエラーにする話とかあったよなー……と思って検索したら https://www.schoolofhaskell.com/user/konn/prove-your-haskell-for-great-safety/dependent-types-in-haskell みたいな話はあります。

ただまあ理論的な結果があるといっても、現実の問題に実際に適用してみたらいろいろな細かい問題はおこりうるだろうとは思うんですよね。convolutionみたいな引数はけっこうややこしいだろうし、embedded lookupみたいなので値域とサイズが入れ替わる場合とかもあるし。

あと自然言語処理みたいな応用例だと数万次元とかあるわけですが、サイズをナイーブにチャーチ数でエンコードしたらパフォーマンス的に大丈夫なんだろうか、とか。

まあそれなりにやってみたら面白いのでは、というのが素人考えですが、理論的には大して面白くないかもしれない。

ドラマ『シリコンバレー』シーズン3

HBOのテレビドラマシリーズ Silicon Valley のシーズン3がGoogle Playに来てたので観た。今回も面白かった!

シリコンバレーの大企業Hooliから飛び出したリチャード・ヘンドリクスが創業したスタートアップ、Pied Piperの面々の活躍(?)を描いたコメディシリーズのシーズン3。Hooliとの訴訟を乗り越えたものの最後の最後でいきなりの解任騒ぎとなったシーズン2のラストでしたが、そこからそのままつながったシーズン3も見どころは多く、いろんな小ネタがてんこ盛り。

ネタ的には、主人公のリチャード・ヘンドリクスがタブ派であることを明言し、せっかくできたfacebook社員の彼女とタブ・スペース論争で喧嘩して別れるあたりがおかしいし、冒頭でベンダーのエンジニアがコーディング規約に従ってくれない……という話からの展開はまあ見事。ただ一番面白かったのは Pipey。あれは声を上げて笑ったし本当になんというか、完成度が高い……。

それにしても、ギークネタの使い方もうまいですけど、毎回毎回いろんな小ネタをはさみつつ、各回でもきちんと起承転結がついていながら、思わぬ伏線が回収されて綺麗な結末に着地していく流れが本当に見事だなと。シーズン2の判決シーンも好きなんだけど、シーズン3のラストも謎の感動がありました。


ところでオープニングも毎シーズン微妙に細かく変わっていていろいろ芸コマ(YouTube)。シーズン2で出現したUberのバルーンは脇に出てきたLyftのバルーンとぶつかってるし、ドローンが飛び交ってるし、Yahoo!のところに阿里巴巴があるし、Googleの上にAlphabetの看板が立ってるし。

Screenshot 2016-09-06 at 00.08.53

比較のためにシーズン1の動画を見てたらsgiが崩れてGoogleになったりNetscapeがChromeになったりMyspaceがあったりNapsterのバルーンがしぼんで落ちたり、とにかく芸コマですし、ちゃんと時流を合わせててすごいなぁ。

Screenshot 2016-09-06 at 00.11.44.png

手もちのChromebookにもPlay Storeが来たので

手元のChromebook Pixel2にもGoogle Play Storeが来ていて大半のアンドロイドアプリが利用可能になってました。

喜び勇んでいろいろと入れてみた。

Screenshot 2016-09-01 at 20.27.39

しかしまぁなんだな。思ったよりも「これを入れねば!」というアプリってあんまりないんだよなぁ。Kindleはクラウドリーダーはいろいろしょぼいので良いかも、というのとあとはSkypeぐらい? てかまあSkypeも、もう何年も使っておらず、そっちで繋がってる人々はそんなにいないし。

微妙にウェブ対応がしょぼいやつで、モバイルアプリのほうが良いやつとかもあるんだろうけど、あんまりデスクトップで使うものというのもないものですね。アンドロイドアプリはモバイルコンテキストで使うものが多いしな。

あとはゲームとかなのかなぁ。

とりあえずFirefox(モバイル)を入れて「おーChromeOSでFirefoxがうごいた!」って遊びをしている……