GNU Smalltalk チュートリアル(その2)

続きです。

前回までのあらすじ

前回は GNU Smalltalkチュートリアルといいつつ、普通の Smalltalk との差分説明でした。なのでほとんどの人をおいてけぼり状態(^^;

とりあえず問題点をまとめますと、

  • 前提知識が普通のSmalltalk とか、どんだけ...。
  • N-Queenアルゴリズムの説明がないぞ(カモノハシ本買えといわれてもなぁ...)
  • みながわけんじさんに 「staticにしてやろうか」 と言われてしまう

なところでしょうか。これはいけない。

そんなわけで、今回のテーマは「せめて、オブジェクト指向らしく」。デザインパターンちっくな設計を織り交ぜつつ、前回の N-Queenアルゴリズムを振り返るような構成でせめたいと思います。

──ていうか、やりなおし?

クラスである意味が無い

前回の run.st を再び振り返れば、

#!/usr/bin/env gst
Eval [
    | result viewer |

    FileStream fileIn: 'nqueen.st'.
    FileStream fileIn: 'nqueenViewer.st'.

    result := (NQueenPuzzle new: 10) solvePuzzle.
    result printNl.

    viewer := NQueenViewer new.
    viewer show: result.
]

こんなでした。図にするならこんな感じ。


(下の方の落書きは気にしないでくだせい)

NQueenPuzzle も NQueenViewer もいちいち new する意味が分からないというもの。これでは「static にしてやろうか」と言われても仕方がないかもしれません。

というわけで、もうすこし「らしい」作りを見せるために、今回は解を説いている真っ最中に状態を表示し続ける・・というのをやってみます。となると、動くチェス盤が必要です。

せっかくの GNU Smalltalk 3.2 なので GTK で作ろうかとも思いましたが、いえいえ「せっかくの」ならば「GNU」が先です。GTK は後の楽しみのとっておいて、今回は みんな大好きスターライトブレイカー..じゃなかった、curses (ncurses)で逝ってみようとおもいます。

(えらく食い合わせが悪そうに思えるのは、きっと気のせいでしょう)

Dependency機構

モデルの更新を随時表示に反映する・・となれば、Observerパターンの出番です。Observerパターンは モデル→ビュー または モデル→コントローラ の依存を基底クラスに持っていくことで依存関係を逆転させるデザインですが、Smalltalk の場合これを Dependency機構と呼び、Object クラスに既に組み込まれています。

Observer パターンとの関係を図にするとこんな感じ。

がおー。(癖になるな〜、このらくがき)

ではさっそく nqueen.st に 通知機構を組み込んでいきましょう。まず Queen クラスですが、

  • nqueen.st
Object subclass: Queen [
    | row column neighbor maxRow |
            ・
            ・
            ・
    advance [
        (row < maxRow) ifTrue: [
            row := 1 + row.
            self changed.
            ^self findSolution ].

        (neighbor advance) ifFalse: [^false].

        row := 1 .
        self changed.
        ^self findSolution
    ]
            ・
            ・
    column [
        ^column
    ]

    row [
        ^row
    ]
]

なかんじで、advance で Queen の row フィールドが変更される度に changed メッセージを発行するようにします。あと、Viewer からアクセスするであろう column, row メソッドを追加します。

続いて NQueenPuzzle クラスにて、

Object subclass: NQueenPuzzle [
    | queenCnt viewer |
    NQueenPuzzle class >> new: aNumber [
        ^(self new) initialize: aNumber; yourself
    ]

    initialize: aNumber [
        queenCnt := aNumber
    ]

    viewer: aObj [
        viewer := aObj
    ]

    queenCnt [
        ^ queenCnt
    ]

    solvePuzzle [
        | lastQueen |
        lastQueen := SentinelQueen new.

        1 to: queenCnt do: [:i | 
            lastQueen := (Queen new)
                setColumn: i neighbor: lastQueen maxRow: queenCnt;
                addDependent: viewer;
                changed;
                yourself.
            lastQueen findSolution.
        ].

        ^lastQueen result
    ]
]

Queen を一つ生成する度に viewer オブジェクトを addDependent: していくコードを追加します。それと忘れてはいけないのは新に Queen を生成したら一度 changed を呼んでおくことで、これをしないと 1マス目に出現した Queen は一歩も動かないかぎりいつまで立ってもステルスモードです。

つづけて、NQueenViewer 側を update: メソッドを追加する段です。

NCurses版 NQueenViewer

cursesUNIX の テキストインターフェイスを作るためのライブラリで、平たく言えば Rogue や vi みたいなのを簡単につくれる仕組みです。ncurses は new curses の略で、cursesGNU による 新しい実装です。

GNU Smalltalk には この ncurses をつかうためのパッケージ、 NCurses があります。前回の NQueenViewer を この NCurses を使って全面的に書き換えたのがこちらです。(ちと長いですが、ご容赦)

  • nqueenViewer.st
PackageLoader fileInPackage: 'NCurses'.

Object subclass: NQueenViewer [
    | puzzle boardWin infoWin step |

    setModel: aNQueenPuzzle [
        puzzle := aNQueenPuzzle.
        puzzle viewer: self
    ]

    initializeScreen [
        NCWindow
            initscr;
            noecho;
            cbreak.

        self initBoardWindow.
        self initInfoWindow
    ]

    endScreen [
        NCWindow endwin.
    ]

    notifyFinish [
        infoWin mvwprintw:0 x:0
            str: 'Finish! step=', step asString,
                '. Press ''q'' key to exit'.
        [infoWin wgetch = $q asInteger] whileFalse: 
            [(Delay forSeconds:1) wait].
    ]

    update: aQueen [
        self updateBoard: aQueen.
        self updateInfo: aQueen.
    ]


    initBoardWindow [
        boardWin := NCWindow
            newwin: puzzle queenCnt * 2 + 1
            cols: puzzle queenCnt * 4 +1
            beginY: 1 beginX: 1.
        self writeBoard.
    ]

    writeBoard [
        1 to: puzzle queenCnt do: [:l|
            self writeBoardLine: l.
            self writeBoardCell: l  ].

        self writeBoardLine: puzzle queenCnt + 1.
    ]

    writeBoardLine: row  [
        | y |
        y := self rowToY: row.
        boardWin
            mvwprintw: y x: 0 str: '+';
            mvwprintw: y x: 1 str:
                (1 to: puzzle queenCnt collect: [:e|'---+']) join
    ]

    writeBoardCell: row [
        | y |
        y := (self rowToY: row) + 1.
        boardWin
            mvwprintw: y x: 0 str: '|';
            mvwprintw: y x: 1 str:
                (1 to: puzzle queenCnt collect: [:e|'   |']) join
    ]

    updateBoard: aQueen [
        self deleteQueen: aQueen.
        self writeQueen: aQueen.
        boardWin wrefresh
    ]

    deleteQueen: aQueen  [
        | col |
        col := aQueen column.
        1 to: puzzle queenCnt do: [:row|
            boardWin mvwprintw: (self rowToY: row) +1
                x: (self colToX: col) +2 str: ' ']
    ]

    writeQueen: aQueen [
        boardWin mvwprintw: (self rowToY: aQueen row) +1
            x: (self colToX: aQueen column) +2 str: 'Q'
    ]

    rowToY: row [
        ^ row -1 * 2
    ]

    colToX: col [
        ^ col -1 * 4
    ]

    initInfoWindow [
        infoWin := NCWindow
            newwin: 1 cols: puzzle queenCnt * 4 +1
            beginY: 0 beginX: 1.

        step := 0.
        infoWin mvwprintw: 0 x: 0 str: 'step:'
    ]

    updateInfo: aQueen [
        step := step + 1.
        infoWin mvwprintw: 0 x: 5 str: step asString.
        infoWin wrefresh
    ]
]

 
メソッド名をみれば大体のやってることは分かると思いますが、問題はその中身。詳細ですね。

パッケージローダー

まず、GNU Smalltalk で ncurses を使うには NCurses パッケージを

PackageLoader fileInPackage: 'NCurses'

でファイルインします。

GNU Smalltalk のパッケージとは、package.xml と .st ファイルを zip で 固めたもので、hogehoge.star という名前になっています。GNU Smalltalk パッケージローダーは、

  1. karnel ディレクトリの親ディレクトリ(/usr/local/share/smalltalk)
  2. .st/packages.xml ファイル に書かれたパッケージ
  3. カレントイメージのあるディレクトリの pacages.xml

の順にパッケージを探します。(詳しくはこちら:Packages -GNU Smalltalk User's Guide)

この手のライブラリをイメージの中に取り込んでいないのが新鮮です。必要なときに必要なだけ、一時的に File in するのがGNU Smalltalk流ということでしょうか。

パッケージのブラウジング

さて、NCurses パッケージを理解するためにそのコードを眺めたいところですが、Smalltalk で クラスライブラリを眺めるにはやっぱりシステムブラウザが便利です。GNU Smalltalk 3.2 からは、GTK+ を用いた VisualGST が利用でき、さらに嬉しさ倍増ですね。コンソールで

$ gtl-browser

と打てば、システムブラウザとワークスペース、トランスクリプトが合体した 今時IDE風のVisualGST が立ち上がります。リッチになったなぁ。

ですが、この立ち上がったままの状態では各種パッケージは読み込まれていません。なので NCurses について調べたいなら、まずこれを FileInしなくてはいけません。それには [File]->[Open]から読み込めばいいハズですが、パッケージの在り処を探すのが面倒くさいので、下のウインドウのタブ Workspace に

PackageLoader fileInPacage: 'NCurses'

と打って、do it (コードを選択して右クリックメニューから実行)しちゃいましょう。すると、

な感じで NCurses Wrapper というクラスカテゴリが登場し、快適環境でパッケージの中身を読むことが出来ます。

NCurses パッケージ

NCursesパッケージですが、中には NCWindow クラス一つしかありません。名前空間 NCurses もなく、ただポツンと NCWindow があるだけ。うーん、パッケージってなんじゃろ。名前空間が作られていないのでパッケージロードしたらそのまま NCWindow という名前が使えます。これはこれでどうなの、と思いますが、うにゅん。

そして NCWindow クラスですが、これは ncurses の単純なラッパーです。NCWindow のメソッドのコメントも、ほとんどが 元ネタの man を参照してね、ばかりだったり(^_^; というわけで、ncurses を使える人ならすぐに使えてしまうでしょう。

わたしは使えないのでこんな本を買ってしまいましたが...。

curses―UNIXユーティリティライブラリ

curses―UNIXユーティリティライブラリ

こういう絶版技術書が楽に手に入るのはいい世の中ですよね。Amazon万歳!

・・と Amazon 賛美から話を戻して、ncurses の man に頼らなくても、NCWindow クラスに examples コードが埋め込まれていますので、最低限の掴みはこれで OK です。

クラスメソッドに examples というカテゴリをつくって、そこにサンプルコードを埋め込むのは Smalltalk の美しき良き文化です。せっかくですので、その examples を話のタネに、ざっくばらんに NCurses パッケージ を説明しましょう。

まず、NCWindow class >> helloWorld。

helloWorld [
	<category: 'examples'>
	self
	    initscr;
	    printw: 'hello world';
	    refresh;
	    getch;
	    endwin
    ]

当然ですがクラスメソッドなので、脳内で s/self/NCWindow/g して読んでください。

ncurses の使い方の基本形は、 initscr で画面を初期化して、ゴニョゴニョして、最後に endwin して終わらせます。GNU Smalltalk の NCurses パッケージでもこれらはそのまま NCWindow のクラスメソッドになってます。このような全体的な初期化・終了等のコードの他に、ncurses の定数や、標準スクリーンへの操作も NCWindow のクラスメソッドとして実装されています。

標準スクリーン(stdscr) とは、その名のとおりstdout のようなスクリーンで、最初から作られていて、デフォルトではそこに出力されるスクリーンです。

ncurses では、ウインドウやパッドというオブジェクトを作って、そこの論理座標に対して文字を書いたり等するのですが、標準スクリーンなら、いちいちウインドウ(NCWindow インスタンス)を作らなくてもつかえるので便利です。

というわけで、前述のとおり標準スクリーンに対する操作は「お前もStaticにしてやんよ」を地で実装されています。例えば上記コードの printw, refresh, getch がそれです。halloWorld example は、みながわさんの完全勝利ですね。

一方インスタンスを作る方の使い方は NCWindow class >> clock メソッド の example が参考になります。

clock [
	<category: 'examples'>
	| screen |
	self
	    initscr;
	    noecho;
	    cbreak;
	    refresh.
	screen := self 
		    newwin: 13
		    cols: 27
		    beginY: 1
		    beginX: 1.
	screen nodelay: true.
	[screen wgetch = $q asInteger] whileFalse: 
		[screen
		    mvwprintw: 3
			x: 6
			str: Date today printString;
		    mvwprintw: 5
			x: 6
			str: Time now printString;
		    wrefresh.
		(Delay forSeconds: 1) wait].
	self endwin
    ]

こちらも標準スクリーンで「おまえも static にしてやろうか」が出来るのですが、そうでないのも出来るということで。

NQueenViewer

というわけで、前回の解を受けて一発書いておしまいな Viwer から、Observer パターンを使って Queen が動く度に 表示を更新するようにパワーアップした NQueenViewer です。

NQueenクラスで NQueen >> advance メソッドに仕込まれた changed メッセージが送られる度に、depandency 機構 をつかって NQueenViewer に update: aQueen なメッセージが届きます。

これらを使う、新たな run.st はこちらです。

  • run.st
Eval [
    | puzzle viewer |

    FileStream fileIn: 'nqueen.st'.
    FileStream fileIn: 'nqueenViewer.st'.

    puzzle := NQueenPuzzle new: 12.
    viewer := NQueenViewer new.
    viewer setModel: puzzle.

    viewer initializeScreen.
    puzzle solvePuzzle.
    viewer notifyFinish.
    viewer endScreen
]

前の NQueenPuzzle と NQueenViewer は確かにサブルーチンでもそのまま表現できましたが、今度の構造はそうはいかないということで、static にされちゃわないようにはなったと思います。

リアルタイム表示自体は 別にOOP でなくても普通に Puzzle から 表示関数を呼べばいいだけなのですが、この様にすることで それこそ Viewer が GTKベースになったとしても、NQueenPuzzle 側にはまったく影響がないという点をキープしつつ リアルタイム表示が出来るのがおいしいのです。

N-Queenアルゴリズム

以上で、Depencency機構 やら NCurses やらの説明は おしまい。ここからは前回棚上げした N-Queenアルゴリズムを見ていきましょう。

カモノハシ本の N-Queen の解アルゴリズムは、

  • よくよく考えたら一列に一つしかQueenを置けないじゃん
  • だったら各列のQueenが何行目にいるかを求めるだけでよくない?

という視点で、1個ずつQueenを増やしながらそのQueen個数での部分解を求めていくアルゴリズムです。

Queen を新たに盤面に足すと、まずその Queen の解(=row位置) を求めさせます(findSolution)。

findSolution の 具体的な解き方ですが、Queen はお隣さん(達)に「私の場所、攻撃できる?」(canAttack)と聞き、「バッチできるよ!」と言われたら、一歩前に進んで(advance)から、また同じように聞きます。で「いあいあ出来ないよ」と言われるまでそれを繰り返すわけです。ちなみに canAttack は Chain of Responsibility パターンになっていて、隣の、隣の、隣の・・と伝言ゲームで「攻撃できる?」とやっています。

もし、Queen が一番最後の row まで到達してしまった場合は、つまりどこにも居場所が無いというわけで、お隣さんに一歩前に進んでもらい、お隣さんたちの部分解をもう一度求め直してもらってからやり直しです。──というのが カモノハシ本 N-Queen パズルのアルゴリズム

本当は何人かが集まって、CRCカードでロールプレイなんかするとわかりやすいのですが、Queen の動きを眺めるのもなかなか理解がしやすいです。・・といってもそのままでは Queen が韋駄天すぎて よく見えないので、

Object subclass: NQueenViewer [
    update: aQueen [
        self updateBoard: aQueen.
        self updateInfo: aQueen.
        (Delay forMilliseconds: 2000) wait
    ]

でゆっくりにしたり、

Object subclass: NQueenViewer [
    update: aQueen [
        self updateBoard: aQueen.
        self updateInfo: aQueen.

        [boardWin wgetch = $n asInteger] whileFalse: 
            [(Delay forSeconds:1) wait].    ]

で、1手ずつ止めながらやって見るとわかりやすいです(ホントは Observer の update でこんなことするのは良くないことなのだけれども)。

一応 アニメーションGIF を作ってみたのですが、ファイルサイズが大きすぎにならないよう最小の4Queen です。でも 4Queen だといまいちですね。実際につくって、やってみるのが一番です。


* * *


実のところ、前回があまりに読み手を置いてけぼりだったのでフレンドリで楽しい感じにしようと、旬のネタをもりこんだり、絵で簡単そうな雰囲気を演出したり、説明をもっと丁寧にしたり等、今回はおおいにコテ入れしたのです。・・・ですがなぜでしょう、とっても「やっちまった」感が拭えません。

うーん、最初に 「N-QueenGNU Smalltalkチュートリアルを書こう!」ってネタを思いついたときは、イケるアイデアじゃん!と、思ったんですけれど。そもそもチュートリアルという方向性がよくなかったのでしょうか(「遊んでみた」のほうが良かったかも)・・・まったく「どうしてこうなった!」です。

そんなこんなで非常にグダグダで大丈夫?という感じですが、きっと次回に続きます。たぶん。

余談

あんまり Linux を使っていなかったわたしですので、今回はじめて ncurses を弄んだのですが、これはお手軽かつ楽しいですね。ついつい時代に逆行して端末上にリッチなアプリを作りたくなってしまいます。

こういうのが Windowsコマンドプロンプトでもできたら、プログラマがもっと増えるかも〜、とか思ってしまいました。(奴は酷すぎデス/結局全部消して書き直すしかないという...orz)

そういう本としては Rogue ちっくなゲームを自作する「デバッグではじめるCプログラミング」があります。

デバッグではじめるCプログラミング

デバッグではじめるCプログラミング

屋根裏書庫から久しぶりに引っ張り出して読み返していたのですが、この本の Linux 版とかあるとプログラミング的にすごく良い(楽しい)でしょうね。ですが、Linux であるということで この本の想定読者には届かないという矛盾。むー、世の中難しいですね。