for VisualWorks 7.8 / 7.7 / 7.6 with Jun790
フィボナッチ数を求めるプログラムは、通常、以下のようになりますが、40ぐらいのフィボナッチ数を求めるあたりから、ものすごい手間がかかりだします。2のn乗のオーダーで計算量が増加です。
Core.Integer methods for 'mathematical functions' fibonacci "12 fibonacci." "40 fibonacci." self negative ifTrue: [^nil]. self = 0 ifTrue: [^0]. self = 1 ifTrue: [^1]. ^(self - 1) fibonacci + (self - 2) fibonacci
それを軽減するためには、連想計算というリフレクティブな手法を用いるのが効果的であることが知られています。本日(2010/12/13)、学生とペアプログラミングしながら作りましたので、それを紹介しておきます。
Core.Integer methods for 'mathematical functions' fibonacci "12 fibonacci." "100 fibonacci." | aValue aCode aString anIndex | self negative ifTrue: [^nil]. self = 0 ifTrue: [^0]. self = 1 ifTrue: [^1]. aValue := (self - 1) fibonacci + (self - 2) fibonacci. [aCode := Integer sourceCodeAt: #fibonacci. aString := 'aValue :='. (anIndex := aCode findString: aString startingAt: 1) > 0 ifTrue: [| aStream | aStream := (String new: aCode size + 1024) writeStream. [(1 to: anIndex - 1) do: [:index | aStream nextPut: (aCode at: index)]. aStream nextPutAll: 'self = '; nextPutAll: self printString; nextPutAll: ' ifTrue: [^'; nextPutAll: aValue printString; nextPutAll: '].'; crtab. (anIndex to: aCode size) do: [:index | aStream nextPut: (aCode at: index)]. aCode := aStream contents] ensure: [aStream close]. Integer compile: aCode classified: #'mathematical functions']] on: Object errorSignal do: [:anException | anException return]. ^aValue
プログラムの実行中に、その実行中のプログラム自身を書き換えて(コンパイルし直して)います。まさに動的な(フルな)リフレクションになりますでしょ。100ぐらいのフィボナッチ数も平気です。
|
Core.Integer methods for 'mathematical functions' fibonacci "12 fibonacci." "100 fibonacci." | aValue aCode aString anIndex | self negative ifTrue: [^nil]. self = 0 ifTrue: [^0]. self = 1 ifTrue: [^1]. self = 2 ifTrue: [^1]. self = 3 ifTrue: [^2]. self = 4 ifTrue: [^3]. self = 5 ifTrue: [^5]. self = 6 ifTrue: [^8]. self = 7 ifTrue: [^13]. self = 8 ifTrue: [^21]. self = 9 ifTrue: [^34]. self = 10 ifTrue: [^55]. self = 11 ifTrue: [^89]. self = 12 ifTrue: [^144]. self = 13 ifTrue: [^233]. self = 14 ifTrue: [^377]. self = 15 ifTrue: [^610]. self = 16 ifTrue: [^987]. self = 17 ifTrue: [^1597]. self = 18 ifTrue: [^2584]. self = 19 ifTrue: [^4181]. self = 20 ifTrue: [^6765]. self = 21 ifTrue: [^10946]. self = 22 ifTrue: [^17711]. self = 23 ifTrue: [^28657]. self = 24 ifTrue: [^46368]. self = 25 ifTrue: [^75025]. self = 26 ifTrue: [^121393]. self = 27 ifTrue: [^196418]. self = 28 ifTrue: [^317811]. self = 29 ifTrue: [^514229]. self = 30 ifTrue: [^832040]. self = 31 ifTrue: [^1346269]. self = 32 ifTrue: [^2178309]. self = 33 ifTrue: [^3524578]. self = 34 ifTrue: [^5702887]. self = 35 ifTrue: [^9227465]. self = 36 ifTrue: [^14930352]. self = 37 ifTrue: [^24157817]. self = 38 ifTrue: [^39088169]. self = 39 ifTrue: [^63245986]. self = 40 ifTrue: [^102334155]. self = 41 ifTrue: [^165580141]. self = 42 ifTrue: [^267914296]. self = 43 ifTrue: [^433494437]. self = 44 ifTrue: [^701408733]. self = 45 ifTrue: [^1134903170]. self = 46 ifTrue: [^1836311903]. self = 47 ifTrue: [^2971215073]. self = 48 ifTrue: [^4807526976]. self = 49 ifTrue: [^7778742049]. self = 50 ifTrue: [^12586269025]. self = 51 ifTrue: [^20365011074]. self = 52 ifTrue: [^32951280099]. self = 53 ifTrue: [^53316291173]. self = 54 ifTrue: [^86267571272]. self = 55 ifTrue: [^139583862445]. self = 56 ifTrue: [^225851433717]. self = 57 ifTrue: [^365435296162]. self = 58 ifTrue: [^591286729879]. self = 59 ifTrue: [^956722026041]. self = 60 ifTrue: [^1548008755920]. self = 61 ifTrue: [^2504730781961]. self = 62 ifTrue: [^4052739537881]. self = 63 ifTrue: [^6557470319842]. self = 64 ifTrue: [^10610209857723]. self = 65 ifTrue: [^17167680177565]. self = 66 ifTrue: [^27777890035288]. self = 67 ifTrue: [^44945570212853]. self = 68 ifTrue: [^72723460248141]. self = 69 ifTrue: [^117669030460994]. self = 70 ifTrue: [^190392490709135]. self = 71 ifTrue: [^308061521170129]. self = 72 ifTrue: [^498454011879264]. self = 73 ifTrue: [^806515533049393]. self = 74 ifTrue: [^1304969544928657]. self = 75 ifTrue: [^2111485077978050]. self = 76 ifTrue: [^3416454622906707]. self = 77 ifTrue: [^5527939700884757]. self = 78 ifTrue: [^8944394323791464]. self = 79 ifTrue: [^14472334024676221]. self = 80 ifTrue: [^23416728348467685]. self = 81 ifTrue: [^37889062373143906]. self = 82 ifTrue: [^61305790721611591]. self = 83 ifTrue: [^99194853094755497]. self = 84 ifTrue: [^160500643816367088]. self = 85 ifTrue: [^259695496911122585]. self = 86 ifTrue: [^420196140727489673]. self = 87 ifTrue: [^679891637638612258]. self = 88 ifTrue: [^1100087778366101931]. self = 89 ifTrue: [^1779979416004714189]. self = 90 ifTrue: [^2880067194370816120]. self = 91 ifTrue: [^4660046610375530309]. self = 92 ifTrue: [^7540113804746346429]. self = 93 ifTrue: [^12200160415121876738]. self = 94 ifTrue: [^19740274219868223167]. self = 95 ifTrue: [^31940434634990099905]. self = 96 ifTrue: [^51680708854858323072]. self = 97 ifTrue: [^83621143489848422977]. self = 98 ifTrue: [^135301852344706746049]. self = 99 ifTrue: [^218922995834555169026]. self = 100 ifTrue: [^354224848179261915075]. aValue := (self - 1) fibonacci + (self - 2) fibonacci. [aCode := Integer sourceCodeAt: #fibonacci. aString := 'aValue :='. (anIndex := aCode findString: aString startingAt: 1) > 0 ifTrue: [| aStream | aStream := (String new: aCode size + 1024) writeStream. [(1 to: anIndex - 1) do: [:index | aStream nextPut: (aCode at: index)]. aStream nextPutAll: 'self = '; nextPutAll: self printString; nextPutAll: ' ifTrue: [^'; nextPutAll: aValue printString; nextPutAll: '].'; crtab. (anIndex to: aCode size) do: [:index | aStream nextPut: (aCode at: index)]. aCode := aStream contents] ensure: [aStream close]. Integer compile: aCode classified: #'mathematical functions']] on: Object errorSignal do: [:anException | anException return]. ^aValue
以下のPrologとLispのリフレクティブなフィボナッチ数の計算プログラムもたどってみてください。
時計のプログラムをダウンロードし、ファイルイン(fileIn)して、アナログ時計とデジタル時計の両方を動かします。
| aString aURL aFilename | aString := 'http://www.cc.kyoto-su.ac.jp/~atsushi/Programs/VisualWorks/Reflection/Foo-Clock.st'. aURL := JunURL named: aString. aURL exists ifFalse: [^nil]. aFilename := Filename defaultDirectory construct: aURL asURI tail. aURL downloadTo: aFilename. aFilename exists ifFalse: [^nil]. aFilename fileIn. #{FooClockModel} value example3
|
アナログ時計とデジタル時計の両方を動かしたプログラム(FooClockModelのクラスメソッドexample3)を閲覧します。
| aBrowser aWindow aPackage aNavigator aClass aProtocol aSelector | aBrowser := #{Refactory.Browser.RefactoringBrowser} value open. aWindow := aBrowser builder ifNil: [^nil] ifNotNil: [:aBuilder | aBuilder window]. aWindow displayBox: (200 @ 100 extent: 800 @ 600). aPackage := Store.Registry packageNamed: 'Foo-Clock'. aPackage ifNil: [^nil]. aNavigator := aBrowser navigator. aNavigator selectPundle: aPackage. aClass := FooClockModel class. aProtocol := #examples. aSelector := #example3. (aNavigator state) classesAndNameSpaces: (Array with: aClass); protocols: (Array with: aProtocol); selectors: (Array with: aSelector). aNavigator setState: aNavigator state; changed. Smalltalk at: #FooClockBrowser put: aBrowser. ^#{FooClockBrowser} value
|
アナログ時計の秒針を描き出すプログラム(FooAnalogClockViewのインスタンスメソッドdisplayTickHandOn:)を閲覧します。
| aBrowser aNavigator aClass aProtocol aSelector | aBrowser := #{FooClockBrowser} value. aBrowser ifNil: [^nil]. aNavigator := aBrowser navigator. aClass := FooAnalogClockView. aProtocol := #displaying. aSelector := #displayTickHandOn:. (aNavigator state) classesAndNameSpaces: (Array with: aClass); protocols: (Array with: aProtocol); selectors: (Array with: aSelector). aNavigator setState: aNavigator state; changed. ^aBrowser
|
そのソースコードを取り出し、秒針の色と太さを変更します。現在、動作しているアナログ時計の秒針の色と太さが変わると同時に、プログラムのソースコードも変わっているでしょ。
| aClass aProtocol aSelector aCode aString anIndex aBrowser aNavigator | aClass := FooAnalogClockView. aProtocol := #displaying. aSelector := #displayTickHandOn:. aCode := aClass sourceCodeAt: aSelector. aString := 'paint: self selectionForegroundColor;'. (anIndex := aCode findString: aString startingAt: 1) > 0 ifTrue: [aCode := aCode copyReplaceFrom: anIndex to: anIndex + aString size - 1 with: 'paint: ColorValue red;']. aString := 'lineWidth: 1;'. (anIndex := aCode findString: aString startingAt: 1) > 0 ifTrue: [aCode := aCode copyReplaceFrom: anIndex to: anIndex + aString size - 1 with: 'lineWidth: 3;']. aClass compile: aCode classified: aProtocol. aBrowser := #{FooClockBrowser} value. aBrowser ifNil: [^nil]. aNavigator := aBrowser navigator. aNavigator setState: aNavigator state; changed. ^aBrowser
|
今度は、デジタル時計の時刻を描き出すプログラム(FooAnalogClockViewのインスタンスメソッドdisplayTickHandOn:)を閲覧し、3秒待って(実質的には4秒後に)色を変更してみましょう。まさにリフレクションですね。
| aBrowser aNavigator aClass aProtocol aSelector aCode theString aString anIndex | aBrowser := #{FooClockBrowser} value. aBrowser ifNil: [^nil]. aNavigator := aBrowser navigator. aClass := FooDigitalClockView. aProtocol := #displaying. aSelector := #displayTimeOn:. (aNavigator state) classesAndNameSpaces: (Array with: aClass); protocols: (Array with: aProtocol); selectors: (Array with: aSelector). aNavigator setState: aNavigator state; changed. 3 seconds wait. aCode := aClass sourceCodeAt: aSelector. theString := 'graphicsContext paint: ColorValue blue.'. (anIndex := aCode findString: theString startingAt: 1) > 0 ifTrue: [^nil]. aString := 'text displayOn: graphicsContext'. (anIndex := aCode findString: aString startingAt: 1) > 0 ifTrue: [aCode := aCode copyReplaceFrom: anIndex to: anIndex + aString size - 1 with: theString , (String with: Character cr with: Character tab) , aString]. aClass compile: aCode classified: aProtocol. aBrowser := #{FooClockBrowser} value. aBrowser ifNil: [^nil]. aNavigator := aBrowser navigator. aNavigator setState: aNavigator state; changed. ^aBrowser
|
アプリケーション(時計)を動かしている真っ最中に、そのプログラム(ソースコード)を閲覧し、編集し、変更を施した途端に、アプリケーションの動作に反映され、プログラムの閲覧内容にも当該の変更が即座に反映されます。上記の一連のプログラム群は、この「フル・リフレクション」を行うプログラムだったわけです。ここまでを可能にした統合化プログラミング環境(統合開発環境:IDE:Integrated Development Environment)は、なかなか無いのではないでしょうか…。
for VisualWorks 7.8 / 7.7 / 7.6 with Jun790