Macr055発表の反省

プロシンでいただいたコメントとかに対するメモ

再帰的なマクロの例が欲しい

(言い訳: 「マクロに展開されるマクロ」がちゃんと再帰的に扱えれば、あとはそのマクロが自分自身でも同じことだ、と思っていたのですが)質疑応答のかなり最後のほうで、「再帰(によるループ)ができても、ifelseのようなことができないと、再帰すると止まらなくなるので結局使えない。一方ifelseがあればそれと再帰でいろいろできる」というように回答したのだけども、ifelseを紹介したついでとして何か簡単な「再帰的なマクロ」の例があればよかった(多分それで時間もバランスが取れたかもしれない)

プッシュバックの様子とかが可視化されるデモみたいなので説明が欲しい

(デモ用途に限らず、マクロプログラミング(特にデバッグ)に有効だろうと考えていて、インタフェイスを考えてるところ)

予稿のリファレンスの番号がズレている

後から確認したら、「LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.」が出てないか注意しましょう、というオチでした(参照番号が[?]になったりはしていなかったので油断した)。

「m55_define」は長くてうっとうしい

(設計者の弁: ユーザが任意の名前を使えるよう、処理系組込みの名前は「予約名前空間」のようなイメージで全てプレフィクスを付けている)

「例えば def という名前にしたりはできないのか」ともコメントされたので簡単に検討したところ、現在の仕様では全く透過的にはできないことがわかり、定義ではなくエイリアスの機能があったほうが良いかも、と思ったのでその後で簡単に実装した(抜けとかあるかもしれないのでそのうちチェックしたらリポジトリを更新する予定)。

『ソフトウェア作法』は「さくほう」

と読むのだ、と訳者の先生ご本人がおっしゃっていた、とのコメントが。(両方を掛けている、とどこかで読んだ記憶があるんだけどなぁ……)

簡易回転計算

というツイートを見て、少し考えてみました。

角度が θ(以下、全てラジアン(弧度法)とする)で、ごく小さい( θ ≒ 0 )時、sin(θ) ≒ θ, cos(θ) ≒ 1 という近似もありますが、それとは少し違う感じです。

ピタゴラスの定理から sin2(θ) + cos2(θ) = 1 という関係がありますが、それを変形すると、互いに sin(θ) = √( 1 ー cos2(θ) ), cos(θ) = √( 1 ー sin2(θ) ) となりますので、それをちょっと考えてみます。すると次のように、cos の側から計算するとうまいこと変形できて、

√( 1 - (127/128)2 ) = √( 1 - 16129/16384 ) = √( 255/16384 ) ≒ ( 16/128 ) = 1/8

のように、cosの側を基準にするとsinがわずかに大きくなっている近似と言えます。

ここでもう少し √( 1 - ((N-1)/N)2 ) について考えてみますと、

√( 1 - ((N-1)/N)2 ) = √( 1 - (N-1)2/N2 )

   = √( 1 - (N2-2N+1)/N2 )

   = √( (N2-N2+2N-1)/N2 )

   = √( (2N-1)/N2 )

   = √(2N-1) / N

となりますので、2N(か、2N-1)がちょうど平方数になり、かつその平方根がNの約数、というような時にうまく上記の場合のような関係になることがわかります(例示の場合では N = 128、平方数が256=162)。

小さい方を考えてみますと、

N = 98 の時 97/98 と 1/7 (平方数が196=142

N = 72 の時 71/72 と 1/6 (平方数が144=122

といったようにして同じような関係は(誤差がだんだん大きくなりながらも)成立していますが、うまく2の冪の計算が8ビット機で使えるのは、1/8が出てくる上記の場合だけでしょう。

process reaperの実験

procctlという、プロセスの属性の一部を制御するAPIFreeBSD 10で追加されたものですが、10.2 でそれに reaper facility と呼ばれている機能が追加されました。基本的な機能性はLinuxを参考に(Linuxでは prctl(2) というAPIです)、APIの設計はDragonflyBSDをベースにしており、manページもFreeBSDのものよりDragonflyのほうがわかりやくす書かれていますから、そちらを参考にすると良いでしょう。こちらのメイルから始まるスレッドもご参考ください https://lists.freebsd.org/pipermail/freebsd-arch/2014-December/016437.html

process reaperとは、子プロセスを作った場合の親プロセスのように、子プロセスが終了してゾンビになった後で、それに対応するwaitシステムコールを発行するプロセスのことを指します(ゾンビの魂(?)を、死神の鎌で刈る(reap)というイメージですね)。しかしこれらのAPIでは、Unixにおいて PID 1 の、通常は init が(あるいは近年のmacOSLinuxでは違いますが)受け持つ、親プロセスが先に終了したようないわゆる orphan プロセスの親となり、それらが終了した後に wait を発行する、という権利と義務(?)について、init になり代わる、という機能を扱っています。

procctlという関数名ですが、manを見るときは同名のコマンドと被ってますので、man 2 procctlのようにして参照する必要があります。

次にサンプルコードを示します。

最後のほうでforkしていて、子プロセスのほうからはxtermを起動していますので(xtermが無い環境の方は適宜修正してお試しください)、そのxtermの中のシェルから sleep 100 & など適当に時間のかかるプロセスを起動しておいてからxtermを終了し、別のターミナルなどから ps -d などで確認すると、orphan プロセスの親になっているのが確認できるかと思います。

この機能、軽量コンテナのインスタンス毎のinitとして、とかに使うためのものだろうかとか思ってますが、どうなんでしょうか? (あるいはデーモンマネジャのようなものを実装するのにも使えそうですが)

総和の計算は、なぜどのように難しいのか

プログラミング入門で、forループを使う例題としてよく出てきたりするように、総和計算は一見簡単そうですが、実はどのように難しいのか、という点を書いてみます。

まず、対象が整数であれば、大きな問題はありません。昔のようにintが16ビットの場合は、160*160=25600 でぎりぎりに近く 200*200=40000 ではもう 32767 を超えて溢れますから、intではなくlongを使うといった注意が、以前は必要だったというくらいでしょうか。

一方、対象が浮動小数点の総和は、場合によってはそう簡単ではありません。

場合として、まず、符号が正か負の片方だけであれば簡単です(代表的なものとしては内積など)。ソートして絶対値順に並べ、絶対値が小さい側の端2個のペアを取り出して、その和を計算し、結果をソートされている列の入るべき場所に挿入する、という操作を繰り返せば、基本的には問題はありません。

符号が両方ある場合は、正と負に振り分けてそれぞれ計算し、最後に差をとれば良い、と思うかもしれませんが、それではうまくない場合があります。極端な場合として、正側と負側のそれぞれの合計の絶対値が、2倍以内という近い値になってしまうかもしれません。そうなると桁落ちになります。

桁落ちという現象は、しばしば誤解が見られますが、それ自身は誤差を発生させません。正確には、絶対誤差は増えないが、値が小さくなるために相対誤差が(場合によっては文字通り「桁違いに」)大きくなる、という現象です。

そういったような場合、その絶対誤差は、そこに至るまでの計算過程での情報落ちによる誤差の積み残しの集積になっています。

直感的には、桁落ちの英語が「キャンセル」であるように、総和をとる対象中の、正負それぞれの絶対値の大きい値どうしでキャンセルできるものがあれば、それぞれでキャンセルすれば、「桁落ちは起きているが、情報は失われていない」という状態を維持できるので、それを繰り返してゆけば、正確な計算ができるはずです。

しかし、そのようなヒューリスティック的な計算をいちいちやっていては、総和計算に期待されるような O(n) に近い効率はとても実現できませんから、実際に提案されている手法は、何らかの方法で積み残しを全部残すであるとか、倍精度浮動小数点で表現可能な値の範囲全体をカバーする巨大な固定小数点で計算するとか、そういった手法になっています。

Ruby 2.4 の新機能, Array#sum

Ruby 2.4 で追加されている新機能のひとつに Array#sum があります。

(参: ドキュメントは http://ruby-doc.org/core-2.4.0_rc1/Array.html#method-i-sum

共立『アルゴリズム辞典』でも「総和計算」を立項しているように、情報落ち*1*2による「積み残し」が場合によっては著しいのが、対象が浮動小数点の時の総和計算の問題点です。

Array#sum は、Kahan summation algorithm(wikipedia:カハンの加算アルゴリズム、summation なので -総和アルゴリズム ないし -総和計算アルゴリズム、としたほうが訳としては正確)の改良版などの手法を実装しており、かなりの高精度な結果が得られます。

次のようなスクリプトで試してみると(実験に適した浮動小数点乱数を生成するため、拙作の RandomFloat を使用)、

# sum sample
require_relative 'random_float'

r_f = RandomFloat.new gt:1, lt:2**38

loop {
  arr = []
  (1000000).times {
    x = r_f.rand
    arr << x
    arr << -x
  }
  arr.shuffle!
  p arr.sum
}

そこそこ過酷な条件の総和計算ですが、次のように、ほぼ正確な結果を得られています(完全に正確ではない結果も、時折出ています)。

$ ruby-trunk -v sum_sample.rb
ruby 2.4.0p0 (2016-12-24 revision 57164) [x86_64-freebsd10.3]
0.0
0.0
0.0
0.0
0.0
-1.3322676295501878e-15
0.0
1.4654943925052066e-14
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0

Python の math.fsum との違い

ネットを捜すと、Python の math.fsum との関連で議論されていることがありますが、両者は基本的なコンセプトの点で別物です。今回実装された Array#sum は、あくまでも「高精度」であり、誤差が発生する可能性自体はあります。一方(現在の?)Python の math.fsum は、たとえて言うなら、入力や途中の計算を全て Rational に変換してから行い(実際の実装は異なります*3)、最後に浮動小数点に戻したような「正確」な結果を返すもので、前述で見たような誤差が発生することはありません。

もしそのような「正確な総和」が Ruby でどうしても必要な場合は、Rational を使ってユーザが実装すれば良いでしょう。そのような sum も(私見では、現在の sum と別の実装として、違う名前でメソッドを追加すべきだと思っています)もしかしたら今後実装されるかもしれません(関連するチケットは存在しています)。

*1:正負の要素があると、桁落ちが発生することもありますが、総和計算における主要な問題は桁落ちではありません。むしろ、正しく計画された桁落ちであれば情報は欠けないのであり、情報が積み残されて消えてしまった、という「結果が露呈する(ことがある)」のが、総和計算における桁落ちです。

*2:この桁落ちに関しては、以前のPythonのドキュメントの和訳に、原文には相当するcancellationという語は実のところ無いのですが、手違いにより「桁落ち」という表現があったため、誤解している人ももしかしたらいるかもしれません。

*3:色々な手法が提案されています。

拡張ライブラリでキーワード引数を処理する定番プラクティス(ベストじゃないかも)

ruby 2.4 リリースおめでとうございます。つい先日まで「拡張モジュール」と「拡張ライブラリ」の、どちらの呼称がobsoletedなのかいまいちはっきり認識していなかったきしもとです(ClassクラスのスーパークラスであるModuleのほうのモジュールがあるので、「拡張モジュール」がobsoletedです)。

いつのまにやら内蔵ライブラリでも結構いろいろ使われているなど、一般的になっていたRubyのキーワード引数ですが、じつはつい先日まで、C API で提供されているユーティリティ関数にバグがあり、だいぶ悩ませられていた人もあったようです。

さいわい、良いタイミングで修正されて、本日リリースされた 2.4 からは普通に使えるようになっていますので、拡張ライブラリでキーワード引数を処理する定番プラクティス(ベストじゃないかも)をまとめておきます。

1. Rubyレイヤで処理できないか検討

いきなりタイトルから外れるようなことを書きますが、doc/extension.rdoc の英語版にはあるように(日本語版では省略されている)、

  Be warned, handling keyword arguments in the C API is less efficient
  than handling them in Ruby.  Consider using a Ruby wrapper method
  around a non-keyword C function.
  ref: https://bugs.ruby-lang.org/issues/11339

といったように効率上は、Rubyで実装されたメソッドに対するキーワード引数の処理のほうが効率がよく(参照先によれば数倍?)、プログラムの見やすさのこともありますから、キーワード引数はRubyレイヤで受けて、拡張ライブラリ側で処理するのは避ける、というのも一つの手です。

2. アリティの確認

ここから拡張ライブラリの話に入ります。

まずメソッド定義の C API であるrb_define_methodなどには、キーワード引数の扱いは現れてきません。rb_define_methodの場合、第4引数( argc )を -1 にして、可変長引数のメソッドとして定義します。

そして、Rubyでキーワード引数付きのメソッドを定義した場合、アリティ(引数の個数)が、定義側(仮引数)と呼出側(実引数)で一致しているか否かは、どちらの側もキーワード引数が無いものとしてチェックされています(必須なキーワードがある場合も)。ですから、拡張ライブラリの場合もそれに合わせます。rb_define_methodで登録すべき C 関数の骨組みは次のようになります。

/* 必須な引数の個数が 1 個で、キーワード引数も取るメソッド */
static VALUE
my_kw_method(int argc, VALUE argv[], VALUE obj)
{
    VALUE h;

    /* アリティチェックよりも前にキーワード引数の存在をチェックする */
    h = rb_check_hash_type(argv[argc-1]);
    if ( ! NIL_P(h)) {
        --argc;
    }
    rb_check_arity(argc, 1, 1);  /* 必須な引数は1個で */
        /* (キーワード引数以外の)オプショナルな引数は無し */

    if ( ! NIL_P(h)) {
        /*
         *
         * ここでキーワード引数取得の処理
         *
         */
    }

    /*
     * ここにメソッドの処理の本体
     */
}

3. rb_get_kwargs

キーワード引数の処理のために用意されている C API のrb_get_kwargsですが、先日までバグっていた上に、(仕様の変遷があったため)ドキュメントがコードと一致しなくなっていました。ですので、以前にドキュメントを読んで実装してハマったというようなかたは、まずドキュメントを読み直してみてください。

「ここでキーワード引数取得の処理」となっている部分のコードは、次のようになります。

    /* 必須キーワードが 3、省略可能が 2 個、余ったキーワードがあったらエラー */
    VALUE foo, bar, baz,  quux, hoge;
     :
     :
     :
        ID table[5];
        VALUE values[5];
        table[0] = rb_intern("foo");
        table[1] = rb_intern("bar");
        table[2] = rb_intern("baz");
        table[3] = rb_intern("quux");
        table[4] = rb_intern("hoge");
        rb_get_kwargs(h, table, 3, 2, values);  // ここの「2」は、余ったキーワードを無視するなら -3 に変える
        foo = values[0];
        bar = values[1];
        baz = values[2];
        quux = ( (values[3] != Qundef) ? (values[3]) : デフォルト値 ) ;
        hoge = ( (values[4] != Qundef) ? (values[4]) : デフォルト値 ) ;

ここで、デフォルト値についてはあらかじめ変数をその値に設定(初期化)しておいて、3項演算子ではなく if による分岐で書く、というようなバリエーションもありえますが、デフォルト値にオブジェクトの生成などがあると、無駄に余計なオブジェクトを作ってしまうことになります。

一方で、必須のキーワードが無い場合に、キーワード引数がまるごと無いと、この例のように書いてしまうと変数が未初期化のままになります。そういうわけで、そのあたりはケースバイケースで書き分ける感じになるでしょう。

4. 余ったキーワードの扱い

上記のコードでは、余ったキーワードがあると "unknown keyword" ArgumentError の例外が上がります。第4引数(省略可能なキーワードの個数)を 2 から -2-1 に変えると(-1は、ゼロ個の時のための調整用(でしょう))、余ったキーワードがあっても無視されるようになります。その場合、余ったキーワード(と値のペア)はハッシュ h の中に残されます(rb_get_kwargsは、処理できたキーワードを h から取り除きます)。

余ったキーワード(意図的に任意のキーワードを、意味をもって受け付けるような場合を除いて)の扱いをどうするかは、cruby開発陣の中で、まだプラクティスが確立していません(内蔵ライブラリや、標準添付ライブラリでもまちまちになっています)。もしこの件に関心があるようであれば、時々気にしてみてください(確かチケットには(まだ)なっていません)。

5. その他

values としてヌルポインタを渡すと、値を取り出さずにキーワード引数の存在のチェックのみを行います。

移植性が(ほとんど)あり性能問題が無い(かもしれない)、負の値に対応した算術右シフトのCコード

普通は、自分のマシンでどのようなコードが生成されるかを確認して、うまくいっていればそれで良しとする所ですが、右シフトは凝ったコードを書こうとするCプログラマにとって悩みの種です。

しかし、手元の環境( FreeBSD clang version 3.4.1 )で、次のような、「あらゆる環境で2の補数マシンをエミュレーションするコード」を、

(追記: ビットパターンが 0x800...000 のようになるような最小の負の値の時には、このコードでも「未定義」を踏んでいます)と思ったのですが、最初に +1 することで回避してますねコレ。それでも未定義に落とせる抜け穴あるかな?

int
signed_shift_right(int x, unsigned a)
{
    return ( (x < 0) ? (-(-(x+1)>>a)-1) : (x >> a) ) ;
}

-O3 オプション付きでコンパイルしてみたところ、次のように「完全に」最適化されました。

$ clang -W -Wall -Wextra -pedantic -O3 -S signed_shift_right.c
$ cat signed_shift_right.s
	.file	"signed_shift_right.c"
	.text
	.globl	signed_shift_right
	.align	16, 0x90
	.type	signed_shift_right,@function
signed_shift_right:                     # @signed_shift_right
	.cfi_startproc
# BB#0:
	pushq	%rbp
.Ltmp2:
	.cfi_def_cfa_offset 16
.Ltmp3:
	.cfi_offset %rbp, -16
	movq	%rsp, %rbp
.Ltmp4:
	.cfi_def_cfa_register %rbp
	movb	%sil, %cl
	sarl	%cl, %edi
	movl	%edi, %eax
	popq	%rbp
	ret
.Ltmp5:
	.size	signed_shift_right, .Ltmp5-signed_shift_right
	.cfi_endproc


	.ident	"FreeBSD clang version 3.4.1 (tags/RELEASE_34/dot1-final 208032) 20140512"
	.section	".note.GNU-stack","",@progbits

static inline を付けて、インライン展開まで効けば、おそらく完全にオーバヘッド0のコードが生成されるものと思われます。