近&況

Recent Posts
Edit

オブジェクト指向言語をLLVM IRにコンパイルするには

2017-02-07

昨年から、Esquisという言語を作っている。Rubyっぽい文法の静的型付け言語になる予定で、実行はLLVM IRを経由して行う。

ということで、(クラスベースの)オブジェクト指向言語をLLVM IRで表現する方法について考えていたので、分かったことをまとめておく。既存の実装としては主にCrystalの生成するLLVM IRを参考にした。

オブジェクトをstructに対応させる

LLVMにはstruct型というものがあり、オブジェクトはこれで表現することができる。問題はどのようなstruct型を定義するかだ。

最初に考えたのは、EsObjという型を作って、すべてのオブジェクトを表現するという方法だ。

%EsObj = type { ... }

だがすぐに、この方法では上手くいかない点が見つかった。オブジェクトはインスタンス変数の値を保持する必要があるが、オブジェクトがどのようなインスタンス変数を持つかは属するクラスによって異なるので、一つのLLVM structで全てを表現することはできない。

ということでEsquisの1クラスごとに、対応するstruct型を定義する必要がある(ちなみにCrystalの生成するLLVM IRもそのようになっている)。以下は例である(Esquisの言語仕様はまだちゃんと決めてないので雰囲気で読んで下さい)。

; 1. インスタンス変数を持たないクラス
; class A
; end
%A = type {}

; 2. 整数型のインスタンス変数をひとつ持つクラス
; class B
;   def initialize(Int @i)
;   end
; end
%B = type { i32 }

インスタンス生成

次にインスタンス生成のコンパイルを考える。メモリを確保する必要があるので、今回はBoehm GCを使う。@GC_mallocを呼べばメモリの確保(と、必要に応じてメモリの回収)が行われるので、何バイト確保するのかだけ考えればよい。structのサイズ計算については前の記事で触れた。

これを使って、クラスAのインスタンスを生成する関数を書く。名前は@"A.new"としよう。この関数は新しくメモリを確保して、struct Aのポインタ(%A*)を返す。

define %A* @"A.new"() {
  ; struct Aのサイズを計算する
  %A_size = ptrtoint %"A"* getelementptr (%"A", %"A"* null, i32 1) to i64
  ; メモリを確保する
  %raw_addr = call i8* @GC_malloc(i64 %A_size)
  ; i8*を%A*に変換する
  %addr = bitcast i8* %raw_addr to %A*
  ; 変換後のアドレスを返す
  ret %A* %addr
}

これだけでも動くが、CrystalのLLVM IRを見るとメモリ確保後に@llvm.memsetで内容をゼロクリアしていることが分かる。ゼロクリアしないと、作っている処理系にバグがあったときに毎回挙動が違うことになりかねないので、クリアしたほうが良さそうだ。

declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1)
...
  call void @llvm.memset.p0i8.i64(i8* %raw_addr, i8 0, i64 %A_size, i32 4, i1 false)

インスタンスを生成する側は以下のようになる。

define i32 @main() {
  ...
  ; a = A.new
  %a = call %A* @"A.new"()
  ...

メソッド呼び出し

次にメソッド呼び出しを考える。継承はまだ考えないものとする。オブジェクトの型が事前に分かっている(= 呼ばれるメソッドが事前に特定できる)のであれば、以下のように単なる関数呼び出しにコンパイルできる。ただしメソッドに対応する関数は、第一引数として当該オブジェクトのアドレス%selfを受け取るものとする(今回は必要ないが、インスタンス変数の値を参照したりする場合に必要となる)。

; class A
;   def foo
;     213
;   end
; end
%A = type { }
define i32 @"A#foo"(%A* %self) {
  ret i32 213
}

define i32 @main() {
  ...
  ; a = A.new
  %a = call %A* @"A.new"()
  ; a.foo
  %result = call i32 @"A#foo"(%A* %a)
  ...

多態

次に、継承について考える。継承がある場合、ある変数に代入されているオブジェクトのクラスは実行時まで確定しないことがある。

例として、「図形」を表すShapeクラスと、そのサブクラスであるCircleクラスおよびSquareクラスがあるとしよう。各クラスは面積を計算して返すareaというメソッドをもつとする。

以下のような場合、変数sがCircleなのかSquareなのかは、実行時になるまで確定しない。そのため、どちらであっても対応できるようなLLVM IRを生成する必要がある。

; sampleメソッドは、配列のいずれかの要素をランダムに返す
s = [Circle.new(10), Square.new(20)].sample
s.area

クラスID

これに対応するには、各オブジェクトに所属するクラスの情報を入れておく必要がある。例えば各クラスに番号(以下、クラスID)を振り、それをstructの最初の要素とするというのは一つの方法である。

; class A
; end
%A = type { i32 }   ; クラスID 

; class B
;   def initialize(Int @i)
;   end
; end
%B = type { i32, i32 }  ; クラスID、インスタンス変数@i

クラスIDは、クラスのインスタンスを生成したタイミングでそのインスタンスに書き込む。クラスAの場合でいえば、先ほどの@"A.new"を改修する。

多態に対応したメソッド呼び出し

areaメソッドの呼び出しを考える。Shape#areaメソッドを作り、CircleかSquareか分からないオブジェクトsはとりあえずこの関数に渡すことにする。Shape#areaはclass_idを見て、Circle#areaまたはSquare#areaをcallする。

define i32 @"Shape#area"(%"Shape"* %self) {
  %id_addr = getelementptr inbounds %"Shape", %"Shape"* %a, i32 0, i32 0
  %class_id = load i32, i32* %id_addr

  ; %class_idが1ならCircle#areaをcall
  ...
  ; %class_idが2ならSquare#areaをcall
  %sq = bitcast %Shape* %self to %Square*  ; %selfは%Shape*なので、%Square*にキャストする必要がある
  %ret = call i32 @"Square#area"(%Square* %sq)
  ret i32 %ret
}

おわりに

大したことはやってないのだが、分かったことを一つずつまとめていたら長くなってしまった。いままでクラスやオブジェクトといったものがどのように実現されるかについてはあまり深く考えて無かったので、いろいろな発見があって面白かった。

Edit

syntax-rules進捗

2017-02-06

去年の夏頃から、BiwaSchemeにsyntax-rulesを入れようと思ってぼちぼち調べてたんだけど、どうもこれは本腰入れて調べないと進捗しないなということで、年末からいろいろ文献を読むなどしていた。

その成果がこちら。

swapマクロを展開させてみたところ

orrというマクロを素朴に展開すると、マクロ内で使っているtという変数名が呼び出し側で定義しているtと衝突してしまう。これを自動でt.0とt.1にリネームしている、という図。

ソースコードはブランチにpushしてある。まだhygenic macroに対応したエクスパンダが本体とは独立に存在するという状態で、最終的にはこれで本体のエクスパンダ(Biwascheme.Interpreter.expand)を置き換えるということになる。

読んだものとか

最初は「syntax-rules 実装」とかで検索してたんだけど全然資料がなくて、上位互換であるsyntax-caseについての文献を読んでいた。

ビューティフルコード

25章がDybvig先生によるsyntax-caseの実装についての寄稿で、結局これが一番参考になった。エッセイ集にこの内容ぶち込むのすごい。

日本語版と英語版のどちらを読むかは悩ましいところで、日本語版の方が概要を掴むのは早いと思うが、多少意味が取りづらい箇所がある。

論文

これもsyntax-caseの説明で、範囲はビューティフルコードとだいたい同じ。

ビューティフルコードも論文の方も、方針が詳しめに解説されているという感じで、詳細な全体像は載っていない。実装へのリンクとか付けてほしい…。書いてない部分は想像力で補完する必要がある。

今後の予定

とりあえず最小の例がうまく動いたというだけなので、リリースにはまだたくさんの作業が残っている。

が、まあ夏〜秋頃を目標にぼちぼちとやっていきたい。というのもBiwaSchemeは僕の中ではサイドプロジェクトという位置づけなので、静的型付け言語の実装の方をメインにやっていきたいのだった(今日LLVMのエントリを書いたのはこっちの作業)。

とはいえ今年はBiwaScheme 10周年イヤー(!)なので、今年中には実装を済ませて、1.0.0をリリースしたいと考えている。規格の範囲にはまだ未実装の大物がいくつか残っているが(ライブラリ、例外、dynamic-windなど)、アプリを作って遊べる程度の能力はもうだいぶ前からあるので。

追記

書き忘れていたことを一つ。書籍・論文の他には「既存の処理系の実装を読む」という方法があって、実際にいくつか眺めてみたのだけど、これはあまりうまく行かなかった。hygenic macroというシステムは処理系全体のさまざまなもの(シンボル、マクロ展開器、ライブラリシステム等)と関係しているため、処理系のどの部分まで読めばいいかの判断が難しいのと、処理系によって実装が全然違う(syntax-rulesだけを実装しているもの、psyntax経由でsyntax-rulesとsyntax-caseを実装しているもの、独自の低レベルマクロシステムの上にexplicit renamingとsyntax-rulesを実装しているもの、etc.)というのが大変だった。

Edit

llvmのsub expressionっぽいやつの書き方

2017-02-06

メモ。

LLVM IRは基本的に以下のような構造をしている。

; (レジスタ名) = (命令名) (引数 ...)
%2 = mul i64 %0, %1

ところがコンパイラが生成した.llファイルを見ていると、引数の部分に別の命令が入っていたりする。

%4 = mul i32 ptrtoint (i1** getelementptr (i1*, i1** null, i32 1) to i32), %3

ここではmul命令の引数に、ptrtoint命令とgetelementptr命令の呼び出しが入っている…ように見える。しかしそれにしては括弧の位置が微妙におかしい。例えば「to i32」はどの命令にかかるのだろうか?

実はこれらはConstant Expressionsと呼ばれるもので、特定の命令だけ、このような書き方が許されている。上記の例では以下の2つのConstant Expressionが使われている。

ptrtoint (CST to TYPE)
getelementptr (TY, CSTPTR, IDX0, IDX1, ...)

ということで、上記の「to i32」はptrtointと対応しているのであった。

以下のような構造体Aについて、これのサイズを計算したいとする。

%A = type { i32 }

これは以下のように書ける。

; nullを%A*と見なして、1だけ進めた位置のアドレスを得る
%addr = getelementptr %A, %A* null, i32 1
; アドレス値を整数に変換する
%A_size = ptrtoint %A* %addr to i64

この2行を1行にまとめるにはどうすれば良いか。まず1行目のgetelementptrをConstant Expressionとして書き直すと以下のようになる。

getelementptr (%A, %A* null, i32 1)

これを2行目の%addrと差し替えれば出来上がり。

%A_size = ptrtoint %A* getelementptr (%A, %A* null, i32 1) to i64

(LLVM構造体のサイズ計算についてはこのエントリを参考にした)

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

まとめ

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

Next »