棒倒し法

棒倒し法とは迷路作成の為のアルゴリズムの一番簡単なヤツである。

かなり前、教えて!gooに上がった質問で、あまりロクなネット上での棒倒し法の解説が当時は無かったので、ググりながらプログラムを作ったのを良く覚えている。

外枠と、中の柱を建てることはできたのですが、棒を倒すことができません。
コンパイルしようとすると、停止してしまいます。
どこがまずいのか、教えてください。

棒倒し法、とは基本的にまずは次のようなマップを用意する。

そしてi = 2、j = 2の地点、つまり左上の最初の柱から2個毎に、つまり、柱の上を移っていくわけだな。

そして柱を「蹴倒す」、と表現してるが、要するに乱数に従って柱の周り東西南北のどれかを一つ塗りつぶす。

ただ、ここにちょっとルールがある。

教えて!gooにも書いたが、再録しておこう。

i = 2の時は上下左右どこへでも棒を蹴り倒して良い。
i ≠ 2の時、棒を上に蹴り倒してはならない。棒は下と左右だけに蹴り倒す事が出来るが、次の付随ルールがある。

左に棒がある場合は下と右にしか蹴り倒せない
左に棒がなかったら下と左右どれかに蹴飛ばして構わない。

単純に言うとi = 2であるかどうか、あとは今いる地点の左のマスが壁なのか否か、で使うべき乱数の幅が変わるのである。

で、この時はC言語で書いて列挙体を駆使して・・・とかやってたが、今回はこれをRacketに移植してみようと思う。

なお、このテの・・・あからさまにC言語ないしはBASICで作られたようなアルゴリズムはLispと相性が悪い。consであるリストをcarしたりcdrしたりmapしたりreduceしたりするのはLispのお家芸だが、配列の要素番号に従ってその中身を書き換えたりするのはLispは苦手だし(破壊的変更だし)、そもそも配列にアクセスするのが面倒くせぇのだ。この辺はLispが、正直苦手な分野だと思っている。

とは言っても極論数値しかないC言語に比べるとコードはある意味「明快」になるのはLispの良さだろう。何故ならシンボルがある以上、型がなくても「名前で色々と判断可能」だからだ。

今回は、棒倒し法による迷路作成プログラムを利用して、Racketでのシェルスクリプト(Windowsで言うトコのBATファイル)の作り方、及び、スタンドアロン・エクセキュータブルの作り方も説明する。

1. 棒倒し法による迷路作成プログラム

最初は取り敢えず、大域変数として次の二つを定義してみる。

(define *empty* #□)
(define *wall* #■)

RacketはUTF-8 Welcomeな処理系なんで、UTF-8で扱えるモノなら全部文字として扱える。#と言うのはRacketでの「文字」を意味してる。

なお、C言語なら''だが、Pythonには「文字」と言う概念がない。

いずれにせよ、これで「空」は□だし、「壁」は■だと決まった。

次に迷路の初期状態、上で見せた写真のような迷路を作るコードを書く。

Lispだとconsばっかしてるんで、要素数を頂いてリストを構築する、ってのは正直ピンと来ない。来ないが出来る。出来るがLispらしくない。

とか葛藤がないわけじゃないが、やってみよう。

;フィールド作成
(define (make-field m n)
　(let ((x (+ m 2)) (y (+ n 2)))
　　(let loop ((i 0) (j 0) (raw '()) (raws '()))
　　　(cond ((= i x) (reverse raws))
　　　　　((= j y)
　　　　　　(loop (+ i 1) 0 '() (cons (reverse raw) raws)))
　　　　　(else
　　　　　　(loop i (+ j 1)
　　　　　　　　(cons
　　　　　　　　　(if (or (zero? i) (= i (- x 1))
　　　　　　　　　　　(zero? j) (= j (- y 1))
　　　　　　　　　　　(and (even? i) (even? j)))
　　　　　　　　　　*wall* *empty*) raw) raws))))))

基本的に行(raw)があり、行の構成が終わったらアキュムレータであるrawsにconsする、と言う考え方だ・・・・・・まぁreverse噛ましてたりするが、いずれにせよ、jが目標値まで到達すればiとjを更新する、そしてそうやって二次元リストを構成していく、と言うのは元のCコードと変わらない。

中でnamed-letによる末尾再帰を行っているが、結局返すべきなのは3パターンしかない。

iが末端(x)に届いたので構築した二次元リストを返すパターン。
jが末端(y)に届いたので、rawの構築が終了。rawはアキュムレータrawsにconsしてraw自体は空リストに戻す。また、iを1進め、jはまた行の先頭を表す0になる。=> (loop (+ i 1) 0 '() (cons (reverse raw) raws))
それ以外は条件に従って壁なり空なりを嵌め込んでいく。 => (loop i (+ j 1) (cons (なんかの条件 *wall* *empty*) raw) raws)

3.の条件に関しては先述した。

そしてここではLispらしく、条件で要素を振り分けつつconsしてる。Cを始めとする殆どの言語では三項演算子、等の力を借りないと出来ないが、Lispなら「全てが式」なので、四項だろうが五項だろうが好きなだけ条件節とその結果をぶっこめる。

さて、make-fieldを使えば先に見せたような迷路の初期状態が見れる。11×11の広さなら次のようなリストのリストが返ってくる。

うん、上手く行ってる。

では次にサイコロを定義する。

次のようにする。

;サイコロ、及び方向を定義
(define (dice n)
　(list-ref '(right down left up) (random 0 n)))

ここではサイコロの「目」を返すのではなく、乱数に従って4方向(右、下、左、上)のうちの一つをシンボルとして返す。これがLispの明解性の一つだ。

ちなみに、教えて!gooの方にも書いたが、「4方向」は平等ではない。右と下はいつも使われるが「左」は左隣が壁なのか否かで使われる、使われないが決まるし、「上」は i = 2 の時しか出てこない、と言うのは最初に書いた。

よって偏りがある・・・と言うかサイコロの「面数」は状況で変わるのだ・・・もっとも実際には四面体サイコロはあっても三面体サイコロなんざねぇけどな(笑)。現実に存在しないサイコロを作れちゃうあたりがプログラミングの良いトコである。

なお、二面体サイコロはコインだな。

さて、次に、サイコロの値によって迷路を書き換える関数を定義する。

次のように書く。

;条件によりn面体サイコロが代わり、
;変換されたベクタのどこを変更するか決める
(define (select n i j field)
　(let ((v (list->vector (map list->vector field)))
　　　(direction (dice n)))
　　(set! (vector-ref
　　　　　(vector-ref v
　　　　　　　　　(case direction
　　　　　　　　　　((down) (+ i 1))
　　　　　　　　　　((up) (- i 1))
　　　　　　　　　　(else i)))
　　　　　(case direction
　　　　　　((right) (+ j 1))
　　　　　　((left) (- j 1))
　　　　　　(else j))) *wall*)
　　(vector->list (vector-map vector->list v))))

出来なくはないが、基本、リストで要素番号を参照するよりベクタで要素番号を参照した方が簡単だと思う・・・・・・それでもフツーの言語よか面倒くせぇけどな。

LispのベクタはLisp内では比較的新しいデータ型だが、これはフツーの言語で言うトコの配列で、一旦定義されてしまえばリストみたいに可変長ではない。

ただ、要素数でアクセス出来る以上、リストに比べると速いデータ構造だ、と言うメリットがある。

ところで、Schemeでは、配列の要素を変更する際にvector-set!を用いるが、これが結構混乱の元である。今回みたいな二次元ベクタの場合、参照要素がどれで変更したい箇所がどれで、と考え出すとこんがらがってしまうのだ。

Lispと配列はマジで相性が悪いが、一方、ANSI Common Lispの場合、それでも混乱が少ないように設計されている。setfの存在である。

setfなら参照したモノを書き換える事が出来る。一方、Schemeだと参照は参照、書き換えは書き換え、となってる為、原理主義だが途中で何をやってたんだかちと忘れちまう事があり得るのだ。

ANSI Common Lispは原理主義ではなく、全般的に総称的で、「似た機能は似た機能」で関数としてまとめてるし、今回のように「参照しつつ書き換え」もフツーに出来る。そして「参照しつつ書き換え」はフツーのプログラミング言語では良くやってるのだ。

# Python の例

>>> ls = ["foo", "bar", "baz"] # リストの定義
>>> ls[0] = "hoge" # リストを「0で参照しつつ」書き換えてるが、これがSchemeには出来ない
>>> ls
['hoge', 'bar', 'baz']
>>>

さて、出来たら最低でも、ANSI Common Lisp的なsetfがSchemeないしはRacketに欲しいトコだが、それを実現するのがsrfi-17であり、パワーはANSI Common Lispのsetfには及ばないが、今回みたいなケースだと重宝する。

(require srfi/17) ;; srfi-17 の呼び出し

;; 元々のSchemeでの書き方
> (define v (vector 'foo 'bar 'baz))
> v
'#(foo bar baz)
> (vector-set! v 0 'hoge) ;; vector-set! と言う専用の関数を必要とする
> v
'#(hoge bar baz)
>
;; SRFI-17 の「一般化されたset!」を利用した書き方

> (define v (vector 'foo 'bar 'baz))
> v
'#(foo bar baz)
> (set! (vector-ref v 0) 'hoge) ;; vector-refで「参照した」値を書き換えるので分かりやすい
> v
'#(hoge bar baz)
>

さて、ところで

「あれ?要素を書き換えてるんで、ここって関数型プログラミングじゃないんじゃない?」

とか思うだろう。その通りだ。

しかし結果的に、破壊的変更をしてるのに破壊的変更されてないのだ(笑)。

何故ならRacketは基本的に、「値渡し」のプログラミング言語だから、だ。

もうちょっと細かく見てみよう。

関数selectにはリストfieldが引数として渡されるが、実は値渡しの為、渡されるのはfieldのコピーになるのだ。

結果、fieldのコピーを関数select内でベクタに変換、そしてそのベクタを破壊的変更した後、リストに変換して返り値としてる。

分かるだろうか?実は引数で受け取ったリストfieldと関数selectの返り値は結果同じものではない。

ちょっと試してみようか。

> (define ls '(foo bar baz)) ;; ls を定義する
> ls
'(foo bar baz) ;; ls の中身
;; 仮引数 ls を受け取り、中でベクタに変換して破壊的変更をした後
;; そのベクタをリストに変換して返す関数を書く
> (define (hoge ls) (let ((v (list->vector ls)))　
　　　　　　　　(vector-set! v 0 'hoge)
　　　　　　　　(vector->list v)))
> (hoge ls) ;; ls に hogeを適用した返り値を見る
'(hoge bar baz)
> ls 　　　;; しかし元データの ls はサッパリ影響を受けてない。バンザイ!
'(foo bar baz)

つまり、理論的な話をすると、いくら破壊的変更をしたとしても元データのコピー対象にだけ行った、と言う場合は関数型プログラミングに則ってるのだ。重要なのは元データを変更しない事。コピーならいくら弄っても構わん、と言う抜け道があるんだな。

(多分このテの話はLand of Lispが詳しい)

さて、そうなると、あとは一般化されたset!とサイコロにより、柱の周りの「どれか」を「空」から「壁」に書き換えるだけ、である。caseを上手く使って場合分けしよう。

書き換えが終わったらベクタをリストに再び変換して返す。

ベクタをリストに変換する組み込み関数はvector->listだけど、ベクタ専用のmapping関数、vector-mapを使う事を忘れない。先にも書いたけど、Schemeの関数はANSI Common Lispと違って総称的ではない。データ型別に適する関数が別々に存在してる。mapはあくまでリスト用なのだ。

さて、ここまで終わったらあとは迷路生成関数make-mazeを作るだけだ。

make-mazeは二次元リストであるfieldを引数に取り、それを元にしてselectを適用しつつ迷路を生成していく。

;maze(迷路)作成
(define (make-maze field)
　(let ((x (length field)) (y (length (car field))))
　　; 端以外は行・列共に偶数の時は壁なので、ループを回す初期値は2、
　　; 以降カウンタは2づつ増やす
　　(let loop ((i 2) (j 2) (field field))
　　　(cond ((>= i (- x 1)) field)
　　　((>= j (- y 1)) (loop (+ i 2) 2 field))
　　　(else
　　　　(loop i (+ j 2)
　　　　　(select
　　　　　　(cond ((= i 2) 4)
　　　　　　　　((char=?
　　　　　　　　　(list-ref (list-ref field i) (- j 1))
　　　　　　　　　*wall*) 2)
　　　　　　　　(else 3)) i j field)))))))

これも基本的にはiが目標値に達して完成した迷路を返す、かjが目標値に到達したんで、iとjを更新するか、あとはjを進めつつselect関数でfieldを弄るか、の3つしかやることがない。

まぁ、iとjを弄るが為再帰関数loopを呼び出す、と言うのも大仰しく見えるかもしれないが、そもそも「末尾再帰とは引数内で計算をする」のでこれでいいのだ。iやjの「更新」でさえ、計算の一種である。

あとは、select関数の第1引数に何を与えるか、と言うことだがこれは最初から書いてて、次のように表現が変えられた。

i = 2の時は使うサイコロは4面体
左隣が壁の時、使うサイコロは2面体
それ以外では3面体サイコロを使う

実際、make-fieldとmake-mazeを組み合わせて何が返るのか見てみよう。

リストのリストが返ってくるが、もう充分迷路臭くなっている。

ところで文字のリストはlist->string関数で文字列に変換する事が出来る。

そして文字列同士はstring-appendで結合可能だ。

これを利用して、迷路を表現した二次元リストを改行を挟みつつ文字列に変換するmaze->string関数を書く。

次のようなカンジだ。

;フィールド(迷路)を文字列に変換
(define (maze->string maze)
　(apply string-append
　　　(map (lambda (x)
　　　　　　(list->string
　　　　　　　(append x '(# ewline))))
　　　　　maze)))

最終的に「文字列のリスト」にstring-appendを適用したいのでapplyのお世話になる。

これを使うと出力の「直前」はこうなる。

結果、端末等の標準出力に送り出すdisplayなぞを用いると次のように出力される。

キチンと迷路が出来てるだろう。

これで一応は完成である。

2. スクリプトファイルの作り方

さて、一応プログラムは書き上がった。Racketのリスナーで評価すればいつでも迷路を自動生成可能にはなったわけだ。

しかし、プログラムを走らせたい毎にRacketを立ち上げるのもどーよ、って話が出てくる。どうせなら端末でコマンドを走らせただけで結果を得られないか、と。

そういう場合、このテの言語には二つの手がある。

シェルスクリプトファイルとしてしまう(あるいはBATファイル@Windows)
コンパイルしてスタンドアロン・エクセキュータブルにしてしまう。

平たく言うと、C言語は1の能力はないが、2を行っているわけだ。

Perl、Python、Rubyなんかは1.で力を発揮してみんなに認められた、と言って良い。

また、Perl、Python、Rubyなんかで書かれたWebアプリと言われるブツは、原理的にはサーバー上での役割はまさしく1.なのだ。ブログも1.の変化球に過ぎない。

さて、Racketもシェルスクリプトとして使える。っつーかシェルスクリプトの「作り方」が分かれば、色んな便利ツールもRacketで書けて自分が使ってるPCで走らせる事が可能だ、と言うことになる。

大まかに言うとシェルスクリプトに必要なのは次の二点である。

シェバング(Sharp-bang)。スクリプトから処理系を指定・呼び出しするオマジナイ。
コマンドライン引数の受け取り方。

まずは1番。

PythonだとUNIX系だろうとWindowsだろうと古典的なUNIX系のシェバン、

#!/usr/bin/env python

でパスからPythonを見つけてくれるようにしてくれた。偉い。

一方、Racketだとまだそこまで進んでいない。

UNIX系だと、インストールパスにも依るが、基本的には

#! /usr/bin/racket

とインストールパスを指定せねばならない。

また、Windowsでは、ファイル冒頭で

; @echo off

; Racket.exe "%~f0" %*

; exit /b

とオマジナイを書かないとならない(なお、Racket.exeを環境変数PATHに登録しておかないとならない)。

次はコマンドライン引数の受け取り方。

Pythonなんかだと、基本的にはimport sysしてsys.argvがコマンドライン引数(のリスト)になってる。

Racketの場合、単一の引数が欲しければcurrent-command-line-arguments、もうちょっと細かく情報を操りたければそのものズバリ、command-lineを用いれば良い。

例えば迷路作成プログラムは端末から二つ引数を受け取って実行したい、とする。

そういうケースを想定すると、C言語なんかでは「そこを」main関数で書くような仕組みになっているが、Racketだと次のように記述するだけで充分である。

;;; Racketの迷路生成プログラムでC言語のmain関数にあたる部分

(let ((argv (map (lambda (x)
　　　　　　　(string->number x 10))
　　　　　　(command-line #:args (x y) (list x y)))))
　(display (maze->string (make-maze (make-field (car argv)
　　　　　　　　　　　　　　　　　　　(cadr argv))))))

例えばargvと言う変数を作っちゃってcommand-lineの返り値を束縛してしまう。

原則、どんなプログラミング言語を用いようとコマンドライン引数は「文字列」である。

従って、今回のような「引数に整数が必要な関数」の場合、文字列から数値に変換しないとならない。そういう場合はstring->number関数が使える。string->number関数の第二引数は「基底」の指定だ。今回は10進数なので10を指定してる。

そしてcommand-lineは何個受け取った引数を渡すか、どんなカタチで渡すか、と言うのをコントロール可能である。従って、mapping関数で文字列から整数へと一気に変えたいので、リストとして返す形式を選んだ。

そうすると、結果argvは整数のリストとなる。argvの第0引数をmake-fieldの第1引数に渡し、第1引数を第2引数に渡し、で計算がスタートする。

UNIX/Linux系OSだとスクリプトを端末で走らせたい場合、chmod +x で実行許可を与えなければならないが、いずれにせよ、端末で・・・例えばこの場合、maze.rktとファイル名を名付けていたら、それ＋二つの引数でスクリプトが実行される。

なお、この時点で一応全ソースをあげておこう。

スクリプトファイルで完全だったら、残り、スタンドアロンな実行形式も「そのまま作成可能だ」と言う意味だからだ。

maze.rkt

3. 実行ファイルの作り方

さて、先にも書いたが、端末でスクリプトを単独実行出来るようにプログラムを書ければ、Racketで実行ファイル、あるいはWindowsで言うトコのexeファイルを作る事は難しくない。

難しくない、と言うことは、貴方がRacketで書いたプログラムはRacketが無い環境のPCへも配布可能で、またそこで動く、と言うことである。

が、その前に「実行ファイルとは何か」一応説明しておこう。

元々、Lispの前提では、コンパイルしようとしまいと、そのLispが無い環境では「動かない」と言うのが原則。

つまり、「とあるコード」がコンパイルされてようがされてまいが、そいつを動かす為にはそのコードが書かれた「環境」が必要だと言うことだ。要はユーザーがそのコードを動かす為には同じLisp環境をインストールする必要があるわけだ。

不便だと思う?

でも実のこと言うと殆どのプログラミング言語はそうなんだ。

例えば昔のVBの話は聞いた事があるだろう。ランタイムヘル、って奴だ。ぶっちゃけるとこの「ランタイム」と言うのがVisual Basicの走る「環境」である。Visual Basicでコンパイルしようとしまいと関係ないのだ。そして適した「環境」がなければまた別の「ランタイム」をダウンロードしてインストールせなアカン、と言うのをVBユーザーが「ランタイム地獄」と評したわけだな。

JavaはJVMを要する。結果、原理的にはJavaで書いたプログラムにやっぱり「スタンドアロン」、つまり単独実行可能なexeファイルと言うのはあり得ない。JVMと言う名の「Java用インタプリタ」を、コンパイルしても要求するのだ。

Microsoft製言語じゃないから「別途インストールする」必要が生じるのか?半分Yesで半分Noだ。例えばC#も結果Javaと変わらん。別途インストールする必要がないのはMicrosoft製だから仮想マシンがWindowsに最初から入ってるからだ。結局、C#のソフトでも「単独実行可能なexeファイル」なんつーのは無い。

じゃあ、Microsoftが技術力がないからこうなってんだろうか。Appleは?ハッキリ言うけどAppleはもっと酷い。Objective Cは本当に「PCのOS丸ごと」ひっついてるような状態になってて、これから何かを引き剥がすのは並大抵ではない。そこでは全てがOS Xの一部であり、Objective Cの開発環境の一部となっている。

だからこそMacで開発されたブツは同じUNIX系であるLinuxへ持ってきづらい。Macで生まれたブツは全部Objective Cが形成する「環境」から糸を引いた納豆みてぇに雁字搦めになってて引き剥がせない。

このMac OS Xのヘンな状況はSmalltalkと言う言語環境の影響を受けている。そう、OS Xになろうがなるまいが、Macは最初からXeroxのSmalltalk環境が織りなす「オブジェクト指向」の方に親和性を持っていたのだ。

Smalltalkも誤解を畏れずに言うと、作った「作品」はSmalltalkの外に持ち出す事が出来ない。Smalltalkと言う「閉じた」環境の中でしか活き活きしねぇのだ。水槽の外に出すと死んじまうんだよ(笑)。

じゃあ、やっぱり単独実行可能なオブジェクトファイルを作れるC言語は優秀なんだろうか。これもYesでありNoである。

素のCだとその通りなんだけど、素のCで出来る事なんざたかが知れている。

ところが外部ライブラリを使ってプログラミングを始めると・・・そう、結果、そのプラットフォームから「引き剥がすのは」難しくなるのだ・・・結局どの言語でもある「作品」を作ったらそれが生まれた「環境」から引き剥がすのは難しい。

結果同じなのである。大同小異だ。

でも「移植性」を考えると、CPUとメモリの上で直接走らせるよか、何らかの「環境」・・・カッコ付けて言うと「VM」とか「仮想マシン」上で走らせた方がラクなんだ、ってのがこの20年くらいの結論なのだ。スタンドアロンファイルは小さくて軽くて、でも仮想マシンは大きくて重い?文句言われても結果後者の方がアプリケーションの移植性は高いんだよ。前者は一体「いつダメになるか」分からん。

Wizardryはディスクの中にPascalの仮想マシンも詰め込まれていた。

JavaはJVMをインストールしてください、とユーザーに頼む。別にLispもユーザーにインストールしてください、って頼んで悪いことはない。「仮想マシン」と言う意味では両者共仕組みは殆ど変わらないのである。

ただ、それでも「単独実行ファイル」を作りたい、と言う願いはあるこたぁある。願いはあっても「それって色々な条件よりなかなか難しいんだな」と言うことをまずは把握してもらいたい。

同様の理由より、Pythonでソフトウェアを書いた場合、やっぱり「単独実行ファイル」を作るのは難しい・・・いや、そういうツールもあるこたぁあるんだが。

これは実は仕組みとしてはこういう事だ。

Pythonはインタプリタや仮想マシンを備えてるんだけど、中に「コア」と呼ばれる中核部分がある。

そいつを切り離(または複製)して小さなインタプリタ/仮想マシンを作り、それを作成したフォルダに入れるんだな。

それで貴方の書いたプログラムと、それが必要とするライブラリを同梱する。

そうして「配布可能な」exeファイルが作られるんだ。

でもこれって見た目だけで(笑)、Cで作られる実行ファイルに比べると同じことしててもメチャクチャ大きかったりする(笑)。CD1枚分くらいの大きさ、とかな(笑)。

うん、要するに、幾分小さいとは言っても実はシステム全部詰めてる、ってのは詰めてるわけ。Cで言う「実行ファイル」とは明らかにニュアンスが違うね。

ただ、Pythonだけじゃなくって、Lispなんかでもこうやって「コアとその他モロモロ」で実行ファイルを作る例が多い。

そして実行ファイルってのはなかなか悩ましい問題で、じゃあ、Cが作るのは軽いから良い、って問題にもならん、ってのは既に書いたよね?結局Cだけでプログラムを書かない以上、メンドい問題は必ず出てくるし、C自体は取り立ててポータビリティが高いわけではない、ってのは何度か指摘してる通りだ。Cの移植性伝説?ウソだろ(笑)。

とまぁ、背景を理解してもらって。

それでもRacketでスタンドアロン実行ファイル(Windowsで言うexeファイル)を作るのは凄く簡単だ。全てのLisp処理系でダントツで簡単だ、と言わせてもらおう。

単にプルダウンメニューからこれを選ぶだけ、だ。