今週のまとめ (2017/7/21)
- [アルゴリズム] Bloom Filters by Example
- Bloom Filter のデモ
- [プログラミング言語] How Discord Scaled Elixir to 5,000,000 Concurrent Users
- [プログラミング言語] DoppioJVM: A JVM in JavaScript
- Pure JavaScript で実装された JVM。File System や Socket や Multithread API なども対応している模様。
- [プログラミング言語][数学] GitHub - ryanrhymes/owl: Owl is an OCaml numerical library: dense and sparse matrix, linear algebra, regressions, maths and stats functions.
- [プログラミング言語] zero allocation continuations
- C++ での Promise-chain でのオーバーヘッドを減らす試み。
- [プログラミング言語] Coq による correct-by-construction implementation
- [セキュリティ] RECON Slides
- モントリオールで行われたリバースエンジニアリングカンファレンスでの発表スライド一覧。
- [Web] Tippy.js - Vanilla JS Tooltip Library
指で数字を増やして5を目指すゲームが後手必勝であることを示す
指で数字を増やして5を目指すゲームとは
子供の頃やってたこれらの遊び、皆様の地元ではなんて呼んでましたか?ちょっと仕事で参考にしたいので、県名とかも教えてくれると嬉しいです!
— やしろあずき@1日目M-03a (@yashi09) 2017年7月5日
ちなみにやしろあずきの地元では
①「これやろうぜ!」
②「これやろうぜ!」
③「これやろうぜ!」
④「これやろうぜ!」
でした。アホか。 pic.twitter.com/pJaurIQUls
これの③です。
正式な名称はないようで、Wikipediaには「数字を増やす遊び」という名前で紹介されているようです。その記事によれば 割り箸・マッチ・グリンピース・戦争・プラフィン という地域名があるらしいです。
続きを読む今週のまとめ (2017/6/30)
La fin du premier semestre approche.
- [プログラミング言語] Streaming Combinators and Extracting Flat Parallelism | Futhark - A High Performance Functional Array Language
- [プログラミング言語][Haskell] mazzo.li – blag – Threading responsibly
- [プログラミング言語][Rust] Writing parsers like it is 2017. PDF
- 2017年にもなってメモリ違反で苦しんでるのはおかしいので、パーサを C 言語で書くのやめて Rust にリプレースしようという話。
- [プログラミング言語] Home – the Common Lisp Cookbook
- Common Lisp の CookBook。便利なリンク集もあり。
- [セキュリティ] The Symbolic Maze! | Feliam's Blog
- LLVMのシンボリック実行フレームワーク KLEE を使って迷路を解いてみるという面白い例。
- 実行は Docker を使うのが一番ラクです → Using KLEE with Docker · KLEE
- [Web] A guide to RESTful API design: 35+ must-reads | TechBeacon
- [Web] emotion - high performance css-in-js
*1: 要検証
今週のまとめ (2017/06/23)
- [アルゴリズム] AVL tree - Growing with the Web
- AVL木についての解説。計算量の解析と Java / JavaScript のコードがついている。
- [プログラミング言語] Macaron - a high productive and modular web framework in Go
- Go言語でのWebフレームワーク。Martini にインスパイアされたらしい (APIが似ている)
- [プログラミング言語] GitHub - kovidgoyal/html5-parser: Fast C based HTML 5 parsing for python
- [プログラミング言語] Inside D’s GC
- [プログラミング言語, アルゴリズム] GitHub - EbTech/rust-algorithms: Common data structures and algorithms in Rust
- [プログラミング言語] main is usually a function: A Rust view on Effective Modern C++
- [プログラミング言語] GitHub - nick-paul/aya-lang: A terse stack oriented programming language
- Esolang。 雰囲気としては APL/J に近い。グラフにプロットする機能などがある。
- [プログラミング言語] Luna. Visual and textual functional programming language.
- ビジュアルだがテキストでの編集も可能なプログラミング言語。関数型プログラミングに強い影響を受けており、依存型システムを持つらしい。画像編集やストリーム処理もできる様に見える。実装はオープンアルファのみで未公開。
- [その他] Regex Set Scanning with Hyperscan and RE2::Set | 01.org
今週のまとめ (2017/6/16)
時間短縮のため記事をコンパクトにします。*1
- [プログラミング言語] Writing a Forth
- [アルゴリズム] Data structure for triangle meshes
- 三角形分割のデータ構造とアルゴリズムについての記事
- [機械学習] Exploring LSTMs
- LSTMについてのコードや可視化が付いた丁寧な解説
- [プログラミング言語] 100+ Emulators Written in JavaScript - Hacker Lists
- JavaScript で書かれた エミュレータ一覧、各種CPUの実装からNESなどのゲーム機まで
- [数学] 18.783 - Elliptic Curves
- [数学] 測度論的確率論 2017 - Kengo Kato
- [その他] Color fonts! WTF? 🌈
- フォント自体に色がついたフォントについての解説。Photoshopなどが実装している。ブラウザ上の実装は Edge が頑張っている。
今週のまとめ (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: これらが十分詳しいのでこれをネタにして記事書いたろという気持ちがなくなってしまった