giantneco’s blog

技術メモ

ScalaMatsuri2018 3日目 メモ

Scala Matsuri 2018 の 3 日目。この日はアンカンファレンス形式だった。

結局圏論が理解出来なかった俺達の復習

圏論の話。 圏論を学ぶ理由として、「抽象」の見方が変わるという話があった。

  • proper value -> 即値みたいなもの
  • first order value -> \x -> x + 1
    • OR function
  • high order value(function)

  • 圏論がなぜ良く出てくるか

    • 上記のものを型でやる
  • proper type = 値を入れることができるもの

  • 型コンストラクタ = 1 order kinded type
    • 型は
      • 数学的には「*」と書くことが多い
      • Scala 的には「A」とだけ書いたり
    • Option の型
      • F[A]
      • * -> *
    • Either
      • F[A1, A2]
      • `* -> * -> *
    • Functor
      • `( -> ) -> *``
      • 高カインド型
      • 型コンストラクタを受け取る型コンストラクタ
      • F[G[A]]
  • Scala は higher kinded type を扱えるので、より関数型言語っぽいことができる
    • See 型システム入門
  • parametricity -> 多相性のひとつ?
  • 圏論を学ぶ理由
    • 少しかじると大切なことを学べる
    • 「抽象」が抽象的でなくなる
    • 圏論的な「抽象」
      • 圏論の公理を使って組み立てること
  • Product, 積 -> tuple, Co Product, 余積 -> Either

依存型プログラミング入門

Idris は Haskell ベースの関数型言語で、

  • 次の点でHaskell と違う
    • default eager evauation
    • type annotation
    • etc
  • 機能
    • Dependent type
    • Type depends on value 型の中に値を持っている
    • types are first class
    • Proof with dependent type

Idris 入門

  • Vect 型
    • list which contains number of elements in this type
    • Vect n a
      • n: number of elements
      • a: type of elment
      • Vect : Nat -> Type -> Type
      • Nil : Vect 0 elem

Vect に対する tail 関数は次のようになる

my_vect_tail : Vect (S n) a -> Vect n a
my_vect_tail (x :: xs) = xs

Vect に対する zip 関数は次のようになる

my_vect_zip : Vect n a -> Vect n b -> Vect n (a,b)
my_vect_zip [] [] = []
my_vect_zip (x :: xs) ( y :: ys) = (x,y) :: my_vect_zip xs ys

これだけで定義完了。 長さが等しいことをコンパイラがしっている

index 関数

my_index : Fin len -> Vect len elem -> elem
my_index FZ (x::xs) = x
my_index FS (x::xs) = index k xs
  • Fin len とすると、 0 以上 len 未満になる
  • my_index never fail

実際に my_vect_zip を呼ぶ際には、ユーザ側で引数のVect同士の長さが等しいことを示してあげる必要がある

ここらへんあまり追えてないが、EqNatというものを使ってどうにかしていた。

data EqNat : (num1 : Nat) -> (num2 : Nat) -> Type where
     Same: (num : Nat) -> EqNat num num
  • EqNat のコンストラクタは Same のみ
  • Same では型引数はひとつしかない。
  • -> EqNat の型引数 num1 と num2 は同じもの

以上のような自分でzip関数を書いてみるのはチュートリアルのなかであるらしい。

実践ScalaでDDD(改訂版) @crossroad0201

Scala での DDD の話。

たこ焼き屋に並んでたため、途中からしか見てない…

  • データと動作を分離させる
    • implicit で動作を分離させる
  • コーディング
    • 名前をちゃんとつける
    • prefix で型を知らせる (ex. maybeUser で option に包んだ User とか)
    • formatter を使う
  • レイヤー
    • 依存性の逆転を使う
    • Onion Architecture
      • Clean Archiitecture, Hexagonal Architecture
      • 原理は一緒(と思われる)
  • Error Handling
    • 例外は基本使わない。 Option を使う

DDD compmonents by Scala

  • Application Service
  • Entity
    • 1 Entity in 1 Aggregation
  • Value Objects
    • type alias
    • extens AnyValue
  • Role
    • DDD にはないモデル
    • リレーションを拡張する仕組み
    • 例えば、ユーザにたいして Author という関係が惹かれていた場合、 User にメソッドを入れるのではなく、Author とうロールを作って、 そこにメソッドを追加したい
    • implicit でうまくやる

Scala Design Patterns @gakuzzzz

Scala でのデザインパターンの話。

  • Builder Pattern → Scala では必要なし
    • 条件に合わない初期化をコンパイルエラーにする Type-safe Builder Pattern は finagle とかで使われている
  • Concept Pattern → 型クラス
  • Loan Pattern
    • リソースのクローズなど、処理忘れをしたくない時にやる
      • 言語機構としては try, finally
  • a la carte import
  • Aux パターン

あと3日でJava 10がリリースですが、興味ある人いますか?

Java 10 の話。

Java 10 はとりあえずいれてみた。 Docker aware になるのは 10 からで、それまでどうやってたか気になって調べたが、cpu を指定するオプションがあるもよう。

Dottyの新機能 @amaya382

Dottyの話。型推論が賢くなるのはいいね。

ScalaMatsuri 2018 に参加してきた (2日目)

今年で参加4回目のイベント。 それほど Scala は書いていないが、関数型言語、DDDあたりの話を聞きに行っている。

今回は 3 日間の開催で、1 日目はトレーニングデー、2 日目は普通のセッション形式、3 日目はアンカンファレンス形式になっている。 1 日目は不参加(あるのに気付いてなかった)で 2, 3 日目に参加した。

以下は 2 日目のメモ、ただし後から調べたこともちょっと入っている。

Why Composability matters @gakuzzzz

http://gakuzzzz.github.io/slides/why_composability_matters/

Scala と他の言語を分けるのは Composability。 Composability は同じ概念の異なる要素を特定の方法で組み合わせて同一概念の別要素を作ること

このセッションでの定義として、「Composability が高い」という場合は合成する手段が多いということを指す。

では、なぜ「Composability が高い」と嬉しいかというと、分割統治をするのに複数の手段があるということになるから。

Functional Performance @mjpt777 Martin Thompson

関数型言語の向けのパフォーマンスの話。とはあったが関数型言語でなくても通じる話だと思う。 メモリあたりの低レイヤの話から、関数型言語向けのデータ構造の話まで出てくる。

資料に出ていた Unified Reservation Station が気になって調べたが、これは命令のアウトオブオーダー実行のための仕組みで、キューに溜まった命令に対して必要なオペランドが揃ったら実行される。 1GB の long 配列の和を Haswell 上で計算する例に出されているが、 周波数を3GHzとして、1サイクルは0.3 nsで、マニュアルをみると 256bit のロード・ストアは 1 サイクルで済むように書いてあるので、 うまくキャッシュに乗っていればベンチマーク結果にある 0.83 ns/op というのもすごく有り得そうな数字に見えてくる。

パフォーマンスのための式としてM/D/1の待ち行列式と、Universal Scalability Law が紹介されている。

M/D/1 の待ち行列{ \displaystyle
\begin{align}
r = \frac{s(2 - \rho)}{2(1-\rho)}
\end{align}
}

USL { \displaystyle
\begin{align}
C(N) = N/1 + \alpha (N - 1) + \beta N (N - 1)
\end{align}
} 個人的にはアムダールの法則をよく使うが、コヒーレンシを考える必要がある場合はこっちのほうが適当か。

CRDTs

モダンな分散環境ではメッセージのやり取りに TCP より UDP の方が向いている。 ただし UDP によるメッセージングだと順序の保証がないので、データ構造も良く考える必要がある 関数型言語が使うデータ構造だと skip list, tree, scoreboard があるが、実装としてはポインタの参照地獄になってしまう。 Immutability のため、また Concurrent Tree Update をしようとすると Path Copy をすることになってパフォーマンスが問題になる。またガベージコレクションも大変になる。

そこで CRDTs = Conflict-Free Replicated Data Type

CRDTs は時間効率、空間効率ともによいデータ構造 CRDTs には 2 種類あり、オペレーションをコピーする CmRDT = Commputative Replicated Data Types とステートをコピーする CvRDT = Convergent Replicated Data Types

CmRDT * オペレーションを複製 * オペレーションは可換 * オペレーションはべき等でない

CvRDT * ステートを複製 * ステートアップデートは単純増加 * つまり追記のみで、削除には特別な操作が必要 * マージ処理は結合的,可換,べき等

Aeron の Log Buffer が上記の CRDT になっているらしく、オペレーションが中断した場合なども

Publishers, Senders, Receivers, Subscribers が単調増加だけするカウンタを持っていてる。 ステートを持つのは悪かもしれないが、単調増加だけする場合は許容できる。

Monad Transformaers Down to Earth , Gabriele Petronella

モナド変換子の話。モナド変換子自体は前から知っていたが説明が抜群にうまかった。見習いたい。

型クラスが入れ子になっているときは Monad の flatmap を使う。

flatpmap: F[F[A]] -> F[A]

なら異なる型クラスで包まれていたら?モナド同士は合成できないので困ったことになる。

F[G[A]]

こういう場合に使うのがモナド変換子で、合成の代わりに変換をする。

F[G[A]] -> GT[F[_], A]

モナド変換子はモナド名+Tという名前にする(Option モナドならモナド変換子は OptionTになる)

実用的な圏論入門 @DanielaSfregola

圏論のハンズオン。途中から別のセッションを聞きに行った。 かなり初心者向けで、手を動かしながら聞けるのでわかりやすい。

Building Distributed System with Akka @anildigital , Anil Wadghule

分散システムと Akka の話。

  • 背景
    • size of internet growing
    • concurrent connections, big data, respoinse time
    • high require
    • reactive prinsiples
  • Distrubuited system をスケールさせるには
    • 読み込みの複製
      • 複雑、一貫性に問題
    • シャーディング
      • これも複雑、データモデルに制限
    • Consistent Hasing
  • CAP 定理
  • Distributed computation strategy
    • fault tolerant system
    • Resilence
  • Akka
    • Actor model on JVM
    • 方針として「Let it crash」
      • Normal flow and Fault recovery flow

Scalaらしいオブジェクト指向プログラミング @tototoshi

Scala でのオブジェクト指向プログラミング Tips。 Scala には合成の方法が複数があるが、それぞれ長所・短所がある。

ScalaJava に対して Immutability と Composability へのサポートが多くて、 Case クラスや、 trait を使える。

  • Case Class
    • 代数的データ型として使える
  • trait
    • Java の interface に相当。 mixin や cake pattern に使える
  • object

DI についても Scala では次のような手法がある * コンストラクタインジェクション * コンストラクタで渡すパターン * Cake Pattern * with句でtraitを渡していくパターン * 関数型プログラミングスタイルなら Reader Monad, Free Monad + tagless final

Extensible Effects in Dotty @halcat0x15a

Dottyの新機能と、Dotty で使えるようになる Extensible Effects の話。 この日のセッションのうち一番話が難しかった。 正直このあたりの話はあまり理解できているとは言いがたいので、手を動かして確認したい。

Dotty は Scala の新しいコンパイラで DOT = Dependent Objectt Types という理論に基づいている。その新機能のひとつに Extensible Effects で使う Open Union がある。

Extensible Effects は複数の操作?を効率的に合成してくれるもので、モナド変換子をネストして使った場合にパフォーマンスが落ちる問題を解決してくれる。

この Extensible Effects に至るまでの話が複雑で、まず Free Monad が出てくる。 Free Monad は Functor を Monad にしてくれるが、Functor にしか適用できない。 これに対して Coyoneda を使って Functor 以外にも適用できるようにしたのが Freer Monad。 ただし Freer Monad は flatMap を複数回適用するため重いという問題がある。 これを解決するために Type-Aligned Queue というものを使って、 早くしたのが Fast Freer Monad。 で、Open Union に Fast Freer Monad を適用したものが Extensible Effects であるらしい。

話の流れだけはなんとなく把握したが、実際どういうことをしているのかがわかっていない。

システムパフォーマンス勉強会第8回

www.slideshare.net

社内で行ったシステムパフォーマンス勉強会の第8回。 下半期で終わらせるつもりだったので、一通り重要そうなところはよんだということでとりあえず終わり。

全体としてコードを書く時に知っておくと良いことも多々あったが、全体としてはパフォーマンスエンジニア向けの内容だった。 正直作った後のチューニングとか、機器選定とかインフラ周りとか自分はあまりやらんだろうし。

また社内でやった意味もあったと思う。メモリとかCPUとか低レイヤだが知っておいたほうがいい知識と、並列処理まわりのパフォーマンス関連の話が多少でも共有できたのは良かったと思う。 もうちょっと人を集められるとよかったが…

4月からはなにやろうか?

システムパフォーマンス勉強会第7回

社内で行っているシステムパフォーマンス勉強会のメモ。

今回は詳解システムパフォーマンスの 9 章ディスクを対象にしている。

勉強会中に出た話としては:

  • ディスクのモデル
    • シンプルディスクとキャッシングディスク
  • コンセプト
    • 計測時間
  • サービス時間、待ち時間、応答時間
  • キャッシング
  • ランダムI/OとシーケンシャルI/O
  • 飽和
    • ディスクデバイスの場合はOSのデバイス待機キューの平均長になる
  • 同期I/O と非同期I/O
  • アーキテクチャ
  • メソドロジ
    • ツールメソッド
      • 使用するツールは iostat, iotop, stap, perf など
    • USE メソッド
      • 使用率はデバイスがビジーだった時間
      • 飽和はI/Oがキューで待機している度合い
      • エラーはデバイスのエラー
      • 最初にエラーをチェックする
        • ディスクはエラーがあった場合に縮退運転するのが一般的なため

これまであまり知らなかった点がある一方で、 普段アプリを作る上で意識する点がそれほど多くなさそう。

最新コンパイラ構成技法 #1

色々復習したいことがあり、最新コンパイラ構成技法を読むことにした。

ここしばらくの作業だとコンパイラのフロントエンド部分しかしていないし、 さらに言うと機能追加が主な作業で既存のコードにちょくちょく修正を入れるだけで それほどコンパイラ屋らしい仕事はしてない。 (仕事としては一区切りついたので、この件についてもそのうちまとめたい)

かなり怪しい部分もあるので一通り読みたいところではある。

第1章では次のようにおおまかなコンパイルの流れについて説明している。

  • 字句解析
  • 構文解析
  • 意味動作
  • 意味解析
  • フレーム割り付け
  • 翻訳
  • 正準化
  • 命令選択
  • 制御フロー解析
  • データフロー解析
  • レジスタ割付け
  • コード生成

この分類だと、ここ最近の仕事ではいわゆるコンパイラフロントエンドと呼ばれる字句解析から意味解析までを中心に扱っていた。 また意味解析はあまり聞き慣れない用語で、構文解析に含まれるんじゃなかろうかとも思う。 フレーム割付けからは下は概念としては知っているが、実際に手を動かしたことがあったかどうか。 動くものが作れれば嬉しい。

実装に使う言語をどうしようかちょっと考え中。本は ML 使っているが、OCaml にするか、それともいっそ Haskell にしてみるか…

システムパフォーマンス勉強会第6回

www.slideshare.net

社内で行ったシステムパフォーマンス勉強会の第6回。

社内機械学習勉強会#5

www.slideshare.net

社内で行っている機械学習勉強会の自分担当回。 内容はタネ本にしている詳解ディープラーニングの4.5という狭い範囲なので楽だと思っていたが、 本に書いてある説明だとよくわからないことが多く結局元の論文読んでみるなどして結構詰まった。

数式のこの部分がどういう意図でそうなっているのか、というのは未だによくわからない部分がある、 あと指摘されたのは: - アイディアの元になったアナロジーを理解しておくと理解に役立つ - 二階微分は難しいので近似していることに注意

一応コードも書いて、手元では実験もしていたがあまり見せる機会がなかった。 MNISTを対象にしていると大抵それなりの精度が出るので、 この手法じゃないとうまく行かないデータとかがあったりするといいんだろうか。