ときどきの雑記帖 RE* (新南口)

スターライト・セレナーデ

September 25, 2022

カレンダー

久しぶりに池袋のジュンク堂まで行ってきたのだけど 2023年のカレンダーがもう並び始めていてちと驚いた。いやまああと数日で10月だし、驚くようなことではないのかもしれないけど。

999

今日(9/25)tvkでの放送が最終回なのだけど同じ日にBS12でさよなら銀河鉄道999 を放送するのは狙ってなのか何なのか。

続編? 知らない子ですね😄

no starch

Full Catalog | No Starch Press を見ていて

NeBSDはないんだろうかと思ってしまった。

なんで no starchのサイトを見ていたかというと

なんてのを見かけてしまったからなんだけど、これもいい値段だねえ😓

デファクト

過去のもの ( 「デファクト言語」(Java)) を読み返していて気がついた

Javaの未来

エンタープライズソフトウェアではいまだデファクト言語の地位に君臨する。

という記述をみて「あーまたこんな(ry」と元記事を参照したら

it is still the de-facto language for enterprise software.

とあったりして宇宙猫に。

これ、((de-facto language) for enterprise software) じゃなくて (de-facto (language for enterprise software)) だ。後者で解釈すれば宇宙猫になる必要なかった。

gnep

むかーし、jusの研究会でこんな発表があったのです。https://t.co/j7zyDwYdKy
egrepが早かったということで。

Gnu grepは変わらないということですが。
— むとうたけし (@610t) September 12, 2022

できればきちんと裏を取ってから書きたかったのだけど、すぐには見つかりそうもないので忘れないうちに記憶をdumpしておく😄

(egrepが)「早い」は egrepの処理速度が速いとして、それはなぜかというと grepとegrepの実装の違いから来るものだったというのがありまして。大雑把に書くと egrepが入力されたパターンに対するDFAを構築してからマッチングを開始するのに対して grepはそうではないから。そしてその裏返しでegrepでは後方参照が使えなかったりしたと。

GNU grepが当時から grepとegrep(相当)で処理速度が変わらなかったというのは、一種類のマッチング用関数群だけが用意されていていつでもDFAを構築するようになっているから。え、じゃあ後方参照は? という疑問が出るかもしれないけどそこは「いろいろやってる」 (興味のある人はソースコードを(ry)。

その上で

1.xまではfgrepは別コード

というのは、grep、egrepとfgrepとでマッチングに使うオートマトンが全然違うから。実際、2.0以降でfgrepが統合された後も、 fgrep的なマッチングのための関数群は e?grep用のそれとは別々に用意されている (興味のある人はソースコードを(ry)。

grepはUNIX のversion4あたりで入ったらしいのだけど、残念ながら The Unix Tree を探してもV7のそれが見つかる中で一番古いもののよう。とは言えV7のgrepでも、それほど複雑にはなってはおらず以前のものの面影を残しているんじゃないかと思う。たぶん。

egrepとfgrepはどちらもV7からのもののようで、当時の実装の説明は grep - Wikipedia にもある。

Implementations

A variety of grep implementations are available in many operating systems and software development environments.[11] Early variants included egrep and fgrep, introduced in Version 7 Unix.[10] The “egrep” variant supports an extended regular expression syntax added by Alfred Aho after Ken Thompson’s original regular expression implementation.[12] The “fgrep” variant searches for any of a list of fixed strings using the Aho–Corasick string matching algorithm.[13] Binaries of these variants persist in most modern systems, usually linking to grep; however, using these binaries has been deprecated in favor of using the -E and -F command-line switches of grep instead.[14]

Aho-Corasickのアルゴリズムについては、十年以上前にはてなで単純な正規表現の(|を使った)連結からこのアルゴリズムを使うようにプログラム変更して高速化したとかいう話があったはず。

…ちょっと違ったかも

ということでV7でのこれら三つのソースコードは以下の場所などで参照できる。

コメントがほとんどないので追いかけづらいとは思うけど、 egrepでDFAを作っていたりfgrepでtrieを作っているのは理解できるだろう(と期待している)。

あと

のカーニハン大先生の章にも正規表現のマッチングをするコードが載っているけど、これはもっと単純なものだったような記憶がある。 grepに(\を前置したものも含めて)'|'を使った選択がなかったのもそこから考えれば納得できそうではある(実際のところは知らない)。

GNU grepが実行ファイルの名前で云々というのは過去の自分が書いている。

GNU grep を egrepという名前で起動したときに使用できる正規表現演算子は以下のものです。 grepに-Eオプションを指定したときと似ていますが、全く同一というわけではありません。また、通常egrepという名前が付けられているものに比べ、使用できる演算子が増えているので注意が必要です。
2003年2月21日付記: GNU grep 2.5では-Eオプション指定時の挙動と egrepという名前で起動したときの挙動は同一です。-Eオプション指定時の動作については前の項を参照してください(2.4あたりでこうなったようです)。

(完全には消去していなかった自分偉い)

残念ながらGNU grepのソースコードは2.0より前のコードは見当たらない。

注釈

gnepというのは、GNU grepの最初の頃の名前(のはず)。なんか当時は同じ名前を使うのも(権利関係の問題で?) はばかられていたような。

(

grepで(と’)‘が通常の文字でグルーピングを行うメタ文字が \(と\)のようになっているのは、 (や)を含む検索をすることが多くていちいちエスケープするのは面倒だっからという話を聞いた覚えがあるのだけどガセ度高めなので誰かよろしく。

specification

正規表現：曖昧なパターンはエンジンによって動作が変わる（教訓） - Qiita

(abc)?文字列\1
abcはあってもなくてもよくて、abcが先頭にあった場合は末尾にもあってほしい。

…グループの外にハテナつけたときって参照はちゃんと効くのかな…？

あとで調べる(たぶん)。

Regular Expressions

A subexpression repeated by an asterisk ( ‘*’ ) or an interval expression shall not match a null expression unless this is the only match for the repetition or it is necessary to satisfy the exact or minimum number of occurrences for the interval expression.

FORTRAN Compiler on IBM 704

呼び出し規約

http://bitsavers.org/pdf/ibm/704/704_FORTRAN_MiscMemos.pdf のp.3 Calling Sequence に次のような記述があった。

Type 1;
CLA     ARG1
LDQ     ARG2    (if ARG2 exists)
TSX     NAME,4  UPON entry ARG3, if it exists, will be stored at 7775, ARG4 at 77774, etc.

Type 2;
TSX     NAME, 4 Upon entry the n
TSX     LARG1   argument locations
TSX     LARG2   are specified in the
 "        "     address fields
TSX     LARGN   of the n words immediately following
                the entry word. Control returns to the
                main program at n+1.

どういういわれで二種類あるのかとか使い分けはとか新たな疑問もわいたけどとりあえずメモ。

また FORTRAN のp.40 Writing Subroutines for the Master Tape には

Library subroutines exist on the master FORTRAN tape in relocatable binary form. Placing a new subroutine on that tape involves (1) producing the routine in the form of relocatable binary cards, and (2) transcribing those cards on to the master tape by means of a program furnished for that purpose. Further details will be found in the FORTRAN Operator’s Manual.
In the object program transfer to the subroutine is by the sequence
   TSX Subroutine, 4
   Return
The subroutine itself and any constants that it requires should be located in relocatable locations 0, 1, 2, . . . . It may also make use of a common storage region of any desired length n, beginning with relocatable location 77777,-(n-1) and ending with relocatable location 77777,.
At the moment of transfer to the subroutine Arg1, will have been’placed in the AC, Arg2 (if it exists) in the MQ, Arg3, (if it exists) in relocatable location 77775, of the common storage region, Arg4 (if it exists) in relocatable location 77774,, etc. The common storage region may also be used for erasable storage by the subroutine. The output of the subroutine is to be left in the AC, and index registers 1 and 2 must be returned with their original contents.
Fixed point quantities in the object program exist in the following format: sign in sign bit, magnitude in decrement field, remainder of word all zeroes. It is suggested that error HALTS in subroutines be coded as HPR instructions, permitting the tag and address fields to contain identifying numbers which can be recognised at the console.

自己書換

自己書換で容量を節約しているパターン。

LATXL  CAL TXLOP                                                        4F13745
       TRA LATXL+3                                                      4F13746
LATXH  CAL TXHOP                                                        4F13747
       STP CM4105                                                       4F13748

ラベルCM4105の位置に置かれている命令が、 LATXLを経由するか LATXHを経由するかで TXH/TXLのいずれかになる。

CM4102 SXD CBAR,B                                                       4F13958 
       TXI CM4104,B,-1                                                  4F13959 
CM4104 SXD NBAR,B                                                       4F13960 
CM4105 *** MS010,0                                                      4F13961 
MS020  CAL ADSTAR                                                       4F13962 
       TRA MS030                                                        4F13963

bsearch_s

C言語でクロージャーを実現したい、あるいは実行時のコード生成によるクロージャー | 雑記帳

記事の本題とはちょっと外れるけど

// C標準のbsearch_s:
void *bsearch_s(const void *key, const void *base, rsize_t nmemb, rsize_t size,
               int (*compar)(const void *k, const void *y, void *context),
               void *context);

// MSVCのbsearch_s: https://learn.microsoft.com/en-us/cpp/c-runtime-library/reference/bsearch-s?view=msvc-170
void *bsearch_s(const void *key, const void *base, size_t number, size_t width,
               int (*compare)(void *context, const void *key, const void *datum),
               void *context);

C標準の bsearch_s に与える比較関数とMSVCの bsearch_s に与える比較関数で、context引数の位置が違うことにお気づきだろうか？

そう言えばそういう話もあったっけかと改めて調べてみると

…なんでこうなった (qsort_sなんかも同じ?)。

最後の cppreferenceのページには

References

C17 standard (ISO/IEC 9899:2018):

7.22.5.1 The bsearch function (p: 258)

K.3.6.3.1 The bsearch_s function (p: 441-442)

C11 standard (ISO/IEC 9899:2011):

7.22.5.1 The bsearch function (p: 355)

K.3.6.3.1 The bsearch_s function (p: 608-609)

C99 standard (ISO/IEC 9899:1999):

7.20.5.1 The bsearch function (p: 318-319)

C89/C90 standard (ISO/IEC 9899:1990):

4.10.5.1 The bsearch function

とあるな。VCのbsearch_sっていつ頃入ったんだっけ(調べない)。

そういや似たような話(同じ名前で引数の違う関数)を以前書いて、その後ツッコミ(情報)をもらった記憶が。

なんかブコメで叩かれていて凹んだけれども技術者でもなさそうなのでどうでも良いかという感じ。

自分は完全でもないし、これだけツイ廃のごとく書いていれば間違いも多いですが、それを恥しいとも特に思ってないです。深夜に目をこすりながら書いてたりしますし。
— 高梨陣平 (@jingbay) September 17, 2022