[Emacs][Racket] Geiserを使う

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

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

インストール

実行環境

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

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

Geiserのインストール

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

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

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

M-x package-install RET geiser RET

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

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

Geiserの起動

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

M-x run-geiser

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

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

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

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

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

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

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

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

参考URL

• Realm of Racket http://realmofracket.com/
• Geiser http://www.nongnu.org/geiser/

[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の実装(16) defineを実装

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

define命令の追加

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

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

define式のコンパイル

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

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

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

2番目の形式の場合は、
(define (func arg0...) body)
↓
(define func (lambda (arg0...) body))
に変換し、再度コンパイルする。

実行例

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

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

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

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

実行例

$ ruby uschemer.rb                
> (+ 1 2 3)
#<SNumber:0x9f53a08 @value=6>
> ((lambda (a b) (+ a b)) 10 20)
#<SNumber:0x9f58940 @value=30>
>
S式出力は、まだ整形しておらず、Rubyのオブジェクト出力のままだ。

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

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

[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は使わない等の強い制約の元で実装することで、オブジェクト指向プログラミングがうまくなるらしい。
このルールに従ってリファクタリングしてみるのも、いろいろと得るものがありそうだ。