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らしくなってきた。

2013年5月8日水曜日

[Ruby][Scheme] Micro Schemeの実装(3) let式の評価

let式を扱えるようにした。
https://github.com/takeisa/uschemer/tree/v0.03

lambda式への変換

let式の束縛リストに定義した環境で本体を評価すれば良いので、以下のようにlambda式に変換する。

(let 束縛リスト 本体)

((lambda 仮引数リスト 本体) 引数)

let式を使って作成したクロージャをlambda式に変換する例

(let ((a 1) (b 2))
     (lambda (x) (+ a b x)))

((lambda (a b)
     (lambda (x) (+ a b x))
) 1 2)

処理手順

  1. let式か判定する。
  2. let式の場合は、上記のルールでlambda式に変換する。
  3. 変換後の式を再評価する。

実行例

eval_print([:let, [[:a, 1], [:b, 2]], [:+, :a, :b]], env)
[:let, [[:a, 1], [:b, 2]], [:+, :a, :b]] #=> 3

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:0x9d4bbe8@uschemer.rb:6 (lambda)>],
   :-=>[:built_in, #<Proc:0x9d4bbc0@uschemer.rb:7 (lambda)>],
   :*=>[:built_in, #<Proc:0x9d4bb98@uschemer.rb:8 (lambda)>],
   :/=>[:built_in, #<Proc:0x9d4bb70@uschemer.rb:9 (lambda)>]}]]

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

2013年5月6日月曜日

[Ruby][Scheme] Micro Schemeの実装(2) lambda式とクロージャの評価

lambda式とクロージャを評価できるようにした。
https://github.com/takeisa/uschemer/tree/v0.02

束縛と環境

lambda式評価時の仮引数と引数の対応を束縛とし、その束縛のリストを環境とする。
束縛はハッシュで管理する。
環境の先頭から束縛のハッシュを順に検索して、束縛した値を取得する。

lambda式の評価方法

評価時の環境をひもづけてクロージャを作成する。

クロージャの評価方法

クロージャの仮引数と引数より束縛を作成し、環境の先頭に追加する。
この環境を利用してクロージャの本体を評価する。

実行例

eval_print([:+, :x, :y], [{:x => 123, :y => 456}] + env)
[:+, :x, :y] #=> 579

eval_print([:lambda, [:x, :y], [:+, :x, :y]], env)
[:lambda, [:x, :y], [:+, :x, :y]] #=> [:closure,
 [:x, :y],
 [:+, :x, :y],
 [{:+=>[:built_in, #<Proc:0xb747bca8@uschemer.rb:6>],
   :/=>[:built_in, #<Proc:0xb747b780@uschemer.rb:9>],
   :-=>[:built_in, #<Proc:0xb747baf0@uschemer.rb:7>],
   :*=>[:built_in, #<Proc:0xb747b938@uschemer.rb:8>]}]]

eval_print([[:lambda, [:x, :y], [:+, :x, :y]], 1, 2], env)
[[:lambda, [:x, :y], [:+, :x, :y]], 1, 2] #=> 3

eval_print(
  [[[:lambda, [:y], [:lambda, [:x], [:+, :x, :y]]], 5], 10],
  env
)
[[[:lambda, [:y], [:lambda, [:x], [:+, :x, :y]]], 5], 10] #=> 15

2013年5月3日金曜日

[Ruby][Scheme] Micro Schemeの実装(1) 四則演算の評価


積読していていた
つくって学ぶプログラミング言語 RubyによるScheme処理系の実装 (達人出版会)
を読みつつ、Micro Schemeを作ることにした。

この本にも推奨されていたが、
内容を理解したら、本のコードを見ないで自分で実装する方が理解が深まるので
それに従って、実装した。

作成するプログラム

小さなScheme処理系
Rubyで実装
SchemeプログラムはRubyのリストで表現
例: [:+, [:+, 1, 2], 3]

四則演算できるところまで実装した。
https://github.com/takeisa/uschemer/tree/v0.01

プログラム評価のアルゴリズム

(1)リストの場合
  関数呼び出しとして処理する。
(1)-1 リストの最初のシンボルに対応する関数を取得する。
    ※シンボルに対応する関数は USchemeR.FUNCS で定義している。
(1)-2 二番目以降の要素を引数として、全て評価する(再帰呼び出し)。
(1)-3 評価後の引数を関数に適用する。

(2)リスト以外の場合
a)数値の場合は数値を返す。

b)それ以外は関数を返す。

これだけ。
まだ、lambda式やクロージャも扱えないので、簡単だ。

実行例

eval_print(1)
1 #=> 1

eval_print(:+)
:+ #=> #<Proc:0xb743dc8c@uschemer.rb:7>

eval_print([:+, 1, 2])
[:+, 1, 2] #=> 3

eval_print([:+, [:+, 1, 2], [:+, 3, 4]])
[:+, [:+, 1, 2], [:+, 3, 4]] #=> 10

2013年5月1日水曜日

[Ruby][Emacs]smart-compile.elを使う

EmacsでRubyコードを書くときに、何か便利なものはないかなーと
Web検索していたら、smart-compile.elという、M-x compileの代替となる
便利なELispがあった。

何をするもの?

Smart Compile は M-x comileコマンドの代替で、
ファイル名やメジャーモードに応じて、実行するコマンドを切り替えることが可能になる。
実行するコマンドはカスタマイズできる。

インストール

(1) smart-compile.elをダウンロードする。
(2) ~/.emacs.d/els に格納する。
  ※私は単一のelファイルは els ディレクトリに格納している。
(3) ~/.emacs.d/init.el に以下の設定を追加する。

(add-to-list 'load-path "~/.emacs.d/els/")
(require 'smart-compile)
(setq smart-compile-alist
      (append
       '(("\\.rb$" . "ruby %f"))
       smart-compile-alist))
(add-hook 'ruby-mode-hook
      (lambda ()
        (define-key ruby-mode-map (kbd "C-c c") 'smart-compile)
        (define-key ruby-mode-map (kbd "C-c C-c") (kbd "C-c c C-m"))))

デフォルトだと 拡張子rbは ruby -cw %f を実行する設定になっていたので、スクリプトを実行するように変更した。
Emacs における快適な Ruby 開発環境を求めてを参考に、キーカスタマイズした。
  C-c c : スクリプトを実行する。
  C-c C-c : スクリプトに引数を渡す。

実行例


参考