読者です 読者をやめる 読者になる 読者になる

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

概要: Rustの名前解決の詳細について解説する。本記事では、インポート解決について説明する。 名前解決のタイミング コンパイラの名前解決に関するコードを探す上で重要な点のひとつは、「 use や extern crate などの主要な構文要素は対応するHIRの要素を…

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

概要: Rustの名前解決の詳細について解説する。本記事では、名前解決に関する構文を紹介する。 Rustのモジュール Rustのコンパイルはcrate単位で行われ、必ずcrateのトップレベルモジュールに相当するファイルが存在する。これには lib.rs や main.rs という…

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標準と矛盾する拡張機能を無効化する…

64bit windows上でのalloy* (hola)

Alloy (hola) のバックエンドはSATソルバであり、いくつかのバックエンドから選べる。しかし、64bit windows上の64bit JREでは、SAT4J以外は動作しない。以下の手順で自分でjarを作成すれば、minisat等が動くバイナリが作れる。 kodkodのネイティブライブラ…

C++11 random 覚え書き

C++11以降では<random>ヘッダで良質な擬似乱数を得ることができる。 #include <random> 外部からの乱数 外部から乱数を得るにはrandom_deviceを使う。 #include <random> #include <iostream> int main() { std::random_device rand_dev; std::cout << rand_dev() << std::endl; std::cout << r</iostream></random></random></random>…

いわゆる「中卒」は数学/情報オリンピックには参加できるのか否か

「高校生に相当する年齢だが、高校等の教育機関に在学していない」場合、数学オリンピックや情報オリンピックには参加できるのか、という問題がある。該当する組織に直接訊ねるのが最も正確だと思われるが、2015/06/26時点の資料を読む限り、おそらく以下の…

C言語(標準)にM_PIは無い

C言語で円周率πを使うには M_PI を使う、と経験で知っている人は多いが、あれは実はC言語の規格には含まれていない。むしろ、処理系がM_PIを定義してはいけない事情(c - Using M_PI with C89 standard - Stack Overflow)がある。 ここでは、C言語の最新規格…

GW-450DやWN-AC433UKをRaspberry Piで使う

planexのありがたい記事を参考に作業。環境としてはRaspbian wheezyを仮定。おおまかな流れ : まず、下準備としてカーネルモジュールのビルドに必要な道具を揃える(既に揃えてある人はスルーしてよい)。続いて、ドライバのソースコードを取得し、必要な変更…

Coqの新機能、Primitive Projectionについて

Coqリポジトリのtrunkを見ると、次の2つの機能が入っていることがわかります。 Universe Polymorphism Primitive Projection Universe Polymorphismは、グローバル定義をUniverseのレベルについて量化した形で定義することができる機能で、型に飾り付けをし…

よく使う Coq.Logic の公理

Coq.Logic にはCoqの集合論モデルにおいて正しい公理や、それらの間の関係が記述されている。ここではその一部を取り上げて、意味を説明する。 前提知識 公理を仮定しない状態では、 Coqの論理は直観主義論理である。 ある2つが「等しい」という命題が証明で…

WindowsでCoqIDEの見た目をWindows風にする方法

%COQ%\share\themes\MS-Windows\gtk-2.0\gtkrc を %COQ%\etc\gtk-2.0 の下にコピーする。ただし、%COQ%はCoqのインストールディレクトリのことを指すとする。たとえば %COQ% = C:\Program Files (x86)\Coq

C++で多倍長整数ライブラリGMPを使う

目的 GCJなど一部のプログラミングコンテストでは既存のライブラリを使用することが認められている。特にC++であれば多倍長整数ライブラリとしてGMPを使うのが妥当であると考えられる。GMPを直接叩くのもよいが、GMPのC++バインディングを使うのが簡単である…

PowerPC64アセンブリ開発環境の整備

目的 PowerPC64アセンブリの演習のための環境を手元で構築する. 最新情報へのリンク 2015/01/11 以下のように事情が変化している。 PowerPC64 アセンブリ開発環境の設定メモに、以下の手順を現在行った場合に起きる問題への対処法がある。 crosstool-ngのバ…