オフラインリアルタイムどう書くE28の実装例 ( Ruby )
オフラインリアルタイムどう書くE28の問題「増築の果ての隣室」の実装例を、Ruby で。
問題 : http://nabetani.sakura.ne.jp/hena/orde28sqst/
実装リンク集 : https://qiita.com/Nabetani/items/4e3fac2746ca05a93165
イベント : https://yhpg.doorkeeper.jp/events/81346
めちゃ面白いイベントなのに参加者すくなくて寂しいので参加者募集です！！！次回のイベントももう公開済みなのでぜひ。
負けました。正確には時間切れから発表中デバッグでバグを落としたけど計算量減らしてないのでNo30くらいまでしか通せず。家帰ってちょこちょこ直していまは通ってます。以下、ざっくり方針。
なんか計算で番号求められるんじゃね？って思ったんだけど、増築されていくごとに分割数が増えていくことにより、1辺の長さを割っていったもの(あるいはかけていったもの)が膨らんでいって、どうもさくっとは計算できなさそうだった。なので真面目に増築することにする。
Ruby なので有理数が扱えて最初の正方形の1辺を1としたときに4分割なら 1/4 、そのあと7分割なら 4/28 みたいな感じで考えていくと楽かも、と思った。ただどうも隣接の判定をミスりそうな気がしたので4分割したら最初の正方形の1辺を4、さらに7分割なら28と増やしていくことにした。Rubyなら扱いきれるだろ、みたいな雑な予想込みで。
んで、そうやってかけていった値をもとにすると、すべての部屋の辺の長さが整数で扱えるようになる。じゃあそのあとどうするのっていうと、 Hash{Integer => Hash{ Integer => Integer}} みたいな型で盤面を用意してほんとに正方形を塗っていくことにした。配列にしてないのはSあるいはW方向への増築をすると x, y がマイナス側にいくかもだから。全く塗る必要はないのだが脳内デバッグが下手すぎて実際に塗ってたらなんかわかるようになってきた。実際発表中に debug モードで見せたりしてウケた1。
ただこれがとんでもなく遅い。そりゃ当然だということで全部塗るわけじゃなくて辺だけ塗るようにした。
でもこれも遅い。辺すら塗る必要ないよね、といって部屋の情報を貯め込むようにした。
これもまた遅い。これがなんで遅いのかというと隣接判定のところで r1.to_a & r2.to_a 的なことをやってたせいだった。そりゃそうだ。隣接判定のため、x座標的にあるいはy座標的に同じところにいるかどうか、みたいな判定。
def neighbor?(other) if h_match?(other) x2 == other.x1 || x1 == other.x2 elsif v_match?(other) y2 == other.y1 || y1 == other.y2 end end def v_match?(other) !((x1...x2).to_a & (other.x1...other.x2).to_a).empty? end def h_match?(other) !((y1...y2).to_a & (other.y1...other.y2).to_a).empty? end
重なりがあること、というのがうまく言語化できなかったのだが両手をピースにしてごにょごにょ動かしてたら、一方の始点がもう一方の終点より大きいケースがだめであることがわかった。というわけで最終形は以下。これは普通に返ってくる。 x1, x2, y1, y2 の計算あたりは正方形なので全然いらない情報なのだが一旦通ってるのでこのままで。
class Solver Instruction = Struct.new(:dir, :size) Sq = Struct.new(:num, :x1, :x2, :y1, :y2) do def cover?(x, y) x1 <= x && x <= x2 && y1 <= y && y <= y2 end def neighbor?(other) if h_match?(other) x2 == other.x1 || x1 == other.x2 elsif v_match?(other) y2 == other.y1 || y1 == other.y2 end end def v_match?(other) !((x2 - 1) < other.x1 || (other.x2 - 1) < x1) end def h_match?(other) !((y2 - 1) < other.y1 || (other.y2 - 1) < y1) end end class Board attr_reader :min_w, :max_w, :min_h, :max_h def initialize @min_w = 0 @max_w = 0 @min_h = 0 @max_h = 0 @sqs = [] end def fetch(x, y) @sqs.find { |e| e.cover?(x, y) }&.num end def neighbors(num) t = @sqs.find { |e| e.num == num } @sqs.select { |e| t.neighbor?(e) }.sort_by(&:num) end def rect(num, x1, x2, y1, y2) @min_w = x1 if x1 < min_w @max_w = x2 if x2 > max_w @min_h = y1 if y1 < min_h @max_h = y2 if y2 > max_h @sqs << Sq.new(num, x1, x2, y1, y2) end end def initialize @base = 1 # base_size end def solve(input) a, b = input.split('/', 2) @target = b.to_i @insns = a.chars.each_slice(2).map do |s| Instruction.new(s[0].to_sym, s[1].to_i) end @insns.each do |insn| @base *= insn.size end board = Board.new board.rect(1, 0, @base, 0, @base) n = 1 @insns.each.with_index do |insn, i| minw = board.min_w maxw = board.max_w minh = board.min_h maxh = board.max_h case insn.dir when :N, :S tmp_base = (maxw - minw) / insn.size else tmp_base = (maxh - minh) / insn.size end 1.upto(insn.size) do |d| case insn.dir when :N x2 = minw + (tmp_base * d) x1 = x2 - tmp_base y1 = maxh y2 = maxh + tmp_base when :S x2 = minw + (tmp_base * d) x1 = x2 - tmp_base y2 = minh y1 = minh - tmp_base when :E y1 = maxh - (tmp_base * d) y2 = y1 + tmp_base x1 = maxw x2 = maxw + tmp_base when :W y1 = maxh - (tmp_base * d) y2 = y1 + tmp_base x2 = minw x1 = minw - tmp_base end board.rect(n+d, x1, x2, y1, y2) end n += insn.size end board.neighbors(@target).map(&:num).join(',') end end
読了: 『Go言語による並行処理』
読みました。ちょっと駆け足気味だけど。
全体的に良書でこういったことが知りたかったんだということが書いてあってよかったです。一方で悪い点もほんのちょっとありました。先に悪いと思っている点について書いておこうと思います。
悪かったと思った点
まず、interface{} 型の利用は、うーん、やめたほうがいいんじゃないの、という感じです。まあこれは補遺Bにより訳者の方による go generate の利用の推奨などもありまあええやろって思いました。
また、 done チャネルの利用は、context がある程度普及している昨今ではかえって混乱を招いたのではないかと思います。最初の1例は「お、これ context の本質を捉えてていいな」と思ったのですが。エラー処理も pkg/errors でよくね？と最初は思ったのですが、そちらはいろいろ学びがあったので、逆に done についての煩雑さが目についたというのもあります。
まあこれらはどちらも個人の趣味の範疇かもしれません。そんなに目くじら立てるようなことでもないでしょう。
これは本文とは関係ないのですが、DLしたPDFファイルの outline が iOS 上の GoodNotes というアプリでは部分的にしか解釈できてなかったようです。これはアプリ側の問題の可能性もありますが。ちょっと読書体験が悪かったです。
良かったと思った点
まず「並行」「並列」について。僕はこの本で出てきた説明が一番しっくりきました。曰く「並行性はコードの性質を指し、並列性は動作しているプログラムの性質を指」すとのことです。以前にはおそらく Rebuild.fm でささださん達が説明されていた回で聞いていたのですがその後あまり意識することがなくうろ覚えになっていました。今回のこの説明は結構すんなり納得できました。
エラー処理や流量制限については現在 go でなにかを書いてる身としては参考になりました。実際運用するとこういうことありそうだなーとか不安になったりしてね……。はい。「ゴルーチンの生成コストとか気にすんな」という話はもともと繰り返し出ていて「いやでも無限に生成できると、DB詰まったりとか考えるとそこの生成数とかに制限かけないと安定しなくね？」みたいなことを思っていましたのが流量制限に集約していたのだなーと気づきました。
チャネルの所有権を曖昧にしないことや正しくリソース管理する点についてのイディオムというか、お作法について明に暗に示されていたのもよかったです。構造体のメンバにするなとか、レキシカル1に縛っておけとか。
p.32 からはじまる「チャネルを使うかどうか」という決定木や4章の各種パターンは有用そうなので忘れた頃に確認したほうが良さそうですね。チームでの読み合わせなどをしたほうが良いかもしれません。
読書メモ
コピらずメモったので原文と表記が違うかもしれません。
p.39
結果としてゴルーチンは、暗黙的には並行処理の構成要素ですが、並行性というのはコルーチンの性質ではありません。
各コルーチンを逐次実行するような処理系もありうるから、かな？
ゴルーチンはグリーンスレッドにスケジュールされます
へー。これ知らなかった。6章で解説あり。
p.53 あたり
Cond いまいちよくわからない
p.68
無名ゴルーチンが終了するとき
言語仕様的には無名ゴルーチンが終了するのと stringStream からの読み込みでブロックするのはどっちが先かわからないのではないか、と思った。些細な点だけど。
p.74
くっそどうでもいいが出力結果がおかしい。実装してみたのが以下。
chap4.1 全体 あんまりよくわからなかった
p.123
同じ型の2値を戻すとき、名前付き戻り値を _ で受けることによって型を2回書かずに済むというテクを覚えた(おそらく使わない)。
scope 切って一回変数にうけてから chan 型変数を nil 代入して処理済みを表す、というテクを覚えた。これは使うかもしれない。
p.132
リトルの法則について、総和をとってよいのかはあまり自明ではないのでは？と思った。各パイプラインは、直前の例のように重なり合うことが可能なので単純な足し算にしてよいのか、という点が疑問として残る。リトルの法則自体はある程度独立したトピックなので後で調べるかも。
p.207
「プログラムがゴルーチン内の関数に実行してもらいたいと思うのはよくあることでしょう」の文意がとれなかった。前後の流れから、「作ったゴルーチンをすぐに実行してもらいたいと思うのはよくあることでしょう」という感じだろうか。
20181028 19時過ぎ
誤字脱字系は本家サポートレポジトリで issue 化したので読書メモから消した
go のパッケージで特定の型のメンバをもった構造体が定義されていないことを確認したい
モチベ
swagger 定義から go client を生成するときに、 type: "number" はデフォルトでは float32 型として定義される。これは type: "number", format: "double" とすることにより float64 型に変更可能である。
該当プロジェクトでは精度的な観点から float64 を使うことが望ましかった1。定義ファイルの変更は完了したが、生成したクライアントライブラリが float32 型を含まないことを確認したくなったので静的に解析することにした。
制約
swagger による go client は構造体のメンバの型に alias された型を使わないのでその前提とする。すなわち type f32 float32 のようなことは起きないものとする。
また構造体のメンバのみに限定し、関数のシグネチャや定数・変数の類も気にしないことにする。
実装
以下のようなコードになる
func TestType(t *testing.T) { subPackage := "pkgname" set := token.NewFileSet() packs, err := parser.ParseDir(set, subPackage, nil, 0) if err != nil { t.Fatal("Failed to parse package:", err) } for _, pack := range packs { for path, f := range pack.Files { tokenFile := set.File(f.Pos()) bs, err := ioutil.ReadFile(path) if err != nil { t.Fatal(err) } for _, d := range f.Decls { if g, ok := d.(*ast.GenDecl); ok { if g.Tok == token.TYPE { for _, v := range g.Specs { if ts, ok := v.(*ast.TypeSpec); ok { if st, ok := ts.Type.(*ast.StructType); ok { for _, f := range st.Fields.List { bp := tokenFile.Position(f.Pos()) ep := tokenFile.Position(f.End()) s := string(bs[bp.Offset:ep.Offset]) if strings.Index(s, "float32") >= 0 { t.Errorf("should not contain float32 type at %s:%d", tokenFile.Name(), bp.Line) } } } } } } } } } } }
今後の課題
ioutil.ReadFile は必要になるまで呼び出しを遅延したほうがよいのだろうが面倒なので必ず読むようにしている。これはまあやたらファイル数が多くなければ問題にならないだろう。
最終的に strings.Index で判定しているのがダサいので別の手法を試したい。
-
本当は decimal がほしいので10進数表現の文字列がほしいのだが↩
Ruby でリファクタリングをした際にテスト要否を判断したい
TL; DR
- rubocop の自動修正とかが正しいのか不安になる
- Ruby なら ISeq に差分があるか調べればよい
- line number, column number 問題は本体に手をいれておけばある程度乗り越えられる
前提
$ ruby -v ruby 2.5.1p57 (2018-03-29 revision 63029) [x86_64-darwin17] $ bundle exec rubocop -V 0.59.2 (using Parser 2.5.1.2, running on ruby 2.5.1 x86_64-darwin17)
モチベ
rubocop には自動修正機能がついているわけですが、実際に rubocop のソースを読んでいない身としては盲信するわけにもいかない、というつらいところがあります。日々活発に追加される cop の中にはもしかしたらバグっているのもあるかもしれません。そうするとプロダクションコードにえいやでいれるにはちょっと気がひけるところがあったりなかったりします1。
ですので上で紹介した記事のように、言語処理系がどのようにソースコードを捉えているのかという観点から auto correct による変更の安全性を確かめたいと思います。
コンセプト
Ruby script を実行する場合には ソースコード -> AST -> ISeq ( instruction sequence ) と変換されてから YARV が ISeq 実行するようになっています2。
ruby コマンドには --dump=insns という便利なオプションがあり ISeq を(比較的)人間に読みやすい表現で確認することができます。今回はこの --dump=insns の結果をもとに安全性を担保します。
$ ruby -e 'puts 1' 1 $ ruby -e 'puts 1' --dump=insns == disasm: #<ISeq:<main>@-e:1 (1,0)-(1,6)>============================== 0000 putself ( 1)[Li] 0001 putobject_OP_INT2FIX_O_1_C_ 0002 opt_send_without_block <callinfo!mid:puts, argc:1, FCALL|ARGS_SIMPLE>, <callcache> 0005 leave
実践
簡単なケース
まずは以下のような簡単な例からいきます。
# frozen_string_literal: true class Foo def foo puts 1 end end
puts と 1 の間に2スペース入ってますね。さて、この状態の --dump=insns の結果は以下になります。
== disasm: #<ISeq:<main>@sample1.rb:1 (1,0)-(7,3)>====================== 0000 putspecialobject 3 ( 3)[Li] 0002 putnil 0003 defineclass :Foo, <class:Foo>, 0 0007 leave == disasm: #<ISeq:<class:Foo>@sample1.rb:3 (3,0)-(7,3)>================= 0000 putspecialobject 1 ( 4)[LiCl] 0002 putobject :foo 0004 putiseq foo 0006 opt_send_without_block <callinfo!mid:core#define_method, argc:2, ARGS_SIMPLE>, <callcache> 0009 leave ( 7)[En] == disasm: #<ISeq:foo@sample1.rb:4 (4,2)-(6,5)>========================= 0000 putself ( 5)[LiCa] 0001 putobject_OP_INT2FIX_O_1_C_ 0002 opt_send_without_block <callinfo!mid:puts, argc:1, FCALL|ARGS_SIMPLE>, <callcache> 0005 leave ( 6)[Re]
今回の本旨とは外れるので内容は飛ばします。 ruby --dump=insns sample1.rb | md5とかして md5 hash をとっておくと eac204585dcd059cbf333c3f6681d59e でした。
さて、rubocop に autocorrect してもらうとどうなるでしょうか。
$ bundle exec rubocop -a (snip)
diff --git a/iseq-diff/sample1.rb b/iseq-diff/sample1.rb index 97256e1..f847a3d 100644 --- a/iseq-diff/sample1.rb +++ b/iseq-diff/sample1.rb @@ -2,6 +2,6 @@ class Foo def foo - puts 1 + puts 1 end end
スクリプトの中身は変わっていますが、前後でハッシュ値が変わってないので YARV に渡される AST は変わらないことがわかります。
$ ruby --dump=insns sample1.rb | md5 eac204585dcd059cbf333c3f6681d59e
このケースはこれでおk
難しいケース
先程掲載された insns を見ていると謎の数値がいくつかでてきます。
sample1.rb:1 (1,0)-(7,3)
0000 putspecialobject 3 ( 3)[Li]
このうちいくつかはソースファイルにおける行番号・列番号を示しています。
そのため、以下のようなファイルでは --dump=insns の結果が変わってしまいます。
# frozen_string_literal: true puts 1
$ ruby --dump=insns sample2.rb == disasm: #<ISeq:<main>@sample2.rb:1 (1,0)-(3,7)>====================== 0000 putself ( 3)[Li] 0001 putobject_OP_INT2FIX_O_1_C_ 0002 opt_send_without_block <callinfo!mid:puts, argc:1, FCALL|ARGS_SIMPLE>, <callcache> 0005 leave $ bundle exec rubocop -a (snip) $ git diff sample2.rb diff --git a/iseq-diff/sample2.rb b/iseq-diff/sample2.rb index 851def2..946ef90 100644 --- a/iseq-diff/sample2.rb +++ b/iseq-diff/sample2.rb @@ -1,3 +1,3 @@ # frozen_string_literal: true -puts 1 +puts 1 $ ruby --dump=insns sample2.rb == disasm: #<ISeq:<main>@sample2.rb:1 (1,0)-(3,6)>====================== 0000 putself ( 3)[Li] 0001 putobject_OP_INT2FIX_O_1_C_ 0002 opt_send_without_block <callinfo!mid:puts, argc:1, FCALL|ARGS_SIMPLE>, <callcache> 0005 leave
(1,0)-(3,7) と (1,0)-(3,6) で差異があります。これは (lineno,colno) の組み合わせです。評価したブロックを構成する token について、の最初の token の開始位置と最後の token の終了位置が示されているので、こういった最後の token の終了位置がずれる変更については差分が出てしまいます。
また改行があったときには ( lineno)[LI] のような表記が現れます。しかし行の変更はほとんどのケースにおいて意味がないので検知したくありません(後述)。そこで ruby コマンドによって --dump=insns で表示される情報から lineno, colno の情報を抜いてしまうことにします。
以下コードリーディングしたときの雑な流れです。
- 起動時のオプションを判断して分岐がありそうなので
insnsで grep してDUMP_BIT(insns)がそのフラグっぽいことを突き止める - ruby.c の中で
rb_io_write(rb_stdout, rb_iseq_disasm((const rb_iseq_t *)iseq));がDUMP_BIT(insns)を使った分岐の中にあるのでrb_iseq_disasmが出力を形作る本体であろうと予想をつける rb_iseq_disasm_X系の中でなんとなくそれっぽいところを変えていく。
実際の diff としてはこうなります。不要な [Li] あたりのコメントアウトと、(lineno, colno) を全部 (1, 1) に置き換えの2点。
diff --git a/iseq.c b/iseq.c index 831a9e8109..a25b179178 100644 --- a/iseq.c +++ b/iseq.c @@ -1895,15 +1895,15 @@ rb_iseq_disasm_insn(VALUE ret, const VALUE *code, size_t pos, } } - { - unsigned int line_no = rb_iseq_line_no(iseq, pos); - unsigned int prev = pos == 0 ? 0 : rb_iseq_line_no(iseq, pos - 1); - if (line_no && line_no != prev) { - long slen = RSTRING_LEN(str); - slen = (slen > 70) ? 0 : (70 - slen); - str = rb_str_catf(str, "%*s(%4d)", (int)slen, "", line_no); - } - } +// { +// unsigned int line_no = rb_iseq_line_no(iseq, pos); +// unsigned int prev = pos == 0 ? 0 : rb_iseq_line_no(iseq, pos - 1); +// if (line_no && line_no != prev) { +// long slen = RSTRING_LEN(str); +// slen = (slen > 70) ? 0 : (70 - slen); +// str = rb_str_catf(str, "%*s(%4d)", (int)slen, "", line_no); +// } +// } { rb_event_flag_t events = rb_iseq_event_flags(iseq, pos); @@ -1965,11 +1965,11 @@ iseq_inspect(const rb_iseq_t *iseq) const rb_code_location_t *loc = &body->location.code_location; return rb_sprintf("#<ISeq:%"PRIsVALUE"@%"PRIsVALUE":%d (%d,%d)-(%d,%d)>", body->location.label, rb_iseq_path(iseq), - loc->beg_pos.lineno, - loc->beg_pos.lineno, - loc->beg_pos.column, - loc->end_pos.lineno, - loc->end_pos.column); + 1, // loc->beg_pos.lineno, + 1, // loc->beg_pos.lineno, + 1, // loc->beg_pos.column, + 1, // loc->end_pos.lineno, + 1); //loc->end_pos.column); } }
実行しないならば外部ライブラリは不要なので miniruby で十分です。 make miniruby してできたバイナリを用いて比較していきます。
$ path/to/miniruby --dump=insns sample2.rb | md5 3d80188a91c6d6c6c84f2520b77a43f0 $ rubocop -a (snip) $ git diff sample2.rb diff --git a/iseq-diff/sample2.rb b/iseq-diff/sample2.rb index 851def2..946ef90 100644 --- a/iseq-diff/sample2.rb +++ b/iseq-diff/sample2.rb @@ -1,3 +1,3 @@ # frozen_string_literal: true -puts 1 +puts 1 $ path/to/miniruby --dump=insns sample2.rb | md5 3d80188a91c6d6c6c84f2520b77a43f0
一致しましたね！一応手元ではもう少し難しそうな以下のようなファイルでも差分が出ないことを確認しています。
class Foo # todo: nya-n def no_body end def show(_mode) if _mode; puts :a else puts 1 || 2; end end end module Main end def Main.exec Foo.new.show(false) end Main::exec
diff --git a/iseq-diff/sample3.rb b/iseq-diff/sample3.rb index 1cd1af4..6b946e1 100644 --- a/iseq-diff/sample3.rb +++ b/iseq-diff/sample3.rb @@ -1,10 +1,11 @@ +# frozen_string_literal: true + class Foo - # todo: nya-n - def no_body - end + # TODO: nya-n + def no_body; end def show(_mode) - if _mode; puts :a else puts 1 || 2; end + _mode ? (puts :a) : (puts 1 || 2) end end @@ -14,4 +15,4 @@ def Main.exec Foo.new.show(false) end -Main::exec +Main.exec
課題
このアプローチにはいくつかの問題点があります。まず、Ruby スクリプトにおいて行番号は、意味のない情報ではありません。例えばみなさんが大好きな Tracepoint の line イベントに影響があります。まあ Tracepoint をプロダクションコードで使うケースは稀だとは思いますが3。
しかし、ぱっと思いついたものでも __LINE__ についての影響は実際のアプリケーションにも影響がありそうです。
$ cat a.rb __LINE__ $ cat b.rb __LINE__ $ path/to/miniruby --dump=insns a.rb == disasm: #<ISeq:<main>@a.rb:1 (1,1)-(1,1)> (catch: FALSE) 0000 putobject 2[Li] 0002 leave $ path/to/miniruby --dump=insns b.rb == disasm: #<ISeq:<main>@b.rb:1 (1,1)-(1,1)> (catch: FALSE) 0000 putobject 3[Li] 0002 leave
__LINE__ は行番号に変換されますが、これはなんとASTの時点で NODE_LIT に変換されています4。そのためディスアセンブルした結果を表示する箇所をいかにいじろうとも無力です。しかも実際にメタプロの現場では __LINE__ を使う書き方は頻出です。下記の記事が仕様と __LINE__ を使うメリットについてよくまとまっています。
また、実行時のバイナリと違うバイナリで比較して意味あんのか、という観点でも課題があります。
これから
ISeq を比較するという手法である限り、__LINE__ などの課題に対して有効な解決策はなさそうです。
一方でバイナリ違う問題については、 RubyVM::AST を用いることで ruby コマンドに手を入れなくても評価可能なのではないか？と思っています。未着手ですけど。「Ruby 本体で AST の等値性を保証してくんねーかなー」という気持ちもありますが、「等値性」がこの場合においては一般的ではないので、自分で 「 lexical な差異には目をつむって、ほかはなんとなくあってそうなの」という評価をするしかなさそうですね。
-
ゆーて大丈夫だとは思っていますが。現実的に払えるコストなら払っていいんじゃないの、という気持ち↩
-
このへんは『Rubyのしくみ Ruby Under a Microscope』 などをどうぞ。↩
-
事例があったら知りたいのでささよろです↩
-
--dump=paで確認可↩
オフラインリアルタイムどう書く E27 の解答例
問題 : http://nabetani.sakura.ne.jp/hena/orde27cardgame/
実装リンク集 : https://qiita.com/Nabetani/items/cdc102d186faaf542574
久々に勝ちました。
割と素直な実装です。計算量的に大丈夫かかなり不安だったけど結構すぐだった。
8枚のうち、ストーリーとカインドは2個のまとまりが必要なので枚数でいうとパターンが少ない。列挙すると以下の通り。
patterns = [ [8], [6, 2], [5, 3], [4, 4], [4, 2, 2], [3, 3, 2], [2, 2, 2, 2], ]
この枚数にたいしてストーリーあるいはカインドをつくって抜いて、と再帰すればよい。
初期実装は再帰じゃなくて if の羅列になってて結構汚いです。
リファクタリングしたほう
TaPL読書録 #6
前回:
今回は7章、8章。
7章は実装章である。個人的には小ステップの実装をするところまでで終わり。大ステップには変換しなかった。もうひとり書いてきた人のと小ステップ・大ステップでの差異をかるく比較して終わり。実装したのは2人だったが、「実装したからといって理解したとは限らない」のであった。
8章からは「型つき算術式」ということでようやく型がついた。長く苦しい戦いだった(マジ)
以前は「行き詰まり状態」というものを導入して評価をとめていたが、それらを実行前に静的に解釈して行き詰まり状態であることを検査したい。そのため型 Nat, Bool を導入する。
検査は「保守的」に行われることに注意。すなわち if 項 if t1 then t2 else t3 において、 t1 が「明らかに」真である場合にも t3 の型情報も用いる、という話である。ここでは t2 と t3 についてユニオンしたような型の導入は行わない1
補題8.2.2.「型付け関係の逆転」
逆転が成り立つのは、ある値が複数の型に解釈される可能性がないからである。すなわち 1 が型 Nat であり、かつ型 Rational でもあるような値が今の所存在しないことが前提となっている。これは定理 8.2.4. 「型の一意性」にて言及されている。
演習8.2.3.
「正しく片付けされた項」の「正しく」ってなんだっけ、というメモがあったが定義 8.2.1 に「項 t にたいしてある型 T が存在して t: T となるとき t は型付け可能(または正しく型付けされている)という」と書いてあった。
解答してはだいたい自明で、筆者のメモでは「規則に従ってるので規則が正しく型付けされていること・保守的に評価することを考えたら自明」とある。はい。おそらく正式に書く場合には逆転補題についてそれぞれ追えばよい。
定理8.2.4「型の一意性」
余談として部分型(で合ってたか少し自信がないが)についての話が出てきた。以下のようなクラス、関数を考える。記法は独自文法であるが意味はおそらくとれるとおもう2。
class A x: int end class B x: int y: int end func f(a: A) -> int return a.x * 2 end
上記の関数 f について、仮引数 a として B のインスタンスをいれることが可能なのか、という話。この場合 B ⊂ A なので、使えてもいいよね、という話をした。
ここでダイヤモンド継承の話もした。ダイヤモンド継承をして同名メソッドがあったときには、シグネチャさえ同じならば型システム的にはおkになりそうだよねー、実装的にはどっちにとぶか決められなくてつらそうだよねーなど。
8.3.
型の安全性とは進行と保存である。
演習 8.3.4. スキップ
演習 8.3.5.
俺のメモでは pred 0 で行き詰まるので pred nv の nv は「0 ではない numeric value」という型情報をもたないと型システムが健全じゃなくなるので無理、と書いてあった。
演習 8.3.6.
良問では？という話になった。
メモでは「型付けされていて、型が2つしかないから保存の定理の対偶から明らか」とあるが、実際のところは if true then 0 else false みたいな項が反例となる。
演習 8.3.7.
大ステップにおける「最終的に値になる」という制約が強いのだなあ、ということを確認して終わり。
次回 chap9 全部。
読了: Clean Architecture 達人に学ぶソフトウェアの構造と設計
『Clean Architecture 達人に学ぶソフトウェアの構造と設計』を読み終えたので感想です。
なにか新しいことが書いているというわけではなく、ちゃんと依存関係について考えようねという本だと捉えている。ソフトウェア設計の原則を、クラスなどの細かい粒度からもっと粗いパッケージ・サービスの粒度まで適用して俯瞰することができた。
悪書だとは思わないが、特にめちゃくちゃよい本だとも思わなかった。普通のことを「丁寧に」書いているような印象。個人的には逆にくどく感じられ、ざっと流し読み、というスピードで読了した。
さて、本書では「依存関係を整理しろ」ということを具体例を挙げて話していた。しかし普段は Ruby で書くことが多く、パッケージ・あるいはクラスに対する依存が不明確になりがちである。例えば require した場合に定数はグローバルにロードされるため、あるファイル内で何に依存しているのかということは人間としても機械としても(ツールを用いても)不明瞭になりがちである。
require 'foo' require 'bar' Baz.new
例えば上記スクリプトでは Baz について fooで require したのか、 bar で require したのか、あるいはこのファイルを実行する側で require / 定義されたのかわからない。そもそも Baz がオープンクラスされている可能性もあり、上記すべてで定義されている可能性もある。
一方で Go などであれば、別パッケージで定義されたものはパッケージ名から引かなければならず、依存は明示される。ツールにやさしい1。
package main import "fmt" func main() { fmt.Println("Hello") // fmt パッケージへの依存が明確 }
これを考えると Ruby において依存関係の整理をやろうとするのは難しいような気がする。RoR がそういったフレームワークでないという話もあるが。なお、本書の中では「アーキテクチャまで決めるようなフレームワークに依存するな」という趣旨の主張も記載されていた2。
また、別の大きな主張として「システムとしての詳細に依存するな」というのも挙げられる。具体的にはDBとかである。これに関しても「せやな〜」という気持ちはある一方でDBやミドルウェアの特性にひどく依存したシステムというのもあるような気がしていて、それをパッケージとしてまとめて覆い隠すのは少しむずかしいような気もした。これに関してはちょうど go でなんやかんや書く機会があるので実践してみようと思う。
他には、マイクロサービスへの言及もあり「サービスとして切り出しただけで依存が切れると思ったら大間違いだぞ」という話があってほっこりした。一方で「週次ビルド」についての言及もあり、時代を感じさせるものでもあった。
