ピタゴラ三角 .. (n)prolog

再帰の夢

”天気晴朗なれど 波高し” これ、有名な電文。これ自体が暗号(かな)。”天気晴朗なれど 無茶寒い” な日々である。ああ、漢文の素養が無いなあ。

まあ、そんな日は風呂でまったりするに限る。車で10分そこそこの、源泉かけ流しの露天風呂へ行ったよ。空は抜けるように青く、それに紅葉が映えて、豪華な気分。つくづく日本に生まれてよかったわい。

気分良く浸かっていたら少々のぼせぎみ。風呂から出て、甲羅干し。取り留め無い事が浮かんでくる。この間読んだ、山崎豊子さんの『約束の海』に潜水艦が出て来る。司令部と連絡する時は、浮上して、アンテナを海上に出す、なんて下りがあった。

このアンテナって、1/4λなバーチカルアンテナかなあ? ハムの間では5/8の方が良いと言う伝説があるけど、実際の所はどうなんだろう? 国家秘密だからなあ。ハッチの大きさも国家秘密らしい。そんな大袈裟なものか。とか、取り留めもなく。。。

Go to 食事券って無茶違和感がある。コロナ対策で、わんさかと金をばら撒いているけど、それって原資が税金だよな。政府が貸してくれる借金だ。借金はいつか返さないといけない。それとも、居直って倒産するか。頑張って借金返しましょ。 3倍返しだな。一番簡単なのは、消費税30%とかにしちゃう事。一度上げた税率は、天地がひっくり返らない限り、元には戻らない。誰もが薄々気付いているだろうけど、言葉にすると実現しちゃいそう。 何たって、日本は言霊の国だからね。。。

オリンピックの胴元がやって来るそうだけど、何しに来る? 表面上は、対策の視察とか言ってるけど、中止の打診だろう。まあ、オリンピックは、一部の連中の集金システムだから、庶民には関係ねぇと、傍観しましょかね。米国の、4年に一度の祭りもフェードアウトの雰囲気だしね。

ああ、無我の境地にはなれないなあ。あのスティーブ・ジョブズが、禅僧に師事して、無に至りたいって気持ちが分かるよ。等々。。。。。

そのうちに、最近やってるprolog資料の事も浮かんできた。ループを実現するには、再帰しかありません。まあ、for相当のターゲットを作ってしまえばいいんだろうけどね。

ピタゴラスの三角形を求めるのを、どう実現したら良い? 脳内シュミレーションを続けているうちに、再帰が止まらなくなったぞ。いつの間に、再帰か夢か現実かのうつつな気分で、寝入ってしまった。

残念ながら、アルキメデスのように、わかったぞと、フルチンで風呂を飛び出す所業にはならなかった。凡人で良かったわい。

帰りには、新蕎麦を頂いた。佳き秋の一日でしたよ。

install command

前回出て来たinstallコマンド。そのオプションを見る限りではshell scriptで実現出来そうなのに、バイナリーファイルになってた(C語でゴリゴリ書いた奴)。何でかな? ソース読んだら、その秘密に迫れるかな? こういうのもOpenBSDの楽しみの一つ。

リナでは敷居が高いからね。apt source installとかすればいい話ではありますが。と思ったら違った。installが何処のパッケージに所属してるねん? それを見つけ出してから、apt sourceしなきゃいけない。

実際にやってみたら、コマンド詰め合わせセット状態だった。

sakae@pen:/tmp/z/coreutils-8.30/man$ ls *.1|wc
    107     107     840

busyboxでも作れるかな? そんな事より、install.cだけ(改造して)コンパイル出来るかな?

sakae@pen:/tmp/z/coreutils-8.30/src$ gcc install.c
install.c:19:10: fatal error: config.h: No such file or directory
 #include <config.h>
          ^~~~~~~~~~
compilation terminated.

ちゃんと正規な手順(configure)を踏まないと、コンパイル出来ない。面倒なこったい!

で、OpenBSDのそれ、オーナーとかグループを厳しく査定しているなあ。一番大変なのは、安全なコピーを実現する為にやっている事。これはもう、絶対にshell scriptでは実現出来ない。

OpenBSDを構成してるソース一式、kernelソース、パッケージを作るためのmakefile類一式を、インストール時に入れておけば、思い立ったら何時でも参照出来る(たった3個のtar玉を取って来て、展開するだけ)。OSSなものは、ソースが見られて、改変出来てなんぼのもの。ただアプリを使うだけじゃ、OSSの魅力半減、いや使ってるとは認められません。ああ、個人の感想ですんで、押し付ける気はありませんです。

ピタゴラ三角

キャッチャーな短縮見出し。流行りですから。

yhoo知恵袋に質問してた人がいたので、答えをぱくってきた。それじゃあんまりなんで、斜辺のスキャンを奇数だけにした。どうしてかは、ウィキペディアを参照。

オイラーが初めてコンピュータに触れた時、宿題に出たやつだ。勿論言語はBASICね。

#include <stdio.h>

int main (void) {
  int a, b, c;

  for (c = 1; c < 100; c += 2)
    for (b = 1; b < c; b++)
      for (a = 1; a < b; a++)
        if (a * a + b * b == c * c)
          printf ("(%2d, %2d, %2d)\n", a, b, c);
}

実行結果を上げておく。

( 3,  4,  5)
( 5, 12, 13)
( 9, 12, 15)
( 8, 15, 17)
(15, 20, 25)
( 7, 24, 25)
(20, 21, 29)
 :
(35, 84, 91)
(57, 76, 95)
(65, 72, 97)

いきがかり上、これをprologでやってみる。いきなり3重ループはきついので、問題を小さくする為、斜辺Cを与えて、その中で、ピタゴラ三角が成立する組み合わせを求める事にした。

p(A,B,C) :- A^2 + B^2 =:= C^2, A < B,
            write(A), write(', '), write(B), write(', '), write(C), nl, fail.
p(A,B,C) :- X is A - 1, X > 0, p(X,B,C).
p(A,B,C) :- Y is B - 1, Y > 0, p(A,Y,C).

findp(C) :- p(C,C,C).

ドライバーと言うか駆動は、見ての通りfindpとした。findピタゴラの略と取ってもいいし、pをlispでよく使われる、述語のpと思っても構わない(schemeなら、find? ってなるけど、見つかった? で、こちらの方がより意味を明確に表しているな)。

露天風呂で考えていた再帰ね。ループさせたい時は、自分自身を呼び出せばよい。再帰の終了は? そりゃ、全部を調べ尽くした時。だから、一番最初の述語で、ピタゴラ三角が成立しても、わざとfailさせて、次の組み合わせを調べるようにした。

?- findp(5).
3, 4, 5
3, 4, 5
3, 4, 5
false.

何故か、同じ組み合わせが3つ出て来た。なんで? 考えても分からないので、swiplのトレースのご厄介になる事にした。

?- trace.
true.

[trace]  ?- findp(5).
   Call: (8) findp(5) ? creep
   Call: (9) p(5, 5, 5) ? creep
   Call: (10) 5^2+5^2=:=5^2 ? creep
   Fail: (10) 5^2+5^2=:=5^2 ? creep
   Redo: (9) p(5, 5, 5) ? creep
   Call: (10) _1972 is 5+ -1 ? creep
   Exit: (10) 4 is 5+ -1 ? creep
   Call: (10) 4>0 ? creep
   Exit: (10) 4>0 ? creep
   Call: (10) p(4, 5, 5) ? creep
   Call: (11) 4^2+5^2=:=5^2 ? creep
   Fail: (11) 4^2+5^2=:=5^2 ? creep
   Redo: (10) p(4, 5, 5) ?       %% press h
Options:
+:                  spy        -:              no spy
/c|e|r|f|u|a goal:  find       .:              repeat find
a:                  abort      A:              alternatives
b:                  break      c (ret, space): creep
[depth] d:          depth      e:              exit
f:                  fail       [ndepth] g:     goals (backtrace)
h (?):              help       i:              ignore
l:                  leap       L:              listing
n:                  no debug   p:              print
r:                  retry      s:              skip
u:                  up         w:              write
m:                  exception details
C:                  toggle show context
   Redo: (10) p(4, 5, 5) ?

何か、日が暮れそうな雰囲気だ(最近は、日暮れの時間が早いですからね)。

p(A,B,C) :- write('.'), X is A - 1, X > 0, p(X,B,C).
p(A,B,C) :- write('-'), Y is B - 1, Y > 0, p(A,Y,C).

通過したら報告するようにした(正にローテクな方法ですな)。

?- findp(5).
.....-.-.-.-.--..-.-.-.--..-.-.--..-.--..---3, 4, 5
...-.-.-.--..-.-.--..-.--..---...-.-.--..-.--..---...-.--..---...----.3, 4, 5
...-.-.-.--..-.-.--..-.--..---...-.-.--..-.--..---...-.--..---...----....-.-.--..-.--..---...-.--..---...----....-.--..---...----....-----..3, 4, 5
...-.-.-.--..-.-.--..-.--..---...-.-.--..-.--..---...-.--..---...----....-.-.--..-.--..---...-.--..---...----....-.--..---...----....-----.....-.-.--..-.--..---...-.--..---...----....-.--..---...----....-----.....-.--..---...----....-----.....-----
false.

節のコールグラフか? いや、ヘボな通信士が、電鍵を叩いたトン・ツー信号みたいだな。これじゃ、語の区切りはおろか、字の区切りも無いじゃん。まて、これを適当に区切れば、ピタゴラ三角のモールス信号になるぞ。暇ならやって聞け。

?- findp(1).
.-
false.

?- findp(2).
..-.--..--
false.

問題を小さくした。これで、脳内トレース出来るだろう。無理無理。今度はgprologのトレースでも使ってみるかな。

| ?- trace.
The debugger will first creep -- showing everything (trace)

yes
{trace}
| ?- findp(2).
      1    1  Call: findp(2) ?
      2    2  Call: p(2,2,2) ?
      3    3  Call: 2^2+2^2=:=2^2 ?
      3    3  Fail: 2^2+2^2=:=2^2 ?
      3    3  Call: _113 is 2-1 ?
      3    3  Exit: 1 is 2-1 ?
      4    3  Call: 1>0 ?
      4    3  Exit: 1>0 ?
      5    3  Call: p(1,2,2) ?
      6    4  Call: 1^2+2^2=:=2^2 ?
      6    4  Fail: 1^2+2^2=:=2^2 ?
      6    4  Call: _191 is 1-1 ?
      6    4  Exit: 0 is 1-1 ?
      7    4  Call: 0>0 ?
      7    4  Fail: 0>0 ?
      6    4  Call: _191 is 2-1 ?
      6    4  Exit: 1 is 2-1 ?
      7    4  Call: 1>0 ?
      7    4  Exit: 1>0 ?
      8    4  Call: p(1,1,2) ? h
Debugging commands:

RET/c creep        l  leap
   s  skip         G  goto
   r  retry        f  fail
   w  write        d  display
   p  print        e  exception
   g  ancestors    A  alternatives
   u  unify        .  father file
   n  nodebug      =  debugging
   +  spy this     *  spy conditionally
   -  nospy this   L  listing
   a  abort        b  break
   @  command      <  set printdepth
  h/? help         W  WAM debugger

      8    4  Call: p(1,1,2) ?

ちゃんと、使いこなしていないな。もう少し、熟成もとえ熟考しよう(また夢に出てきたりして)。

from exmple/tests

代わりに、nprologの参考資料を見る事にする。 作者さんが、例題と試験用のコードを惜しげもなく公開しているからね。そこらのaptとかで入れた奴は、往々にして省略されてる事が多いので、これはありがたい。勉強材料にうってつけ。

examples/fizzbuzz.pl

?- test(10).
buzz11fizz1314fizz1617fizz19yes
?- test(11).
11fizz1314fizz1617fizz19yes
?- test(20).
yes
?- test(21).
fizz2223fizzbuzz26fizz2829fizz3132f ... 17fizz9019buzzResource error

暴走理由とかを考えるのも、これまた楽し。Prolog Language これも自習書の一つだなあ。

tests/init.pl

main :-
    write(test_hello),
    nl.

:- main.

コメントが付いていたけど、省略した。いや、コメントに惹かれて実験したのだけどね。

debian:tests$ npl -c init.pl
N-Prolog Ver 1.43
test_hello
?-

やはり、mainは特別扱いなのかな。いや、そんな事は無いはずだ、C語と違いますって、きっぱり言明するだろうね。プチ気になるのが、mainの呼び出しがメダカに続いている事。特殊な用法なのかな。

確かに、起動時に(読み込み)実行してる。これなら、nplの起動・実行・終了までに要した時間を、外部から測定できるはず。

:- main, halt.

実行して、直ぐに終了せいに変更。これが出来れば、(コンパイルして)超難読化したコードを実行させるアプリが可能になるな。

そうそう、最近出た、『ネット興亡記』なんて本を読んだんよ。日本のインターネットを発達させた人達の物語。IIJの創始者とか、ホリエモンとか、mixiとか、LINEとか、メリカリとかね。 オイラーが以前お世話になってたyahoo運用のgeocitiesの話なんかも出て来る。

勿論、楽天の三木谷君の話も出て来てた(偉そうに、君を付けていいのか? せめて氏ぐらいにしろよ。それが大人のたしなみってもんだ(お前、それでも日本人か!用法用量は正確に))。簡単にカスタマイズしたHPを作れるアプリが欲しい。ポール・グレアム氏のアプリがぴったり。米国へ交渉に行った。

彼のアプリは、何やらカッコだらけの不思議な言語で書かれている。おいそれと真似が出来ない。それが、彼の武器。強気な彼は、申し出を断ってしまう。

みんな知ってるだろう。彼のエッセイ『ハッカーと画家』って本を。彼はコンピュータと絵の両方をやってた。画家になりたくて、絵を売る算段を考えた。そうだ、絵を売るためのサイトを作ろう。それで、CLISPを使ってごりごりコードを書いた。そのアプリで70社ほど契約できた。

三木谷氏の申し出は断ったけど、後日、そのアプリをYAHOOに売却したそうな(yahoo store)。そして彼は、それらの経験を生かして、Yコンピネータと言う、スタートアップ企業に投資する会社を作った。 Yコンビネータって、実に意味深な名前だな。彼の気概が良く表れていると思うぞ。

なるほどね。世間一般から無視されてるような言語を使え。そして自己防衛しろ。今のprologはぴったりじゃないですか。

debian:tests$ npl -c init.pl
N-Prolog Ver 1.43
test_hello
- good bye -
Segmentation fault

ありゃ、SEGVのおまけが付いてきたぞ。timeを使って、時間計測すると、0.6秒だった。リナはデフォでは、げろを記録しないけど、OpenBSDは、後々のためにちゃんと証拠を採取するから、もっと時間がかかるな。

このSEGVは、debian(32Bit)機で確認したんだけど、 OpenBSD(32Bit)でも再現。386Mと言う膨大なゲロなんで、RAM-DISKに吐き出すと言っても、4秒かかったぞ。nplを控え目に作っても、これだけの図体になってる。そのほとんどはBSSだな。

勿論、repl上から init.pl を実行する分には、SEGVはしないけど、それでは意味がないな。我ながら、変な用法を思い付いたものだ。

vbox$ ./npl
N-Prolog Ver 1.2
?- compile_file('init.pl').
pass1
test_hello
- good bye -
vbox$

更に、これも困った使い方だ。

Go to 0番地は地獄へと続く道。SEGVが口を開けて待ってるぞ。後は作者様に回避を懇願するだけです。

cc vs. gcc for gdb

nprologのgdbによる観光をチマチマとやってる。source中に出て来るマクロの定義がどうだったかなとプチ確認したい事がある。まあ、npl.hを見れば済む話ですが。。面倒、gdb上で確認したい。昔やったのを手繰って、こんな設定で再コンパイル。

CFLAGS = $(INCS) -Wall -g3 -O0 -gdwarf-2
(gdb) info macro GET_CAR
The symbol `GET_CAR' has no definition as a C/C++ preprocessor macro
at <user-defined>:-1

んが、駄目じゃん。これはきっとccがgdb用のinfoを作成してくれないからだろうと見当をつけた。使うコンパイラーをgccに変更したよ。

(gdb) info macro GET_CAR
Defined at /tmp/mynp-1.2/npl.h:215
  included at /tmp/mynp-1.2/main.c:9
#define GET_CAR(addr) heap[addr].val.car.intnum

そしたら、ちゃんと使えた。

lldbは、/usr/ports/devel/llvmにあるツールチェーンの一部になってるけどemacsでサポートしてるのかな? realgud-lldb これか。GDB to LLDB command map を見ても、オイラーみたいな贅沢を言う人は居ないみたいだな。当面、リナ系と共通に使えるgccで我慢するか。

?- 1^2 + 2^2 =:= 3^2.

numeqpで確認してるみたい。そこに到達した時、最終的に GET_INT を呼び出している。

(gdb) p x
$1 = 1073741829
(gdb) p y
$2 = 1073741833
(gdb) info macro GET_INT
Defined at /usr/include/sys/cdefs.h:207
  included at /home/sakae/src/mynp-1.2/compute.c:9
#define GET_INT(addr) get_int(addr)

マクロ変換されてるんで、先回りしてBPを設定

  int get_int(int addr){
B =>  if(addr >= 0)
          return(INT_MASK & addr);
      else
          return(addr);
  }
(gdb) info macro INT_MASK
Defined at /usr/include/sys/cdefs.h:59
  included at /home/sakae/src/mynp-1.2/compute.c:9
#define INT_MASK 1073741823
(gdb) p (INT_MASK & addr)
$3 = 5

マスク値が不思議な値ってのを確認しつつ、先回りして計算させてみた。

(gdb) c
Continuing.

Breakpoint 2, get_int (addr=1073741833) at compute.c:15
15          if(addr >= 0)
(gdb) p (INT_MASK & addr)
$4 = 9

快適に、納得が行くgdbライフを楽しめるな。

なお、今回は使う場面が無かったけれど、マクロを拡張させる事も出来る。

(gdb) macro expand min(12, 44)
expands to: ((12) < (44) ? (12) : (44))

これをgdb君にevalってもらうと

(gdb) p ((12) < (44) ? (12) : (44))
$1 = 12

便利な技である。マクロがどう展開されるかなんてのも、gdbで簡単に確認出来るよ。

(gdb) macro expand FILE_SET_MATURE(fp,p)
expands to: do { (fp)->f_iflags &= ~0x02; (--(fp)->f_count == 0 ? fdrop(fp, p) : 0); } while (0)

まあ、gcc -E xx.c とかやってもいいんだけど、お目当てな部分を探すのが大変なのよね。

etc