stack overflow .. nprolog

前回、prologの本質（の半分ぐらい）を、自己説明してみた。こうして書き出す事は良い事。 理解が整理出来るしね。Bugに悩んだら、部屋に飾ってあるティディイベアに説明するのが良いとされている。オイラーもこの方法に何度となく助けられたよ。

prologの実行状態を、疑似schemeで説明したんで、それが本当に成り立つか、例のピタゴラを求めるcodeをschemeに翻訳してみる。使ったschemeはguileだ。だって、手厚いemacsの支援(geiser-mode)が有りますから。

;; for guile
(use-modules (ice-9 format))

(define (pp a b c)
  (or
   (and (eqv? (+ (* a a) (* b b)) (* c c))
        (format #t "~d, ~d, ~d~%" a b c))
   #t))

(define (pa a b c)
  (if (eqv? a b)
      #t
      (and (pp a b c) (pa (+ a 1) b c))))

(define (pb a b c)
  (if (eqv? b c)
      #t
      (and (pa a b c) (pb 1 (+ b 1) c))))

(define (pc a b c cM)
  (if (> c cM)
      #t
      (and (pb 1 1 c) (pc 1 1 (+ c 1) cM))))

(define (run cM) (pc 1 1 1 cM))

andとかを積極的に使って、prologに似せてみた。 一番似てるのはppって関数だろう。数値比較のeqv?が真なら、結果を出力して関数を抜ける。 何故ならorの最初の式andが真だから。andが満足されない場合は、#tに来るけど、これは必ず真だから、pp全体としては、必ず真となる。

paとかの関数のelseの所にもandを使ってみた。普通ならbeginとかを使うんだけどね。ppが必ず真を返すので、paの戻り値は真が保障されている。

手軽にandが使えるのは、ｔしか扱っていないから。ｔ大好き。lispだとnil以外は全てｔ扱い。C語も0以外はみんなtrueってんで、lispに似ている。schemeは、論理値には #t/#f しか許さない。lispの佳き伝統を壊したと異議を唱えていた人が居たな。通称、黒板の人。懐かしい話だ。(Gauche Night)

昔のlisperは真の事をｔと言っていた。で、飛行機に乗った時、スッチィーの機内サービスを受けた。右手にコーヒーポット、左手にティーポットを持ってlisperの所にやって来た。右手のコーヒーポット付き出して、coffee ?。lisperはコーヒーを飲みたかったので、yesの代わりに思わずｔと言ってしまったとか。かくして、茶がカップに注がれたとさ。語り尽くされた小噺である。

これぐらいの書き換えなら、ググルあたりが持ってるAIでも楽勝だろう。いよいよプログラミング分野にもAIが進出して、プログラマーは失職しますよ。

創造性ってかアイデアを持ってる人しか、生きていけない時代になりつつある。と、ここまで書いてきて、schemeの再帰の書き方に毒されている事に気付いた。

(define (pa a b c)
  (or (eqv? a b)
      (and (pp a b c) (pa (+ a 1) b c))))

この方がprologの考え方に沿っているな。節が幸い２つだったんで、ifを使って容易に書き表せけど、それ以上になると大変。だったらcondを思い出せってのがあるけど、それはコンドね（寒い親父ギャグだ）。

sakae@pen:/tmp$ guile
GNU Guile 2.2.4
 :
scheme@(guile-user)> (load "p.scm")
;;; note: auto-compilation is enabled, set GUILE_AUTO_COMPILE=0
;;;       or pass the --no-auto-compile argument to disable.
;;; compiling /tmp/p.scm
;;; compiled /home/sakae/.cache/guile/ccache/2.2-LE-8-3.A/tmp/p.scm.go
scheme@(guile-user)> (run 20)
3, 4, 5
6, 8, 10
5, 12, 13
9, 12, 15
8, 15, 17
12, 16, 20
$1 = #t
scheme@(guile-user)> (run 100)
 :
57, 76, 95
65, 72, 97
60, 80, 100
28, 96, 100
$2 = #t

(run 1000)ぐらいでも、へこたれないで普通に探索してる。

前回のOpenBSDでのCore発生。夢枕に神だか仏様が立ち、stack-overflowを調べよと告げられた。あれだなと、記憶が飛ばないうちに調べてみたよ。

sakae@pen:/tmp$ ulimit -s
8192

リナでは、スタックサイズに8192Kbyteを割り当てている。

ob$ ulimit -s 
4096

一方、OpenBSDでは、32Bitでも64Bitのシステムでも、4096Kbyteしか割り当てていない。

prologでは、バックトラックに備えて、大量にstackを消費する（関数の相互呼び出しで実現）。よって、ハードウェアのスタックがみるみるうちに消費されて、OpenBSDでは、先にstack-overflowになる。

リナの方では、スタックには余裕が有るものの、呼び出し回数の制限をnprolog内部で行っていて、そのリミットに達した為、リソースエラーになったとの事。

この際だから、スタックオーバーフローを起こすコードを書いてみた。

#include <stdio.h>

void use(int n){
  int dmy[256 * 1024];

  printf("run: %d adr: %p\n", n, &dmy);
  use( n + 1);
}

int main(){
  int n = 0;
  use(n);
}

歯止めが無い、再帰関数呼び出し。しかも呼び出す度に、256Kのint配列をスタックに確保してくやつ。確保した配列の先頭アドレスを表示するようにしてる。

vbox$ ./a.out
run: 0 adr: 0xcf6d7750
run: 1 adr: 0xcf5d7724
run: 2 adr: 0xcf4d76f8
Segmentation fault (core dumped)

呼び出される度に、配列のアドレスが低い方に配置されていっている。このアドレス差が、ほぼ 配列のサイズになるはずなんで、確認してみる。

vbox$ gdb -q
(gdb) p(0xcf6d7750 - 0xcf5d7724)
$1 = 1048620
(gdb) p/x $1
$2 = 0x10002c

16進の引き算。何も指定しないと、10進数で回答してくる。p/x すれば、16進で表示してくれる。

Coreが出来ていたので、一応検視。

(gdb) bt
#0  0x1746160b in use (n=3) at ck.c:3
#1  0x1746166e in use (n=2) at ck.c:7
#2  0x1746166e in use (n=1) at ck.c:7
#3  0x1746166e in use (n=0) at ck.c:7
#4  0x174616db in main () at ck.c:12
(gdb) info registers
eax            0x17     23
ecx            0x3      3
edx            0x1      1
ebx            0x374600a8       927334568
esp            0xcf3d76b4       0xcf3d76b4
ebp            0xcf4d76d8       0xcf4d76d8
esi            0x2      2
edi            0x1      1
eip            0x1746160b       0x1746160b <use+11>
:

かわゆいよ、i386な石。

当然、32BitのOSと64BitのOSでは挙動が違う。顕著に差が出るのは、上記のチェックプログラムの所の配列確保をintからlong intにすれば確認出来る。

事実、nprologでも、32Bit版と64Bit版で、スタック使用の耐性が異なってくる。こういうのを楽しむのは、仮想マシンを複数作っておくに限る。各種OSも色々入れらるしね。

オイラーは、リアルマシンとしてWindows10(64Bit)と、Windows7の糞に嫌気が指してdebian(32bit)にしちゃったやつの2台だ。

仮想マシンは、Windows10の方に複数作っている。仮想化ソフトも、VertualBoxとVMware playerを入れている。どちらかが使えなくなっても(供給元の都合で)、継続出来るように、保険をかけている、とも言える。詳しい構成は、オイラーのHPのTopに張り付けてある。 金もかからず、場所も取らずに楽しめるよ。

現在の悩みは、今日は何を起動しようか、ぐらいだな。debin(32Bit)は、昔ながらのHDDを積んでいる。余り長時間通電しないと、HDDのヘッドが円盤に固着しちゃうんで、最低でも、週に一度ぐらいは、皿回ししたい。その点、Windows10はSSDだから心配ないけどね。

とすると、使うOSは、単純にラウンドロビンでいいかなとも思うんだけど、ふとした拍子にこれが乱れる事があるんだ。これを書いてる今、次に起動するのはFreeBSDだなと、run-listの先頭に指定されたよ。何故か？　FreeBSDってデフォで、lldb入っているのかなあ？　OpenBSDは、オプションでportsから入れないといかん、ってな具合。

仮にlldbが入っていると、nice値が変更されて、優先度が俄然にUpする。こんな具合になっちゃうんで、prologが得意とする（らしい）スケジューリングの最適化でも調べてみたい。何たって、７つの世界本で、prologユーザーに、使い方をインタビューしてた。

ハワイでイルカの研究をやってる所。10人ぐらいのチームを組んでやるらしいけど、個々人のスキルがそれぞれ違う。だから必要な技量を集めなければ実験出来ない。その組み合わせが膨大になりすぎて、人の頭では解決不能。それでprologに依頼してるそうだ。

Prolog : Programming for Artificial こんな本を勧められたけど、手に入るの？　希少本ばかりで、売りたい放題になってるからなあ。

PrologからJavaへのトランスレータ処理系とその 応用　こうう資料も引っかかってきた。これなら、無料で読めるな。

ひょっとして、スケジューリングって、積み木の世界 で、どう動かせばいいかっての？

忘れないうちに、lldbを内蔵してるか、確認。

[sakae@fb /tmp]$ lldb --version
lldb version 10.0.1 (git@github.com:llvm/llvm-project.git revision llvmorg-10.0.1-0-gef32c611aa2)
  clang revision llvmorg-10.0.1-0-gef32c611aa2
  llvm revision llvmorg-10.0.1-0-gef32c611aa2

これはもう、lldbを覚えるチャンスだな。何せ目の前に有るんですから。

と同時に、上でやったスタックリミットもチェックしておくか。

stack size              (kbytes, -s) 524288

もう、夢のような広大さです。気分を良くしたんで、早速手製のコア作成プログラムを走らせてみます。

   :
run: 507 adr: 0x7fffe03f8be0
run: 508 adr: 0x7fffe02f8bb0
run: 509 adr: 0x7fffe01f8b80
run: 510 adr: 0x7fffe00f8b50
Segmentation fault (core dumped)

確かに、気が遠くなるようだ。

[sakae@fb /tmp]$ lldb a.out a.out.core
(lldb) target create "a.out.core"
Current executable set to '/tmp/a.out.core' (x86_64).
(lldb) bt
error: invalid process

Coreの分析方法分からずなんで、普通の使い方を試してみる。

[sakae@fb /tmp]$ lldb a.out
(lldb) target create "a.out"
Current executable set to '/tmp/a.out' (x86_64).
(lldb) b use
Breakpoint 1: where = a.out`use + 14 at ck.c:6:31, address = 0x000000000020194e
(lldb) r
Process 6579 launching
Process 6579 launched: '/tmp/a.out' (x86_64)
Process 6579 stopped
 * thread #1, name = 'a.out', stop reason = breakpoint 1.1
    frame #0: 0x000000000020194e a.out`use(n=0) at ck.c:6:31
   3    void use(int n){
   4      int dmy[256 * 1024];
   5
-> 6      printf("run: %d adr: %p\n", n, &dmy);
   7      use( n + 1);
   8    }
   9
(lldb) c
  :
(lldb) bt
 * thread #1, name = 'a.out', stop reason = breakpoint 1.1
  * frame #0: 0x000000000020194e a.out`use(n=3) at ck.c:6:31
    frame #1: 0x000000000020197c a.out`use(n=2) at ck.c:7:3
    frame #2: 0x000000000020197c a.out`use(n=1) at ck.c:7:3
    frame #3: 0x000000000020197c a.out`use(n=0) at ck.c:7:3
    frame #4: 0x00000000002019a7 a.out`main at ck.c:12:3
    frame #5: 0x0000000000201750 a.out`_start(ap=<unavailable>, cleanup=<unavailable>) at crt1.c:76:7

走り出さないと、バックトレースは出来ないのか（な）？ まあ、おいおい勉強していけばいいな。それにしても画面の文字に色がついて、にぎやかだ箏。

(lldb) c 10
error: The 'process continue' command does not take any arguments.
(lldb) help c
     Continue execution of all threads in the current process.

Syntax: c <cmd-options>

Command Options Usage:
  c [-i <unsigned-integer>]

       -i <unsigned-integer> ( --ignore-count <unsigned-integer> )
            Ignore <N> crossings of the breakpoint (if it exists) for the
            currently selected thread.

'c' is an abbreviation for 'process continue'

gdb風に10回回れは拒否された。今時のアプリなら、その場でhelpが当たり前のようにあるだろう。ビンゴでした。

(lldb) c -i 5
Process 6579 resuming
run: 16 adr: 0x7ffffeefe7e0
run: 17 adr: 0x7ffffedfe7b0
run: 18 adr: 0x7ffffecfe780
run: 19 adr: 0x7ffffebfe750
run: 20 adr: 0x7ffffeafe720
run: 21 adr: 0x7ffffe9fe6f0
Process 6579 stopped
 * thread #1, name = 'a.out', stop reason = breakpoint 1.1
    :

実際に確認。

FreeBSDのstackエリアは広い方が良い主張を受け入れて、nprologを試してみる。 main.c内にある、リミットカウンター値は、デフォの1000倍に設定。

[sakae@fb /tmp/nprolog]$ ./npl -c p.pl
N-Prolog Ver 1.46
?- run(100).
 :
13, 84, 85
60, 63, 87
Resource error wcons

今度は、workエリアのcons不足エラーで落ちてる。 スタックだけじゃなくて、ワークエリアも不足するのか。膨大な計算をしてるんだな。 どんな計算をしてるのだろう？

色々なOSが出て来た。主義主張が違って面白い。ってか、リナ一色じゃつまらないと思うぞ。 間口が広い方が、色々な知見が得られて有益な事が多い。最近の風潮をみてると、異種コラボとか言って、色々な業界人の交流や起業が有るようだ。

今回お勧めしたいのは、大きな数値の表し方。

上でちょっと出て来たCoreを作るC語の部分。

int dmy[256 * 1024];

サイズを指定するのに、わざわざ掛け算で表現してる。これを見れば、ああ、1000を1024と解釈したいバイナリアンと一発で分かる。じゃなくて、こちらはどうだ。

#define CELLSIZE    10000000
extern cell heap[CELLSIZE];

ぱっと見、幾つのエレメントか分からない。

数字を専門に扱う銀行屋は、カンマを３桁毎にいれるよね。また素人相手のATMでは、ご丁寧に、万と千のキーが用意されてる。３万円おろしたい時、３万で済む。300000なんて言う桁の間違いを防止してるんだ（ジジババも使うからね）。

C語でも３桁毎に区切ろうよ（漢のオイラーなら万区切りを望むけど）。残念ながら、C語の伝統でそんなのは無い。新種のjuliaとかなら、 30_000 なんてのを許してる。

苦肉の策として、OpenBSDの人達は、掛け算区切りで表す方法を思い付いた（あの頃若かったメインの開発者も、老眼鏡を手放せない年代に突入してますから）。

#define CELLSIZE    10 * 1000 * 1000

パッと見、10Mだなってすぐに分かる。どうせコンパイラーがα簡約してくれるから、見易い方が絶対お得です。

技術屋なら、E表現の方が分かり易い。

vbox$ cc ck.c
ck.c:4:11: error: size of array has non-integer type 'double'
  int dmy[1e6];
          ^~~
1 error generated.
vbox$ gcc ck.c
ck.c: In function 'use':
ck.c:4:7: error: size of array 'dmy' has non-integer type
   int dmy[1e6];
       ^~~

残念ながら、こういうのは、お目玉食らったよ。

---

This year's Index

Home

---