「Scheme修行」献本頂きました！

「Scheme修行」は先だって出版された「Scheme手習い」の続編です。
これらは「The Little Schemer」「The Seasoned Schemer」という、Lisp/Schemeの入門書として知られる2冊の翻訳本です。

Scheme修行

posted with amazlet at 11.06.11

Daniel P. Friedman and Matthias Felleisen
オーム社
売り上げランキング: 66881

Amazon.co.jp で詳細を見る

目次

• Scheme修行｜Ohmsha

訳者まえがき
序文
はじめに

11章 おかえりなさい、ようこそショーへ
12章 避難しましょう
13章 ホップ、スキップ、ジャンプ1
14章 名前をつけましょう
15章 大人と子供の違い……
16章 位置について、セット、バン！
17章 我変わる、ゆえに我あり！
18章 我変わる、ゆえに我同じなり！
19章 宝石泥棒
20章 店には何がある？

後序
索引

すでに「Scheme手習い」を読んだ方はご存知でしょうが、実際はこれがS式で書いてあります（笑）

内容

• Twitter / @golden_lucky: 『Scheme修行』は、カバーの像が牙を生やしている ...

『Scheme修行』は、カバーの像が牙を生やしていることからわかるように、大人のSchemerを目指すための本。

• Twitter / @golden_lucky: 『Scheme手習い』が副作用のない安全な世界での話 ...

『Scheme手習い』が副作用のない安全な世界での話だとしたら、『Scheme修行』は代入やジャンプのような危険な世界でちゃんと生き抜く大人の態度を学ぶ話。

「Scheme修行」では、代入や継続について学びます。とくに継続（continuation）については、その強力さの一端に触れることになります。今後、継続の真の力を学ぶ上での足がかりになると思います。他にも「Scheme手習い」では出てこなかったif, let, letrecなどの基本的な要素についても学びます。もちろん「Scheme手習い」同様、さりげないやり取りにニヤニヤさせられます。


序盤は「Scheme手習い」で繰り返し繰り返し学んだ再帰の復習といったところでしょうか。ここでletrecが出てきます（letrecの登場シーンでフイタのは私だけじゃないはず）。この辺で出てくる「scramble」という手続きが印象に残っています。

• vallog: TSS scramble
• vallog: scramble (The Seasoned Schemer)

中盤で代入と継続についてじっくり学びます。かなりのページ数が割かれており、ここがメインだと言って良いと思います。letやifもここらで出てきます。ここで再度Y combinator（今回はY!も）出てきます。なぜこうもY combinatorの話が出てくるかというと、こういう話もあるようです。

• vallog: 「そのプロセスにおいて、Schemeを使うことに関する多くの勘を やしなうだろう。」

後半は、CPS(continuation passing style)や、Lispインタプリタの実装もあり、読み応えありです。「Scheme手習い」でも最終章でLispインタプリタを作りましたが、今回も作ります。もちろん今回学んだ継続や代入を取り入れたパワーアップしたインタプリタです。

「序文」と「後序」のGuy L. Steele Jr.の言葉も必見。

私は以前、The Little Schemer同様、原書を読んだのですが、やはり日本語で読む方がよく理解できて大変面白かったです。原書を読んだときには気づかなかったこともたくさんありました。

参考

• バベル案内

あなたはまたLispも知る必要がある。

The Little Schemer と The Seasoned Schemerの練習問題を自力ですべて解ければ十分だと思う。

本家っぽいページ（著者の一人 Matthias Felleisen のページ？）に追加のエクササイズがpsファイル（35ページくらい）で置いてあったりします。。

• The Little Schemer

最後に

なりましたが、初めて「献本」というものを頂きました。すごくうれしいです！
今回、オーム社の鹿野さん(@golden_luckyさん)から査読？レビュー？のお話を頂きました。
私は「The Little Schemer」「The Seasoned Schemer」が大好きなので、こういった機会を頂いたことがとてもうれしかったです。
このような機会を与えて頂いたことに感謝いたします。ありがとうございました。

関連

• vallog: おめでとうございます！「『Scheme手習い』（The Little Schemer, 4th edition）10月23日発売予定」

• The Little Schemer (リトル スキーマー) - 関心空間

MIT の教科書 "計算機プログラムの構造と解釈" (昔は構造と実行) を読む為の本だったそうである。

scramble (The Seasoned Schemer)

;; scranmble

;; (scramble '(1 1 1 3 4 2 1 1 9 2))
;;  -> (1 1 1 1 1 4 1 1 1 9)
;; (scramble '(1 2 3 4 5 6 7 8 9))
;;  -> (1 1 1 1 1 1 1 1 1)
;; (scramble '(1 2 3 1 2 3 4 1 8 2 10))
;;  -> (1 1 1 1 1 1 1 1 2 8 2)

となるような手続き scramble 。

これが複雑というかなんというか、わかりにくい。「何をしているか」がまずわかりにくく、それがわかっても「目的」がよくわからないのです。。それはともかく「できるだけ見やすく」「できるだけわかりやすく」できないものか、いくつか書いてみました。

取りあえず named-let による末尾再帰版。

(define (scramble tup)
  (define (pick ls n)
    (list-ref ls (- n 1)))
  (let rec ((ls tup)(rev '())(acc '()))
    (if (null? ls)
        (reverse acc)
        (let* ((head (car ls))
               (rev (cons (car ls) rev))
               (ret (cons (pick rev (car ls)) acc)))
          (rec (cdr ls) rev ret)))))


(scramble '(1 1 1 3 4 2 1 1 9 2))
;; -> (1 1 1 1 1 4 1 1 1 9)
(scramble '(1 2 3 4 5 6 7 8 9))
;; -> (1 1 1 1 1 1 1 1 1)
(scramble '(1 2 3 1 2 3 4 1 8 2 10))
;; -> (1 1 1 1 1 1 1 1 2 8 2)

次いで、gauche.collection から map-accum を用いた版。

(use gauche.collection)

(define (scramble tup)
  (receive (ret rev)
      (map-accum (^ (e acc)
                    (let1 rev (cons e acc)
                      (values (list-ref rev (- e 1)) rev)))
                 '() tup)
    ret))

(scramble '(1 1 1 3 4 2 1 1 9 2))
;; -> (1 1 1 1 1 4 1 1 1 9)
(scramble '(1 2 3 4 5 6 7 8 9))
;; -> (1 1 1 1 1 1 1 1 1)
(scramble '(1 2 3 1 2 3 4 1 8 2 10))
;; -> (1 1 1 1 1 1 1 1 2 8 2)

次いで、gauche.sequence から map-with-index を用いた版。わざわざ反転したリストを内部で作る必要はないだろうということで書いてみました。が、厳密にはエラーケースが異なりそうです。

(use gauche.sequence)

(define (scramble tup)
  (map-with-index (^ (idx e)
                     (list-ref tup (- idx (- e 1))))
                  tup))

(scramble '(1 1 1 3 4 2 1 1 9 2))
;; -> (1 1 1 1 1 4 1 1 1 9)
(scramble '(1 2 3 4 5 6 7 8 9))
;; -> (1 1 1 1 1 1 1 1 1)
(scramble '(1 2 3 1 2 3 4 1 8 2 10))
;; -> (1 1 1 1 1 1 1 1 2 8 2)

オリジナル（に近い版？）は以前書いています。

• vallog: TSS scramble
• vallog: TSS scramble
• vallog: TSS letting, scramble, fold2

syntax-rules: try

macroの方のPDFを一通り読み終えたので、continuationの方のPDFを読み始めました。

• (PDF)Advanced Scheme TechniquesSome Naughty Bits

英語の方は、ほとんどわかりません。The Seasoned SchemerやThe Little Schemer, 4th Editionは雰囲気と勢いで読みました。

• vallog: TSS rember1*, let/cc, try
• vallog: TSS rember1*, let/cc, try

The Seasoned Schemerに出てくる try のことを思い出しました。

Re: TSS rember1*

• vallog: TSS rember1*
• vallog: TSS rember1*, let/cc, try

もっとカッコよく書けないのかなーと思いながら。



いくつか書いていれば何か思いつくかなー、と思いましたが思いつきませんでした。わかりにくくなった気がします。

• How To Become A Hacker: TSS rember1*

しかし、ホント The Seasoned Schemer のコードときたら・・・。。

TSS beglis, box-all, evlis を末尾再帰へ

• vallog: Re:Re: 読んだ「The Seasoned Schemer」

末尾再帰へ書き直してみました。reverse が気になる。末尾再帰かどうか以前に大丈夫なのか？
相変わらず letrec 経由しないと named-let が書けない。

• vallog: TSS chapter 20 は Lisp on Lisp on Scheme だった・・・

Scheme で作った小さな Lisp 処理系に自身の定義を食わせて、Scheme の上で走る Lisp の上で走る Lisp を動かす、という趣旨だったようです。

Lisp on Lisp on Scheme は、もう良いや。放置。

追記

よく見たら beglis は初めから末尾再帰っぽい。

TSS chapter 20 は Lisp on Lisp on Scheme だった・・・

ちゃんと読めていませんでした・・・。掲題の通りでした。
Scheme で作った小さな Lisp 処理系に自身の定義を食わせて、Scheme の上で走る Lisp の上で走る Lisp を動かす、という趣旨だったようです。

どうりで if ではなく cond を使っているし、(let ((var init) ...) body ...) を使わずに ((lambda (var ...) body ...) init ...) だったわけなんですね・・・。

つまり、 (value '(value 1)) が動くようにするということだったようです。

Lisp 系の書籍は、このネタ多いなー（笑）LOL では「Lisp Moving Forth Moving Lisp」でした。

• vallog: 読んだ「The Seasoned Schemer」
• vallog: Re: 読んだ「The Seasoned Schemer」
• vallog: Re:Re: 読んだ「The Seasoned Schemer」

Re:Re: 読んだ「The Seasoned Schemer」

• vallog: 読んだ「The Seasoned Schemer」
• vallog: Re: 読んだ「The Seasoned Schemer」

紛らわしい気がしたので、define を def にしました。
あと、以下のようなマクロを書いてみました。

で、この小さなLisp処理系には、数値演算がadd1とsub1しかありません。add1 と sub1 は、それぞれインクリメントとデクリメントです。

四則演算できるように、小さなLisp処理系自身を使って +, -, *, / などを追加。こちらも紛らわしいので、プレフィックスにアンパサンド（なんでも良かったんですが）を付けました。

def と &-, &* を用いて、階乗（fact）も定義できました。

ちなみに、四則演算は The Little Schemer, 4th Edition の4章である「Numbers Games」を参考にしました。

追記

ソースはここ

• valvallow's TheSeasonedSchemer at master - GitHub

Re: 読んだ「The Seasoned Schemer」

• vallog: 読んだ「The Seasoned Schemer」

20章の小さな Lisp 処理系はよくわかりませんでした。動いているような動いていないような。

Schemeで Lisp 処理系を作るというテーマについては、特に The Seasoned Schemer にこだわる必要はないと思うので、放置します。気が向いたら、そのうちということで。

せっかくなので動くようにしてみました。ちなみに、The Little Schemer, 4th Edition の10章と同じく、value 手続きが eval 相当の手続きです。

動かしてみると、以下のような感じ。defineも使えます。

取りあえず動くようになった20章のコードは以下。


まだコード的に微妙なところも多いですけども。

追記

ソースはここ

• valvallow's TheSeasonedSchemer at master - GitHub

読んだ「The Seasoned Schemer」

一応 The Seasoned Schemer 読了ということで。

The Little Schemer はおもしろくて刺激的だったけど、The Seasoned Schemer は call/cc と letcc 以外は特におもしろくなかった。 最後の小さな Lisp 処理系はよくわからなかったので放置。less than a minute ago via twiclivalvallow
valvallow

call/cc, let/cc などの継続呼び出しについては分かり易かったし、おもしろかったです。
17, 18, 19 章は飛ばしました。20章の小さな Lisp 処理系はよくわかりませんでした。動いているような動いていないような。

• valvallow's TheSeasonedSchemer at master - GitHub

The Little Schemer, 4th Edition の10章で作るものと大きく違う点は、define がある点でしょうか。

• valvallow's TheLittleSchemer at master - GitHub

誰かちゃんと動くように作ってる人いないかなー、と探してみました。

• pkrumins's the-seasoned-schemer at master - GitHub

が、20章がありませんね・・・。

Schemeで Lisp 処理系を作るというテーマについては、特に The Seasoned Schemer にこだわる必要はないと思うので、放置します。気が向いたら、そのうちということで。

• The Little Schemer, 4th Edition
• The Seasoned Schemer

TSS TLS atom?

無駄に複雑に書き直した話。

The Little Schemer, 4th Edition と The Seasoned Schemer に出てくる、atom?手続き。


上が本の序文に記載されているもので、下が書き直したもの。

TSS define?

わりとどうでも良い話です。

10章（The Little Schemer, 4th Edition）では、defineのない小さなLisp処理系を作りました。

• vallog: defineないけど小さなSchemeもどきで再帰動いたよー

20章（The Seasoned Schemer）ではdefineのある小さなLisp処理系を作るようです。そこでリストの先頭が(quote define)であるかどうかを判定するdefine?という手続きを作るわけです。

上記のようなコードが記載されています。The Little Schemer, 4th Edition でも The Seasoned Schemerでも、このスタイルです。不恰好ですよね。そこで、もう少しどうにかならないものかと考えてみるわけです。

書いてはみるものの、微妙です。微妙なので取り合えずブログに書いとけ、と思うわけです。ただそれだけです。

追記

そうでしたよ。Common Lispなら、こんなどうでも良いこと気にもならんのですよね。

TSS length, Y!, Y-bang

The Seasoned Shcemer P.119からまたもやlengthを使ったY Combinatorが出てきます。The Little Schemerで出てきたY Combinatorと違うのは、どうやら副作用を使うところのようです。名前にも「！（bangと読むらしい）」がついています。

ここ、ちょっとよくわかりませんでした。再読が必要かもしれません。取り合えずコードは書いてみました。

member?, let/cc

こういうのもありかな。

TSS deep

The Seasoned Schemer 16章。

(deep 3)

; -> (((pizza)))

というような手続きを書け、とのこと。無理やり（？）fold-rightなんかで書いてみたり。

続きのdeepR, deepMなど。

TSS set!

The Seasoned Schemerの15章になって初めて出てきたset!。set!ってのはこういうのだよーという章。

また出てきたYコンビネータ。Y!。

また出てきました。今度はThe Seasoned Schemerに。The Little Schemerでも9章で出てきました。理解できなくて散々書きました。

• vallog: Y Combinator

Yコンビネータは、いろんなサイトや解説記事を読みましたが、結局The Little Schemerが一番わかりやすかったです。The Seasoned SchemerではY!が出てきます。「！」ということで、副作用ありです。side effectです。その名もY-bang。ワイバーンみたい。

• 副作用 (プログラム) - Wikipedia

The Little SchemerとThe Seasoned Schemer合わせて20章のうちで、初めて副作用が出てくるのが15章です。ここまで代入などを使わずにきて、急に使うことになるとさすがに気持ち悪く感じますね。

ちなみにY!が出てくるのは16章です。

Thunk you, Peter J. Landin.

だそうです。

• http://codepad.org/6J0R4UkO

(define Y! (lambda (L) (let ((h (lambda (l)(quote ())))) (set! h (L (lambda (arg)(h arg)))) h))) (define Y-bang (lambda (f) (letrec ((h (f (lambda (arg)(h arg))))) h)))

あれ、でも下のY-bangは副作用あるか？

そういえば、Yコンビネータはこれを見たときに、理解のきっかけになりました。

• http://codepad.org/8DOhaOBO

((lambda (f) (f f 10)) (lambda (f n) (cond ((< 0 n) (print "hello") (f f (- n 1))))))

• vallog: [scheme][2ch]10 times print "hello"

(begin a b ...)と(let () a b ...)は同じじゃない

• vallog: TSS leftmost, let/cc, named-let

コメントでご指摘頂いてました。ここに改めてメモとして残しておきます。

Scheme の begin には面白い特徴があります。

新しいスコープを作らないのです。

なるほど。知りませんでした。（「RnRS読め」ですよね）

例えば ↓ こんなコードでエラーが起こりません。

(begin (define a 1))

(display a)

ホンマや。

• http://codepad.org/BJNCWWp9

Scheme

(begin (define x 100)) (display x)

Output: 100

a はトップレベルで定義されたことになります。

記事中のコードは begin と let のどちらを使っても問題ないと思いますが、同等と考えていると不意につまづくこともあるかもしれません。

begin のこの性質はマクロを書くときに必要になることがあります。

まんまと(let () a b ...)で(begin a b ...)と同じことできるなら、begin要らなくね？などと思っちゃってました。勉強になりました。ありがとうございました！

追記

(let ((x 1))
  (define x 2)
  x)
2

(let ((x 1))
  (let ()
    (define x 2))
  x)
1

(let ((x 1))
  (begin
    (define x 2))
  x)
2

TSS rember1*, let/cc, try

rember1*はThe Seasoned Schemerに何度も出てくる練習問題です。

例えば

(rember1* 'meat '((pasta meat) pasta (noodles meat sauce) meat tomatoes))

; -> ((pasta) pasta  (noodles meat sauce) meat tomatoes)

というようなものです。

The Seasoned Schemerでは、一般的な再帰やlet/ccを使った例が出てきますが、いまいちです。いまいち、というかすごくわかりにくいです。

• vallog: TSS rember1*
• How To Become A Hacker: TSS rember1*

取り合えず、以下のコードが14章にでてくるlet/ccとtryを使った例です。

TSS leftmost, let/cc, named-let

let のこんな使い方は驚きました。begin とか progn と同等と考えて良さそうですね。
(let () a b . . .)

• vallog: (begin a b ...)と(let () a b ...)は同じじゃない

コードの方↓は、なんともゴチャゴチャしてしている。

ところで明日は 9LISP。

TSS letting, scramble, fold2

11章に出てきたscrambleをlettingするエクササイズらしい。
foldでは書けないよなー、と思い探してみるとfold2なるものがgauche.collectionにありました。

• Gauche ユーザリファレンス: 9.3 gauche.collection - コレクションフレームワーク

reverse格好悪い・・・。

追記

• vallog: scramble (The Seasoned Schemer)