Scheme修行16章

TheSeasonedSchemer (5) - /var/log/messages

自分も!をbangと呼ぶの知らなくて今まで「setびっくり!」とか「setびっくら!」って読んでました。

#!をshebangと呼ぶのと似た感じですね。

letでつけた名前は内側のlambdaからしか見えなかったりするので確かに属性みたいな感じ。

15章は1ステップずつ読まないと前の問いが後ろに影響することもあって(define した値にset!してたり)結局テスト書いてないです。

16章もそんな感じでがんがんset!してたのでテスト中途半端にしか書けてないです orz

本に書いてあるコードを1つずつ実行したログを編集して16.logとしてまとめました。

感想

途中まではメモ化にset!を使う話をしている気がしました。

• まずは普通に再帰


• 再帰の結果をメモ


• (deep n)は(cons (deep (- n 1)) '())なので(deep (- n 1))がないか調べる


• deepの再帰の中でもメモ化したdeepMを呼び出すようにする

その流れで第19の戒律

関数の二度の呼び出しにまたがり貴重なものを覚えておく際には(set! ...)を使用して貴重なものをおぼえておくべし。

が出てきました。

後半はletrecの仕組みとY!コンビネータ、YとY!の違いについて、といった感じがします。

YとY!の違いを理解するのにちょっと時間かかりました orz

この章も深い。

メモ

• この章もset!ばかりで、テストどうかこう orz
  
  
  
  
  • 結局中途半端にテスト書きました。
  
  
  
  


• deepやsweet-toothの実行結果をset!でlistに保存していく


• 第19の戒律が出てきた。
  
  
  
  
  • 1回の呼び出し内で複数回使われる値はletで、複数回にまたがる場合はset!で覚えておく
  
  
  
  


• deepM
  
  
  
  
  • findは値が見つかる場合に呼ばれる
    
    
    
    
    • 後ほどfindに値が見つからない場合を1行追加
    
    
    
    
  
  
  • findが呼び出せるかはあらかじめdeepMがmember?で調べる
  
  
  • この役割分担がいいなぁ
  
  
  • deepRを内側に取り込んで簡素化
  
  
  
  


• p120まではメモ化の話かな?


• p121、第17の戒律最終版、xの新しい値がx(自分自身?)を参照する関数のとき、が追加


• 「架空の名前h1を通して自分自身の再帰的コピーを参照しているだけです」


• Y!コンビネータ
  
  
  
  
  • 再帰的な部分だけ残してlengthに特徴的な部分を切り出す
  
  
  • Lに(lambda (arg) (h arg))を渡してる
    
    
    
    
    • hをそのまま渡すと(set! h (L h))になってしまう
    
    
    • それだと(L h)となり、hが先に評価される
    
    
    • 新しいhになる前のhの値そのものをLに渡してしまわないように、lambdaでくるんでる?
    
    
    
    
  
  
  
  


• letrecはletとset!からなる式の省略らしい。letrecを使ったバージョンがY-bang


• この流れが適用順手続き的Yコンビネータの導出、らしい

YとY!の違い

「Y!はこの形をした全てのfに対してYと同じ再帰関数を作り出す」

biz関数をYに適用した場合と、Y!に適用した場合とで結果が違う。

違いを確かめるために2つのことを試してみました。

• biz関数の(lambda (a)の下に(print x)つけたら、Y!だとxがずっと1のままだった。


• biz関数の(set!の下に(print x)つけるとYは毎回表示、Y!だと1回しか表示されない

よくよく定義を見ると

• Yは(biz (lambda (arg) ((f f) arg)))の(f f)で自分自身を得る際に毎回bizを呼び出してる


• Y!は(set! hする時、1回しか(biz (lambda (arg) (h arg)))を呼び出さない

(Y biz)には再帰に(set!の部分が含まれてるけど(Y! biz)では含まれてない、という違い。

Y!だとxは1のままなので終わらないです。

気になること

「ありがとう、Peter J.Landin」とあったので名前で検索したら

関連する項目でISWIM - Wikipediaを見つけ

「J演算子は継続を可能としたもので、Scheme の call/cc は J 演算子を簡略化したものである」

という興味深い記述を見つけました。J演算子…

他にもScheme手習いのYコンビネータの前半部分(lambda (f) (f f))のUコンビネータ、SKIコンビネータなど

そこらへんがっつり調べたり、いい資料あったら教えてもらいたいです。

JavaScript

JavaScriptも手続きオブジェクトがあって面白いですよね。

A re-introduction to JavaScript - MDNやってみます。

JavaScriptでクロージャを云々だとWhat’s a Closure?のレッスンも面白かったです。

Scheme修行15章

Scheme修行は毎章違う題材が出てきます。前の章の継続も面白かったけど今回のも面白い。

メモ等

• ここに来て初めてdefineで値に名前をつける。


• set!の読み方「セット、バン!」


• set!は値を返さない。defineと似たもの。Lispではsetq(セットキュー、説得)


• set!すると名前の参照を変更出来る。あたかもxが定義されてないときにdefineで名前をつけるように。


• lambdaの値部分に2つ式があるのはletやbeginと同じ。2番目の式(最後の式)の値を返す。


• 別々の関数で同じ名前に対してset!する衝突が起こりえる。それは困る。


• lambdaをletで囲む
  
  
  
  
  • あたかも架空の名前x1をdefineしたかのよう
  
  
  • 架空の名前の値はない。
  
  
  • 架空の名前が何を表しているか覚えておかないといけない
  
  
  
  


• 16の戒律「(let...)で定義された名前に対してのみ、(set!...)を使うべし
  
  
  
  
  • 大域的な名前にset!すると駄目
  
  
  
  


• 第17の戒律(予備版)

(let ( (x ...)) ...)に対して(set! x ...)を用いる際には

それらの間には少なくとも1つのlambdaを置くべし

• letとsetの間にlambdaを入れないで使っても何かを覚える役には経たない


• 第18の戒律「(set! x ...)はxが参照する値がもはや必要ないときにのみ使うべし」
  
  
  
  
  • set!すると値への参照がなくなってしまうので。
  
  
  • swapを例に
  
  
  • letを使って名前をつけるとその値を参照するのに2通りの方法がある
  
  
  
  

感想

15章ではset!の使い方と破壊的代入の問題点を説明している感じがしました。

ふつーのプログラミング入門だと変数に値を入れるのが関数の定義よりも先に来ますよね。

Scheme手習い、Scheme修行ではアトムから始まって、すぐに関数を定義して、値は引数で取り、関数を組み合わせて抽象化し、わざわざ関数に名前をつけずともY Combinaterがあれば再帰が出来る事を示し、計算結果を覚えるためにletを使い、と、ここまで値にdefineで名前をつける必要がありませんでした。

set!の説明と問題点を示すためだけにdefineで値に名前をつけている気がします。

関数プログラミング的な考えが重用視されてるような感じをちょっと受けています。

次の章が楽しみです。set!の上手い使いどころを示してくれそうな感じ。

# ホワイトボード使ってやるのも楽しそうですね

※ところでこの章、試験なナニを書けない気がします。なので実行ログを残しました。

gosh> (define x
(cons 'chicago
(cons 'pizza '())))
x
gosh> x
(chicago pizza)
gosh> (set! x 'gone)
gone
gosh> x
gone
gosh> (set! x 'skins)
skins
gosh> (define gourmet
(lambda (food)
(cons food (cons x '()))))
gourmet
gosh> x
skins
gosh> (cons x '())
(skins)
gosh> (gourmet 'onion)
(onion skins)
gosh> (set! x 'rings)
rings
gosh> (gourmet 'onion)
(onion rings)
gosh> (define gourmand
(lambda (food)
(set! x food)
(cons food (cons x '()))))
gourmand
gosh> (gourmand 'potato)
(potato potato)
gosh> x
potato
gosh> (gourmand 'rice)
(rice rice)
gosh> x
rice
gosh> (define diner
(lambda (food)
(cons 'milkshake (cons food '()))))
diner
gosh> (define dinerR
(lambda (food)
(set! x food)
(cons 'milkshake (cons food '()))))
dinerR
gosh> (dinerR 'onion)
(milkshake onion)
gosh> x
onion
gosh> (dinerR 'pecanpie)
(milkshake pecanpie)
gosh> x
pecanpie
gosh> (gourmand 'onion)
(onion onion)
gosh> (define omnivore
(let ((x 'minestrone))
(lambda (food)
(set! x food)
(cons food (cons x '())))))
omnivore
gosh> 'minestrone
minestrone
gosh> (omnivore 'bouillabaisse)
(bouillabaisse bouillabaisse)
gosh> (define gobbler
(let ((x 'minestrone))
(lambda (food)
(set! x food)
(cons food (cons x '())))))
gobbler
gosh> (gobbler 'gumbo)
(gumbo gumbo)
gosh> (define nibbler
(lambda (food)
(let ((x 'donut))
(set! x food)
(cons food (cons x '())))))
nibbler
gosh> (nibbler 'cheerio)
(cheerio cheerio)
gosh> (define food 'none)
food
gosh> (define glutton
(lambda (x)
(set! food x)
(cons 'more (cons x (cons 'more (cons x '()))))))
glutton
gosh> (glutton 'garlic)
(more garlic more garlic)
gosh> food
garlic
gosh> x
onion
gosh> (define chez-nous
(lambda ()
(set! food x)
(set! x food)))
chez-nous
gosh> food
garlic
gosh> x
onion
gosh> (chez-nous)
onion
gosh> food
onion
gosh> x
onion
gosh> (define chez-nous
(lambda ()
(let ((a food))
(set! food x)
(set! x a))))
chez-nous
gosh> (glutton 'garlic)
(more garlic more garlic)
gosh> food
garlic
gosh> (gourmand 'potato)
(potato potato)
gosh> x
potato
gosh> (chez-nous)
garlic
gosh> food
potato
gosh> x
garlic
gosh>

リポジトリの方にもcommitしてるのですが、外出先からPDA Net使ってgit pushしようとしたのですが繋がらないため、GitHubの同期はちょっと遅れてしまいそうです。ごめんなさい。

Scheme修行14章

14章では新しく第15の戒律、letが出てきます。進むにつれて第14、第12の戒律を組み合わせて少しずつ奇麗なコードへ。

letccで得た方位磁針を渡してskipするなど前章とちょっとだけ違う使い方をしてるのも面白かったです。

気づいた点等、とりあえずメモ書き。

• 同じ式が繰り返しでてくるのはまずい
  
  
  
  
  • 関数を理解するのに同じ式を2回読まないといけない
  
  
  • 関数を読んでる人が理解しづらいのと、2回評価するからその分計算が増えるからいけてない
  
  
  
  


• 繰り返される式に名前をつけるためにletを使う
  
  
  
  
  • 再帰関数に名前をつけるのにはletrecを使う(以前の章でやった)
  
  
  • letrecは多分let recursiveの略、letは何の略かな?
  
  
  • letは以下のλ式のシンタックスシュガー
    
    
    
    
    • (let ( (x1 α1) ... (xn αn)) β...)
    
    
    • ((lambda (x1 ... xn) β...) α1 ... αn)
    
    
    • λの仮引数x1...xnがα1...αnに束縛される
    
    
    • letrecは複数定義したのを相互に使えるけどletは駄目。
    
    
    • α1...αnを評価している環境の違いかな?
    
    
    
    
  
  
  
  


• eqlist?はTheLittleSchemerでは自分で定義してた。(define eqlist? equal?)して代用。


• letrecとletを使ってrember*を定義
  
  
  
  
  • avは何の略だろう?
  
  
  
  


• 第15の戒律(仮)「繰り返される式の値に名づくるには(let ...)を用うべし。」
  
  
  
  
  • 「名づくる」「用う」初めて見た
  
  
  
  


• rember1*を途中までrember*に空目してた


• p70のdepth*は書き換えてテスト実行したけど確かに通らなかった
  
  
  
  
  • lが空か分かる前に(car l)の値に依存してしまっている
  
  
  
  


• p73のdepthは非常に読みづらい
  
  
  
  
  • 1回しか評価されないのにletで名づくるのは読みづらくなったりする
  
  
  
  


• 第15の戒律「関数定義において繰り返される式は、当の関数を1回使用するときに2回評価される可能性があるなら、それらの値を名づくるに(let ...)を用うべし。」


• if文出てきた!
  
  
  
  
  • もっと前に知っておくべきだった?「何事にも、ふさわしい時と場所があるのです。」
  
  
  • (if α β γ)は(cond (α β) (else γ))と同じ
  
  
  • condを知ってればすっとifを理解出来る。
  
  
  • 答えによって2つに分かれる時ifを使うとcondよりも読みやすくなる
  
  
  
  


• 最初のコードから掟に従いつつ構造を考えていくと可読性があがりますね
  
  
  
  
  • 比較するために1回、値を返すためにもう1回、合わせて2回評価してた
  
  
  • letで束縛すると2回評価しないでよくなってコードもすっきり
  
  
  • 2つに分岐するだけならifのがすっきり
  
  
  • やってることを抽象化してmaxを使えばすっきり
  
  
  • リファクタリングってこんな感じなのだろうか
  
  
  
  


• letのbody部分に複数の式を置いてbegin的に使うなど


• 「第14の戒律を用いるときに第13の戒律を忘れてはならない」
  
  
  
  
  • 関数を書き直していく時、今まで出てきた戒律を意識せねば。
  
  
  
  


• letで順番よく実行している途中で答えを見つけたとき、抜け出すために方位磁針skipを使う
  
  
  
  
  • 継続を取り出してからマイナー関数に渡すことで、マイナー関数の中で値が求まった時に即座に返す事が出来る!
  
  
  
  


• letccを使ったrember1*について
  
  
  
  
  • rember1*の中で、(car l)から何も取り除けなかったら方位磁針を使って戻って来る。
  
  
  • 取り除けた時はaを取り除いたリストを作りながら戻って来る。
  
  
  • 取り除けなかった時はnoっていうアトムを持って戻って来る。
  
  
  • 取り除けたら終わり、取り除けなかったらcdrで再帰
  
  
  • 方位磁針を使う事がないと分かっている場合は、0や'()を方位磁針として渡しても大丈夫。
  
  
  
  


• tryを使うとちょうすっきり書ける。tryはマクロで書いた。
  
  
  
  
  • (try x a b)aの中でxを使うとaを抜けて、bを返す
  
  
  • 使わずにaを終了した場合、bは実行せず即座に値を返す
  
  
  
  

感想等

この章は結構ボリュームあった。休憩させるために「象を数えてみましょう。」とかそういうのが出て来るのが多かった気がする。

途中まではletの使い方で、2度評価される式に名前をつけたり、letをbeginのように使う使い方が出てきたり面白い。

後半数ページはletあまり関係なく継続の話だった。

引数でletccの方位磁針を受け取ったり、ifの条件式の中でletccを使うなど今までと違う使い方が出てきてこれもまた興味深い。

あと、tryを使うとなんだかものすっごいすっきり書けますね。

rmから結果を受け取って、rmの外側で成功したか判断して値を返すのではなく、

rm自身に失敗時の処理へ飛ぶ方位磁針を渡して渡しているのが面白い。

方位磁針を使わなかったら失敗時の処理へは飛ばず、rmの値が返る。

rmがその方位磁針を使うか使わないかをrmの内側で制御出来るようなイメージ。

方位磁針を使った時に返す値('no)をいじるともっと色々出来るのかな?

修行読みつつ(読み終わったら、になるかもしれないけど)プログラミングGauche読みます。

次の章への期待

この章まででかなり色々な関数の使い方を覚えました。

15章は表紙の絵だし、タイトルも「大人と子供の違い…」と、一区切り付きそうな印象。

時間をしっかり作りながら読んでいきたいと思います。

そういえば、バイト出始めたのでプライベートな時間ががくっと減って、働きながら勉強してって大変だなと思いました。

いつもおつきあい頂いてありがとうございます。 id:yamanetoshi となく!

Scheme修行13章

letcc - /var/log/messages

フライングされていたので早速13章を読みました。1度読んで2度目読む前にプログラミングGaucheの継続の章を斜め読みしたらちょっとすっきりしました。

その後バスの中でもう一度読んでソースコード書きながら読んで、再度メモを確認しつつ軽く読んだのでエントリを書きます。

letccについて

call-with-current-continuation、その略のcall/cc、継続の事です。

Scheme 修行 - /var/log/messages

を参考にgaucheのマニュアルのletccの項目Gauche ユーザリファレンス: 6.17 制御を読むと

(let/cc var body…)が(call/cc (lambda (var) body …))に展開されると書いてあります。

なのでlet/ccを使うことにしました。

メモ書き

• (hop M)に遭遇する前にすべきことだった事を全て忘れて(letcc hop M)の値を求めたかのように振る舞う


• (letcc hop ( (hop)を呼び出すまでの色々な手続き ) M)の色々な手続きを全部忘れてMのところまでジャンプすると考えちゃってもいいのかな


• hopと唱えて、結果と一緒に正しい場所へ


• 第14の戒律「(letcc ...)を用いて、値を直ちに、すばやく返すべし。」


• どこかで覚えてた計算を忘れる


• intersectallとrember-upto-lastで違うとこ
  
  
  
  
  • intersectallは結果が何かを知っている
    
    
    
    
    • 空集合が1つでもあれば、結果は空集合
    
    
    
    
  
  
  • rember-upto-lastはリストの部分が結果に「ない」か知っている
    
    
    
    
    • リストの中にaを見つけたら、リストの残りに結果がある。前の部分には「ない」。
    
    
    
    
  
  
  
  


• consが結果を待ってるはずなのにconsしないでskipしてたり色々と面白い。


• 結果をまたずに抜け出すとき、必要のない部分を捨てるときに使うと便利っぽい
  
  
  
  
  • 計算途中だった値はどこへいっちゃうんだろ
  
  
  
  


• 継続についてはもうちょっと別の本やウェブサイト読まないと完全には理解出来てなさそうな感じがする

間違いかな?と思ったもの

• p45の(null? (cdr lset))の質問の答えは真じゃないかな?


• p49とp50のJの中のcondのmember?とelse?の結果の式は反対じゃないかな。

感想

再帰がどんなに深くても一番最初のとこまで戻って来れる! すごい!

継続はもっと色々な使い方が出来そうなのでScheme修行読んだらプログラミングGauche読んで再度勉強したい。

そういえば「再起」関数のtypoをオーム社さんのTwitterアカウントにmention飛ばしたんだけど返事が帰ってきてないので後でちゃんと窓口から連絡しようと思います。

Scheme修行12章

学園祭の準備をしつつ12章を読みました。学園祭が無事終了したのでブログのエントリをあげます。

11章では必要があれば一つ前の要素や今までの加算の結果や逆順のリストなど付加的な引数を渡す、第11の戒律を学びました。

JavaScriptのreduce - MDNと似た感じの印象を受けました。

12章ではletrecについて。

再帰する時に変化しない引数をletrecを使って除く方法、第12の戒律を学びます。

この章の名前は「避難しましょう」です。letrecのもう1つの使い方として、補助関数を守るための第13の戒律が出てきます。

メモなど

• multiremberのYコンビネータを使った定義では一番外側のlambdaでaが束縛されるのでYコンビネータに渡す関数の中でaを使う事が出来る。


• p18の動かないmrの定義
  
  
  
  
  • mrの中のaは束縛されていない自由変数
  
  
  • Schemeは静的スコープなのでmrが定義された時にaが値に束縛されてないとunbound variableとエラーが出て動かない。
  
  
  • mrを呼び出しているmultiremberの中の変数aはmrの定義時にはスコープの外、mrからはaが見えていない。
  
  
  • 試しにElispで書いたら動いた。Elispは動的スコープなので呼び出し元の環境の変数aを参照するため動く。

(defun mr (lat)
(cond ((null lat) '())
((eq a (car lat)) (mr (cdr lat)))
(t (cons (car lat) (mr (cdr lat))))))

(defun multirember (a lat)
(mr lat))

(multirember 'pie '(apple custard pie linzer pie torte))

• p19にてα変換、α同値の話が出てくる。


• p20 「再起関数」typo発見


• p20 「(letrec ...)の名前づけ部分で定義された関数は囲まれている全ての(lambda ...)式の全ての引数を知っています。」
  
  
  
  
  • (letrec ( (mr ...) ) mr)はmrという名前の関数を定義して、その再帰関数を返している。
  
  
  • letrec中のmrは外側のlambdaの引数aを知っている。


• letrecを使ったmultirember
  
  
  
  
  • mr pieを定義してlatに用いたように見える
  
  
  • p21下線のついたdefineは実際には存在しないけれどそのように想像することで理解の助けになる
  
  
  • mr pieはdefineを使って定義した関数と違って外側からは見えない!


• 第12の戒律「再帰を適用している間に変化せぬ引数を除くには(letrec ...)を用いるべし。」


• p23~p26でletrecを使ってmultirember-fを定義している。letrecの使い方は同じ。関数を定義して返す。


• member?やunionなどを第12の戒律に従い書き直し。
  
  
  
  
  • member?の中のyes?で引数の名前がlなのはlatと被らないように?それとも短い名前がよかったから?


• 関数を守る
  
  
  
  
  • unionの中のUは、unionが知っている事はすべて知っている。
  
  
  • unionの中にmember?の定義は出てこない
  
  
  • unionの動作はmember?に依存してる。member?の引数の順番が変わったら動かなくなってしまう。
  
  
  • letrecはかっこで囲んだ関数定義を複数おける。(condの条件みたいに)
  
  
  • そこで、unionの内側のletrecでmember?を定義する


• 第13の戒律「関数を隠し、守るには、(letrec ...)を用いるべし。」
  
  
  
  
  • 補助関数はその関数にとって特別な値に使う。だから補助関数の定義が変わって変な値を返さないようにその場に隠す。

感想

letrecと(define (hoge) (define (fuga) ...) ...)

SICPでは補助関数はdefineの中でdefineを書いてた気がします。

defineの中にdefineだとどうなるんだろう、気になったので調べてみると

letrec - karetta.jp

letrecを使うか、defineの中にdefineを書くかは好みの問題です。

本当に好みの問題なのか気になったのでR5RSを読んでみると

Revised(5) Report on the Algorithmic Language Scheme

内部での定義を含む<ボディ>は、完全に等価なletrec式に必ず変換できる。例えば上記のlet式は次の式に等価である。

だそうで、やっぱり好みの問題らしい。

印象に残った部分

p28の

Q.

そのとおり。AはUとまったく同じ名前です。
どんな名前でもかまいませんよね。

A.

かまいませんが、定義を楽しみたい人にとって名前の選び方は大切です。

と書いてあったのがちょっと印象的。やっぱり関数の名前付けは大事。

Aじゃよく分からなくてもUだったらUnionのUだなって分かるので。

テスト

今まで

$ gosh test11.scm

とやってたのを

$ for i in `ls test*.scm`; do gosh $i; done

とするようにした。今回11.scmの中身も書き換えたのでいちいちgosh test11.scm、gosh test12.scmと2回やるのが面倒だったので。

シェルスクリプトも覚えないと orz

少し残った疑問と次章への期待

関数をどこらへんまで守るべきなんだろうか。

他にもmember?を使う関数があったらその関数も内部で同じmember?を持つので無駄な気もするんだけど。

member?が引数を決まった順序で取るという仮定が崩れないなら使ってもいいのかな…

とりあえず

• 関数が他の関数の定義に依存すると、依存している関数の定義を変えたとき動かなくなってしまう


• 動かなくなると困る関数はletrecで守る。隠す。

というのをしっかり頭に置きながら残りの章を読んで行きたいと思います。

どうやら次章でついに継続が出て来る! call/cc! call/cc!

楽しみです :)

Scheme修行11章

11章を読んでいたのでメモと感想をまとめてみます。

メモ

• Scheme手習いの続きなので11から始まる。


• 究極のλを知っていますか?


• two-in-a-row-b?は2つの引数が変わるのに、質問は1つの引数についてのみ


• p10「一方の引数は他方の引数について関数に何かを伝えます」
  
  
  
  
  • このトリックは面白い
  
  
  • two-in-a-row-bのprecedingではlatの引数の前の要素を
  
  
  • sum-of-prefixes-bのsonssfはこれまでの全ての数の合計を
  
  
  • scramble-bのrev-preは自分より前の部分の逆を
  
  
  
  


• 第11の戒律「ある関数が、その関数に対する他の引数がいかなるものか知る必要があるときは、付加的な引数を用いるべし。」


• 出てきてる用語
  
  
  
  
  • parsleyはパセリ
  
  
  • sardinesはイワシ
  
  
  • sonssfは「sum of numbers seen so far.(それまで見てきた数の合計)」の略
  
  
  • scrambleのニュアンスがちょっと分からない
  
  
  • rev-preはreversed prefix
  
  
  
  


• 前章で定義してあったone?やpickなどの手続きを使っているので、11.scmの先頭に定義した
  
  
  
  
  • atom?等、他の章でも使うものは共通のファイルに抜き出していこうと思う。
  
  
  
  


• 「関数の手がかりは、いつだってその名前です。」
  
  
  
  
  • いい名前は理解を助けてくれますね。
  
  
  
  


• 食事の回数、3回
  
  
  
  
  • p13 「覚えているならアイスクリームを食べましょう」
  
  
  • p15 「スナックを食べる前に」
  
  
  • p15 「お茶の時間です。」
  
  
  
  

感想

「はじめに」によると「食べ物がちょっとした気晴らしになってこの本を一度にたくさん読まないで済むことを願っている」らしい。

でも面白いから読み始めると1章、一気に読んでしまいますね。

読んでから少し時間が経ってしまったので理解しているか確かめるためにthree-in-a-row?を定義してみた。

(define three-in-a-row-b?
(lambda (preceding1 preceding2 lat)
(cond ((null? lat) #f)
(else (or (and (eq? preceding1 preceding2)
(eq? preceding2 (car lat)))
(three-in-a-row-b? preceding2 (car lat) (cdr lat)))))))

(define three-in-a-row?
(lambda (lat)
(cond ((null? lat) #f)
((null? (cdr lat)) #f)
(else (three-in-a-row-b? (car lat) (car (cdr lat)) (cdr (cdr lat)))))))

で、n-in-a-row?を定義したくなったので色々といじっていたらいつの間にかYコンビネータを書いたり

(define Y
(lambda (f)
((lambda (x) (x x))
(lambda (x) (f (lambda (y) ((x x) y)))))))

(define L
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (+ 1 (length (cdr l))))))))

(define T
(lambda (take)
(lambda (nl)
(cond ((= 0 (car nl)) '())
(else (cons (car (car (cdr nl)))
(take (cons (- (car nl) 1)
(cons (cdr (car (cdr nl)))
'())))))))))
(define length (Y L))
(define take (Y T))

(define n-in-a-row?
(lambda (n)
(Y (lambda (n-in-a-row?)
(lambda (lat)
(cond ((> n (length lat)) #f)
(else (or ((Y ((lambda (a)
(lambda (every)
(lambda (lat)
(cond ((null? lat) #t)
((eq? a (car lat))
(every (cdr lat)))
(else #f)))))
(car lat)))
(take (cons n (cons lat '()))))
(n-in-a-row? (cdr lat))))))))))

それを無名にしてみたり

(define n-in-a-row?
(lambda (n)
((lambda (f)
((lambda (x) (x x))
(lambda (x) (f (lambda (y) ((x x) y))))))
(lambda (n-in-a-row?)
(lambda (lat)
(cond ((> n (((lambda (f)
((lambda (x) (x x))
(lambda (x) (f (lambda (y) ((x x) y))))))
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (+ 1 (length (cdr l)))))))) lat)) #f)
(else
(or (((lambda (f)
((lambda (x) (x x))
(lambda (x) (f (lambda (y) ((x x) y))))))
((lambda (a)
(lambda (every)
(lambda (lat)
(cond ((null? lat) #t)
((eq? a (car lat)) (every (cdr lat)))
(else #f)))))
(car lat)))
(((lambda (f)
((lambda (x) (x x))
(lambda (x) (f (lambda (y) ((x x) y))))))
(lambda (take)
(lambda (nl)
(cond ((= 0 (car nl)) '())
(else (cons (car (car (cdr nl)))
(take (cons (- (car nl) 1)
(cons (cdr (car (cdr nl)))
'())))))))))
(cons n (cons lat '()))))
(n-in-a-row? (cdr lat))))))))))

なんかこの章の理解を確かめるというより究極のlambda復習してしまった orz

Scheme修行の11章を読む前に

Scheme手習いを読み終わったのでScheme修行を読みます。

本文の前に

• 訳者前書き


• 序文


• はじめに

があるのでまずは気になったところのメモと感想など書きます。

訳者前書き

メモ

• Scheme手習いと同じ著者による続編


• 2冊合わせてSchemeの入門書として完結
  
  
  
  
  • なのでScheme手習いの続き、11章から始まっている
  
  
  
  


• Scheme手習いと同じく質問と答えのペア


• 前作は「再帰的」な考え方、今回は継続と代入


• 他の言語にも継続に似た機能はある
  
  
  
  
  • Lispの例外(catch throw)やCのsetjump, longjump
  
  
  • 大域的な脱出手段なので後から使えない(のかな?)
  
  
  • Schemeの継続はいつでも使用することは可能
  
  
  
  


• Scheme手習い・Scheme修行ではSchemeの制御構造については継続をのぞいては触れられていない
  
  
  
  
  • 末尾再帰最適化の話とか
    
    
    
    
    • Schemeは静的束縛なのでそれが実現出来るらしい
    
    
    • 動的な束縛をする言語では実現出来ない
    
    
    • 似たような言語だからといってLispで同じことをやるとスタックが溢れる
    
    
    
    
  
  
  
  


• letccを実現するためにletccを使っているので本書で作成しているインタプリタはSchemeでしか実現出来ない


• 継続渡しスタイルについて調べてみるのも面白い

感想

スタックの話でもあったけどSchemeはLispの方言とは言うがLispとは別物のよう。

Lispによって変数のスコープも違えば言語で規定されてる機能も全然違いそう。

継続渡しスタイルについては後で継続渡しスタイル - karetta.jpを読もうと思う。

ということはSchemeじゃないLispにはSchemeにない機能もあるに違いないので読み終わったら取り組む。

実はPractical CommonLisp読んでる途中でやめちゃいましたので。

序文

メモ

• 「もし誰かに魚をあげたら、一日食べることができる。もし誰かに釣りを教えたら、一生食べることができる。」


• Lispは元々「LISt Processor」、リスト処理


• Lispはリストだけでなく計算を行う関数を持っている。リストはLispの心臓、関数は魂。


• 生きるためには食べ物以外のものも必要。釣りを習いましょう!

感想

リストが心臓で関数が魂ってなんかアツい!

確かにLispにはどっちも欠かせない気がする。

リストが心臓で関数が魂なら、マクロは一体なんだろう?

序文の最初に出て来る言葉は深い。

ググってみたけど中国のことわざ?元ネタが分からないです orz

はじめに

メモ

• 「この本の目的は、読者に計算の性質について考えることを教えることにある。」


• プログラミング言語は、計算の性質を伝える最も良い方法、数学と違い直接体験出来る


• プログラミングの実用的な世界への入門書ではないが、計算の性質を理解する出発点


• ガイドライン
  
  
  
  
  • 急いで読んではだめ。5回未満で読み切ろうとしないこと。(ちなみにScheme手習いには2回未満で読み切ろうとしないこと、と書いてる)
  
  
  • 飛ばして後ろから読んではだめ。少しずつ難しくなっていくので完全に理解してから進む。
  
  
  • 「読みながら例を試してほしい」
  
  
  • 「この本では形式的な定義はしない。読者が自分の定義を形式化し、覚えて理解するほうがよいと信じているからである」
  
  
  • しかし戒律はその先を読む前に知って理解しておくこと。
  
  
  • プログラミングのこつはデータおよび処理のパターンを認識すること。
  
  
  
  

感想

最後に「次のページで読者を待っている挑戦を楽しんでほしい。」と書いていた。なので、Scheme修行も楽しみながら読むぞ!

ガイドラインに書かれていたように、本にちりばめられたヒントから自分の定義を形式化し、覚え、理解したい。

ちりばめられたヒントを拾うためにも5回ぐらい読まないと気づかない点があるんだと思う。

計算の性質について考えれば、一生プログラマで食べていくこと、出来るかな?

Yコンビネータを理解したい

Scheme手習いの9章にYコンビネータが出てきます。

Y combinator - /var/log/messages

を読んで、もう一度しっかり取り組んでみようかと思いました。

前回読んだときの感想で最後に「すっきり」と書いておきながら再度9章読むとやっぱり理解出来てなかったかも。

頑張って「λ計算入門」でググって基礎文法最速マスターを読んだり、どこかの大学の講義のpdfな資料を読んだり、Yコンビネータでググって資料を読んだり。(本はScheme手習い以外読んでないです*^q^*

少しだけ分かった気がするのでエントリにまとめておきます。

Yに渡す関数

リストの長さを求める関数、とりあえずFとでも名付けましょう。

(define F
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (+ 1 (length (cdr l))))))))

Fは長さを計算する関数lengthを取り関数を返す。

listを取って空なら0を、それ以外の場合lのcdrの長さをlengthで求めそれに1を加えて返す関数。

Yコンビネータ

(define Y
(lambda (le)
((lambda (f) (f f))
(lambda (f)
(le (lambda (x) ((f f) x)))))))

中身の2つの関数、別々に見てみる。

最初の関数

(lambda (f) (f f))

関数fを引数に取り、fにfを適用する。(この時点でちょっと???な感じww)

2番目の関数B

(lambda (f)
(le (lambda (x) ((f f) x))))

引数で直接(le (f f))という風に渡すと、先に引数を評価してからleを呼び出すので、leを呼び出す前に(f f)の部分で延々と再帰します。

なのでlambdaで包んで評価を遅らせてますね(p173)

FにYを適用するとどうなるのか

とりあえずScheme手習いで出て来るYコンビネータをFに適用する

(Y F)

Yの定義のlambdaに置き換え。

((lambda (le)
((lambda (f) (f f))
(lambda (f)
(le (lambda (x) ((f f) x))))))
F)

leの部分をFで置き換えてこんな感じになる。

((lambda (f) (f f))
(lambda (f)
(F (lambda (x) ((f f) x)))))

fの部分を置き換えて

((lambda (f)
(F (lambda (x) ((f f) x))))
(lambda (f)
(F (lambda (x) ((f f) x)))))

こうなる。

よく見るYコンビネータの中身と同じになりましたね。

で、こうなると、(lambda (f) ...)で取っているのは自分自身

Fに渡す無名関数

(lambda (x) ((f f) x))

の中で使われてるfは

(lambda (f)
(F (lambda (x) ((f f) x))))

に束縛されてるのかな。

無名関数にFを適用する

さて、帰って来る(F (lambda (x) ((f f) x)))のFを置き換えてみると

((lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (+ 1 (length (cdr l)))))))
(lambda (x) ((f f) x)))

lengthを引数で置き換えて

(lambda (l)
(cond ((null? l) 0)
(else (+ 1 ((lambda (x) ((f f) x)) (cdr l))))))

こんな関数が帰って来る、と。これがlengthか。

その関数に'()を与えると、0を。そうでない場合に+1して

((lambda (x) ((f f) x)) (cdr l))

が呼び出されています。

(f f)が何をしてるか

このfには

(lambda (f)
(F (lambda (x) ((f f) x))))

が入っています。なのでこれにfを与える、つまり

((lambda (f)
(F (lambda (x) ((f f) x))))
(lambda (f)
(F (lambda (x) ((f f) x)))))

となる。

で、これさっき見たよね。

(f f)を呼び出すだけで再帰が出来とる!!w

YじゃなくてZコンビネータらしい

(lambda (x) ((f f) x))

でlambdaでくるんでるのは(f f)が引数の方が先に評価されてしまうから。評価順序云々が絡んでるみたいです。先行評価。

で、実はλで遅延させてるのはZコンビネータらしい。

普通のYコンビネータはこう。

λf.(λx.f(xx))(λx.f(xx))

Zはこう。

λf.(λx.f(λy.xxy))(λx.f(λy.xxy))

Zの一部をη変換するとYと同じになる、という理解。

Yコンビネータの話

Y = λf.(λx.f(xx))(λx.f(xx))

MにYを適用してみると

YM = λf.(λx.f(xx))(λx.f(xx))M
= (λx.M(xx))(λx.M(xx))
= M(λx.M(xx)(λx.M(xx)))

最終的にこんな形に。3行目の引数が2行目と同じになるので

YM=M(YM)

Zだと

Z = λf.(λx.f(λy.xxy))(λx.f(λy.xxy))
ZM = (λf.(λx.f(λy.xxy))(λx.f(λy.xxy)))M
= (λx.M(λy.xxy))(λx.M(λy.xxy))
= M(λy.(λx.M(λy.xxy))(λx.M(λy.xxy))y)

Mの引数で渡してるのはλ、ここで1回評価を遅らせてる感じなのだろうか

最後の形の引数をη変換すると

(λx.M(λy.xxy))(λx.M(λy.xxy))

となって、ZMを簡約してる途中で出てきたのと同じ形になる

つまり、M(ZM) = ZM

ってことなのかな

(Y Y)はどうなるの

YFするとF(YF)が帰って来る。ここでFの場合はYFをlengthとして受け取った後に、(lambda (l) …)な関数を戻しているのでそこで計算が止まる。

YYするとY(YY)が帰って来る。Y(YY)はYYを返す。でYYはY(YY)を返す。でYYは…と無限ループする。

という理解でいいのかな。

「リストの内容比較」を解いてみる

お題：リストの内容比較 - No Programming, No Lifeを解いてみた。

なんか思ったよりすっきり書けませんでした orz

「ランダム文字列」をGaucheで解いてみる

お題：ランダム文字列 - No Programming, No Lifeを書いてみる。

すっきり。#[\w]は文字集合、\wは単語を構成する文字の集合でa-zA-Z_。#[a-zA-Z0-9_]でもいいかな。

char-set->stringで文字集合を文字列に変換するためにsrfi-14

文字列をshuffleでシャッフルするのにgauche.sequence

16文字抜き打すのにsrfi-13のstring-takeを使っています。

追記

さっき

(use gauche.sequence)
(use srfi-13)
(use srfi-14)
(string-take (shuffle (char-set->string #[a-zA-Z0-9_])) 16)

こんなの書いてましたが誤りです。これだと同じ文字が2連続しない。ランダムではない。恥ずかしい。

これでどうだ!

(use gauche.sequence)
(use srfi-14)
(use srfi-42)
(string-ec (: i 16) (~ (shuffle (char-set->string #[a-zA-Z0-9_])) 0))

また追記

実行時間をはかろうとしてtimeしたら

gosh> (time (length '(1 2 3)))
 ERROR: failed to link /usr/local/Cellar/gauche/0.9.2/lib/gauche-0.9/0.9.2/i386-apple-darwin11.0.1/gauche--auxsys.so dynamically: dlopen(/usr/local/Cellar/gauche/0.9.2/lib/gauche-0.9/0.9.2/i386-apple-darwin11.0.1/gauche--auxsys.so, 10): Symbol not found: _environ
Referenced from: /usr/local/Cellar/gauche/0.9.2/lib/gauche-0.9/0.9.2/i386-apple-darwin11.0.1/gauche--auxsys.so
Expected in: flat namespace
in /usr/local/Cellar/gauche/0.9.2/lib/gauche-0.9/0.9.2/i386-apple-darwin11.0.1/gauche--auxsys.so
Stack Trace:
_______________________________________
0  (sys-times)
[unknown location]

こんな表示が。

後でググろう…

さっきのだと遅いかな、と思って書き直してみた

実行時間をはかる。

前のをちょっと変えたのをa.scmと今のをb.scmに書いて実行する

前の

a.scm

(use gauche.sequence)
(use srfi-14)
(use srfi-42)
(dotimes (n 1000)
(let ((src (char-set->string #[a-zA-Z0-9_])))
(string-ec (: i 16) (~ (shuffle src) 0))))

$ time gosh a.scm

real	0m1.475s
user	0m1.463s
sys	0m0.010s

今の

b.scm

(use srfi-14)
(use srfi-27)
(use srfi-42)
(dotimes (n 1000)
(let* ((src (char-set->string #[a-zA-Z0-9_]))
(src-len (string-length src)))
(string-ec (: i 16) (~ src  (random-integer src-len)))))

$ time gosh b.scm

real	0m0.105s
user	0m0.098s
sys	0m0.006s

もっといい方法があるに違いない。

「文字列を先頭から見て同じところまで除去」をGaucheで解いてみた

お題：文字列を先頭から見て同じところまで除去 - No Programming, No Life

をGaucheで解いてみた。多分0.9じゃないと動かないです。

とりあえずこんな感じです
(use srfi-13)
(define (q . los)
(map (^s (string-drop s (apply min (map (^s (string-prefix-length (car los) s)) los)))) los))

2011-08-14 00:22:07 via YoruFukurou

つぶやける長さになった!



学校卒業するまでの間はSchemeいっぱい書いて生きたい。

追記

あまりにも説明なさ過ぎな気がしたのでちょっとだけ説明も書いてみる。

後述するstring-prefix-lengthっていう便利な関数を使うため(use srfi-13)でSchemeのライブラリsrfi-13を読み込む。

(define (q . los) ～)のように書くとqに渡された引数が全て入ったリストがlosに束縛される。

qの中身を内側から見て行く。

srfi-13に用意されているstring-prefix-lengthを使うと2つの文字列の先頭から見て同じとこまでの長さが得られる。

(map (^s (string-prefix-length (first los) s)) los)

(^s ～)は(lambda (s) ～)のシンタックスシュガー、Gaucheの機能。

mapを使ってlosの全ての文字列sとlosの最初の文字列、2つの文字列の「先頭から見て同じとこまでの長さ」のリストを得る。

(apply min ～)でもっとも短い「先頭から見て同じとこまでの長さ」を取り出す。

そしてstring-dropでlosの全ての文字列sから、もっとも短い「先頭から見て同じとこまでの長さ」の分の文字を取り除く。

そんな流れです。

自分の理解を助けるためにも、もう一度さっくりまとめると

• 2つの文字列の「先頭から見て同じとこまでの長さ」を返す便利な関数、string-prefix-lengthがsrfi-13で定義されてるのでそれを使う。


• 関数に渡された全ての引数(文字列)をリストとして受け取る


• 全ての文字列と最初に渡された文字列との「先頭から見て同じとこまでの長さ」を求める


• 一番短い「先頭から見て同じとこまでの長さ」まで文字を取り除いた文字列を返す。

以上です。まじめに書こうとすると日本語難しい。

追記

何も考えず別解。



引数の中に空文字列か、先頭の1文字が他のと同じでない文字列があったら引数をそのまま返す。

それ以外の場合は引数の文字列を先頭から1文字取り除いて再帰

再帰! 再帰!

Scheme修行を読む。

Scheme手習いについて

Scheme手習いを読み終わりました。

Scheme手習い

• 作者: Daniel P. Friedman,Matthias Felleisen,元吉文男,横山晶一



• 出版社/メーカー: オーム社



• 発売日: 2010/10/22


• メディア: 単行本（ソフトカバー）


• 購入: 5人 クリック: 101回


• この商品を含むブログ (27件) を見る

本読んで内容を書いてhanachin/TheLittleSchemer ? GitHubにアップしてブログを書いてid:yamanetoshiさんに読んだエントリ投入のお知らせを書いて、疑問点等補足してもらって…という感じで読み進めました。

エントリあげる間隔はちょっとゆっくり目でしたが orz

ひとまず一冊読み終える事が出来て嬉しいです。

Scheme手習いの冒頭には2度以下で読むなと書いてあったので今度は同級生の方ともう一度読んでみようかと思ってます。

Scheme修行について

続編のScheme修行も購入しました。

Scheme修行

• 作者: Daniel P. Friedman and Matthias Felleisen,元吉文男,横山晶一



• 出版社/メーカー: オーム社



• 発売日: 2011/06/15


• メディア: 単行本（ソフトカバー）


• 購入: 3人 クリック: 33回


• この商品を含むブログ (8件) を見る

以前から手元にあって、手習いを読み終わったら読もうと思ってわくわくしていた本です。

手習いを読み終わった翌日、もう我慢出来なくなってしまって早速読書用のリポジトリhanachin/TheSeasonedSchemer ? GitHubを建ててマクドナルドに居座り一気に1章読んでしまいましたw

前回の書き方

前回は質問に対応したテストを読みながら書いていって、その質問の答えを定義して、テストが通るか確認して、というTDD的な流れで進めました。

テストケースのファイルを章ごとに1.scm、2.scm、3.scm...と作っていって、テスト用のマクロをtest-util.scmで少しだけ定義してテストケース冒頭で読み込み、本に出て来る関数の定義は全部func.scmの1ファイルに書いて、という感じの構成にしてみましたが最終的にfunc.scmが985行になりました。

全部1つに定義しちゃうと1章ごとにやった内容を確認しづらいし区切りがつけづらいかな、と思ったり。

あとコミットメッセージも謎の英語でぱっと見分からなかったような orz

今回はどうしよう

テストケースを書いてから答えを書く姿勢はそのままで行こうと思います。

テストケースになりそうな質問を本文から全て拾ってから答えを考え読み進めるようにします。

ファイルの構成は、前回func.scmが大きくなったのをふまえ、それぞれの章で使う関数の定義や質問の答えを11.scm、12.scm、13.scm...という風に1章1ファイルで書いていこうかと。

よく重複して定義してしまう関数は別途切り出したり、前章で定義した関数を使う際はloadで前章を読み込もうかと。

テストケースはtest11.scm、test12.scm、test13.scm...のようにtestを頭につけて1章1ファイルずつ作っていきます。

加えてnotes.orgにメモを取って、それもgitで管理する事にします。

後、コミットメッセージを日本語でちゃんと書くようにしてみます。

目標

前回、1章読む間隔が結構あいてしまったので1週間に1章は読むようにして、3ヶ月以内に読了していけるように頑張りたいです。

Scheme手習いだと2回以下で読み切るな、だったのがScheme修行だと5回以下で読み切るな、となってるので前回以上に読み込まなければならないですね…

楽しんで読めると嬉しいな。1章読んだエントリは後ほどあげます。

Scheme手習い Chapter 10

ついに10章まで来てしまった。この章で最後。手習いを終えたら修行が待っている。

いつも通り読みながらの気づき等

読みながらのメモ

• エントリ(entry)とは(集合のリスト ←と同じ長さの値のリスト)のペア


• (new-entry setl l)でエントリを作れる


• lookup-in-entryはnameとentryとentry-fを取る
  
  
  
  
  • entryの名前の集合からnameを探して対応する値を返す
  
  
  • entryの中でnameが見つから無かった時はentry-fにnameを渡して呼び出す
  
  
  • entryをnamesとvaluesに分解して、lookup-in-entry-helpを呼んでいる
  
  
  
  


• テーブル(table)はエントリ(entry)のリスト
  
  
  
  
  • 環境ともいう
  
  
  
  


• extend-tableはエントリを古いテーブルの先頭に付け加え、新しいテーブルを作る


• lookup-in-tableはnameとtableとtable-fを取る
  
  
  
  
  • テーブルの中の先頭のエントリから順にnameの値を探して対応する値を返す
  
  
  • tableの中でnameが見つから無かった時はtable-fにnameを渡して呼び出す
  
  
  • tableから先頭のエントリを取り出してlookup-in-entryを呼んでいる
  
  
  • 先頭のエントリの中でnameが見つからなかった時に次のエントリを探せるように、entry-fにtableへの参照を持ったクロージャを渡している
  
  
  
  


• 式(Expression)
  
  
  
  
  • eはexpressionの略
  
  
  • タイプが6つある
  
  
  • *const
  
  
  • *quote
  
  
  • *identifier
  
  
  • *lambda
  
  
  • *cond
  
  
  • *application
  
  
  • タイプを関数、actionとして表現する
  
  
  • 8章のatom-to-functionのようにexpression-to-actionを定義
  
  
  • atomならatom-to-action
  
  
  • listならlist-to-action
    
    
    
    
    • carを見て判断
    
    
    
    
  
  
  
  


• expression-to-actionがきちんと動作するならvalueとmeaningを定義出来る


• valueはSchemeのevalと同じ。引数で式を取る
  
  
  
  
  • meaningに式と空の環境を渡して呼び出す
  
  
  
  


• meaningは式と環境を引数に取る
  
  
  
  
  • expression-to-actionでタイプの表現、関数を取り出す
  
  
  • 式と環境を渡しその関数を呼び出す
  
  
  
  


• タイプを表現するアクション達


• 非基本関数と基本関数
  
  
  
  
  • 基本関数は何をするものか知っている関数
  
  
  • 非基本関数は引数と関数本体によって定義される関数
  
  
  • 仮引数と関数本体を覚えておく必要がある。
  
  
  • (lambda (x) x)でいうcdrの((x) x)の部分
  
  
  • それに加えテーブルを覚えておく。
  
  
  • この3つでクロージャレコード
  
  
  
  


• evcon
  
  
  
  
  • null?の質問がないまま再帰しているのでquestion-ofが真になるlineが無かったらエラーが出るため、少なくとも1つの質問は真である必要がある。
  
  
  
  


• evlis
  
  
  
  
  • listの全ての意味をmeaningで求めて新しいlistにして返す、のかな
  
  
  
  


• apply
  
  
  
  
  • primitiveかそうでないか、でapply-primitiveとapply-closureに処理を振り分けてる。
  
  
  
  

気づき疑問等

• extend-tableで新しいエントリを先頭につけるのは、carを使って先頭から探るため?


• p183のadd1?sub1?はadd1、sub1の間違い?


• *identifierの中のinitial-tableは…


• evconはeval-condの略?


• evlisはeval-list?


• :atom?をatom?だと思っててハマった orz


• あと:atom?がキーワードとして認識されちゃったのでmy-atom?に変更


• ページの順番通りに*applicationを定義した後applyを定義してハマった。
  
  
  
  
  • 最初に*applicationを定義する時、中でapplyを使ってる
  
  
  • 自前applyを定義する前に*applicationを定義するとGaucheに元からあるapplyを見ちゃう
  
  
  • 自前applyを定義するのを*applicationの前にもってきて解決
  
  
  
  


• defineが出てきてないのに「再帰はYコンビネータによって得られるので、必要はありません。」という答え方は素敵だと思った
  
  
  
  
  • 全部lambdaで書けばdefine使わなくてok的な
  
  
  • でも「Scheme修行も見てください。」とのこと。
  
  
  
  


• 「Yコンビネータによる変形を行うとインタプリタ上でインタプリタを走らせる事が可能である」
  
  
  
  
  • 前の章で出てきたYコンビネータがしっかりとインタプリタで動く事を確認してちょっと感動。動きを追ってみたい。
  
  
  • loopはYコンビネータで出来るし、evalは今作った。後はreadとprintだけ用意してやればREPLが出来る!?
  
  
  
  

感想

最後の章でもapplyのところで処理を分けたり、table関連でうまく抽象化しててすごく分かりやすい。

lookup-in-tableの中でlookup-in-entryに渡すentry-fのクロージャ(cdr table)の部分が好き。

(lambda (name)
(lookup-in-table name (cdr table) table-f))

この10章だけでも何回も読めそう。

冒頭にある読者へのガイドラインでは

急いでこの本を読まないでほしい。注意深く読むこと。有益なヒントがテキスト全体にちりばめてある。この本を2回以下で読み切ろうとしないこと。系統的に読むこと。ある章が完全には理解できなければ、次の章はもっと理解できなくなる。質問はだんだん難しくなるように並べてある。前の方が解けないと、後ろのほうはもっと難しい。

と書いてあるけど、もう一周読んでみても楽しめそうです。

前半部分は何度も読んでるけど8, 9, 10とそこらへんは理解度足りてない感じもするのでもうちょい読み込む予定…

最初にエントリをあげたのが2011年4月14日で、今は8月10だから大体4ヶ月ほど。

特にYコンビネータのところでコミットの感覚が20日以上あいてるのでそこが一番難しかったような。

前の方から後ろに行けばいくほど楽しかったです。

Scheme手習い Chapter 9

気付き感想等

• 全関数と部分関数
  
  
  
  
  • keep-lookingはlatの一部分に対して再帰しているのではない
    
    
    
    
    • 不自然な再帰
    
    
    • 部分関数
    
    
    • これまでに見てきた関数は全関数
    
    
    
    
  
  
  
  


• ゴールに到達しない関数でもっと短いもの
  
  
  
  
  • (define eternity (lambda (x) (eternity x)))
  
  
  • いつまでたっても終わらない、最も不自然な再帰で、最も部分的な関数
  
  
  
  


• alignは第7の戒律に違反している
  
  
  
  
  • 第2の質問(a-pair? (first para))の後、alignに(shift para)の値を渡している。
  
  
  • 第7の戒律
  
  
  
  

「性質を同じくするすべての構成部分について再帰すべし。すなわち、
*リストのすべての部分リストについて
*算術式のすべての部分式について」

• 前の章から題材になってるものが何かしっかり分かってない orz
  
  
  
  
  • 集合・部分関数・全関数…
  
  
  
  


• p157のCはコラッツの問題 - Wikipedia
  
  
  
  
  • 全関数であるかどうかはだれもしらないらしい。
  
  
  
  


• p158のAはアッカーマン関数 - Wikipedia


• p162で停止性問題 - Wikipedia

Yコンビネータ

9章の最後に来てYコンビネータ。

手順を追って書いていく。

;; defineがなかったらlengthは定義出来るか?

;; 空リストの長さを決めるが他に何も決めない。
;; 名前を付けるとしたらlength0
(lambda (l)
(cond ((null? l) 0)
(else (add1 (eternity (cdr l))))))

;; 要素が1以下のリストの長さを決めるlength<=1はこんな感じ
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length0 (cdr l))))))

;; length0の名前を付けられない。
;; length<=1の中のlength0の部分をlength0の定義で置き換え
(lambda (l)
(cond ((null? l) 0)
(else (add1 ((lambda (l)
(cond ((null? l) 0)
(else (add1 (eternity (cdr l))))))
(cdr l))))))

;; もしもlength<=3、length<=4、length<=5のような形で無限の関数を書ければlength∞が書ける。
;; それは無理なのでパターンを探す。
;; lengthに似た関数があるので、それを抽象化する。
;; length0を作る関数を書く
((lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cdr l)))))))
eternity)

;; 同じようにlength<=1
((lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cdr l)))))))
((lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cdr l)))))))
eternity))

;; length<=2
((lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cdr l)))))))
((lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cdr l)))))))
((lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cdr l)))))))
eternity)))

;; まだ繰り返しがある。lengthに似た関数を返す関数に名前をつける。
;; length0
((lambda (mk-length)
(mk-length eternity))
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cdr l))))))))

;; length<=1
((lambda (mk-length)
(mk-length (mk-length eternity)))
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cdr l))))))))

;; length<=2
((lambda (mk-length)
(mk-length (mk-length (mk-length eternity))))
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cdr l))))))))

;; 再帰とは無限にmk-lengthの適用が続いてるようなもの
;; eternityを渡さないでも誰も気にしない。
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (mk-length (cdr l))))))))

;; lengthと似た関数を作る関数を1回適用するとlength<=1が出来る。
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 ((mk-length eternity) (cdr l))))))))

;; mk-length自身を渡す事で再帰が出来る(!)
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 ((mk-length mk-length) (cdr l))))))))

;; mk-lengthの部分を取り出して、それにlengthという名前を付ける事が出来る。
;; だけど引数に(mk-length mk-length)を渡すと引数を評価してるとこで再帰する。
;; なのでlambdaで包んで評価しないようにしてみる。
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cdr l)))))))
(lambda (x)
((mk-length mk-length) x)))))

;; 後はlengthの部分だけを取り出す
((lambda (le)
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(le
(lambda (x)
((mk-length mk-length) x))))))
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (add1 (length (cdr l))))))))

;; このlengthを生成してる関数はYコンビネータというらしい。
(define Y
(lambda (le)
((lambda (f)
(f f))
(lambda (f)
(le (lambda (x) ((f f) x)))))))

すっきり。

evens-only*&co

ちょっと時間があったのでダラダラと書いてみたのをgistにあげてみました。

Scheme手習い Chapter 8

さて、いよいよ後半になって難しくなってきた。

8章ではカリー化、収集子(継続とも呼ばれる)、収集子を渡すスタイルの関数の書き方。

第10の掟「同時に2つ以上の値を集める際には関数を作るべし。」が出てきた。

自分なりまとめ

• 関数はリストとアトムを返せる
  
  
  
  
  • 関数自身を返す事も出来る
    
    
    
    
    • これは関数が第一級オブジェクトだから?
    
    
    • 第一級ってどんな事かっていうと
      
      
      
      
      • 関数を引数にとれる
      
      
      • 関数を変数に代入出来る
      
      
      • 関数に名前をつける必要がない
      
      
      
      
    
    
    • よく聞く関数が第一級市民というのはWikipedia見ると『この言葉は1960年代にChristopher Stracheyによって「functions as first-class citizens」という文脈で初めて使われた。』らしいのでそれから来てるのかな。
    
    
    
    
  
  
  
  


• カリー化
  
  
  
  
  • 『カリー化 (currying) とは、計算機科学分野の技法の一つ。複数の引数をとる関数を、引数が「もとの関数の最初の引数」で戻り値が「もとの関数の残りの引数を取り結果を返す関数」であるような関数にすること。』(Wikipediaより)
  
  
  
  

気付きとか

• func.scmが700行越えてきて見通し悪い
  
  
  
  
  • なんか前もこんな事書いた気がする
    
    
    
    
    • 1章1ファイルにまとめるとすっきりしそう
    
    
    • テストも1つのファイルにまとめられたりするかな?
    
    
    
    
  
  
  
  


• insertR-fとinsertL-fの内側のlambdaの引数の名前
  
  
  
  
  • insertRやinsertLのときは(new old lat)だったのが(new old l)になってる。
  
  
  • コピペでinsertR-fとinsertL-fを作ったのでlatのままにしてたのに気付き、後から修正 orz
  
  
  • test?を取るのでlat以外の構造も比較出来る。だからlatじゃなくてl、なのかな?
  
  
  • 引数の名前付けって大事っすね…
  
  
  • でもinsert-gだとeq?で比較してるのにlだ。latじゃないのかな…謎。
  
  
  
  


• 前に定義した関数を定義しなおした時ってテストどうしよ
  
  
  
  
  • とりあえず1.scmから順番に全部通るのを確認してみてる
  
  
  
  


• こないだ作ったf-testマクロの都合で関数を返す関数のテストが出来ないかも


• 無名関数を渡すようにすると覚えておく名前が少なくてすむ(p135)便利!


• 関数を取って関数を返す関数は怖くない!


• multirember&coみたいに、名前に&がつくのには、最後に?がつくのは述語!のように決まりがあるのだろうか


• 継続渡しスタイル面白い!


• even?の定義
  
  
  
  
  • 自分で作ったo+ o* o/を使わずにSchemeに元からある+ * /を使って定義すると奇数でも#tになるので注意。
  
  
  
  


• p148のevens-only*&coの結果は間違ってるらしい
  
  
  
  
  • http://wiki.fdiary.net/LittleSchemerJa/?Errata
  
  
  • テストケースを修正。
  
  
  
  


• evens-only*&coは一応書けた。やっぱり一番最後の収集子が難しい。
  
  
  
  
  • 一応かけたけど何をしてるかって聞かれるとまだ説明しづらい。
  
  
  
  

感想

収集子面白い!

lambdaでくるんで渡して後続の計算から呼び出されるところとか

クロージャで前の計算の値を保持してるとことか

Scheme手習い Chapter 7

気付きとか

• 集合の例として出ているものについて(p.113)
  
  
  
  
  • (apple peaches apple plum)や(apples peaches pears plums)などリストの中の要素に複数形のものがある。
  
  
  • set?がどんな関数か考えさせるために複数形の名詞を入れてるのかなぁ(複数形の名詞だからといってsetなわけではないみたいな)
  
  
  
  


• eq?をequal?使って書き直したっけ?
  
  
  
  
  • p.113とp.115でmember?とかmultirember?の定義をequal?使って書き直したって記述があるんだけど記憶になかった orz
  
  
  
  


• makesetのテストケースについて
  
  
  
  
  • 最初のmakesetの定義だと結果はp.114の最初の質問の答え(apple peach pear plum lemon)と同じ結果にならない。
  
  
  • 最初のmakesetの定義だと結果はp.114の最後の質問の答え(pear plum apple lemon peach)になる。
  
  
  • 第2のmakesetの定義だとその逆で、最初の質問の答えになるが、最後の質問の答えと同じ結果にならない。
  
  
  • とりあえず最後の定義で通るように修正。
  
  
  
  


• subset?の2つ目の質問でandと5の間にスペースがあいてないのは間違いかな? (p.115)


• intersect?の定義のところで、最初の質問の答えが#fじゃなくてnilになってるのが所々ある。間違い?


• p120のfirst, secondの定義では引数がp(pair)、p121のthirdの定義だとl(list)。引数の名前付けも中身に対応してて分かりやすい。


• 集合とか、そこらへんの数学出てくるとお手上げ。
  
  
  
  
  • 情報数学入門でも読むか… orz
  
  
  
  


• fullfun?を、最初

(define fullfun?
(lambda (fun)
(and (set? (firsts fun))
(set? (seconds fun)))))

と書いたんだけど、funが渡されてくる前提があるから最初の質問はいらなかった。

感想

• 前に定義した関数を使って簡潔に書ける
  
  
  
  
  • makesetでmultirember
  
  
  • eqset?の中のsubset?
  
  
  • intersectallの中でintersect
  
  
  
  


• 表現から部分を取り出す補助関数first, second, buildを使ってすっきり書ける
  
  
  
  
  • 前章でも表現から部分を取り出す補助関数を定義して抽象化してた。(1st-sub-exp, operatorなど)
    
    
    
    
    • 読み易くなって変更にも強い!
    
    
    
    
  
  
  • revrelで補助関数を使った定義と使わない定義を見比べると超違う
    
    
    
    
    • 使わないとき
    
    
    
    
  
  
  
  

(define revrel
(lambda (rel)
(cond ((null? rel) '())
(else (cons (cons (car (cdr (car rel)))
(cons (car (car rel))
'()))
(revrel (cdr rel)))))))

• build, first, second使うと

(define revrel
(lambda (rel)
(cond ((null? rel) '())
(else (cons (build (second (car rel))
(first (car rel)))
(revrel (cdr rel)))))))

• 更にrevpairを使うとすっきり

(define revrel
(lambda (rel)
(cond ((null? rel) '())
(else (cons (revpair (car rel))
(revrel (cdr rel)))))))

• fullfun?も
  
  
  
  
  • (set? (seconds fun))か(fun? (revrel fun))で。
  
  
  
  

なんというか一行文の補助関数がある/なしで大分読み易さが違うなって印象でした。

前章でも出てきた第8の戒律

表現から抽象化するに際し、補助関数を使用すべし。

はめっちゃ大事ですね。

今までの章で書いたのも補助関数を使うと読み易くなるのだろうか。

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を定義

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

感想

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

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

補助関数スゴいよぅ

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

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の省略形として書く事は出来る)がちょっと発想の転換な気がして面白かった。