2011年5月30日月曜日

Scheme手習い Chapter 6(再)



算術式とは


(数を含む)アトムか、2つの算術式を+か×か↑で結合したもの


算術式の例として




  • 1 (アトム)

  • 3 (アトム)

  • 1 + 3(1と3、2つの算術式を+で結合)

  • 1 + 3 × 4(1と3、2つの算術式を+で結合した算術式と、4を×で結合)

  • cookie(アトム)


算術式の表現


「カッコはそこにないと思えばいいでしょう。」


カッコなんて飾りです。


(n + 3)というS式でn + 3を表現すると次のような利点が。




  • S式なので関数の引数とすることが可能。

  • 構造的にn + 3と似てる。


算術式と算術式が結合したら?



  • 3 + 4 × 5は(3 + (4 × 5))


    • 普通の入れ子だ!




最初に定義したnumbered?


cookieなどのシンボルや"文字列"もアトムなので算術式。


numbered?は、算術式の表現(S式)が+×↑を除いて数だけを含んでいるかどうかを決める。




  1. アトムどうか

  2. 演算子が+×↑かどうか

  3. 第一被演算子と第二被演算子をnumbered?で調べる。


簡素化したnumbered?


aexpが算術式だと分かっているなら+×↑とアトムのみ含まれるという事がわかる。


なので




  1. もしもaexpがアトムなら数かどうか調べる。

  2. 数でないなら、第一被演算子と第二被演算子をnumbered?で調べandを取る。


という風に簡素化出来る。


value


数値式である算術式の自然な値と思われるものを返す。




  • 算術式が数ならその数自身。

  • +や×や↑で結合されているなら、2つの部分式に対してvalueを再帰していけばいい。


    • 性質が同じだから再帰出来る!(2つの部分式はどっちも算術式)




算術式の表現を変える


補助関数を定義する

部分式を取り出す補助関数、1st-sub-expと、2nd-sub-expを定義する。


演算子を取り出す補助関数、operatorも定義する。


補助関数は表現を隠す

実際の算術式の表現を扱うのは補助関数。


なのでvalueで直接表現を触らずに補助関数を使うようにすると、表現の変更の影響が少くなる。(補助関数を書き換えるだけ)


抽象化出来る!


実は数も表現だった


4は4という概念を表す表現。アラビア数字の記号。


別に4を表すなら空リスト4つのリストでもいいんじゃね?


数を抽象化する補助関数

sero? edd1 zub1を定義


それを使って+を書きなおすと数の表現が()のリストで出来る。


感想


表現を直接使わないよう、補助関数を使い抽象化すると表現の変更が楽。


算術式の部分式も算術式だから再帰で処理していける。


補助関数スゴいよぅ





2011年5月20日金曜日

Scheme手習い Chapter 6



この章では抽象化っぽい事をやってるのかな?とりあえず気付き等を。


この章では算術式(簡単な計算式とか?)をS式で表現して、計算式を扱う手続きを抽象化


気付き


算術式だからarithmetic expressionでaexp、number expressionでnexp?




  • S式で算術式を表現すると嬉しい事


    • S式なので関数の引数とする事が可能である。

    • 構造的にn + 3と(n + 3)が似てる。(カッコでくくってあるだけだもんね)

    • 先頭に+を持ってきたら(+ n 3)まんまLisp



  • numbered?は


    • 演算子の+, *, exptを除いて数だけを含んでいるかを調べる



  • value


    • nexpを評価出来たw すごいw

    • 補助関数を使うと定義がすっきり。




感想




  • ちょっとテストかきづらかったかも。算術式を別形式で書いたり、戻したりで…

  • 簡単な算術式なら演算出来るようになった!ふつうの計算なら自分の定義したやつで出来る。嬉しい。

  • 実際のデータ構造から演算子や被演算子を取り出す手続きを補助関数を定義する事で抽象化しているのかな?

  • 算術式のフォーマットを変えても補助関数を書きなおすだけでvalueが動いた。すごい。

  • 最終的に数も抽象化して、'()の含まれてるリストで数を表現しててなんじゃこりゃと思ったw






2011年5月16日月曜日

Scheme手習い Chapter 5



3でlatの再帰、4で数の再帰、5はリストの再帰。




  • ここで第1の戒律、第4の戒律が最終版に。アトムのリストlatの場合、数nの場合、S式のリストの場合の再帰の掟が決まる。

  • *関数は'(), (cons a l), (cons l l)のいずれかの上で動くから、3つ質問をする。

  • equal?を定義した

  • equal?を使って任意のS式とリストを取るremberに書き直した

  • 第6の掟「関数が正しいときのみ簡素化せよ。」が登場。


    • 書いてて今までの章よりも関数のcondが多かった印象。



  • eqan?以外の関数の中のeq?や=に関してはequal?で一般化出来る。


気付き感想




  • 最初はアトムから始まり、cons、lat・数・リストの再帰と来てなんだか少しずつ扱えるデータが増えてきたような。

  • それに伴ってeq?, =, eqan?, equal?とより多くのデータを扱える関数を使ってremberを定義しなおしたり、面白い!

  • equal?を使う事で処理が簡素化出来て理解しやすくなった。すごい。

  • p91の注に出てくる話(andもorもcondの省略形として書く事は出来る)がちょっと発想の転換な気がして面白かった。





2011年5月8日日曜日

Scheme手習い Chapter 4

Chapter 3までは主にリストを再帰させてたけど今度は数の再帰。

自分の中でのまとめ
  • リストの時はリストが空かどうかを判定し再帰を終わらせるためにnull?を最初に質問したが、数で再帰する場合は再帰を終わらせるためzero?でゼロかどうか質問する。
  • 第5の戒律はわかりやすい。数で再帰する場合、再帰の終わりでは今までの計算を変えないような値を返し、リストで再帰する時はリストの終端nilを返す。
  • number?は基本関数。add1 sub1 zero? car cdr cons null eq? atom?も基本関数。

気をつけた事
  • +, -, *, /, <, >, =はoを付けo+, o-, o*, o/, o<, o>と書いた。exptはo-exptと、o-を付けた。でもlengthはo-付けずにそのまま書いた。
    • 「はじめに」p.xiiiを見るとsub1とadd1がないので組込み関数+と-を使って定義する。
    • +や-を直接書くと循環的な定義になってしまうのでo+, o-と書く。
    • という事はR5RSで定義されてる関数はo-つけたりoつけて書いた方がよいのだろうか?

疑問点
  • 基本関数って?「はじめに」p.xiiに出ているSchemeの一部の機能の中で特殊形式じゃない関数の事を基本関数と呼ぶのかな?
  • p79でもcondでnull?か調べてelseで分岐した後またcondしてる。これも簡素化してないのは3章p42「そのときに関数の構造が引数の構造と一致しないからです」という事なのだろうか。
  • p80で同じatomかの判定にeq?を使っているがこれだと同じシンボルか判定出来ても同じ数か判定出来ないのでは?(p12参照。実際eq?の引数に数が来てもかまわない、と注釈に書いてはいるが。)eqan?の間違い?

gitの使い方
とりあえずこんな感じの事をした。前にも1回やったような気がする。忘れそうなのでメモ。
こまめにpushしない方がいいかな?ちょっと悩みますね。

そんな感じです。ext/charconv/test.scmについては別途読んでエントリあげてみようかな、と。

2011年5月6日金曜日

テストの件



id:yamanetoshi さんのところでgauche.testについて触れられてたので自分でも試行錯誤してみた。


gauche.test の件 - /var/log/messages


GWなのでよく理解しないままマクロでコネコネした結果こうなったとさ。


f-testでテストしたい関数fと[answer args ...]のリストをつらつら書くとargs ...をfに与えた時の結果がanswerと一緒かテストしてくれます。ついでなんで関数名でtest-sectionも吐くように。argsは勝手にquoteするようにしてみた。でもこれだと数がargsやanswerな時まずいかもなぁ。まぁいっか。後で考える。



(use gauche.test)
(add-load-path ".")
(load "func")

(define-syntax test-q&a (syntax-rules () ((_ q a) (test* (quote q) a q))))
(define-syntax f-test
(syntax-rules ()
((_ f (a args ...) ...)
(begin
(test-section (symbol->string (quote f)))
(test-q&a (f (quote args) ...) (quote a)) ...))))

(test-start "chapter 3")

(f-test
rember
[(lamb chops and jelly) mint (lamb chops and mint jelly)]
[(lamb chops and flavored mint jelly) mint (lamb chops and mint flavored mint jelly)]
[(bacon lettuce and tomato) toast (bacon lettuce and tomato)]
[(coffee tea cup and hick cup) cup (coffee cup tea cup and hick cup)]
[(lettuce and tomato) bacon (bacon lettuce and tomato)]
[(bacon lettuce tomato) and (bacon lettuce and tomato)]
[(soy and tomato sauce) sauce (soy sauce and tomato sauce)])

(f-test
firsts
[(apple plum grape bean) ((apple peach pumpkin)
(plum pear cherry)
(grape raisin pea)
(bean carrot eggplant))]
[(a c e) ((a b) (c d) (e f))]
[() ()]
[(five four eleven) ((five plums) (four) (eleven green oranges))]
[((five plums) eleven (no)) (((five plums) four)
(eleven green oranges)
((no) more))])

(f-test
seconds
[(b d f) ((a b)
(c d)
(e f))])

(f-test
insertR
[(ice cream with fudge topping for dessert)
topping fudge (ice cream with fudge for dessert)]
;; Gauche
;; [(tacos tamales and |jalape&#241;o| salsa) |jalape&#241;o| and (tacos tamales and salsa)]
[(tacos tamales and jalapeno salsa) jalapeno and (tacos tamales and salsa)]
[(a b c d e f g d h) e d (a b c d f g d h)])

;; my insertL test
(f-test
insertL
[(ice cream with topping fudge for dessert) topping fudge (ice cream with fudge for dessert)]
[(tacos tamales jalapeno and salsa) jalapeno and (tacos tamales and salsa)]
[(a b c e d f g d h) e d (a b c d f g d h)])

(f-test
subst
[(ice cream with topping for dessert) topping fudge (ice cream with fudge for dessert)])

(f-test
subst2
[(vanilla ice creamwith chocolate topping)
vanilla chocolate banana (banana ice creamwith chocolate topping)])

(f-test
multirember
[(coffee tea and hick) cup (coffee cup tea cup and hick cup)])

;; my multiinsertR test
(f-test
multiinsertR
[(a b c d e f g d e h) e d (a b c d f g d h)]
[(w r y y y y y y y y y y) y y (w r y y y y y)])

(f-test
multiinsertL
[(chips and fried fish or fried fish and fried) fried fish (chips and fish or fish and fried)]
[(j o j o) j o (o o)])

(f-test
multisubst
[(o p p a o) o i (i p p a i)]
[() o i ()])

(test-end)


なんかだ随分寂しい感じ。すっかすか。


実行結果がこれ。diffとったけど普通に最初書いたテストと変わらなかった。



> gosh 3.scm
Testing chapter 3 ...
<rember>-----------------------------------------------------------------------
test (rember 'mint '(lamb chops and mint jelly)), expects (lamb chops and jelly) ==> ok
test (rember 'mint '(lamb chops and mint flavored mint jelly)), expects (lamb chops and flavored mint jelly) ==> ok
test (rember 'toast '(bacon lettuce and tomato)), expects (bacon lettuce and tomato) ==> ok
test (rember 'cup '(coffee cup tea cup and hick cup)), expects (coffee tea cup and hick cup) ==> ok
test (rember 'bacon '(bacon lettuce and tomato)), expects (lettuce and tomato) ==> ok
test (rember 'and '(bacon lettuce and tomato)), expects (bacon lettuce tomato) ==> ok
test (rember 'sauce '(soy sauce and tomato sauce)), expects (soy and tomato sauce) ==> ok
<firsts>-----------------------------------------------------------------------
test (firsts '((apple peach pumpkin) (plum pear cherry) (grape raisin pea) (bean carrot eggplant))), expects (apple plum grape bean) ==> ok
test (firsts '((a b) (c d) (e f))), expects (a c e) ==> ok
test (firsts '()), expects () ==> ok
test (firsts '((five plums) (four) (eleven green oranges))), expects (five four eleven) ==> ok
test (firsts '(((five plums) four) (eleven green oranges) ((no) more))), expects ((five plums) eleven (no)) ==> ok
<seconds>----------------------------------------------------------------------
test (seconds '((a b) (c d) (e f))), expects (b d f) ==> ok
<insertR>----------------------------------------------------------------------
test (insertR 'topping 'fudge '(ice cream with fudge for dessert)), expects (ice cream with fudge topping for dessert) ==> ok
test (insertR 'jalapeno 'and '(tacos tamales and salsa)), expects (tacos tamales and jalapeno salsa) ==> ok
test (insertR 'e 'd '(a b c d f g d h)), expects (a b c d e f g d h) ==> ok
<insertL>----------------------------------------------------------------------
test (insertL 'topping 'fudge '(ice cream with fudge for dessert)), expects (ice cream with topping fudge for dessert) ==> ok
test (insertL 'jalapeno 'and '(tacos tamales and salsa)), expects (tacos tamales jalapeno and salsa) ==> ok
test (insertL 'e 'd '(a b c d f g d h)), expects (a b c e d f g d h) ==> ok
<subst>------------------------------------------------------------------------
test (subst 'topping 'fudge '(ice cream with fudge for dessert)), expects (ice cream with topping for dessert) ==> ok
<subst2>-----------------------------------------------------------------------
test (subst2 'vanilla 'chocolate 'banana '(banana ice creamwith chocolate topping)), expects (vanilla ice creamwith chocolate topping) ==> ok
<multirember>------------------------------------------------------------------
test (multirember 'cup '(coffee cup tea cup and hick cup)), expects (coffee tea and hick) ==> ok
<multiinsertR>-----------------------------------------------------------------
test (multiinsertR 'e 'd '(a b c d f g d h)), expects (a b c d e f g d e h) ==> ok
test (multiinsertR 'y 'y '(w r y y y y y)), expects (w r y y y y y y y y y y) ==> ok
<multiinsertL>-----------------------------------------------------------------
test (multiinsertL 'fried 'fish '(chips and fish or fish and fried)), expects (chips and fried fish or fried fish and fried) ==> ok
test (multiinsertL 'j 'o '(o o)), expects (j o j o) ==> ok
<multisubst>-------------------------------------------------------------------
test (multisubst 'o 'i '(i p p a i)), expects (o p p a o) ==> ok
test (multisubst 'o 'i '()), expects () ==> ok
passed.


f-testとかも適当に名前つけちゃった。どうなんだろこれ。なんか分かりづらくなってしまったような気がしないでもない。





2011年5月1日日曜日

Scheme手習い Chapter 3

GW入ったのもあって早速進めようかと。
とりあえず読んでの感想的な
  • remberは「remove a member」
    • p23第1の戒律 (仮)いかなる関数を表現するときも最初の質問はすべてnull?にすべし
    • p35の定義だとmemberが見つかる前のアトムがすべて失なわれてしまう。
    • そこで偉大なるConsの出番! (p37第2の戒律 リストを作るにはconsを用いるべし。)
    • condのelseにcondを書いてるのは簡素化出来る。
  • firsts
    • p46第3の戒律 リストを作らんとせしときは、最初の要素になるものを記述し、しかる後にそれを自然なる再帰にconsすべし。
    • (else (cons (car (car l)) (firsts (cdr l)))の(car (car l))が要素になるもの、(firsts (cdr l))が自然な再帰。
    • 自然なる再帰にconsするためには、自然なる再帰の最後に返す値がリストでないといけないよね。なので最後に空リストを返すのか。(p9Consの掟 関数consは2つの引数を取る。consの第2引数はリストでなければならない。結果はリストとなる。)
  • insertR, insertL, subst, subst2は最初の解けたら似た感じだったので楽だった。
  • multi系もほぼ同じような感じだったので楽にかけた。
    • でもmultiinsertRのconsの順番間違えてmultiinsertLになってしまった。テスト通らなくて発見した。テスト様々。

疑問点や引っかかった事
  • testのnameのとこどうしよう。今はテスト本体のexprと同じの書いてるけどコピペが面倒になってきたり。
    • マクロでごにょごにょしたら出来るのかな
    • ページ番号でもいいかなーとか思ったけどぱっとみて何のテストか分からないような。
  • remberとか書くとき最初から簡素化してしまったんだけどこれは引数が空か確認する前後で分けてる感じかな?本には
    Q.ではなぜすぐに簡素化しないのですか。
    A.そのときに関数の構造が引数の構造と一致しないからです。
    と書かれてた。
  • コミットする時のメッセージのどういう風に書けばいいんだろ
    • 英語ェ…
    • 本とコミット内容の対応を取りやすいようにページ番号を入れてみた。
    • そういえば関数定義の前にもページ番号入れてみてます。自分で定義したやつはmy ~って書いてたり。
  • テストケースが無い関数は自分で考えないので頑張りたいところ。テストケースある関数に対しても自分でテストケース加えた方が楽しめるかな?
  • ハラペーニョ問題
    • jalapñoのñの読み方と入力方法がわからなかった。調べたところ「エニェ」
    • そもそもñってシンボルの名前に使えるのか?
    • 困った時はR5RS。
      Revised^5 Report on the Algorithmic Language Scheme
      The rules for writing a symbol are exactly the same as the rules for writing an identifier; see sections 2.1 and 7.1.1.
      という事で、シンボルを書くときのルールは識別子を書くときのルールと一緒みたい。とりあえずsections 2.1と7.1.1.を見よう。

      Revised^5 Report on the Algorithmic Language Scheme
      The precise rules for forming identifiers vary among implementations of Scheme, but in all implementations a sequence of letters, digits, and ``extended alphabetic characters'' that begins with a character that cannot begin a number is an identifier. In addition, +, -, and ... are identifiers.Here are some examples of identifiers:

      lambda q
      list->vector soup
      + V17a
      <=? a34kTMNs the-word-recursion-has-many-meanings Extended alphabetic characters may be used within identifiers as if they were letters. The following are extended alphabetic characters: ! $ % & * + - . / : < = > ? @ ^ _ ~ See section 7.1.1 for a formal syntax of identifiers.

      Schemeの処理系によって異るのかな、でもlettersとdigitsと記号はokっぽい。んで7.1.1を見ろと書いてあるので見る。

      Revised^5 Report on the Algorithmic Language Scheme
      こちらに図が載っておりました。identifierからこそこそ見てみるとなんかñは駄目っぽい
      http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-G-3.gif
    • という事でjalapeñoはjalapenoで代用しました。
    • ちなみにGaucheのドキュメントでこんなものを発見
      Gauche ユーザリファレンス: 6.6 シンボル
      R5RSのシンボルの定義では許されていない文字を使った妙な名前のシンボルを表記するのに 使う構文です。
      なるほど。これを使えばいいのか。使ってテストしてみるとこんな感じでした。


後は、multiremberをtraceしてみたけど分かりやすかった。たまにやっとこう…