ハードウェアや自動微分などの概念の解釈(interpretation)を、圏 (デカルト圏) の言葉に翻訳してコードに落とし込むという技法 (論文：http://conal.net/papers/compiling-to-categories/) のサンプルコード。Deep Embedded な DSL の代替となるらしい。(が、論文もコードも難しくてわからなかった)

アルゴリズム

keon/algorithms: Minimal examples of data structures and algorithms in Python

github.com

Pythonによるアルゴリズム・データ構造の「図鑑」。165個ある。競技プログラミング向けか。

Web

Choo: sturdy 4kb frontend framework

https://choo.io/

Webフロントエンドのフレームワーク。今やフロントエンドフレームワークのデファクト・スタンダードとなった Virtual DOM ではなく実際の DOM で差分計算をするnanomorphというのを使っているらしい。

WebGL Fundamentals

webglfundamentals.org

WebGLの入門サイト。解説の図や例が豊富。 WebGLとは何かという基礎の基礎から、(GLでは面倒な)文字の出し方やアンチパターンなどもカバーしている。

機械学習

Picasso: A CNN visualizer

github.com

畳み込みネットワークの可視化。解説記事によると、ネットワークの内部状態を可視化することにより数値の指標(検出率等)では分からない「誤解」を調べることができるという利点をあげている。

関連して、手書き認識のCNNのWebでの綺麗なビジュアライゼーションデモを紹介しておく。

3D Visualization of a Convolutional Neural Network

データベース

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

github.com

Lock-free な Key-Value store。詳しくは読んでいない。SIMD要素はlock-freeでのcompare-exchangeをまとめてやる部分か？(不明)

2017-05-12

今週のまとめ (2017/5/12)

前回はおやすみでした。

プログラミング言語
セキュリティ
- [PDF] Quick introduction into SAT/SMT solvers and symbolic execution
- Linux Kernel Exploitation
機械学習
- Data Version Control
- Deep Learning AMI — Amazon Web Services
数学
- Coding The Matrix と線形代数

プログラミング言語

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

www.brendangregg.com

プログラムのパフォーマンスを評価するときには、stall-waiting も含まれる CPU使用率ではなくIPC(Instruction per Clock)を見るべきという論説。そうすることによって、問題がメモリバウンドかCPUバウンドか分かるようになる、と主張している。

セキュリティ

[PDF] Quick introduction into SAT/SMT solvers and symbolic execution

https://yurichev.com/writings/SAT_SMT_draft-EN.pdf

SAT/SMTソルバとシンボリック実行の入門書。未だ草稿らしいが、内容は豊富である。典型的な数独等のパズルを解くものから、簡単なデコンパイラを作りその検証をZ3で行うと言った高度なものまである。シンボリック実行については LLVM のシンボリック実行ツール KLEE の解説に一章割かれている。筆者は Reverse Engineering for Beginners で有名であり *1 、そういった話題が多い。

Linux Kernel Exploitation

github.com

近年の Linux カーネルに存在した脆弱性についてのまとめ。それぞれの脆弱性の発見手法や報告の他に、ファジングや検出・exploitツール、CTFのwriteupなども紹介されている。

機械学習

Data Version Control

dataversioncontrol.com

機械学習での開発においては前処理→学習→評価などの幾つかの段階を経ることが普通であるが、それらの依存関係を解析し、自動的に処理フローを実行できるようにするといった趣旨のビルドツール。コードやデータの変更に対しても容易に適応できるような設計を売りにしている。

Deep Learning AMI — Amazon Web Services

Deep Learning AMI — Amazon Web Services

AWSでディープラーニングをするときに役立つ公式イメージ(AMI)。設定済みの TensorFlow, CNTK, Caffe, Caffe2, Theano, Torch, Keras 等が使用できる。どうでもよいが、Theanoだけロゴが見えないのかわいそうである。

数学

Coding The Matrix と線形代数

Coding The Matrix

情報工学のための線形代数の講義のサポートページ。本(有料)やスライドやソースコードなどのリソースが置かれている。また、情報工学における線形代数の応用例についてもいくらか説明されている。

ところで、情報工学のための線形代数のリソースは巷に多くあるが、個人的には以下の講義資料『産業応用のための基礎数理』が面白いと感じた。

情報科学類情報線形代数／情報メディア創成学類情報数学IV *2

内容はスペクトル分解やノルムや特異値分解など一歩進んだ線形代数の内容であるが、「産業応用のための」とあるように、画像処理や信号処理などの実際の応用においてそれらがどのように役に立つか分かるような構成になっている。

*1: 自分でも言っている / “As of 2013-2017 I mostly known for “Reverse Engineering for Beginners” free book.” https://yurichev.com/

*2:4章以降はリンク切れに見えるがURLをいじれば(数字をインクリメントすれば)見ることは出来る

2017-04-28

今週のまとめ (2017/4/28)

4月も終わり (ここで家賃振込みを忘れてたことに気づき書くのを中断し銀行へ行く) ですね。

プログラミング言語
アルゴリズム
- C++ implementation of a fast and memory efficient HAT-trie
セキュリティ
- Referrer Policy
- Top 10 Developer crypto mistakes
データベース
- CMU 15-721

プログラミング言語

Monads to Machine Code

www.stephendiehl.com

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+

www.bonobo-project.org

Python3.5のためのデータ処理フレームワーク。Python3 の言語機能を取り込みよりモダンな設計になっている。開発中のため現時点で利用は推奨されていない。

Kaitai Struct

kaitai.io

バイナリ構造をパースするライブラリ・フレームワーク。バイナリフォーマットを 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

github.com

HAT-trie木 *1 の C++による実装。HAT-trie木は空間計算量が良い木で連想配列などに用いることができる。この実装は pure HAT-trie 木の実装で、もっと効率の良い hybrid HAT-trie 木は “may arrive later” とのこと。 Cによる実装は既にある。

セキュリティ

Referrer Policy

scotthelme.co.uk

サイトから出ていく際に付く 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の誤り」。目次を引用すると、

ハードコード化されたキー

不適切な初期ベクトル(IV)の選択

ECBモードでの操作

パスワード保管のための暗号プリミティブの誤使用

MD5 と SHA1

パスワードは暗号化キーでは無い

暗号化がメッセージの完全性を保証していると考える *3

非対称キーの長さが短い

暗号的でない乱数

“暗号スープ” (暗号プリミティブの混在)

データベース

CMU 15-721

Advanced Database Systems

15721.courses.cs.cmu.edu

カーネギーメロン大学のデータベースの講義。講義のスライドとビデオ、また参考文献となる論文が公開されている。 DBMS の実装においての並列モデル・データレイアウト・データ圧縮・最適化などを論文を参照しながら行う。

*1: http://crpit.com/confpapers/CRPITV62Askitis.pdf

*2: 前者は Referer で、後者は Referrer。非常にややこしい

*3: HMACなどを使おうという話らしい

2017-04-21

今週のまとめ (2017/4/21)

今週のまとめのリンクは iCloud のメモ帳で管理しています。iPhone からの保存が楽なので…

プログラミング言語
機械学習
- Paperspace Machine Learning
インフラ
- aws-fpga
- AWS Codestar
アルゴリズム
- 500 Data structures and Algorithms interview questions and their solutions
- Competitive Programmer’s Handbook
その他
- Nintaco - NES Emulator
- Kakoune Code Editor

プログラミング言語

cmacro – Lisp macros for C

github.com

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

www.paperspace.com

機械学習(主に深層学習)に特化したクラウド計算サービスで、GPUを提供している。時間毎課金。競合として AWS [pg]2.xlarge との比較表が載っている。*4

インフラ

aws-fpga

github.com

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

Download Nintaco

NES エミュレータ。C, C#, Java, Lua, Python の API が提供され、メモリや入出力などが制御できる。例えば、ゲームのAIを作るなどの用途が考えられる。

Kakoune Code Editor

kakoune.org

VimにインスパイアされたTUIのエディタ。Sublime Text にあるような Multiple Selection や複数人で編集する Collaborative edit などが主な機能となる。Vim のモードの概念や hjkl による移動等の一部のキーバインドなどが継承されている。今後少しずつ使ってみて慣れてきたら記事を上げたいと思う。

*1: 0.x 系列。現行の sweet js は AST を operational に変換するような設計になった

*2: よくわからなかった

*3: これは時代を反映していると思う(開発元の研究所からの手厚いサポートがあったと書かれている)。だが、今では OCaml の大きな(ユーザー|開発者|研究者)コミュニティが存在するのでサポートに関しては(別の観点ではあるが)今でも通用する。

*4: これインフラカテゴリでも良かった

2017-04-14

今週のまとめ (2017/4/14)

すた丼

プログラミング言語

Dale - Lisp Flavored C

github.com

Lisp のような S式で記述されたコンパイラ型言語。Lisp風Cとあるが、C言語へのトランスレータではなくLLVMをバックエンドとしている。また、macro や module や concept などの C言語を超えた言語機構もある。

LowLevelProgramming-University

github.com

低レベルプログラミングについての資料集。アセンブリ、C言語、ハードウェア、ファームウェア、Linux カーネル・デバイスドライバなどの資料が載っている。

Functional Language Research Compiler

github.com

Intel製の関数プログラミングのコンパイラフレームワーク。これを用いると

[GHC フロントエンド] 
↓ Ext Core
[HRC (Haskell Research Compiler)] 
↓ MIL IR 
[FLRC] 
↓ C files 
[Intel C Compiler] → Executable binary

のようにしてCコードが出力され、iccでコンパイルされるらしい。

セキュリティ

Detecting ROP with statistical learning of program characteristics

blog.acolyer.org

ROP( Return-oriented programming - Wikipedia )検出の手段として統計的手法が用いられることがあり、そこでは異常検知による物が多いが、新たな統計的尺度を用いることによって検出率を改善した…という論文をまとめているブログ記事。

人工知能

Best Practices for Applying Deep Learning to Novel Applications

[1704.01568] Best Practices for Applying Deep Learning to Novel Applications

ディープラーニングを実際のアプリケーションに応用するためのベストプラクティス集。論文の最後には実際の応用例として arXiv のリンクが会ってうれしい。

以下の流れで説明されている

準備を行う。

データを準備する

作りたいアプリケーションに対して、それに近いディープラーニングのアプリケーションとの類似点を見つける

最小限のベースモデルを作る

可視化やデバッグツールを作る

モデルのチューニングをする

エンドツーエンドの学習、あるいは学習器の組み合わせなど

2017-04-07

今週のまとめ (2017/4/7)

春

プログラミング言語

[Rust] Building Realtime APIs in Rust

Building Realtime APIs in Rust – Robert Lord

Rust を用いたネットワークプログラミング、フレームワークを用いて認証システムやリアルタイムAPIを構築するデモ。

[JavaScript] BitArray.js

github.com

1bitのフラグデータを配列して32bit数値などにパックするビット配列の実装。通常の配列を用いるより高速 (約1.54倍) でメモリ効率は著しく良い (98.75%の削減)

[JavaScript] Using the Chrome devtools new code coverage feature

blog.logrocket.com

Chrome Canary の DevTools にコードカバレッジ計測ツールが公開された。これにより環境構築不要で簡単にカバレッジ計測ができるようになりかなり嬉しい。この関連記事には他の DevTools の機能が紹介されているのでそちらも見るとタメになる。

0.30000000000000004.com

ドメイン名で出落ち感があるが、各言語(41個)での浮動小数点計算での計算誤差の違いをまとめた資料となっている。

アルゴリズム

Interesting data structures: the BK-tree

http://signal-to-noise.xyz/post/bk-tree/

距離空間でデータのインデックス化を行うデータ構造である、BK木についての解説。レーベンシュタイン距離を使うと文字列の効率的な検索に使えるようで、この記事もその実例とコードを示している。

機械学習

arxivist

arxivst.com

arXiv に投稿されるマシンラーニング関連の論文のキュレーション。説明を読む限り人力で選択・要約を行っている。

数学

Higher-Dimensional Categories: an illustrated guide book

http://cheng.staff.shef.ac.uk/guidebook/guidebook-new.pdf

高次元圏(高階圏) についての解説。図が豊富に使われており丁寧だが、話題自体は難解なので読むのには力がいる。