m.hana

ごあいさつ

はじめまして。プログラマですと言いたくても言えないレベルの会社員です。 まともに使える言語はJavaしかありませんが、いろんな言語をかじっては挫折、を繰り返しつつ学生時代になんとなく本を読んだLispにも手を出してみてそうこうするうちにSchemeを知り、Practical Scheme経由でこちらにきました。SICPをオンラインでみて、これはすごい本だと思ってSchemeの勉強をしたりしていますが、あんまり進んでません。SICPはSchemeですが、これをJavaやほかの言語でやったらどうなるんだろうということを考えつつ、その逆、Scheme以外で説明されているものをSchemeでやったら勉強になるかもということで試しに http://www.sra.co.jp/people/aoki/ にある「Smalltalkerのための初等数学」を教材にやってみることにしました。 試行錯誤が誰かの役に立つかもと思ったのでここにかかせてもらいます。おかしなところが多々あると思いますのでお気軽につっこんでください。（これも途中で挫折するかも...） PLTScheme使ってます。-> Gauche入れました(2006/06/10 23:42:17 PDT)

(2006/06/05 04:11:48 PDT)

5. remove

WiLiKiとかその他色々みていると自分のレベルの低さがいやになりますが、とはいえだんだんわかってきている気もしますが、読んだことをすぐに忘れてしまうのでこまります。しかし、以前読んでさっぱりわからなかったなんでもλがちょっとわかるようになっていてうれしかったりもします。

さて、removeですが、これは引数と等しい要素を削除するという関数です。Smalltalkのほうでは、集合の要素を順番に調べて一致したら削除するということをしています。うーん。最近知った事によるとGaucheにはremove!というのがあるようですが、せっかく作ったrejectが使えそうなのでこれを使ってみます。 

(define-syntax remove-from-set!
   (syntax-rules ()
     ((remove-from-set! set obj)
      (let ((result (reject set (lambda (each)
                              (equal? each obj)))))
      (set! set result)))))

これもマクロじゃないとできないですね。

テスト。 

(define (test-remove-from-set)
  (begin
    (define set1 (make-set 1 2 3))
    (define set2 (make-set 2 3))
    (define set3 (make-set 4 5 6))
    (define set4 (make-set 4 5 6))
    (remove-from-set! set1 1)
    (assert-true "(1 2 3)から1を除いたら(2 3)" (eq-set? set2 set1))
    (remove-from-set! set3 10)
    (assert-true "(4 5 6)から10を除いたら(4 5 6)" (eq-set? set4 set3))))
(test-remove-from-set)

まだGaucheの機能をまったく使ってないです。addもremoveも名前がそのままだと何にaddやremoveなのかをわかるような名前を付けていますが、オブジェクト指向だとクラスが名前空間的に使えるのでそっちの方がいい気もします。Gaucheだとモジュールとか使うんでしょうか。2006/06/24 10:16:17 PDT

やっとGauche入れました。夜中に入れたのですが、compile.cのところで妙に時間がかかったのでそのまま寝たら朝には終わってました。installでエラーが出てあれ？と思ったらsudoしてなかった。動かしてみるとおお、早い。エディタは何にしようかな。Eclipseは遅いしなー。(2006/06/10 23:42:17 PDT)

4. add

変なことを考えてました。m.hana:迷想

いよいよ集合に要素を追加するaddを作ります。addじゃよくわからないのでadd-to-setという名前にします。 これは簡単だ。なんたって僕たちにはconsがある。楽勝だ！と思っていたのですがはまりました。挫折しそうになりました。

初めは意気揚々と下のように作りました。 

(define (add-to-set set obj)
  (if (not-includes? set obj)
      (cons obj set)))

集合は重複する要素を含まないということですので含まれないかどうかチェックしてからconsします。書いてからふと。元のsetにconsされへんがな。と思いました。どうすればいいんだろう。リスト以外の何かにしなければいけないんだろうか...。うーんベクタとかあったなーとか考えながらR5RS（の翻訳版）をみてみたらベクタに値をセットする関数がありました。これだと思ってベクタを使うようにmake-setとかincludes?とかeach-elementとか全部書き直してからadd-to-setを書こうとしたら、あれ？ベクタって長さかわらないの？JavaのVectorと違うのか。ということは元のやつより大きいやつを作ってコピーして追加する要素をセットして、とかやってたら結局もとの集合に追加できないではないかということに気づきました。でも新しいやつを元のやつにset!すればいいんだな、ということはリストを使うやり方のほうがいいじゃないかと思ってまたmake-setとかincludes?とかeach-elementとか全部作り直しました。 

(define (add-to-set set obj)
   (if (not-includes? set obj)
       set! set (cons set obj)))

できた。確認。あれ？元の集合がかわってない...。あ、Schemeは値渡しか。じゃあどうすればいいんだ。完全に行き詰まりました。やめようかと思いました。しかし、じゃあset!とかvector-set!とかはどうやってるんだろうと考えていてぴーんときたのが「マクロか？」ということです。そうだマクロだと思いましたがマクロって何？というレベルなので独習Scheme三週間をみました（なぜかR5RSではない）。define-macroか。やってみたら怒られました。よく見ると実装していない処理系もあるようでPLTSchemeはそのひとつのようでした。define-syntaxというのをみたことがあるのでR5RSのマクロの節をみてみるとlet-syntaxの説明しか書いてません。構文定義の節をみると、あ、あった。しかしサンプルコードがlet-syntax使ってる...。全然書き方がわかりません。let-syntaxとおんなじ書き方かと思ってやってみたら違うしあーわからーんと思いながらいろんなことをしてやっとエラーが出なくなりました。 

(define-syntax add-to-set! 
  (syntax-rules ()
    ((add-to-set! set obj)
     (if (not-includes? set obj)
         (set! set (cons obj set))))))

これを書いた後にR5RSの下の方に、いろんなマクロが書いてあるのを見つけました...。テストします。 

(define (test-add-to-set)
      (define set1 (make-set))
      (assert-equals "set1が空ならOK" '() set1)
      (add-to-set! set1 1)
      (assert-equals "set1は(1)のはず" (make-set 1) set1)
      (add-to-set! set1 1)
      (assert-equals "set1は(1)のはず" (make-set 1) set1))
(test-add-to-set)

通りました。あー苦労した。今更ながら自分の学習の効率の悪さと頭の悪さがいやになりました（文章自体から頭の悪さがにじみでてますね）。素直にSICPをやった方がいいのかな...。(2006/06/09 18:35:20 PDT)

3. =

Scheme:Schemeプログラマのレベル10によるとレベル1.5ぐらいか...。

今回は二つの集合が同じかどうかを比較する関数です。Smalltalkの方では=メソッドをオーバーライドしていましたが、Schemeでは=という名前はまずいですよね。ちょっと考えてeq-set?という名前にしました。アルゴリズムは、お互いの要素の中で他方に含まれない要素がないことを調べるということです。SmalltalkのコードをそのままSchemeで置き換えてみます。 

(define (eq-set? set another)
  (and (null? (reject set
              (lambda (each)
                (includes? another each))))
        (null? (reject another
              (lambda (each)
                (includes? set each))))))

なんか、rejectというメソッドがありますが、これは親クラスCollectionかそのまた親クラスか...にあるメソッドのようです。こっちにはないので作ります。コードから想像するに、相手の集合にない要素を集めてくるメソッドのようです。つまり、ある集合に対してある条件に合わない要素の集合、ということですか。なんかややこしいですが、集合の要素を順に調べて条件に合わなかったらそれを結果の集合に追加していけばいいということですね。集合の要素を順に調べる、ということは前に作ったeach-elementが使えそうなのでそれを使います。eac-elementに渡すクロージャで条件に合わないやつを集める仕事をさせます。 

(define (reject set cond)
  (let ((result '()))
    (begin
    (each-element set
                  (lambda (each)
                    (if (not (cond each))
                      (set! result (cons each result)))))
    result)))

condという名前を使ってしまった。(set! result (cons result))っていうのもなんかひっかかる。とりあえずテストします。 

(define (test-reject)
    (define set1 (make-set 0 1 2 3 4))
    (assert-equals "(0 1 2 3 4)から2未満を除外すると(4 3 2)のはず"
                   (make-set 4 3 2)
                   (reject set1
                           (lambda (each) (if (< each 2) #t #f))))
    (assert-equals "(0 1 2 3 4)から5を除外すると(4 3 2 1 0)のはず"
                   (make-set 4 3 2 1 0)
                   (reject set1 (lambda (each) (equal? each 5)))))

(define (test-eq-set)
    (define set1 (make-set 1 2 3))
    (define set2 (make-set 2 3 1))
    (define set3 (make-set 2 3))
    (define set4 (make-set 1 2))
    (assert-true "(1 2 3)と(2 3 1)は同じ集合" (eq-set? set1 set2))
    (assert-true "(1 2 3)と(2 3 1)は同じ集合" (eq-set? set2 set1))
    (assert-true "(1 2 3)と(2 3)は違う集合1" (not (eq-set? set1 set3)))
    (assert-true "(1 2 3)と(2 3)は違う集合2" (not (eq-set? set3 set1)))
    (assert-true "(1 2 3)と(1 2)は違う集合1" (not (eq-set? set1 set4)))
    (assert-true "(1 2 3)と(1 2)は違う集合2" (not (eq-set? set4 set1))))

(test-reject)
(test-eq-set)

通りました。(0 1 2 3 4)から2未満を除外すると(2 3 4)じゃなくて(4 3 2)...。かっこわるい。まあ集合は順番関係ないからいいことにします。rejectのlet内にあるbeginはいらないような気がするのでとってテストをしてみると通りました。defineとかletの中は順番に評価されるんですね。

などと一発で通ったように書いてますがほんとはそんなわけはありません。eq-set?のテストで引数の順番をかえてテストしてますがなんと片方しか通らなかったのです。テスト書いてるときはまさかな、と思いながら書いてましたがそのまさかがおこりました。テスト書いててよかった。 2006/06/07 06:58:26 PDT

2.テスト

さっそくいろいろアドバイスをいただいています。ありがとうございます。アドバイスをみて「書いた覚えがない文章がある...」などと思ってしまいました。ぼけてます。

最初にはじめは集合ですとか書いてしまいましたが「Smalltalkerのための初等数学」には集合しか記事がありませんので最後まで集合です。ということでいままで作った分のテストをしようと思います。適当に関数を実行して結果を目で見て確認、ということをやっていたのですがなんどもやっているとめんどくさいのでテスト用の関数を作ることにしました。で、Schemeにもテスト用のフレームワークとかあるのでしょうが、自前で簡単なユーティリティを作ってみました。 

(define (assert-equals msg expected actual)
  (if (not (equal? expected actual))
      (begin
        (display "失敗! assert-equals ")
        (display msg)
        (display " 期待値=")
        (display expected)
        (display " 実際の値=")
        (display actual)
        (newline))))

(define (assert-true msg value)
  (if (not value)
      (begin
        (display "失敗! assert-true ")
        (display msg)
        (newline))))

失敗したときだけ失敗したことを表示します。includes?のところでequals?を使うのはよろしくないと指摘されてますが、ここでもassert-equalsにequal?を使っているのがいかにもだめっぽい。とりあえずincludes?のテストをします。 

(define (test-includes)
  (begin
    (define set1 (make-set 1 2 3))
    (define set2 (make-set 4 5 6))
    (define set3 (make-set 3 '(4) 5))
    (assert-true "(1 2 3)は1を含むはず" (includes? set1 1))
    (assert-true "(4 5 6)は (4)を含まない" (not (includes? set2 '(4))))
    (assert-true "(3 (4) 5) は(4)を含む" (includes? set3 '(4)))))_

(test-inludes)

defineを使ってますが普通はletなんでしょうか。letとdefineは何か違うのかな。テストケースはあれですが、とりあえずテストは通ったようです。

妖怪キートップはずし（息子）にキートップをはずされそうなのでこの辺で。 2006/06/06 04:43:15 PDT

1.集合-データ構造とか

ということで、はじめは「集合」です。最初にパッケージを作ったり名前空間を作ったりクラスを作ったりしてますが、全部飛ばして、メソッドnewからいきます。集合をどう作るかですが、Schemeですのでリストを使います。というかそれしか知りません。SICPのmake-ratにならって 

 (define make-set list)

としました。SICP読んでなかったらこんなこと思いつきもしなかったでしょうね。メソッドnew:sizeは作りません。initializeも作りません。 次は集合の中に、ある要素が含まれているかどうかを返すメソッドinclude:です。集合の中を調べるわけですから、集合の各要素に関数を適用するような関数があれば便利かも、と思いそのようなやつを作るというXPの精神（必要かどうかわからないものは作るな）に反することをしする私です。それが以下の関数、each-elementです。集合とクロージャを引数にとります。 

 (define (each-element set closure)
  (define (loop rest)
    (if (not (null? rest))
        (begin
          (closure (car rest))
          (loop (cdr rest)))))
  (loop set))

これができたところで、関数includes?を作ります。が、要素が含まれていることがわかったらその場で#tを返せばいいのだから、というか返したいので全部の要素を調べる必要はありません。each-elementでそんなことできるのか？しばらく考えましたができそうにないので結局each-elementは使いませんでした。XPの教えは正しかったのです（別のところで使いましたが）。ということでincludes?は次のようにしました。集合setのcarが引数anObjに等しいかどうかを調べていきます。局所的な関数loopで再帰してます。 

 (define (includes? set anObj)
  (define (loop rest)
    (if (null? rest)
        #f
        (if (equal? (car rest) anObj)
            #t
            (loop (cdr rest)))))
  (if (= 0 (set-size set))
      #f
      (loop set)))

 (define set-size length)

ちなみにeq?とeqv?とequal?の違いがいまだによくわかりません。carとかcdrが出てくるのがいやですが（抽象化できてないっぽいので）、目をつぶります。

次は要素が集合に含まれないかどうかを返すnot-includes?です。これはincludes?を使えば簡単にできました。 

 (define (not-includes? set anObject)
  (not (includes? set anObject)))

ということで今日はこのぐらいで。 2006/06/05 06:59:29 PDT

eq?/eqv?/equal?は目的に応じて使い分けるものなので、includes?内に直接書くのはよろしくないのですが、この段階では特に気にしなくても良いと思います。 また、「リストが特定の要素を含むことを調べる」のであれば、R5RSにmemq/memv/memberという手続きが定義されているので、 

  (define (includes? set anObj)
    (member anObj set))

これでもよいでしょう。setに#fが含まれていると不味いですが。2006/06/05 07:33:05 PDT

Topics
Sponsored Links
Search
Recent Changes
More ...
Last modified : 2013/04/28 22:54:26 UTC
WiLiKi 0.8.3 running on Gauche 0.9.15-p2