trick2015 ko1さんの1つ目のやつを読むやつ

前回に引き続き trick コードを読んだのを書きます、といっても実はこっちのほうが先だったのですが。最近これに関連するものを twitter で教えてもらったので書きます。

前回はこちら

hkdnet.hatenablog.com

trick とは

なんかよくわかんないけどすごい ruby コードのコンテストです。すごい ruby コードは ruby に対する深い理解に基づいて書かれていることが多く、読むだけで勉強になったりならなかったりします。

ko1_1

バック・トゥ・ザ・フューチャーネタのほうです。

https://github.com/tric/trick2015/blob/master/ko1_1/entry.rb

コアコンセプトはそんなに難しくなくて、すべてのオブジェクトにアクセスできる ObjectSpace から iso8601 形式で書かれた時刻を昇順で取り出して、unixtime化して 0xff と論理積をとるといい感じにコードポイントに落ちてメッセージが表示できる、という感じです。¹

一応小ネタを解説しておくと。 Integer#chr は自身をコードポイントとして見たときに対応する文字を1つ返すやつです。対応表は ascii 対応表とかを見るとよいと思います。

97.chr # => 'a' 
'a'.ord # => 97

最終的な出力は eval によって行われています。eval を p に変えて実行してみると、ローカル変数 s をごにょごにょした結果は最終的には puts '"Nope. Already been there."' という文字列になり、これを eval して出力してることがわかります。

だけども

iso8601形式の文字列たちが実際の実行コードを作っていることはわかりました。しかし、 ObjectSpace.each_object{|u|s<<u} でその時刻文字列を拾ってこれるのはなんで？という疑問はあります。

例えば以下のコードだとローカル変数 f が保持しているインスタンスを見れるのは妥当な気がします。

class Foo
end

f = Foo.new
p ObjectSpace.each_object { |e| break e if e.is_a?(Foo) } # => #<Foo:0x00007fb5c98fdd70>

一方で今回のコードでは 0.times { } 内で宣言されてる %w リテラルです。これは 0.times なのでランタイムでは実際にオブジェクトを生成する必要はないですし、作成してても GC.start したら消えそうな気もします。

と、ここで RubyKaigi2018 で tenderlove の発表を思い出すと、Ruby はソースコードを解釈したあとASTを作成し、VMに実行させるための命令列を作成すること、またその命令列は Ruby 上のオブジェクトであるという話でした。² つまり、実行していなくても生成した iseq (命令列) の中に文字列リテラルがいるような気がしてきます。僕の理解が正しければあの発表の後半は、そういった iseq 上の Ruby オブジェクトをGCされないように mark array を使っているがそれのメモリ使用量を減らすために〜という話だったはず。

というわけで iseq が掴んでるんじゃないかという推測をしていたのですがどうやって確かめたらいいのかよくわかりません……。iseqが掴んでいるかどうか……？そんなんわかるの……？と思っていたら twitter で教えてもらいました。

https://t.co/yDtBJo6eXe https://t.co/x76qVtRWlh こんな感じにすると、iseqのオペランドのstringとobject_idが一致する様子がわかりますね。

— y.kaneko (@spikeolaf) August 5, 2018

↑フクロウとお化けのリプライにカエルが恐縮する図

たしかに --dump=insns で iseq が文字列リテラルを掴んでそうな様子が確認できます。

$ ruby --dump=insns ko1_1/entry.rb
== disasm: #<ISeq:<main>@ko1_1/entry.rb:1 (1,0)-(46,54)> (catch: TRUE)
== catch table
| catch type: break  st: 0000 ed: 0005 sp: 0000 cont: 0005
| == disasm: #<ISeq:block in <main>@ko1_1/entry.rb:1 (1,7)-(39,2)> (catch: FALSE)
| == catch table
| | catch type: redo   st: 0001 ed: 0079 sp: 0000 cont: 0001
| | catch type: next   st: 0001 ed: 0079 sp: 0000 cont: 0079
| |------------------------------------------------------------------------
| 0000 nop                                                              (   1)[Bc]
| 0001 putstring                    "2422-02-10T21:45:38+09:00"         (   2)[Li]
| 0003 putstring                    "2580-06-19T08:53:09+09:00"         (   3)
| 0005 putstring                    "2233-01-20T02:06:42+09:00"         (   4)

また謎 patch により current_iseq というメソッドが生えて iseq にアクセスして object_id をとることができるようになって、確かに object_id まで一致していることが確認できました。まだ謎 patch の中身が完全に謎なのでそのへんを追っていきます。疲れたのでまた次回。

---

1. このくらいなら割と素直に読めると思ってしまうが(突然のイキり)読書会参加者の雰囲気を見るとそうでもないのかもしれない↩

2. このへんから https://speakerdeck.com/tenderlove/reducing-memory-usage-in-ruby?slide=102↩

trick2015 yoshi-taka さんの作品を読むやつ

最近毎週水曜日に trick 読書会というのが開催されておりましてそこで読んだネタをブログ記事にしておくやつです。

先週読んだのはコレ。

trick2015/entry.rb at master · tric/trick2015 · GitHub

とりあえずぱっとみ markdown ファイルにしか見えないやつですが、なんと ruby スクリプトとして実行すると正常終了します。不思議

いくつかコアの概念があるので読んでて気づいたものを紹介します。

後置 if と短絡評価の and

ruby スクリプトとして実行するには2つの壁があります。 syntax error にならないこと、例外なく実行できることの2つです。この後置 if は後者の壁をすり抜けるのによく使います。

# 存在しないメソッド呼び出し、ローカル変数参照、定数参照はエラー
no_such_method

no_such_method if false # 後置 if の条件が満たされないので メソッドがなくてもエラーにならない
NoSuchConstant if false # 同様に存在しない定数でもエラーにならない

また同じような処理として11行目などは後置 until の後置 rescue と重ねられています。

後置 if により、この ruby スクリプトのうち実行される部分がめちゃくちゃ少なくなっています。

行末ピリオド

ruby はメソッド呼び出しのカッコを省略できることもあり、適当に単語を羅列していてもなんとなく syntax としては通ります。

foo bar baz # ok
foo(bar(baz)) # 上と同じ意味

ですが、これだけでは英文を書くことはできません。なぜなら改行した瞬間に式の終わりとみなされて評価がされてしまうからです。このまま実行すると NoMethodError で落ちることになります。しかし、それを行末にピリオドを置くことで回避しています。

まるで文末に置かれてる句点かのようにみえる . ですが、 ruby においてはレシーバーに対するメソッド呼び出しの起点になっています。これによってパーザに「まだこの行は終わってないよ」と錯覚させることができます。

Description from Ky.
----------
What if # 以下略

これは Ky に対する - メソッド呼び出しで、引数が単項演算子 -@ が 9個ついた What として解釈されます。 -> Ky.-(---------What)

なのでこの1, 2 行目には後置 if がないようにみえますが実際には3行目の後置 if まで1つの式としてつながっており、キャンセルすることができます。

ちなみに2行目のハイフン列は上記のように解釈されていますが、7行目の場合には単項 -@ を10個ならべた 2020 について9行目で演算する形式になっておりネタかぶりを防いでいます。

さりげない : と - と .

22行目の行末には : があり、英文的にも「以下のように」と実例を見せる感じで使われてますね。でも ruby スクリプトなので : が解釈できるかどうかが争点になります。実際にはこれは like メソッドのキーワード引数 this として this: 'ruby (略)' を渡している形式になります。これはさりげなく上手いなと思いました。

また、ruby -v の - は単項演算子 -@ を用いて ruby(-v) となっていますし、 ruby entry.rb の . はメソッド呼び出しになっています。コマンドライン上の操作も ruby スクリプトとして syntax ok になっているのもおもしろポイントですね。

---

今回は2015でしたが2013についてもなんとなく読んではいて、いずれ記事を書くかもしれません。

プレイドオフィス移転パーティー に参加してきました

plaidtech.connpass.com

お邪魔してきました。
たぶん twitter でしか知らない人も何人かいた気がするのだけど、せっかくの機会なので plaid 社の人の話を中心に聞くぞ、ということでブース来訪がメインに据えました。記憶をたよりにどんな話を聞いたのか書いておきます。

とりあえず始まる前に製品のこと知らないし(すみません)聞いとくかーという感じで聞いてきました。というわけで今夏リリースの [Karte live](https://karte.io/product/live/] の話を最初に。

見た感じだとwebサイト来訪者がどんな画面をみてるかリアルタイムに確認できる機能です。ユーザー側がスクロールするとオペレーター側の画面もスクロールされる、というような感じでした。すごーい。web接客ということで、チャットとかのご案内がうまくできるのも魅力ですけどwebサービスのサポートとかに使えるような気もしました。ざっくり話を聞いてるとセッション情報とかイベントとかを全部サーバ側に送信して、ビューアーで再生してるだけっぽいです。reduxっぽいなにか(vue だと vuex ですか？)があればイベントを再生する「だけ」ではあるんだけどいろいろ難しい点がありそうですよね。karteユーザーのサイトがそういう作りしてるかわかんないし。
今ぱっと思いつくだけで「ユーザーとオペレーターでブラウザ/os違ったらイベント再生してもズレちゃうんじゃないの」とか「イベント送信に欠落・追い越しとかがあったらどうすんの」とか「フォーム入力→POSTのイベントとかが複数回発生したりしないの」とか「パスワードとかの入力イベント送らないようにするにはどうするの」とか。実際のパーティ会場ではユーザー/オペレーターの環境差異はどうするんですか、という質問にはビューアー側を頑張ってなんとかしてるという回答を頂いた気がします。嘘言ってたらすみません。イベント送信に関してはよく考えたらそもそも karte 自体がそういうものなのでなんかいい感じに追い越しを並べ替えたりとかできるのかもですね。多少のイベント欠損はなんとかなる気もするし。そういえばパスワード入力フォームとかはそもそも見えないようになんかできるって言ってたから上手いことやってるのでしょう。

あとインフラの話が結構面白かったです。AWS + GCP のマルチクラウドになっていてこの間のGCPのLB障害のときもさっと切り替えて対応できましたー、という話を聞いたのですが、そもそもマルチクラウドになってる経緯が面白かった。AWS EC2上にnode APサーバ群とmongoクラスタを組んで運用してたんだけどmongo部分がスケールせずにGCP上のマネージドサービス(最初は BigQuery 目当てだったって言ってたかな)に移行。でもすでにmongoに入っているデータから移行するのは難しいんだか後回しになってるんだか、まあ両方併用しているのが現状とのこと。うーん、歴史を感じる。
マルチクラウドで障害時にも切り替えて対応できるとはいえいくつか対応できない障害はありそうで、AWS<->GCP間のVPCとかGCPのBQ, Spannarあたりとか、上述のmongoとか外部のマネージドredisとかもだめそう。あと障害時の切り替えってどうやってるんですか？と聞いたら Route53 のフェイルオーバーとのこと。そのへん全然知らんけどそういう機能あるんですねえ……。インフラ周りの知識が浅くて困る。

というわけで参加記録です。全体的に面白かったし、空間的にもいいオフィスでした。

『[試して理解]Linuxのしくみ ~実験と図解で学ぶOSとハードウェアの基礎知識』読了

[試して理解]Linuxのしくみ ~実験と図解で学ぶOSとハードウェアの基礎知識

結構前に読了してたけど書いてなかったので書きます。

ざっというと、OS初心者向けの解説本ですね。タイトルから受ける印象とレベル感が合っていたと思います。
僕自身も適当に ubuntu 触ったりふつリナやったくらいでそんなに詳しいわけじゃないのですが、特に詰まることなく読み進められました。
本書の特徴として書名にもあるように「試して理解」という点が挙げられています。具体的なソースコードと計測結果をもとにどう動いているかを解説するコンセプトは非常に面白かったです。

github.com

(が、上記レポを見ればわかるとおりそんなに自分ではやってません……。特に興味があったところくらい)

なお、Vagrant 上で試す場合には /vagrant のような共有フォルダ上ではファイル操作がうまく動かないことがあるのでご注意ください。確か、mmap とかやってるときにうまくいかなかった。

普段はあんまり意識していないOOMの話やファイルシステムの話に触れられたのがよかったです。この次のステップとして挙げられていた本がだいたいイカツいのでどうしたもんかと困っていますが、まあ気長にやっていこうと思います。はい。

1点だけ難点をあげると、誤記がかなり多かったように思いました。正誤表もあるので、版が進むにつれてよくなっていくとは思います。なのでそんなに気にすることではないかもしれません。

RubyVM::AST を用いた Ruby 製 Ruby インタプリタを作っている話

Ruby では v2.6 から RubyVM::AST というのが入ることになりまして、Ruby ランタイム上から AST を取得できるようになります。この話は以前に書いたので省略しますが、ASTがとれるということはASTを解釈して実行することもできるわけです。やるしかないですね。

というわけでやったのがこれです。まだ全然途中ですが。

github.com

デモ

if 式を解釈できるようす

# spec/snippets/if.rb
a = true
if a
  puts "truthy"
else
  puts "falsy"
end

b = false
if b
  puts "truthy"
else
  puts "falsy"
end

$ bin/stray spec/snippets/if.rb
truthy
falsy

メソッドを定義したりできてるようす

# spec/snippets/method.rb
def foo
  puts :foo
end

foo

def bar(arg)
  puts arg
end

bar :bar

def blk
  yield 1
end

blk do |arg|
  puts arg
end

$ bin/stray spec/snippets/method.rb
foo
bar
1

進捗

プロジェクトとしての進捗はこんな感じです。今回は紹介程度に留めて、実装時に留意したことなどは別エントリに書きます。インタプリタの実装をするのは初めてだったのでいろんな壁にぶつかりながらやってます。

できること

• Integer, String, Symbol, Array あたりのリテラル
  • Float とかそういうのはちょっと面倒なんでやりません
• ローカル変数代入
• メソッド定義
  • オプショナル引数、キーワード引数はまだ
• メソッド呼び出し
• yield
• if 式
• ぼっち演算子

できないこと

• クラス定義
  • サボってます
  • rb_cClass とかの定義を見てそれに合わせないとダメなのはわかってるんだけどオレオレ実装してしまったので修正が面倒……。
  • 当然継承とか include とか extend とか using ( refinements )とか
• Kernel モジュール、Objectクラスに定義されてるだいたいのもの
  • 実装するのがめんどくさくて puts くらいしかやってない
• case 式
  • === をちゃんとするのが単純にめんどくさそうでやってない
• lambda とか

ちょっと外れた話

cruby のソースを読んでたらフォーマットが他と違うところを発見したのでPRしました。

Use nd_X shorthand for annotation by hkdnet · Pull Request #1901 · ruby/ruby · GitHub

また、実装していると NODE_DEFN から nd_mid を取れないことに気づきました。 NODE_DEFN は def foo; end のようなメソッド定義を示すノード種別です。nd_mid はメソッド名に対応するシンボルです。先程の例だと :foo という情報です。これがないとなんのメソッドを定義したのかわかりません。 twitter で y.kaneko さん( @spikeolaf )に質問したら快く修正してくれました。

hkd氏におどされ、なくなくコミット。

— y.kaneko (@spikeolaf) June 28, 2018

新しい機能を実際に使ってみた結果をフィードバックをする人はたぶん少ないので意味がありそうですね。

オフラインリアルタイムどう書く E25 の解答

qiita.com

オンライン参加で解けました。17:02なので45分くらいでしょうか。

#yhpg とけたー

— はくどー (@HKDnet) July 7, 2018

方針としては、たかだか200x200マス = 40000通りなので、スタート地点以外の1点を選んでベクトル作ってベクトル回して伸ばして座標が盤面内にあるかどうかを確認するので間に合いそうです。おわり。

というのを問題をみて3分くらいで決めたんだけど、回転下手なのと盤面の境界条件を間違えるといういつもので苦戦してました。 というわけでコード。割と汚めです。

class Solver
  def initialize
  end

  def solve(input)
    w, h, str = input.split(',', 3)
    @w = w.to_i
    @h = h.to_i
    x, y = str.scan(/\d+/).map(&:to_i)
    answer = {}
    s = [x, y]

    @w.times do |sx|
      @h.times do |sy|
        v = [sx - x, sy - y]
        ps = points(s, v)
        if ps.all? { |p| valid?(p) }
          l = len_of(v)
          answer[l] ||= []
          answer[l] << ps
        end
      end
    end

    m = answer.keys.max
    if answer[m].size == 1 && m != 0
      answer[m].first.map { |p| "(#{p.first},#{p.last})" }.join(",")
    else
      '-'
    end
  end

  def len_of(v)
    Math.sqrt(v.first**2 + v.last**2)
  end

  def valid?(p)
    (0...@w).include?(p.first) && (0...@h).include?(p.last)
  end

  def points(s, v)
    sx, sy = s
    a, b = v
    p1 = [sx + a, sy + b]
    p2 = [p1.first - b, p1.last + a]
    p3 = [p2.first - 2*a, p2.last - 2*b]
    [p1, p2, p3]
  end
end

リファクタリングしたのでこっちのがみやすいかも。あとサイズ小さいやつとか見る意味ないじゃんって気づいたので途中で next いれるようにしました(max_l あたり)

class Solver
  Pair = Struct.new(:x, :y) do
    def add(other)
      Pair.new(x + other.x, y + other.y)
    end

    def sub(other)
      Pair.new(x - other.x, y - other.y)
    end

    def multi(s)
      Pair.new(x * s, y * s)
    end

    def rotate270
      Pair.new(-y, x)
    end

    def to_s
      "(#{x},#{y})"
    end

    def size
      Math.sqrt(x**2 + y**2)
    end
  end

  def solve(input)
    w, h, str = input.split(',', 3)
    @w = w.to_i
    @h = h.to_i
    x, y = str.scan(/\d+/).map(&:to_i)
    answer = {}
    s = Pair.new(x, y)
    max_l = 0

    @w.times do |sx|
      @h.times do |sy|
        v = Pair.new(sx, sy).sub(s)
        next if v.size < max_l
        ps = points(s, v)
        if ps.all? { |p| valid?(p) }
          l = v.size
          answer[l] ||= []
          answer[l] << ps
          max_l = l if l > max_l
        end
      end
    end

    m = answer.keys.max
    if answer[m].size == 1 && m != 0
      answer[m].first.map(&:to_s).join(",")
    else
      '-'
    end
  end

  def valid?(p)
    (0...@w).include?(p.x) && (0...@h).include?(p.y)
  end

  def points(s, v)
    p1 = s.add(v)
    p2 = p1.add(v.rotate270)
    p3 = p2.sub(v.multi(2))
    [p1, p2, p3]
  end
end

TaPL読書録 #5

前回: hkdnet.hatenablog.com

今回は6章まるごと。

アルファ変換を許可する、というのは第5章で学んだが、しかし変数名が重複してるんだっけ？という疑念は常につきまとう。特に理論的な部分ではなく実装するという観点においては「標準の」の表現を定めておいたほうがいいとうことで デブルーイン ド・ブラウンの de Bruijn index という概念を導入してがんばるよ、という章である。

p.57
手法(4) の「明示的代入」とはなにか？がよくわからなかった。"explicit assignment" か？と思いググってみたがそれっぽいのが見つからず……( "explicit assignment lambda calculus" でぐぐった)。その場では放置したが後日論文から引けばいいのか、と思って著者から検索したら以下がヒット。 explicit substitution だったらしい。

http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-54.pdf

p.59 \w. y w -> \. 4 0 なのが初見殺しっぽい。ラムダ内なのでシフトが起きていて、名前付け文脈Τにおいて y = 3 なのに 4 になっている。

p.59 演習 6.1.5
ここの問題により「同じ名前がでてきても大丈夫であること」が確認できたとの声あり。

p.59 最終段落
[1 -> s](\. 2) の元になる de Bruijn index を用いない表現を考えられるか？という問題で僕が「これでしょ〜」って提示したのが間違ってて死亡。
提示したのは T: z => 2 という名前付け文脈における \x. -> x z だったのだけどこれはラムダ内に入るときにシフトが起きるので T: z => 1 における、 \x. -> x z が正しい(直後に書いてある)。

演習問題としてはやるだけが多かったのでさくさく進み、やるだけじゃないのが出てきたときはみんな「わからん」と言っていたのでアレだった。
さくっと答え合わせしたものを以下に書いておく

ex 6.2.3 -> スルーした
ex 6.2.6 -> 代入しても中でラムダができた場合との増減で相殺するからそうなるんじゃないの、とのこと
ex 6.2.8 -> スルー ex 6.3.1 -> 「0があってもラムダがあるのでセーフ」という走り書きが残っている
ex 6.3.2 -> ラムダの数をLとした場合に de Bruijn index i と de Bruijn level l について l = L - i として変換すればﾖｻｿｳ

次回7章全部。7章の末尾には「実装したからといって、理解したとは限らない」という挑戦的な文言が載っていることに注意。