新しい XCTU での XBee ファームウェアの復元
卒研で ZigBee 通信デバイスの XBee ZB S2 を使っているのだが、設定ソフトの XCTU (http://www.digi.com/support/productdetail?pid=3430&type=utilities) を使ってファームウェアを更新するときに失敗してしまって、PC から見えなくなってしまった。検索すると古い XCTU でファームウェアを復元する方法は見つかるが、新しい XCTU v6.2.0 で行う方法は見つからなかったのでまとめてみる。
USB 接続アダプタを準備する
XCTU を使っている時点で大丈夫だとは思うが、USB 接続アダプタが必要となる。自分が使ったのは秋月電子通商の XBee USB インターフェースボードキット。
XCTU を使ってファームウェアを復元する
『Xbeeファームウェアが飛んじゃったら。その対処法 - zimudomuzidomuの日記』にあるように、XBee を USB 接続アダプタに接続せずに XCTU を起動した。ただし、新しくなった XCTU でも最初に未接続にする必要があるかどうかは不明である。
起動したら、下図赤丸の「Add devices」をクリックする。
いつもの「Add a radio module」画面が出る。アダプタが接続されているポートと通信の設定を確認して次へ進む。
しばらくデバイスを探すが、ファームウェアが死んでいるので反応しない。「Action required」画面が出たらあきらめて「Cancel」を押す。
キャンセルすると「Could not found any radio module」画面が出る。下図赤丸の「Recovery」を押す。
ファームウェア選択画面が出る。直前まで使っていたファームウェアを選択する。外してある XBee を手元に置いてから、「Recover」を押す。
「Recovering radio module」画面が出たら、素早く USB 接続アダプタに XBee を挿す。数十秒未接続だと、上記の「Action required」画面が出てしまうので注意。自分の使っていた XBee では、挿すとすぐにファームウェアの書き込みが始まった。
認識されることを確認し、再設定を行う
ファームウェアの書き込みが終わると自動的にモジュールの探索が行われる。正常に書き込まれたならば、初期状態に戻った XBee が一覧に現れる。
XBee が無事に現れたら、以前と同じ状態になるように設定しなおせばよい。
和歌山県の道路規制情報のリポジトリ
先月はドライブ日和な日が多かったので、静岡 r389（水窪→山住神社→春野）とか r263（春野→川根本町）といった険道で楽しんできた。ところで GitHub を眺めていると、交通関係で気になるリポジトリが。
https://github.com/wakayama-pref-org/information-of-road-traffic-regulation
和歌山県の道路規制情報のリポジトリ。オープンデータとしてCSVが出たのは初めてではないだろうか。
これに対して国土地理院の藤村英範さんが GeoJSON 化の pull request を投稿している。GitHub 上のプレビュー画面を見ると、地図上に情報が出ていて分かりやすい。
それなりの距離のドライブをするときには道路の交通規制情報は重要なのだけれど、自分が知る限り、日本では再利用可能なデータとしては一切公開されていない。集約して公開する権利は日本交通情報センター（JARTIC）が握っていて、一般の人がまとめることは非常に難しい。このような事情であるから、他の都道府県にもこの例のようにまずオープンデータとして公開する流れが広まってほしいと思っている。理想的には形式の統一まで進んでほしい。
2015-06-10 の日記
今日は午後から、マイコン（授業で使っている AKI-H8/3069F ボード）に RS-232C 接続のバーコードリーダー経由で情報を取り込む実験を行った。取り込んだ情報は最終的にモデルに流し込み、LCD に表示することとなる。インターフェース技術の授業で習ったとはいえ、実際に回路を組むのは初めてなので分からないことばかりだった。
# 機材を取りに校内を行ったり来たりしていたときになおやさん（@naoya_24）と出会った。校長先生も一緒だったけれど、どんなご用事だったのだろう。
最終目的がバーコードリーダーを使うことだとしても、それ以前にシリアル通信で情報を取り込めなければ話にならないので、まずはそこから。授業で、TeraTerm を起動しキーボードで打った 1 文字を読み込む実習は行ったが、文字を貯め込むのはやったことがなかった。ただループで回すと同じ文字が大量に入力されることになったので、同じ文字が打たれている間は無視するようにしなければならない。大まかな流れは以下の形。
/* * シリアル通信で文字を取り込む */ #include "reg3067.h" // シリアル通信関連のビット #define SSR_RDR_FULL 0x40 // SCI1 を使って 1 文字受信する unsigned char SCI1_getchar(void); int main(void) { unsigned char ch; // 読み込んだ文字 unsigned char last_ch = '\0'; // 最後に読み込んだ文字 // シリアル通信の設定 SMR1 = 0x00; BRR1 = 10; // 20 MHz, 57600 bps SCR1 = 0x30; // RE on, TE on while (1) { ch = SCI1_getchar(); if (ch != last_ch) { // 同じ文字が入力された際の初回のみ // 文字を貯め込んで LCD 等に表示する } last_ch = ch; } return 0; } unsigned char SCI1_getchar(void) { // SCI1 受信：キー入力待ち SSR1 = 0x00; while (!(SSR1 & SSR_RDR_FULL)); return RDR1; // 読み出し }
バーコードは形式によって桁数が異なるが、今回は 8 桁程度あれば大丈夫そうなので、簡単な 8 桁分のリングバッファに貯めることにした。メモリを動的に確保しなくても使える。
/* * 8 文字分のリングバッファ */ // 8 文字分のリングバッファの構造体 typedef struct ring_buffer8 { unsigned int length; // 貯めこまれている文字列の長さ unsigned int current_index; // 現在の位置 char chars[9]; // printf デバッグをしやすいように 1 つ大きくした } ring_buffer8_t; // リングバッファを初期化する void ring_buffer8_init(ring_buffer8_t* buffer) { unsigned int i; buffer->length = 0; buffer->current_index = 0; for (i = 0; i < 9; ++i) { buffer->chars[i] = '\0'; } } // リングバッファに 1 文字追加する void ring_buffer8_push(ring_buffer8_t* buffer, unsigned char ch) { buffer->chars[buffer->current_index] = ch; if (buffer->length < 8) { ++buffer->length; } buffer->current_index = (buffer->current_index + 1) % 8; } // リングバッファの内容を文字列として取り出す void ring_buffer8_to_string(ring_buffer8_t* buffer, char* dest) { unsigned int i; if (length < 8) { for (i = 0; i < buffer->length; ++i) { dest[i] = buffer->chars[i]; } } else { unsigned int j; // 折り返し前：現在の位置から最後まで for (i = 0, j = buffer->current_index; j < 8; ++i, ++j) { dest[i] = buffer->chars[j]; } // 折り返し後：最初から現在の位置の手前まで for (j = 0; j < buffer->current_index; ++i, ++j) { dest[i] = buffer->chars[j]; } } dest[buffer->length] = '\0'; }
ここまでやって TeraTerm 上でキーボードを打つことで情報を入力できるようになったが、今日はバーコードリーダーへの移行は完了しなかった。TeraTerm では通信設定さえ合わせれば、きちんとバーコードを読み取って数字が表示された。オシロスコープで見ると、バーコードリーダーで読み取った情報は RxD 端子（D-Sub 9 ピンコネクタ 2 番）から流れてくるようだった。マニュアルを見ると JP1 と SCI0 がつながっていて、また電圧レベル変換 IC の ADM3202AN にも接続されているので、コネクタと JP1 の対応する端子同士を線材＋はんだ付けで接続すれば良さそう。次回はそんな感じで進めたい。
すごい E 本・第 8 章の逆ポーランド記法計算機
「すごい Erlang ゆかいに学ぼう！」第 8 章の逆ポーランド記法（RPN）計算機を打ち込んでみた。パターンマッチのおかげで簡潔に書けるのが好み。こういう例は、今まで自分が使ってきた言語ではどうしても長くなってしまいそう。
演習問題
いくつか演習問題があったので考えてみた。
和
まずは和 sum。6 章でやったように fold が使える。スタックとして使っているリストへの数の追加の順番を考えると foldr が自然だけれど、foldl にしてみた。加算は可換だから同じ結果になり、またマニュアルを見ると foldl は末尾再帰だから、こちらの方が速そう。
rpn("sum", Stack) -> [lists:foldl(fun(N, Sum) -> Sum+N end, 0, Stack)];
積
積 prod も同様。ちょうどこの前書いた SICP の問題の解答にもあった。初期値（単位元）が 1 であることに注意。
rpn("prod", Stack) -> [lists:foldl(fun(N, Prod) -> Prod*N end, 1, Stack)];
badarith エラーを上げるようにする
pp. 100—101 の「NOTE」に書いてあること。よく分からない演算子やスタックに値が残ってクラッシュするときに、badarith エラーを上げるようにする。
まずはスタックに余分な値が残っているとき。rpn/1 を修正する。
rpn(L) when is_list(L) -> case lists:foldl(fun rpn/2, [], string:tokens(L, " ")) of [Res] -> Res; _ -> erlang:error(badarith) % 追加 end.
続いて、よく分からない演算子が見つかったとき。read/1 の list_to_integer に失敗することを利用すると、この場合を検出することができた。
read(N) -> case string:to_float(N) of {error,no_float} -> %% ここから追加 try list_to_integer(N) catch error:badarg -> erlang:error(badarith) end; %% 追加ここまで {F,_} -> F end.
さらに演算子を追加する例
例えば階乗を追加してみたらどうか、と思ってやってみた。
rpn("fact", [N|S]) -> [factorial(N)|S];
log10 等と同様にスタックから取り出す数は 1 つ。長くなるので factorial は別に書いた。
%% 階乗関数 factorial(N) -> factorial(N, 1). factorial(0, Acc) -> Acc; factorial(N, Acc) when N > 0 -> factorial(N-1, N*Acc).
実行例。
14> calc:rpn("0 fact").
1
15> calc:rpn("3 fact").
6
16> calc:rpn("7 fact").
5040
まとめ
本からいろいろと追加した分を含めた calc.erl を載せておく。
SICP: Exercise 1.36
問題 1.36
問題 1.22 で示した基本の
newlineとdisplayを使い、生成する近似値を順に印字するようfixed-pointを修正せよ。次に \( x \mapsto \log(1000)/\log(x) \) の不動点を探索することで、\( x^x = 1000 \) の解を見つけよ。（自然対数を計算する Scheme の基本log手続きを使う。）平均緩和を使った時と使わない時のステップ数を比べよ。（fixed-pointの予測値を 1 にして始めてはいけない。\( \log(1) = 0 \) による除算を惹き起すからだ。）
fixed-point の方は、printf デバッグのように display を追加するだけ。
(define tolerance 0.00001) (define (fixed-point f guess) (define (close-enough? v1 v2) (< (abs (- v1 v2)) tolerance)) (define (try guess) (let ((next (f guess))) (display "guess: ") (display guess) (display ", next: ") (display next) (newline) (if (close-enough? guess next) next (try next)))) (try guess))
平均緩和を行わない場合は
(define (f x) (/ (log 1000) (log x))) (define (solve-x^x=1000) (fixed-point f 2.0)) (solve-x^x=1000) ; guess: 2.0, next: 9.965784284662087 ; guess: 9.965784284662087, next: 3.004472209841214 ; guess: 3.004472209841214, next: 6.279195757507157 ; guess: 6.279195757507157, next: 3.759850702401539 ; guess: 3.759850702401539, next: 5.215843784925895 ; guess: 5.215843784925895, next: 4.182207192401397 ; guess: 4.182207192401397, next: 4.8277650983445906 ; guess: 4.8277650983445906, next: 4.387593384662677 ; guess: 4.387593384662677, next: 4.671250085763899 ; guess: 4.671250085763899, next: 4.481403616895052 ; guess: 4.481403616895052, next: 4.6053657460929 ; guess: 4.6053657460929, next: 4.5230849678718865 ; guess: 4.5230849678718865, next: 4.577114682047341 ; guess: 4.577114682047341, next: 4.541382480151454 ; guess: 4.541382480151454, next: 4.564903245230833 ; guess: 4.564903245230833, next: 4.549372679303342 ; guess: 4.549372679303342, next: 4.559606491913287 ; guess: 4.559606491913287, next: 4.552853875788271 ; guess: 4.552853875788271, next: 4.557305529748263 ; guess: 4.557305529748263, next: 4.554369064436181 ; guess: 4.554369064436181, next: 4.556305311532999 ; guess: 4.556305311532999, next: 4.555028263573554 ; guess: 4.555028263573554, next: 4.555870396702851 ; guess: 4.555870396702851, next: 4.555315001192079 ; guess: 4.555315001192079, next: 4.5556812635433275 ; guess: 4.5556812635433275, next: 4.555439715736846 ; guess: 4.555439715736846, next: 4.555599009998291 ; guess: 4.555599009998291, next: 4.555493957531389 ; guess: 4.555493957531389, next: 4.555563237292884 ; guess: 4.555563237292884, next: 4.555517548417651 ; guess: 4.555517548417651, next: 4.555547679306398 ; guess: 4.555547679306398, next: 4.555527808516254 ; guess: 4.555527808516254, next: 4.555540912917957 ; guess: 4.555540912917957, next: 4.555532270803653 4.555532270803653
となった。34 ステップ。
\( x \mapsto \log(1000)/\log(x) \) の不動点探索で平均緩和を行う場合は、本文にあるとおり両辺に \( x \) を足して 2 で割る。 $$ \frac{x + x}{2} = \frac{x + \log(1000)/\log(x)}{2} \quad \therefore\ x = \frac{x + \log(1000)/\log(x)}{2} $$
コードを書いて実行すると
(define (solve-x^x=1000-with-average-damping) (fixed-point (lambda (x) (average x (f x))) 2.0)) (solve-x^x=1000-with-average-damping) ; guess: 2.0, next: 5.9828921423310435 ; guess: 5.9828921423310435, next: 4.922168721308343 ; guess: 4.922168721308343, next: 4.628224318195455 ; guess: 4.628224318195455, next: 4.568346513136242 ; guess: 4.568346513136242, next: 4.5577305909237005 ; guess: 4.5577305909237005, next: 4.555909809045131 ; guess: 4.555909809045131, next: 4.555599411610624 ; guess: 4.555599411610624, next: 4.5555465521473675 ; guess: 4.5555465521473675, next: 4.555537551999825 4.555537551999825
となった。9 ステップと大幅にステップ数が縮まった。
SICP: Exercise 1.35
問題 1.35
（1.2.2 節の）黄金比 \( \phi \) が変換 \( x \mapsto 1 + \frac{1}{x} \) の不動点であることを示し、この事実を使い
fixed-point手続きにより \( \phi \) を計算せよ。
\( f(x) = x \) となる \( x \) を関数 \( f \) の不動点という。グラフを考えると、不動点において $$ \begin{cases} y = f(x) \\ y = x \end{cases} $$ と書けるから、これはグラフ \( y = f(x) \) と直線 \( y = x \) の交点である。また、 $$ f(x),\,f(f(x)),\,f(f(f(x))),\,\cdots $$ と \( f \) を繰り返し作用させていけば不動点 \( x_0 \) に収束していくとき、\( x_0 \) を吸引的不動点というらしい。
方程式の解の探索を不動点探索によって行える場合がある。方程式を変形して \( x = f(x) \) と書くことができ、\( f(x) \) が吸引的不動点を持つならば、不動点探索によって解 \( x \) を求めることができる。
さて、これを黄金比 \( \phi \) を求めるのに利用してみる。1.2.2 節より \( \phi^2 = \phi + 1 \) だったから、両辺を \( \phi \) で割って $$ \phi = 1 + \frac{1}{\phi} $$ したがって、\( f(x) = 1 + \frac{1}{x} \)、つまり \( x \mapsto 1 + \frac{1}{x} \) とおけば \( \phi \) はその不動点である。
実際に計算してみると
;; 不動点探索で求めた黄金比 (define golden-ratio-as-fixed-point (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)) 1.6180327868852458 ;; 正確な黄金比 (define accurate-golden-ratio (/ (+ 1 (sqrt 5)) 2.0)) 1.618033988749895 ;; 誤差 (- golden-ratio-as-fixed-point accurate-golden-ratio) -1.2018646491362972e-6
そこそこの精度で求められている。
黄金比に収束することの証明
詳しい話が Amaca, Edgar Gilbuena, "On rational functions with Golden Ratio as fixed point" (2008). Thesis. Rochester Institute of Technology. に載っていた。問題 1.13 とこの論文を参考にして、上記の関数を繰り返し作用させれば黄金比に収束することが理解できた。
本文の平方根の計算と同様に、上記の \( f \) を \( x \) に \( n \) 回作用させた結果を \( y_n \) と書くことにする。まず、\( n \) が小さいときの \( y_n \) を簡単な分数で表してみる。 \begin{align*} y_1 &= 1 + \frac{1}{x} = \frac{x + 1}{x} \\ y_2 &= 1 + \frac{1}{\displaystyle 1 + \frac{1}{x}} = 1 + \frac{1}{\displaystyle \frac{x + 1}{x}} = 1 + \frac{x}{x + 1} = \frac{2x + 1}{x + 1} \\ y_3 &= 1 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 1 + \frac{1}{x}}} = 1 + \frac{1}{\displaystyle \frac{2x + 1}{x + 1}} = 1 + \frac{x + 1}{2x + 1} = \frac{3x + 2}{2x + 1} \\ y_4 &= 1 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 1 + \frac{1}{x}}}} = 1 + \frac{1}{\displaystyle \frac{3x + 2}{2x + 1}} = 1 + \frac{2x + 1}{3x + 2} = \frac{5x + 3}{3x + 2} \\ y_5 &= 1 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 1 + \frac{1}{x}}}}} = 1 + \frac{1}{\displaystyle \frac{5x + 3}{3x + 2}} = 1 + \frac{3x + 2}{5x + 3} = \frac{8x + 5}{5x + 3} \end{align*}
この辺りまで出してみれば十分だろう。フィボナッチ数を \( F_n \) として、すべての自然数 \( n \) に対して以下が成り立つことが予想できる。 $$ y_n = \frac{F_{n + 1} x + F_n}{F_n x + F_{n - 1}} $$ ただし、 $$ \begin{cases} F_0 = 0 \\ F_1 = 1 \\ F_n = F_{n - 1} + F_{n - 2} \quad (n \geq 2) \end{cases} $$ である。
予想が正しいことを数学的帰納法で示す。
\( n = 1 \) のときは成立している。\( n = k \) のときに成立する、すなわち $$ y_k = \frac{F_{k + 1} x + F_k}{F_k x + F_{k - 1}} $$ であると仮定する。このとき $$ \begin{align*} y_{k + 1} &= 1 + \frac{1}{y_k} = 1 + \frac{F_k x + F_{k - 1}}{F_{k + 1} x + F_k} = \frac{(F_{k + 1} + F_k)x + (F_k + F_{k - 1})}{F_{k + 1} x + F_k} \\ &= \frac{F_{k + 2} x + F_{k + 1}}{F_{k + 1} x + F_k} \end{align*} $$ であるから、仮定の下では \( n = k + 1 \) でも成立する。以上から、すべての自然数 \( n \) に対して $$ y_n = \frac{F_{n + 1} x + F_n}{F_n x + F_{n - 1}} $$ が成立することが示された。
次に $$ \lim_{n \to \infty} y_n = \phi $$ を示す。
問題 1.13 より $$ F_n = \frac{\phi^n - \psi^n}{\sqrt{5}} \quad \left( \phi = \frac{1 + \sqrt{5}}{2}, \, \psi = \frac{1 - \sqrt{5}}{2} \right) $$ であった。
まず、以下の極限を求める。 $$ \lim_{n \to \infty} \frac{F_{n + 1}}{F_n} = \lim_{n \to \infty} \frac{\displaystyle \frac{\phi^{n + 1} - \psi^{n + 1}}{\sqrt{5}}}{\displaystyle \frac{\phi^n - \psi^n}{\sqrt{5}}} = \lim_{n \to \infty} \frac{\phi^{n + 1} - \psi^{n + 1}}{\phi^n - \psi^n} $$ \( \psi \) について $$ -1 = \frac{1 - \sqrt{9}}{2} < \frac{1 - \sqrt{5}}{2} = \psi < 0 \quad \therefore\ |\psi| < 1 $$ したがって \( \lim_{n \to \infty} \psi^n = 0 \) であるから $$ \begin{align*} \lim_{n \to \infty} \frac{F_{n + 1}}{F_n} &= \frac{\displaystyle \lim_{n \to \infty} \phi^{n + 1} - \lim_{n \to \infty} \psi^{n + 1}}{\displaystyle \lim_{n \to \infty} \phi^n - \lim_{n \to \infty} \psi^n} = \frac{\displaystyle \lim_{n \to \infty} \phi^{n + 1} - 0}{\displaystyle \lim_{n \to \infty} \phi^n - 0} = \frac{\displaystyle \lim_{n \to \infty} \phi^{n + 1}}{\displaystyle \lim_{n \to \infty} \phi^n} \\ &= \lim_{n \to \infty} \frac{\phi^{n + 1}}{\phi^n} = \lim_{n \to \infty} \phi = \phi \end{align*} $$
これを利用すると $$ \begin{align*} \lim_{n \to \infty} y_n &= \lim_{n \to \infty} \frac{F_{n + 1} x + F_n}{F_n x + F_{n - 1}} = \lim_{n \to \infty} \frac{F_{n + 1} x + F_n}{F_n x + F_{n - 1}} \cdot \frac{\displaystyle \frac{1}{F_n}}{\displaystyle \frac{1}{F_n}} = \lim_{n \to \infty} \frac{\displaystyle \frac{F_{n + 1}}{F_n} x + 1}{\displaystyle x + \frac{F_{n - 1}}{F_n}} \\ &= \frac{\phi x + 1}{\displaystyle x + \frac{1}{\phi}} = \frac{\phi (\phi x + 1)}{\phi x + 1} = \phi \end{align*} $$
よって、\( \phi \) は関数 \( f(x) = 1 + \frac{1}{x} \) の吸引的不動点である。
SICP: Exercise 1.34
「1.3.2 lambda を使う手続きの構築」でついに無名関数 lambda が出てきた。先に JavaScript で見慣れていたから驚きは少なかったけれど、他の言語でプログラミングを始めていたら大きく驚いたかも（とはいえ、例えば C 言語でも関数ポインタとかあるしなぁ…）。だんだん関数型プログラミングらしくなっていく。
あと、局所変数束縛の特殊形式 let も出てきた。
(let ((var1 exp1) (var2 exp2) ... (varn expn)) body)
は
((lambda (var1 var2 ... varn) body) exp1 exp2 ... expn)
のシンタックスシュガー。「変数の値は let の外側で計算される」ということは覚えておいた方がよさそう。
というわけで問題。
問題 1.34
手続き
(define (f g) (g 2))を定義したとする。その時
(f square) 4 (f (lambda (z) (* z (+ z 1)))) 6解釈系に組合せ
(f f)を（意地悪く）評価させるとどうなるか。説明せよ。
置換モデルで少しずつ還元していく。ややこしいので「1.1.5 手続き作用の置換えモデル」の手順で一歩ずつ。
(f f) (g 2) ; g：仮引数 (f 2) ; 仮引数 g -> f (g 2) ; g：仮引数 (2 2) ; 仮引数 g -> 2 ; エラー ; 2 は手続きでないので作用させることができない
SICP: Exercise 1.33
問題 1.33
組み合せる項にフィルタ（filter）の考えを入れることで、
accumulate（問題 1.32）の更に一般的なものが得られる。つまり範囲から得られて、指定した条件を満した項だけを組み合せる。出来上ったfiltered-accumulate抽象は、accumulateと同じ引数の他、フィルタを指定する一引数の述語をとる。filtered-accumulateを手続きとして書け。filtered-accumulateを使い、次をどう表現するかを示せ。
- 区間 \( a \), \( b \) の素数の二乗の和（
prime?述語は持っていると仮定する。）- \( n \) と互いに素で、\( n \) より小さい正の整数（つまり \( i < n \) で \( \mathrm{GCD}(i, n) = 1 \) なる全整数 \( i \)）の積
これもリストの扱いでよくありそうな処理、filter してから reduce。問題文にある通り、注目している番号が指定した条件を満たしているときのみ組合せを行うようにすればよい。
まずは再帰的プロセス版。
(define (filtered-accumulate combiner null-value pred term a next b) (if (> a b) null-value (if (pred a) (combiner (term a) (filtered-accumulate combiner null-value pred term (next a) next b)) (filtered-accumulate combiner null-value pred term (next a) next b))))
続いて反復的プロセス版。こちらの方が簡潔に見える。
(define (filtered-accumulate combiner null-value pred term a next b) (define (iter a result) (if (> a b) result (iter (next a) (if (pred a) (combiner (term a) result) result)))) (iter a null-value))
細かいことだけれど、引数の pred を入れる場所としてどこが最適かで悩んだ。この順番だと自然に読めるように感じたが、どうだろうか。
a
素数の 2 乗の和。filtered-accumulate のおかげでとても短く書ける。
(define (sum-of-squared-primes a b) (filtered-accumulate + 0 prime? square a inc b))
正しく答えが出れば prime? はどれでも良いので、1.2.6 節からどれかを持ってくる。ここでは本文と問題 1.23 のもので試してみる。
;; 反復的プロセスの filtered-accumulate (define (filtered-accumulate combiner null-value pred term a next b) (define (iter a result) (if (> a b) result (iter (next a) (if (pred a) (combiner (term a) result) result)))) (iter a null-value)) ;; 素数判定 (define (prime? n) (= n (smallest-divisor n))) (define (smallest-divisor n) (find-divisor n 2)) (define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (next test-divisor))))) (define (divides? a b) (= (remainder b a) 0)) (define (next n) (if (= n 2) 3 (+ n 2))) ;; 素数の 2 乗の和 (define (sum-of-squared-primes a b) (filtered-accumulate prime? + 0 square a inc b)) (define (square x) (* x x)) (define (inc x) (+ x 1)) ;; 2 以上 10 以下の素数（2, 3, 5, 7）の 2 乗の和を求めてみる (+ 4 9 25 49) ; => 87 (sum-of-squared-primes 2 10) ; => 87
合っていた。
b
\( n \) と互いに素で、\( n \) より小さい正の整数の積。一見ややこしい条件だけれど、互いに素（最大公約数が 1）かどうかを返す手続きを作れば分かりやすくなる。
(define (product-of-relatively-prime-numbers n) (define (relatively-prime? i) (= (gcd n i) 1)) (filtered-accumulate * 1 relatively-prime? identity 1 inc (- n 1)))
こちらもテストしてみる。
;; 10 と互いに素で、それより小さい正の整数の積を求めてみる (* 1 3 7 9) ; => 189 (product-of-relatively-prime-numbers 10) ; => 189
大丈夫だった。
抽象化のおかげで、いずれの場合も必要な部分だけ簡潔に書くことができた。無駄がなくてすっきり。
2015-05-17 の日記
このところ学校やボランティアで作業に参加しているクリエイターズネットワークで、これまで触れてこなかった技術に触れる機会が多くて、その度にいろいろなことができるようになっている。
学校では ET ロボコン 2015に向けての勉強が始まった。研究室の先生によるモデリングの特別講義を受けたり、その後で Git 勉強会を開いてみんなでコミットできるようになったり。今週末にはメンバーのひとりが名古屋に行って研修を受けるのだけれど、そのときの使用言語が学校では習っていない C++ で、慌てて一緒に勉強したりとか。とにかく授業だけでは不十分なのが実感できるのだけれど、メンバー全員が結構興味を持って取り組めているので、非常に良い雰囲気。できるだけ続けていきたい。
クリエイターズネットワークの方では最近 HTTP サーバーの調子が悪いのでいろいろ調整しているのだけれど、負荷削減やアクセスログ解析等のために Nginx を使って Web アプリを動かすための作業を行う機会が増えた。WordPress やアクセスログ解析の AWStats といったアプリごとにつまづく点があって苦労したけれど、変更するファイルの書き方を少しずつ理解できてきたので、今後同様の作業をするときには多少楽に進められるようになりそう。なんとか安定動作に持っていきたい。
日々が充実していて時間が足りないのが一番の悩みだ。
SICP: Exercise 1.32
問題 1.32
sumと（問題 1.31 の）productは、一般的なアキュムレーションの関数：(accumulate combiner null-value term a next b)を使い、項の集りを組み合せる
accumulateという更に一般的なものの特殊な場合であることを示せ。accumulateは引数としてsumやproductと同様、項と範囲指定と、先行する項のアキュムレーションと現在の項をどう組み合せるかを指定する（二引数の）combiner手続き、項がなくなった時に使う値を指定するnull-valueをとる。accumulateを書き、sumやproductがaccumulateの単なる呼出しで定義出来ることを示せ。上の
accumulateが再帰的プロセスを生成するなら、反復的プロセスを生成するものを書け。反復的プロセスを生成するなら、再帰的プロセスを生成するものを書け。
脚注 51 で触れられているように、後に並び（リスト）が出たとき、アキュミュレーションは fold とか reduce としてよく使われる。
まずは再帰的プロセスで書いてみる。
(define (accumulate combiner null-value term a next b) (if (> a b) null-value (combiner (term a) (accumulate combiner null-value term (next a) next b))))
次に反復的プロセスで書く。問題 1.30 と同様。
(define (accumulate combiner null-value term a next b) (define (iter a result) (if (> a b) result (iter (next a) (combiner result (term a))))) (iter a null-value))
sum や product を accumulate を使って書くとこうなる。
(define (sum term a next b) (accumulate + 0 term a next b)) (define (product term a next b) (accumulate * 1 term a next b))
とても簡潔。
