(wat-aro)

生きてます

Schemeでクイックソート

先日の納会でソートの話が少し出たのでクイックソートを書いてみました.
書きやすいのでGaucheで.

まず普通に書いてみます.

(define (quick lst)
  (if (null? lst)
      '()
      (let ((first (car lst)))
        (append (quick (filter (lambda (x) (< x first)) lst))
                (filter (lambda (x) (= x first)) lst)
                (quick (filter (lambda (x) (< first x)) lst))))))
gosh> (quick '( 4 7 8 3 9 2 7 3 92 7 1))
(1 2 3 3 4 7 7 7 8 9 92)

普通ですね.
ただfilterで何度もリストの中身を舐めているのが嫌です. ここでstreamを使ってみます.

(use util.stream)
(define (quick lst)
  (stream->list
   (let recur ((s (list->stream lst)))
     (if (stream-null? s)
         stream-null
         (let ((first (stream-car s)))
           (stream-append (recur (stream-filter (lambda (x) (< x first)) s))
                          (stream-filter (lambda (x) (= x first)) s)
                          (recur (stream-filter (lambda (x) (< first x)) s))))))))
gosh> (quick '( 4 7 8 3 9 2 7 3 92 7 1))
(1 2 3 3 4 7 7 7 8 9 92)

リストからストリームへの変換とストリームからリストへの変換が入っているので
効率的になったのかどうか怪しいですが一応期待通りに動いていますね.
どうするのが正解なんでしょう?

once-onlyマクロの解読

実践Common Lisp p100にあるonce-onlyマクロの解読に挑戦.

実践Common Lisp

実践Common Lisp

 
 
 

マクロのコードは以下のとおり.

(defmacro onece-only ((&rest names) &body body)
  (let ((gensyms (loop for n in names collect (gensym))))
    `(let (,@ (loop for g in gensyms collect `(,g (gensym))))
       `(let (,,@ (loop for g in gensyms for n in names collect ``(,,g ,,n)))
          ,(let (,@ (loop for n in names for g in gensyms collect `(,n ,g)))
                ,@body)))))

一行ずつ解読していく

まずは

(let ((gensyms (loop for n in names collect (gensym))))

の部分から.
バッククォートがないので何がgensymsに束縛されるかをREPLで確かめる.

CL-USER> (let ((gensyms (loop for n in '(a b c) collect (gensym))))
           gensyms)
(#:G884 #:G885 #:G886)

namesの数と同じだけのユニークなシンボルを作成している.  
 
次の行は

`(let (,@ (loop for g in gensyms collect `(,g (gensym))))

gensymsは一行目の処理でユニークなシンボルのリストになっている.
gensymsのそれぞれの要素と(gensym)をペアにしていく.
ここまでを実行してみる.

CL-USER> (let ((gensyms (loop for n in '(a b c) collect (gensym))))
           `(let (,@ (loop for g in gensyms collect `(,g (gensym))))))
(LET ((#:G887 (GENSYM)) (#:G888 (GENSYM)) (#:G889 (GENSYM)))
  )

 
三行目.

`(let (,,@ (loop for g in gensyms for n in names collect ``(,,g ,,n)))

とうとう`,が二重に.
1つずつ見ていく. 二行目の`(let の式の中で `(letとなっているのでここは出力後の形が`(letとなってほしいはず.
,,@となっているのは二行目のバッククォート,三行目頭のバッククォートと二回バッククォートされているので 二度展開しなといloopが展開されない. これでloop内は展開されるようになった. 次は``(,,g ,,n).二重にバッククォートするのは先ほどと同じように`(foo bar) という形のリストにしたいから.
(,,g ,,n)になっているのはloopでgensymsの要素をgに,namesの要素をnに対応付けているから.
`(,gensymsの要素 ,nameの要素)という形に変換しようとしている.
  
ここまでを展開するとこうなる

CL-USER> (let ((names '(a b c)))
           (let ((gensyms (loop for n in names collect (gensym))))
             `(let (,@(loop for g in gensyms collect `(,g (gensym))))
                `(let (,,@ (loop for g in gensyms for n in names collect ``(,,g ,,n)))
                   ))))
(LET ((#:G937 (GENSYM)) (#:G938 (GENSYM)) (#:G939 (GENSYM)))
  `(LET (,`(,#:G937 ,A) ,`(,#:G938 ,B) ,`(,#:G939 ,C))
     ))

コンパイル時には新たに(gensym)で作られたユニークなシンボルにnamesの値が束縛されるようになる.
 
 
最後に4行目.

,(let (,@ (loop for n in names for g in gensyms collect `(,n ,g)))

二行目と三行目でバッククォートされてるので,先頭のカンマは展開されず(let ...という形になる.
,@の部分は既に先頭で一度カンマがあった後なのでそのまま展開出来る.
`(,n ,g)の部分で実際にAにAの値を束縛するという部分を作る.
なのでここではバッククォートが一つ.
ここのgには3行目で値に束縛したユニークなシンボルが入る.
実際に展開する.
最後なのですべて展開するとこうなる.

CL-USER> (let ((names '(a b c))
               (body '(body)))
           (let ((gensyms (loop for n in names collect (gensym))))
             `(let (,@(loop for g in gensyms collect `(,g (gensym))))
                `(let (,,@ (loop for g in gensyms for n in names collect ``(,,g ,,n)))
                   ,(let (,@ (loop for n in names for g in gensyms collect `(,n ,g)))
                         ,@body)))))
(LET ((#:G934 (GENSYM)) (#:G935 (GENSYM)) (#:G936 (GENSYM)))
  `(LET (,`(,#:G934 ,A) ,`(,#:G935 ,B) ,`(,#:G936 ,C))
     ,(LET ((A #:G934) (B #:G935) (C #:G936))
        BODY)))

まとめ

まずnamesと同じ数だけ(gensym)でユニークなシンボルを作り,それをgensymsというリストにする.
gensymsの各要素を新たに(gensym)に束縛するlet式を作る.
この(gensym)はonce-onlyを使うマクロの展開時に新しくユニークなシンボルを作る.
gensymsの各要素を評価すると新しく作られるユニークなシンボルを返すようになる. このユニークなシンボルにnamesの各値を束縛するようにする.
それが本体の三行目に当たる. 四行目ではnamesのシンボルにgensymsの各要素を対応付ける.
gensymsの各要素は新たに作られたユニークなシンボルに束縛され,そのユニークなシンボルはnameの値に束縛される.
以上で終わり.  
 
高階マクロで名前の衝突を回避して,評価順序を保つのはこんなに大変なんですね.

shibuya.lispで発表しました

ゆるわな感じです.

Lisp Meet Up presented by Shibuya.lisp #38 - connpass

niconare.nicovideo.jp

反省点は聞いてる人のほうを向いて喋れなかったことですね. 自分のPCのモニタばかり見てました. 次どこかで発表するときはそこを改善したいですね. 後もっとましなスライドを作れるようになりたい.

計算機プログラムの構造と解釈 第2版

計算機プログラムの構造と解釈 第2版

Emacsのhtmlizeを使ってコードのシンタックスハイライトを保ったままKeynoteにコピペ

SchemeのコードをKeynoteシンタックスハイライトを保ってコピペする方法がわからずに困っていたら Twitterで教えてもらいました.

EmacsでhtmlizeでHTMLを出力してそれをSafariで開く.
 
 

f:id:wat-aro:20160324235611p:plain  
 
 
SafariからKeynoteへコピペ

f:id:wat-aro:20160324235830p:plain

おおー!これはいい!
ちなみにChromeで開くとうまくいきませんでした.
Gistからコピペするのと違ってこれならEmacsシンタックスハイライトのままコピペできるのがいいですね.
ありがたや〜

Rubyで言語処理100本ノック 00-04

www.cl.ecei.tohoku.ac.jp

Rubyの練習のために始めました.
4章からは難しそうなので3章まで頑張りたい.でも飽きたらやめるかも.
コードを書く基礎が足りない気がするのでもっと書かないと.
始めるにあって,とりあえずRuby 2.2.3のStringクラスは一通り目を通してきました.
全体的に末尾再帰でなんとかしようとしてます.
Rubyは末尾再帰の最適化がないって聞いたんですがどうなんですかね? Rubyっぽい書き方がわからないので,Rubocop先生に出来るだけ怒られないように書いてます.

00

# 00 文字列を受け取り,末尾から順に表示する
class String
  def my_reverse
    size = length
    result = ''
    while size > 0
      size -= 1
      result << self[size]
    end
    result
  end

  # Like tail call
  def iter_reverse
    iter('', length)
  end

  private

  def iter(str, str_len)
    if str_len > 0
      iter(str + self[str_len - 1], str_len - 1)
    else
      str
    end
  end
end

'reverse'.my_reverse                # => "esrever"
'a'.my_reverse                      # => "a"
''.my_reverse                       # => ""

'reverse'.iter_reverse          # => "esrever"
'a'.iter_reverse                # => "a"
''.iter_reverse                 # => ""

01

# 01 文字列の奇数番目だけ取り出した新しい文字列を返す
class String
  def str_odd
    iter(0, '')
  end

  private

  def iter(index, str)
    if index < length
      if index.even?
        iter(index + 1, str + self[index])
      else
        iter(index + 1, str)
      end
    else
      str
    end
  end
end

'hello'.str_odd                # => "hlo"
'abcde'.str_odd                # => "ace"
'パタトクカシーー'.str_odd     # => "パトカー"

02

# 02 2つの文字列を受け取り,先頭から交互に混ぜた文字列をつくる
def comb_str(str1, str2)
  iter(str1, str2, '')
end

def iter(str1, str2, result)
  if str1.empty?
    result + str2
  elsif str2.empty?
    result + str1
  else
    iter(str1[1..-1], str2[1..-1], result + str1[0] + str2[0])
  end
end

comb_str('パトカー', 'タクシー') # => "パタトクカシーー"

03

# 03 文字列から数字のリストをつくる
class String
  def pi
    split.map(&:length)
  end
end

"Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics.".pi
 # => [3, 1, 4, 1, 6, 9, 2, 7, 5, 3, 5, 8, 9, 7, 10]

04

# 04 文字列を受け取り,単語に分解し,1, 5, 6, 7, 8, 9, 15, 16, 19番目の単語は先頭の1文字
# それ以外の単語は先頭に2文字を取り出し,取り出した文字列から単語の位置(先頭から何番目の単語か)への連想配列を返す
class String
  def element
    recur(split, 1, [])
  end

  private

  def helper(str, i)
    case i
    when 1, 5, 6, 7, 8, 9, 15, 16, 19
      [str[0], i]
    else
      [str[0, 2], i]
    end
  end

  def recur(arr, index, result)
    if arr.empty?
      result
    else
      recur(arr.drop(1), index + 1, result.push(helper(arr[0], index)))
    end
  end
end

"Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause. Arthur King Can.".element
# => [["H", 1], ["He", 2], ["Li", 3], ["Be", 4], ["B", 5], ["C", 6], ["N", 7], ["O", 8], ["F", 9], ["Ne", 10], ["Na", 11], ["Mi", 12], ["Al", 13], ["Si", 14], ["P", 15], ["S", 16], ["Cl", 17], ["Ar", 18], ["K", 19], ["Ca", 20]]

Stringクラスを一読するのに時間がかかったので今日はこれだけ.

OSX クリーンインストール前の準備

yosemiteからEl Capitanへアップデートする前の準備.

dotfilesの準備

.bashrcや.emacs.dなどインストール後に必要になりそうなものをここに入れてしまいます.
他にも次の環境に必要なものはここに入れてしまいます.
そしてシンボリックリンクを貼るスクリプトをつけておきます.

最強の dotfiles 駆動開発と GitHub で管理する運用方法 - Qiita

ここのスクリプトを少し変更して

#!/bin/bash
for f in .??*
do
    filepath="${PWD}/${f}"
    homefile="${HOME}/${f}"
    
    [[ "$f" == ".git" ]] && continue
    [[ "$f" == ".DS_Store" ]] && continue
    
    ln -snf $filepath $homefile
done

これを実行すればホームディレクトリにシンボリックリンクが張られます.

Homebrewでインストールしたもののリスト,tap先を保存する

Homebrewで何を入れたかなんて覚えていられませんね.
tapで何を追加したのかも覚えていられません.
なのでファイルに書き出しておきます.
ここから抜き出して一気にインストールなんてことが出来るかは知りません.
クリーンインストール後に調べます.

$ brew tap > ~/dotfiles/brewtaplist
$ brew list > ~/dotfiles/brewlist

これで全て書きだされます.
さっきのスクリプトドットファイル以外のシンボリックリンクは作らないのでこれらのリンクは作られません.

iTerm2の設定のエクスポート

iTerm2の設定も覚えていられませんね.
未来を見てきたらこういうのです.(timemachineで戻ってきました)
なので設定ファイルをエクスポートしておきます.

iTerm2の設定をインポート・エクスポートする方法 - Qiita

ここを見てきてください.
Preferences > General > Prefeences のLoad preferences ... のチェックボックスをクリックしてホームディレクトリのdotfilesにします.
ディレクトリを確認して com.googlecode.iterm2.plist があればOK.
なければもう一度保存先のディレクトリ名があってるか確認してください.

Karabinerの設定のエクスポート

Karabinerの設定も覚えていられませんね.
快適な環境を維持するためにこれもエクスポートして次の環境に持って行きましょう.

Karabinerの設定移行 - Qiita

$ /Applications/Karabiner.app/Contents/Library/bin/karabiner export > ~/dotfiles/karabiner.sh

これで大丈夫です.

最後に

以上の作業で作ったdotfilesをgithubに上げるなり,dropboxに上げるなり,外付けHDDに入れるなりして次の環境に送りましょう.
準備完了です.

初めてのgem

github.com

キャメルケース,スネークケース,パスカルケースを相互に変換するgemを書きました.
書き方わからずに色々やってたら最初にリリースした分は盛大にバグってました.
とりあえずバグが取れたのでまたgemに.
一応 gem install case_converter で入れられます.

使い方はこんな感じ

"camel_case".snake_to_camel                 # => "camelCase"

"string ca_mel_case string".snake_to_camel  # => "string caMelCase string"

"pascal_case".snake_to_camel                # => "pascalCase"

"string pas_cal_case string".snake_to_camel # => "string pasCalCase string"

"snakeCase".camel_to_snake                  # => "snake_case"

"foo snakeCase bar".camel_to_snake          # => "foo snake_case bar"

"pascalCase".camel_to_pascal                # => "PascalCase"

"foo pasCalCase bar".camel_to_snake         # => "foo pas_cal_case bar"

"SnakeCase".pascal_to_snake                 # => "snake_case"

"foo SnaKeCase bar".pascal_to_snake         # => "foo sna_ke_case bar"

"CamelCase".pascal_to_camel                 # => "camelCase"

"foo CaMelCase bar".pascal_to_camel         # => "foo caMelCase bar"

初心者でもこれなら簡単に書ける!