Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2008-07-18

Getting Started in *LISP (12)

| 20:38 | Getting Started in *LISP (12) - わだばLisperになる を含むブックマーク はてなブックマーク - Getting Started in *LISP (12) - わだばLisperになる

こちらも放置しておりました、*Lispのチュートリアル。

同じく細かく進めて行くことにしました。

3.3 Communication Operators

データをCPU間でやりとりすることを"コミュニケーション"と表現することにする。

コミュニケーションには2種類あって、ルータコミュニケーションと、グリッドコミュニケーションがある。

3.3.1 Router Communication - General-Purpose Data Exchange

CM(コネクションマシン)では、各CPUは接続されていて、互いに通信ができるネットワークを持つ。これをルータと呼ぶらしい。

各プロセッサには、番地があるので、(self-address!!で取得可能)、これを利用してデータを特定のプロセッサ間で通信できる。

3.3.2 The Router Communication Opetators of *Lisp

ルータコミュニケーションに使用するオペレータには

  • *pset

あるプロセッサからデータを対象のプロセッサに送信する。パラレル動作。

  • pref!!

あるプロセッサが対象のプロセッサよりデータを取得。パラレル動作。

の2種類がある。

;; *pset

*number-of-processors-limit*
;==> 256

(*let (data)
  (*pset :no-collisions
         (self-address!!) ;送信元番地
         data             ;格納場所
         (-!! *number-of-processors-limit* ;着信番地
              (self-address!!)
              1))
  ;; 表示
  (ppp data))
;>>> 255 254 253 252 251 250 249 248 247 246 
;==>NIL

*psetは、(*pset combiner source-pvar dest-pvar send-address-pvar ...)という形式

  • 上の例の場合、自分の番地を値として送信。
  • dataは格納されるpvar
  • (-!! 〜)の部分は、送信先アドレス

つまり、255番プロセッサが、255という値を、0番プロセッサに送信、結果として、pvarの0番目に255が格納される。

次回3.3.3より再開

2008-06-01

Getting Started in *LISP (11)

| 18:14 | Getting Started in *LISP (11) - わだばLisperになる を含むブックマーク はてなブックマーク - Getting Started in *LISP (11) - わだばLisperになる

今回は、3章から再開です。

Chapter 3: Parallel Programming Tools

これまで、CLとの共通点が多くあることをみてきたが、この章では*Lisp特有のところをみてゆく、とのこと。

3.1 Data Parallel Programming

*Lispのデータ操作には大別すると5種類ある。

  1. プロセッサを選択し一連のオペレーションを実行するもの
  2. Connection Machine内のプロセッサ間のデータ移動をするもの
  3. ホストコンピュータとConnection Machine間のデータ転送をするもの
  4. データを合成/加工するもの
  5. pvarの形を決定するもの

以下、それぞれに2づつ例を挙げてゆく

3.2 Processor Selection Operators

常に全プロセッサで計算をしたいとは限らないので、*Lispでは各々のプロセッサを指定して計算したりしなかったりできる。

デフォルトで*cold-bootした場合、全プロセッサは活性状態であるとのこと。

3.2.1 Processor Selection - Doing More by Doing Less

条件分岐のようにプロセッサ毎に特定の命令を実行したりしなかったりすることができて、例えば、CLのwhenのような*whenや、if!!が使える。

色々試してみる。

(*defvar data 4)

;; とりあえず全部4で埋める
(ppp DATA :end 20)
;>>> 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
;==> NIL

;; self-address!!ではプロセッサの番号を取得できるが、
;; 番号の性質を判定して実行

(ppp (self-address!!) :end 20)
;>>> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
;==>  NIL

(ppp (evenp!! (self-address!!)) :end 20)
;>>>T NIL T NIL T NIL T NIL T NIL T NIL T NIL T NIL T NIL T NIL 
;==> NIL

;; ==> 偶数番号のプロセッサはTを返していることがわかる


;; ちょっと応用
;; アドレスが偶数番号のプロセッサの値に3を加える

(*when (evenp!! (self-address!!))
  (*set data (+!! data 3)))

(ppp DATA :end 20)
;>>> 7 4 7 4 7 4 7 4 7 4 7 4 7 4 7 4 7 4 7 4 
;==> NIL

;; if!!
(ppp (if!! (oddp!! (self-address!!))
           (+!! data 3)
           (-!! data 3))
     :end 20)
;>>> 4 7 4 7 4 7 4 7 4 7 4 7 4 7 4 7 4 7 4 7
;==>  NIL

self-address!!に似たものとして、enumerate!!という数え上げの関数がある。

;; 0で埋める
(*defvar empty-pvar 0)

(ppp empty-pvar :end 20)
;>> 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
;==> NIL

;; 偶数番プロセッサで、enumerate!!を実行
(*when (evenp!! (self-address!!))
  (*set empty-pvar (enumerate!!)))

(ppp empty-pvar :end 20)
;>>> 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0
;==> NIL

条件を満したところがenumerate!!の結果で埋まっていることが分かり、順に数え上げられている。

3.2.2 The Processor Selection Operators of *Lisp

*LispにはCLのwhen, unless, if, cond, case, ecaseに対応する述語に加えて、独自の

*allとwith-css-savedという述語が用意されているが詳細は解説しないとのことで、リファレンスを参照せよ、とのこと。

リファレンスもないので、とりあえず、どういうものかを試して探ってみたものの、良く分からず…。

*allは、定義を眺める限りでは、こんな定義。どうやら全プロセッサを選択した状態でなにかをする時に使うものらしい…。

with-css-savedは、currently selected setの状態を保持しつつボディ部を実行するものの様子。しかし、これも詳細不明…。

次回3.3章から再開です。

2008-05-24

Getting Started in *LISP (10)

| 16:19 | Getting Started in *LISP (10) - わだばLisperになる を含むブックマーク はてなブックマーク - Getting Started in *LISP (10) - わだばLisperになる

2.7 Defining *Lisp Functions and Macros

この章では、関数とマクロをどう定義してゆくかを解説

2.7.1 To Define a Function, Use defun

関数定義には、通常のCLのように、defunが使える

(defun add-mult!! (a b c)
  (*!! (+!! a b) c))

(ppp (ADD-MULT!! 1 2 3) :end 12)
;>>> 9 9 9 9 9 9 9 9 9 9 9 9 
;==> nil

(*defvar my-pvar 1)

(*set my-pvar (add-mult!! my-pvar -6 (self-address!!)))

(ppp my-pvar :end 12)
0 -5 -10 -15 -20 -25 -30 -35 -40 -45 -50 -55 NIL

という風に割とCLのまま書ける。

*Lispには、*defunというものも用意されているが、特殊な状況を除き使用する必要はなく、殆どdefunでまかなえるとのこと。

2.7.2 To Define a Macro, Use defmacro

マクロの定義もお馴染みのdefmacroで定義。

(defmacro *two-incf (pvar)
  `(*set ,pvar (+!! ,pvar 2)))

(*TWO-INCF my-pvar)

(ppp my-pvar :end 12)
;>>> 2 -3 -8 -13 -18 -23 -28 -33 -38 -43 -48 -53
;==> NIL

というようにCLそのままな感じ。

2.8 Compiling *Lisp Code

コンパイルについてもCLと同様で、関数単位、ファイル単位で可能。

(compile 'add-mult!!)

(compile-file "starlisp-code.lisp")
(load "starlisp-code")
  • A Note about Declarations

コンパイラへの宣言については、*Lispでは、関数の引数と返り値の型を完全に明確に宣言しないと、完全にコンパイルされないということに注意せよ、とのこと。

詳細は、5章で解説。

完全な宣言の例

(defun add-mult!! (a b c)
  (declare (type (pvar (signed-byte 32)) a b c))
  (*!! (+!! a b) c))

型宣言しなければ、コンパイルされないわけではなく、パフォーマンス等で機能を十全に発揮させるには、型宣言が必要になることに注意せよ、とのこと。

2.9 Summary: How *Lisp and Common Lisp Are Similar

CLと*Lispの共通点についてのまとめ

  • pvarは、CLのアレイのようなもの
  • pvarのプリティプリントにはpppがある
  • 並列動作する関数は、pvarに対して動作する並列版CL関数ともいうべきもの
  • defunや、defmacro等CLと同じものが使える
  • コンパイラは、*Lisp用に拡張されたCLのコンパイラのようなもの

次回、3章から再開です。

2008-05-15

Getting Started in *LISP (9)

| 23:44 |  Getting Started in *LISP (9) - わだばLisperになる を含むブックマーク はてなブックマーク -  Getting Started in *LISP (9) - わだばLisperになる

*LISPのチュートリアルを細々とさらっております。今回は、2.4章から再開

2.4 The Size and Shape of Pvars

重要な違いはあるものの、これまでの内容からもPVARとCLのアレイは似たようなものと考えることができることが分かった。

共通点としては、

  • 多数の要素を持つ
  • 要素の形(次元等)と、要素数を指定する。
  • インデックスを指定して読み書きする。
  • 関数に引数として与えられた場合は、値を渡すのではなく、参照を渡す。

等がある。

アレイのサイズの指定のように、PVARの配列サイズはどのようにして決めるか、ということになるが、cold-boot時に指定する方法と後の章で説明する方法がある。

2.4.1 Processor Grids and Configurations

とりあえず、*cold-bootでの初期化の方法の解説。

*cold-bootを呼ぶとPVARは初期化されるが、引数なしで、*cold-bootが呼ばれた場合、搭載されているCPUの数となり、2次元のグリッドで、CPUの個数に応じて適宜調整される。

8K個の場合は、64 x 128 に配置される(8192)

シミュレータの場合は、デフォルト値8 x 4(16)

2.4.2 *cold-boot

*cold-bootの様子

(*cold-boot)

Thinking Machines Starlisp Simulator.  Version 20.0

1 ;シミュレータなので、1個ということか?…。
(16 16)
Configuration Variables

グリッドについては、色々と変数がある。

CPUの数

*number-of-processors-limit*
;=> 256

グリッドの形状

*current-cm-configuration*
;=> (16 16)

2.4.3 Processor Grids and Pvar Shapes

*current-cm-configuration*が8192の場合、(!! 24)を実行すると、64 * 128のグリッド全部に24が格納された状態になっている。

2.4.4 Pvars of Different Shapes and Sizes-VP Sets

プログラム中で、pvarのグリッドの形を変更したくなった場合はどうするか。

そういう場合のためにvirtual processor sets (VP sets)という概念が用意されているが、とりあえず、初歩的な説明を続けるとのこと。

2.5 Calling Parallel Functions

並列関数?を色々と使ってみた例

(ppp (+!! (self-address!!) 3) :end 20)
;>>> 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 

(ppp (*!! (self-address!!) pi) :end 4)
;>>> 0.0d0 3.141592653589793d0 6.283185307179586d0 9.42477796076938d0

(ppp (float!! (1+!! (self-address!!))) :end 12)
;>>> 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10.0 11.0 12.0

(ppp (sin!! (*!! (self-address!!) (/!! pi 4))) :end 4)
;>>> 0.0d0 0.7071067811865475d0 1.0d0 0.7071067811865476d0 

(let ((i #C(0.0 1.0)))
  (ppp (exp!! (*!! 2 pi i)) :end 3))
>>> #C(1.0d0 -2.4492127076447545d-16) #C(1.0d0 -2.4492127076447545d-16) #C(1.0d0 -2.4492127076447545d-16)
;; シミュレータだと、数値がちょっと違う…

(ppp (random!! 20) :end 20)
;>>> 3 5 13 4 7 18 15 13 18 19 10 0 8 11 12 4 11 14 9 9
*Lispの関数名について

CLの関数に対応するものが、*Lispの並列版として用意されているが、

  • 大抵末尾に'!!'が付くか、先頭に'*'が付く
  • 動作は殆ど同じだが、並列に動作する

のが特徴。

'!!'(読み:バンバン)が末尾に付いたものは、並列に動作し、いつもPVARを返す。

'*'(読み:スター)が付いたものは、並列に動作するが、基本的にPVARは返さないもの。

という方針で名付けられているとのこと。

2.6 Printing Pvars in Many Ways

PVARのプリティプリント関数である、pppの解説。

オプションを色々解説。

一番簡単なオプションは、:endで、指定した場所まで、表示する。

(*defvar my-pvar 5)

(ppp my-pvar :end 20)
;>>> 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 

:start は開始位置を指定する。

(ppp (self-address!!) :start 20 :end 30)
;>>> 20 21 22 23 24 25 26 27 28 29

:per-line で一行あたりの表示個数を指定できる。

(ppp (self-address!!) :end 30 :per-line 12)
0 1 2 3 4 5 6 7 8 9 10 11 
12 13 14 15 16 17 18 19 20 21 22 23 
24 25 26 27 28 29 

:grid を使うことで現在のグリッドを表示することもできる。

(ppp (self-address!!) :mode :grid :end '(4 4))

;>>>
;     DIMENSION 0 (X)  ----->
;
;0 16 32 48 
;1 17 33 49 
;2 18 34 50 
;3 19 35 51 

:format を付けてさらにみやすく整形。フォーマット指示子は、formatと同じものが使えるらしい。

(ppp (self-address!!) :mode :grid :end '(4 4) :format "~2D ")
;>>>
;     DIMENSION 0 (X)  ----->
;
; 0 16 32 48 
; 1 17 33 49 
; 2 18 34 50 
; 3 19 35 51 

(ppp (self-address!!) :end 32 :per-line 8 :format "~2D " :title "Send addresses")

:title で、グリッドのタイトルを指定可能
;>>>
;Send addresses:
; 0  1  2  3  4  5  6  7 
; 8  9 10 11 12 13 14 15 
;16 17 18 19 20 21 22 23 
;24 25 26 27 28 29 30 31 

2008-05-10

Getting Started in *LISP (8)

| 14:49 | Getting Started in *LISP (8) - わだばLisperになる を含むブックマーク はてなブックマーク - Getting Started in *LISP (8) - わだばLisperになる

*LISPのチュートリアルを細々とさらっております。今回は、2.2章から再開

2.2 Data Parallelism-A Different Value for Each Processor

これまでの内容で、全プロセッサに同じ値を割り付けることは分かった。

しかし、*Lispのデータパラレリズム言語としての肝は、各々のプロセッサが同一のオペレーションをするというところにあり、大抵各プロセッサで違う内容のデータを処理することになるので、それの解説。

各プロセッサに別々の値を割り付けるものには、既出のものでは、random!!がある。

同様のものとしては、self-address!!がある。

プロセッサには一意の番号が定数として割り付けられているので、その番号を取得するもの。

(ppp (self-address!!) :end 20)
;>>> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

アドレスを指定して値を取得するには、2.1.4で説明されたprefが使える。

2.3 Pvar Data Types

Pvarで利用可能な色々なデータ型を解説。

まず、*Lispへスカラー値が渡った場合は、pvarとみなされるとのこと。

つまり、5と書いても、(!! 5)と見做されるということ。

ブール値

t!!、nil!!等があり、また述語もあり。

(ppp (evenp!! (self-address!!)) :end 10)
;=> T NIL T NIL T NIL T NIL T NIL 
unsigned-byte、 signed-byte
(+!! 3 5)

(ppp (-!! (self-address!!) 800) :end 10)
;>>> -800 -799 -798 -797 -796 -795 -794 -793 -792 -791 
defined-float
(float!! 34)

(ppp (/!! (self-address!!) 4) :end 10)
;>>> 0.0 0.25 0.5 0.75 1.0 1.25 1.5 1.75 2.0 2.25 
complex
(complex!! 3 1)

(ppp (complex!! (self-address!!) 1) :end 5)
;>>> #C(0 1) #C(1 1) #C(2 1) #C(3 1) #C(4 1) 
character
(!! #\C)
(int-char!! 23)

(ppp (!! #\C) :end 10)
;>>> #\C #\C #\C #\C #\C #\C #\C #\C #\C #\C 

;; int-char!!がエミュレータにはない。
;; code-char!!になっている様子。

(ppp (code-char!! 23) :end 10)
;>>> #\^w #\^w #\^w #\^w #\^w #\^w #\^w #\^w #\^w #\^w 
array
(ppp (make-array!! '(2 8) :element-type 'single-float :initial-element pi) :end 1)
;>>> #2A((3.141592653589793d0 3.141592653589793d0 3.141592653589793d0
;         3.141592653589793d0 3.141592653589793d0 3.141592653589793d0
;         3.141592653589793d0 3.141592653589793d0)
;        (3.141592653589793d0 3.141592653589793d0 3.141592653589793d0
;         3.141592653589793d0 3.141592653589793d0 3.141592653589793d0
;         3.141592653589793d0 3.141592653589793d0)) 
structure
(*defstruct particle
  (x-pos 0 :type (unsigned-byte 32))
  (y-pos 0 :type (unsigned-byte 32)))

(*let ((sts (make-particle!! :x-pos 20 :y-pos 61)))
  (ppp (particle-x-pos!! sts) :end 10))
;>>> 20 20 20 20 20 20 20 20 20 20 
2.3.1 Other Pvar Types

その他に扱えるものとして、front-endがあり、参照を格納できるらしい。

(ppp (front-end!! 3) :end 10)

(ppp (front-end!! '(foo bar baz)) :end 5)
;>>> (FOO BAR BAZ) (FOO BAR BAZ) (FOO BAR BAZ) (FOO BAR BAZ) (FOO BAR BAZ) 
(ppp (!! '(foo bar baz)) :end 10)
;!!! Cannot put values of type CONS into a pvar
;となり、pvarにはコンスは格納できない。

上記のように、コンス(リスト)はPVARに格納できないので、扱うとすれば、ポインタ参照経由でということになるのだろうか。

まだ、それぞれのプロセッサごとに異なる参照を格納する解説はなし。

ということで、色々な型のデータをpvarとして格納できることが分かった。

また、PVAR変数の作成は、

(*defvar my-pvar 5)

のようにするが、型を指定したpvarの作り方については、5章で解説するとのこと。

2008-05-01

Getting Started in *LISP (7)

| 16:24 | Getting Started in *LISP (7) - わだばLisperになる を含むブックマーク はてなブックマーク - Getting Started in *LISP (7) - わだばLisperになる

*LISPのチュートリアルを細々とさらっております。今回は、2章から再開

Chapter 2 The *Lisp Language

この章では、

  1. *Lispの並列型データの基本としてのpvar
  2. データパラレリズム
  3. *Lispでの並列版関数が元のCLのどの関数に相当するか
  4. 並列版関数の定義とコンパイル

についての詳細を解説するとのこと。

2.1 Creating and Using Parallel Variables

*Lispの並列処理で基本となるデータ型は、pvar(Parallel Variable)

このpvarは各々Connection Machineの1プロセッサに対応していて、number、character、array、structure型が扱える。

2.1.1 Creating a Pvar - !!

*Lispで一番単純な並列操作は、!!(バンバンと読むそうな…)で、スカラー値を引数に取り、pvarを返します。

(!! 24)

;=> #<PVAR CONSTANT-24 :GENERAL  *DEFAULT-VP-SET* (8 4)>

これは、24という値を全部のプロセッサに送るもの。

使われるのは一時的な格納場所ということで、!!では、各プロセッサに値を保持することはできない。

2.1.2 Permanent Pvars - *defvar

値を再度設定するまで永続化したい場合は、*defvarを使う。

(*defvar my-pvar 5)

全プロセッサのmy-pvarに5を代入。

*Lispでは、最初から2つの並列版のpvarが設定されていて、並列版t!!と、nil!!がある。CLでは、tとnilに相当。

2.1.3 Local Pvars - *let

*defvarは、大域的で、ローカルにpvarを設定したい場合には、(なんか微妙な表現だな(^^; ) *letが使える

(*let ((two!! 2)
       (three!! 3.0))
  (+!! two!! three!! my-pvar))

これで、全プロセッサで2 + 3.0を計算する。演算子も+!!という並列版を使う必要あり。

2.1.4 Reading, Writing, and Printing Pvar values

プロセッサは沢山あるけれど(Connection Machine(CM-2)の場合65536個)特定のプロセッサの値を見たい場合は、prefが使える。"processor reference"の略でarefの類推から来てるらしい。

(pref my-pvar 12)
;=> 5

これは、12番プロセッサの値を取得する。上で、*defvarで全部5に設定したので、5が返ってくる。

値を代入したい場合は、*setfを使う。

(*setf (pref my-pvar 12) 42)
;=> 42
(pref my-pvar 12)
;=> 42

値をプリティプリントしたい場合は、pppか、pretty-print-pvarを使う。

(ppp my-pvar :end 20)
;>>> 5 5 5 5 5 5 5 5 5 5 5 5 42 5 5 5 5 5 5 5 

12番目が、42になっているのが確認できる。

*setfの他には、set*が使える。これは、setqの並列版なのか、setの並列版なのかどっちなのだろう。

(*set my-pvar 9)

(ppp my-pvar :end 20)
;>>> 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 NIL

(*defvar copy-pvar)
; (ちなみに、初期化しないと#:ILLEGAL-VALUE-21421で埋まっている模様)
(ppp COPY-PVAR :end 1)

(*set copy-pvar my-pvar)
(ppp copy-pvar)
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 NIL

代入できた。

一括で扱うのには、*系、プロセッサで並列に実行させたり、その値は、!!系の名前になっているんだろうか。

2008-04-24

Getting Started in *LISP (6)

| 23:37 | Getting Started in *LISP (6) - わだばLisperになる を含むブックマーク はてなブックマーク - Getting Started in *LISP (6) - わだばLisperになる

*LISPのチュートリアルを細々とさらっております。今回は、1.2.5章から再開

1.2.5 Personalize Your System

このセクションは作成したプログラムファイルのロードについて等の記述に軽く触れている程度の内容です。

1.3 Exiting From *LISP

*LISPはコネクションマシンに接続されたホストから操作するのですが、ホスト機としては、SUNのUNIXワークステーションや、SymbolicsのLispマシンが対応していました。

ホスト機のLispの処理系は、Lucid Common Lisp、Symbolicsは、Symbolics Common Lisp(だったのかな?)のようです。

面白いのが、Symbolicsの方は、Lispマシンということもあって、終了の方法は、パッケージを移動するだけ、というところ。

UNIXは、最近のCL処理系と同じく(quit)とかしてシェルに抜けます。

次回、第2章から再開で、パラレル変数の扱い等々です。

2008-04-17

Getting Started in *LISP (5)

| 15:35 | Getting Started in *LISP (5) - わだばLisperになる を含むブックマーク はてなブックマーク - Getting Started in *LISP (5) - わだばLisperになる

実に2ヶ月も間が空いてしまいました…。

もう、自分自身すっかり忘れてしまっていますが、

Getting Started in StarLispという*LISPのチュートリアルの実習をしています。

とりあえず、毎週木曜日には、このシリーズでエントリを書くことにしました。

1.2.4 Mortal or Immortal

前回までは、ムーア型とノイマン型のオートマトンを作成して様子を観察していましたが、今回は、それぞれ絶滅するパターンはあるか?を探るようです。

どうやって集計するかですが、*LISPには、*SUMというpvarの数を集計してくれる関数があるので、それを使います。

(*sum (signum!! *automata-grid*))

SIMD版signumで、0、1、-1に割り振って集計というわけですね。-1はありえないので、個体数を勘定するのに使えます。

それで、それをユーティリティとして定義してみます。

(defun deadp ()
  (zerop (*sum (signum!! *automata-grid*))))

これで、絶滅したかを確認することができます。ここで、zeropと、zerop!!の使い分けについての説明があります。

今回の場合、*sumは、PVARを返すわけではなく、スカラー値を返すので、zeropを使うのが適切とのこと。

これらを使って絶滅するパターンを探ってみよう、という感じです。

次回は、1.2.5からです。

2008-02-10

Getting Started in *LISP (4)

| 08:49 | Getting Started in *LISP (4) - わだばLisperになる を含むブックマーク はてなブックマーク - Getting Started in *LISP (4) - わだばLisperになる

*LISPのチュートリアルをさらってみることの4回目。

大分間があいてしまいました‥。

特に理由はないけれどこのチュートリアルは終らせたいところ。

1.2.3 Defining a More Complex Automaton

の続きで、One Small Step...for 9 Life

(defun one-step ()
  (*let ((count (neighbor-count)))
    (cond!!
      ;; 周囲の数が<1か、>3なら、1を引く
      ((or!! (<!! count 1) (>!! count 3))
       (if!! (zerop!! *automata-grid*)
	     *automata-grid*
	     (1-!! *automata-grid*)))

      ;; 2か、3なら1を足す
      ((<=!! 2 count 3) (1+!! *automata-grid*))

      ;; その他は、そのまま
      (t *automata-grid*))))

オートマトンの状態を一段階ずつ進める関数を定義

cond!!と、if!!は、pvarそれぞれを判定して結果を返す、SIMD版condとif

他にも色々ユーティリティを定義

(defun set-cells (cell-list value)
  (dolist (cell cell-list)
    (set-cell (car cell) (cadr cell) value)))

(defun init ()
  (set-grid 0)
  (set-cells '((2 2) (3 1) (3 2) (3 3) (4 1))
	     1)
  (view))

(defun view-step (&optional (n 1))
  (run n)
  (view))

実行してみる

(init)
;
;     DIMENSION 0 (X)  ----->
;
;0 0 0 0 0 0 0 0 
;0 0 0 1 1 0 0 0 
;0 0 1 1 0 0 0 0 
;0 0 0 1 0 0 0 0 
;0 0 0 0 0 0 0 0 

(view-step)
;     DIMENSION 0 (X)  ----->
;
;0 0 0 0 0 0 0 0 
;0 0 1 2 1 0 0 0 
;0 0 1 2 1 0 0 0 
;0 0 1 1 0 0 0 0 
;0 0 0 0 0 0 0 0 

(view-step 45)  ...
;
;     DIMENSION 0 (X)  ----->
;
;0 0 0 0 0 0 0 0 
;0 0 0 8 3 0 0 0 
;0 0 5 0 7 0 0 0 
;0 0 4 5 9 0 0 0 
;0 0 0 0 0 0 0 0 

しかし、これだと、おなじ升目から動かない。

→ノイマン型だから

;; moore型に変更
(setq *neighborhood* :moore)
(init) 
;
;     DIMENSION 0 (X)  ----->
;
;0 0 0 0 0 0 0 0 
;0 0 0 1 1 0 0 0 
;0 0 1 1 0 0 0 0 
;0 0 0 1 0 0 0 0 
;0 0 0 0 0 0 0 0 

(view-step) 
;
;     DIMENSION 0 (X)  ----->
;
;0 0 0 1 1 0 0 0 
;0 0 1 2 2 0 0 0 
;0 0 2 0 0 0 0 0 
;0 0 1 2 1 0 0 0 
;0 0 0 0 0 0 0 0 

(view-step 50)  
;
;     DIMENSION 0 (X)  ----->
;
;1 2 1 0 5 0 7 0 
;1 1 1 1 7 0 9 1 
;3 1 0 1 1 5 0 0 
;0 0 1 1 1 1 2 4 
;2 0 1 0 1 1 1 0 

ムーア型だと大分ばらける

2008-01-27

Getting Started in *LISP (3)

| 23:48 | Getting Started in *LISP (3) - わだばLisperになる を含むブックマーク はてなブックマーク - Getting Started in *LISP (3) - わだばLisperになる

*LISPのチュートリアルをさらってみることの3回目。

1.2.3 Defining a More Complex Automaton

この節では、もうちょっと複雑なオートマトン、"9ライフ"を作成してみるとのこと。

ルールは以下の通り

  1. 各々のセルの周囲の0でないセルの個数を数える。
  2. 上記の個数が、1より小さいか、3より大きい場合、セルの値から1引く
  3. 同様に、2個から3個の場合は、セルの値に1足す

周囲の定義には2種類あり、フォン・ノイマン型とムーア型があるそうな。

フォン・ノイマン型は、上下左右の4方向が隣人とみなされ、ムーア型は、8方向が隣人。

今回は9ライフなので、ムーア型を採用。

逐次型と並列型の違い

各々のセルを一世代、更新する関数を逐次実行で書くとすると、x軸とy軸のアレイをループ処理することになり、下記のようになるんじゃないかとのこと。

(defun serial-one-step (array-x-size array-y-size)
  (dotimes (x array-x-size)
    (dotimes (y array-y-size)
      (let ((neighbors (list	(get-cell (- x 1) y)
				(get-cell (+ x 1) y)
				(get-cell x (- y 1))
				(get-cell x (+ y 1))
				... )))
	(store-new-cell-value x y
			      (new-value neighbors)))))
  (update-grid))

内容としては、隣のセルの番地を計算して、その値を取得し結果を合計している。

隣のセルの値の取得については、*LISPには隣のグリッドの値を並列に取得するためのnews!!という関数が用意されているので、ループを回す必要はない。

newsは東西南北のn、e、w、sの意味。

(news!! x y)となるので、(news!! 1 0)の場合、自身の東の値となる。

東の値を自身の位置に表示すると結果として西にずれたように見える。

(let ((g (random!! 10)))
  (ppp g :end '(8 8))
  (ppp (news!! g 1 0) :end '(8 8))
;=>
;     DIMENSION 0 (X)  ----->
;
;3 4 0 0 3 3 2 2 
;4 0 1 8 3 4 5 9 
;5 2 0 0 5 3 7 2 
;6 1 5 7 1 0 4 6 
;0 5 8 9 8 6 4 8 
;1 3 8 3 8 0 8 6 
;9 0 5 6 3 6 8 2 
;3 2 7 8 4 6 0 9 
;
;     DIMENSION 0 (X)  ----->
;
;4 0 0 3 3 2 2 2 
;0 1 8 3 4 5 9 1 
;2 0 0 5 3 7 2 6 
;1 5 7 1 0 4 6 6 
;5 8 9 8 6 4 8 1 
;3 8 3 8 0 8 6 1 
;0 5 6 3 6 8 2 2 
;2 7 8 4 6 0 9 6 

news!!を使うと、フォン・ノイマン型の隣人を求める関数は、

(defun neumann-count (grid)
  (+!! (news!! grid  0 -1)	;; north
       (news!! grid  0  1)	;; south
       (news!! grid -1  0)	;; west
       (news!! grid  1  0)	;; east
       ))

のように定義できる。

ムーア型は、8方向なので、

(defun moore-count (grid)
  (+!!	(news!! grid  0 -1)			;; north
	(news!! grid  0  1)			;; south
	(news!! grid -1  0)			;; west
	(news!! grid  1  0)			;; east
	(news!! grid -1 -1)			;; northwest
	(news!! grid -1  1)			;; southwest
	(news!! grid  1 -1)			;; northeast
	(news!! grid  1  1)			;; southeast
	))

となる。

周囲の非ゼロのセルの個数の合計は、ノイマン型とムーア型を*neighborhood*で切り分けられるように定義するとすれば、

(defvar *neighborhood* :neumann)

(defun neighbor-count ()
  (*let ((grid (signum!! *automata-grid*)))
    (ecase *neighborhood*
      (:moore (moore-count grid))
      (:neumann (neumann-count grid)))))

のように書ける。signum!!はsignumのSIMD命令版。*LETは、pvarを扱うlet

;; ランダムな値で埋めて、ノイマン方式で隣人の数を勘定してみる
(progn
  (random-grid)
  (view 8 8)
  (ppp (neighbor-count) :end '(8 8)))

;=>
;     DIMENSION 0 (X)  ----->
;セルの値
;8 8 4 0 0 8 5 6 
;5 8 4 9 0 1 7 2 
;5 7 2 4 9 7 6 3 
;9 4 9 5 5 4 0 2 
;1 2 4 7 5 3 1 6 
;8 1 1 6 7 8 5 8 
;4 5 8 4 8 3 8 7 
;8 7 1 4 1 5 0 2 
;
;     DIMENSION 0 (X)  ----->
;隣人数
;4 4 3 3 2 3 4 4 
;4 4 4 2 3 3 4 4 
;4 4 4 4 3 4 3 3 
;4 4 4 4 4 3 4 3 
;4 4 4 4 4 4 3 4 
;4 4 4 4 4 4 4 4 
;4 4 4 4 4 4 3 4 
;4 4 4 4 3 3 4 3 
;

2008-01-26

Getting Started in *LISP (2)

| 18:01 | Getting Started in *LISP (2) - わだばLisperになる を含むブックマーク はてなブックマーク - Getting Started in *LISP (2) - わだばLisperになる

*LISPのチュートリアルをさらってみることの2回目。

1.2.2 Defining a Simple Automaton

この節では、簡単なオートマトンを作ってみるとのこと。

ルールは下記の通り

  1. 各々のセルは0〜9の値を持つ
  2. セルの偶数ならば、2で割る
  3. 奇数ならば、1足して2を掛ける

ということで、世代を進めるための関数を作ってみる。

(defun one-step ()
  (if!! (evenp!! *automata-grid*)
	(floor!! *automata-grid* 2)
	(*!! (1+!! *automata-grid*) 2)))
  • if!!

*LISPでは、各グリッドが各々のプロセッサに一対一で割り振られていて、それぞれ値を持っている。

この値に対して一斉にある操作をしたい場合(以下面倒なので、SIMD云々と略してみる)は、!!系の名前になっている。

if!!はSIMD版のif。上記、one-stepでは、evenp!!、floor!!、*!!、1+!!がSIMD命令。

色々と定義

;; 状態の数 (0〜9で10通り)
(defvar *total-number-of-states* 10)

;; グリッドに値を設定するが、*total-number-of-states*を法とした数に設定される 
(defun set-grid (newvalue)
  (*set *automata-grid*
	(mod!! newvalue *total-number-of-states*)))

(set-grid 27)

(view 8 3)
;     DIMENSION 0 (X)  ----->
;
;7 7 7 7 7 7 7 7 
;7 7 7 7 7 7 7 7 
;7 7 7 7 7 7 7 7 

;; 乱数を設定してみる。
(set-grid (random!! 27))
(view 8 3)
;     DIMENSION 0 (X)  ----->
;
;3 4 8 4 0 3 6 0 
;1 2 3 9 2 6 2 6 
;7 6 3 4 9 3 3 3 

;; 上記は便利なので、関数として定義
(defun random-grid ()
  (set-grid (random!! *total-number-of-states*)))

;; 何世代かをまとめて実行するユーティリティ
(defun run (&optional (n 1))
  (dotimes (i n)
    (set-grid (one-step))))
  • 実験してみる
(progn
  (random-grid) ; 乱数で埋める
  (view 8 8)
  (run 100)     ; 百世代実行
  (view 8 8))   ; 結果を確認
;=>
;     DIMENSION 0 (X)  ----->
;
;0 3 1 9 2 9 5 4 
;7 3 2 3 7 4 6 3 
;5 5 4 0 4 9 9 3 
;7 8 0 9 0 7 4 5 
;5 6 8 3 0 3 3 0 
;3 2 1 3 4 4 9 9 
;2 8 4 8 4 9 6 7 
;7 4 1 4 5 1 8 0 
;
;     DIMENSION 0 (X)  ----->
;
;0 1 4 0 1 0 2 2 
;4 1 1 1 4 2 2 1 
;2 2 2 0 2 0 0 1 
;4 4 0 0 0 4 2 2 
;2 2 4 1 0 1 1 0 
;1 1 4 1 2 2 0 0 
;1 4 2 4 2 0 2 4 
;4 2 4 2 2 4 4 0 

このパターンの場合、何世代か実行すると、0、1、2、4の数値に収束する。

うーん、勿論シミュレータなので、実際には、ループに展開されているだけなのですが、実機だと実際に65536個のプロセッサで同時に計算できたりするわけで、ロマンですねー。

並列処理で思い出したのですが、Dan Friedman氏の60歳を祝って著名な関係者が記念の講演をしていて、その中にGuy Steel氏の講演もあります。

これまでGLSが研究して来た内容が数々紹介されていて面白いのですが、並列の話もしていました。

この中の説明は、*LISPではなくてConnection Machine Lispの説明になっていますが、並列の話題に限らず、非常に面白い講演なのでおすすめです!

2008-01-25

Getting Started in *LISP (1)

| 18:01 | Getting Started in *LISP (1) - わだばLisperになる を含むブックマーク はてなブックマーク - Getting Started in *LISP (1) - わだばLisperになる

*LISPのシミュレータに何か魅かれるものがあるので、とりあえずGetting Started in *LISPというチュートリアルを試してみることにしました。

Chapter 1. Instant *LISP

1章では、セル・オートマトンを作ってみるようです。

序盤で、セル・オートマトンの解説があって、次に*LISPの使用方法について。実機もシミュレータも、

(*lisp)
(*cold-boot :initial-dimensions '(16 16))

のような感じでスタートさせます。

  • 1.2 Using *Lisp
  • 1.2.1 Defining an Automata Grid

とりあえず、セル・オートマトンの実習開始

(*defvar *automata-grid* 0)
*AUTOMATA-GRID*

でグリッドを作成。初期値は、0

(ppp *automata-grid* :mode :grid :end '(8 5))
;=>
;     DIMENSION 0 (X)  ----->
;
;0 0 0 0 0 0 0 0 
;0 0 0 0 0 0 0 0 
;0 0 0 0 0 0 0 0 
;0 0 0 0 0 0 0 0 
;0 0 0 0 0 0 0 0 

pppは、pretty-print-pvarの略で、グリッドの内容を綺麗に整形して表示してくれます。

その前にpvarですが、parallel variableの略です。

操作に便利なユーティリティを色々と定義しつつ、関数を紹介

  • viewたん
(defun view (&optional (width 8) (height 5))
  (ppp *automata-grid* :mode :grid :end (list width height)))

グリッドを表示するためユーティリティ

  • read-cell
(defun read-cell (x y)
  (pref *automata-grid* (grid x y)))

(read-cell 5 1)
;=>0

一個のセルを表示するユーティリティ。

prefはpvarと、位置情報を引数に取って指定した位置の内容を返すもの。aref的なもの。

gridは、xとyから位置情報を生成する関数の模様。

  • set-cell
(defun set-cell (x y newvalue)
  (*setf (pref *automata-grid* (grid x y)) newvalue))

セルの内容を設定するユーティリティ

*setfは、pvarを操作するためのsetfのようなもので、感覚的にはsetf。

(set-cell 5 1 7)

(read-cell 5 1)
7

(view 8 3)
;=>
;     DIMENSION 0 (X)  ----->
;
;0 0 0 0 0 0 0 0 
;0 0 0 0 0 7 0 0 
;0 0 0 0 0 0 0 0 
  • set-grid
(defun set-grid (newvalue)
  (*set *automata-grid* newvalue))

グリッド全体の値を設定するユーティリティの模様。

*setは、setqのpvar版の模様。

(set-grid 7)

(view 8 3)
;
;     DIMENSION 0 (X)  ----->
;
;7 7 7 7 7 7 7 7 
;7 7 7 7 7 7 7 7 
;7 7 7 7 7 7 7 7 

;; 乱数で埋めてみる
(set-grid (random!! 10))

(view 8 3)
;     DIMENSION 0 (X)  ----->
;
;5 4 0 6 5 2 3 1 
;3 9 6 2 0 1 5 1 
;4 9 9 0 7 6 6 6 

random!!は、通常の(random x)の並列版で、返り値として全体のpvarを返すもの。

2008-01-23

*LISPシミュレータ

| 19:40 | *LISPシミュレータ - わだばLisperになる を含むブックマーク はてなブックマーク - *LISPシミュレータ - わだばLisperになる

どう書くorgのお題:ライフゲームで*LISPのシミュレータを使ってみたわけなのですが、面白いので、もうちょっと追っ掛けてみることにしました。

とりあえず、毎回インストールの度にインストール方法を忘れてしまうので、メモがてら纏めてみたいと思います。

そもそも*LISPってなんだ

*LISPは、シンキングマシンズ社の65536個もプロセッサがある超並列計算機Connection Machineの上で動いていたLISPの処理系でした。

Wikipediaに詳しい説明とマニュアル等のリンクがあります。

Connection Machine用のLISPの処理系としては、当時この会社で働いていた、Guy L. Steel Jr.氏が筆頭となって、そのまんまな名前のConnection Machine Lisp(以下CM Lisp)というものが開発されていたようですが、結局完成はしなかったようで、代わりにこの*LISPが使われることになったようです。CM Lispについては、論文も書かれていますが、新しいアイディアが満載で、かなり強力だったようなので、完成して日の目を見なかったのは残念ですね。まあ、強力過ぎて完成しなかったのかもしれず…。ちなみにCM LispはCLtL2にもリーダマクロの説明等で、ちょこちょこ登場しています。

そんなこんなもあり、CM Lispと、*LISPは結構混同されていることが多いようです。

*LISPは、主にConnection Machineに合わせてマクロで拡張されたCLのスーパーセットになっているようです。また、現実的な需要からか、当時からこのシミュレータも存在してしました。1990年頃から公開されていた様子ですが、2003年に主要開発者のJ. P. Massar氏がANSI規格に沿うように改訂して今に至ります。

ソース入手

シミュレータのソースは下記からダウンロードできます。

インストール

自分が動作確認できた処理系は、AllegroとCLISPです。SBCL、Clozure CLはコンパイルに失敗してしまいます。(詳細後述)

まず、環境に合わせて設定ファイルを書き換え、コンパイルを実行しますが、処理系によっては、若干ソースを修正する必要があります。

  • ANSIに合わせたとか言いつつ、パッケージ名をuserと記載しているままな個所があるので、cl-user等に直します。

パターンとしては、以下の3つです。

user:: -> cl-user::
:user -> :cl-user
"USER" -> "CL-USER"
  • 設定ファイルにソースが展開されたパスを記述します。

ちなみに、unzipをするとディレクトリを作らず、撒き散らかすタイプです。

/var/tmp/starlispにディレクトリを作成して中身を展開したと仮定すると下記のような記述になります。

; make.lisp
(defparameter *defsystem-search-path* '("/var/tmp/starlisp/"))
;
; f20.sys
(define-alias "STARLISP" "/var/tmp/starlisp/")
(define-alias "VERSION" "/")
;
  • ファイル名の修正

f20.sysというファイルをF20.sysという名前に変更するか、リンクします。

大文字にしないと(ms :f20)したときにファイルの呼び出しに失敗します。

もしくは、f20.sysの中の、 :f20〜の個所を:|f20|として、(ms :|f20|)とすれば大丈夫ですが、こっちの方が面倒かと思います。

;
(compile-file "/var/tmp/starlisp/make")
(load *)
(ms :f20)
;〜
;

これで、システムが読み込まれます。

;
(*lisp)
;

とすると、

Thinking Machines Starlisp Simulator.  Version 20.0

と出たりするので、おおっ!とか思いますが、単にパッケージを移動しているだけだったりします。

マニュアル

本格的なマニュアルは、*Lisp Reference Manualというものがあったようなのですが、当然ながら入手困難なようです。

配布物のなかに、tutorial.pdfと、getting-started-guide.txtというチュートリアルがあります。

自分は、PDFで見た目も綺麗ということで、tutorial.pdfを参照してgetting-started-guide.txtは見てなかったのですが、このエントリを書くにあたって、Wikipediaのリンクから辿って、マニュアルを漁っていたところ、getting-started-guideのPDF版を見付けました。

これを眺めたところ、ライフゲームの図が沢山あるので、チュートリアルの題材が思いっ切り今回のどう書くorgのお題のライフゲームだということに気付きました。

当然ながら、コードは洗練されています。思いっきりループ版を投稿したり、その後、このチュートリアルの劣化版のような並列構文版を投稿したりした自分が恥ずかしい…(;´Д`)

…まあ、良いや、誰も気付かないだろうし…。というか改めて確認しましたが、テキスト版のgetting-started-guide.txtよりtutorial.pdfの方が題材にしている処理系のバージョンが古いみたいですので、getting-started-guide.txtがお勧めです。

追記

  • SBCLとか、Clozure CLでのコンパイルが失敗する場所

type-system-deftypes.lispの

(deftype pvar (&optional (element-type '*))
  ;; I have to return a satisfies type with a closure so that typep can work.
  ;; But, returning a closure will blow up both subtypep and the compiler on lucid.
  (let ((closure (*lisp-i::pvar-type-predicate 
                  (cadr (*lisp-i::canonical-pvar-type `(pvar ,element-type))))))
    `(satisfies ,closure)))

;

の個所がコンパイルできないようです。SBCLや、Closure CLでは、SATISFIESにLAMBDA式が渡るのが許されないことが原因のようなのですが、自分のレベルでは、対処方法が分からず…。ここを通過できれば、使えるんですが…。アドバイス等ありましたら是非お願いしたいです!