kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

reasonedschemer

Reasoned Schemer (33) わり算

わり算も引き算と同様、関係プログラミング式のやり方は取れないので独自に実装 筆算式にやっています

Reasoned Schemer (32) かけ算

かけ算はすんなり

Reasoned Schemer (31) 引き算 続き

(Reasoned Schemerから少し離れてしまっている) でどっちでやろうか full-adderとかの方が自分にとって新しいのでそっちで書いてみよう 全部反対にするだけだろうし と思った私があさはかでした

Reasoned Schemer (30) 引き算

次は引き算ですがこれはそのままとはいきません 関係プログラミングだから足し算ができれば自動的に引き算もできてましたが(効率とかどうなのかな) 普通は引き算は引き算で書かないと 引き算を書くには、足し算と同じようなことを書く方法もありますが、 …

Reasoned Schemer (29) 普通に書いてみる

これって関係プログラミングで書いてて何がいいんだろう、ということで 普通に書いてみて、比較しようと思います まずは足し算まで

Reasoned Schemer (28) わり算 終わり

で、ふたつに分けたらわり算がどうなるというのか わり算短くなったなーと思ったら (defrel (/o n m q r) (conde ((== '() q) (== r n) (

Reasoned Schemer (28) わり算 続き

次はlの右側の0がなくなる例でやってみよう もう少し圧縮した書き方で s -> (splito '(0 0 1 0 1) '(1) l h) 4 -> (splito '(0 1 0 1) '() '() h), l=() 2 -> h=(1 0 1), l=() 6 -> (splito '(0 1 0 1) '() ^l h), l=(0 . ^l), (pos ^l) 2 -> h=(1 0 1), ^l=…

Reasoned Schemer (28) わり算 続き

splitoは数をふたつの部分に分けてくれるわけですが splitoは他にどんなことをしますか? splitoは関係ですから、下位ビットのlと上位ビットのhを結合してnを作ることができます。rの長さを使ってパディングビットを詰めます。 こういうの聞くと関係に名前を…

Reasoned Schemer (26) わり算 続き

三つ目のconde行は十分一般的に見えますが、なぜはじめの二つのconde行が必要なんですか? これでいいんじゃないの、って話 (defrel (/o n m q r) (fresh (mq) (

Reasoned Schemer (25) わり算 続き

で本文を読みすすめてみる n < m、n = m、n > m の3つの場合に分けている それならそういうことがわかりやすいように書くべきなんではないだろうか 素のSchemeで言えば (cond ((< n m) ...) ((= n m) ...) ((> n m) ...)) って書いてあれば一目瞭然なんだから

Reasoned Schemer (24) わり算

わり算 いきなり(run 4 (n m q r) (/o n m q r))の値はこれこれです、と見せておいて 定義は次のページなのはニクい演出?たまたま? ついクセで引き算を再帰的に繰り返すようなのを想像してページをめくりました

Reasoned Schemer (23) 数の比較

=loとほぼ同じ形で

Reasoned Schemer (21) かけ算続き

bound-*oが仕事をしないとたとえば(run 1 (n m) (>1o n) (>1o m) (*o n m '(1 1)))が値を返さない それはそうですね それはそういうものかと思ってた 終われるようにするんだ bound-*oが何をすれば終わる?失敗しても次のn、mで試すだけなのでは?

Reasoned Schemer (20) 足し算、引き算、整数

(defrel (+o n m k) (addero 0 n m k)) これは当然 (defrel (-o n m k) (+o m k n)) なるほどね 関係プログラミングっぽい! (defrel (lengtho l n) (conde ((nullo l) (== '() n)) ((fresh (d res) (cdro l d) (+o '(1) res n)) (lengtho d res)))) からの …

Reasoned Schemer (19) gen-addero

さてgen-addero ある意味こっちが本体? genは何のgenかな 特殊ケースを除いた残りだから、genericのgenだろうか (defrel (gen-addero b n m r) (fresh (a c d e x y z) (== `(,a . ,x) n) nの最下位ビットがa、上位ビットがx nは1以上でないと困るね

Reasoned Schemer (18) adderoまとめ

表にしてみた 行 b n m r overlap 計算 1 =0 =0 6(n=1 m=0) 8(n=2 m=0) (== n r) 2 =0 =0 >0 -- (== m r) 3 =1 =0 6(n=1 m=0) 8(n=2 m=0) (addero 0 n '(1) r) 4 =1 =0 >0 -- (addero 0 '(1) m r) 5 =1 =1 6(n=1 m=1) (full-addero b 1 1 a c) 6 =1 1 3 5 (g…

Reasoned Schemer (17) addero中身

はじめて読む人は114コマ目まで飛ばしていいよ でも読む やっぱり2回は読めってことだなPreface には書いてなかったけど 処理系まで理解してからもう一度読めばそりゃ間違いなく理解度は上がるもんな nとmを足した答えがr 下からの繰り上がりはb (defrel (ad…

Reasoned Schemer (16) addero

90 adderoの定義は104コマめにあります。 なぜ前方参照? しかもadderoややこしそう・・・ (run 3 (x y r) (addero 0 x y r))の値はなんですか。 ((_0 () _0) (() (_0 . _1) (_0 . _1)) ((1) (1) (0 1))) 値がそうなることは(順番を除けば)理解できる ((1)…

Reasoned Schemer (015) 自然数

自然数の表現 ビット(0、1)のリスト リストの先頭が20の位、末尾が最上位 表現は一意 最上位は0にならない 自然数0の表現は() 自然数をビットによる表現に変換する

Reasoned Schemer (015) ビット演算

7. A Bit Too Much bitです (defrel (bit-xoro x y r) (conde ((== 0 x) (== 0 y) (== 0 r)) ((== 0 x) (== 1 y) (== 1 r)) ((== 1 x) (== 0 y) (== 1 r)) ((== 1 x) (== 1 y) (== 0 r)))) これは単純 (defrel (bit-xoro x y r) (fresh (s t u) (bit-nando x…

Reasoned Schemer (014) nevero

こんどはいっそうシンプルに (defrel (nevero) (nevero)) #uは失敗するが、(nevero)は成功も失敗もしない (run 1 q (nevero)) → 値なし (run 1 q #u (nevero)) → () 1回目に#uで失敗するから (run 1 q (conde (#s) ((nevero)))) → (_0) 1回目に#sで成功する…

Reasoned Schemer (012) rembero続き

(a b e d _0)はy=eってことなんだろうけどやっぱり なんで右側のeが消えているのか 左のeが消える場合も右のeが消える場合もあって、ここでは右のeが消えてる、ってこと? ひとつずつ再帰を追っていけばわかるのかなあ (a b _0 d _1 e)に至ってはなぜ_0が消…

Reasoned Schemer (011) memo、rembero (わからん)

5. Members Only またわからんタイトルを (define (mem x l) (cond ((null? l) #f) ((equal? (car l) x) l) (#t (mem x (cdr l))))) memだからか安直な いやダブルミーニングが隠されてるかもしれないぞ気をつけろ

Reasoned Schemer (010) 戒律・法則・unwrap

いろんなパターンを試します (run 5 x (fresh (y) `(appendo `(cake & ice . ,y) '(d t) x))) の値は (() (_0) (_0 _1) (_0 _1 _2) (_0 _1 _2 _3)) run*だと帰ってこないパターンですね なのに (run* x (fresh (z) `(appendo '(cake & ice cream) `(d t . ,z…

Reasoned Schemer (009) appendoと翻訳(最終版)

4. Double Your Fun 何が2倍? (define (append l t) (cond ((null? l) t) (#t (cons (car l) (append (cdr l) t))))) lがプロパーなリストだと値を持たないけれども tはプロパーなリストでも値を持つ ということを気にしている?

Reasoned Schemer (008) member?とmembero

member?を翻訳して簡略化して試します 再帰をひとつずつたどっていったり 値を持たなかったり member?はプロパーなリストでないとエラーになりますが memberoは最後の要素が無視されるだけ Schemeの関数から翻訳していますがSchemeの関数と同じ結果を出すわ…

Reasoned Schemer (006) (Schemeからの)翻訳

nulloは見たまんま (defrel (nullo x) (== '() x)) なんだけどじーっと見てるとわからなくなってきたり これは#sとか#uとか返すやつ pairoもやることは見たまんまなんだけど定義にはconsoを使う (defrel (pairo p) (fresh (a d) (conso a d p))) Is pairo re…

Reasoned Schemer (005) caro、cdro、conso

2. Teaching Old Toys New Tricks Don't put new wine into old bottlesのもじりだったりするんだろうか あんまり関係ないかな そういうとこ気にしなきゃいけないとこが多そうで翻訳はちょっとたいへんそうだな SICPとかマジメなやつのほうがある意味楽そう …

Reasoned Schemer (004) conde

disj2の中にconj2が現れるパターンはよく出てくるので、conde式を導入する (run* (x y) (disj2 (conj2 (teacupo x) (teacupo x)) (conj2 (== #f x) (teacupo y)))) は (run* (x y) (conde ((teacupo x) (teacupo x)) ((== #f x) (teacupo y)))) と書ける

Reasoned Schemer (003) conj2、disj2、defrel

conj2はふたつのゴールが両方とも成功すれば成功する 2は引数がふたつってこと conjはたぶんconjunctionの略 連言てやつ andみたいなもの 定理証明手習いにも出てきた