今週のまとめ (2017/6/9)
ネタがないので短い記事です。
- C言語の構文ミスをディープラーニングで治す論文 https://www.aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14603
- seq2seq でエイとやっているようだが知識がないので詳しくは不明
- Rustのマクロ入門 https://danielkeep.github.io/practical-intro-to-macros.html
- Clojureのcore.asyncによる並列処理 http://eli.thegreenplace.net/2017/reducers-transducers-and-coreasync-in-clojure/
今週のまとめ (2017/6/2)
プログラミング言語
libtins: C++ packet crafting and sniffing library
C++ でパケットをパースしたり生成したりするライブラリ。色々なレイヤーでのプロトコルを解析・生成できる。pcapの読み書きなども可能。
Rust from Scala
〇〇言語利用者から見たRustシリーズ Scala編。
MoonScript: a programming language that compiles to Lua.
MoonScript, a language that compiles to Lua
AltLua。言語としては CoffeeScript に近く、Python や Ruby の影響を受けている。
Imperative Haskell
HaskellにおいてSTモナドで命令言語的にクイックソートを実装してみた記事。
Tour of an open source Elm SPA
Elm で Qiitaのような情報共有サイトを SPA で実装したデモ。Elmについて 個人的には Farewell to FRP したのが悲しくてまだ引きずっている
アルゴリズム
A C++ library of Concurrent Data Structures
主に lock-free な各種並行データ構造の実装。論文リスト付き。
A GENERATIVE APPROACH TO SIMULATING WATERCOLOR PAINTS
水彩画のようなテクスチャをアルゴリズミックに生成する方法について。ソースは Quil という Processing を Clojure でやるものを用いている。
Web
A list of everything that could go in the
HTML の <head> に書くもの一覧。HTML自体の仕様にあるものから、Twitter Cards 等に対するサイト説明や特定のブラウザでの挙動指定まである。
数学
Elliptic curves as Python Objects
楕円曲線上の演算を Python の演算しオーバーロードを用いて実装する。
usl4j And You
スケーラビリティに関する数学的モデルについての考察。「リトルの法則」は待ち行列理論の文脈で聞いたことがあるがもっと踏み込んだ Universal Scalability Law という法則について考察している。
以下も参考になる。 How to Quantify Scalability
ひとこと: ReDoS について
今週 Atom を使っていたら突然固まって落ちるという現象があり、調べてみたら、検索で正規表現のバックトラックの数が膨大になり計算が止まらないという事態になっていたことがわかった。つまり邪悪な正規表現を入れた自分が悪かった。
こういったバックトラックが爆発することを Catastrophic Backtracking というらしく、またセキュリティの文脈においてはこれを利用してサービスを停止させる ReDOS (Regexp DoS) という攻撃があるらしい。
日本語の文献は以下が参考になる。*2
- 正規表現を使ったDoS – ReDoS | yohgaki's blog
- ReDoSの回避 | yohgaki's blog
- 正規表現でのメールアドレスチェックは見直すべき – ReDoS | yohgaki's blog
上にもあるように StackExchange がサービス停止した事例や、 Express.js の脆弱性 といった事例もあり、正規表現の取り扱いには気をつけたほうがいいということを認識した。
対策としては、
- (任意の)正規表現を入力として利用するシステムは絶対に作らない。
- Catastrophic Backtracking を起こす正規表現を用いない。
- 起こすかどうかを検査したり解析したりするツールもある
- 長い文字列を正規表現にかけない。
- Catastrophic Backtracking を起こさない正規表現エンジンを用いる。
- https://github.com/google/re2 は線形時間でマッチが終わるように作られている(らしい)
- Go は re2 が標準ライブラリにある言語です
等々。
*1: from:ヘンペルのカラス - Wikipedia image: https://www.flickr.com/photos/90678392@N00/305302998
*2: これらが十分詳しいのでこれをネタにして記事書いたろという気持ちがなくなってしまった
今週のまとめ (2017/5/26)
5月も終わりですね…え？
プログラミング言語
System Programming in Rust: Beyond Safety
https://www.sigops.org/hotos/hotos17/papers/hotos17-final92.pdf
VMWare Research が出した、Rustの紹介論文(draft)。システムプログラミングの視点から語っている。
ところで Rust を Linear Type の言語と言っているが正しいのだろうか…？ *1
Haret
Rust製の分散合意形成フレームワーク。使いやすさに重点を置いているらしい。使用アルゴリズムはViewstamped Replicationとのこと。
Practical Deep Learning in Haskell
GitHub - HuwCampbell/grenade: Practical Deep Learning in Haskell
Haskell製のニューラルネットワーク。デザインはシンプルながら自由度が高く、逆伝播はもちろんのことRNNやGANも書ける。
以下の理論も参照すると良い。 blog.jle.im
c2goasm
C言語からGo言語へのアセンブリへ変換するツール。開発動機は C/C++ with SIMD で書かれたツールをGoに移植するために作ったとのこと。
Understanding Virtual Tables In C++
C++のオブジェクトシステムでつまづきやすいvtables に関する解説
retries: A tiny Rubygem for retrying code with randomized, exponential backoff.
exponential backoff について調べたときに出てきた Ruby のライブラリ。exponential backoff とは、要求が失敗しリトライをする際に 2^k (kはリトライした回数) 分の sleep を入れる制御機構。イーサネットで使われている。
アーキテクチャ
How to Build a Non-Volatile Memory Database System
最近 Intel が不揮発性RAMを組み込んだやつを出したが、そういうのはどこで使うのという疑問に答えるもの。
ツール
Git Town
Gitコマンドを拡張する。masterを取ってきてブランチする git hack や ブランチを進行中の変更とともに更新する git sync などがある。
ひとこと
コメントに疲れが出ている。
今週のまとめ (2017/5/19)
ぞい。
プログラミング言語
Constrained Category
ハードウェアや自動微分などの概念の解釈(interpretation)を、圏 (デカルト圏) の言葉に翻訳してコードに落とし込むという技法 (論文：http://conal.net/papers/compiling-to-categories/) のサンプルコード。Deep Embedded な DSL の代替となるらしい。(が、論文もコードも難しくてわからなかった)
アルゴリズム
keon/algorithms: Minimal examples of data structures and algorithms in Python
Pythonによるアルゴリズム・データ構造の「図鑑」。165個ある。競技プログラミング向けか。
Web
Choo: sturdy 4kb frontend framework
Webフロントエンドのフレームワーク。今やフロントエンドフレームワークのデファクト・スタンダードとなった Virtual DOM ではなく実際の DOM で差分計算をするnanomorphというのを使っているらしい。
WebGL Fundamentals
WebGLの入門サイト。解説の図や例が豊富。 WebGLとは何かという基礎の基礎から、(GLでは面倒な)文字の出し方やアンチパターンなどもカバーしている。
機械学習
Picasso: A CNN visualizer
畳み込みネットワークの可視化。解説記事 によると、ネットワークの内部状態を可視化することにより数値の指標(検出率等)では分からない「誤解」を調べることができるという利点をあげている。
関連して、手書き認識のCNNのWebでの綺麗なビジュアライゼーションデモを紹介しておく。
データベース
Badger: Fastest key/value store in Go.
Introducing Badger: A fast key-value store written natively in Go - Dgraph Blog
Repos: github.com
Go言語で書かれた Key/Value ストア。Log-structured merge (LSM) ツリー を用いてキーを格納するが、値はその上ではポインタとして保存しておき、値自体は値ログという場所に分離しておくことにより効率を良くしている。値ログへのアクセスのため、この設計はランダムアクセスが高速で可能な SSD に最適化されたものとなっている。
simdb: A high performance, shared memory, lock free, cross platform, single file, no dependencies, C++11 key-value store
Lock-free な Key-Value store。詳しくは読んでいない。SIMD要素はlock-freeでのcompare-exchangeをまとめてやる部分か？(不明)
今週のまとめ (2017/5/12)
前回はおやすみでした。
プログラミング言語
Categorical Semantics for Dynamically Typed Programming Languages
Categorical Semantics for Dynamically Typed Programming Languages
「動的型付言語の圏論的意味論」というタイトルの短い論文。「単純型付ラムダ計算がデカルト閉圏(CCC)に対応する (Lambek)」というのはプログラミングをする上ではもはや知らなければ恥ずかしいレベルの常識であるが、じゃあ型無しラムダ計算の場合はどうなるの？という疑問に答えている。短い論文で歴史的なオーバービューの側面が強いが、参考文献から参照することができる。
A true heterogeneous container in C++
A true heterogeneous container in C++gieseanw.wordpress.com
C++ で任意の型のデータが格納できるコンテナを実行時型情報を用いずに作ったもの。TMPとC++14/17の機能を用いて実現している。 std::visit などは初めて知った。
CPU Utilization is Wrong
プログラムのパフォーマンスを評価するときには、stall-waiting も含まれる CPU使用率ではなくIPC(Instruction per Clock)を見るべきという論説。そうすることによって、問題がメモリバウンドかCPUバウンドか分かるようになる、と主張している。
セキュリティ
[PDF] Quick introduction into SAT/SMT solvers and symbolic execution
SAT/SMTソルバとシンボリック実行の入門書。未だ草稿らしいが、内容は豊富である。典型的な数独等のパズルを解くものから、簡単なデコンパイラを作りその検証をZ3で行うと言った高度なものまである。シンボリック実行については LLVM の シンボリック実行ツール KLEE の解説に一章割かれている。 筆者は Reverse Engineering for Beginners で有名であり *1 、そういった話題が多い。
Linux Kernel Exploitation
近年の Linux カーネルに存在した脆弱性についてのまとめ。それぞれの脆弱性の発見手法や報告の他に、ファジングや検出・exploitツール、CTFのwriteupなども紹介されている。
機械学習
Data Version Control
機械学習での開発においては前処理→学習→評価などの幾つかの段階を経ることが普通であるが、それらの依存関係を解析し、自動的に処理フローを実行できるようにするといった趣旨のビルドツール。 コードやデータの変更に対しても容易に適応できるような設計を売りにしている。
Deep Learning AMI — Amazon Web Services
AWSでディープラーニングをするときに役立つ公式イメージ(AMI)。設定済みの TensorFlow, CNTK, Caffe, Caffe2, Theano, Torch, Keras 等が使用できる。 どうでもよいが、Theanoだけロゴが見えないのかわいそうである。
数学
Coding The Matrix と線形代数
情報工学のための線形代数の講義のサポートページ。本(有料)やスライドやソースコードなどのリソースが置かれている。また、情報工学における線形代数の応用例についてもいくらか説明されている。
ところで、情報工学のための線形代数のリソースは巷に多くあるが、個人的には以下の講義資料『産業応用のための基礎数理』が面白いと感じた。
内容はスペクトル分解やノルムや特異値分解など一歩進んだ線形代数の内容であるが、「産業応用のための」とあるように、画像処理や信号処理などの実際の応用においてそれらがどのように役に立つか分かるような構成になっている。
*1: 自分でも言っている / “As of 2013-2017 I mostly known for “Reverse Engineering for Beginners” free book.” https://yurichev.com/
*2:4章以降はリンク切れに見えるがURLをいじれば(数字をインクリメントすれば)見ることは出来る
今週のまとめ (2017/4/28)
4月も終わり (ここで家賃振込みを忘れてたことに気づき書くのを中断し銀行へ行く) ですね。
プログラミング言語
Monads to Machine Code
Haskell で LLVMライクな中間言語から x86 の命令を出力する JIT コンパイラを作る記事。それぞれの命令解説があるのでx86の知識がなくても読める。
Helix: Native Ruby Extensions without Fear
Helix: Native Ruby Extensions Without Fear
Rust で Ruby拡張を書くためのライブラリ。Ruby では高速化などの目的で C で拡張を書くことが多々あるが、 Rust もこの目的として使えるようになる。Rust の マクロ機能を用いてより直感的に書きるようになっており、Rust コードで定義したクラスを Ruby でバリアフリーに使うことができる。
Bonobo: data-processing for humans | Python 3.5+
Python3.5のためのデータ処理フレームワーク。Python3 の言語機能を取り込みよりモダンな設計になっている。 開発中のため現時点で利用は推奨されていない。
Kaitai Struct
バイナリ構造をパースするライブラリ・フレームワーク。 バイナリフォーマットを KSL というマークアップ言語で書くと ( GIFでの例 ) 、バイナリデータが構造体やオブジェクトにマップされるようになる。対応言語は、C++, C#, Java, JavaScript, Perl, PHP, Python, Ruby。 KSLを直接各言語のコードに変換するコンパイラやビジュアライザ、Webで動作するIDEなども提供されている。
また、Githubレポジトリ には、画像フォーマットからネットワークプロトコルまでいろいろな KSLでの定義がある。
アルゴリズム
C++ implementation of a fast and memory efficient HAT-trie
HAT-trie木 *1 の C++による実装。HAT-trie木は空間計算量が良い木で連想配列などに用いることができる。 この実装は pure HAT-trie 木の実装で、もっと効率の良い hybrid HAT-trie 木は “may arrive later” とのこと。 Cによる実装は既にある。
セキュリティ
Referrer Policy
See also: Referrer-Policy - HTTP | MDN, Referrer を制御する - Qiita
サイトから出ていく際に付く Refererヘッダ (遷移先のサイトに遷移前のサイトのURLを追加する)をどのように扱うかを制御することができるヘッダ Referrer-Policy についての説明。*2 それぞれの設定項目に対して丁寧に場合分けされている。残念ながら現在 Referrer-Policy を利用できるブラウザは少ない (Firefox等)。
このブログ筆者が運営しているサービスに securityheaders.io というのがある。サイトのセキュリティヘッダが設定されているか確認でき、ランクが付けられる。
securityheaders.io
某大のポータルサイトがF判定だった
Top 10 Developer crypto mistakes
Top 10 Developer Crypto Mistakeslittlemaninmyhead.wordpress.com
「プログラマが暗号にして最も起こりしやすい10の誤り」。目次を引用すると、
データベース
CMU 15-721
Advanced Database Systems
カーネギーメロン大学のデータベースの講義。講義のスライドとビデオ、また参考文献となる論文が公開されている。 DBMS の実装においての並列モデル・データレイアウト・データ圧縮・最適化などを論文を参照しながら行う。
*1: http://crpit.com/confpapers/CRPITV62Askitis.pdf
*2: 前者は Referer で、後者は Referrer。非常にややこしい
*3: HMACなどを使おうという話らしい
今週のまとめ (2017/4/21)
今週のまとめのリンクは iCloud のメモ帳で管理しています。iPhone からの保存が楽なので…
プログラミング言語
cmacro – Lisp macros for C
C言語で高機能な衛生的マクロを実現する(前)処理系。記法は sweet.js (JSにマクロを導入するもの) ( の以前のバージョン *1 ) のものに近い。
Why ML/OCaml are good for writing compilers?
Why ML/OCaml are good for writing compilers
なぜ ML や OCaml でコンパイラが書かれているかの理由についての投稿。1998年の文章だが、2017年の今でもそれらコンパイラの実装言語としてよく使われており、その理由はここに書かれているものとほとんど変わらないと考える。
目次？: 1. ガベージコレクション 2. 末尾再帰の最適化 3. MLのデータ型はコンパイル処理において扱いやすい。 4. MLのデータコンストラクタは AST の扱いを楽にする。 5. 安全性 6. MLは再帰的構造が特徴である問題領域（定理証明等）に対して設計された 7. 例外 8. 型推論 9. 構文解析器ツールキットの存在 (yacc/lex/burg) *2 10. 実行速度 11. サポート *3 12. ライブラリ 13. モジュールシステム
Ruby 2.4 のハッシュテーブル高速化を理解する
Ruby 2.4 のハッシュテーブル高速化を理解する // Speaker Deck
題意の通り。ハードウェアでのデータの局所性に着目し高速化を行ったとのこと。
機械学習
Paperspace Machine Learning
機械学習(主に深層学習)に特化したクラウド計算サービスで、GPUを提供している。時間毎課金。競合として AWS [pg]2.xlarge との比較表が載っている。*4
インフラ
aws-fpga
AWS には FPGA を提供する F1 インスタンス ( https://aws.amazon.com/jp/ec2/instance-types/f1/ ) がある。これはそのための HDK (Hardware Development Kit) と SDK。合成の部分は vivado を使っているのでライセンス?が必要。
AWS Codestar
New- Introducing AWS CodeStar – Quickly Develop, Build, and Deploy Applications on AWS | AWS Blog
AWS 上でのアプリケーションに対する統合された コード管理 & CI サービス。
- EC2, Lambda などのいろいろなサービス・言語に対応
- Django や Express (Node) などの blueprint からすぐにアプリケーションを作れる。
- AWS上でのコード管理、テスト、デプロイの一元管理が可能。
- Eclipse や VS、JIRA との連携。
が注目すべき点。
アルゴリズム
500 Data structures and Algorithms interview questions and their solutions
500 Data structures and algorithms interview qu... - Techie Delight - Quora
プログラマの採用面接で聞かれるような、アルゴリズムとデータ構造に関する一問一答集。それぞれの問いには、時間・空間計算量別に複数の回答(C/Java)が載っている。
Competitive Programmer’s Handbook
Competitive Programmer's Handbook
IOI や ICPC に出場する学生に向けた競技プログラミングの無料 e-book。グラフアルゴリズムが三章のうち一章まるごと割かれている。
類似した競技プログラミングの本(で無料に手に入るもの)としては、 Competitive Programming Book Companion Website がある。(一部有料)
その他
Nintaco - NES Emulator
NESエミュレータ。C, C#, Java, Lua, Python の API が提供され、メモリや入出力などが制御できる。例えば、ゲームのAIを作るなどの用途が考えられる。
Kakoune Code Editor
VimにインスパイアされたTUIのエディタ。Sublime Text にあるような Multiple Selection や 複数人で編集する Collaborative edit などが主な機能となる。Vim のモードの概念や hjkl による移動等の一部のキーバインドなどが継承されている。今後少しずつ使ってみて慣れてきたら記事を上げたいと思う。
