extern "rust-call" とは何か

extern "rust-call" は(Rust 1.16.0時点では) Fn, FnMut, FnOnce の宣言に出現する。この意味について Rust issue 41058: Get rid of the “rust-call” hack の説明がわかりやすい。 Currently, we fake variadics by defining functions with the rust-call …

Rustの多相性にかかわる構文

概要: Rustの型多相性の詳しい挙動を調べる前に、まず構文を調べる。 型仮引数 型仮引数のフォーマットは以下の通りである。 (parse_generics) < と > で囲った部分に、型仮引数の名前をカンマ区切りで指定する。 末尾のカンマは省略可能である。 型仮引数は…

Rustで挿入ソート + 強制move outで高速化

挿入ソートは時間計算量 のソートアルゴリズムであるが、特に入力 の転倒数に対して で抑えられること、また定数倍で高速なことから特定の場面で使われる場合がある。 Rustで挿入ソートを素朴に実装すると以下のようになる。 pub fn safe_insert_sort<T: Ord>(arr: &</t:>…

記事の更新頻度について

1日1回更新は一ヶ月続けることができた。ブログ駆動で色々調べる機会が得られたのはよかったが、さすがにこの頻度は大変なので、以降は2日に1回の更新にしようと思う。また、既存の記事の英訳をしてみるのもよいかもしれない。

RustのジョークRFC

Rustでは言語仕様に対する大きな変更はまずRFCという形で投稿し、十分に検討をしながらコンパイラに組み込むことになっている。(これはIETF RFCとは同名だが別のもので、 Rust RFCsで管理されている。Python PEPsと似たような仕組みといえる。) 先日、Rust R…

ハッシュベースの署名(公開鍵署名)を書いてみた

Post-Quantum Cryptography, Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, Springer-Verlag Berlin Heidelberg, 2009の冒頭部で、ごく簡単なハッシュベースの署名アルゴリズムが紹介されていて感動したのを思い出したので書いてみた。 コード…

Rustの単一実装トレイトパターン

概要: ただ一つの実装をもつトレイトを定義するデザインパターンでできることとデメリットを紹介する。「単一実装トレイトパターン」という名前は今考えたもので、他に名前があるかもしれない。 既存の型や既存のトレイトにメソッドを追加する Rubyというプ…

Rustの名前解決(5/5) 可視性判定

概要: Rustの名前解決の詳細について解説する。本記事では、解決された名前の可視性判定について説明する。 名前解決にかかわる構文 インポート解決 パス解決 メソッド記法とメンバ変数と関連アイテムの解決 可視性判定 可視性 Rustの可視性は ast::Visibili…

Rustの名前解決(4/5) メソッド記法とメンバ変数と関連アイテムの解決

概要: Rustの名前解決の詳細について解説する。本記事では、型情報を必要とする名前の解決を説明する。 名前解決にかかわる構文 インポート解決 パス解決 メソッド記法とメンバ変数と関連アイテムの解決 可視性判定 曖昧性が生じる例 この記事で扱うのは、型…

Rustの名前解決(3/5) パス解決

概要: Rustの名前解決の詳細について解説する。本記事では、パス解決について説明する。 名前解決にかかわる構文 インポート解決 パス解決 メソッド記法とメンバ変数と関連アイテムの解決 可視性判定 パス解決とは Rustで foo::bar のようにパスを書いたとき…

Rustの名前解決(2/5) インポート解決

概要: Rustの名前解決の詳細について解説する。本記事では、インポート解決について説明する。 名前解決にかかわる構文 インポート解決 パス解決 メソッド記法とメンバ変数と関連アイテムの解決 可視性判定 名前解決のタイミング コンパイラの名前解決に関す…

Rustの名前解決(1/5) 名前解決にかかわる構文

概要: Rustの名前解決の詳細について解説する。本記事では、名前解決に関する構文を紹介する。 名前解決にかかわる構文 インポート解決 パス解決 メソッド記法とメンバ変数と関連アイテムの解決 可視性判定 Rustのモジュール Rustのコンパイルはcrate単位で…

Rustのthread local gensym/internパターン

概要: Rustでgensymおよびinternを行う方法を説明する。 gensymとinternとは何か gensymパターンは、「まだ使われていない整数」を返す fresh() 関数を実装するというパターンである。型推論などで一時変数を作成するなどの用途で用いられる。 internパター…

Rustマクロの衛生性はどのように実現されているか(2/2) 構文の優先度に関する衛生性

概要: Rustマクロは2つの意味で衛生的である。その衛生性の説明とともに、それを実現するためのコンパイラの仕組みを説明する。 Rustマクロの2つの衛生性 Rustマクロ (ja) は次の2つの意味で衛生的(hygienic; 健全ともいう)である。 マクロ内で導入される変…

Rustマクロの衛生性はどのように実現されているか(1/2) 識別子に関する衛生性

概要: Rustマクロは2つの意味で衛生的である。その衛生性の説明とともに、それを実現するためのコンパイラの仕組みを説明する。 Rustマクロの2つの衛生性 Rustマクロ (ja) は次の2つの意味で衛生的(hygienic; 健全ともいう)である。 マクロ内で導入される変…

Rustは構文解析をしてからマクロを展開する

C言語では字句解析の次が前処理で、前処理のあとに構文解析が行われるが、Rustでは構文解析が終わってからマクロが展開される。 より正確に説明すると、Rustのコンパイルはcrate単位で行われ、crateのコンパイル処理の冒頭部は以下の2フェーズに分かれている…

Rustのself引数まとめ

概要: Rustの随所でself引数は特別扱いされている。それらの挙動について調べた。 self引数とメソッド Rustではnon-staticメソッドは self という特殊な名前の引数を持つ関数として定義されている。例えば、 struct A; // parse_self_arg impl A { fn f1(sel…

Rustトレイトの既定実装と否定実装

概要: SendやSyncなど一部のトレイトで採用されている機能である、既定実装と否定実装の挙動を調べた。 既定実装と否定実装について 既定実装(デフォルト実装, 自動実装, オート実装, default impl, auto impl)と否定実装(negative impl)はRust RFC 0019: Op…

Rustの組み込みマクロ

Rustのマクロの多くは macro_rules! で定義されるが、トークン列をトークン列に変換するものなら何でもマクロとして実装されうる。 Rustの標準ライブラリのマクロの多くは core::macros にて定義されている。 以下のマクロは通常の macro_rules! により定義…

Rustのマングリング(名前修飾)

Rustの生成したネイティブコードを見ると、 _ZN6thread5sleep20h87eee61de4645181cAbE のようなシンボル名が見える。この例は std::thread::sleep に対応している。このようにRustの(単相化された)アイテム(関数や変数など)の名前をリンカが認識できる文字列…

Rustのvtableの内部構造

trait objectは、型情報を忘れるかわりにvtableへの参照を持ち回すことで動的ディスパッチを実現している。 vtableを生成するコードはrustc_trans::meth 112行目にある。これによると、vtableの構造は以下のとおり。 0番目: Drop Glue をあらわす関数ポイン…

RustでPhantomDataにT以外のものを入れるのはなぜか

PhantomDataにT以外のものを入れるのは、主に3つの理由がある。 生存期間変数に言及するため。 変性を制御するため。 所有関係を制御するため。 生存期間変数に言及するため 型だけではなく、生存期間変数も、迷子になっては困る。こういうときは参照を使っ…

Rustで型の多相再帰はできない

OCamlやHaskellに比べると、Rustは多相再帰ができない場合がほとんどである。以下にその詳細を説明する。 多相再帰 異なる型引数による再帰呼び出しを多相再帰 (polymorphic recursion) という。多相再帰はPurely Functinoal Data Structuresで紹介されてい…

RustのDropの実装に対する制約とDrop Checkの規則

DropとDrop CheckについてはThe Book: DropとNomicon: Drop Checkを読んでもらうとして、この辺りの規則はコンパイラの typeck::check::dropckのコメントに解説がある。 Dropの非伝搬性 ところで、筆者が個人的に勘違いしていた点として、「 T: Drop である …

Rustのクエスチョンマーク

Rustに出現するクエスチョンマーク let f = File::open("input.txt")?; はRust 1.13で導入された機能で、ほぼ try! の構文糖衣である。 「ほぼ」というのは、 ? が将来的にはより汎用的に使えるように設計されているためで、 Result に限らない一般の std::o…

Rustのsize_of_valはどこで実装されているか

概要: std::mem::size_of_val はRustでもCでも実装できない。どこで実装されているかを調べた。 size_of_val が特殊な理由 std::mem::size_of_val は std::mem::size_of の親戚である。 size_of はCのsizeofと似たようなものだと言ってよい。 RustはCとは異…

クロージャを boxせずに 返したい: Rustのconservative_impl_traitとimplementation leak

概要: 「クロージャを boxせずに 返したい」という欲求は人類の四大欲求のひとつと言われている。 conservative_impl_trait という機能を使うことでこれをスパッと解決できるが、これは単なる構文糖衣にとどまらずRustの型システムに食い込むこともあってか…

gitコマンドがgitリポジトリを探す順番

git

概要: 多くのgitコマンドは特定のgitリポジトリに対する操作であるから、現在位置から対応するリポジトリを発見する必要がある。環境変数かコマンドラインオプションで指定された場合を除き、gitはまず ./.git ファイル、 ./.git/ ディレクトリ、 . の3つを…

Rustの字句

以下はRust1.15.1の syntax::parse::lexer をもとに作成したPEG風の字句規則である。 IdentStart <- [a-zA-Z_] / # Any Unicode scalar value >= 0x80 with XID_Start property IdentContinue <- [a-zA-Z0-9_] / # Any Unicode scalar value >= 0x80 wih XID…

C言語のinline

C C++

C/C++のinlineで間違いやすい3つのポイントがある。 1つは、GCCは3種類の異なるinline仕様を使い分けているという点である。3種類とは、「C++のinline」「C90用のGCC拡張inline」「C99以降のinline」である。 2つ目は、inlineを使っても、コンパイラが必ずイ…

RustのFn* trait

Rustにおけるクロージャとは、 Fn, FnMut, または FnOnce を実装した値にすぎない。これらを追ってみた。 Fnはどこから来たか まず、 Fn/FnMut/FnOnceはキーワード/予約語ではない。syntax::symbolの一覧にない。 fn main() { let Fn = 0; } そこで、広く使…

C言語における空白文字

C

C言語における空白文字は、文字列の一部分としてと、トークンを明示的に区切る (long long と longlong は違う) こと以外には基本的に無意味というように思える。しかしプリプロセッサレベルでは、以下の場面で意味がある。 includeの中身 通常 <stdio.h> のようなコ</stdio.h>…

C言語の型の読み方

C

C言語の型の読み方の解説は探すと色々出てくるが、改めて自分で説明してみることにした。 用語説明 C言語のポインタ記法に代わる記法として、ここでは次のような記法を導入する。もちろんこれはC言語にはない。 型 T へのポインタを ptr<T> と書く。 型 T が n </t>…

Feedly用ブックマークレット

以前から使っていたものが微妙だったので作り直した。 Subscribe it with Feedly JavaScript部分は以下のようになっている。 void(feedtag=document.evaluate('//link[@rel="alternate"][@type="application/atom+xml" or @type="application/rss+xml"]', do…

RustのSizedとfatポインタ

概要: RustにはSizedというトレイトがあり、一部の例外を除いて暗黙のうちに実装されている。Sizedが実装されていない型はDynamically Sized Typeと呼ばれ、これらのデータはfatポインタを経由してアクセスする。この仕組みを説明する。 Sizedの使い方はAPI…

CMS (contestms) のユニットテストと機能テスト

CMS (contestms) は国際情報オリンピックと各国の情報オリンピックを中心に利用されているオープンソースのオンラインジャッジシステムである。 CMSのバックエンドに手を入れる場合には、ユニットテストと機能テストを手元で実行できるようにしたほうがよい…

gitでbareとnon-bareを切り替える

git

用語集 non-bare repository: 皆様のお手元にある普通のリポジトリがそれです。 bare repository: 普通はgitサーバーにある。手元でも取り扱い可能。ただしworking directoryがないので、work treeを必要とする様々な操作ができない。 bare repositoryは hog…

過去のコミットでgit LFSを使うように歴史改変をする

git

「Subversionからgitに移行したはいいが、履歴があまりにでかいのでPDFを別管理にしたい」という状況を考える。でかいデータやバイナリを別管理にするといえばgit LFS, 昔の履歴に遡って変更を加えるにはgit filter-branchであるが、これらを組み合わせる方…

gitの履歴から大きなファイルを探すスクリプトを書き直した

git

巷では、gitの履歴から大きなファイルを探す方法を紹介する記事がいくつかあるが、ここに書かれているスクリプトは遅いし、bareリポジトリやsubmoduleやpackのないリポジトリでは動作しないし、looseオブジェクトからは探してくれないので、書き直してみた。…

combine: マクロのいらないRustのパーサーコンビネーター

はじめに Rustには有名なnomというパーサーコンビネーターライブラリがあるが、せっかく高級な型システムと最適化があるのにマクロで何とかしようとするのは勿体無いと思うので、マクロに深く依存しないcombineを使ってみた。 combineの主な特徴 parsec リス…

OCamlのformat (型安全なprintf/scanf) の仕組み

OCamlのPervasives (デフォルトでopenされるモジュール) には、Printf/Format/Scanfで使うための format という型がある。OCamlの特殊機能として、型推論時に文字列リテラルにstringではなくformatという型がつくことがある。 $ ocaml OCaml version 4.04.0+…

C言語で部分適用したい!(実は、できるアーキテクチャがあるんです)

通常、C言語の関数ポインタは、クロージャではない。したがって、関数を部分適用したり、カリー化したり、ローカル変数をキャプチャーした関数ポインタを返したりすることはできない。しかし、実際にC言語が動作する環境のなかには、そのようなことが実現で…

巻き舌できるようになった(たぶん)

これまで巻き舌ができなかったが、今日ふと試したらできるようになった。巻き舌といっても、舌を変な形にするほうではなく、Rの音を出すほう。あんまり参考にならないかもしれないけど、一応どんな風にやったか書いておく 舌を意図的に動かす ロシア語やイタ…

ランサムウェアを作ってみた(シェルスクリプトで)

ランサムウェアの暗号化部分についての実証コードを書いてみた。暗号の計算にはOpenSSLのコマンドが使えるので、シェルスクリプトを使って書いた。github.com 注意 このコードを試して起こった損害について作者は責任を追わない。基本的にdocuments/以下にあ…

とある偽シャッフルアルゴリズムとその分布

次のようなシャッフルアルゴリズムを考える(簡単のためrand()%Nと表記したが、この部分で0以上N-1未満の一様な整数乱数が生成されると仮定して議論する)。出力されるものは 0, ..., 255 を並び換えたもの(置換)である。 std::vector<int> a(N); for(int i = 0; i </int>…

C/C++の静的解析ツール・事例まとめ

C/C++の静的解析は、どう考えても大変なんだけどどう考えても需要が高いので、やはり色々なソフトウェアや事例があるようだ。まとまった情報が欲しいけど見つからなかったので自分の調べた範囲でまとめることにした。他にも耳寄りな情報があったら教えてほし…

latexmk設定メモ

LaTeX文書のコンパイルをよしなにやってくれるlatexmkについて。全体設定である ~/.latexmkrcには以下のように記入してある。 #!/usr/bin/env perl $pdf_mode = 3; $latex = 'uplatex -kanji=utf8 -synctex=1 -file-line-error -halt-on-error -interaction=…

volatileとatomicの違い

volatileとatomicの違いを調べるために、以下のC++プログラムをコンパイルしてみる。 #include <atomic> void func1(int *p) { ++*p; ++*p; } void func2(volatile int *p) { ++*p; ++*p; } void func3(std::atomic_int *p) { ++*p; ++*p; } $ g++ -std=c++11 -pthre</atomic>…

文脈自由文法(CFG)と解析表現文法(PEG)をHaskellのモナドで説明する話

文脈自由文法(Context Free Grammar) と 解析表現文法(Parsing Expression Grammar) は記法が似ているものの、その性質は大きく異なっている。しかし、以下のようにHaskellのモナドを用いて、左再帰的でない文脈自由文法をそのままパーサーコンビネーターと…

GCC拡張の無効化 (と、それにまつわる細かい話)

端的に言えば-pedantic-errorsを使えばよい。(できれば-std=...も併用したほうがいいだろう)以下解説GCCのC/C++コンパイラは、独自の拡張機能を導入している。これを無効化するオプションには2種類あり、意味が異なる。 C標準と矛盾する拡張機能を無効化する…