Hatena::ブログ(Diary)

<s>gnarl,</s>技術メモ”’<marquee><textarea>¥ このページをアンテナに追加 RSSフィード Twitter

2007-03-23

WindowsでTierra

はじめに

Tierraとは、トム・レイが開発した人工生命環境で、自己複製・突然変異自然淘汰による進化をコンピュータ上で再現したものです。Windowsで動くGUIなTierraを数年前に作っていたのですが、せっかくなので公開します。


ダウンロード

windowsバイナリ(動作環境: .net framework 2.0以上)

http://www.todesking.com/files/Tierra_6854.zip

ソースはcodereposから。

http://coderepos.org/share/browser/lang/csharp/Tierra/trunk

svn checkout http://svn.coderepos.org/share/lang/csharp/Tierra/trunk/

で落とせます。

Tierraのしくみ

自己複製

Tierra世界の生命は、それぞれが「遺伝子」と呼ばれるプログラムを持っています。プログラムの目的は、自己複製、つまり子孫を残すこと。プログラムは、

  1. メモリ領域を確保
  2. 確保した領域に自分のプログラムをコピー
  3. プログラムを実行

という動作を行ないます。放っておけばどんどん増殖します。

突然変異

生命がプログラムを実行する際、ある確率でエラーが起こります。たとえばメモリ確保に失敗したり、コピーする際間違ったデータを書き込んだり。また、プログラムのあるビットが反転して意味が変わってしまうことがあります。

自然淘汰

Tierra世界において、メモリと計算資源は有限です。メモリがいっぱいになると、年老いた生命が死に、メモリに空きを作ります。プログラムを実行するのに必要な計算資源は、プログラムが短いほど多く与えられます。

メモリが有限であること、小さいほど多くの計算資源がもらえること。これらの条件は、生命のサイズを小さくする方向への淘汰圧となります。


関連リンク

Tierraについての詳しい情報は以下を参照してください

Tierra (コンピュータプログラム) - Wikipedia

no title

Tierra実行環境

f:id:gnarl:20070323160228p:image

初期画面はこのようになっています。

一番右にあるのは遺伝子のコレクションです。「80aaa」を右クリックして、新しい遺伝子をメモリプールに追加してみましょう。


f:id:gnarl:20070323160228p:image

中央には選択した生命の情報が表示されています。下段がその生命が持っているプログラム。命令の意味はno titleを参照してください。



f:id:gnarl:20070323160852p:image

Runボタンを押すと繁殖がはじまります。黄緑色は生命本体、緑は確保されたメモリ、白は空き領域、赤は現在実行中の生命を示しています。


f:id:gnarl:20070323161040p:image

Windowメニューから情報ウィンドウを開くことができます。

GeneViewウィンドウでは選択された遺伝子家系をみることができます。

CellListウィンドウでは、現在のメモリプールに存在する生命のリストを一覧表示できます(自動同期はしないのでRefleshボタンを押してください)

f:id:gnarl:20070323161807p:image

進化を続けたら、命令長57の種が大勢を占めるようになりました。

C#でSchemeを作ってみた

S式コンパイルしてVMで実行するタイプ。末尾再帰最適化あり。call/ccあり。syntax-rulesあり(一部。もちろんhygienic

)。これも去年ごろ製作したものを諸般の事情により公開。

評価機はhttp://www.cs.indiana.edu/~dyb/papers/3imp.pdfを参考にした。

できること

(+ 1 2)
 => 3

(define (add x y) (+ x y))
(add 10 20)
 => 30

(define x "global")
(define f  (let ((x "local"))(lambda () x))))
(f)
 => "local"

(let ((counter 0)) (set! incr (lambda () (set! counter (+ 1 counter)) counter)))
(incr)
 => 1
(incr)
 => 2

(+ 10 (call/cc (lambda (c) (set! cont c) 10)))
 => 20
(cont 10)
 => 20

(define (tarai x y z)
    (if (<= x y)
      y
      (tarai (tarai (- x 1) y z)
         (tarai (- y 1) z x)
         (tarai (- z 1) x y))))
(tarai 10 5 0)
 => 10 ;;遅い

;;syntax-rules
(define-syntax cond
         (syntax-rules (else =>)
               ((cond (else result1 result2 ...))
                (begin result1 result2 ...))
               ((cond (test => result))
                (let ((temp test))
                (if temp (result temp))))
               ((cond (test => result) clause1 clause2 ...)
                (let ((temp test))
                (if temp
                  (result temp)
                  (cond clause1 clause2 ...))))
               ((cond (test)) test)
               ((cond (test) clause1 clause2 ...)
                (let ((temp test))
                (if temp
                  temp
                  (cond clause1 clause2 ...))))
               ((cond (test result1 result2 ...))
                (if test (begin result1 result2 ...)))
               ((cond (test result1 result2 ...) clause1 clause2 ...)
                (if test
                  (begin result1 result2 ...)
                (cond clause1 clause2 ...)))))
(define-syntax
 let (syntax-rules ()
           ((_ ((var val) ...) body ...)
             ((lambda (var ...) body ...) val ...))
           ((_ name ((var val) ...) body ...)
          ((letrec ((name (lambda (var ...) body ...))) name)
           val ...)))) 
;;とかが通る。


VMのコードはこんなかんじ

;;x
(refer-global x)
(halt)

;;(f 1 2 3)
(new-frame) {
  (const 3)
  (push-param)
  (const 2)
  (push-param)
  (const 1)
  (push-param)
  (refer-global f)
  (apply)
}
(halt)

評価の過程はやや複雑で、S式マクロを展開しながらパースして中間言語に変換→さらにそれをコンパイルしてVMの命令列を得るようになっています。今思えば中間表現もS式で済む話だったのだけれど。

コンソールに出力されているのは中間表現。display-assemblyプロシージャでVMの命令列が見えます。

> (define (f x) (let ((hoge 1)) (+ x hoge)))
expand-macro result:
define f Lambda ( x) {
    Apply {
        target:
        Lambda ( hoge) {
            Apply {
                target:
                GlobalBinding +
                params:
                LocalBinding x(level:0,index:0)
                LocalBinding hoge(level:1,index:0)
            }
        }
        params:
        Const 1
    }
}


eval result:
#<closure>

> (display-assembly '(define (f x) (let ((hoge 1)) (+ x hoge))))
expand-macro result:
Apply {
    target:
    GlobalBinding display-assembly
    params:
    Const (define (f x) (let ((hoge 1)) (+ x hoge)))
}

eval result:
(create-closure ( x) <
(clear-args)
(const 1)
(push-param)
(create-closure ( hoge) <
(clear-args)
(refer-local hoge(1 0) )
(push-param)
(refer-local x(0 0) )
(push-param)
(refer-global +)
(apply)
>)
(apply)
>)
(define f)
(halt)



ダウンロード

現在ファイルサーバが死亡しています。近日中にソースをcodereposにupする予定はあります。(2008.02.18)

→ソースを紛失しました、なんてこったい。おれの青春が…… (20090506)

jsで実装したSchemeというのもつくりました、興味があるかたはどうぞ。