Occur で C-c C-f でびっくり！

この機能知らなかったとか恥ずかしくて書きづらいんですが，まあ，メモっときます．docstring によれば，

Minor mode for compilation, occur and diff modes.
When turned on, cursor motion in the compilation, grep, occur or diff
buffer causes automatic display of the corresponding source code
location.

とのことなので，compilation, occur, diff, grep で同様のことが出来ます．

λ

Chapter 2 Building Abstractions with Data

2.1 Introduction to Data Abstraction

2.1.1 Example: Arithmetic Operations for Rational Numbers

データを抽象化させるとかそんな感じ．例では，二つの整数 n, d の対（pairs）をデータ（structure）として扱い，constructor として make-rat を，selector として numer, denom を定義している．

2.1.2 Abstraction Barriers

abstraction barriers は抽象化の度合い（レベル）のようなもの．
Q. 何故，データを抽象化させるんですか？
A. This simple idea has many advantages. One advantage is that it makes programs much easier to maintain and to modify.

2.1.3 What Is Meant by Data?

うーん，message passing の重要性がまだよく掴めていない．

Exercise 2.6.

Church numerals．これは，ラムダ計算のなかで扱われる項目．wikipedia の当該項目を読んでみても案の定さっぱりなので，ヒントを参考にやってみる．
(Hint: Use substitution to evaluate (add-1 zero)).
以下，ラムダ計算の気分を味わうために，lambda をλと表記することにします．

(define zero (λ (f) (λ (x) x)))

(define add-1
  (λ (n) (λ (f) (λ (x) (f ((n f) x))))))

(add-1 zero)
;; add-1 を展開する．
-> ((λ (n) (λ (f) (λ (x) (f ((n f) x))))) zero)
;; zero を展開する．
-> ((λ (n) (λ (f) (λ (x) (f ((n f) x))))) (λ (f) (λ (x) x)))
;; 展開された add-1 が評価され，引数 n として，展開された zero を受け取る．
-> (λ (f) (λ (x) (f (((λ (f) (λ (x) x)) f) x))))
;; 受け取った部分（引数 n だった部分）は f を引数とする関数として評価され，
-> (λ (f) (λ (x) (f ((λ (x) x) x))))
;; 更に，((λ (x) x) x) が再帰的に評価され，
-> (λ (f) (λ (x) (f x)))
;; これ以上評価される部分はないので，このラムダ式が返り値となる．
(λ (f) (λ (x) (f x)))

よって，two も同様に考え，

(define one (λ (f) (λ (x) (f x))))     ; ∵ one = (add-1 zero)
(define two (λ (f) (λ (x) (f (f x))))) ; ∵ two = (add-1 one)

となる．以上のことから Church numerals（C:n）は帰納的に次のように表される．

C:0 = (λ (f) (λ (x) x))
C:1 = (λ (f) (λ (x) (f x)))
C:2 = (λ (f) (λ (x) (f (f x))))
...
C:n = (λ (f) (λ (x) (f ... (f x)...))) ; x に対して再帰的に n 回 f を適用

また，(add-1 zero) の評価過程や C:n の一般形から，C:n に関する次のような性質が考察でき，

((λ (n) (λ (f) (λ (x) ((n f) x)))) C:n)
= (λ (f) (λ (x) (f ... (f x)...)))    ; x に対して再帰的に n 回 f を適用

そのことから，

C:m+n = (λ (f) (λ (x) (f ... (f x)...))) ; x に対して再帰的に m + n 回 f を適用
= (λ (f) (λ (x) (f ... ((n f) x)...))) ; ((n f) x) に対して再帰的に m 回 f を適用
= (λ (f) (λ (x) ((m f) ((n f) x))))

となる．従って，

(define (+ m n)
  (λ (f) (λ (x) ((m f) ((n f) x)))))

何故か数学っぽくなる．数学嫌いなのに＞＜

hoge

勉強の仕方とか，ブログへの載せ方がまだ定まらないなあ．chapter 1 は丸々載せちゃってるし．gist とか tumblr あたりに exercise の部分だけちまちま貼りつけていく方がいいんだろうか．

まあ，取り敢えずは，気が向いたときにこのブログに上げることにしよう．

hogehoge

と，ぐだぐだ書いていたら，github に exercise 毎に .scm に小分けにして上げている人を発見してみたり．

doc-view-mode を使ってみた

pdf を png に変換して表示するらしい（Ghostscript が必要）．キャッシュがない場合は変換に数秒から数分かかる．その間はこんな画面が表示される．

文書内検索には pdftotext が必要．ない場合は

% brew install xpdf

とかして入れる．
検索を一度実行すると，クエリを保存して次からもそのキーワードで検索しようとするので，次のようにして isearch と同じような挙動にした．

;;; emacs-version -> "23.2.1"

(defun my-doc-view-search (new-query &optional backward)
  "Like `doc-view-search' but always start a new search."
  (interactive "P")
  (setq doc-view-current-search-matches nil)
  (doc-view-search new-query backward))

(defun my-doc-view-search-forward (new-query)
  (interactive "P")
  (doc-view-search new-query))

(eval-after-load "doc-view"
  '(let ((map doc-view-mode-map))
     (define-key map (kbd "C-s") 'my-doc-view-search)
     (define-key map (kbd "s-d") 'doc-view-search-backward)
     (define-key map (kbd "s-g") 'my-doc-view-search-forward)
     ))

雑感

• インクリメンタルな検索ができない
• 検索したキーワードがハイライトされない
• リンクが無効になるので，脚注などに飛びづらい
• 時々落ちる
• 日本語は試していないので謎

といった感じだったので，Preview.app で見ることにした．

Cocoa Emacs に Aspell が入ってないことに気付く

homebrew なら

brew install aspell --lang=en

だけでいける．ispell-program-name は自動で設定されるはずだけど，上手くいかない場合は "/usr/local/bin" にパスが通っていないってことだから，どこかに

(let ((brew "/usr/local/bin")
      (path (getenv "PATH")))
  (unless (string-match brew path)
    (setenv "PATH" (concat brew ":" path)))
  (add-to-list 'exec-path brew))

とか書いとく．

Chapter 1 Building Abstractions with Procedures

追記：英語の文章はSICPからの引用です．

何故 lisp なのか云々．

1.1 The Elements of Programming

In programming, we deal with two kinds of elements: procedures and data. (Later we will discover that they are really not so distinct.) Informally, data is ``stuff'' that we want to manipulate, and procedures are descriptions of the rules for manipulating the data.

1.1.2 Naming and the Environment

It should be clear that the possibility of associating values with symbols and later retrieving them means that the interpreter must maintain some sort of memory that keeps track of the name-object pairs. This memory is called the environment (more precisely the global environment, since we will see later that a computation may involve a number of different environments).
この話は chapter 3 で詳しくやるそうな．

1.1.5 The Substitution Model for Procedure Application

式の評価のされ方．或いはその順序．
Applicative order versus normal order

(f 5)
-> (sum-of-squares (+ 5 1) (* 5 2))
-> (+ (square (+ 5 1)) (square (* 5 2)))
-> (+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
-> (+ (* 6 6) (* 10 10))
-> (+ 36 100)
-> 136

• normal-order - ``fully expand and then reduce'' evaluation method
• applicative-order - ``evaluate the arguments and then apply'' method

上の例は normal-order で，いったんすべての式を primitive な部分まで展開させてから評価する．一方，applicative-order では最初に arguments を評価してから展開していく．applicative-order では，

(f 5)
-> (sum-of-squares (+ 5 1) (* 5 2))
-> (sum-of-squares 6 10)
-> (+ (square 6) (square 10))
-> (+ (* 6 6) (* 10 10))
-> (+ 36 100)
-> 136

となる．この場合，normal-order よりも (+ 5 1)，(* 5 2) の評価回数が少ないので効率が良い．

Exercise 1.3.

暗黙の了解として，これまでに出てきていない関数とかは使っちゃ駄目なんだよね，きっと．

(define (largest a b c)
  (cond ((or (< a b) (< a c))
         (largest b c a))
        ((= a b)
         (if (< a c) c a))
        ((= a c)
         (largest a c b))
        (else a)))

(define (secondly a b c)
  (if (= a (largest a b c))
      (if (> b c) b c)
      (secondly b c a)))

(define (sum-of-squares-of-two-larger-numbers a b c)
  (sum-of-squares (largest a b c)
                  (secondly a b c)))

何も考えずに書き下していくと非効率なコードが出来上がる．そんな典型．

Exercise 1.4.

+ と - を評価すると関数オブジェクトが返ってくるのが気になった．

gosh> +
#<subr +>
gosh> -
#<subr ->

少し疑問が湧いたので実験．

gosh> (define a 1)
a
gosh> a
1
gosh> (define a 2)
a
gosh> a
2
gosh> (equal? a 2)
#t
gosh> (define (a) 2)
a
gosh> a
#<closure a>
gosh> (a)
2
gosh> (equal? a 2)
#f

ヤダ，なにこれ，怖い．．．define が関数だろうと変数だろうと値を上書きしてる．しかも，関数と変数が同じ名前空間に定義されてる．これが scheme の流儀ということか．

Exercise 1.5.

面白かったので，elisp でもやってみた．

(defun p () (p))
(defun test (x y) (if (= x 0) 0 y))

(test 0 (p))

これを Emacs 上で評価してみると．．．

1.1.7 Example: Square Roots by Newton's Method

平方根を返す関数 sqrt を Newton's Method を使って定義．

Exercise 1.6.

lisp は applicative-order なので，「new-if を呼び出したときに先ずその引数をすべて評価しようとする．その過程で，new-if の else-clause が評価されるとき，sqrt-iter を呼び出す．sqrt-iter は当然 new-if を呼び出し，その new-if は更に sqrt-iter を呼び出す．」といった具合に無限ループに陥る．
なんか，説明文まで無限ループに陥りそうだな．違った言い方すると，applicative-order は ``evaluate the arguments and then apply'' で，new-if に当てはめると，then apply が cond 式になってる．で，実際に new-if の評価が開始されると，evaluate the arguments の時点で sqrt-iter の反復が始まってしまい，then apply が実行されないまま無限ループに陥る．

1.1.8 Procedures as Black-Box Abstractions

前半は関数を役割ごとに切り分けましょう，というお説教．後半は関数のパッケージングについて．

(define (sqrt x)
  (define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess x)
    (average guess (/ x guess)))
  (define (sqrt-iter guess x)
    (if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x) x)))
  (sqrt-iter 1.0 x))

とすると，sqrt 内だけで有効なローカルな関数を定義できる．更に，sqrt の引数 x は lexical-scope になっているので，

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))

と書ける．

1.2 Procedures and the Processes They Generate

To become experts, we must learn to visualize the processes generated by various types of procedures.

1.2.1 Linear Recursion and Iteration

n! を求める関数 factorial について考える．
線型再帰（linear recursive）の場合，

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

と書くことが出来，次のように評価される．

(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

一方，線型反復（linear iterative）の場合，

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

と書くことが出来，次のように評価される．

(factorial 6)
((fact-iter   1 1 6))
(((fact-iter   1 2 6)))
((((fact-iter   2 3 6))))
(((((fact-iter   6 4 6)))))
((((((fact-iter  24 5 6))))))
(((((((fact-iter 120 6 6)))))))
((((((((fact-iter 720 7 6))))))))
(((((((720)))))))
((((((720))))))
(((((720)))))
((((720))))
(((720)))
((720))
(720)
720

ここで，fact-iter は末尾再帰（評価の一番最後に自分自身を呼び出す）になっているので，末尾再帰の最適化が行われ，実際には次のように評価される（参考）．

(factorial 6)
(fact-iter   1 1 6)
(fact-iter   1 2 6)
(fact-iter   2 3 6)
(fact-iter   6 4 6)
(fact-iter  24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720

1.2.2 Tree Recursion

木構造再帰は重複する計算が出てくるので，反復よりも遅くなるが，再帰でないと書けないような手続きもあるよ，ということで，コインの両替の話が出てくる．

1.2.3 Orders of Growth

ある手続きがどの程度のオーダーで評価されていくかをランダウ記法を使って考える．
線型再帰（linear recursive）な factorial の場合，

Θ(n) ; order of growth of the number of steps
Θ(n) ; order of growth of the space

線型反復（linear iterative）な factorial の場合，

Θ(n) ; order of growth of the number of steps
Θ(1) ; order of growth of the space

ここではΘを使っているけど，O で表現するほうが一般的かもしれない．

1.3 Formulating Abstractions with Higher-Order Procedures

高階関数

Exercise 1.29.

シンプソンの公式

gosh> (define (integral f a b n)
        (define h (/ (- b a) n))
        (define (y k) (f (+ a (* k h))))
        (define (integral-term x)
          (+ (y (* 2 x))
             (* 4 (y (inc (* 2 x))))
             (y (+ (* 2 x) 2))))
        (/ (* h (sum integral-term 0 inc (dec (/ n 2)))) 3))
integral
gosh> (integral cube 0 1 100)
1/4
gosh> (integral cube 0 1 1000)
1/4

分数出てきちゃったし．．．

gosh> (define (integral f a b n)
        (define h (/ (- b a) n))
        (define (y k) (f (+ a (* k h))))
        (define (integral-term x)
          (+ (y (* 2 x))
             (* 4 (y (inc (* 2 x))))
             (y (+ (* 2 x) 2))))
        (/ (* h (sum integral-term 0 inc (dec (/ n 2)))) 3.0))
integral
gosh> (integral cube 0 1 100)
0.25
gosh> (integral cube 0 1 1000)
0.25

そこじゃないのか．

gosh> (define (integral f a b n)
        (define h (/ (- b a) n))
        (define (y k) (f (+ a (* k h 1.0))))
        (define (integral-term x)
          (+ (y (* 2 x))
             (* 4 (y (inc (* 2 x))))
             (y (+ (* 2 x) 2))))
        (/ (* h (sum integral-term 0 inc (dec (/ n 2)))) 3))
integral
gosh> (integral cube 0 1 100)
0.2500000000000001
gosh> (integral cube 0 1 1000)
0.2500000000000001

これでいいのか．．．？

Exercise 1.31.

総乗
a. 取り敢えず反復で．

(define (product term a next b)
  (define (iter a res)
    (if (> a b)
        res
        (iter (next a) (* (term a) res))))
  (iter a 1))

product を使えば factorial も瞬殺．

(define (factorial n)
  (product identity 1 inc n))

円周率の近似式

(define (pi n)
  (define (term k)
    (/ (* 4 k (inc k)) (square (inc (* 2 k)))))
  (* 4 (product term 1 inc (/ n 2))))

シンプソンの公式の時もだけど，内部で (/ n 2) してるのは行儀が悪いのかもしれない．どちらも近似式なので，割る必要はないんだろうね．
b. product を再帰で．

(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))

1.3.2 Constructing Procedures Using Lambda

無名関数 lambda とそのシンタックスシュガーである let の説明．
某三週間によれば，

(define (func arg)
  arg)

は，λを使って，

(define func
  (lambda (arg)
  arg))

とも書ける．また，fluid-let という dynamic-scope の変数束縛もある（処理系依存）．

Exercise 1.34.

gosh> (define (f g)
        (g 2))
f
gosh> (f f)
*** ERROR: invalid application: (2 2)
Stack Trace:
_______________________________________

(f f)
-> g = f と解釈して (g 2) を呼び出す
-> (f 2)
-> g = 2 と解釈して (g 2) を呼び出す
-> (2 2)
-> 2 は関数じゃないよ

1.3.3 Procedures as General Methods

x |-> y

は，x を写像（関数）を通して y にするって意味だったはず．
Finding fixed points of functions
不動点の性質を利用して sqrt を定義する（Newton's Method とは異なるアプローチ）．

;; without average damping
(define (sqrt x)
  (fixed-point (lambda (y) (/ x y))
               1.0))

;; with average damping
(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y)))
               1.0))

1.3.4 Procedures as Returned Values

Experienced programmers know how to choose procedural formulations that are particularly perspicuous, and where useful elements of the process are exposed as separate entities that can be reused in other applications.
Newton's method
derivative（導関数），average damping, fixed-point などのアプローチを考慮して，Newton's method を再定義．

Abstractions and first-class procedures

高階関数を使ってプログラムを適度に抽象化させることは大事だよね．
This is not to say that one should always write programs in the most abstract way possible; expert programmers know how to choose the level of abstraction appropriate to their task.

Exercise 1.46.

(define (iterative-improve guess-func improve-func)
  (lambda (x)
    (if (guess-func x)
        x
        ((iterative-improve guess-func improve-func) (improve-func x)))))

(define (sqrt x)
  ((iterative-improve (lambda (guess)
                        (< (abs (- (* guess guess) x)) 0.001))
                      (lambda (guess)
                        ((lambda (a b) (/ (+ a b) 2)) guess (/ x guess))))
   1.0))

(define (fixed-point f first-guess)
  ((iterative-improve (lambda (guess)
                        (< (abs (- guess (f guess))) 0.00001))
                      f)
   first-guess))

λ使い過ぎて可読性が下がってるな．

SICP 読むための設定とか

春休みなのでプログラミングを勉強しようと思い，SICPを読んでいます（取り敢えず三章までやる予定）．以下は SICP のサンプルコードに使われている Scheme の処理系（Gauche）をインストールをした際のメモです．

Gauche のインストール

homebrew の pull request に上がっていた Gauche 用 formula を少しゴニョゴニョしてインストール（参考: Formula Cookbook）．SLIB モジュールの trace がデバッグに便利なようなので，Gauche:FAQ - SLIBは使えますか 等を参考に SLIB もインストール．

Emacs の設定

gosh-mode

最初は scheme-complete, quack, gauche-mode を使っていたんですが，物足りなかったので，今風な感じの gosh-mode をインストール．

% make install

して，どこかに

(require 'gosh-config)

と書いておく．これでよしなにやってくれるはずだけど，うちの環境だと，auto-complete-mode が上手く動いてくれなかったので（make install が上手くいってない？），一旦，gosh-mode.elc を捨てて Emacs 起動後に

M-x byte-compile-file RET /path/to/gosh-mode.el RET

として，gosh-mode.elc を作りなおしてみると上手くいきました．
init file は以下のように設定．

(require 'gosh-config)
(setq gosh-mode-hook nil)
(setq gosh-inferior-mode-hook nil)
(defun my-gosh-mode-initialize ()
  (set (make-local-variable 'eldoc-idle-delay) 1.2)
  (turn-on-eldoc-mode))
(add-hook 'gosh-mode-hook 'my-gosh-mode-initialize)
(add-hook 'gosh-inferior-mode-hook 'my-gosh-mode-initialize)
(set-face-foreground 'gosh-modeline-normal-face "gold")

gosh-config をロードすると，(gosh-sticky-mode 1) となって自動で flymake をオンにするのだけれど，自分の scheme レベルではバッファが真っ赤に染まって大変なことになるので，hook を再定義して flymake を使わないようにしました．それと，eldoc で呼び出す関数 gosh-eldoc-print-current-symbol-info が重い感じがしたので，eldoc-idle-delay の値を少し大きくしてます（デフォルトは 0.2）．
以上で，M-x gosh-run で REPL が使えたり C-x C-e が出来たりと，かなりいい感じになったので，先に挙げた三つの拡張はやめて，今は gosh-mode だけ使ってます．

info

SICP はどこかで拾った pdf 形式のものを読んでいるんですが，info 形式のものもあると便利なのでインストールしておきます．僕の場合，追加の info file は ~/.emacs.d/share/info で管理しているので，こんな感じに書いています．

;;; info
;; For adding .info to the entry, run the following in your shell.
;; % sudo install-info /path/to/foo.info /path/to/dir
(let ((my-info-dir "~/.emacs.d/share/info")
      (info-path (getenv "INFOPATH")))
  (unless (string-match (concat "\\`" (regexp-quote my-info-dir)) info-path)
    (setenv "INFOPATH"
            (concat my-info-dir ":" info-path))))

(defun open-sicp (&optional other-window)
  (interactive "P")
  (info "sicp.info" (and other-window "*SICP*")))

あと，anything を使って gauche-refj.info を読めるように

(defun anything-info-scheme-at-point ()
  (interactive)
  (anything
   :sources '(
              ((info-index . "gauche-refj.info"))
              ;; ((info-index . "gauche-refe.info"))
              ((info-index . "sicp.info"))
              )
   :input (thing-at-point 'symbol)
   :buffer "*info scheme*"))

とかしてます．でもなんか文字化けしてるよ．．．

SICP を読む前に

独習 Scheme 三週間 とか読んでおくと，scheme の雰囲気がつかめるかも．

zsh 導入メモ

面倒臭くてやってなかったんだけど，いい加減やんなきゃなあと思い，zsh を導入．

環境

Mac OS X 10.6.6

zsh

Mac 付属のもの（4.3.9）ではなく，最新のもの（4.3.11）をインストールする．

$ brew install zsh

ログインシェルの変更と ~/.zshrc*1 の作成

$ sudo sh -c "echo '/usr/local/bin/zsh' >> /etc/shells"
$ chsh -s /usr/local/bin/zsh
$ touch ~/.zshrc
$ echo 'export PATH=/usr/local/bin:$PATH' >> ~/.zshrc

設定の反映

zsh を再起動するか，以下を実行する．

% source ~/.zshrc

設定とか拡張とか

以下のサイトを参考に設定した．

• 漢のzsh | コラム | エンタープライズ | マイコミジャーナル
• 連載：zshで究極のオペレーションを｜gihyo.jp … 技術評論社
• zshで自動補完したい - hchbaw記
• Git だろうと Mercurial だろうと、ブランチ名をzshのプロンプトにスマートに表示する方法 - ess sup

おお，これはすごい！

*1:設定ファイルは .zshenv, .zshrc, .zlogin の三種類あるらしい．