08 Jun 2015, 13:06

SICP 第 2 章 データによる抽象の構築を読んだ

SICP 第 2 章を読み終わった?のでなんか書きます.

感想

第 1 章を読み終わってから 3 ヶ月が経っていた…

実は一旦挫折した. 問題が難しくて解けないからだ. しかし、ある時発想を変えて、とにかく写経しながら進めようと思った.

問題は解けないけれども、分からないわけではないので、理解できる範囲で頑張ろうと思った. すると、一旦は折れた心も再び立ち上がることができて、先に進めるようになった.

あと、ところどころ本流に関係なさそうな部分は飛ばしながら読んだ. ズル読み.

あと、Emacs lisp で問題をといていたが、途中で Scheme に変更した. ときどき、動かないプログラムがでてくるので.

要点

データ抽象・抽象の壁

constructor(構成子), selector(選択子) によって、どう使うかに関するプログラムの 抽象の壁 を構築し、抽象レイヤを構築する.

これを、Data Abstruction(データ抽象) という.

データオブジェクトをどう表現するかに関するプログラムの部分を、 データオブジェクトをどう使うかに関するプログラムから隔離する.

データによるレイヤー構造を構築することで, 複雑なシステムをうまく構築することができる.

  • ある場所での変更を局所的なレイヤの変更に封じこめることができる
  • 実装方法(どう表現するか)を自由に入れ替えることができる.

有理数の構成子 make-rat と 選択子 numer, denum を利用することで、 有理数の演算を定義できる.

;; --------------------------------------
(defun cons (x y) ...)
(defun car (x) ...)
(defun cdr (x) ...)
;; --------------------------------------
(defun make-rat (n d) (cons n d))
(defun numer (x) (car x))
(defun denum (x) (cdr x))
;; --------------------------------------
;; このレイヤは car cdr cons は意識しなくていい
;; numer,denum がどう実装されていても気にしない.
(defun add-rat (x y)
  (make-rat (+ (* (numer x) (denom y)
                  (numer y) (denom x)))
            (* (denum x) (denum y))))
;; --------------------------------------

所感

カプセル化との違いが分からない. 状態を持たないということだろうか?

公認インタフェース 

並びを操作するための手続き.

  • map
  • filter
  • accumulate
  • flatmap

公認インタフェースを組み合わせることで、リストを自由に操作できる.

いろいろなブログをみると、ここで Lisp に目覚めるひとがおおいとか?!

所感

unix のパイプラインと似ている. 部品を組み合わせることことよって、データを処理する.

こういう処理を自由自在にかけるようになりたい!

cat file.txt | sort | cut ....

実装例

(defun accumulate (op initial sequence)
  (if (null sequence)
      initial
      (funcall op (car sequence)
               (accumulate op initial (cdr sequence)))))

(defun map (p seq)
  (accumulate (lambda (x y) (cons (funcall p x) y))
              nil
              seq))

(defun filter (predicate sequence)
  (cond ((null sequence) nil)
        ((funcall predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (t (filter predicate  (cdr sequence)))))

02 Mar 2015, 13:21

SICP 手続きによる抽象の構築を読んだ

はじめに

SICP を今年から読んでいます. 第一章を読むのに 2 ヶ月かかった!

こりゃ, 全部読みきるのに 1 年くらいはかかりそうだ… or2.

気長に楽しみながら頑張る. 切りがいいので, ここまでの要点をまとめてみる.

手続きとは

大事な, そしてややこしい用語がでてくるので, 整理する.

式 (Expression)

計算機の解釈系に渡される前の表現. 解釈系に評価されると, 式はプロセスになる.

以下, wikipedia からの引用も.

言語によって定められた優先順位や結びつきの規定に則って評価 される値, 変数, 演算子, 関数の組み合わせ.

プロセス (Process)

プロセスは計算機のなかに潜む抽象的な存在. プロセスはもう一つの抽象的な存在, データを操作する. プロセスの進行は, 規則のパターン, プログラムにしたがう.

プログラム (Program)

プロセスの進行を指示する, 規則のパターン.

プログラムは二つの要素をもつ.

  • 手続き: データの処理方法 (能動的) ex.) +, -
  • データ: 処理したいもの (受動的) ex.) 1,2,3

手続きによる抽象の構築

この章のおもしろいところは, はじめは基本的な手続きからはじまり, ひとつずつ抽象度をあげていくところにある.

章でいうと, 1.1 と 1.3. 1.2 は再帰手続きについてかかれている.

                     procedures       data

primitive element +, *, <, = 23, 1.738 means of combination () combination
if
cond
means of abstraction defun

言語は以下の仕掛けを有している.

Level0: 基本式 (プリミティブな手続きの構築)

もっとも基本的な手続き.

  • which represent the simplest entities the language is concerned with,
  • 言語が関わるもっとも単純なものを表す.

primitive expressions 基本式:

  • which represent the simplest entities the language is concerned with,
  • 言語が関わるもっとも単純なものを表す.
1, +, -

Level1: 組合せ法 (組み合わせ手続きによる抽象の構築)

複数の手続きを組み合わせて一つにした手続き.

  • by which compound elements are built from simpler ones.
  • より単純なものから合成物をつくる.

Emacs Lisp では 組合せ (combination) は () で表現する.

(* 1 1)

Level2: 抽象化法 (名前つき値による抽象の構築)

オブジェクトを値 (value) とする変数 (variable) を識別するものが名前. 名前をつけることで, 値を識別する.

Emacs Lisp では 名前つけは defun で表現する.

(defun size () 2)
(size)

Level3: 手続き定義 (名前つき手続きによる抽象の構築)

名前付けは, 値だけでなくて手続きにもできる.

  • by which compound elements can be named and manipulated as units.
  • 合成物に名をつけ, 単一のもとして扱う.

名前のつけられた手続き. これをいわゆる関数と呼ぶ.

(defun square (x) (* x x))

手続き定義は, 細部をかくすことができる. いわゆる 手続き抽象 という.

Level4: 高階手続きによる抽象の構築

手続きをあつかう手続きを高階手続きという

  • 手続きを引数にとる
  • 手続きを戻り値として返す
(square (square (square 2)))

Level5: lambda (名前なし手続き による抽象の構築)

高階手続きの引数にいちいち, defun で定義された手続きをわかすのは煩わしい.

名前なしの手続きを扱いたい. プロセスを生み出す特殊形式を lambda という.

Emacs Lisp では lambda で表現する.

名前つき手続きは, 以下の糖衣構文となっている. Lisp インタプリタは実際には以下のように解釈している.

(defun square
    (lambda (x) (* x x))

さいごに

さいごに, 感動したセンテンスをぬきだして, 第一章を締めくくる.

われわれはプログラマとして, プログラムの根底にある抽象をみつけ, より強力な抽象化ができるように努めてなければならない.

高階手続きの重要さは, それにより抽象をプログラム言語の要素して 確かに表せ, 他の計算要素として扱えるようになる点にある.

26 Feb 2015, 14:54

Emacs Lisp で SICP に挑戦するさいの落とし穴

はじめに

SICP を Emacs Lisp でとくという, やや無謀なことに挑戦中.

SICP 自体は Scheme をベースにかかれているので, 例題や回答を elisp に置き換えながら読んでいく.

Emacs Lisp は不自由なもので, 結構ハマリポイントがあった.

第一章がようやく終わったところで, いったんたまったノウハウをはきだしておこう.

よくある置き換え

defun

毎回ある置き換え.

;; scheme
(define (hoge x) x)

;; emacs lisp
(defun hoge (x) x)

cond

cond の書き方について,

  • scheme は 一番最後に else をつける.
  • elips は 一番最後に t をつける.
(cond ((= 1 1) 1)
      (else 2))

(cond ((= 1 1) 1)
      (t 2))

高階関数

関数にの頭に ‘をつけて別の関数の引数にすると, 関数は評価されずに引数に渡すことができる.

評価するときは, (funcall f) のように funcall を呼ぶ.

ローカル変数

elips は scheme のように, 関数の中に関数をかいても 変数や関数のスコープを限定できない.

let, let*, letrec が利用をうまくつかって, ローカルな変数や関数をつかう.

ローカル関数の定義

let + lambda を利用する, 変数に無名関数を bind させることで実現する.

(let ((p (lambda (a) (message a))))
    (funcall p "hoge"))

letrec を利用する方が正式か?

letrec の rec は 再帰のこと. let は再帰関数が定義できないが, letrec はできる.

落とし穴

Dynamic Scope

Emacs Lisp は Dynamic Scope という方式をとり, 名前空間がない. なので, 安直な a とか sum とかいう関数を名づけてしまうと, うっかり他の関数と競合する.

できるだけ, 他とかぶらない関数名をつけるほうが無難.

Emacs24 からは, ファイルの先頭に以下を書くと, setq で宣言した変数は本当の Lexical Scope になる.

-*- lexical-binding: t -*- 

高階関数で 関数がわたせない

無名関数を入力しても, なぜか Symbol value as void となる.

以下を行頭に買いて, M-x eval-buffer で評価することで, 回避できた.

;; -*- lexical-binding: t -*- 

max-lisp-eval-depth 発生

Emacs Lisp は 末尾最適化がされないため, 深い再帰処理をかくと, よくクラッシュする.

これによって, 解くのを諦めた問題多数. これが Elisp の限界か.

その他

自分一人で行き詰まった時は, 先人の知恵を拝借する.

31 Dec 2014, 16:00

SICP を読むために Emacs で Scheme 環境を構築

はじめに

2015 年は SICP を読んでいく予定です.

というわけで, Scheme の開発環境を Emacs で構築しました.

Scheme の処理系 Gauche

まずは, Scheme 処理系をインストール.(ゴーシュ)

gosh -V

scheme-mode

Default で Emacs にはいっている. 以下の設定を参考にした.

;; UTF-8 に統一
(setq process-coding-system-alist
      (cons '("gosh" utf-8 . utf-8) process-coding-system-alist))

(setq scheme-program-name "gosh -i")
(autoload 'scheme-mode "cmuscheme" "Major mode for Scheme." t)
(autoload 'run-scheme "cmuscheme" "Run an inferior Scheme process." t)

;; 別のウィンドウに gosh を動作させる
(defun scheme-other-window ()
  "Run Gauche on other window"
  (interactive)
  (split-window-horizontally (/ (frame-width) 2))
  (let ((buf-name (buffer-name (current-buffer))))
    (scheme-mode)
    (switch-to-buffer-other-window
     (get-buffer-create "*scheme*"))
    (run-scheme scheme-program-name)
    (switch-to-buffer-other-window
     (get-buffer-create buf-name))))

(define-key global-map "\C-cS" 'scheme-other-window)

smartparens

カッコをあつかうための多機能な移動・編集ツール.

(require 'smartparens-config)
(smartparens-global-mode t)

default

smartparens-config では以下が設定される.

example

設定例.

あまりに多機能すぎて使いこなす自信がないな..

覚えておきたいのは,

  • かっこで囲む xx sp-pair M-(
  • かっこを外す sp-unwrap C-M-s
(define-key sp-keymap (kbd "C-M-f") 'sp-forward-sexp)
(define-key sp-keymap (kbd "C-M-b") 'sp-backward-sexp)

(define-key sp-keymap (kbd "C-M-d") 'sp-down-sexp)
(define-key sp-keymap (kbd "C-M-a") 'sp-backward-down-sexp)
(define-key sp-keymap (kbd "C-S-a") 'sp-beginning-of-sexp)
(define-key sp-keymap (kbd "C-S-d") 'sp-end-of-sexp)

(define-key sp-keymap (kbd "C-M-e") 'sp-up-sexp)
(define-key emacs-lisp-mode-map (kbd ")") 'sp-up-sexp)
(define-key sp-keymap (kbd "C-M-u") 'sp-backward-up-sexp)
(define-key sp-keymap (kbd "C-M-t") 'sp-transpose-sexp)

(define-key sp-keymap (kbd "C-M-n") 'sp-next-sexp)
(define-key sp-keymap (kbd "C-M-p") 'sp-previous-sexp)

(define-key sp-keymap (kbd "C-M-k") 'sp-kill-sexp)
(define-key sp-keymap (kbd "C-M-w") 'sp-copy-sexp)

(define-key sp-keymap (kbd "C-M-s") 'sp-unwrap-sexp)
(define-key sp-keymap (kbd "M-<backspace>") 'sp-backward-unwrap-sexp)

(define-key sp-keymap (kbd "C-<right>") 'sp-forward-slurp-sexp)
(define-key sp-keymap (kbd "C-<left>") 'sp-forward-barf-sexp)
(define-key sp-keymap (kbd "C-M-<left>") 'sp-backward-slurp-sexp)
(define-key sp-keymap (kbd "C-M-<right>") 'sp-backward-barf-sexp)

(define-key sp-keymap (kbd "M-D") 'sp-splice-sexp)
(define-key sp-keymap (kbd "C-M-<delete>") 'sp-splice-sexp-killing-forward)
(define-key sp-keymap (kbd "C-M-<backspace>") 'sp-splice-sexp-killing-backward)
(define-key sp-keymap (kbd "C-S-<backspace>") 'sp-splice-sexp-killing-around)

(define-key sp-keymap (kbd "C-]") 'sp-select-next-thing-exchange)
(define-key sp-keymap (kbd "C-<left_bracket>") 'sp-select-previous-thing)
(define-key sp-keymap (kbd "C-M-]") 'sp-select-next-thing)

(define-key sp-keymap (kbd "M-F") 'sp-forward-symbol)
(define-key sp-keymap (kbd "M-B") 'sp-backward-symbol)

(define-key sp-keymap (kbd "H-t") 'sp-prefix-tag-object)
(define-key sp-keymap (kbd "H-p") 'sp-prefix-pair-object)
(define-key sp-keymap (kbd "H-s c") 'sp-convolute-sexp)
(define-key sp-keymap (kbd "H-s a") 'sp-absorb-sexp)
(define-key sp-keymap (kbd "H-s e") 'sp-emit-sexp)
(define-key sp-keymap (kbd "H-s p") 'sp-add-to-previous-sexp)
(define-key sp-keymap (kbd "H-s n") 'sp-add-to-next-sexp)
(define-key sp-keymap (kbd "H-s j") 'sp-join-sexp)
(define-key sp-keymap (kbd "H-s s") 'sp-split-sexp)

;;;;;;;;;;;;;;;;;;
;; pair management
(sp-local-pair 'minibuffer-inactive-mode "'" nil :actions nil)

;;; lisp modes
(sp-with-modes sp--lisp-modes
  (sp-local-pair "(" nil :bind "C-("))

(sp-pair "(" ")" :wrap "M-(")

rainbow-delimiters

かっこの深さに応じて色付けしてくれる.

かっこの強調をどきつくする. これはいいなぁ.

注意 テーマ読み込みのあとに配置すること.

(require 'rainbow-delimiters)
(add-hook 'emacs-lisp-mode-hook 'rainbow-delimiters-mode)
(add-hook 'scheme-mode-hook 'rainbow-delimiters-mode)
(add-hook 'lisp-mode-hook 'rainbow-delimiters-mode)

;; these setting should be placed after load-theme
;; using stronger colors
(require 'cl-lib)
(require 'color)

;; 関数にしないとうまくいかない...手動で有効に
(defun rainbow-delimiters-using-stronger-colors ()
  (interactive)
  (cl-loop
   for index from 1 to rainbow-delimiters-max-face-count
   do
   (let ((face (intern (format "rainbow-delimiters-depth-%d-face" index))))
     (cl-callf color-saturate-name (face-foreground face) 100))))

;; making unmatched parens stand out more
(set-face-attribute 'rainbow-delimiters-unmatched-face nil
            :foreground 'unspecified
            :inherit 'error
            :strike-through t)

SICP を info で読む

以下の設定で Emacs の info で SICP が読める (English)

この方法のよいところは, テキストの文章をそのまま C-x C-e で評価して実 行できるところ.

# sicp.info 取得
wget http://www.neilvandyke.org/sicp-texi/sicp.info.gz
gunzip sicp.info.gz

# /usr/local/info に sicp.info をコピー.
$ sudo mkdir -p /usr/local/info
$ sudo cp sicp.info /usr/local/info

# dir ファイルを編集.
$ sudo emacs /usr/local/share/info/dir

# 次の二行を追記.
 The Algorithmic Language Scheme
 * SICP : (sicp.info). Structure and Interpretation of Computer Programs.

調べたけど利用しないもの

せっかく調べたけど, 設定を有効にしない (できない) ものも列挙.

paredit

Lisp コードで頻出する括弧類のバランスを維持することを目的としたもの.

smartparens に人気をとられてしまったかわいそうな子.

gosh-mode

scheme-mode の拡張.

scheme-mode を継承しているので, 基本的な操作は変わらないそうだ.

el-get で取得. リボジトリから取得後に make && make install

(require 'gosh-config)

M-x gosh-run で gosh が起動すれば OK.

scheme-mode に比べて情報がすくないのと, すごさがわからないので, ひとまずは scheme-mode を利用することにした.

なれてきたらそのうちもう一度挑戦する.

scheme-complete

auto-complete で補完をすることができる. デフォルト設定で, そこそこの補完候補が出る.

scheme-complete というものもあるそうなので,気休め程度に導入.

本家のサーバ落ちた?? github の mirror より取得.

以下を参考にして, auto-complete の source に scheme-complete の情報源を加える.

メンテされていないのと, auto-complete で何とかなるので削除.

(autoload 'scheme-smart-complete "scheme-complete" nil t)
(autoload 'scheme-get-current-symbol-info "scheme-complete" nil t)

(eval-after-load 'scheme
  '(define-key scheme-mode-map "\e\t" 'scheme-smart-complete))

;; scheme-mode-hook
(defvar ac-source-scheme
  '((candidates
     . (lambda ()
         (require 'scheme-complete)
         (all-completions ac-target (car (scheme-current-env))))))
  "Source for scheme keywords.")

(add-hook 'scheme-mode-hook
          '(lambda ()
             (make-local-variable 'ac-sources)
             (setq ac-sources (append ac-sources '(ac-source-scheme)))))

eldoc

scheme の eldoc は scheme-complete と合わせて利用するらしいが, eldoc error void-function eldoc-current-symbol とでてエラーする.

(require 'eldoc-extension)
(add-hook 'scheme-mode-hook
  (lambda ()
    ;; Gauche の場合, 次の 2 個の変数を設定しておいたほうがよいのかも.
    (setq default-scheme-implementation 'gauche)
    (setq *current-scheme-implementation* 'gauche)
    ;; eldoc-mode
    (set (make-local-variable 'eldoc-documentation-function)
     'scheme-get-current-symbol-info)
    (eldoc-mode t)
    )
  )
(setq lisp-indent-function 'scheme-smart-indent-function)

flymake 設定

glint というものがあるらしい. gauche 0.8.13 でしか動作しないようなので試していない.