newLISPの内部
SDを買ったついでに横に有ったCQ誌も久しぶりに買ってみた。だって最近はちっとも書店へ 行かないんだもの。
相変わらずの広告ですなあ。トランシーバー１台が110万円って、無銭家とは違う世界の 人達用だな。株で儲けて小金がじゃらじゃらしてる人用か。車が一台買えますよ。
還暦ハムの7MHzリニアアンプ製作奮闘記ですって。アンプの形式は爺々もとえ、GGアンプ (grounded grid Amp.)ですって。勿論、球ですよ。プレートに800Vもかけてるって事は、人生の終いにどうぞってのも 兼ねているんだな。納得。おいらも一台作っておきたいぞ。
この方、πマッチに使う、高耐圧用のバリコンは、ハムフェアと言うジャンク市で手に入れ、 出力が出ないと空で嘆いていたら、空から高出力用のトランスが降ってきたという、幸運の 持ち主。球は最初6KD6を捜しておられたようだけど出物が無し。30KD6が2本、オークションに 出ているのを発見して、手に入れたとか。
回路は既に絶版になった、リニアアンプ・ハンドブックを司書のオネーチャンに探して 貰ってきて、それをコピペしたとか。さすが年の功。世渡りが旨い。伊達に年は取って おりません。だから、年寄りは大切に。オイラーの事を、爺々と軽々しく呼ぶな ＞ XYL。
CQ図書部屋なんてのが新設されてた。ハムに関する本の紹介コーナーだな。先月はモールス通信士が 取り上げられていたようだけど、今月は電波の発見に貢献したファラディーさんと マクスウェルさん。２人は手紙のやりとりをしてたそうだ。狭い世界だったんですねぇ。
ファラディー伝と言うのを愛知敬一さんと言う方が執筆したそうだけど、著作権が切れて 青空文庫 に上がっている。青空工作員はハムの方。有り難く拝読しましょう。
マクスウェル繋がりかどうかは不明だけど、JA1ANこと原昌三さんが、マクスウェルと電磁方程式って思い出を 執筆されてる。ドイツはミュンヘンの博物館にヘルツの送受信機が展示してあるそうな。 それを見て、なるほどなぁ と思ったとか。
オイラーも昔、ドイツに駐留してた時に、同博物館へ行った事があるぞ。やたら広くて、 昔の飛行機がいろいろ展示されたのを鮮明に覚えているよ。
それからBMWも博物館。こちらで強烈だったのは、鍵マークのついたオートバイ。昔は、 オートバイも兵器扱いだったんですねぇ。壊れないように、メンテナンスしやすいように ってんで、技術が鍛え上げられて、有名になったんだな。
ああ、SDの補足が出てました。 増補版:気軽に試してみよう！今こそ Lisp 入門
fftの結果表示
前回は、ひょんな事からfftに対面した。fftの結果は複素数が返ってくるんだけど、 それの絶対値を求めて、パワースペクトラムと称したけど、本来は違うみたいね。
音のプログラミング本によると、実部は振幅スペクトラム、虚部は位相スペクトラムって 説明になってた。音響の世界では、人間が相手なんだけど、位相なんて耳で検知出来ない から、無視される事が多く、もっぱら振幅スペクトラムに注目が集まるらしい。
その本にお馴染みの複素数を極座標で表す図が載ってた。そうか、それならfftの結果を 極座標で表すのもオツなものだね。やってみるか。えと、gnuplotで出来るんかいな？
何か忘れていないか？ 以前書いた、htmlで図を描くやつがあるじゃん。あれを使えよ。
(module "pc.lsp")
(define (grf v)
(setq xy (apply max (map abs (flat v))))
(setq nxy (sub 0 xy))
(pc:html "<h3>Polar figure</h3>")
(pc:canvas )
(pc:vbox nxy nxy xy xy)
(setq R 0.1 G 1.0 B 1.0)
(pc:line-color R G B)
(setq N (/ (length v) 4))
(setq N1 (- N 1))
(dolist (i v)
(pc:move 0 0)
(pc:draw (i 0) (i 1))
(when (= (% $idx N) N1)
(pc:line-color (inc R 0.2) (dec G 0.25) (dec B 0.25))))
(pc:line-color 1.0 0.1 0)
(pc:move nxy 0) (pc:draw xy 0)
(pc:move 0 nxy) (pc:draw 0 xy)
(pc:render) xy)
(define (show wv)
(setq fd (fft wv))
(setq pd (1 (/ (length fd) 2) fd))
(grf pd))
;(setq wv (series 1 1.1 1024))
(setq wv (rand 6 256))
(show wv)
(exit)
書き下ろしのコードなんで、整理が付いていないけど、まあいいか。思いついたらさーと 描けるのが利点のLLですから。
wvに波形をセットする。fftの都合によりリストの長さは２のべき乗にする事。 それをfftし、結果の複素数群から、直流成分と、折り返し部分を除いたものを作る。 pythonみたいに、リストのスライスが出来てラクチン。 そして、その結果を極座標表示ルーチンへ渡して、ブラウザーに表示。
表示ルーチン内では、表示範囲の座標の大きさを決める必要がある。複素数の組をまずは フラットにして、絶対値を取る。そして一番大きい数値を見つける。 後は、その数のマイナス値を求めておいて、仮想座標をセット。
ベクトルの表示は、原点から、ベクトルの先まで、ただ線を引くだけ。それを、複素数の 数だけ実施。後は、X軸とY軸を描いて終了。 周波数帯域を４つに分け（低い、やや低い、やや高い、高い）、線の色を変えるように してあります。
一応、最大値を返すようにしておいたので、 座標の最大値が分かるよ。
波形は、サイコロを256回振った時の出目をFFTしてみた。某放送局を見学した時に、オイラーの 目を引いた、ベクトル表示のオシロスコープみたいな結果が出て満足。 ソニーのコマーシャルにも出てきていたね。音響の世界では、当たり前の表示方式なんだろうか。
もう一つ、コメントになってる波形。実行してみると綺麗な模様が出てくるよ。 この元波形は、１万円を年利１割で1024年に渡って預けた時に、幾らになるかってのを 計算したもの(等比数列)。夢のような金額になるぞ。そんなに生きられないって！ ごもっとも、 だったら、せめて解析結果を楽しんで見て。
ああ、そうだ、血圧のデータも解析してみるかな。測定グラフを見てると、数日から10日間 ぐらいの周期で高い時と低い時があるように見える。サラリーマン時代なら、一週間周期で 高い低いがあるのは肯けるけど、freeになった今も周期性があると思えるぞ。顕著な周期性が 認められたら、学会に発表ですかね。
で、データをどうやって今のスクリプトに持ち込む？ read-file関数をコピペして、CSVファイルを 読み込むか？ そんなのLisperらしく無い。以前の血圧グラフを書くスクリプト環境中では、 Lisp形式のデータが揃っているんで、それをdumpすればいいだろう。
世界共通のフォーマットったら、 JSONだな。厚切りジェイソンに頼むか？ まさか！ そんな事もあろうかと専用関数が用意 されてる。saveとかsourceさ。load関数と対になるやつ。(save "mydata.lsp" 'am 'pm) とかすれば、 データが保存され、後はそれをloadすればOK。ファイル名にURLを与える事も出来て、その 場合はhttpプロトコルを使って、save/loadされる。
256日分のデータを極座標表示してみたけど、サイコロを振った図と大差なかったぞ。贔屓目に 見てただけかな。
dump-symbol
前回はCELLのメモリーがどうなってるか見た。って、前回からの続きばっかりだね。 まあ、あれもこれも思う所があるからね。
で。dump繋がりで、シンボルもダンプ出来るみたい。使えるようにするには、スイッチを入れて から、再コンパイルする必要が有る。設定はnewlisp.hに書くのが、一応のお約束。
#define SYMBOL_DEBUG 1
修正後、makeすれば良いはずなんだけど、今のMakefileでは、ヘッダーファイルの変化を 検出して再コンパイルって機能は付いていない。まあ、ユーザー先でインストールするのが 目的なんで、八苦用にはなっていないって事。
Makefileを修正するのが筋だろうけど、運試しに newlisp.o nl-symbol.o の２つのファイルを 削除してからmake。何故か？ チラ見した所、関数はnl-symbol.cに定義されてる、 その関数を登録してるのは、newlisp.cの中だから。これだけで済めば、強運。
適当に登録されてる関数名を入れてダンプしてみる。
> (dump-symbol "and") name=and color=red parent=> left=abs right=begin true > (dump-symbol ">") name=> color=black parent=cond left=% right=and true > (dump-symbol "cond") name=cond color=red parent=dump-symbol left=> right=define true > (dump-symbol "dump-symbol") name=dump-symbol color=black parent=macro left=cond right=for true > (dump-symbol "macro") name=macro color=black parent=ROOT left=dump-symbol right=sequence true > (dump-symbol "ROOT") nil > (dump-symbol "cons") name=cons color=black parent=constant left=NIL right=NIL true
どうやらシンボルは木に登録されてる。気になる木だな。最近はこのコマーシャルが流れる 番組は見てないけど、まだやってるのかしらん？
左と右の枝、それに親の枝を辿れるようになってる。どんどん親の枝を登って 行くと、最後は根っ子のROOTになるのね。一方、左と右に枝が無い節も あるのね。節には赤とか黒の色分けがしてある。こういう木を赤黒木って 言うそうだ。
普通のLispとかSchemeだと、このあたりはhashを使うんだけど、木にこだわって みましたってLisperらしい。そう言えば、Lisper御用達のconsの連鎖は、普通は 単方向リストって捉えるけど、L木とも言うそうな。確かに、リストの図表現方法を 木のように書くと、car部分が葉で、cdr部分が枝のように見えるわな。
赤黒木について少々調べてみたぞ。
木構造とハッシュ―平衡二分探索木「赤黒木」で知る豊かなデータ型
この赤黒木がnewLISPの中では、どう使われているか？ CRUDの観点で見て行く。ああ、赤黒木には Uに相当する更新ってのは無いな。U相当をやるなら、DしてからCだ。更新したい節を消して、 新しいのを作る。
例によってソースの名前から、扱っている所を推測すると、そう、nl-symbol.cになる。 一番頭に書いてあったのが、p_symbols。 これ、システムに収監されてるシンボルをリスト にして返してくれるやつだな。
> (module "pc.lsp") MAIN > (symbols pc) (pc:// pc:Linux pc:XMAX pc:YMAX pc:all pc:alpha pc:blue pc:body-close pc:body-html pc:bottom pc:canvas pc:canvas-name pc:canvas-script pc:canvas-template pc:color pc:display-html pc:draw pc:eval-string-js pc:files pc:fill-color pc:gr_xconst pc:gr_xfac pc:gr_yconst pc:gr_yfac pc:green pc:header pc:header-tags pc:height pc:html pc:left pc:line-color pc:line-feed pc:line-width pc:mode pc:move pc:other pc:page pc:pc pc:prog pc:red pc:render pc:right pc:script-close pc:script-header pc:script-template pc:show-in-browser pc:str pc:tags pc:template-header pc:top pc:unix pc:vbox pc:width pc:x pc:xp pc:xpen pc:y pc:yp pc:ypen)
引数を指定しないと、MAINのシンボルが表示される。
ざっとファイルを眺めると、前半はnewLISP用のコード、後半は赤黒木の実現って感じ。 面白そうな、
/*
* if forceFlag is TRUE then create the symbol, if not found in the context
* specified in that context else if not found try to inherit from MAIN as a
* global or primitive, else create it in context specified
*/
SYMBOL *translateCreateSymbol
(char *token, int type, SYMBOL * context, int forceFlag){
:
にBPを置いて、gdbで観察してみる。
(gdb) bt #0 translateCreateSymbol (token=0x80ad653 "while", type=263, context=0x2880d180, force\Flag=1) at nl-symbol.c:167 #1 0x08051e9f in initialize () at newlisp.c:1338 #2 0x08050dae in main (argc=1, argv=0xbfbfec7c) at newlisp.c:722
追って行くと、forceFLAGが立ってるので、findInsertSymbolに飛んでくる。この中では、 指定したものが登録済みかまず確認。
while (current != NIL_SYM) {
if (((c = str2cmp(key, current->name)) == 0) && ((c = strcmp(key, current->name)) == 0))
return (current);
検索を効率よく実施する為、まず先頭文字だけ確認。一致してたら、全文字列を比較してる。 ちょっとしたテクニックだねど、高速化寄与率高いと思われ。
その後、シンボル用のメモリーをcallocMemoryで確保、一シンボルでどれぐらいのメモリーを 使うかと言うと、
(gdb) p sizeof(SYMBOL) $1 = 32
egdb君はちゃんと知ってました。
typedef struct tagSYMBOL {
int flags;
int color;
char *name;
UINT contents;
struct tagSYMBOL *context;
struct tagSYMBOL *parent;
struct tagSYMBOL *left;
struct tagSYMBOL *right;
} SYMBOL;
わざわざ計算してみなくても、潜れば、サイズが露わになりますよ。
callocMemory (nbytes=32) at newlisp.c:2349 2349 if ((ptr = (void *)calloc(nbytes, 1)) == NULL)
そして、その後、リンク等の処理をして戻って来て、
} else {
=> sPtr->name = token;
sPtr->contents = (UINT) nilCell;
}
sPtr->context = context;
return (sPtr);
で、シンボルの名前を埋め込んでいる。プリミティブじゃない場合は、if文のtrue句の 中にある
len = strlen(token);
sPtr->name = (char *)allocMemory(len + 1);
memcpy(sPtr->name, token, len + 1);
が実行されて、名前の文字列が、埋め込まれる。プリミティブの場合は、primes.h内で 定義されてる、primitive[]の中の文字列(コンパイル時にアドレス確定）が使われるのだな。 とかく、文字列は何処に入ってるってのが軽視されるけど、これで疑問が氷解しましただ。
挿入や削除をすると、木のバランスが崩れる。それをほっておくと、検索の時に性能低下を 起すんで、バランス修正を行う事が大事。insetFixupとdeleteFixupがその任に当たっている。 ややこしいのに、コードを読むのはやめましょ。こういうのをネチネチするのは、盆栽を趣味に する人に任せましょう。あるいは、静岡にある盆栽学校に入校するとか。 枝ぶりを整える親方になれますよ。
ついでに、primitiveも見ておくか
(gdb) p primitive[0]
$2 = {name = 0x3abaa41b "dump-symbol", function = 0x1abbe980 <p_dumpSymbol>, flags = 0}
(gdb) p primitive[1]
$3 = {name = 0x3abaa42a "while", function = 0x1abb5550 <p_while>, flags = 2}
(gdb) p primitive[2]
$4 = {name = 0x3abaa433 "until", function = 0x1abb5510 <p_until>, flags = 2}
ソース上では、こんな定義だけど、メモリー上では、上のようになるのね。
PRIMITIVE primitive[] =
{
/* --------- core ------------------ */
#ifdef SYMBOL_DEBUG
{"dump-symbol", p_dumpSymbol, 0},
#endif
{"while", p_while, 2},
{"until", p_until, 2},
まだまだ、このあたりの脳内変換が弱いな。そうだ、こういう時は、バイナリーエディタで、 開いてみれば良いのか。万能ツールのemacsでは、普通（強引）にバイナリーファイルを開き、 M-x hexl-mode すればいいんだな。
専用のものだと、hexeditとかbviとかがunix用に用意されてる。試しにbviを入れてみたぞ。 TABキーで、hex部分と文字部分を行ったり来たり出来る。viと言うかexを使える人にはお勧めだな。 bmoreなんてのも付いてくるしね。（システム備え付けのhexdumpでもいいけど、こちらの方が楽な事は確かです）
この際なんで、構造体を使って、newlispの関数登録あたりを真似てみる。CELLを受け取って、 CELLを返すんじゃ、大事過ぎるので、やんわりと文字列を返すやつです。
#include <stdio.h>
char* p_panda(){ return "Collect money"; }
char* p_fire() { return "Match pump"; }
char* p_true_t() { return "Source from ntp.nict.jp"; }
typedef struct {
char *name;
char* (*pfunc)();
short int flags;
} PRIMITIVE;
PRIMITIVE primitive[] = {
{"panda", p_panda, 0x6e},
{"fire", p_fire, 0x77},
{"true-time", p_true_t, 0x75},
{NULL, NULL, 0},
};
main(){
int i;
for (i = 0; primitive[i].name != NULL; i++) {
printf("struct-base: %p\n", &primitive[i]);
printf("func-adr: %p\n", primitive[i].pfunc );
printf("result: %s\n", primitive[i].pfunc() );
}
}
実行結果
[sakae@fb10 ~/pc]$ ./a.out struct-base: 0x804988c func-adr: 0x8048590 result: Collect money struct-base: 0x8049898 func-adr: 0x80485a0 result: Match pump struct-base: 0x80498a4 func-adr: 0x80485b0 result: Source from ntp.nict.jp
構造体のサイズは12バイトでtextの後ろの方に配置されてる。そりゃそうだわな。文字列への ポインター２本と整数１個だから、12バイト。short intもintで代用ですな。
このバイナリーファイルをbmoreで閲覧すると、文字列は
000006C0 83 EC 0C E8 68 FE FF FF 83 C4 0C C3 43 6F 6C 6C ....h.......Coll 000006D0 65 63 74 20 6D 6F 6E 65 79 00 4D 61 74 63 68 20 ect money.Match 000006E0 70 75 6D 70 00 53 6F 75 72 63 65 20 66 72 6F 6D pump.Source from 000006F0 20 6E 74 70 2E 6E 69 63 74 2E 6A 70 00 70 61 6E ntp.nict.jp.pan 00000700 64 61 00 66 69 72 65 00 74 72 75 65 2D 74 69 6D da.fire.true-tim 00000710 65 00 73 74 72 75 63 74 2D 62 61 73 65 3A 20 25 e.struct-base: % 00000720 70 0A 00 66 75 6E 63 2D 61 64 72 3A 20 20 20 20 p..func-adr: 00000730 25 70 0A 00 72 65 73 75 6C 74 3A 20 20 20 20 20 %p..result: 00000740 20 25 73 0A 00 00 00 00 01 1B 03 3B 10 00 00 00 %s........;....
こんな所に固まっていた。不変なデータは一箇所にって方針。readelfでセクション・ヘッダーを見ると
Section Headers: [Nr] Name Type Addr Off Size ES Flg Lk Inf Al [12] .text PROGBITS 08048380 000380 000340 00 AX 0 0 16 [13] .fini PROGBITS 080486c0 0006c0 00000c 00 AX 0 0 4 [14] .rodata PROGBITS 080486cc 0006cc 000079 01 AMS 0 0 1
確かに、rodataは、ファイルオフセット0006ccの所に鎮座してる。コードは380の所からだな。 gdbにかけられるようにフラグを付けてコンパイル。mainで止めて、メモリー検査。
(gdb) p &primitive
$1 = (PRIMITIVE (*)[4]) 0x804988c
(gdb) x/12w 0x804988c
0x804988c <primitive>: 0x080486fd 0x08048590 0x0000006e 0x08048703
0x804989c <primitive+16>: 0x080485a0 0x00000077 0x08048708 0x080485b0
0x80498ac <primitive+32>: 0x00000075 0x00000000 0x00000000 0x00000000
(gdb) x/s 0x8048708
0x8048708 <.rodata+60>: "true-time"
(gdb) set print pretty
(gdb) p primitive
$2 = {{
name = 0x80486fd "panda",
pfunc = 0x8048590 <p_panda>,
flags = 110
}, {
name = 0x8048703 "fire",
pfunc = 0x80485a0 <p_fire>,
flags = 119
}, {
name = 0x8048708 "true-time",
pfunc = 0x80485b0 <p_true_t>,
flags = 117
}, {
name = 0x0,
pfunc = 0,
flags = 0
}}
(gdb) disassemble 0x8048590
Dump of assembler code for function p_panda:
0x08048590 <p_panda+0>: push %ebp
0x08048591 <p_panda+1>: mov %esp,%ebp
0x08048593 <p_panda+3>: lea 0x80486cc,%eax
0x08048599 <p_panda+9>: pop %ebp
0x0804859a <p_panda+10>: ret
End of assembler dump.
同じ事を、OpenBSDでやると、実行する度に、primitive配列のアドレスや関数のアドレスが ランダムに配置されてました。このランダム性はmallocで領域も貰う場合だけじゃなかったのね。 徹底してるな。
このランダム性をどうやって担保するか？ その片鱗が、関数にも及んでいました。 FreeBSDでは、素直に文字列の位置が埋め込まれていて、それを返しているだけ。 OpenBSDは、ecxレジスタからの相対になってる。そして、そのecxに、ランダムな値の ベースが埋め込まれているんだな。
(gdb) disassemble 0x18f7fab4 Dump of assembler code for function p_panda: 0x18f7fab4 <p_panda+0>: push %ebp 0x18f7fab5 <p_panda+1>: mov %esp,%ebp 0x18f7fab7 <p_panda+3>: sub $0x10,%esp 0x18f7faba <p_panda+6>: call 0x18f7faaf <__i686.get_pc_thunk.cx> 0x18f7fabf <p_panda+11>: add $0x200016b9,%ecx 0x18f7fac5 <p_panda+17>: lea 0xffffde89(%ecx),%eax 0x18f7facb <p_panda+23>: leave 0x18f7facc <p_panda+24>: ret End of assembler dump.
ふーーぅ、納得しましただ。