Programmer's Note

コード読み書きの備忘録。

Vimにneosnippetを導入

SICPのexerciseをやっていると、例えば(ns …)の宣言など定型的な部分は、snippetがあると便利だなーと思う。 探してみたらvimのpluginで定番のneosnippetがあった。

GitHub - Shougo/neosnippet.vim: neo-snippet plugin

この動作にはneocompleteが必要だったの一緒に導入した。

上記サイトにはneocompleteの代わりにneocomplcacheも使えると書いてあるが、自分の環境(Mac OS X 10.9, vim 7.4)ではうまく動作しなかった。 (インストールはうまく行ったがまったくcompleteしてくる様子がなかった)

導入方法

NeoBundleのリストに追加する。

call neobundle#begin(expand('~/.vim/bundle/'))
...
NeoBundle 'Shougo/neocomplete'
NeoBundle 'Shougo/neosnippet'
NeoBundle 'Shougo/neosnippet-snippets'
call neobundle#end()

あとは、もろもろの設定を.vimrcに追加する

"" --------------------------------------------
"" neocomplete
"" --------------------------------------------
" Disable AutoComplPop.
let g:acp_enableAtStartup = 0
" Use neocomplete.
let g:neocomplete#enable_at_startup = 1
" Use smartcase.
let g:neocomplete#enable_smart_case = 1
" Set minimum syntax keyword length.
let g:neocomplete#sources#syntax#min_keyword_length = 3

" Define dictionary.
let g:neocomplete#sources#dictionary#dictionaries = {
    \ 'default' : '',
    \ 'vimshell' : $HOME.'/.vimshell_hist',
    \ 'scheme' : $HOME.'/.gosh_completions'
        \ }

" Define keyword.
if !exists('g:neocomplete#keyword_patterns')
    let g:neocomplete#keyword_patterns = {}
endif
let g:neocomplete#keyword_patterns['default'] = '\h\w*'

" Plugin key-mappings.
inoremap <expr><C-g>     neocomplete#undo_completion()
inoremap <expr><C-l>     neocomplete#complete_common_string()

" Recommended key-mappings.
" <CR>: close popup and save indent.
inoremap <silent> <CR> <C-r>=<SID>my_cr_function()<CR>
function! s:my_cr_function()
  return (pumvisible() ? "\<C-y>" : "" ) . "\<CR>"
  " For no inserting <CR> key.
  "return pumvisible() ? "\<C-y>" : "\<CR>"
endfunction
" <TAB>: completion.
inoremap <expr><TAB>  pumvisible() ? "\<C-n>" : "\<TAB>"
" <C-h>, <BS>: close popup and delete backword char.
inoremap <expr><C-h> neocomplete#smart_close_popup()."\<C-h>"
inoremap <expr><BS> neocomplete#smart_close_popup()."\<C-h>"
" Close popup by <Space>.
"inoremap <expr><Space> pumvisible() ? "\<C-y>" : "\<Space>"

" AutoComplPop like behavior.
"let g:neocomplete#enable_auto_select = 1

" Shell like behavior(not recommended).
"set completeopt+=longest
"let g:neocomplete#enable_auto_select = 1
"let g:neocomplete#disable_auto_complete = 1
"inoremap <expr><TAB>  pumvisible() ? "\<Down>" : "\<C-x>\<C-u>"

" Enable omni completion.
"autocmd FileType css setlocal omnifunc=csscomplete#CompleteCSS
"autocmd FileType html,markdown setlocal omnifunc=htmlcomplete#CompleteTags
"autocmd FileType javascript setlocal omnifunc=javascriptcomplete#CompleteJS
"autocmd FileType python setlocal omnifunc=pythoncomplete#Complete
"autocmd FileType xml setlocal omnifunc=xmlcomplete#CompleteTags

" Enable heavy omni completion.
if !exists('g:neocomplete#sources#omni#input_patterns')
  let g:neocomplete#sources#omni#input_patterns = {}
endif
"let g:neocomplete#sources#omni#input_patterns.php = '[^. \t]->\h\w*\|\h\w*::'
"let g:neocomplete#sources#omni#input_patterns.c = '[^.[:digit:] *\t]\%(\.\|->\)'
"let g:neocomplete#sources#omni#input_patterns.cpp = '[^.[:digit:] *\t]\%(\.\|->\)\|\h\w*::'

" For perlomni.vim setting.
" https://github.com/c9s/perlomni.vim
let g:neocomplete#sources#omni#input_patterns.perl = '\h\w*->\h\w*\|\h\w*::'


"" --------------------------------------------
"" neo-snippet
"" --------------------------------------------
" Plugin key-mappings.
" Note: It must be "imap" and "smap".  It uses <Plug> mappings.
imap <C-k>     <Plug>(neosnippet_expand_or_jump)
smap <C-k>     <Plug>(neosnippet_expand_or_jump)
xmap <C-k>     <Plug>(neosnippet_expand_target)

" SuperTab like snippets behavior.
" Note: It must be "imap" and "smap".  It uses <Plug> mappings.
imap <C-k>     <Plug>(neosnippet_expand_or_jump)
"imap <expr><TAB>
" \ pumvisible() ? "\<C-n>" :
" \ neosnippet#expandable_or_jumpable() ?
" \    "\<Plug>(neosnippet_expand_or_jump)" : "\<TAB>"
smap <expr><TAB> neosnippet#expandable_or_jumpable() ?
\ "\<Plug>(neosnippet_expand_or_jump)" : "\<TAB>"

" For conceal markers.
if has('conceal')
  set conceallevel=2 concealcursor=niv
endif

動作確認

試しにnsのsnippetを使ってみる。 vimを起動して適当に:e /tmp/test.cljとかでファイルを編集する。 インサーションモードに入り、nsを入力してC-kを押すと、一瞬で下記のようなコードに展開してくれる。

(ns .tmp.test
  (:require <`2:`>))

この状態でカーソルはtmp.testにあたっており、編集できる状態になっていて、 さらにC-kを押すと、カーソルは<`2:`>に飛ぶ。 素晴らしい。

snippetファイルは自分で作成できる。標準のclojureのsnippetは

~/.vim/bundle/neosnippet-snippets/neosnippets/clojure.snip

に入っているので、これを参考にして色々追加してみるかな。

以上。

[SICP] SICP第2章読了

第2章の最後の課題は残しているが、読了した。データの抽象化の威力をまざまざと見せられた。

なんといってもこの章のクライマックスの多項式の演算プログラム。

データの型およびClojureでいうマルチメソッドのシステムを自前で用意して、実にエレガントに解いてみせる。これがポリモーフィズムの真価かと。

多項式の係数が多項式の場合も、全く特別扱いする必要なく、再帰的に処理できてしまう。美しい!

取り扱う問題が数学の問題なので、泥臭い部分がなくて済んでしまうのかもしれない。

しかし教科書としてはこれがいい。整理しやすく記憶に残る。データの抽象化とポリモーフィズムがどういうケースで生きるかイメージに残るから応用しやすい。

mapのループをforで表現する

前回(mapと再帰で木構造を扱う - Programmer's Note)は、mapと再帰木構造を扱う処理を書いたが、mapはシーケンスを順になめていく高階関数であって、いわゆるコレクションを扱うfor文と変わらない。 Clojureにもforマクロは用意されていて、かなり表現力が高い。

前回のscale-tree関数は、

(defn scale-tree [tree factor]
  (map (fn [sub-tree]
         (if (coll? sub-tree)
           (scale-tree sub-tree factor)
           (* sub-tree factor)))
       tree))

だが、これをforを使って書き直すと以下になる。

(defn scale-tree [tree factor]
  (for [item tree]
    (if (coll? item)
      (scale-tree item factor)
      (* item factor))))

処理内容がだいぶ読みやすくなった。mapは汎用性が高く利点はあるが、無名関数の定義(fn [..] ..)が入る分コードが煩雑になり読みにくくなる。 Schemeなどだと無名関数はいわゆるlambda関数なので、表記が(lambda (...) ..)でさらに読みにくい。

forの場合は、扱うコレクションと各要素を代入する変数が一緒に、要素に対する処理の手前に置かれるので、コードを追いやすい。

プログラムの可読性はシンタックスがもろに効いてくることを実感させられる。

さて、SICPにはmapを使った以下のような例(練習問題)が出てくる。

(defn unique-pairs [n]
  (reduce concat
          (map 
            (fn [i]
              (map (fn [j] (list i j))
                   (range 1 i)))
            (range 1 (inc n)))))

これは、1 <= j < i <= nのiとjのペアの集合を作る関数だ。 実行結果は以下のようになる。

(unique-pairs 6)
;-> ((2 1) (3 1) (3 2) (4 1) (4 2) (4 3) (5 1) (5 2) (5 3) (5 4) (6 1) (6 2) (6 3) (6 4) (6 5))

このコードはmapを二重に使っていて読みにくいが、forを使うとすっきりと表現できる。

(defn unique-pairs [n]
  (reduce concat
          (for [i (range 1 (inc n))]
            (for [j (range 1 i)]
              (list i j)))))

これにとどまらず、Clojureforマクロはかなり便利で、二重ループはもっとすっきり表現できる。

(defn unique-pairs [n]
  (for [i (range 1 (inc n))
        j (range 1 i)]
    (list i j)))

なんと、これだけで済んでしまった。 Clojure見事なり。

mapと再帰で木構造を扱う

SICP楽しすぎるな。 第2章の途中、mapを使って木構造のデータ処理を紹介していて、えらく感動した。

題材は以下のとおり、木構造の中の全要素に対して任意のfactorを掛ける関数scale-treeを作ること。

(def ttree (list 1 (list 2 (list 3 4) 5) (list 6 7)))
(scale-tree ttree 10)
;-> (10 (20 (30 40) 50) (60 70))

再帰を使うのは分かりやすい。

(defn scale-tree [tree factor]
  (cond (not (coll? tree)) (* tree factor)
        (empty? tree) nil
        :else (cons (scale-tree (first tree) factor)
                    (scale-tree (rest tree) factor))))

一回分解して組み立て直しているコストはかかるが、木構造再帰は実に相性がよい。

処理の流れは以下のとおりで、データの先頭と残り取り出して、ツリー階層を下っている。 (カッコがあるとデータが分かりにくいので、関数呼び出しは簡略的に記す。)

1: scale-tree (1 (2 (3 4) 5) (6 7)), 10
2: cons scale-tree 1, 10
        scale-tree ((2 (3 4) 5) (6 7)), 10
3: cons 10
        scale-tree ((2 (3 4) 5) (6 7)), 10
4: cons 10
        cons scale-tree (2 (3 4) 5)), 10
             scale-tree (6 7), 10
5: cons 10
        cons cons 2, 10
                  ((3 4) 5), 10
             scale-tree (6 7), 10
...

これをmapを使うと以下のように書ける。

(defn scale-tree [tree factor]
  (map (fn [sub-tree]
         (if (coll? sub-tree)
           (scale-tree sub-tree factor)
           (* sub-tree factor)))
       tree))

処理の流れは下記のとおり。

1: scale-tree (1 (2 (3 4) 5) (6 7)), 10
2: map処理
      fn 1
      fn (2 (3 4) 5)
      fn (6 7)
3: map処理
      10
      scale-tree (2 (3 4) 5)
      fn (6 7)
4: map処理
      10
      map処理
         fn 2
         fn (3 4)
         fn 5
      fn (6 7)
...

これの何がすごいかって? 実際には木構造を再構築しているのにconsをまったく使用していないところだ。 (表に見えるところでは)

map関数はシーケンス(データ列)をインプットに、各要素に処理を施したあとのシーケンスを返す。 しかし、これが単純なデータ列だけではなく、木構造にも応用できるとは思ってもみなかった。

それも、概念を整理するとシンプルで、シーケンスの構成要素が、たまたま別のシーケンスだった場合は そこを再帰的にたどっていけばよいだけ、だ。

同じデータ構造に対して、別の視点を持つことで、プログラミングの仕方が変わってくる。 SICPを読んでいると、こういうパラダイムの転換が頻繁に出てくるから実に面白い。

recordを使ってデータ構造をつくる

SICPまじ楽しいな。この本は、一読して内容を理解するだけじゃなくて、手を動かしてコードを写経したり練習問題をやると、純粋にプログラミングの楽しさを味わえる。本質的な部分(パラダイム)を濃密に扱っているので、数学と一緒で、手を動かして思考を追う過程に悦びがある。

まだ2章の途中だが、データ構造をLISPの流儀で定義するところが、考え方としてはすごくシンプルでエレガント。 しかし、何度味わっても美味しい。(いや、逆にシンプルゆえに美味しいのかもしれない)

手続き型言語オブジェクト指向言語みたいにstructやclassを使ってデータ構造そのものを定義するのではなく、関数というインタフェースだけを使って、データの抽象概念を見せる。

さて、練習問題2.2では、線分を作ってその線分の中点を求めるために、点、線分を扱う関数を定義する。 使う側からすると以下のようになる。

(def seg (make-segment (make-point 10 20)
                       (make-point 20 30)))

(x (midpoint-segment seg)) ; -> 15
(y (midpoint-segment seg)) ; -> 25

OOPっぽく書けば

seg = Segment.new( Point.new(10,20), Point.new(20, 30))

seg.midpoint-segment.x  # -> 15
seg.midpoint-segment.y  # -> 25

(x-point (midpoint-segment seg))seg.midpoint-segment.x-pointは順番が逆になっただけで、記述量に違いはない。 しかし、考え方が真逆なのが、やはり面白い。

関数の定義は、SICP流に従ってClojureで書くと下記のとおりになる。

(defn make-point [x y] (list x y))
(defn x [p] (first p))
(defn y [p] (last p))

(defn make-segment [start end] [start end])
(defn start [s] (first s))
(defn end [s] (last s))

(defn midpoint-segment [s]
  (let [ss (start s)
        es (end s)]
    (make-point (/ (+ (x ss) (x es)) 2)
                (/ (+ (y ss) (y es)) 2))))

これをClojureのrecordと使うと、ぐっと簡単に書ける。 midpoint-segmentはデストラクテャリングを使って記述を短くしている。

(defrecord Point [x y])
(defrecord Segment [start end])

(defn midpoint-segment 
  [{:keys [start end]}]
    (->Point (/ (+ (:x start) (:x end)) 2)
             (/ (+ (:y start) (:y end)) 2)))

recordは内部的にはJavaのclassそのもので、データ構造を定義できて、なおかつClojureで定義したものをJavaの世界からでも参照できる。 まさにJavaとのinteroperabilityのための機能だ。

recordのいいところはmapと同等の機能を持つ点で、要素を取り出すための関数定義xystartendが不要で、 defrecord時の引数に渡す要素名がそのままkeyとして使える。

さらに、生成関数を自前で定義する必要ないという点もある。 (->Segment)と書けばSegment.new()に相当する。(Segment.)と書いても動作する。

このJavaからのいいとこ取り、しかもwell-designedなところが、Clojureのセクシーなところだ。

最初の使用例を書き直すと下記になる。

(def seg (->Segment (->Point 10 20)
                    (->Point 20 30)))

(:x (midpoint-segment seg)) ;-> 15
(:y (midpoint-segment seg)) ;-> 25

最後の2行は、スレッディングマクロを使えば、さらにOOPっぽくかける。

(-> seg midpoint-segment :x) ;-> 15
(-> seg midpoint-segment :y) ;-> 25

以上。

SICP第一章読了

SICP第1章を読了した。演習問題もコンプリート! 言語はSchemeではなくClojureを使ったのでClojureのいい練習にもなった。

振り返ると、プログラミングの教材として、構成が実によく考えられていて感動すら覚える。 一級品の少年漫画やRPGなみのストーリー展開を思わせる(笑)。 序盤の伏線がクライマックスで花開く、みたいな。

しょっぱなの入り口では、平方根を求める関数を、ニュートン法の考え方を使って、 丁寧に要素に分解して関数を階層化してプログラムを作っていく。 関数型プログラミングのまさにお手本を示している。

クライマックスにおいては、まったく同じ問題を、高階関数を使うことでより高いレベルで解いている。 プログラミングの道具としては「関数を引数に渡す」「関数を返り値にする」機能を使うことで、 もののみごとに平方根を求める処理が、汎用的な抽象概念の組み合わせによって表現できることを示す。

平方根をもとめることとは何か? それは、y = x/yの平均減衰(average damp)を使って不動点(fixed point)を求めるに等しい。

(defn sqrt [x]
  (fixed-point (average-damp (fn [y] (/ x y)))
               1.0))

まさにコードが体を表している。

上記はSchemeではなくClojureで書いたコードだが、 この本がプログラミング言語LISPを選んだ理由がよくわかる。 問題を解くための手続きを、これ以上直接的かつ簡潔に表現できる言語は他には無いと思う。 余計なものはいっさいない。表現したいことをダイレクトに表現できる。

読んでいると、この本のプログラムで何気なくやっていることが、他の言語だと難しいだろうなと感じることも多々ある。 Schemeは実にシンプルで強力だな!とほれぼれする。

いまのところClojure以外はやる気はしないのだが、Schemeがそれに匹敵するものだとよく分かった。 結局、動作環境(プラットホーム)が一番重要なんだな。ClojureJVMを選んで大正解だと思う。

しかし、SICPClojureで十分幸せなプログラミングの時間を過ごせるな。SICPで数学自体の面白さも味わえるし。 まあ、この本はむしろ数学のバックボーンがしっかりしている学生にプログラミングを教えるための教材ではあるが。

Clojureでパスカルの三角形

SICP遅々と読む。練習問題にパスカルの三角形の要素を計算せよ(再帰を使って)、というのがある。 フィボナッチ数列の次くらいに手軽な題材でいろいろ試せて遊べるなと。

Clojureらしい解き方は、やっぱ遅延シーケンスを作るやり方だろうなと。 出力形式は問われていないから、任意の行数までの計算結果を返すとしよう。

=> (take 5 (pascal-triangle))
([1] [1 1] [1 2 1] [1 3 3 1] [1 4 6 4 1])

=> (nth (pascal-triangle) 5)
[1 5 10 10 5 1]

コード:

(defn next-row
    [row]
    (letfn [(add-1-both-ends [coll] (concat [1] coll [1]))]
      (->> (partition 2 1 row)
           (map (fn [[a b]] (+ a b)))
           add-1-both-ends
           vec)))

(defn pascal-triangle
  ([] (pascal-triangle [1]))
  ([col] (lazy-seq (cons col (pascal-triangle (next-row col))))))

next-rowパスカル三角形の特定の行の数列が与えられたとして、その次の行の数列を返す。

=> (next-row [1 1])
[1 2 1]
=> (next-row [1 2 1])
[1 3 3 1]

この関数の実装方法としては、以前「プログラミングClojure」で衝撃的だったフィボナッチ数列の解き方に習って、 いったん与えられた数列の形を扱いやすい形に変えている。

[1 3 3 1] → [[1 3] [3 3] [3 1]]

これで再帰を使わなくてもmapを使って要素の計算ができる。 partitionという関数を使えば、上記は簡単に出来る。

=> (partition 2 1 [1 3 3 1])
((1 3) (3 3) (3 1))

仮にcore関数のpartitionを使わずに、似たことをやるとしたら以下の関数を作れば良い。

(defn my-partition
   [[a b :as col]]
   (when (and a b)
     (cons [a b] (my-partition (rest col)))))

デストラクチャリングを使って要素を取り出して再帰するClojureのエレガントさを味わえるので、これはこれで楽しい。

pascal-triangle関数も、遅延シーケンスを使わずに再帰を使って、しかもStack Overflowを起こさない末尾最適可能なように作るとしたら、下記になるかなと。(中で使っているnext-rowは変わらない)

(defn pascal-triangle
  ([n] (pascal-triangle n [1] []))
  ([n a b]
    (if (zero? n)
      b
      (recur (dec n) (next-row a) (conj b a)))))

遅延シーケンスほど使い回しは効かなくなるが、

=> (pascal-triangle 5)
([1] [1 1] [1 2 1] [1 3 3 1] [1 4 6 4 1])

という感じになる。

この小さい題材の実装でもClojureの以下の機能が便利すぎて、

  • シーケンスを扱う高階関数(map, partition)
  • 引数個数ごとに関数の処理を分けて定義できる(multi-arity)
  • デストラクチャリングによる引数の分解
  • スレッディングマクロ(->>)

これらが無い世界で暮らすのが辛い(笑)。