文字列を任意の文字列で分割するには、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月29日日曜日
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版が無いので、ソースからインストールした。
現在は 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 自身にインストールされる。
Emacsとの連携
http://docs.racket-lang.org/guide/Emacs.html を見ると Emacsのmajorモードもあるようなので、後で試してみよう。
参考
書中では、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のソースを検索できるようにしよう。
gem でインストールできる。
rroonga(groongaのRuby用API)
$ gem install rroonga
$ gem install milkode
これでmilkコマンドが使えるようになる。
create : /home/satoshi/.milkode/milkode.yaml
create : /home/satoshi/.milkode/db/milkode.db created.
$ mkdir src
$ cd src
$:~/src git clone https://github.com/clojure/clojure.git
package : clojure
result : 1 packages, 279 records, 279 add. (1.56sec)
*milkode* : 1 packages, 279 records in /home/satoshi/.milkode/db/milkode.db.
clojure ← ◆登録された
*milkode* : 1 packages, 279 records in /home/satoshi/.milkode/db/milkode.db.
$:~/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を参照。
$ milk web
デフォルトではブラウザを起動する。
ブラウザを起動せずに、外部からの接続を許可した状態で起動するには、以下のコマンドを実行する。
$ milk web -n -o 0.0.0.0
詳細は milk help web コマンドを参照。
次は検索結果の画面。
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 を付けないと正しく検索できなかった。カレントディレクトリがソースのディレクトリ内ではないから？)
結構な規模で、ファイル数が多く、grepによる検索では非常に時間がかかり、効率が悪い。
Milkodeは全文検索エンジンgroongaを使った、ソースコード検索用のツールで、数万ファイルを対象にしても、瞬時に検索できる。
Webアプリとしても動作し、ブラウザを使って検索もできる。
検索するソースの追加も簡単なので、重宝している。
Clojureのソースを検索できるようにしよう。
インストール
MilodeはRubyアプリである。gem でインストールできる。
rroonga(groongaのRuby用API)
$ gem install rroonga
$ gem install milkode
これでmilkコマンドが使えるようになる。
データベースの作成
$ milk init --defaultcreate : /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 clojurepackage : clojure
result : 1 packages, 279 records, 279 add. (1.56sec)
*milkode* : 1 packages, 279 records in /home/satoshi/.milkode/db/milkode.db.
登録したプロジェクトの確認
$ milk listclojure ← ◆登録された
*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]
$ gem install rouge-lang
REPLを起動するには rougeコマンドを使う。
$ rouge
Rouge 0.0.15
user=>
ついついprintlnとやってしまいそうになるが、putsでhello。
user=> (puts "hello, Rouge!")
hello, Rouge!
nil
user=> ^Dで終了
$ gem install 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
(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) ;; ブラウザを終了させないようにコメントアウト
上記のコードは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」を検索する。
Emacs ciderで接続できない。これはかなり残念。
https://github.com/clojure/tools.nrepl をrougeに移植すれば良いのかな?
でも大変そう。
Rubyの豊富なライブラリが利用できるのは便利だ。
エラーが起きても、該当行が表示されないので、デバッグが大変だ。
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
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個)で囲む。
(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は、手軽に機能を拡張できるので、便利だ。
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コマンドがあることを考えると、機能的には微妙なプラグインだな...
{: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))
うーむ。まったくもって、行き当たりばったりな実装だ。
Note that since Emacs 23 this is the preferred way to use Emacs in daemon mode. (start-server) is now mostly deprecated.
というコメントがあった。
ほー。今はdaemon modeで使う方が良いようだ。
とすると、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はそのままで、使用したい外部ライブラリを引数に渡すだけで、試すことができるようになる。
{:user {:plugins [[lein-try "0.4.1"]]}}
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していたので、これはお手軽で、とても便利。
lein-tryプラグインを使うと、project.cljはそのままで、使用したい外部ライブラリを引数に渡すだけで、試すことができるようになる。
準備
以下のように~/.lein/profiles.cljを編集して、lein-tryプラグインを使えるようにする。{:user {:plugins [[lein-try "0.4.1"]]}}
試してみる
satoshi@debian:~/workspace/clojure$ lein depsRetrieving 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)その形態素の連鎖をモデル化して、マルコフ連鎖に基づく文生成をする。
(: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"))))
吾輩は猫である。
名前はまだ無い。
どこで生れたかとんと見当がつかぬ。
何でも薄暗いじめじめした所でニャーニャー泣いていた事だけは記憶している。
吾輩はここで始めて人間というものを見た。
しかもあとで聞くとそれは書生という人間中で一番獰悪な種族であったそうだ。
この書生というのは時々我々を捕えて煮て食うという話である。
しかしその当時は何という考もなかったから別段恐しいとも思わなかった。
ただ彼の掌に載せられてスーと持ち上げられた時何だかフワフワした感じがあったばかりである。
掌の上で少し落ちついて書生の顔を見たのがいわゆる人間というものの見始であろう。
この時妙なものだと思った感じが今でも残っている。
第一毛をもって装飾されべきはずの顔がつるつるしてまるで薬缶だ。
その後猫にもだいぶ逢ったがこんな片輪には一度も出会わした事がない。
のみならず顔の真中があまりに突起している。
そうしてその穴の中から時々ぷうぷうと煙を吹く。
どうも咽せぽくて実に弱った。
これが人間の飲む煙草というものである事はようやくこの頃知った。
#<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の方が書き易い。
文生成が面白そうだったので、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 のドキュメントのどこかに書いてあるのかな？
トランザクションの処理に時間がかかり、何回繰り返してもリファレンスの値を更新できない場合は 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に次の設定を書く。
: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のサンプルが参考になった。
(: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のクラスを使う単純なコードだ。
gosen.core> (-main)
Java 名詞,固有名詞,組織,*,*,*,*
より 助詞,格助詞,一般,*,*,*,より,ヨリ,ヨリ
楽しい 形容詞,自立,*,*,形容詞・イ段,基本形,楽しい,タノシイ,タノシイ
Clojure 名詞,一般,*,*,*,*,*
。 記号,句点,*,*,*,*,。,。,。
nil
ユーザ辞書を追加することも簡単なようなので、試してみる予定。
この類のプログラムを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
試しに使ってみたら、結構便利。
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
ミニバッファに
pattern:
と表示されるので、検索したい文字列を入力する。
sort mapを入力した場合は、次のように表示される。
キーバインドは次の通り。
C-p 前の行
C-n 次の行
RET 選択した項目の表示
clojure-mode時に有効になるような、キーバインドを書いておくと便利かも。
試していないが、Helmのsourceにも対応している。
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で書いてみた。
四則演算のみサポートする単純な処理である。
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を使うとコードが分かり易くて、なかなか良いね。
(: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関数を作れば良いのだけど。
四則演算のみサポートする単純な処理である。
Haskellの場合
module RPN wheresolveRPN :: 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の最新版をインストールした。
$ 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
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
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
$ cabal update
$ cabal install ghc-mod
で、ghc-modがインストールできた。
どうしようもなかったので、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.htmlhttp://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を表示しないように設定して、対処した。
もっと簡単な方法は無いのかな?
"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)
hello0 ← ^M が消えてスッキリ
hello1
hello2
hello3
hello4
nil
user>
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を使うと問題なく動作した。
従来のダウンロード先にあったドライバは全て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!
[clj-webdriver "0.6.0"]
[org.seleniumhq.selenium/selenium-java "2.35.0"]
(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))))
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']"))
原因を調べてみると、DesiredCapabilitiesオブジェクトにchrome.switchesを追加しても、Chromeの起動オプションに追加されなくなっていた。
起動オプションの追加方法が変更されたようで、ChromeOptions#addArgumentsを使うと問題なく動作した。
実行環境
- Windows 8
- clj-webdriver 0.6.0
- 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
括弧内をハイライト表示できるのは知らなかった。
;;; 対応する括弧をハイライトさせる
(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-reader2013年6月19日水曜日
[Emacs][Racket] Geiserを使う
Realm of Racket を読みながら Racketを使い始めた。Racketは、標準でIDEを提供しており、面倒な環境構築しなくても、すぐにプログラムを実行できるようなっている。そのIDEを少し使ってみたが、キーバインドをEmacsに変更できないようなので、非常に使い難かった。調べてみると、Emacsで Geiser を使えば、Racketが使えることが分かった。
GeiserはSchemeインタープリタであるRacketまたはGuile用のメジャーモードを実現するもので、Slimeのようなインタラクティブ環境を利用可能になる。
Emacs: 24.3 (自分でmake,installしたもの)
Racket: 5.1.3(Ubuntu12.04標準)
Geiserのサイトの説明を見ると Racketのバージョンは5.3以上を推奨しているが、5.1.3でも一応動いた。
そのうちRacketを最新版にしよう。
トールできる。次のようにして、パッケージインストーラーが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)
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 によると、
と、様々な機能がある。
しばらくの間、この環境でRacketのコードを書いて遊ぼう。
GeiserはSchemeインタープリタであるRacketまたはGuile用のメジャーモードを実現するもので、Slimeのようなインタラクティブ環境を利用可能になる。
インストール
実行環境
OS: Ubuntu12.04Emacs: 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
- Realm of Racket http://realmofracket.com/
- Geiser http://www.nongnu.org/geiser/
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?メソッドとした方が良かったかも。
Micro Scheme
> (define (add a b) (+ a b))
#<Instruction::Closure:0x98295fc>
> (add 10 20)
30
>
いままでは評価結果は内部で使用しているRubyオブジェクトをそのまま表示していたが、やっと、Scheme処理系らしくなってきた。
なお、リストの表示方法を書いたけど、まだリストは扱えない。
次はリスト処理関数をいくつか追加しよう。
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.rbMicro 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
Virutal machineに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))
に変換し、再度コンパイルする。
> (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の命令に変換し、関数呼び出しで、それが実行される。
自分で実装して、実際に動かしてみると、なかなか感動的で、かなり楽しい。
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
> (+ 1 2 3)
#<SNumber:0x9f53a08 @value=6>
> ((lambda (a b) (+ a b)) 10 20)
#<SNumber:0x9f58940 @value=30>
>
S式出力は、まだ整形しておらず、Rubyのオブジェクト出力のままだ。
数値、文字列、シンボルはRubyオブジェクトをそのまま使っていたが、
ラッパークラスを作成し、これらのオブジェクトはラッパークラス経由で使用するようにした。
シンボルはinternする仕組みを作っておらず、毎回オブジェクト生成しているので、リソースの無駄使いをしている。
defineが無いと不便なので、先にこちらを実装しよう。
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(3imp.pdfとして有名)というScheme処理系の実装方式の解説を読んだ結果、コンパイルしたSchemeコードをScheme用に最適化したVitrual machine上で実行する方式のほうが、インタプリタ方式よりも、末尾最適化や継続の実装が簡単そうだった。
VMを使う方式では、末尾最適化と継続は次のように実装できる。
いまのところ 3imp.pdf とほぼ同じ仕様だ。
備忘録をかねて書いておこう。
5つのレジスタを持つ。
Virtual machineでサポートしている命令は以下の通り。
命令の中には、次に実行する命令を引数に取るものもあるが、以下では省略している。
式に応じてVirutal machineの命令を生成する。
いくつかコンパイル例を示す。
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)
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)
このルールに従ってリファクタリングしてみるのも、いろいろと得るものがありそうだ。
そこで、方針を変えて、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 doit {
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 doit {
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を変更できるようにした。
(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トップを表示できる。
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
もっと良い構成にできそうだが、いくらか見通しが良くなったので、ここまでにしておこう。
プログラム中ではRubyのリストオブジェクトのまま扱っているので、
今のままでは、Consセルを実現できない。
こちらはConsセルが必要になるまで、後回しにしよう。
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
式e1からenまで順に評価し、すべてが真の場合は、最後の式enの値を返す。
いずれかが偽の場合は falseを返す。
式e1からenまで順に評価し、真となった値を返す。
すべてが偽の場合は falseを返す。
式eが真の場合は falseを返す。
式eが偽の場合は trueを返す。
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
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
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パターンを適用して、それぞれのスペシャルフォームをクラス化すると、すっきりするかな？
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
:+ => [: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..
}
今回から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になったときに、原因が明確になるように、機能の対象となる部分のテストコードを書くべきなんだろうけど、まずはこれで良しとしよう。
とても分かり易くまとまっているのでおすすめ。
その他の「+」、「*」、「/」関数も同様に対応させた。
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
([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
(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 になってしまう。
(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を使ったマクロで実装したい。
その前に、リスト処理をする関数がいくつか必要だ。
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では、一行毎にトークン分割をして、結果を配列に格納しておく。
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
以下のように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
print Parser.new(Lexer.new(STDIN)).parse
(define (hello) ←入力
"hello") ←入力
[:define, [:hello], "hello"] ← 結果
うまく動いた。
実行例は以下の通り。
(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あたりで書くのが順当かな。
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について理解した(つもり)。まとめ。
関数を引数にとり、新しい関数を返す関数Fとする。
FをY Combinatorに適用すると、再帰関数fができる。
この再帰関数fは最初の関数Fの不動点である。
不動点であるため、この再帰関数fを関数Fに適用すると再帰関数fができる。
これで関数で再帰できることになる。
関数の引数として受け取った関数で再帰できるので、関数の名前が不要である。
無名再帰ともいうようだ。
と書いていて、本当に理解したのか怪しくなってくるなぁ...
こちらにも感謝!
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
(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
おーーー。動いた。
ちょっと感動...
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
(1)第一引数に変数、第二引数に値を指定する形式
(define id (lambda (x) ...))
(2)第一引数に関数名と仮引数のリスト、第二引数に関数本体を指定する形式
(define (id x) (...))
(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
正しく計算できた。これは楽しい!
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 ((fact
(lambda (x) (if (= x 0)
1
(* x (fact (- x 1))))))) ← ◆このfactは参照できない
(fact 5))
外側のletで自分自身を変数に束縛しても、lambda式を評価してクロージャを生成した時の環境と、クロージャの仮引数と引数の束縛を使って、クロージャ本体を評価するため、クロージャ本体からは、その変数で自分自身を参照できない。
(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)の実装とは違うが、
この方式だと何か問題があるのかな？
(lambda (x)
(if (= x 0)
1
(* x (fact (- x 1)))))))
(fact 10))
#=> 3628800
(lambda (x)
(if (= x 0)
1
(* x (fact (- x 1)))))))
(fact 100))
#=> 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
再帰呼び出しで、正しく計算できた。
少しずつ出来ることが増えてきて、なかなか楽しい。
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 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式の動作を、そのまま実装したコードで、とても簡単だ。
KEYWORDS = {
:true => true,
:false => false
}
を定義し、環境に追加した。
FUNCS = {
〜略〜
:< => [:built_in, lambda {|x, y| x < y}],
:> => [:built_in, lambda {|x, y| x > y}],
〜略〜
}
(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
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
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
まだ文字列は扱わないので、すごく単純だ。
(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らしくなってきた。
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らしくなってきた。
登録:
投稿 (Atom)