＞トップ
システムプログラミングにまつわる、キモというよりもっと gdgd したものについての書き置きとかリンク集
（余談ですが、何で読んだか忘れてしまいましたが（金田一先生の本だったか？）日本語（やまとことば）の語彙には、内臓をあらわす言葉が「わた」と「きも」の 2 つしかないそうです。ある時その話が出て、つまり日本人は魚を食べる民族だったんだな、と）
いちいち断ってなくても文献は編者未読の場合があります。
現代風の実装についての最短距離での道案内としては、
関数型言語を実行する抽象機械として、1963 年に提案されたのが SECD マシンである。
「SECDマシン再訪」に、簡単だが完全に動く SECD マシンの ML による実装のソースリストが収録されている。
Haskell に移植したものを置いておく。
"A Rational Deconstruction of Landin's SECD Machine" という論文がある（未読）
SECD マシンは、正格評価の実行系である。そのあとで研究された遅延評価のための技法などについては、80 年代後半（執筆時期）のものまでが、"The Implementation of Functional Programming Languages" によくまとまっている。手っ取り早く動かすには "Implementing functional languages: a tutorial" が参考になる。
前述の Simon Peyton Jones の書籍によくまとまった解説があるが、SK リダクションマシン、スーパコンビネータ、ラムダリフティングの初出論文はそれぞれ以下の通り。
CW 2011 Tutorial: Introduction to Programming with Shift and Reset (2011/Sep/23)
(by shiro, from https://www.reddit.com/r/lisp_ja/comments/3h605m/セル供養_ガベージコレクション/cu4k0qx ) GCは (1)Cなど低レベル言語で書く部分の自由度を下げてよい(2)性能をとことん追求しない(3)自分の持ってるマシンだけで動けばいい、のなら難しくない。(後略)
TBD
のざきさんの「どのようにしてlibcは後方互換を保つのか？」
アセンブリ言語や伝統的 Basic では、サブルーチンの先頭でなくどこからでも、外から飛び込んで実行できたわけだが、最近の言語ではそういったことはできないのがもっぱらである（ C89 の議論のはじめの頃は entry というキーワードがそのために予約されるかも、ということがあったが、結局なくなった）。GCC 拡張の Labels as Values という拡張機能を使って無理やり飛ぶことができるが、関数をまたがってジャンプした場合は「If you do that, totally unpredictable things will happen.」であるとドキュメントに書かれている。
そんなわけで言語の上からは消えたが、たとえば duff's device（ http://catb.org/jargon/html/D/Duffs-device.html ）は一種のそれであるし、言語処理系が生成するコードで使われることもある。
たとえば C 言語で、末尾再帰で自分自身を呼び出すコードの場合、関数プロローグの後のあたりにジャンプするようなコードが生成されることがある。また（和田研の）UtiLisp では（現在の UtiLisp/C ではなく System/360 や 68000 版）、可変個引数の処理でこれを使っている。
（以下の話はこちらの Shibuya.lispテクニカルトーク第4回の近山先生の動画から http://www.youtube.com/watch?v=whX8WWFsIgU 、というかほぼそのまま ）UtiLisp では、Lisp 関数の効率的なコンパイルだけではなく、徹底したモジュール化もおこなった。すなわち、可変個の引数を取る関数であっても、呼び出し側は呼び出し対象についての情報なしにコンパイルされねばならないし、呼び出され側はそれをサポートするようにコンパイルされねばならない。その前提でどうやって可変個の引数を持つような関数を呼ぶコードを生成し、また呼び出され側ではオプショナルな引数についてデフォルトの初期化式を必要に応じて評価するようなコードを生成するのか？
まず、呼び出され側についての情報として、コンパイル時に、引数の最大個数についての情報を持っておく。実行時に呼び出し側は、呼び出す対象についてそれを参照し、実引数の個数が越えてないかどうかをチェックする（ようなコードを、呼び出し側のコード生成の時に生成する。これは講演後の QA にある）。
呼び出され側には複数個の入り口（のテーブル）があり、順番にそれぞれ、実引数 0 個、1 個、2 個 ... 用の入り口である（きしもと注: 引数をいくらでも増やせるような関数には別のプロトコルが必要？）。テーブルジャンプによってそれぞれの入り口に飛ぶと、最低限必要な引数の個数に足りないものはアリティエラーになる。そこから先は具体例があったほうがわかりやすいと思うので具体例で説明する。
(defun hoge (a b (c 42) (d (cons a b))) ...)
というような関数定義があったとする。必須の引数は a と b の 2 個で、c と d はオプショナル。c は実引数が無ければデフォルトで 42 となり、d のデフォルト値は (cons a b) である。これから次のようなコードが生成される。
実引数 0 個の時の入り口 実引数 1 個の時の入り口 アリティエラー発生 実引数 2 個の時の入り口 (3個目の引数用の場所) ← 42 実引数 3 個の時の入り口 (4個目の引数用の場所) ← (cons a b) 実引数 4 個の時の入り口 (以下、関数の本体...)
といったような感じの（ C 言語の switch 文のフォールスルーにも似ているか）コードを生成する。入り口のアドレスは、一定間隔で並べるか、テーブルを作るかして、呼び出し元のコンパイル時に呼び出し先がまだ存在しなくても構わないようにしてある。呼び出し元のコンパイルでは、実引数の個数に対応した飛び先にサブルーチンジャンプするだけでよい。
（なお、発想の元は、System/360 の OS（ OS/360 か？）のシステムコールからの戻り方で、システムコールからの正常終了と異常終了で違う所に戻る、という API だったという話）
この他にも、たとえばアドレスが 24 ビットなので上位 8 ビットをタグとして使用し、オブジェクトタグではなくポインタタグだったり、タグの値を工夫して判定を簡素化する等 UtiLisp にはいろいろあるのだけど、そういった工夫が徒花ではあった、という言葉（発表の後のほうにある）はなんか重い。
格言「生成式を自作するべからず」
原テキストはこちら http://portal.acm.org/citation.cfm?id=63042
日本語訳は bit で、西村恕彦訳「乱数生成系で良質のものはほとんどない」
である
なお、刺激的なタイトルであるため誤解されていることも見受けられるようであるが、こんにち識者が勧めるような乱数生成系はどれも、この文献の言うところの「良質」に含まれるものである。この文献が「良質のものはほとんどない」と槍玉に挙げているのは、当時のプログラミング言語処理系や OS などの標準ライブラリの rand 関数の品質のことで、それはもう酷かった。こんにち広く使われている rand 関数では、メルセンヌツイスタなど非常に良質の生成アルゴリズムが使われており、使い方を間違えない限りたいていは問題ない（たまに古いものがそのままというライブラリもあるので注意は必要だが）
この文献で、最低要求水準としている乱数生成系は、comp.lang.c FAQ list · Question 13.15, "Q: I need a random number generator. " にサンプルコードが示されている。本文の最後にあるように、a には 48271 を使ったほうが、ちょっと良い乱数列が得られる。この rand が使っているのは線形合同法なので、順番に取り出して (x, y) のように多次元の座標に使ったり、サイコロとして使う時など剰余を取ったりしてはいけない、など、注意が必要であるので、用途が確定できない場合などはメルセンヌツイスタなど他のより良い（ということが確実にわかっている）生成系を使うべきである。繰返すが、自作してはならない
擬似乱数生成系については、基本的な文献としては TAoCP の 2 巻（現行の邦訳版は ISBN 4-7561-4543-4 ）がある。過去の擬似乱数生成系についてはだいたいこれ 1 つで相当のところまで十分であろう。ただし古いため、今使うべき乱数生成系を選ぶ参考にはできない。メルセンヌツイスタの発明者の松本さんとのやりとり → http://www.soi.wide.ad.jp/class/20010000/slides/03/16.html も参考に
M系列と呼ばれる擬似乱数生成系があるが、これについては、UP応用数学選書 伏見正則『乱数』（ ISBN 4-13-064072-0 ）が参考になる
また、近年開発された手法に Xorshift などがあり、そういったものについてはウィキペディアなどを参照
暗号学的安全性については、普通の生成系を SHA-2 などのハッシュ関数でフィルタする、という方法（結城浩『新版暗号技術入門』（ ISBN 978-4797350999 ）にある図がわかりやすい）がある、ということまでしか勉強していない。暗号学的に安全な擬似乱数生成系、というものについていい書籍あったら教えてください m(__)m
リンク集
規格以前からまずほぼ間違いなく短絡評価でしたし、ANSI (C89) で短絡評価と決められました (処理系依存とされている Pascal との混同か、Java あたりの解説書のどれかで間違ったことが書かれていたのか)
C言語の論理否定 (反転) の演算子 ! を 2 重に使う !! は、ほとんど NOP のように感じられるが、以下のような用途をこれまでに思いついた。
その昔学校放送の「昼の放送」にどういうコーナーがあるといいと思いますか、というアンケートに「ヘアピンコーナー」と答えた人がいましたが（90年代初頭の F1 ブームの頃でした）
a ? b : c ? d : e は a ? b : (c ? d : e)a ? b : c ? d : e は (a ? b : c) ? d : eこれは罠といったものではないが、知っているうちでは一番めんくらったものなので覚えのために書いておく。
Python 2 の commands ライブラリの commands.getstatus は、なぜか引数として渡されたファイルについて ls -ld を実行し、その文字列を返す、というものだった（他の 2 つの関数から類推される、コマンドを実行し終了ステータスを返す、というものではなく）。実際よくわからないふるまいなので Issue 461280: commands.getstatus does an ls? のようにイシュートラッカに登録されたりもしているのだが、GvR による「ドキュメントに書いてある通りの動作だろ？」というコメントで Status: closed, Resolution: rejected になっている。
その後どうなったかというと、Python 2.6 で導入された subprocess ライブラリによって deprecated となり、Python 3 で commands ライブラリごと削除され、この謎の機能は消えた。
"Division and Modulus for Computer Scientists"
("LVM, the lazy virtual machine" の Appendix E にも収録)
unsignedで以下のように計算する。
/* 半加算 carry, x = x + y; */ x += y; carry = (x < y); /* 全加算 carry, x = x + y + carry; */ x += carry; carry = (x < carry); x += y; carry += (x < y); /* 半減算 borrow, x = x - y; */ borrow = (x < y); x -= y; /* 全減算 borrow, x = x - y - borrow; */ y += borrow; borrow = (y < borrow); borrow += (x < y); x -= y;
( http://d.hatena.ne.jp/tociyuki/20140906/1410012689 より)
右シフトに論理シフトと算術シフトがあるのは当然として、左シフトに論理と算術がある（たとえば、情報処理試験の CASL の COMET など）合理的な理由を聞いた記憶がない。誰か知りませんか？
以下いくつかのプロセッサのシフト命令に関して
（これは左シフトではなく右シフトの話。参考『高性能マイクロプロセッサアーキテクチャ』）
歴史的理由から「算術シフト」「論理シフト」と言われるが、現代的には「符号付き（signed）数のシフト」「符号なし（unsigned）数のシフト」とすべきだろう。
プロセッサの命令において、符号付き数と符号なし数をどう扱い分けるかには大きく 2 種類の流儀がある。ひとつは 8086 の加算命令などの方式で、命令自体では符号付きと符号なしを区別せず、対象が符号付きの時のためのフラグと符号なしの時のためのフラグがある、というもので、具体的には、キャリーフラグが対象を符号なしとした時の溢れのフラグ、オーバフローフラグが対象を符号付きとした時の溢れのフラグである。
一方、乗算命令は、対象が符号付きか符号なしかで、別々の命令になっている。これは加減算のように、結果を共用できないためである。
では、左シフトはどうあるべきだろうか。
仮に、符号ビットだけ保存する左シフト命令があったとしても、8 ビットで -127（ 0b10000001 ）を 1 ビットシフトして -126（ 0b10000010 ）になることが嬉しいようには思えない。
加算命令と同じようにフラグを変化させるとするなら、左シフトで、はみ出たビットに 1 があればキャリーフラグをオン、シフトの前後で MSB の値が変化したのであればオーバフローフラグをオンとする、とするのが妥当な仕様と考えられる。
あるいはフラグが複数ないようなアーキテクチャであれば、溢れの検出として前述のそれぞれを選ぶ命令とすることが考えられる。左シフトを算術と論理に分けるとするなら、そのような差異とするのが妥当ではないだろうか。
抜け穴、多分無いと思いますが、どうでしょうか？
int
signed_shift_right(int x, unsigned a)
{
return ( (x < 0) ? (-(-(x+1)>>a)-1) : (x >> a) ) ;
}
7.3 節「混合展開系の構成」で、ホーナー法の乗算のかわりに除算をおこなう形をした「展開 I」と、連分数の形に展開する「展開 II」について、あっさりと流しているが、実際にはこの本のこの後の部分で、ほとんど詳しい言及のないまま、時折不意に入れ替わることがあるので注意が必要である。
「展開 I」と「展開 II」では具体性がないので、ここでは以降それぞれ「拡張 Horner 法型」「連分数型」と呼ぶ。念のためそれぞれの形を示す。
拡張 Horner 法型
連分数型
ここで、この 2 つの形の相互変換についての詳しい説明もないが、次のように変形すればよい。
\[y_i = x・y_{i+1} + c_i\]\[y_{i+1} = \frac{1}{x・y_{i+2} + c_{i+1}}\]これを、以下のように変形する。
変形がこのようになるため、どちらの形の展開かがはっきりしないと、次数ないし係数と P か C の対応は決まらない。7.3 節のこのすぐ後の P と C の定義では、C は連分数型としている。
表 7.1 と、表 9.3 では、一見対応がおかしいように見える。たとえば、最大相対誤差が 2.209×10-11 の時の展開形が、表 7.1 では PCPCP となっていて、一方表 9.3 では PCPC となっている、というように見える。これは、「PCPC」といった記法では、最高次については cn := 1/cn のように読み替えれば一意であることから、最高次は省略しているのであるが、表 7.1 では、省略される最高次についても P として示しているためである。8 節のプログラムの出力においては、入力されるデータによっては最高次が C 型（つまり 1/cn）のこともあるため、やはり最高次についても P か C かを表示している。
LU 分解と、それを利用した連立方程式を解くコードについては読者が補完することとなっているが、ここで LU 分解する対象は二次元配列 w[j, i] （ 0 ≦ i, j ≦ n ）である。LU 分解にはいくつか手法があるが、部分ピボット選択で十分のようである（私はそうした）。ps という配列が宣言されているが、これを、ピボット選択で入れ替えた行を記憶するのに利用する。配列 w を保存する必要もないので、L と U に in-place に置き換えてゆくアルゴリズムが使える。solve の引数は、solve(var b,c:adgr) となっているが、配列 b が in 引数で、c が out 引数である。
function minimaxr の最後に「minimax:=final」という代入文があるが、これは「minimaxr:=final」のバグ。またメインプログラムのほうに「b[n]:=gamma;」という代入文があるが、b という配列は無いのでコンパイルエラーになる。これもおそらく修正ミスか何かによるバグなので、この代入文は削除する。
また前述したように、入力されるデータによっては最高次が C 型（つまり 1/cn）のこともあるため、このプログラムの出力では、通常本書では省略している最高次についても、P か C かを表示している。
配列の引数について、type dg=0..m; dp=0..m; のように型を定義して使っているが、この型は unsigned になるため、0-1 を計算したりすると -1 ではなく正の大きい値になってバグとなるので注意が必要である。
入力データの先頭の 0.3084.... という数値は (π/4)**2 / 2 である（奇関数である tan の近似を求めているので x を x**2 とみなして計算しているため）。
この節の説明は、どうも、連分数型で説明してあったのを拡張 Horner 法型に書き直したような感じで、一部、注意が必要な部分がある。
乗算の回数の点で有利なので、最終的な近似関数は拡張 Horner 法で書きたいが、実験中であれば、ここに書かれている通りに実装するのではなく、P と C の定義の通りに、連分数型で実装したほうが良いと思う。
ここの記述で具体的に問題があるのは (3) 中段の計算 と (4) 終段の計算である。まず、中段の計算では、「対応する演算子が」とあるが、ここでの計算は拡張 Horner 法型であるので、前に示したように対応が一つずれることに注意しなければならない。次に終段の計算では、演算子列の左端から 1 個目が C だった場合には、そこに書いてあるように s × y1 ではなく、s / y1 を計算しなければならない。
「The Art of Multiprocessor Programming 並行プログラミングの原理から実践まで」のロックフリー並行スキップリストの実装についてのメモ
数学では同値関係といって、関係 ≡ が、
が成り立つような関係であるとき、≡ を同値関係という
C 言語の == 演算子など、プログラミング言語における比較演算も、このような性質をだいたい満たすことを期待したいわけだが、現実には多かれ少なかれ例外がある。以下、そのような例外の例である
以上のように、JavaScript や PHP の === は、常に == ではなく === を使え、と言ってもいいぐらいのものであるが、一方、Ruby の === は反射律すら通常満たさないという、== とは違う演算子であるので、混同しないようにしたい
なお、英語では equality と equivalency という用語があり、前者は {(x, x)|x ∈ X} という関係で、日本の数学では「相等」と呼んでいるもの、後者は同値関係の「同値」である。オブジェクト指向プログラミング言語で考えると、対象のオブジェクトIDが同じであれば同じ、とするのが前者と言えようか
Scheme には eq? eqv? equal? がある
if 文や while 文などで if (条件式) { ... } や while (条件式) { ... } の「条件式」を評価した値として、真として扱われる値を truthy 、偽として扱われる値を falsy という
どうも JavaScript 方面で使われ始めた用語のようだが（ http://d.hatena.ne.jp/mizuno_takaaki/20080608/1212869562 などを参照）、たいへん便利なので他の言語についてもまとめてみる
ISLISPでは、このような「真偽値型ではないが、真偽とみなした値」という意味の用語として、「準真偽値」（quasi-boolean）と呼んでいる（ http://jxck.hatenablog.com/entry/20110708/1310080199 も参考になる）。
C 言語には真偽値の型、といったようなものは存在せず、整数型（ int ）でまかなっている。偽の代表値が 0 、真の代表値が 1 で、真偽反転の前置演算子 ! の結果などは必ず 0 か 1 になる（ならない処理系があるらしいが、そういう処理系には「非標準」と大垣してほしいものだ）
条件式の値としては、任意の値を使うことができ、整数値 0 として評価できる値か、ヌルポインタが偽、他は全て真である。整数値 0 として評価できる値として、浮動小数点型の 0.0 と -0.0 や enum で 0 に対応付けられた値などが falsy である
Haskell 等では真偽値型以外の値を、条件式に使うことができないので、truthy な値は True、falsy な値は False のみである
伝統的な Lisp では、ヌルポインタや空リストの意味でもある値 nil が falsy で、他の値は全て truthy である
Common Lisp では、nil が falsy でそれ以外の全てが truthy だが、そのようにして真偽値として扱うことについて generalized boolean という用語がある。
Scheme は伝統的な Lisp から敢えて改めている点が多いが（特に近年の標準では）、真偽値についても、真と偽の代表値 #t や #f があり nil がない。また #f のみが falsy で、他の値は全て truthy である（とくに空リスト () も truthy であるので、従来の Lisp のコードをそのまま使う時は特に注意が必要な場合がある）
TBD
Ruby では nil と false のみが falsy で、他の値は全て truthy である。真の代表値として true がある。また真偽値のクラスというものがなく、true は TrueClass、false は FalseClass である（ついでに、nil は NilClass である）
Perl では 0、文字列 '0' と ""、空リスト ()、undef が falsy で、他は truthy である。特に真偽値はない
Haskell Mailing list の Wed, 5 Feb 1992 の投稿（ http://code.haskell.org/~dons/haskell-1990-2000/msg00737.html ）より
Wadler's Law: The emotional intensity of debate on a language feature increases as one moves down the following scale: Semantics, Syntax, Lexical syntax, Comments.
HaskellWikiも参照のこと http://www.haskell.org/haskellwiki/Wadler's_Law
Lennart Augustsson氏の「Bluespec --- Designer's Perspective」（ http://csg.csail.mit.edu/IAPBlue/workshop/Augustsson-designer.pdf ）の 3 ページ目によれば、
Robin Milner: People discussing concrete syntax are like people getting into a car; they become animals.
と言った、とのことである。
英語では Parkinson's law of triviality（パーキンソンの法則）、その具体例として bikeshedding あるいは bicycle-shed example とも呼ばれる。直訳すると 自転車 庇 であるが、自転車置き場の雨避け用の庇のことであり、意訳して自転車置き場の議論、などとも言う。
フラッシュメモリは flash memory だが、動作原理的には、押し流す（ flush ）メモリという印象がある。実は開発の時点では flush とするつもりだったが、社のほうから（フラッシュメモリの発明は東芝社内でおこなわれた）商品化にあたりトイレの水洗に使う flush valve などを連想させる flush の語は NG である、と言われたためだ、という話を聞いたことがある。
という疑問を持っていた方がいて、しばらく温めていたのだが、どうも「訪問者カウンター」を作るのにロックが要るからではないか（awkではちょっと簡単には無理）というのがそれっぽそうである。
http://www.iijlab.net/~ew/know_thyself.html
(K先生、ある講演後のQAで) Q. 将棋プログラムの発展で、何か「先生の予想を超えた特異な跳躍」はあったか？ A. だいたい予想の範囲内だったが、強いて挙げるとすればパラメータの自動生成（の登場、ボナメソのこと）による発展が大きかった。
(別の研究者と、プログラミング関係のシンポジウムでの雑談にて) 大きかったが、それでもテクニカルにはだいたい2年ぶんぐらいがいっぺんに進んだぐらい。ただし、テクニカルな点だけでなくマイボナなどで、コンピュータ(将棋)の専門家でなくてもあれこれ試せるものを公開したことで、各所に刺激を与えた、という点も大きい。
FOLLOW()の計算を間違えにくくする工夫 http://kunishi.blogspot.jp/2012/08/follow.html