196
『左と右の科学』なんていう図解雑学本を読んだ。
何故に左と右が有るの？ それはね、上下っていう次元があるでしょ。それから前後っていう方向が あるでしょ。もう一つの次元が右左。人間が、３次元の世界に住んでる限り、方向を区別 する必要が有るからさ。
上下は重力のおかげではっきりしてる、前後もはっきりしてる、左右は？ 彼方にいる（かも知れない） 宇宙人にどうやって、左右の概念を伝えたらいいの？
これが、有名なオズマの問題と言うらしい。そんなの簡単。心臓が有る側が左さ。ブブー。 世の中には心臓が右にある人もいるそうだ。まして、宇宙人の心臓が左にある保障なんて これっぽっちも無い。
生物じゃなくて、物理法則だったら万全に左右が定義出来るんぢゃなかろうか。フレミングの右手だか左手だかの 法則で。電流の向きと力の向きと磁界の向きの関係だから、森羅万象、全宇宙でも通じるに 違いない。
でも、これは却下です。磁界の向きを決めているN極、S極の定義が、地球ローカルなんです。 よその天体で磁界の方向を定義する事は出来ません。（まあ、地球から磁石を運んで行けば 可能だけど、時間がかかってしょうがない）
で、万事窮須かと思ったら、CP対象性の破れとかで、左右を宇宙人に教えてあげる事が 出来るようになったとか。ビックス粒子とかの世界の話みたい。もう、よう分からんな。
で、情緒を変えて、右と左どちらが偉いんでしょう。そんなの同等よ。左右対称が美しいに 決まってるって、シンメトリーな文化が外国では崇められていた。日本は対称の崩れを 愛したんですなあ。（日本庭園対フランス式庭園とかね）
日本では昔、左が優位だったんだけど、中国文化の影響を受けて、右が優位になった。 だから、調子の悪い事を左前になるとか言うね。
外国でも右はRightって事で、正しい。逆に左はLeftって事で不吉な事、悪魔になぞらえられた。 この思想はキリスト圏だけかと思ったら、そうでもないみたい。モンゴルでは左を悪意、虚偽って 捉えているし、タイでは右をより大きいとか重要な方って意味に使ってる。
そう言えば、Haskellに左右が有ったな。
data Either a b = Left a | Right b
deriving (Eq, Ord, Read, Show)
either :: (a -> c) -> (b -> c) -> Either a b -> c
either l r (Left x) = l x
either l r (Right y) = r y
Maybe型の発展系。評価の過程で不都合な結果になった場合等、Maybeよりも親切にその理由を 述べる時に使われる。maybeはM$系のOSが大好きなやつ。either系はunix系OSでも使ってる 親切設計版と、覚えておけば間違いない。
期待の結果はRightで包まれて返り、不都合な結果はLeftで包まれて返ってくるのは、世間一般の 常識だけど、コード上はそんな区別は無い。若し君が悪魔君なら、Leftを重用しても一向に かまわないって事を覚えておこう。全てを反転させるなら、パリティが保存されているって 事だ。
上で、シンメトリーって話題が出てきたけど、文章上の対称性って言うと回文に思いが至る。 いわゆる『たけやぶ やけた』ってやつね。前から読んでも、後ろから読んでも同意になるやつ。 欧文系では、その字句構造から、余り流行らない。ならば、万国共通の数字ならどうか？
121 なんていう数字は、前から読んでも、後ろから読んでも同一になる。任意の数値に 演算を施して、数字の回文(数)は作れるか？ っていう、興味ある問題が紹介されてた。
たとえば、159を取り上げよう。この数値（10進数表現）の、反転を取ると、951．それを元数に 加えると1110が得られる。今度はそれを反転（すると0111）して、1110に加えると、1221に なる。これで回文数になった。文書より手順例の方が、分かり易いかな。
159+951=1110 1110+0111=1221 86+68=154 154+451=605 605+506=1111
任意の数値に対して、成り立つか？ 確認してみれ。
Kitten
マイナー言語 Advent Calendar 2013 なんてのを見ていたら、Kittenでスタックと戯れる なんてのに出合った。
The Kitten Programming Languageってのは、haskellさんで実装 されてるとか。作り方は簡単そう。
git clone git://github.com/evincarofautumn/kitten.git cd kitten make all
早速やって三日。ghcの入っているPCBSDで試したら、まず、cabalを入れろとな。悪い予感が するぞ。取り合えず、cabalを入れてからupdate。その後、makeしたんだけど、エラー。エラーの 対処が面倒そうなんで、とうとう最新式ghcが入りそうな万次郎に舞台を移す事にしました。
最後の最後、testでこけた。
Running 1 test suites... Test suite test: RUNNING... Test suite test: PASS Test suite logged to: dist/test/kitten-0.1-test.log 1 of 1 test suites (1 of 1 test cases) passed. which: no hlint in (/usr/local/bin:/usr/bin:/bin:/usr/local/sbin:/usr/sbin:/sbin:/usr/bin/vendor_perl:/usr/bin/core_perl) No HLint found.
hlintは有り難いものだそうなので入れておくかな。cabal install hlint で入るはず なんだけど、happyが古いとか言われて、コンパイルを中断。調べてみたら、.cabal/binの 下に入っていたけど、PATHが通っていなかった。面倒臭いなあ。
[sakae@manjaro kitten]$ ./kitten
Welcome to Kitten!
Type ':help' for help or ':quit' to quit.
>>> [1, 2, 3] {2 *} map
----
[2, 4, 6]
>>> def sayHello {"Hello!" print newline}
----
[2, 4, 6]
>>> say
say sayBools sayFloat sayInt sayHello
sayBool sayStrings sayFloats sayInts
>>> sayHello
Hello!
----
[2, 4, 6]
TABで、補完が効くのか。sayとかは何処に有るのかな？ 探してみたら、Prerude_IO.ktnに 入ってた。
// Prints a string followed by a newline. def say ([Char] ->): print newline
括弧の中がForthで言うスタック変化か。と、同時に型を示しているんだな。これは、良い考えだ脳。 Prelude_Stack.ktnを見ると、余り関数が定義されていないなあ。自分で定義しろってか
// Swaps two values. Useful for changing argument order when
// partially applying a function.
def swap (a b -> b a):
-> { a b }
b a
これが分かれば、後は何とかなるか。矢印括弧で、stackからpopしたやつに名前を付け、 後は、その名前を書くだけで、pushされるとな。実に分かり易い。
ああ、思い出したぞ。去年retroをやってたな。折角なんで、haskellに対抗してpureでretro してみるかな。 今のkittenはstripされてなくて8.3M。裸にひんむいたら4.9Mになったけど、pureで作ったら 如何程になるのだろうか？ こういう下らない事に興味を持って、開発するって、才能の 無駄使い？
retroの為の下調べ RAM編
pureでretroが動くんだろうか？ 今までの移植の経験から、難所は２つあるように思う。 一つは、retroVMの為のRAMをどう実現するか？ もう一つは、retroのstackをどう実現するかだ。
今まではRAMを配列で実現し、stackは書き換え可能なlistを可能にするため、refを使った。 Haskell寄りのpureで、両者を実現してると良いんだけど。。。
まず配列の方。脳内変換してArrayって事で調べてみると、
mkarray x n¶
create an array consisting of n x‘s
a ! i¶
return the ith member of a
update a i x¶
replace the ith member of a by x
つう事で、何の問題も無さそうに思えるんだけど、大問題な例が載ってた。
Updating a member of an array produces a new array: > let b::array = update a 1 2.0;
Arrayの更新にO(n)時間が必要という制限が有るんです。これじゃ、RAMじゃなくて、EEPROM だよ。RAMと言うからにゃ、O(1)で動く必要があります。
Haskellの専門家も種々のデータ構造のArrayの 説明の所で、同様の意見を述べていました。但し、HaskellでもData.Array.IOってモジュールを 使うと、更新もO(1)で済むよと。ITProでも、Cの配列をHaskellで利用する なんて項が立つぐらいだから、RAMの需要は必ず有るのよ。そして、あの人も、 Haskell ポインタープログラミングなんて 記事を書いている。それによると、peekとpokeの世界が有るようですよ。
半導体メーカーさんは、フラッシュ だけじゃなくて、RAMも安く供給して下さいね。決して、品不足で価格を吊り上げない事ですだ。 http://www.atmarkit.co.jp/ait/articles/1312/24/news051.html ああ、余計な事書いちゃったよ。
で、pureではどうする？ ヒントはCの配列って事かな？ pureはC語との親和性が非常に高い。 mallocなんてのが、pureから苦も無く呼べるようになっている。 後は、mallocで確保した先からデータを呼び出したり、書き込んだりが簡単に出来るかだな。 まあ、こういうのは、ポインターの世界って事で、説明が載ってた。
calloc nmembers size¶
malloc size¶
realloc ptr size¶
free ptr¶
Interface to malloc, free and friends. These let you allocate dynamic
buffers (represented as Pure pointer values) for various purposes.
NAME
malloc, free, calloc, realloc - allocate and free dynamic memory
SYNOPSIS
#include <stdlib.h>
void *malloc(size_t size);
void free(void *ptr);
void *calloc(size_t nmemb, size_t size);
void *realloc(void *ptr, size_t size);
上がpureの説明書で、下がmanからの抜粋。雅にそのままです。それより、そこへのアクセス はどうやるかだな。
The following functions perform direct memory accesses through pointers. Their
primary use is to interface to certain C library functions which take or return
data through pointers. It goes without saying that these operations should be
used with utmost care. No checking is done on the pointer types, so it is the
programmer’s responsibility to ensure that the pointers actually refer to the
corresponding type of data.
get_byte ptr¶
get_short ptr¶
get_int ptr¶
get_int64 ptr¶
get_long ptr¶
get_float ptr¶
get_double ptr¶
get_string ptr¶
get_pointer ptr¶
Return the integer, floating point, string or generic pointer value at the
memory location indicated by ptr.
汝の責任において使用を許可します。まあ、こちらはRAMからの読み出しなんで、へくったって 大した事は無い。
put_byte ptr x¶
put_short ptr x¶
put_int ptr x¶
put_int64 ptr x¶
put_long ptr x¶
put_float ptr x¶
put_double ptr x¶
put_string ptr x¶
put_pointer ptr x¶
Change the integer, floating point, string or generic pointer value at the
memory location indicated by ptr to the given value x.
こちらは、pure側からRAMへの書き込みだ。retroの場合は、intで使う事になるな。
ちょいと、実験してみる。
> using system, pointers; > let ram = malloc (1024*4); > ram; #<pointer 0x968d0d0> > get_int (ram+0*4); 1152059256 > get_int (ram+1*4); 1152059256 > put_int (ram+1*4) 12345; () > get_int (ram+1*4); 12345
1024個のintエリアを確保。mallocは、確保したエリアの先頭を返してくる。後は、それを 使ってアクセス。ポインターに足し算して、場所を決めてる。
疑り深いオイラーは、gdbを使って、書き換えられているか、一応確認。(4100 as pid of pure)
[sakae@fedora pure]$ gdb -q pure 4100 : (gdb) x/4w 0x968d0d0 0x968d0d0: 1152059256 12345 157864136 157864136
どうやら、良さそうなので、読み書きを関数にしとく。
using system, pointers; let base = malloc 1024*4 ; // 4 for int ramr i = get_int (base + i*4); ramw i x = put_int (base + i*4) x ;
我ながらベタな名前だな。なら、peek/pokeって名前にしとけば。。英和辞書で意味を 調べてみたら、品位に欠ける単語と判明したんで、採用を見送ったよ。
retroの為の下調べ Stack編
もう一つの難題。Stackの実現。smlとかには、refが有って、そのおかげで書き換えが容易 だった。果たしてpureに有るかな？ 日和ってるかって事。調べたら有った。まあ、Haskell にも有るぐらいだから、大人の事情なんでしょう。
ref x¶
Create a reference pointing to x initially.
put r x¶
Set a new value x, and return that value.
get r¶
Retrieve the current value r points to.
これだけ有れば、何とかなるかな。ちょっと実験してみる。
> let a = ref [] ; > put a (1:get a); [1] > put a (2:get a); [2,1] > head $ get a; 2 > get a; [2,1]
何とか成りそうだな。
回文数の作成
枕に出てきた問題。コードに落としておかないと、枕を高くして眠れないので、pure語で 書いてみた。
mil n = go n 0 with
go n c = if cp n
then (n,c)
else go (nx n) (c + 1) ;
cp n = (dr n) == (reverse $ dr n) ;
dr n = if bigintp n
then (init . str) n
else str n ;
dz n = dropwhile (=="0") (reverse $ dr n) ;
nx n = n + (val $ dz n) ;
end ;
pure語特有な事情が有ったので、それを回避するようにしてます。問題は２つあった。 まず一つは、数値を文字列に直した時、bigintの場合、123Lのように、数字列の最後にLが 付いてしまう事。L が邪魔なので削除してるのが、関数 dr の仕事さ。
もう一点は、反転した数字列の冒頭が０（zero)になってると、valで数値に戻す時、８進数と みなされてしまう事。それを避ける為、関数 dz を用意した。
> mil 121 ; 121,0 > mil 100 ; 101,1 > mil 159 ; 1221,2 > mil 86 ; 1111,3
一応、検算。タプルの右側の数値は、回文数を作るのに要したステップ数。大丈夫そうなので 少し遊んでみた。
> mil 97; 44044,6 > mil 257; 11011,3 > mil 998 ; 133697796331L,17 > mil 93821834 ; 123347743321L,7 > mil 196 ; :
196から回文数を作ろうと思ったら、永遠と計算を始めた。普段FreeBSDのswapなんて働かないのに 動き始めたぞ。VMwareに768Mのメモリーを分け与えているんだけど、Topで見てたらpureの プロセスmemory(RES)が570Mぐらいから、swapの利用が始まった。
後はswap-outの連続ですよ。どんどんメモリーを消費してくだけで、回収とかが働かない んだな。どんな具合になるか、モニタールーチンを埋め込んで、監視してみるか。
go n c = if cp n
then (n,c)
else ex n c $$ go (nx n) (c + 1) ;
:
ex n c = if c mod 100 == 0
then puts $ str c +" "+ str (# (dr n))
else 0 ;
以前に覚えた、progn相当を使って、go関数のelse区にプローブを差し込んだ。プローブの 内容は、100ステップ毎に、計算してる数値の桁数も表示するっていうもの。
pureの仮想メモリーを含めたサイズが1700Mぐらいから、スラッシングが激しくなり、計算に 進度が見られなくなった。ここまで、約30分のCPU酷使だったぞ。何処まで動いていたかと言うと
48700 20232 48800 20272 48900 20315 49000 20359 49100 20402 <stdin>, line 1: unhandled exception 'signal 15' while evaluating 'mil 196' > Killed: 9
2万桁は達成したか。一生懸命に業務に邁進してたのに、脇から刺されて、突然死させられた pure君に合掌。
kaizen 改善
30分で2万桁ってのは遅くねぇ？ こう、しゃちょさんから言われました。日本が誇るkaizenに 挑戦ですかね。改善のこつは、無理、無駄、むらの3M撲滅ですって、先輩に言われたなあ。
先に書いた奴は関数型って事で綺麗だったけど、何回も同じ計算をしてて無駄っぽい。(dr関数を 経由して何回もstrを呼ぶとか、reverseを呼ぶとか) こういうの一度計算したのをメモ化 しとけばいいんでないかい。
メモ化はfibの計算みたいに、何回も同じ引数で呼ばれる時に威力を発揮するけど、今回の 場合は、同じ引数で、せいぜい３回しか呼ばれないので、大層なしかけは必要なさそう。 せいぜい、みんな大好きキャッシュ（現金はみんな大好きだよね！）ぐらいでいいんでないかい。
キャッシュ化って言うけど、得られた値を変数に仕舞っておけばOK。そんなの変数でいいじゃん。 とはいえ、同一引数への複数回定義は禁止されている。 そこで、refの登場ですよ。引数と計算値のペアで記録するなら、普通はタプルを思いつくけど、 面倒なので、変数を２つ用意した。正統なキーとしては、引数のｎだろうけど、これ、bigintに なるんで、同値の判定に時間がかかりそう。そんな訳で、キーとしてはステップ数ｃを使う 事にした。
実行時間を計ってみると、、、(mi2がキャッシュ使用版)
mi2 10000 36.7266s, 12485 cells mil 10000 39.5234s, 12485 cells mi2 20000 174.18s, 24896 cells mil 20000 174.438s, 24896 cells mi2 49100 1843.38s, 61217 cells
あらら、全く効果が無かったぞ。何故に効果が無い。何故？何故を最低５回は繰り返して 本質に迫れって教えられたものだ。今回は何故って一回問うと、Cふらふら語を読めって 言われるので、それは避けたい。何処で時間を食い潰しているのだろう？
こんな場合はFBIで採用してる、プロファイリングですよ。でも、調べてみたら、ドイツには 普及してないみたい。だめじゃん。こいういう場合は職人の勘を働かせるしかないか。
> str 11111111111111111111111111111111111111111111111111111111111111111115; "11111111111111111111111111111111111111111111111111111111111111111115L" 0s, 2 cells > reverse ans; "L51111111111111111111111111111111111111111111111111111111111111111111" 0s, 210 cells
reverseって大量にメモリー消費するんだ。って事は、reverseを何回も実行させるのを 防げば効果が有りそう。
mi3 n = go n 0 with
go n c = if cp n || c == 49100
then (n,c)
else ex n c $$ go (nx n) (c + 1) ;
cp n = (dr n) == (rc n);
dr n = if bigintp n
then (init . str) n
else str n;
dz n = dropwhile (=="0") (rc n) ;
nx n = n + (val $ dz n);
ex n c = if c mod 100 == 0
then puts $ str c +" "+ str (# (dr n))
else 0 ;
rc n = if n == (get k)
then get v
else put k n $$ put v (reverse $ dr n) $$ get v;
end when
k = ref (-1) ;
v = ref "" ;
end;
面倒なので、キャッシュ用のキーはnにしました。
mi3 20000 118.156s, 24900 cells mi3 49100 1183.51s, 61219 cells
今までの実行時間のほぼ 2/3 になったぞ。報告してくるcells数は改善の前後で変わらない けど(これも何故何故フラグが建つべきですよ)、topでみてると(vmstatでもいいけど)明らかにswapの使用量が違う。 言語に閉じこもるんじゃなくて、大局的に見ないと駄目だな。
196
196の場合、果たして回文数になるか成らないかは不明らしい。なお、他にも5桁以下の種数から 回文数が発生出来るか、不明な数値として、 879, 978, 1997, 7059, 10553, 10563 (と、その鏡像)なのが有るらしい。 数学的な証明も、まだ無いそうだ。フェルマーの最終定理(x^n + y^n = z^n においてnが3以上の時 式を満たす自然数x,y,zは、存在しない)みたいに、魅力が無いのかしらん？ 暇な人がいたら、チャレンジ きぼんぬ。ちなみに、フェルマー問題は、提起されから360年 かかって、色々な人のチャレンジの末に、やっと証明された。
奇特な人向け参考書 回文数と196
そして、興味のお伴に 整数の類 ここから素数の項を辿ると、回文素数なんてのも有るのね。興味は尽きないなあ。
その前にウォーミングアップしたい方は、次の問題を解いてみてください。
６桁の回文数で、９５で割り切れ、 割った答えも回文数となるものを求めよ。
そして、オイラー向けには、 Jで196問題さ。
FreeBSD desktop on VMware
という事で、あの人が書いていた。ご参考までに 備忘録 - FreeBSD 10 あれこれ
mateって、Gnomeの保守派？ QT陣営と支持が２分してるんだよな。おいらは無党派だから 傍観するだけだけど。そのううちに、OS Xへ行こうと思う。
XPがサポ切れでウブへって記事も有ったぞ。 XPサポ切れ対策待ったなし、個人PCならぜひ脱Windowsを これも派閥拡大の一路線だな。
自分へのメモ: FreeBSD10からpure-modeを使うと、last-command-charなんてしらねって言われて入力出来ない 文字があった。ここを参考に、変更したよ。 みんな、こんなアホな問題に付き合わされていて無駄だなあ。