近&況

Recent Posts
Edit

インドカレー屋のレジの横に置いてあるやつ買った

2017-01-23

インドカレー屋のレジの横に置いてある甘いやつが好きなんだけど、ネットで買えるっぽいので注文してみた。ジップロック的なものに入ってるので便利。


あれの正体はフェンネルシードというハーブに砂糖をかけたもので、消化促進に効果があるらしい。食べてみると心なしか胃がすっきりするような気がするが、そうするとなんかもうちょっと食べられる気がしてお菓子とか食べてしまうので、プラマイゼロかもしれない。

Edit

プログラミング言語「PPAP」を作りました

2017-01-06

プログラミング言語「PPAP」を作りました。

I have 80 Pen
I have 65 Apple

Uh! Put-Pen
Uh! Put-Pen
Uh! Put-Apple
Uh! Put-Pen

実行するとPPAPと出力されます。

% ppap exec ppap.ppap
PPAP

ソースコード

https://github.com/yhara/ppap-lang

FizzBuzzも書けます。

宣伝

このような奇妙なプログラミング言語に興味がある人にぴったりな書籍が存在します。

今ならマナティというマイナビのIT系電子書籍ストアから購入すると割引になっており、2,041円でPDFが手に入ります。1月10日までです。これに合わせようと思ったのに年始になってしまった。

言語仕様

「I have」はレジスタの宣言です。以下はPenというレジスタを用意し、初期値として50を代入します。50個でもPenなのは仕様です(Pensでは動かない)。

I have 50 Pen

PPAP言語にはさまざまなコマンドがあります。コマンドを実行する場合は「Uh!」と気合を入れる必要があります。以下はレジスタPenの中身を数値として出力します。

Uh! Print-Pen

これはラベルです。ジャンプ命令の飛び先として使用します。

Apple-Pen

他にも四則演算、比較などの命令があります。詳細はREADMEを参照してください。レジスタ名・コマンド名には必ず「p」を含めるという仕様にしたため、「>」はありますが「<」がありません。何か良い英単語をご存知でしたらgithub issuesTwitter等で教えてください。割り算の余りを取る命令(mod,「%」)も欲しいですね。

あわせて読みたい

Rubyの作者、まつもとゆきひろ氏の新作。新しい言語「Streem」を実装するという雑誌連載をまとめたもの。

Quineや「絵みたいなソースコード」といったヤバいプログラミングに関する本。

Edit

マクロ展開時に副作用を起こすとどうなるか

2016-12-31

R7RSのマクロシステムはsyntax-rulesだけだが、R6RSにあったsyntax-caseや、いくつかの処理系が実装しているexplicit-renaming, implicit-renamingといったマクロシステムでは、マクロ展開時に任意の式が書ける。

では、マクロ展開時にdisplayを使って文字列を出力した場合、それはどのタイミングで評価されるのだろうか?特にインタプリタじゃなくてコンパイラの場合は?

Chicken Scheme

ということで適当なSchemeコンパイラを用意する。Macだとbrew install chickenでChiken Schemeが入る。マクロシステムはexplicit-renamingがあるようなのでそれを使う。

(define-syntax foo
  (er-macro-transformer
    (lambda (expr rename id=?)
      (display "hello")
      (cadr expr))))

(display (foo 1234))

このようにしたとき、「hello」はどのタイミングで出力されるだろうか?

実行してみる

% csc compile-time.scm
hello
% ./compile-time
1234

ということで、コンパイル時に出力されることが分かった。

本来の使い方

やっておいて何だけど、任意の式が書けるというのは別に文字列を出力するためではない。Racketのマニュアルを見ると、「マクロの使い方を間違えたときにより丁寧なエラーメッセージを出せる」というメリットが挙げられている。あとは動的に関数名を組み立てるとか?

(define-syntax define-getter
  (er-macro-transformer
    (lambda (expr rename id=?)
      (let* ((name (symbol->string (cadr expr)))
             (str (string-append "get-" name))
             (sym (string->symbol str)))
        `(define (,sym) '("get" ,(cadr expr)))))))

(define-getter a)   ; (define (get-a) '("get" a))に展開される
(write (get-a))
;=> ("get" a)

追記:マクロ展開時に呼べる関数について

副作用が起こせるといっても、任意の関数が呼べるとは限らないようだ。例えばRacketではbegin-for-syntaxなどでコンパイル時に使う関数だと明示する必要がある。Chickenでも以下はエラーになった。ふーむ。

(define (bar)
  (display "hello"))

(define-syntax foo
  (er-macro-transformer
    (lambda (expr rename id=?)
      (bar)
      (cadr expr))))

(display (foo 1234))
% csc compile-time.scm

Error: during expansion of (foo ...) - unbound variable: bar

        Call history:

        <syntax>          (##core#begin (display (foo 1234)))
        <syntax>          (display (foo 1234))
        <syntax>          (foo 1234)
        <eval>    (bar) <--
Edit

2016年に聴いた音楽

2016-12-31

近年は音楽を聞くときはほぼMacのiTunesなので、iTunesを開けば何聴いてたか分かって便利。最近はApple Musicとか定額制のサービスも出てるけど、同じアルバムを何回も聞くタイプなので利用していない。

リンク先はYoutubeとかSoundCloudとかBandcampとか、何かしら試聴できるやつにしています。

特に良かった/よく聴いたもの

ロック

エレクトロニック

ヒップホップ

ジャズ・ポップス・その他

Edit

A collision between Yard and FactoryGirl

2016-12-27

Today I encountered a curious error on running tests of a Rails app.

(snip)/gems/yard-0.8.7.6/lib/yard/globals.rb:16:in `log': wrong number of arguments (given 1, expected 0) (ArgumentError)

Solution

I did not indend to use yard while testing. By checking Gemfile.lock, I found pry-doc was the only gem depends on yard. The error was removed by fixing Gemfile to exclude pry-doc from the "test" group.

gem "pry-doc", group: "development"

But why?

FactoryGirl uses method_missing to collect model attributes. In the following example, name and log should result in an invocation of method_missing.

FactoryGirl.define do
  factory :server, class: Server do
    name "server1"
    log "working fine."
  end
end

However, when Yard is loaded, log is treated as an invocation of Kernel#log defined in lib/yard/globals.rb. This is how the ArgumentError is raised.

Points

  1. It is good to check that your Gemfile does not load unnecessary library.
  2. You should be careful when defining a method on the toplevel -- it may result in an unexpected behavior.
  3. method_missing makes your DSL compact but a little fragile. This conflict did not happen if FactoryGirl used a particular method (say, attr) to declare model attributes (and personally I prefer this style because it is clear that which identifier is code and which is data).
FactoryGirl.define do
  factory :server, class: Server do
    attr :name, "server1"
    attr :log, "working fine."
  end
end
Edit

BiwaSchemeのためにCPS(継続渡し形式)でマージソートを実装した話

2016-12-25

本記事は言語実装 Advent Calendar 2016の最終日の記事です。話題が多岐に渡っていて楽しいアドベントカレンダーでしたね。前日はEgisonのリーマン幾何学用記法の話でした。

BiwaSchemeは筆者が作っているJavaScriptによるScheme実装です。先月の話ですが、list-sortという関数を修正し、比較に使うScheme関数を受け取れるように改善しました。BiwaSchemeは中間言語方式(VM方式)かつライブラリを全てJSで実装するという方針になっているため、実装に少し工夫が必要でした。本稿ではそのことについて解説します。

中間言語方式

JavaScriptでScheme処理系を実装する場合、いくつかの方針が考えられます。

  1. インタプリタ方式 (S式を一つずつ読み、評価する)
  2. コンパイラ方式 (プログラム全体を等価なJavaScriptに変換する
  3. 中間言語方式 (プログラムを中間言語に変換し、それを実行するもの(=VM)を用意する)

BiwaSchemeは3.の中間言語方式で実装されています。現代では2.のコンパイラ方式でも十分な速度が出ると思いますが、開発を始めた2008年当時はJavaScriptの処理性能が今ほど良くなかったため、VM方式のほうが性能的メリットがありました。あとは参考にした論文(3imp)がそうなっていたからという理由もあります。

例えば(+ 1 2)というSchemeプログラムは、以下のような中間言語(IL, Intermediate Language)にコンパイルされます。

[frame
   [constant 2
   [argument
   [constant 1
   [argument
   [constant 2
   [argument
   [refer-global "+"
   [apply]]]]]]]]
[halt]]

どのようなILが生成されるかはbiwascheme.orgからオンラインで確認できます。各命令の説明はここです。

ライブラリ関数の呼び出し

上記のようなIL列をループでぐるぐる回して、各命令を順番に実行していくというのがVMの基本的な動作です。しかし場合によっては、命令の実行中に生のJavaScript関数を実行することもあります。

例えばBiwaSchemeではライブラリ関数(上記で言えば、+)は全てJavaScriptで実装しているので、(+ 1 2)というプログラムを実行する場合、足し算を行うところだけJavaScriptの関数が走ります。

シーケンス図

JS側からSchemeのコードを実行したい場合

上図はVMループから生のJavaScript関数を呼び出す例でしたが、場合によってはライブラリ関数からさらにScheme関数を実行したいことがあります。例えば(map f '(1 2 3))ようにしてリストをmapする場合、ライブラリ関数mapの中からSchemeの関数fを呼ぶことになります。

さてこれをどのように実装したら良いでしょうか?例えばfを実行するためにVMループをもう一つ起動するのはどうでしょうか。この方法は単純ですが、長いリストをmapするとVMループがどんどん増えていってしまうという問題があります。

BiwaSchemeではこのような場合、ライブラリ関数から特殊な値(BiwaScheme.Callのインスタンス)を返します。Callオブジェクトはライブラリ関数からVMループに向けて「このScheme関数をこの引数で呼んでほしい」という依頼を示すもので、以下のものが入っています。

after関数は、Scheme関数の呼び出し後に何らかの処理が必要な場合に使います。例えばmapの場合は全ての要素を処理するまで繰り返しScheme関数を呼び出す必要があるので、Callを返す→afterが呼ばれる→Callを返す→…という感じでループしていくことになります(下図)。

シーケンス図

CPS(継続渡し形式)

CPSという言葉を使えば、ここまでの話は要するに「BiwaSchemeのmapはCPS形式で実装されている」と言えます。CPS(Continuation Passing Style, 継続渡し形式)は「残りの計算」を関数として持ち回る形式です。mapの場合はCallオブジェクトのafterによって残りの計算を渡しています。

list-sort

mapの他にもvector-map, for-each, findなど、たくさんのライブラリ関数がCallオブジェクトを使って実装されています。ところが、R6RSのライブラリ関数の中にCallオブジェクトでは実装しづらいものがありました。それがlist-sort(およびvector-sort, vector-sort!)です。

list-sortはリストと比較関数を受け取り、安定ソートした結果を返します。これをCallオブジェクトで実装するには、何らかのソートアルゴリズムをCPSで実装する必要があります。mapの場合は要素を順番にScheme関数に渡すだけなので簡単ですが、ソートとなるとソート途中の状態を保持したまま適切にCallオブジェクトを呼び出す必要があります。

これを解決する方法として、頑張るという方法があります。ソートのアルゴリズムには有名なものがいくつかありますが、クイックソートは最悪計算量が良くない、ヒープソートは安定ソートでないという特徴があるので今回はマージソートを選択しました。マージソートは再帰的なアルゴリズムなのでCPSにするのは大変ですが、頑張ることによって実装ができます。できたものが以下です。

mergeSortがソートを行う関数で、mergeSort_およびmerge_は補助関数です。list-sort等はこのmergeSortを使って定義されています。

最初からCPSでソートを書くのは大変なので、まずは普通に再帰で書いたものを用意し、それをCPSに直すのが良いと思います。再帰の場合はホスト言語(BiwaSchemeの場合、JavaScript処理系)が関数の呼び出し履歴を管理してくれますが、CPSに直す際は処理系が持っていた状態を自分でハンドリングする必要があります。上記のコードではstackという変数がそれで、stack.pushが再帰の呼び出し、stack.popが再帰呼び出しからのreturnに対応しています。

おわりに

本稿ではlist-sortのためにCPSでマージソートを書いたという話をしました。話としてはそれだけなんですが、そこまでのコンテキストを補完すると長くなりますね。

ちなみにLisp処理系を実装する場合、ライブラリ関数もLispで書いてしまうという戦略も考えられます (というかそうする人の方が多いかも?)。この場合はlist-sortもLispで書くので今回のような苦労はないと思います。最低限必要な部分だけをホスト言語で書いて、ライブラリ等はその上に乗せるわけですね。BiwaSchemeの場合はそれをやるとランタイムがすごく大きくなるので避けていますが。

Edit

Rubyで競技プログラミング

2016-12-25

この記事はRuby Advent Calendar 2016の最終日の記事です。

発端

秋に行われたRubyKaigi 2016のあとのAfter partyで、以下のような発表をしました。

内容は、会社の同僚と一緒にRubyでAtCoderをやっているという話でした。AtCoderはオンラインで競技プログラミングができるサイトで、Rubyを含めたさまざまな言語で参加することができ、過去問についても解答を受け付けているため好きなときにチャレンジすることができます。

競技プログラミングではC, C++, C#, Javaといった言語が主流なので、Rubyでは速度が足らないのではないか?と思われるかもしれません。実際、AtCoderでは2秒の制限時間に対し、入力データが10万行を超えることもあります。それでも、適切なアルゴリズムを使うことで、9月時点でチャレンジしていた範囲(ABC035〜041)はRubyでもちゃんとクリア(AC)することができました。

…ただ一問を除いては。

ABC037 D 経路

問題の一問がこれです。数字が敷き詰められた盤面を「数字が大きくなっていくように歩く」とき、何通りの歩き方があるかという問題です。(今回は実行速度の話なので具体的な解法については触れませんが、ネタバレが気になる場合は以下を読む前に一度チャレンジしてみて下さい)

この問題だけがどうしても2秒以内に解けませんでした。TLE(Time Limit Error)だけでなくRE(Runtime Error)が出ていることから、stack level too deepが出ていることが予想されます。アルゴリズムは再帰呼び出しを使ったもので、盤面は最大で1000×1000マスなので、デフォルトのスタックサイズをオーバーしてしまうことは十分に考えられます。

Rubyとスタックサイズ

RubyKaigiでこの件についてささださんに尋ねてみたところ、「スタックサイズは環境変数経由で設定することができる」という情報を頂きました。

ただし残念ながら、環境変数を使わずにスクリプト内からこれを設定する方法はまだないとのことでした(理由は「特に要望がなかったから」)。AtCoderには投稿したプログラムの環境変数をするようなインターフェイスはないので、この方法は使えなさそうです。

と思いきや…

冒頭のスライドを見た@_simanmanさんから、クリアできたという報告が!

どうやら、以下のようにKernel#execでRubyインタプリタをもう一度起動させることで、環境変数を指定しているようです。そんなことをしたら2秒制限にひっかかりそうですが、1991msというぎりぎりのタイムでクリアできています。

if !ENV['RUBY_THREAD_VM_STACK_SIZE']
  exec({'RUBY_THREAD_VM_STACK_SIZE'=>'1000000000'}, '/usr/bin/ruby', $0)
...

どうすれば良かったのか?

クリアできることが分かったので、自分が投稿したプログラムと比較して、どこが悪かったのかを調べてみました。

1. Bignumを経由する箇所があった

まず単純なミスとして、問題文の「10^9+7で割った余りを求めてください」という一節が実装できていませんでした。このため盤面が大きい場合に間違った答えが出る上に、答えが出るまでにとても時間がかかるようになっていました。

Rubyでは四則演算の結果が大きい数になると、自動的にFixnumからBignumへ結果が拡張されるようになっています。これはとても便利な機能ですが、Bignumの計算はFixnumよりも低速です。今回は結果の総数ではなく10^9+7で割った余りだけ分かれば良いので、計算の途中でこまめに10^9+7で割るようにすれば、Bignumを経由しなくて済みます。

2. スタックを浅くする必要があった

AtCoderでは時間制限の他に、メモリ量の制限もあります。ABC037 D問題では使えるメモリは256MBまでで、これを超えるとMLE(Memory Limit Error)というエラーになります。

いろいろ試してみた結果、筆者のもとのプログラムだとスタック制限を回避できたとしてもMLEで止まってしまうことが分かりました。問題の箇所はここです。

def calc(pos)
  ret = 1
  DIRS.each do |d|
    if MAP[pos] < MAP[pos+d]
      plus = ANS[pos+d] || calc(pos+d)   # 再帰呼出し
      ...

このDIRS.eachをwhileに置き換えると、無事Acceptedになります

def calc(pos)
  ret = 1
  i = 0
  v = MAP[pos]
  while i < 4
    d = DIRS[i]
    if v < MAP[pos+d]
      plus = ANS[pos+d] || calc(pos+d)
      ...

@_simanmanさんのプログラムではwhileの代わりにループアンローリングを使っています。ループアンローリングは主に高速化のためにループをべた書きに展開するという手法で、例えば上のwhileを展開すると以下のようになります。

def calc(pos)
  ret = 1

  if MAP[pos] < MAP[pos+1]
    plus = ANS[pos+1] || calc(pos+1); ret += plus
  end
  if MAP[pos] < MAP[pos-1]
    plus = ANS[pos-1] || calc(pos-1); ret += plus
  end
  if MAP[pos] < MAP[pos+W]
    plus = ANS[pos+W] || calc(pos+W); ret += plus
  end
  if MAP[pos] < MAP[pos-W]
    plus = ANS[pos-W] || calc(pos-W); ret += plus
  end

まとめ

今回は以上です。一見どうしようもなさそうな状況でも、意外な方法で回避できるというのが面白かったです。

Edit

Opalでゲームを作るには(opal-phaser)

2016-12-21

この記事はOpal Advent Calendar 2016Ruby Game Developing Advent Calendar 2016の21日目の記事です。

OpalはRubyスクリプトをJavaScriptに変換してくれる処理系です。ということは、Opalを使えばRubyを使ってブラウザで動くゲームが作れるはずです。

opal-phaser

opal-phaserはPhaserというブラウザゲーム用ライブラリをOpalから使えるようにしたものです。今回はこれを触ってみたいと思います。

サンプルを動かしてみる

PhaserのサンプルをOpalに移植したものがあるみたいなので、とりあえず動かしてみましょう。READMEに書いてある通り、git cloneしてbundle installします。

$ git clone https://github.com/orbitalimpact/opal-phaser-examples
$ cd opal-phaser-examples
$ bundle install

そのあと、適当なサンプルのディレクトリに移動してbundle exec rackupし、http://localhost:9292/ を開きます。

$ cd examples/basics/click_on_image/
$ bundle exec rackup

実行結果です。自分が何をしようとしていたのか一瞬分からなくなりましたが、opal-phaserのサンプルを動かしていたのでした。画像をクリックするとクリックした回数が画面に表示されます。とりあえず動いているようで良かったです。

実行結果

他のサンプルも俄然、気になってきましたが、ここから先は自分の目で確かめてほしい。サブディレクトリがたくさんありますが、config.ruで検索すればサンプルだけ列挙できます。

% find . -name config.ru
./examples/animation/animation_events/config.ru
./examples/animation/change_frame/config.ru
./examples/animation/change_texture_on_click/config.ru
./examples/animation/destroy_animation/config.ru
./examples/animation/dynamic_animation/config.ru
./examples/animation/group_creation/config.ru
./examples/animation/load_texture/config.ru
./examples/animation/looped_animation/config.ru
./examples/animation/multiple_anims/config.ru
./examples/basics/click_on_an_image/config.ru
./examples/basics/image_follow_input/config.ru
./examples/basics/load_an_animation/config.ru
./examples/basics/load_an_image/config.ru
./examples/basics/move_an_image/config.ru
./examples/basics/render_text/config.ru
./examples/basics/tween_an_image/config.ru
./examples/bitmap_data/alpha_mask/config.ru
./examples/sprites/dynamic-crop/config.ru

また、phaser.js本体のExampleはもっとたくさんあるようです。

サンプルを読む

先ほどのbasics/click_on_image/のソースを見てみましょう。まず、index.htmlです。

<head>
    <title>Click On An Image</title>
    <script src="//cdn.jsdelivr.net/phaser/2.4.4/phaser.js"></script>
    <script src="/assets/main.js"></script>
</head>

phaser.jsをCDNから読み込んでいます。/assets/main.jsは、同ディレクトリのmain.rbがOpalによってコンパイルされるので、それを読み込んでいます。bodyタグの方も見てみましょう。

    <span id="title">click on an image</span>
    <script>
      Opal.load("main");
    </script>
    <div id="example"></div>

このscriptタグはOpalでコンパイルしたJSを実行開始する部分なので、消してはいけません。それ以外はclick on an imageというメッセージと、divタグが一つあるだけです。このdivタグは画像を表示するために使いそうですね。

main.rb

雰囲気が掴めたところでmain.rbを見てみましょう。これがOpalによってJSに変換されるRubyスクリプトで、このデモの中心部分です。

最初にImageというクラスがあります。こいつがクリックできるアインシュタイン(やっぱりアインシュタインだったのか…)のオブジェクトです。画像ファイルはこのディレクトリではなくて、少し上の階層のassetsというディレクトリにあります。そのあたりの設定はconfig.ruでやっているようです。

class Image
  def initialize(game)
    @sprite_key = "einstein"
    @sprite_url = "assets/pics/ra_einstein.png"
    @game       = game
  end

createメソッドに、クリックイベントを拾う処理が書いてあります。events.onでイベントハンドラを登録できるようですね。

  def create
    @counter = 0

    listener = proc do
      @counter   += 1
      @text.text = "You clicked #{@counter} times!"
    end 
...

    @text = @game.add.text(250, 16, '', { fill: '#ffffff' })

    @image.events.on(:down, self, &listener)
  end

@gameという変数は、以下のGameクラスのオブジェクトです。ファイルの最後がGame.newなので、ここがゲームプログラムのエントリポイントになるようですね。parent: "example"という指定は、index.htmlの<div id="example">を描画領域として使う、という指定でしょう。

class Game
  def initialize
    game  = Phaser::Game.new(width: 800, height: 600, renderer: Phaser::AUTO, parent: "example")
    state = MainState.new(game)
    game.state.add(:main, state, true)
  end
end

MainStateクラスはその下で定義されています。これとかを見ると、「タイトル画面」「プレイ中画面」みたいにシーンごとにStateを定義するみたいです。

class MainState < Phaser::State
  def initialize(game)
    @game = game
  end

  def preload
    @image = Image.new(@game)
    @image.preload
  end

  def create
    @image.create
  end
end

おわりに

今回はopal-phaserを紹介しました。プロジェクトとしては2年前からあるようで、今も開発が続けられています。

https://github.com/orbitalimpact/opal-phaser のGamesの項に、もう少しゲームらしいサンプルがあります。(tankgameはどうやって操作するのかよくわからない感じでしたが)

触ってみて良く分からないとかうまく動かないことがあれば、Twitter等で聞いてもらえればお手伝いできるかもしれません。

Edit

Opalのハッシュはどのようにして実装されているのか

2016-12-19

本記事はOpal Advent Calendar 2016の19日目のエントリです。

今回はOpalのHashクラスの実装について見ていきます。

corelib/runtime.js

opal/corelibは、array.rbやstring.rbなど、組み込みクラスの実装が置かれているディレクトリです。この中に一つだけ、runtime.jsという、拡張子が.jsのファイルがあります。

runtime.jsはコンパイル後のJavaScriptの一部としてそのまま埋め込まれます。クラスの生成定数の探索といった処理系の基礎となる機能が実装されており、Opalの心臓部といえるでしょう。

Opal.hash_xx

runtime.jsでは、ハッシュを扱う以下のような関数が定義されています

hash_getやhash_putを眺めてみると、ハッシュアルゴリズムを自前で実装していることが分かります。

単純な、文字列だけをキーとするハッシュであればJavaScriptのオブジェクトにそのままマップできるかもしれませんが、RubyのHashクラスは任意のRubyオブジェクトをキーにできたり、ハッシュ値を明示できたりするため、このようになっています。

Hashクラスとの関係

Hashクラスはopal/corelib/hash.rbで定義されています。これを見ると、Hashクラスのメソッドは先ほどのhash_getやhash_putを使って実装されていることが分かります。

以下はHash#[]=メソッドの定義です。単純にhash_putを呼ぶだけですね。

  def []=(key, value)
    %x{
      Opal.hash_put(self, key, value);
      return value;
    }
  end

Hash#[]の方も見てみましょう。こちらもほぼhash_getを呼ぶだけですが、値が存在しなかったときはdefaultメソッドを呼ぶようになっています(mrubyのアドカレ記事でもこの話しましたね)。

  def [](key)
    %x{
      var value = Opal.hash_get(self, key);
      if (value !== undefined) {
        return value;
      }
      return self.$default(key);
    }
  end

各関数とメソッドの対応をまとめておきます。

ハッシュオブジェクトの実装

Opal.hash_xxの実装も少し見てみましょう。まず、ハッシュオブジェクトは以下のプロパティを持つことが分かります。

  Opal.hash_init = function(hash) {
    hash.$$smap = {};
    hash.$$map  = {};
    hash.$$keys = [];
  };

$$smapと$$mapが、キーと値の組を保持します。RubyのハッシュのキーはたいていStringかSymbolなので、キーが文字列のときは$$smapを使い、そうでないときだけ$$mapを使うようです。(OpalではSymbolはStringと同じものです)

$$keysはキーの一覧を高速化のためキャッシュしたもので、Hash#keysメソッド等で使われます。またこのプロパティを見ればハッシュのサイズが分かるため、Hash#lengthの実装にも使われています。

  def length
    `self.$$keys.length`
  end

ハッシュテーブルの実装

最後に、ハッシュテーブルの実装を確認するため、Opal.hash_putを見てみましょう。

キーが文字列のときは、$$smapをハッシュテーブル代わりにして値を格納するだけです。

    if (key.$$is_string) {
      if (!hash.$$smap.hasOwnProperty(key)) {
        hash.$$keys.push(key);
      }
      hash.$$smap[key] = value;
      return;
    }

キーが文字列でない場合は、Object#hashメソッドを実行してハッシュ値(key_hash)を得ます。これを使ってキーと値のペアを格納するのですが、ハッシュ値は衝突する可能性があるため注意が必要です。

    var key_hash = key.$hash(), bucket, last_bucket;

まず、衝突が起こらなかった場合です。$$mapにハッシュ値がkey_hashであるオブジェクトが格納されていない場合は、新しいbucketを作って保存します。bucketは生のキーと値を保持するJSオブジェクトで、ここには出てきていないですがもう一つnextというプロパティがあり、要するにリンクドリストになっています。

    if (!hash.$$map.hasOwnProperty(key_hash)) {
      bucket = {key: key, key_hash: key_hash, value: value};
      hash.$$keys.push(bucket);
      hash.$$map[key_hash] = bucket;
      return;
    }

衝突が起こった場合、つまり当該ハッシュ値のbucketが既に存在する場合は、各bucketの中身を調べます。キーが一致する(Object#eql?)ものがあれば、このキーに対する値を上書きしようとしているわけなので、bucket.valueを更新します。

    bucket = hash.$$map[key_hash];

    while (bucket) {
      if (key === bucket.key || key['$eql?'](bucket.key)) {
        last_bucket = undefined;
        bucket.value = value;
        break;
      }
      last_bucket = bucket;
      bucket = bucket.next;
    }

上書きでなかった場合は、最終的にbucket.nextがundefinedになるのでループを抜けます。このとき、一番最後のbucketを覚えておきます(last_bucket)。新しいbucketを作り、last_bucketの後ろに連結します。

    if (last_bucket) {
      bucket = {key: key, key_hash: key_hash, value: value};
      hash.$$keys.push(bucket);
      last_bucket.next = bucket;
    }

以上でOpal.hash_putの実装は終わりです。

まとめ

Edit

Opalはどうやってmethod_missingを実装しているのか

2016-12-17

本記事はOpal Advent Calendar 2016の17日目の記事です。

OpalはRubyからJavaScriptへのコンパイラです。今回はRubyの黒魔術の一つであるmethod_missingの実装について見ていきます。

method_missingとは

Module#method_missingは、あるオブジェクトに対して定義されていないメソッドを呼び出したときに走るフックを定義する機能です。

class A
  def method_missing(name, *args)
    puts "hooked (name: #{name}, args: #{args.inspect})"
  end
end

A.new.foo(1, 2, 3)

上記を実行すると以下のようなメッセージが出力されます。

hooked (name: foo, args: [1, 2, 3])

クラスAにはfooというメソッドがないので、fooの代わりにmethod_missingメソッドが呼ばれるということですね。用途としては、DSLを作る際に使われたりします。

どうやって実装するか?

Opalはこの機能をどうやって実装しているのでしょうか。Opalでは、RubyのメソッドはJavaScriptのメソッド呼び出しに変換されます。

a.foo()
a.$foo();

残念ながら、JavaScriptには存在しないメソッド呼び出しをフックする機能はなく、呼び出そうとすると例外が発生します。

これを回避する単純な方法としては、「メソッド呼び出しの前に毎回、メソッドが存在するか確認する」というやり方があります。実際、昔のOpalはこのようにしていたのですが、これだとmethod_missingを使っていない場合でも動作速度が落ちるという問題があります。

メソッド呼び出しを列挙する

今のOpalはもっと良い方法を使っています。まず、実行するソースコードを解析して、メソッド呼び出しをすべて列挙します。(解析というと大変そうですが、どのみちコンパイルするためにはパースしないといけないので、そこからメソッド呼び出しを列挙するのは簡単です。)

その後、継承関係の上の方(BasicObject)にこれらの名前のメソッドを実装し、method_missingメソッドを呼ぶように設定しておきます。コンパイル後のソースコードのadd_stubsを呼んでいる箇所がそれです。

Opal.add_stubs(["$foo"]);

これにより、fooメソッドをもたないオブジェクトに対してfooを呼ぼうとするとBasicObject#fooが呼ばれ、めでたくmethod_missingが呼ばれるようになります。

補足:sendを使った場合は?

Rubyに詳しい人なら、上の方法では「メソッド呼び出しの一覧」を網羅できないことに気づいたかもしれません。Kernel#sendを使うと、以下のように任意の式がメソッド名になる可能性があるので、実行するまでメソッド名が確定しません。

a.send(["foo", "bar"].sample)  #=> fooかbarのどちらかを呼び出す

しかしsendの場合は実行時にメソッド名が取れるわけなので、sendの側でメソッドがなければmethod_missingを呼ぶよう実装されています。抜かりありませんね。

まとめ

« Prev Next »