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

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

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

インストール

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

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

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

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

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

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

起動

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

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

参考

• Racket

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

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

リストの表示処理

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

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

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

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

実行例

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

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

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

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

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

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

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

Three Implementation Models for Scheme

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

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

末尾最適化

コンパイル時に、呼び出す関数が処理の末尾にあるか判定し、末尾の場合はコールフレームを生成せずに、関数を呼び出すコードを生成する。

継続

継続時点のスタックフレームを保存しておき、継続手続の呼び出しで、スタックフレームを復元後、値を渡す。

Virtual machine

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

レジスタ

5つのレジスタを持つ。

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

命令セット

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

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

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

コンパイラ

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

コンパイル例

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

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

実行例

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

クロージャ

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

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

継続

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

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

不足しているもの

末尾最適化

まだ実装していない。

define special form

VMの命令追加が必要だ。

REPL

REPLが無いと不便だ。

リファクタリング

• Perfecting OO's Small Classes and Short Methods
• [OOP] OOコード養成ギブス
• オブジェクト指向できていますか？

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

[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セルが必要になるまで、後回しにしよう。

[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パターンを適用して、それぞれのスペシャルフォームをクラス化すると、すっきりするかな？

[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
とても分かり易くまとまっているのでおすすめ。

[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を使ったマクロで実装したい。
その前に、リスト処理をする関数がいくつか必要だ。

[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の実装(8) ちょっと脱線 Y Combinator

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

Y Combinatorとは

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

• おとうさんにもわかるYコンビネータ！(絵解き解説編)
• さあ、Yコンビネータ(不動点演算子)を使おう！

関数を引数にとり、新しい関数を返す関数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

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

[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

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

[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

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

[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

[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

[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