2013年12月29日日曜日

[OCaml]文字列のsplit

文字列を任意の文字列で分割するには、Str.splitを使う。
インタプリタで試してみると、

# let xs = Str.split (Str.regexp ",") "a,b,c,d";;
Characters -1--1:
  let xs = Str.split (Str.regexp ",") "a,b,c,d";;
 
Error: Reference to undefined global `Str'
#

怒られた。

Regular Expressions in OCaml を見て解決した。
インタプリタでは、str.cmaをロードしてから、Strモジュールを使う。

# #load "str.cma" ;;
# let xs = Str.split (Str.regexp ",") "a,b,c,d";;
val xs : string list = ["a"; "b"; "c"; "d"]
#

Listモジュールは何もしなくても使えたが、Strは明示的にロードしないと駄目なのか。
よく分からないことだらけだ。

冬休みなので、普段使わないOCamlの学習中。
関数型という同じジャンルのせいか、Haskellとかなり似ている言語だ。
Haskellの文法と、OCamlの文法が頭の中で混ってしまいそう。

2013年12月24日火曜日

[Scheme][Racket]RacketをDebian Wheezy 32bitにインストール

少しだけ読んで積読していたSICP(計算機プログラムの構造と解釈)、冬休みになるし、再読しようと思う。
書中では、Schemeを使うので、グラフィックの描画や、Webサーバの実装が簡単にできそうな、Racket を使おう。

Debian 32bit版にインストールしようとしたが、http://racket-lang.org/download/ を見ると、Linux X86_64 (Debian squeeze) はあるが、32bit版が無いので、ソースからインストールした。

インストール

http://racket-lang.org/download/ から Unix sourceをダウンロードする。

現在は racket-5.3.6-src-unix.tgz が最新版。

~/src/ にダウンロードしたソースを展開する。
$ cd src
$ tar zxf racket-5.3.6-src-unix.tgz

インストール方法は racket-5.3.6/src/README に書いてある。
展開したディレクトリのsrcディレクトリで、
$ cd racket-5.3.6/src
$ mkdir build
$ cd build
$ ../configure
$ make
$ make install

make install には結構時間がかかる。

configure に --prefix を付けていないので、
> If the `--prefix' flag is omitted, the binaries are built for an
> in-place installation (i.e., the parent of the directory containing
> this README will be used directly).
となり、~/src/racket-5.3.6 自身にインストールされる。

起動

racket-5.3.6/bin/ にパスを通して、drracket を実行する。

Emacsとの連携
http://docs.racket-lang.org/guide/Emacs.html を見ると Emacsのmajorモードもあるようなので、後で試してみよう。

参考

2013年12月21日土曜日

[Clojure][Emacs]MilkodeでClojureのソースを検索できるようにしよう

仕事では、メソッド名や変数名等をキーワードにして、複数のプロジェクトのソースを横断的に検索することが多い。
結構な規模で、ファイル数が多く、grepによる検索では非常に時間がかかり、効率が悪い。
Milkodeは全文検索エンジンgroongaを使った、ソースコード検索用のツールで、数万ファイルを対象にしても、瞬時に検索できる。
Webアプリとしても動作し、ブラウザを使って検索もできる。
検索するソースの追加も簡単なので、重宝している。

Clojureのソースを検索できるようにしよう。

インストール

MilodeはRubyアプリである。
gem でインストールできる。
rroonga(groongaのRuby用API)
$ gem install rroonga
$ gem install milkode

これでmilkコマンドが使えるようになる。

データベースの作成

$ milk init --default
create     : /home/satoshi/.milkode/milkode.yaml
create     : /home/satoshi/.milkode/db/milkode.db created.

Clojureソースの取得

srcディレクトリにソースリポジトリをcloneする。
$ mkdir src
$ cd src
$:~/src git clone https://github.com/clojure/clojure.git

ソースプロジェクトの登録

$ milk add clojure
package    : clojure
result     : 1 packages, 279 records, 279 add. (1.56sec)
*milkode*  : 1 packages, 279 records in /home/satoshi/.milkode/db/milkode.db.

登録したプロジェクトの確認

$ milk list
clojure ← ◆登録された
*milkode*  : 1 packages, 279 records in /home/satoshi/.milkode/db/milkode.db.

コマンドラインでの検索

gmilkコマンドで検索できる。

$:~/src cd clojure
$:~/src/clojure gmilk RETRY_LIMIT
src/jvm/clojure/lang/LockingTransaction.java:25:public static final int RETRY_LIMIT = 10000;
src/jvm/clojure/lang/LockingTransaction.java:28://public static int COMMUTE_RETRY_LIMIT = 10;
src/jvm/clojure/lang/LockingTransaction.java:252:    for(int i = 0; !done && i < RETRY_LIMIT; i++)

ソースのディレクトリ内でgmilkコマンドを実行しないと、検索できないことに注意。
ソースのディレクトリ外の場合は、パッケージ名をオプション指定する。
詳細は gmilkコマンドのマニュアルhttp://milkode.ongaeshi.me/gmilk.htmlを参照。

Webアプリでの検索

次のコマンドで検索用のWebアプリを起動する。
$ milk web
デフォルトではブラウザを起動する。

ブラウザを起動せずに、外部からの接続を許可した状態で起動するには、以下のコマンドを実行する。
$ milk web -n -o 0.0.0.0

詳細は milk help web コマンドを参照。

次は検索結果の画面。

Emacsでの検索

検索用のELispもある。
https://github.com/ongaeshi/emacs-milkode

auto-installが使えば、
(auto-install-from-url "https://raw.github.com/ongaeshi/emacs-milkode/master/milkode.el")
でインストールできる。

init.elに次の設定を追加する。
(require 'milkode)

検索するには
M-x milkode:search
を実行する。
ミニバッファに gmilk: と表示されるので、検索文字列を入力する。

図は -a RETRY_LIMIT を入力した例。VPSに接続したターミナル内のEmacsなので、少し表示が汚ない。

-a は 全プロジェクトを対象にする場合のオプション。
(-a を付けないと正しく検索できなかった。カレントディレクトリがソースのディレクトリ内ではないから?)

参考


2013年12月18日水曜日

[Clojure][Ruby]RougeでSelenium WebDriverを使う

Ruby + Clojure = Rouge
Selenium WebDriverを使ってGoogle検索してみた。

Rubyは最新版を使用した。
$ ruby -v
ruby 2.0.0p353 (2013-11-22 revision 43784) [i686-linux]

Rougeのインストールと起動

gemでインストールできる。簡単だ。
$ gem install rouge-lang
REPLを起動するには rougeコマンドを使う。
$ rouge
Rouge 0.0.15
user=>

ついついprintlnとやってしまいそうになるが、putsでhello。

user=> (puts "hello, Rouge!")
hello, Rouge!
nil
user=> ^Dで終了

Selenium WebDriverを使ってみる

gemでselenium-webdriverをインストールしておく。
$ gem install selenium-webdriver

Rubyのコード

require "selenium-webdriver"

driver = Selenium::WebDriver.for :firefox
driver.navigate.to "http://google.com"

element = driver.find_element(:name, 'q')
element.send_keys "Clojure Ruby Rouge"
element.submit

puts driver.title

driver.quit


Rougeのコード

(require "selenium-webdriver")

(def driver (Selenium.WebDriver/for :firefox))

(-> driver
  (.navigate)
  (.to "http://www.google.com/"))

(def element (.find_element driver :name "q"))

(.send_keys element "Clojure Ruby Rouge")
(.submit element)

(puts (.title driver))

;; (.quit driver) ;; ブラウザを終了させないようにコメントアウト


Rougeで実行

拡張子はrgのようだ。
上記のコードはgoogle.rgとした。

rougeコマンドに渡せば良い。
最初分からずに(load-file "google.rg")とやってみたが、
load-fileは定義されていなった。
https://github.com/rouge-lang/rouge/blob/master/lib/boot.rg
https://github.com/rouge-lang/rouge/blob/master/lib/rouge.rb
を見ても、load〜は定義されていないみたい。

$ rouge google.rg
Google

Firefoxが立ち上がり、「Clojure Ruby Rouge」を検索する。

感想

Rougeは起動が早くて良い。
Emacs ciderで接続できない。これはかなり残念。
https://github.com/clojure/tools.nrepl をrougeに移植すれば良いのかな?
でも大変そう。
Rubyの豊富なライブラリが利用できるのは便利だ。
エラーが起きても、該当行が表示されないので、デバッグが大変だ。

参考


2013年12月17日火曜日

[Emacs]リージョンを任意の文字列で囲むコマンドを作成した

Emacsで文章を作成していると、

hogehoge
fugafuga

--------------------
hogehoge
fugafuga
--------------------

と----で囲ったり、
Redmineのコメントで、

hogehoge
fugafuga

<pre>
hogehoge
fugafuga
</pre>

と書くことが結構多い。
指定したリージョンの前後に、任意の文字列を挿入できるコマンドがあると便利そうなので作ってみた。

使い方

リージョンを選択して、
M-x enclose-string
ミニバッファで
String(s/t/num):
と聞いてくるので、以下のいずれかを入力する。

(1)任意の文字列で囲む場合
最初の文字にsを指定する。
例: shoge
hogeで囲む。

(2)タグで囲む場合
最初の文字にtを指定する。
例: tpre
<pre>と</pre>で囲む。

(3)指定した回数を繰り返す文字列で囲む場合
例: 30-
------------------------------(「-」30個)で囲む。

ソース

(defun multi-string (n str)
  (loop repeat n concat str))

(defun pre-post-text-string (str)
 (list str str))

(defun pre-post-tag-string (str)
 (list (concat "<" str ">") (concat "</" str ">")))

(defun pre-post-multi-string (n str)
 (let ((n-str (multi-string (string-to-int n) str)))
    (list n-str n-str)))

(defun pre-post-string (str)
 "書式文字列に応じた前後の文字列を取得する。\n
前の文字列と後ろの文字列のリストを返す。\n
最初の文字が s の場合、それ以降の文字列を前後の文字列とする。\n
例: s--- → (\"---\" \"---\")\n
最初の文字が t の場合、それ以降の文字列をタグ名として扱う。\n
例: tpre → (\"<pre>\" \"</pre>\")\n
最初の文字列が数値の場合、数値の後ろの文字列を数値分繰替えした文字列を、前後の文字列とする。
例: 10* → (\"**********\" \"**********\")\n"
 (cond
  ((string-match "^s\\(.*\\)" str)
    (pre-post-text-string (match-string 1 str)))
  ((string-match "^t\\(.*\\)" str)
    (pre-post-tag-string (match-string 1 str)))
  ((string-match "^\\([0-9]+\\)\\(.*\\)" str)
    (pre-post-multi-string (match-string 1 str) (match-string 2 str)))))

(defun enclose-region (start end str)
  "リージョンの前後に文字列を挿入する。"
  (interactive "r\nsString(s/t/num):")
  (destructuring-bind (pre-str post-str) (pre-post-string str)
    (message (concat pre-str ":" post-str))
    (save-excursion
      (save-restriction
    (narrow-to-region start end)
    (goto-char (point-min))
    (insert pre-str "\n")
    (goto-char (point-max))
    (unless (bolp)
      (insert "\n"))
    (insert-before-markers post-str "\n")))))


Emacsは、手軽に機能を拡張できるので、便利だ。

2013年12月16日月曜日

[Clojure][Emacs]EmacsのCiderを起動するLeiningen pluginを作ってみた

$ lein cider
とすると、REPLを起動して、Emacsのciderコマンドを実行して、Emacs側でもREPLを起動するLeiningen pluginを作ってみた。

私はDebianを常用しており、Clojureでの開発には、REPLとして、Emacs上で動作するCiderを使用している。Emacsと同時に複数のターミナルを開いて、Emacsとターミナルの間を行き来している。
lein replは、ターミナルで起動して、Emacsからはciderコマンドで接続していた。
EmacsとターミナルのREPLを同時に使っていることも多い。
毎回ターミナルでlein replした後に、Emacsからciderで再接続するのが面倒なので、このpluginを作ってみた。

便利かなと思って作ってみたものの、cider-jack-inコマンドがあることを考えると、機能的には微妙なプラグインだな...

使い方

~/.lein/profiles.clj に lein-cider の設定を追加する。

{:user {:plugins [[lein-cider "0.1.0-SNAPSHOT"]]}}

Emacsをサーバーとして起動しておく(server-start関数を使用)。
プロジェクトのディレクトリで、
$ lein cider
を実行すると、Emacs上でciderコマンドが実行されて、REPLを起動する。

ソース

ソースはこちら
標準のREPL(lein repl)を起動後に、emacsclientコマンド経由で ELispのcider関数を呼び出している。
REPLが完全に起動した後に、Emacs側でcider関数を実行しないと、
IllegalAccessError pp does not exist clojure.core/refer
というエラーがでてしまうので、手っ取り早く、もう完全に起動した頃かなーという3秒後に、emacsclientコマンドを実行するようにした。

(defn server [project cfg headless?]
  (let [port (apply original-server-func [project cfg headless?])
        host (:host cfg)]
    (future
      (Thread/sleep leiningen.cider/WAIT_TIME) ; ←◆コレ
      (call-cider host port))
    port))


うーむ。まったくもって、行き当たりばったりな実装だ。

Emacsサーバー

こちらを見ると、
Note that since Emacs 23 this is the preferred way to use Emacs in daemon mode. (start-server) is now mostly deprecated.
というコメントがあった。
ほー。今はdaemon modeで使う方が良いようだ。

参考

2013年12月14日土曜日

[Clojure]lein-tryで外部ライブラリを使う

外部のClojureライブラリを使うには、project.cljのdependenciesに記述しなければならない。ちょっとお試しでライブラリを使用したい場合、これは面倒くさかった。

lein-tryプラグインを使うと、project.cljはそのままで、使用したい外部ライブラリを引数に渡すだけで、試すことができるようになる。

準備

以下のように~/.lein/profiles.cljを編集して、lein-tryプラグインを使えるようにする。
{:user {:plugins [[lein-try "0.4.1"]]}}

試してみる

satoshi@debian:~/workspace/clojure$ lein deps
Retrieving lein-try/lein-try/0.4.1/lein-try-0.4.1.pom from clojars
Retrieving lein-try/lein-try/0.4.1/lein-try-0.4.1.jar from clojars
Couldn't find project.clj, which is needed for deps

プラグインを読み込んだことを確認。

clj-timeの最新版を試してみる。

satoshi@debian:~/workspace/clojure$ lein try clj-time
Retrieving clj-time/clj-time/0.6.0/clj-time-0.6.0.pom from clojars ← clj-timeをロードしている
Retrieving joda-time/joda-time/2.2/joda-time-2.2.pom from central
Retrieving clj-time/clj-time/0.6.0/clj-time-0.6.0.jar from clojars
Retrieving joda-time/joda-time/2.2/joda-time-2.2.jar from central
nREPL server started on port 51459 on host 127.0.0.1
REPL-y 0.3.0
Clojure 1.5.1
    Docs: (doc function-name-here)
          (find-doc "part-of-name-here")
  Source: (source function-name-here)
 Javadoc: (javadoc java-object-or-class-here)
    Exit: Control+D or (exit) or (quit)
 Results: Stored in vars *1, *2, *3, an exception in *e

user=> (require '[clj-time.core :as t])
nil
user=> t/date-time
#<core$date_time clj_time.core$date_time@6849b9>
user=> (t/date-time 2013 12 13)
#<DateTime 2013-12-13T00:00:00.000Z>
user=>

バージョン番号の指定もできる。

satoshi@debian:~/workspace/clojure$ lein try clj-time "0.5.1"
Retrieving clj-time/clj-time/0.5.1/clj-time-0.5.1.pom from clojars
Retrieving clj-time/clj-time/0.5.1/clj-time-0.5.1.jar from clojars
nREPL server started on port 49481 on host 127.0.0.1
REPL-y 0.3.0
Clojure 1.5.1
    Docs: (doc function-name-here)
          (find-doc "part-of-name-here")
  Source: (source function-name-here)
 Javadoc: (javadoc java-object-or-class-here)
    Exit: Control+D or (exit) or (quit)
 Results: Stored in vars *1, *2, *3, an exception in *e

user=>

今まで、いちいちproject.cljにライブラリの設定を書いてからlein replしていたので、これはお手軽で、とても便利。

参考


2013年12月13日金曜日

[Clojure]マルコフ連鎖に基づく文生成

先日購入した、はじめてのAIプログラミング C言語で作る人工知能と人工無能を読んでいる。
文生成が面白そうだったので、Clojureで書いてみた。

処理内容としては、以下の通り。
(1)形態素解析ライブラリKuromojiを使用して、元ネタとなる文章を形態素解析する。
(2)その形態素の連鎖をモデル化して、マルコフ連鎖に基づく文生成をする。

プログラム

(ns ai.sentence
  (:import (org.atilika.kuromoji Token Tokenizer)))

(def ^:dynamic *words*
  "マルコフ連鎖のモデル
次のキーと値のマップ
キー: 形態素
値: キーを次の形態素、値を出現数とするマップ"
  (ref {}))

(defn tokenize [text]
  (let [tokenizer (. (Tokenizer/builder) build)]
    (. tokenizer tokenize text)))

(defn token-word [token]
  (.trim (.getSurfaceForm token)))

(defn inc-map-value [m k]
  (if (get m k)
    (update-in m [k] inc)
    (assoc m k 1)))

(defn register-word [m word1 word2]
  (let [word2-map (get m word1 {})]
    (assoc m word1 (inc-map-value word2-map word2))))

(defn load-text [file-name]
  (let [text (slurp file-name)
        tokens (tokenize text)]
    (reduce (fn [m [token1 token2]]
              (let [word1 (token-word token1)
                    word2 (token-word token2)]
                (if (or (= word1 ""))
                  m
                  (register-word m word1 word2))))
            {} (partition 2 1 tokens))))

(defn select-word [word-map]
  (first (rand-nth (seq word-map))))

(defn select-next-word [word-map word]
  (let [next-word-map (get word-map word)]
    (select-word next-word-map)))

(defn create-sentence [word-map word]
  (loop [sentence ""
         word word]
;    (println (str "*" word))
    (if word
      (if (or (= word "。") (= word "?") )
        sentence
        (recur (str sentence word) (select-next-word word-map word)))
      sentence)))

(defn init []
  (dosync
   (ref-set *words*
            (load-text "/home/satoshi/work/sample.txt"))))


サンプルの文章(sample.txt)

夏目漱石 「我輩は猫である」(青空文庫より)の最初の部分を使用した。

吾輩は猫である。
名前はまだ無い。
どこで生れたかとんと見当がつかぬ。
何でも薄暗いじめじめした所でニャーニャー泣いていた事だけは記憶している。
吾輩はここで始めて人間というものを見た。
しかもあとで聞くとそれは書生という人間中で一番獰悪な種族であったそうだ。
この書生というのは時々我々を捕えて煮て食うという話である。
しかしその当時は何という考もなかったから別段恐しいとも思わなかった。
ただ彼の掌に載せられてスーと持ち上げられた時何だかフワフワした感じがあったばかりである。
掌の上で少し落ちついて書生の顔を見たのがいわゆる人間というものの見始であろう。
この時妙なものだと思った感じが今でも残っている。
第一毛をもって装飾されべきはずの顔がつるつるしてまるで薬缶だ。
その後猫にもだいぶ逢ったがこんな片輪には一度も出会わした事がない。
のみならず顔の真中があまりに突起している。
そうしてその穴の中から時々ぷうぷうと煙を吹く。
どうも咽せぽくて実に弱った。
これが人間の飲む煙草というものである事はようやくこの頃知った。

実行結果

user> (in-ns 'ai.sentence)
#<Namespace ai.sentence>
ai.sentence> (init)
{"だ" {"と" 1, "。" 2}, "ニャーニャー" {"泣い" 1}, "一" {"度" 1, "毛" 1}, "何だか" {"フワフワ" 1}, "所" {"で" 1}, "ここ" {"で" 1}, "名前" {"は" 1}, "あっ" {"た" 2}, "
〜略〜
ai.sentence> (create-sentence @*words* "何")
"何というの飲む煙草という人間というのは何でも残って食うという考もだいぶ逢った"
ai.sentence> (create-sentence @*words* "猫")
"猫でニャーニャー泣いてまるで薬缶だと思った時何だかフワフワして書生のがない"
ai.sentence> (create-sentence @*words* "煙草")
"煙草というものを吹く"

# まさに、人工無能...

形態素を使っているので、n-gramを使用した場合より、まともな文章になっているが、文法に従った文生成をしていないため、意味不明な文になっている。
また、本来は、ある形態素の次の形態素を決めるときには、遷移確率を考慮しなければならないが、均等な確率としている(select-word関数のrand-nth関数)。
このような文字列を扱う処理は、C言語よりも圧倒的にClojureの方が書き易い。

2013年12月12日木曜日

[Clojure]トランザクションの最大リトライ回数

トランザクション内で、リファレンスの値の変更に失敗した場合は、トランザクションの最初から処理をリトライする。

トランザクションの処理に時間がかかり、何回繰り返してもリファレンスの値を更新できない場合は Live lock 状態になる。Clojureでは、これを防ぐため、リトライ回数がある一定値を越えると、例外を投げる仕組みになっている。

リトライ回数の最大値はどのくらいかなと、調べてみた。

(def x (ref 0))

(defn test1 []
 (dosync
  @(future (dosync (alter x inc)))
  (ref-set x -1)))


user> (test1)
RuntimeException Transaction failed after reaching retry limit  clojure.lang.Util.runtimeException (Util.java:219)
user> x
#<Ref@843d62: 10000>
user>

最大10000回もリトライしていた。
数十回程度かなと思っていたので、少しびっくり。
この値は変更できるのか、ざっと調べてみたが、変更方法は見付からなかった。
Clojure の STM のドキュメントのどこかに書いてあるのかな?

2013年12月7日土曜日

[Clojure]形態素解析ライブラリKuromojiを使う

オーム社の100周年記念セールで、はじめてのAIプログラミング C言語で作る人工知能と人工無能を購入した。2006年に出版された書籍で、C言語(Borland C)での実装が解説してある。
この類のプログラムをCで実装するのは煩雑になってしまうので、Clojureで作ったらどんなふうになるのかなと思い、文字列の解析時に使用する形態素ライブラリを調べてみた。
Lucene や Solr に対応したlucene-gosen が、結構使われているようだけど、mavenリポジトリにあるバージョンは少し古く、また、多くのライブラリに依存していており、それらのラブラリのバージョンも少し古かった。
その点、Kuromojiは、依存ライブラリがなく、lucene-gosenと同様に辞書も同梱されているので、こちらのライブラリを試してみた。

project.cljにKuromojiの設定を追加

Kuromojiをmavenで使うためには、リポジトリの追加が必要である。
project.cljに次の設定を書く。

:repositories [["Atilika Open Source repository"
                "http://www.atilika.org/nexus/content/repositories/atilika"]]
:dependencies [[[org.atilika.kuromoji/kuromoji "0.7.7"]]


リポジトリのURLの追加方法が最初分からず、いろいろ調べたが、
sample.project.cljのサンプルが参考になった。


サンプルコード

(ns gosen.core
  (:import (org.atilika.kuromoji Token Tokenizer)))

(defn -main []
  (let [tokenizer (. (Tokenizer/builder) build)]
    (doseq [token (. tokenizer tokenize "Javaより楽しいClojure。")]
      (println (str (. token getSurfaceForm) "\t"
                    (. token getAllFeatures))))))


何のことはない。Kuromojiのクラスを使う単純なコードだ。

実行結果

replより実行した。

gosen.core> (-main)
Java    名詞,固有名詞,組織,*,*,*,*
より    助詞,格助詞,一般,*,*,*,より,ヨリ,ヨリ
楽しい    形容詞,自立,*,*,形容詞・イ段,基本形,楽しい,タノシイ,タノシイ
Clojure    名詞,一般,*,*,*,*,*
。    記号,句点,*,*,*,*,。,。,。
nil

ユーザ辞書を追加することも簡単なようなので、試してみる予定。

参考

Java製形態素解析器「Kuromoji」を試してみる

2013年12月2日月曜日

[Clojure][Emacs]Clojure Cheatsheet for Emacs

EmacsでClojureのCheatsheetを閲覧できるELispがあった。
Clojure Cheatsheet for Emacs
試しに使ってみたら、結構便利。

インストール

Emacs24なら、MELPA経由で簡単にインストールできる。

Emacs初期化ファイルに以下のような設定を書いておけば良い。

;; MELPAを有効にする
(add-to-list 'package-archives '("melpa" . "http://melpa.milkbox.net/packages/") t)


サイトの説明通り、以下のコマンドでインストールする。
M-x package-refresh-contents
M-x package-install RET clojure-cheatsheet

実行

M-x clojure-cheatsheet を実行すると、
ミニバッファに
pattern:
と表示されるので、検索したい文字列を入力する。
sort mapを入力した場合は、次のように表示される。



キーバインドは次の通り。
C-p 前の行
C-n 次の行
RET 選択した項目の表示

clojure-mode時に有効になるような、キーバインドを書いておくと便利かも。
試していないが、Helmのsourceにも対応している。

2013年12月1日日曜日

[Haskell][Clojure]逆ポーランド記法の解析処理

Learn You a Haskell for Great Good で書かれていた逆ポーランド記法の解析処理をClojureで書いてみた。
四則演算のみサポートする単純な処理である。

Haskellの場合

module RPN where
       
solveRPN :: String -> Double
solveRPN = head . foldl func [] . words
    where
      func (x:y:ys) "+" = (y + x) : ys
      func (x:y:ys) "-" = (y - x) : ys
      func (x:y:ys) "*" = (y * x) : ys
      func (x:y:ys) "/" = (y / x) : ys
      func xs num = read num : xs

*RPN> solveRPN "1 2 + 3 * 1 - 2 /"
4.0
     
whereを使うとコードが分かり易くて、なかなか良いね。

Clojureの場合

(ns rpn.core
  (:use [clojure.string :only (split)]))

(defn words [s]
  (split s #"\s+"))

(defn op2 [[x y & ys] f]
  (conj ys (apply f [y x])))

(defn operate [stack item]
  (case item
    "+" (op2 stack +)
    "-" (op2 stack -)
    "*" (op2 stack *)
    "/" (op2 stack /)
    (conj stack (Double/parseDouble item))))

(defn solve-rpn [exprs]
  (first (reduce operate '() (words exprs))))

rpn.core> (solve-rpn "1 2 + 3 * 1 - 2 /")
4.0

solve-rpn関数の中でoperate関数を定義することも可能だが、かえって分かり難くなりそうなので、外出しして関数定義した。
Haskellに比べると冗長になってしまった。
もっと、すっきり書けるのかな?
文字列のdouble型への変換 (Double/parseDouble item) は美しくない。→と思ったときは parse-double関数を作れば良いのだけど。

2013年11月30日土曜日

[Debian][Haskell]WheezyにHaskell Platform最新版をインストール

Wheezyのghcは少しバージョンが古く、ghc-modをcabal installしたらエラーとなった。
どうしようもなかったので、Haskell Platformの最新版をインストールした。

依存ライブラリのインストール

次のパッケージをapt-get installしておく。
$ sudo apt-get install freeglut3-dev libgmp10-dev

このままだと、ghcのconfigure時に
checking for path to top of build tree... utils/ghc-pwd/dist/build/tmp/ghc-pwd: error while loading shared libraries: libgmp.so.3: cannot open shared object file: No such file or directory
と怒られるので、シンボリックリンクを張る。
$ sudo ln -s /usr/lib/i386-linux-gnu/libgmp.so.10 /usr/lib/libgmp.so.3

ghcのインストール

バイナリパッケージを使う。
http://www.haskell.org/ghc/download_ghc_7_6_3
より、32bit版をダウンロードする。
(私はWheezy 32bit版を使用している。)
http://www.haskell.org/ghc/dist/7.6.3/ghc-7.6.3-i386-unknown-linux.tar.bz2
展開して/usr/localにインストールする。
$ tar jxf ghc-7.6.3-i386-unknown-linux.tar.bz2
$ cd ghc-7.6.3
$ ./configure
$ sudo make install

Haskell platformのインストール

http://www.haskell.org/platform/linux.html
http://www.haskell.org/platform/download/2013.2.0.0/haskell-platform-2013.2.0.0.tar.gz
より、ソースをダウンロードする。
ghcと同様に、展開して/usr/localにインストールする。
$ tar zxf haskell-platform-2013.2.0.0.tar.gz
$ cd haskell-platform-2013.2.0.0
$ ./configure
$ make
コンパイルにはしばらく時間がかかる。
$ sudo make install

ghc-modのインストール

これで、
$ cabal update
$ cabal install ghc-mod
で、ghc-modがインストールできた。

2013年10月9日水曜日

[Clojure][Emacs] Windows環境のnreplで表示される^Mを消す

Windows環境でnreplを使うと、改行文字の^Mが表示されてしまい、とても目障りだ。

user> (dotimes [i 5] (println (str "hello" i)))
hello0^M ←◆これが目障り
hello1^M
hello2^M
hello3^M
hello4^M
nil
user>

Emacs Lispを使いbuffer-display-tableで^Mを表示しないように設定して、対処した。
もっと簡単な方法は無いのかな?

^Mを消すためのEmacs Lisp

(defun remove-dos-eol ()
  "Do not show ^M in files containing mixed UNIX and DOS line endings."
  (interactive)
  (setq buffer-display-table (make-display-table))
  (aset buffer-display-table ?\^M []))

(add-hook 'nrepl-repl-mode-hook
 'remove-dos-eol)

適用後

user> (dotimes [i 5] (println (str "hello" i)))
hello0 ← ^M が消えてスッキリ
hello1
hello2
hello3
hello4
nil
user> 

参考





2013年10月6日日曜日

[Clojure] clj-webdriverでChromeのUser-Agentを変更する方法(その2)

[Clojure] clj-webdriverでChromeのUser-Agentを変更する方法 でUser-Agentを変更する方法を書いたが、先日、最新のChromeとchromedriverを使ってみると、User-Agentが変更できなくなっていた。
原因を調べてみると、DesiredCapabilitiesオブジェクトにchrome.switchesを追加しても、Chromeの起動オプションに追加されなくなっていた。
起動オプションの追加方法が変更されたようで、ChromeOptions#addArgumentsを使うと問題なく動作した。

実行環境

  • Windows 8
  • clj-webdriver 0.6.0
  • chromedriver 2.4
chromedriver 2.4 はこちらからダウンロードした。
従来のダウンロード先にあったドライバは全てdeprecatedになっており、http://code.google.com/p/chromedriver/wiki/WheredAllTheDownloadsGo?tm=2 では、以下の説明があった。
Downloads have been moved to http://chromedriver.storage.googleapis.com/index.html, because Google Code downloads are being deprecated!

project.clj

次のライブラリをdependenciesに追加した。

[clj-webdriver "0.6.0"]
[org.seleniumhq.selenium/selenium-java "2.35.0"]

src/cli_webdriver_patch.clj

前回と同様に、clj-webdriver.coreの関数を再定義して対応する。

(ns clj-webdriver-patch)

(in-ns 'clj-webdriver.core)
(import 'org.openqa.selenium.chrome.ChromeOptions)
(declare new-chrome-driver)

(defn new-driver
  "Start a new Driver instance. The `browser-spec` can include `:browser`, `:profile`, and `:cache-spec` keys.
The `:browser` can be one of `:firefox`, `:ie`, `:chrome` or `:htmlunit`.
The `:profile` should be an instance of FirefoxProfile you wish to use.
The `:cache-spec` can contain `:strategy`, `:args`, `:include` and/or `:exclude keys. See documentation on caching for more details."
  ([browser-spec]
     (let [{:keys [browser profile chrome-switches cache-spec]
            :or {browser :firefox
                 profile nil
                 chrome-switches nil
                 cache-spec {}}} browser-spec]
       (if (= browser :chrome)
         (new-chrome-driver chrome-switches)
         (init-driver {:webdriver (new-webdriver* {:browser browser
                                                   :profile profile})
                       :cache-spec cache-spec})))))
(defn new-chrome-driver
  [chrome-switches]
  (let [option (ChromeOptions.)]
    ;; for Linux
    ;; (.setBinary option "chrome.binary" "/usr/bin/google-chrome")
    (if chrome-switches
      (.addArguments option (into-array chrome-switches)))
    (init-driver (ChromeDriver. option))))


src/chrometest/core.clj

サンプルコード。
User-AgentにiPhoneを設定し、googleで「hogehoge」を検索する。

(ns chrometest.core
  (:require [clj-webdriver.core])
  (:use clj-webdriver-patch)
  (:require [clj-webdriver.taxi :as taxi]))

(System/setProperty "webdriver.chrome.driver" "c:/Application/chromedriver/chromedriver-2.4.exe")

(def ^:dynamic *ua-iPhone-3G* "Mozilla/5.0 (iPhone; U; CPU iPhone OS 2_0_1 like Mac OS X; ja-jp) AppleWebKit/525.18.1 (KHTML, like Gecko) Version/3.1.1 Mobile/5B108 Safari/525.20")

(defn user-agent-switch [user-agent]
 (str "--user-agent=\"" user-agent "\""))

(defn test1 []
  (taxi/set-driver! {:browser :chrome
                     :chrome-switches [(user-agent-switch *ua-iPhone-3G*)]})
  (taxi/to "https://www.google.com/")
  (taxi/input-text "input[name='q']" "hogehoge")
  (taxi/click "button[name='btnG']"))


Debian Wheezyでの実行

chromedriverの最新版はglibc2.1.15に依存しており、glibcのバージョンを上げなければならない。
How to upgrade glibc from version 2.13 to 2.15 on Debian? にglibcのバージョンを上げる方法が書かれていたが、試していない。

2013年7月27日土曜日

[Emacs] 括弧内のハイライト表示

対応する括弧をハイライト表示する設定は以前から有効にしていたが、
括弧内をハイライト表示できるのは知らなかった。

;;; 対応する括弧をハイライトさせる
(show-paren-mode t)
; highlight entire bracket expression
(setq show-paren-style 'expression) ← ◆この設定


有効にすると一目で括弧の範囲が分かるので、結構便利。
下は options) の次にカーソルがある場合の表示。



ハイライトの色は変更できるのかな?

参考
How to Set Emacs's User Interface to Modern Conventions

2013年7月26日金曜日

[Ruby][Solr][PDF] PDF解析ライブラリを作成

PDF文書のテキスト抽出

Solrを使ってPDF文書の全文検索システムを作ろうかといろいろと調査中である。
Solr Cellを使うと、PDF文書やWord文書を簡単に取り込めるようだけど、ワードが含まれる場所(ページ番号)は関連付けされないようだ。
ページ番号が不明だと、対象となるPDF文書が分かっても、その文書を開いてから、そのワードを再検索しなければならない。それは面倒なので、ページ番号も一緒に取得できるようにして、コマンドラインから、ページ番号を指定して、PDF文書を開きたい。
まずは、PDF文書からページ単位でテキストを抽出する必要があるので、Rubyのpdf-reader を使い、手持ちの日本語のPDF文書を処理してみたが、最初のページは正しくテキストを抽出できたが、以降のページは文字化けし、正しくテキストを抽出できなかった。
Ubuntu12.04のXPDF(pdfinfo, pdftotextコマンド)では文字化けすることなくテキストを抽出できたので、これをラップしたRubyのライブラリを作成した。

ソースはこちらから。
https://github.com/takeisa/xpdf-ruby

サンプルコード

require './xpdf'

doc = XPDF::Reader.read('sample.pdf')

puts "Title: #{doc.title}"
puts "Author: #{doc.author}"
puts "PDF Version: #{doc.pdf_version}"

doc.pages.each do |page|
  puts page
end


何も難しいところはない。
XPDF::Document#pagesにページ毎に抽出したテキストを格納している。

参考

pdf-reader https://github.com/yob/pdf-reader

2013年6月19日水曜日

[Emacs][Racket] Geiserを使う

Realm of Racket を読みながら Racketを使い始めた。Racketは、標準でIDEを提供しており、面倒な環境構築しなくても、すぐにプログラムを実行できるようなっている。そのIDEを少し使ってみたが、キーバインドをEmacsに変更できないようなので、非常に使い難かった。調べてみると、Emacsで Geiser を使えば、Racketが使えることが分かった。

GeiserはSchemeインタープリタであるRacketまたはGuile用のメジャーモードを実現するもので、Slimeのようなインタラクティブ環境を利用可能になる。

インストール


実行環境

OS: Ubuntu12.04
Emacs: 24.3 (自分でmake,installしたもの)
Racket: 5.1.3(Ubuntu12.04標準)

Geiserのサイトの説明を見ると Racketのバージョンは5.3以上を推奨しているが、5.1.3でも一応動いた。
そのうちRacketを最新版にしよう。

Geiserのインストール

GeiserはELPAでインストールすると簡単だ。Marmaladeリポジトリからインス
トールできる。次のようにして、パッケージインストーラーがMarmaladeリポ
ジトリを参照できるようにする。

(require 'package)
;; Marmaladeを有効にする
(add-to-list 'package-archives '("marmalade" . "http://marmalade-repo.org/packages/") t)


package-installコマンドでインストールする。

M-x package-install RET geiser RET

geiserは ~/.emacs.d/elpa/geiser-0.3/ にインストールされる。
init.elに次の設定を追加する。

;;; Geiser
(add-to-list 'load-path "~/.emacs.d/elpa/geiser-0.3/")
(require 'geiser)


Geiserの起動

次のコマンドで起動する。

M-x run-geiser

「Start Geiser for scheme implementation: 」と聞いてくるので、
racketを入力する。
しばらく待つとREPLが起動する。

M-x run-geiser は毎回、どのschemeを使うか聞いてくるので、init.elに

(setq geiser-active-implementations '(racket))

を書いておけば、常にracketになる。



Mini bufferに関数の説明が出たり、TABでコード補完が効くので、Slime同様に、かなり便利だ。

http://www.nongnu.org/geiser/geiser_3.html#The-REPL によると、

  • swank-server/slime-connectのように、外部のschemeへ接続
  • 名前空間の切り替え (Racketはnamesapceを持っているようだ)
  • コンパイル時のエラーハンドリング (エラー箇所は色が変わるようだ)
  • ドキュメントの表示
  • イメージの表示 (Racketはイメージオブジェクトをサポートしているようだ)

と、様々な機能がある。
しばらくの間、この環境でRacketのコードを書いて遊ぼう。

参考URL

2013年6月15日土曜日

[Ruby][Scheme] Micro Schemeの実装(17) S式の表示

評価結果をRubyオブジェクトではなく、S式として表示できるようにした。
https://github.com/takeisa/uschemer2/tree/v0.03

リストの表示処理

通常のリスト表記とドット表記に対応させた。
SConsクラスのto_sメソッドを呼び出すと、リストを文字列として取得できる。
対応するSConsクラスのto_sメソッドは以下の通り。

  def to_s(need_paren = true)
    s = ""
    s << "(" if need_paren
    s << "#{@car.to_s}"
    if @cdr == SNil then
      # nop
    elsif @cdr.list? then
      s << " #{@cdr.to_s(false)}"
    else
      s << " . #{@cdr.to_s}"
    end
    s << ")" if need_paren
    s
  end


cdrがリスト※か、そうでないかによって、ドット表記を切り換える。
リストの場合は、括弧をつけずに続けて、次の要素を表示したいため、to_sの引数には、括弧が必要かどうかのフラグを持たせている。
リスト中の要素が自分のリストに含まれる要素を参照している場合は、無限ループとなってしまうが、これは後で修正しよう。

※SConsクラスの時にリストと判定している。cons?メソッドとした方が良かったかも。

実行例

$ ruby uschemer.rb
Micro Scheme
> (define (add a b) (+ a b))
#<Instruction::Closure:0x98295fc>
> (add 10 20)
30
>


 いままでは評価結果は内部で使用しているRubyオブジェクトをそのまま表示していたが、やっと、Scheme処理系らしくなってきた。

なお、リストの表示方法を書いたけど、まだリストは扱えない。
次はリスト処理関数をいくつか追加しよう。

2013年6月8日土曜日

[Ruby][Scheme] Micro Schemeの実装(16) defineを実装

defineを実装した。
https://github.com/takeisa/uschemer2/tree/v0.02

define命令の追加


Virutal machineにdefine命令を追加した。

命令説明
(define var)aレジスタのオブジェクトをシンボルvarで束縛する。

define式のコンパイル

define式は
(define var val)
(define (func arg0...) body)
の2種類の形式に対応する。

対応するRubyコードは以下の通り。

elsif symbol == :define then
  if exp.cdr.car.is_a?(SSymbol) then
    # (define var val)
    var = exp.cdr.car
    val = exp.cdr.cdr.car
    compile(val, Define.new(var, next_op))
  elsif list?(exp.cdr.car) then
    # (define (func arg0...) body)
    var = exp.cdr.car.car
    args = exp.cdr.car.cdr
    body = exp.cdr.cdr.car
    val = SCons.new(SSymbol.new(:lambda), SCons.new(args, SCons.new(body)))
    compile(val, Define.new(var, next_op))
  else
    raise "define syntax error"
  end

2番目の形式の場合は、
(define (func arg0...) body)

(define func (lambda (arg0...) body))
に変換し、再度コンパイルする。


実行例

$ ruby uschemer.rb                 
> (define (add a b) (+ a b)) ←◆ここでadd関数を定義
#<Instruction::Closure:0x96d8c98
 @body=
  #<Instruction::Frame:0x96d8cc0
   @ret=#<Instruction::Return:0x96d8d88>,
   @x=
    #<Instruction::Refer:0x96d8cd4
     @var=#<SSymbol:0x96d8e3c @value=:a>,
     @x=
      #<Instruction::Argument:0x96d8ce8
       @x=
        #<Instruction::Refer:0x96d8cfc
         @var=#<SSymbol:0x96d8e14 @value=:b>,
         @x=
          #<Instruction::Argument:0x96d8d10
           @x=
            #<Instruction::Refer:0x96d8d60
             @var=#<SSymbol:0x96d8e64 @value=:+>,
             @x=#<Instruction::Apply:0x96d8d74>>>>>>>,
 @env=
  #<Env:0x96d96e8
   @binds=
    [#<VarBind:0x96d96d4
      @bind=
       {:+=>#<Proc:0x96d9648@uschemer.rb:53 (lambda)>,
        :-=>#<Proc:0x96d95f8@uschemer.rb:54 (lambda)>,
        :*=>#<Proc:0x96d9594@uschemer.rb:55 (lambda)>,
        :/=>#<Proc:0x96d9530@uschemer.rb:56 (lambda)>,
        :add=>#<Instruction::Closure:0x96d8c98 ...>}>]>, ←◆define時の環境を持っている
 @vars=
  #<SCons:0x96d8ef0
   @car=#<SSymbol:0x96d8edc @value=:a>,
   @cdr=
    #<SCons:0x96d8ec8
     @car=#<SSymbol:0x96d8ea0 @value=:b>,
     @cdr=#<SNilClass:0x927bba0>>>>
> (add 10 20) ←◆ここでadd関数呼び出し
#<SNumber:0x96c2df8 @value=30> ← ◆30が返ってきた。

define式の評価後は、Virtual machineのaレジスタにクロージャのコンパイル結果が格納されているため、
上記のような表示となる。
式をVirtual machineの命令に変換し、関数呼び出しで、それが実行される。
自分で実装して、実際に動かしてみると、なかなか感動的で、かなり楽しい。

2013年6月6日木曜日

[Ruby][Scheme] Micro Schemeの実装(15) REPLを作成

REPLを作成し、コンソールから式を評価できるようにした。
https://github.com/takeisa/uschemer2/tree/v0.01

実行例

$ ruby uschemer.rb                
> (+ 1 2 3)
#<SNumber:0x9f53a08 @value=6>
> ((lambda (a b) (+ a b)) 10 20)
#<SNumber:0x9f58940 @value=30>
>

S式出力は、まだ整形しておらず、Rubyのオブジェクト出力のままだ。

数値、文字列、シンボルはRubyオブジェクトをそのまま使っていたが、
ラッパークラスを作成し、これらのオブジェクトはラッパークラス経由で使用するようにした。
シンボルはinternする仕組みを作っておらず、毎回オブジェクト生成しているので、リソースの無駄使いをしている。

defineが無いと不便なので、先にこちらを実装しよう。

2013年6月2日日曜日

[Ruby][Scheme] Micro Schemeの実装(14) Virtual machine方式に変更

いままで実装してきたインタプリタ方式で、末尾最適化や継続を実現するには、どのようにすれば良いのか、Webを検索したり、いろいろ考えていたが、これといった良い方法が思い付かなかった。
そこで、方針を変えて、Virtual Machine を使う方式に変更し、ごそごそやってできたのがこれ。

https://github.com/takeisa/uschemer2/tree/v0.00

Virtual machineとコンパイラを実装した。実装中にいろいろバグが出て、コンパイラのバグなのか、Virtual machineのバグなのか、分かり難かったりしたが、四苦八苦するのも、なかなか楽しい。ただ、適当に作ってしまったのでソースが非常に汚い。orz

Three Implementation Models for Scheme


Three Implementation Models for Scheme(3imp.pdfとして有名)というScheme処理系の実装方式の解説を読んだ結果、コンパイルしたSchemeコードをScheme用に最適化したVitrual machine上で実行する方式のほうが、インタプリタ方式よりも、末尾最適化や継続の実装が簡単そうだった。

VMを使う方式では、末尾最適化と継続は次のように実装できる。

末尾最適化
コンパイル時に、呼び出す関数が処理の末尾にあるか判定し、末尾の場合はコールフレームを生成せずに、関数を呼び出すコードを生成する。
継続
継続時点のスタックフレームを保存しておき、継続手続の呼び出しで、スタックフレームを復元後、値を渡す。

Virtual machine


いまのところ 3imp.pdf とほぼ同じ仕様だ。
備忘録をかねて書いておこう。

レジスタ


5つのレジスタを持つ。

レジスタ機能
aアキュムレータ
x次に実行する式
e現在の環境
r引数のリスト
s現在のスタックフレーム

命令セット


Virtual machineでサポートしている命令は以下の通り。

命令の中には、次に実行する命令を引数に取るものもあるが、以下では省略している。

命令説明
(halt)Virtual machineを停止する。aレジスタの値が評価結果となる。
(refer var)環境を参照し、変数varの値を取得し、aレジスタに設定する。
(constant obj)オブジェクトをaレジスタに設定する。
(test then else)aレジスタが非nilの場合はthenを実行し、nilの場合はelseを実行する。
(assign var)環境を参照し、変数varの値にaレジスタの値を設定する。
(conti)継続オブジェクトを生成する。
(nuate s var)スタックフレームsをsレジスタに設定し、変数varをaレジスタに設定する。
(frame ret)コールフレーム(戻り先retは次に実行する式として設定)を生成し、スタックフレームへ追加する。
(argument)aレジスタの値を、rレジスタに追加する。
(apply)クロージャまたはプリミティブ関数を評価する。
(return)スタックフレームのコールフレームより、フレーム生成前の状態にレジスタを戻す。

コンパイラ


式に応じてVirutal machineの命令を生成する。

コンパイル例


いくつかコンパイル例を示す。

変数aの参照 (refer a)
数値100 (constant 100)
(if pred "true" "false") (refer pred)
(test (constant "true") (constant "false"))
(+ 1 2) (frame)
(constant 1)
(argument)
(constant 2)
(argument)
(refer +)
(apply)
(return)

実行例

今はまだreplは無いので、rspec実行時のデバッグログ出力結果のみ。

クロージャ

context do
  it {
    op = compile('
(((lambda (a)
    (lambda (b) (+ a b))) 10) 20)
')
    res = @vm.eval(op)
    res.should eq 30
  }
end

(((lambda (a)
    (lambda (b) (+ a b))) 10) 20)
 -> (frame) ...
↓ここから下はVMが実行した命令
(frame)
(constant 20)
(argument)
(frame)
(constant 10)
(argument)
(close #<SCons:0x86e7d98> (close #<SCons:0x86e6754> (frame)))
(apply)
(close #<SCons:0x86e6754> (frame))
(return)
(apply)
(frame)
(refer a)
(argument)
(refer b)
(argument)
(refer +)
(apply)
(return)
(return)
(halt)

継続

context do
  it {
    op = compile('(+ 1 (call/cc (lambda (k) (k 3))))')
    res = @vm.eval(op)
    res.should eq 4
  }
end


(+ 1 (call/cc (lambda (k) (k 3)))) -> (frame) ...
↓ここから下はVMが実行した命令
(frame)
(constant 1)
(argument)
(frame)
(conti)
(argument)
(close #<SCons:0x9d1a96c> (frame))
(apply)
(frame)
(constant 3)
(argument)
(refer k)
(apply)
(nuate #<CallFrame:0x9d1a4d0> v)
(return)
(argument)
(refer +)
(apply)
(return)
(halt)



不足しているもの

末尾最適化
まだ実装していない。
define special form
VMの命令追加が必要だ。
REPL
REPLが無いと不便だ。

リファクタリング

メソッド内の最大インデントは一段まで、elseは使わない等の強い制約の元で実装することで、オブジェクト指向プログラミングがうまくなるらしい。
このルールに従ってリファクタリングしてみるのも、いろいろと得るものがありそうだ。

2013年5月29日水曜日

[Clojure] clj-webdriverでChromeのUser-Agentを変更する方法

clj-webdriverを利用すると、Clojureでブラウザを制御できる。プログラムでWebアプリの自動テストや、ブラウザの自動制御が簡単にできるので、便利に使っている。
clj-webdriverでは任意のブラウザを制御できるので、ChromeのUser-Agentを変更してスマホ用のWebアプリを制御しようとしたが、clj-webdriver 0.6.0 では、Chrome Driver へ Capability を渡すコードがコメントアウトされており、User-Agentの変更ができないようだった。
そこで、該当箇所の関数を再定義して、ChromeでUser-Agentを変更できるようにした。

clj-webdriver-patch.clj

 

関数を再定義するプログラムは以下の通り。

(require 'clj-webdriver.core)

(ns clj-webdriver.core
  (:use [clj-webdriver driver])
  (:import org.openqa.selenium.remote.DesiredCapabilities))

(declare new-chrome-driver)

(defn new-driver
 "Start a new Driver instance. The `browser-spec` can include `:browser`, `:profile`, and `:cache-spec` keys.
The `:browser` can be one of `:firefox`, `:ie`, `:chrome` or `:htmlunit`.
The `:profile` should be an instance of FirefoxProfile you wish to use.
The `:cache-spec` can contain `:strategy`, `:args`, `:include` and/or `:exclude keys. See documentation on caching for more details."
 ([browser-spec]
    (let [{:keys [browser profile chrome-switches cache-spec]
           :or {browser :firefox
                profile nil
                chrome-switches nil
                cache-spec {}}} browser-spec]
      (if (= browser :chrome)
        (new-chrome-driver chrome-switches)
        (init-driver {:webdriver (new-webdriver* {:browser browser
                                                  :profile profile})
                      :cache-spec cache-spec})))))

(defn new-chrome-driver
  [chrome-switches]
  (let [cap (DesiredCapabilities/chrome)]
    ;; for Linux
    (.setCapability cap "chrome.binary" "/usr/lib/chromium-browser/chromium-browser")
    (if chrome-switches
      (.setCapability cap "chrome.switches" (into-array chrome-switches)))
    (init-driver (ChromeDriver. cap))))



サンプルコード


User-Agentを iPhone-3G にするコードを以下に示す。

http://code.google.com/p/chromedriver/downloads/list から Chrome Driver をダウンロードし、任意の場所に解凍しておく。
Chrome Driver実行ファイルのパスは以下のコードの (System/setProperty 〜) で設定する。

(ns webdriver-test.core
  (:require [clj-webdriver.taxi :as taxi]))

;; Driver path
(System/setProperty "webdriver.chrome.driver" "/home/hogehoge/opt/chromedriver")
;; (System/setProperty "webdriver.ie.driver" "set ie driver path")

(def ^:dynamic *ua-iPhone-3G* "Mozilla/5.0 (iPhone; U; CPU iPhone OS 2_0_1 like Mac OS X; ja-jp) AppleWebKit/525.18.1 (KHTML, like Gecko) Version/3.1.1 Mobile/5B108 Safari/525.20")

(defn open-browser
  "Open browser."
  [browser]
  (taxi/set-driver! {:browser browser}))

(defn user-agent-switch [user-agent]
  (str "--user-agent=\"" user-agent "\""))

(defn open-chrome [url]
  (taxi/set-driver! {:browser :chrome
                     :chrome-switches [(user-agent-switch *ua-iPhone-3G*)]}
                    url))



(open-chrome "https://www.google.com/") を実行すると スマホ用のGoogleトップを表示できる。

2013年5月25日土曜日

[Ruby][Scheme] Micro Schemeの実装(13) スペシャルフォーム評価処理のクラス化

コードの見通しが悪くなってきたので、リファクタリングした。
https://github.com/takeisa/uschemer/tree/v0.12

スペシャルフォーム評価処理のクラス化


スペシャルフォーム毎に式を評価するクラスを作成した。
処理の概要は以下の通り。

スペシャルフォームの識別子と、それに対応する処理オブジェクトを定義する。

  SP_FORM_EVAL = {
    :lambda => LambdaEval.new,
    :let => LetEval.new,
    :letrec => LetrecEval.new,
    :define => DefineEval.new,
    :if => IfEval.new,
    :cond => CondEval.new,
    :and => AndEval.new,
    :or => OrEval.new,
    :not => NotEval.new
  }

スペシャルフォームを評価する時は、識別子に対応する処理オブジェクトを、このハッシュオブジェクトより取得し、式を評価するevalメソッドを呼び出す。
参考として、if式を評価するクラスを示す。

  class IfEval < BaseEval
    def eval(exp, env, exp_eval)
      test_form, then_form, else_form = if_to_test_then_else(exp)
      if exp_eval.eval(test_form, env) then
        exp_eval.eval(then_form, env)
      else
        exp_eval.eval(else_form, env)
      end
    end
   
    def if_to_test_then_else(exp)
      [exp[1], exp[2], exp[3]]
    end
  end

もっと良い構成にできそうだが、いくらか見通しが良くなったので、ここまでにしておこう。

S式のクラス化


プログラム中ではRubyのリストオブジェクトのまま扱っているので、
今のままでは、Consセルを実現できない。
こちらはConsセルが必要になるまで、後回しにしよう。

2013年5月22日水曜日

[Ruby][Scheme] Micro Schemeの実装(12) and,or,not式の評価

and,or,not式を評価できるようにした。
https://github.com/takeisa/uschemer/tree/v0.11

各式の仕様

and式

(and e1 e2 ... en)
式e1からenまで順に評価し、すべてが真の場合は、最後の式enの値を返す。
いずれかが偽の場合は falseを返す。

or式

(or e1 e2 ... en)
式e1からenまで順に評価し、真となった値を返す。
すべてが偽の場合は falseを返す。

not式

(not e)
式eが真の場合は falseを返す。
式eが偽の場合は trueを返す。

評価部分のコード

実装は仕様そのままで簡単だ。

and式の評価

    def eval_and(exp, env)
      exp_list = and_to_exp_list(exp)
      last_exp = nil
      exp_list.each do |exp|
        last_exp = eval(exp, env)
        return false unless last_exp
      end
      last_exp
    end

    def and_to_exp_list(exp)
      exp[1..-1]
    end


or式の評価

    def eval_or(exp, env)
      exp_list = or_to_exp_list(exp)
      exp_list.each do |exp|
        last_exp = eval(exp, env)
        return last_exp if last_exp
      end
      false
    end

    def or_to_exp_list(exp)
      exp[1..-1]
    end


not式の評価

    def eval_not(exp, env)
      exp = not_to_exp(exp)
      not eval(exp, env)
    end

    def not_to_exp(exp)
      exp[1]
    end



リファクタリング

式の種別に応じて、対応する評価メソッドを呼び出す部分は以下の通り。

    def eval_special_form(exp, env)
      if lambda?(exp) then
        eval_lambda(exp, env)
      elsif let?(exp) then
        eval_let(exp, env)
      elsif if?(exp) then
        eval_if(exp, env)
      elsif letrec?(exp) then
        eval_letrec(exp, env)
      elsif define?(exp) then
        eval_define(exp, env)
      elsif cond?(exp) then
        eval_cond(exp, env)
      elsif and?(exp) then
        eval_and(exp, env)
      elsif or?(exp) then
        eval_or(exp, env)
      elsif not?(exp) then
        eval_not(exp, env)
      end
    end


うーむ。汚ないコードだ。リファクタリングしたい。
Strategyパターンを適用して、それぞれのスペシャルフォームをクラス化すると、すっきりするかな?

2013年5月21日火曜日

[Ruby][Scheme] Micro Schemeの実装(11) 四則演算で3個以上の引数に対応

前回 「-」関数を3個以上に引数に対応させたが、
その他の「+」、「*」、「/」関数も同様に対応させた。
https://github.com/takeisa/uschemer/tree/v0.10

四則演算部分のコード

  FUNCS = {
    :+ => [:primitive, lambda {|*xs| xs.reduce(0) {|a, x| a + x}}],
    :- => [:primitive, lambda {|*xs| if xs.size == 1 then -xs[0] else xs.reduce {|a, x| a - x} end}],
    :* => [:primitive, lambda {|*xs| xs.reduce(1) {|a, x| a * x}}],
    :'/' => [:primitive, lambda {|*xs| if xs.size == 1 then 1 / xs[0] else xs.reduce {|a, x| a / x} end}],
    ..snip..
  }


RSpecでテストファースト

コードが増えてくると、機能の追加や修正で、デグレしやすくなる。
今回からRubyのテスティングフレームワークであるRSpecを使い、テストファーストで実装した。

以下は「+」関数のテストケース。
結構、分かりやすいコードになる。

describe '+ operator' do
  before do
    @env = [USchemeR::KEYWORDS, USchemeR::FUNCS]
  end

  context 'one parameter' do
    it { eval("(+ 1)", @env).should eq 1 }
  end

  context 'two parameters' do
    it { eval("(+ 1 2)", @env).should eq 3 }
  end

  context 'many parameters' do
    it { eval("(+ 1 2 3 4 5)", @env).should eq 15 }
  end
end


テストファーストで実装すると、NGだったテストがOKになるときに、気持ち良さがあり、ちょっとしたコードの実装でも、なかなか楽しい。
本当は、このような上位レベルのテストコードにするのではなく、NGになったときに、原因が明確になるように、機能の対象となる部分のテストコードを書くべきなんだろうけど、まずはこれで良しとしよう。

参考

Rubyist Magazine 改めて学ぶ RSpec
とても分かり易くまとまっているのでおすすめ。

2013年5月19日日曜日

[Ruby][Scheme] Micro Schemeの実装(10) cond式の評価

cond式を使えるようにした。
https://github.com/takeisa/uschemer/tree/v0.09

cond式の評価

(cond ([p1] [e2])
      ([p2] [e2])
      ...
      ([pn] [en])
      (else [e-else])


条件式をp1→pnの順に評価する。
条件式pnが真の場合、対応する式enを結果とする。
いずれの条件式も成立しなかった場合、elseに対応するen-elseを結果とする。
elseは省略可。
else省略時に条件が一つも成立しなかった場合は例外を出すようにしておこう。

対応するコードは以下の通り。

def eval_cond(exp, env)
  pred_exp_list = cond_to_pre_exp_list(exp)
  pred_exp_list.each do |pred_exp|
    pred, exp = pred_exp
    if pred == :else || eval(pred, env) then
      return eval(exp, env)
    end
  end
  raise "cond: not match conditions"
end

def cond_to_pre_exp_list(exp)
  exp[1..-1]
end




abs関数

condの使用例として、数値の絶対値を求めるabs関数を定義する。

(define (abs x)
  (cond ((< x 0) (- x))
        ((= x 0) 0)
        (else x)))


(- x)に対応していなかったので、引数が一つの場合に、符号を反転できるように、「-」関数を以下のように修正した。

引数が一つの場合
  (- 10) ; => -10
引数が複数の場合
  (- 1 2 3) ;=> -4

「-」関数のコードは以下のとおり。
  :- => [:built_in, lambda {|*x| if x.size == 1 then -x[0] else x.reduce {|a, x| a - x}}]

reduceの初期値を0にすれば、引数の個数の判定処理は不要なので、
  :- => [:built_in, lambda {|*x| x.reduce(0) {|a, x| a - x}}]
でOK。
2013/5/20 全然OKじゃないことに気が付いた。後の方法では、(- 2 1) は -3 になってしまう。


実行結果

(define (abs x)
  (cond ((< x 0) (- x))
        ((= x 0) 0)
        (else x)))
 ;=> [:abs,
 [:closure,
  [:x],
  [:cond, [[:<, :x, 0], [:-, :x]], [[:"=", :x, 0], 0], [:else, :x]],
  [{:abs=>[...]},
   {:true=>true, :false=>false},
   {:+=>
     [:built_in,
      #<Proc:0x85e051c@/home/satoshi/workspace/uschemer/uschemer.rb:10 (lambda)>],
    ..snip..
    :>==>
     [:built_in,
      #<Proc:0x85e03dc@/home/satoshi/workspace/uschemer/uschemer.rb:18 (lambda)>]}]]]

(abs -10)
 ;=> 10

(abs 0)
 ;=> 0

(abs 10)
 ;=> 10


if は condを使ったマクロで実装したい。
その前に、リスト処理をする関数がいくつか必要だ。

2013年5月18日土曜日

[Ruby][Scheme] Micro Schemeの実装(9) Parserの改良 - 文字列に対応

へなちょこパーサを廃止し、文字列を扱えるようにパーサを実装した。
https://github.com/takeisa/uschemer/tree/v0.08

Lexerの実装

前回作成したTokenizerクラスで処理するトークンを定義する。
Lexerでは、一行毎にトークン分割をして、結果を配列に格納しておく。
get_tokenメソッドで、読み込んだトークンを一つを返す。
返すトークンが無い場合は、read_tokensメソッドを呼び出し、一行分のトークンを取得する。
unget_tokenメソッドで読み出したトークンを元の配列へ戻す。
これは、トークンを取得して、リストの最後の「)」トークンか判定し、違った場合に元に戻して、
リストのパースを継続するためである。

class Lexer
  def initialize(stream)
    @stream = stream
    @tokens = []

    @tokenizer = Tokenizer.new do |t|
      t.match(/\s+/) do |val|
        # skip
      end

      t.match(/(?:(?:-?[1-9][0-9]*)|0)(?:\.[0-9]+)?/) do |val|
        Token.new(:numeric, eval(val))
      end

      t.match(/"([^"]*)"/) do |val|
        Token.new(:string, val[1..-2])
      end

      t.match(/\(|\)/) do |val|
        Token.new(val.to_sym)
      end

      t.match(/[^\s\(\)]+/) do |val|
        Token.new(:ident, :"#{val}")
      end
    end
  end

  def get_token
    if @tokens.empty? then
      read_tokens
    end
    @tokens.shift
  end

  def read_tokens
    while @tokens.empty?
      line = @stream.readline.chomp
      next if line.empty?
      @tokens = @tokenizer.scan(line)
    end
  end

  def unget_token(token)
    @tokens.unshift(token)
  end
end


Parserの実装

S式のパースなので、非常に簡単だ。
以下のようにS式、リスト、アトムを定義し、再帰下降パーサとして実装した。
S式 := リスト || アトム
リスト := ( S式* )
アトム := 数値 || 文字列 || 識別子

class Parser
  def initialize(lexer)
    @lexer = lexer
  end

  def parse
    parse_sexp
  end

  def parse_sexp
    parse_list || parse_atom
  end

  def parse_list
    token = @lexer.get_token
    unless token.type == :'('
      @lexer.unget_token(token)
      return nil
    end
    list = []
    while TRUE
      token = @lexer.get_token
      if token.type == :')' then
        return list
      end
      @lexer.unget_token(token)
      list.push(parse_sexp)
    end
    list
  end

  def parse_atom
    token = @lexer.get_token
    token.value
  end
end



Parserのテスト

次のコードを実行する。
print Parser.new(Lexer.new(STDIN)).parse
(define (hello) ←入力
"hello") ←入力
[:define, [:hello], "hello"] ← 結果

うまく動いた。

Micro Scheme本体の修正

今回実装したパーサに差し替え、文字列を評価できるようにした。
実行例は以下の通り。

(define (hello) "hello, world!")
 ;=> [:hello,
 [:closure,
  [],
  "hello, world!",
  [{:hello=>[...]},
   {:true=>true, :false=>false},
   {:+=>
     [:built_in,
      #<Proc:0x879dcb0@/home/satoshi/workspace/uschemer/uschemer.rb:10 (lambda)>],
    ...snip...
    :>==>
     [:built_in,
      #<Proc:0x879db70@/home/satoshi/workspace/uschemer/uschemer.rb:18 (lambda)>]}]]]


(hello)
 ;=> "hello, world!"



そろそろテストコードが必要になってきた。
やっぱりRSpecあたりで書くのが順当かな。

[Ruby][Scheme] Micro Schemeの実装(9) Parserの改良 - Tokenizerの実装


今のParserは文字列を認識できないため、改良することにした。

冗長なコード

コードを1行ずつ読み込み、トークン分割する部分を書いていたが、以下のコードのように、冗長になってしまい、あまり美しくない。

scanner = StringScanner.new(line)
until scanner.eos?
  scanner.scan(/\s+/)

  value = scanner.scan(/-?[1-9][0-9]*(?:\.[0-9]+)?/)
  if val then
    @tokens.push Token.new(:numeric, eval(value))
    next
  end

  value = scanner.scan(/"([^"]*)"/)
  if val then
    @tokens.push Token.new(:string, value[1..-2])
    next
  end

  value = scanner.scan(/\(|\)/)
  if val then
    @tokens.push Token.new(:"#{value}")
    next
  end

  value = scanner.scan(/[^\s\(\)]+/)
  if val then
    @tokens.push Token.new(:ident, :"#{value}")
    next
  end

  raise "Invalid token error: #{line}"
end



DSL的に

もう少しDSL的に書けるかなと思い、トークン分割するクラスを作ってみた。

次のようなコードで書けるようになった。

tokenizer = Tokenizer.new do |t|
  t.match(/\s+/)                        {} # skip
  t.match(/-?[1-9][0-9]*(?:\.[0-9]+)?/) { |val| "numeric:" + val }
  t.match(/"([^"]*)"/)                  { |val| "string:" + val[1..-2] }
  t.match(/\(|\)/)                      { |val| "symbol:" + val }
  t.match(/[^\s\(\)]+/)                 { |val| "ident:" + val }
end


p tokenizer.scan('(one 2 "three" 4.5)')
# => ["symbol:(", "ident:one", "numeric:2", "string:three", "numeric:4.5", "symbol:)"]


おぉ。ちょっと、すっきり♪


作成したTokenizerクラス


コード

require 'strscan'

class Tokenizer
  def initialize
    @pattern_operations = []
    yield self if block_given?
  end

  def match(pattern, &operation)
    @pattern_operations.push [pattern, operation]
  end

  def scan(string)
    @tokens = []
    scanner = StringScanner.new(string)
    until scanner.eos?
      matched = false
      @pattern_operations.each do |pattern_operaion|
        pattern, operation = pattern_operaion
        val = scanner.scan(pattern)
        if val then
          token = operation.call(val)
          @tokens.push(token) if token
          matched = true
          break
        end
      end
      unless matched
        raise "invalid token error"
      end
    end
    @tokens
  end
end


説明

(1)コンストラクタで自分自身をyieldして、ブロックで定義できるようにする。
Metaprogramming Rubyでは 自己Yield と呼んでいる。
(2)matchメソッドが呼ばれる度に、トークンにマッチさせるパターンと、そのブロックをリストに積む。
(3)scanメソッドでは解析する文字列を受け取り、(2)で記録したパターンを順次適用し、一致した場合に、対応するブロックを実行する。
(4)ブロックが返す結果をトークンとして配列に積む。
(5)すべて文字列の処理を完了で、トークンの配列を返す。
(6)処理できないトークンの場合はエラー。

次はこのクラスを使って、LexerとParserを作成しよう。

2013年5月16日木曜日

[Ruby][Scheme] Micro Schemeの実装(8) ちょっと脱線 Y Combinator

Y Combinatorについて理解した(つもり)。まとめ。

Y Combinatorとは

以下のブログが非常に分かりやすかった。感謝!

関数を引数にとり、新しい関数を返す関数Fとする。
FをY Combinatorに適用すると、再帰関数fができる。
この再帰関数fは最初の関数Fの不動点である。
不動点であるため、この再帰関数fを関数Fに適用すると再帰関数fができる。
これで関数で再帰できることになる。
関数の引数として受け取った関数で再帰できるので、関数の名前が不要である。
無名再帰ともいうようだ。

と書いていて、本当に理解したのか怪しくなってくるなぁ...

Y Combinatorの求め方

Y Combinatorの求め方は次のブログが参考になった。
こちらにも感謝!
Y Combinator
http://www.loveruby.net/ja/misc/ycombinator.html

自分なりにまとめ直すと、以下の通り。

階乗を求める関数を元に、Y Combinatorを使って名前の定義を不要にするまで。

まずは階乗を求める関数。

(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))

(fact 10) ; => 3628800

階乗を求める関数を作る関数。

(define fact-maker
  (lambda ()
    (lambda (n)
      (if (= n 0)
          1
          (* n ((fact-maker) (- n 1)))))))

((fact-maker) 10) ; => 3628800

(fact-maker)を一番外側のlambdaの仮引数fで受け取るようにする。
再帰時には自分自身を渡さなくてはならないので (f f)となる。

(define fact-maker
  (lambda (f)
    (lambda (n)
      (if (= n 0)
          1
          (* n ((f f) (- n 1)))))))

((fact-maker fact-maker) 10) ; => 3628800

(f f) を f と書きたい。
((f f) arg) は ((lambda (arg) ((f f) arg)) arg) と同じ。

置換すると

(define fact-maker
  (lambda (f)
    (lambda (n)
      (if (= n 0)
          1
          (* n ((lambda (arg) ((f f) arg)) (- n 1)))))))

fact0を以下のようにおき、(lambda (arg) ((f f) arg)) を 渡すようにすれば

(define fact0
  (lambda (f)
    (lambda (n)
      (if (= n 0)
          1
          (* n (f (- n 1)))))))

(define fact-maker
  (lambda (f)
    (fact0 (lambda (arg) ((f f) arg)))))

となる。

ここで f を g に置き換えると

(define fact-maker
  (lambda (g)
    (fact0 (lambda (arg) ((g g) arg)))))

となる。

よって、

(fact-maker fact-maker)

は、以下の式となる。

((lambda (g)
   (fact0 (lambda (arg) ((g g) arg))))
 (lambda (g)
   (fact0 (lambda (arg) ((g g) arg)))))

fact0を外に出すと

(lambda (f)
 ((lambda (g)
    (f (lambda (arg) ((g g) arg))))
  (lambda (g)
    (f (lambda (arg) ((g g) arg))))))

となる。
これが Yコンビネータ。

(define Y
  (lambda (f)
    ((lambda (g)
       (f (lambda (arg) ((g g) arg))))
     (lambda (g)
       (f (lambda (arg) ((g g) arg)))))))

(define fact
  (lambda (f)
    (lambda (n)
      (if (= n 0)
          1
          (* n (f (- n 1)))))))

((Y fact) 10) ; => 3628800

Micro Schemeで実行

現在、作成中の Micro Scheme で実行してみる。

(define Y
  (lambda (f)
    ((lambda (g)
       (f (lambda (arg) ((g g) arg))))
     (lambda (g)
       (f (lambda (arg) ((g g) arg)))))))
 ;=> [:Y,
 [:closure,
  [:f],
  [[:lambda, [:g], [:f, [:lambda, [:arg], [[:g, :g], :arg]]]],
   [:lambda, [:g], [:f, [:lambda, [:arg], [[:g, :g], :arg]]]]],
  [{:Y=>[...]},
   {:true=>true, :false=>false},
   {:+=>[:built_in, #<Proc:0x8d520c0@uschemer.rb:8 (lambda)>],
    :-=>[:built_in, #<Proc:0x8d52098@uschemer.rb:9 (lambda)>],
    :*=>[:built_in, #<Proc:0x8d52070@uschemer.rb:10 (lambda)>],
    :/=>[:built_in, #<Proc:0x8d52048@uschemer.rb:11 (lambda)>],
    :"="=>[:built_in, #<Proc:0x8d52020@uschemer.rb:12 (lambda)>],
    :<=>[:built_in, #<Proc:0x8d51ff8@uschemer.rb:13 (lambda)>],
    :>=>[:built_in, #<Proc:0x8d51fd0@uschemer.rb:14 (lambda)>],
    :<==>[:built_in, #<Proc:0x8d51f6c@uschemer.rb:15 (lambda)>],
    :>==>[:built_in, #<Proc:0x8d51f44@uschemer.rb:16 (lambda)>]}]]]


(define fact
  (lambda (f)
    (lambda (n)
      (if (= n 0)
          1
          (* n (f (- n 1)))))))
 ;=> [:fact,
 [:closure,
  [:f],
  [:lambda, [:n], [:if, [:"=", :n, 0], 1, [:*, :n, [:f, [:-, :n, 1]]]]],
  [{:fact=>[...]},
   {:Y=>
     [:closure,
      [:f],
      [[:lambda, [:g], [:f, [:lambda, [:arg], [[:g, :g], :arg]]]],
       [:lambda, [:g], [:f, [:lambda, [:arg], [[:g, :g], :arg]]]]],
      [...]]},
   {:true=>true, :false=>false},
   {:+=>[:built_in, #<Proc:0x8d520c0@uschemer.rb:8 (lambda)>],
    :-=>[:built_in, #<Proc:0x8d52098@uschemer.rb:9 (lambda)>],
    :*=>[:built_in, #<Proc:0x8d52070@uschemer.rb:10 (lambda)>],
    :/=>[:built_in, #<Proc:0x8d52048@uschemer.rb:11 (lambda)>],
    :"="=>[:built_in, #<Proc:0x8d52020@uschemer.rb:12 (lambda)>],
    :<=>[:built_in, #<Proc:0x8d51ff8@uschemer.rb:13 (lambda)>],
    :>=>[:built_in, #<Proc:0x8d51fd0@uschemer.rb:14 (lambda)>],
    :<==>[:built_in, #<Proc:0x8d51f6c@uschemer.rb:15 (lambda)>],
    :>==>[:built_in, #<Proc:0x8d51f44@uschemer.rb:16 (lambda)>]}]]]


((Y fact) 10)
 ;=> 3628800

おーーー。動いた。
ちょっと感動...

2013年5月14日火曜日

[Ruby][Scheme] Micro Schemeの実装(7) defineの評価

defineを使って、変数や関数を定義できるようにした。
https://github.com/takeisa/uschemer/tree/v0.07

defineの構文

以下の二つの構文に対応する。
(1)第一引数に変数、第二引数に値を指定する形式
(define id (lambda (x) ...))
(2)第一引数に関数名と仮引数のリスト、第二引数に関数本体を指定する形式
(define (id x) (...))

変数と値の束縛

変数をdefineで定義する際に、変数が束縛されているかどうかによって、以下のように処理する。
(1)束縛されている場合
束縛されている変数の値をdefineで指定した値に設定する。
(2)束縛されていない場合
defineで指定した変数と値の束縛を環境に作る。

(1)と(2)のどちらにも対応するというのが嫌な仕様だな。
例えば、
(define fuga ...) ...(a)
(define hoge ...
  (define fuga ...)) ...(b)
この場合、(b)のdefineは、(a)でfugaが定義されているため、上書きされる。
(a)がなければ、hoge内のローカルとなる。
ということは、ローカルのつもりで変数を定義していても、間違って外側でdefineしてしまうと、そちらを参照してしまい、良く分からないバグの原因になりそうだ。
そもそも、defineはこの仕様で正しいのかな?

実行例

フィボナッチ数を求める関数を定義してみた。

(define (fib n)
  (if (<= n 2)
      1
      (+ (fib (- n 2)) (fib (- n 1)))))
 #=> [:fib,
 [:closure,
  [:n],
  [:if, [:<=, :n, 2], 1, [:+, [:fib, [:-, :n, 2]], [:fib, [:-, :n, 1]]]],
  [{:fib=>[...]},
   {:fact=>
     [:closure,
      [:n],
      [:if, [:"=", :n, 0], 1, [:*, :n, [:fact, [:-, :n, 1]]]],
      [...]]},
   {:one=>1},
   {:true=>true, :false=>false},
   {:+=>[:built_in, #<Proc:0x931b574@uschemer.rb:8 (lambda)>],
    :-=>[:built_in, #<Proc:0x931b54c@uschemer.rb:9 (lambda)>],
    :*=>[:built_in, #<Proc:0x931b4fc@uschemer.rb:10 (lambda)>],
    :/=>[:built_in, #<Proc:0x931b4d4@uschemer.rb:11 (lambda)>],
    :"="=>[:built_in, #<Proc:0x931b4ac@uschemer.rb:12 (lambda)>],
    :<=>[:built_in, #<Proc:0x931b484@uschemer.rb:13 (lambda)>],
    :>=>[:built_in, #<Proc:0x931b45c@uschemer.rb:14 (lambda)>],
    :<==>[:built_in, #<Proc:0x931b434@uschemer.rb:15 (lambda)>],
    :>==>[:built_in, #<Proc:0x931b40c@uschemer.rb:16 (lambda)>]}]]]


(fib 15)
 #=> 610

正しく計算できた。これは楽しい!

2013年5月11日土曜日

[Ruby][Scheme] Micro Schemeの実装(6) letrec式の評価

letrec式を評価できるようにし、再帰呼び出しが可能になった。
https://github.com/takeisa/uschemer/tree/v0.06

let式での再帰呼び出し

階乗を求めるコードの例
(let ((fact
      (lambda (x) (if (= x 0)
                      1
                      (* x (fact (- x 1))))))) ← ◆このfactは参照できない
  (fact 5))           

外側のletで自分自身を変数に束縛しても、lambda式を評価してクロージャを生成した時の環境と、クロージャの仮引数と引数の束縛を使って、クロージャ本体を評価するため、クロージャ本体からは、その変数で自分自身を参照できない。

letrec式での再帰呼び出し

(letrec ((fact
         (lambda (x) (if (= x 0)
                         1
                         (* x (fact (- x 1))))))) ← ◆このfactを参照可にする
  (fact 5))           

factを参照できるようにするために、letrecは次のように評価する。
(1)letrecの束縛定義に従い、変数と、lambda式を評価した結果のクロージャの束縛を作成する。
(2)環境にその束縛を追加する。
(3)(1)のクロージャそれぞれの環境に(1)で作成した束縛を追加する。
(4)letrec本体を評価する。

書籍(http://tatsu-zine.com/books/scheme-in-ruby)の実装とは違うが、
この方式だと何か問題があるのかな?

実行結果

10の階乗

(letrec ((fact
         (lambda (x)
                 (if (= x 0)
                     1
                     (* x (fact (- x 1)))))))
  (fact 10))
 #=> 3628800

100の階乗

(letrec ((fact
         (lambda (x)
                 (if (= x 0)
                     1
                     (* x (fact (- x 1)))))))
  (fact 100))
 #=> 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

再帰呼び出しで、正しく計算できた。
少しずつ出来ることが増えてきて、なかなか楽しい。

[Ruby][Scheme] Micro Schemeの実装(5) if式の評価

if式を評価できるようにし、比較関数を追加した。
https://github.com/takeisa/uschemer/tree/v0.05

if式

if式の構文は以下の通り。
(if test-form then-form else-form)

test-formを評価し、その結果に応じて以下の処理を行う。
真の場合 → then-formの評価結果を返す
偽の場合 → else-formの評価結果を返す

この処理のRubyコードの一部示す。
    def eval_if(exp, env)
      test_form, then_form, else_form = if_to_test_then_else(exp)
      if eval(test_form, env) then
        eval(then_form, env)
      else
        eval(else_form, env)
      end
    end

if式の動作を、そのまま実装したコードで、とても簡単だ。

trueとfalse

trueとfalseが使えるように、
  KEYWORDS = {
    :true => true,
    :false => false
  }
を定義し、環境に追加した。

比較関数の定義

ifが使えるようになったので、比較関数 =, <, >, <=, >=, /= を定義した。
  FUNCS = {
    〜略〜
    :< => [:built_in, lambda {|x, y| x < y}],
    :> => [:built_in, lambda {|x, y| x > y}],
    〜略〜
  }

実行例

eval_print("(if true 1 2)")
(if true 1 2) #=> 1

eval_print("(if false 1 3)")
(if false 1 3) #=> 3

eval_print("(if (< 1 2) 1 2)")
(if (< 1 2) 1 2) #=> 1

eval_print("(if (> 1 2) 1 3)")
(if (> 1 2) 1 3) #=> 3

2013年5月9日木曜日

[Ruby][Scheme] Micro Schemeの実装(4) S式パーサの実装

Rubyのリスト形式でSchemeプログラムを書くのは大変なので、S式のパーサを作成した。
https://github.com/takeisa/uschemer/tree/v0.04

パーサの実装

作成中のMicro Schemeは、Rubyの配列でS式を表現している。
S式をRubyの配列形式になるように文字列置換し、Kernel.evalすればS式の配列表現を得ることができる。

    def parse(sexp)
      sexp.gsub!(/[_a-zA-Z\+\*\-\/][_a-zA-Z0-9\+\*\-\/]*/, ':\\0')
      sexp.gsub!(/\s+/, ',')
      sexp.gsub!(/\(/, '[')
      sexp.gsub!(/\)/, ']')
      Kernel.eval(sexp)
    end

まだ文字列は扱わないので、すごく単純だ。


実行例

eval_print("(let ((a 1) (b 1)) (+ a b))", env)
(let ((a 1) (b 1)) (+ a b)) #=> 2

eval_print("(let ((a 1)) (lambda (x) (+ a x)))", env)
(let ((a 1)) (lambda (x) (+ a x))) #=> [:closure,
 [:x],
 [:+, :a, :x],
 [{:a=>1},
  {:+=>[:built_in, #<Proc:0x9e7fec4@uschemer.rb:6 (lambda)>],
   :-=>[:built_in, #<Proc:0x9e7fe9c@uschemer.rb:7 (lambda)>],
   :*=>[:built_in, #<Proc:0x9e7fe4c@uschemer.rb:8 (lambda)>],
   :/=>[:built_in, #<Proc:0x9e7fe10@uschemer.rb:9 (lambda)>]}]]

eval_print("((let ((a 1)) (lambda (x) (+ a x))) 2)", env)
((let ((a 1)) (lambda (x) (+ a x))) 2) #=> 3

やっとLispらしくなってきた。