gosh> (use slib)
#<undef>
gosh> (require 'trace)
*** ERROR: couldn't open output file: "/usr/share/gauche/0.8.4/lib/slibcat"
Stack Trace:
_______________________________________
  0  (call-with-output-file catpath (lambda (op) (define (display* . ar ...
        At line 22 of "/usr/share/slib/mklibcat"
  1  (cons <pathname> extra)
        At line 76 of "/usr/share/slib/require.scm"
  2  (slib:load (in-vicinity (library-vicinity) "mklibcat"))
        At line 141 of "/usr/share/slib/require.scm"
  3  (catalog:get feature)
        At line 200 of "/usr/share/slib/require.scm"

エラーになります。
Gauche:FAQに解決方法が書いてありました。
要はroot権限でuseとrequireを一度実行すればその後は問題なく使えるようになるようです。

traceの使い方

実行をtraceしたい関数の名前を指定して、次にその関数を実行するだけです。

gosh >(trace f)
gosh > (f (list 1 2 3))

これを利用して再帰と反復の違いを理解しようという記事を明日書こうと思います。

※「SICPを読もう」の目次はこちら

計算機プログラムの構造と解釈

posted with amazlet on 06.04.15

Gerald Jay Sussman Julie Sussman Harold Abelson 和田英一
ピアソンエデュケーション (2000/02)
売り上げランキング: 56,404

Amazon.co.jp で詳細を見る

2006-04-16

関数型言語の勉強にSICPを読もう - (7) 1章 - 反復をマスターしたいけど・・・

Scheme SICP

「SICPを読もう - (3) 1章 - 手続きによる抽象の構築(1-30ページ)」で反復が分からないと書いたのですが、trace を使えば視覚的に関数の呼び出しが理解できるのでこれを利用してみました。

題材としては一番単純な factorial を取り上げます。
まずは再帰版

(define (factorial n)
  (if (= 0 n)
      1
      (* n (factorial (- n 1)))))

trace を行うためのおまじないをしてから実行してみます。

gosh> (use slib)
gosh> (require 'trace)
gosh> (factorial 5)
gosh> CALL factorial 5
 CALL factorial 4
  CALL factorial 3
   CALL factorial 2
    CALL factorial 1
    RETN factorial 1
   RETN factorial 2
  RETN factorial 6
 RETN factorial 24
RETN factorial 120
120

関数の呼び出し(CALL)と戻り値(RETN)が視覚的に展開されました。
関数が再帰的に呼ばれてその戻り値に1つずつそのときの引数がかけられていく様子が分かります。
ここの理解は問題ないです。

次に反復版です。

(define (factorial n)
  (iter 1 1 n))

(define (iter product counter max-count)
  (if (> counter max-count)
      product
      (iter (* counter product)
            (+ counter 1)
            max-count)))

まだ理解できていないので1.2.1のコードそのままです。

factorial, iter両方をtraceするように指定します。

(trace factorial)
(trace iter)

実行結果

gosh> CALL factorial 5
 CALL iter 1 1 5
  CALL iter 1 2 5
   CALL iter 2 3 5
    CALL iter 6 4 5
     CALL iter 24 5 5
     RETN iter 120
    RETN iter 120
   RETN iter 120
  RETN iter 120
 RETN iter 120
RETN factorial 120
120

もちろん反復でも関数は再帰的に呼ばれています。
注目すべきはiterの第1第2引数のようです。
結果が第1引数、現在のカウンタが第2引数です。
これで以前よりも大分、視覚的なイメージが頭の中に広がるようになりました。

では実際に自分だけで書けるかをやってみよう。
1からnまでの数を足し合わせる場合。

(define (sum n)
  (define (iter product counter max-count)
    (if (> counter max-count)
        product
        (iter (+ product counter) (+ 1 counter) max-count)))
  (iter 0 1 n))

できました。最初(iter 1 1 n)と書いていて(sum 10) = 56 となってしまいびっくり。
少しだけ反復にも親しみがわいてきました。
では難易度を上げましょう。

問題1.11

一度挫折したこの問題に戻ってきました。
以前は解答を見ても、さっぱり分からなかったで答えを覚えていません、真っ白な頭で再チャレンジ。

まずは再帰版

(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1))
         (* 2 (f (- n 2)))
         (* 3 (f (- n 3))))))
(trace f)
(f 4)

とても直感的に書くことが出来ます。

次に問題の反復版。
やっぱり頭をどうひねっても答えが出てきません。
答えとtrace。

(define (iter a b c count)
  (cond ((= count 0) c)
        ((= count 1) b)
        (else (iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))
(define (f-iter n)
  (iter 2 1 0 n))

(trace f-iter)
(trace iter)

gosh> (f-iter 4)
gosh> CALL f-iter 4
 CALL iter 2 1 0 4
  CALL iter 4 2 1 3
   CALL iter 11 4 2 2
    CALL iter 25 11 4 1
    RETN iter 11
   RETN iter 11
  RETN iter 11
 RETN iter 11
RETN f-iter 11

修行が足りないようです。
実は他の解答方法があってその答えはもっと簡単という可能性があるので帰ったら調べてみよう。
(今は外でこの記事を書いています。)

→調べてみたけど良いのがなかった。

問題はこういう解答が思いつくかどうかなのですが、、反復の練習問題がもっとたくさんあればパターンが見えてきそうです。
簡単なものから少しずつ難しいものへと。算数ドリルみたいなものですね。
どこかにそのような都合の良いものがないだろうか。

追記

404 Blog Not Found:Recursion vs. Iteration。
dan kogaiさんから、またまたトラックバックを頂いた。
まずはいろいろとご助言いただいたことに感謝いたします。

フィボナッチ数を計算する関数を、繰り返し(iteration)をつかって定義しなさい。再帰版は次の通り。
(define (fib n)
(cond
*1(fib (- n 2))))))
SICPの問題より良問だと思う。

取り組んでみました。

(define (fib-iter a b count)
  (cond ((= count 1) b)
        ((= count 2) a)
        (else (fib-iter (+ a b) a (- count 1)))))

(define (fib n)
  (fib-iter 1 1 n))

このような感じでしょうか。（traceのためにiterはfact-iterとして束縛していません。)
良い問題だと思いました。
factorial と例の挫折した問題のちょうど中間地点にありそうな難易度です。

ただ正直に自分がこれをどうやって解いたかといわれると、例の難題との類似性から類推したという形で、まだ完全理解にはたどり着いていない気がします。

ちなみにSICPを読んだことがある方や、Schemeを勉強された方は、どんな些細な感想でもかまいませんのでコメントをいただけるとうれしいです。
例えば「こんな簡単なことで躓くのは駄目だ!」と言われれば自分が甘えていることが分かりますし、「自分も同じところではまりました」であれば多少気持ちが楽になったりと、先人の声を聞いてみたいなと思っています。

追記(その2)

id:nobsunからとても分かりやすいコメントを頂いたので追記。
下から積み上げるというのはかなり分かりやすいですね。
でもまだ頭の中に回路ができてないです。習うより慣れろ系。

気分としては，
再帰プロセスの場合，
「一歩手前までできた」として
そいつにちょこっと手を加えると欲しいものが手にはいる．
反復プロセスの場合，
下から順に成果を積上げて，積み上げたものを次に渡して
ある条件がなりたった時点でおしまい．
という感じでしょうか．この場合，「下からどう道筋を網羅して上へ登るか」と
「つぎに渡す積み上げた成果」を考えるといいかもしれません．
fibonacciや問題1.11のようなシンプルなものの場合，下から順にならべるこ
とができます．このような列を1ステップ分ずらしてならべて，組にして眺める
となにか閃くかもしれませんね．

A------B-----

fib(0)
fib(1) fib(0) ←
fib(2) fib(1) ←
fib(3) fib(2) ←
fib(4) fib(3) ←
...... fib(4)

A----B---C---

f(0)
f(1) f(0)
f(2) f(1) f(0) ←
f(3) f(2) f(1) ←
f(4) f(3) f(2) ←
f(5) f(4) f(3) ←
.... f(5) f(4)
.... .... f(5)
SICPの本文にもあるように，再帰プロセスのプログラムを反復プロセスに
変更するのは必ずしも自明ではありません．反復プロセスはCなどでは
ループに相当します．つまり，ループは再帰よりも難しいとも言えそうですね．
たとえば，count-change を再帰プロセスではなく反復プロセスで書くのは
結構むずかしいと思いますよ．

※「SICPを読もう」の目次はこちら

計算機プログラムの構造と解釈

posted with amazlet on 06.04.15

Gerald Jay Sussman Julie Sussman Harold Abelson 和田英一
ピアソンエデュケーション (2000/02)
売り上げランキング: 56,404

Amazon.co.jp で詳細を見る

*1:= n 1) 1) ((= n 2) 1) (else (+ (fib (- n 1

2006-04-16

関数型言語の勉強にSICPを読もう - (8) 1章 - 手続きによる抽象の構築(31-44ページ)

Scheme SICP

1.3 高階手続き

やっとここまでたどり着いた。
概念は理解しているし、たまに使うけど何か発見があるのではないだろうか。

問題1.31

(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))

(define (factorial n)
  (define (next n)
    (+ n 1))
  (define (term n)
    n)
  (product term 1 next n))

これは再帰的プロセス。
反復的プロセスが苦手だ。
考えてみよう。

反復的プロセスは、状態保持のために引数が増えていて、途中経過は常に引数にわたってくる。
そのため、再帰的プロセスと違いスタック的データ構造に状態保持をしなくて良い。
という理解でよいだろうか？
結局答えを見てしまった。

(define (product term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* (term a) result))))
  (iter a 1))

問題1.32

更にもう一段抽象化する。
楽しくなってきた。

(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))))

(define (product term a next b)
  (define (multiply x y)
    (* x y))
  (accumulate multiply 1 term a next b))

34ページ

あっさりlambda式の説明が終わる。
でも、納得･理解しているので問題ないと思う。
注釈のlambdaの名前についての話が面白い。

36ページ

lambda式で

(define (f x y)
  ((lambda (a b)
     (+ (* x (square a))
        (* y b)
        (* a b)))
   (+ 1 (* x y))
   (- 1 y)))

これが一瞬分からなかった。
無名関数に引数をその場で渡している感じなのか。ふむふむ。
letはこれのシンタックスシュガーとのこと。
まだ頭の中でつながっていないけど言わんとすることは分かる。

だんだんとサンプルをきちんと打ち込まないと理解できないようになって来た。

(define x 5)
(+ (let ((x 3))
     (+ x (* x 10)))
   x)

これが38になるというのがぱっと分からない。

あぁこれは束縛の話か。
つまり

(+ (+ 3 (* 3 10)
   5)

ということ。

37ページ

区間二分法。また数学か!と身構えたが簡単だった。

41ページ

値として返される手続き。
次のステップだ。
例が難しいよ。数学的要素が少なければもっと分かりやすいのに。

43ページ

良い言葉発見
「われわれはプログラマとしてプログラムの根底にある抽象を見つけ、より強力な抽象化ができるよう、その上に構成し一般化するよう努めなければならない。
これはプログラムを可能な限り抽象的に書くべしというのではない。経験をつんだプログラマは自分の仕事に適した抽象のレベルを選ぶことを知っている。」

問題1.41

楽しくなってきた。

(define (double f)
  (lambda (x)
     (f (f x))
     ))
   
((double square) 2)

問題1.42

(define (compose f g)
  (lambda (x)
    (f (g x))))

※「SICPを読もう」の目次はこちら

計算機プログラムの構造と解釈

posted with amazlet on 06.04.15

Gerald Jay Sussman Julie Sussman Harold Abelson 和田英一
ピアソンエデュケーション (2000/02)
売り上げランキング: 56,404

Amazon.co.jp で詳細を見る

2006-04-16

file_serveをLinuxで動かしたい

Mona

Messageのエミュレーション部分は完全に動いた。

自分自身へのメッセージ送信
任意のプロセスへのメッセージ送信

が可能になった。
またMessage::lookupMainThread()もエミュレートできている。

残る作業は、

mona/core/file_server/のソースを experimental/file_server_for_linux/srcにコピー
ビルドが通るまでひたすら細かい直しをする

で良いと思う。

以上「計算機プログラムの構造と解釈」を読んでばかりでなくてMonaもやっていますよというアピールでした。