高校数学の窓LaTeX版: 質問＜３６２８＞２００７／１０／１９from=BOXY「DO〜LOOPのBASICプログラム」

質問させてください。

100 FOR x=1 TO 100
110    FOR y=x TO 100
120       LET a=x
130       LET b=y
140       DO
150          LET r=MOD(a,b)
160 IF r=0 THEN EXIT DO
170 LET a=b
180 LET b=r
190 LOOP
200 IF b=1 THEN
210 LET z=SQR(x^2+y^2)
220 IF INT(z)=z THEN PRINT x,y,z
230 END IF
240 NEXT y
250 NEXT x
260 END

BASICプログラムですが、実行結果の表示とプログラムの意味が
理解できません。の表示になるのですが、
特に前半のDo〜LOOP構文の意味がいまいち理解できません。
アドバイスをお願いいたします。

★希望★完全解答★

いやあ、BASICですか。分かりませんね、こりゃ(苦笑)。
そもそもインデント無しのソースコードって読むの辛いです。どこがブロック構造なんだかちっとも分かりゃしない。現代的じゃない。
さすがFortran直系の言語です(苦笑)。
誰かが

今日のすべての言語はFortranかLispに基づいている。まずい方がFortranで、すばらしい方がLispだ。

とか言ってましたが、むべなるかな、と言うカンジです。
あ、別にBOXYさんのせいじゃありませんよ。こんなの教える、って決めた方が悪いと思います。時代遅れもはなはだしいです。

とか愚痴っててもしょーがないんで、取り敢えず走らせるだけ走らせてみましょうか。
今回、プログラムを走らせるBASICは十進BASICと呼ばれるモノです。Linux版があったので助かりました。
そしてその後、Schemeを使ってBASICのコードを翻訳してみます。その過程で「何が行われているか」分かるでしょう。僕の方も手探り状態なんで(笑)、まあ、一歩一歩進めてみましょうか。
なお、プログラミング言語Schemeに付いては大体の概略は質問＜3567＞、質問＜3590＞、質問＜3609＞辺りに書いていますんで、ザーっと目を通しておいてください。
ないしは初心者向けのサイトでScheme入門と言う易しい入門サイトもありますし、また、Windowsユーザーでしたら、タダで手に入り、遊びながらSchemeの基本が学べる魔法言語リリカル☆Lispと言うアドベンチャー・ゲーム風のチュートリアルソフトがあります(恐らくラストまで進むのに1日かからないでしょう)。

魔法言語リリカル☆Lisp画面写真

BASICを初めて習って大変なのに・・・・・とか思うかもしれませんが、絶対損はさせないのでやってみてください。

閑話休題:BASICは手続き型言語の入門用としては著名ですが、一方Schemeは関数型言語の入門用として著名な言語です。世の中にはたくさんの手続き型言語があって(例えばC言語、Pascal、Java等)、そっちの方が現時点で確かにポピュラーですが、現在は関数型言語の方がある意味、先端技術として注目を集めています(代表的なトコでHaskell、OCaml等)。ソフトウェアの開発効率としては関数型言語の方が優れてる、と言うのがその注目を集めてる理由なんだそうですが、一方、関数型言語は学ぶのが難しいと言われています。
しかしながら、ホントの事を言うと、関数型言語は学ぶのが難しい、と言うよりも、手続き型言語を徹底して学んだ人間にとっては、思考回路を関数型言語に合わせるのが難しい、と言うのが事実のようです。つまり、どうせやるならより初心者に近い時点で関数型言語の思考形式にある程度慣れた方が得策だ、と言う事です。こればっかりは知ってる方が知らないより損なのです。
と言うワケで、将来的な事を考えたら、この時点でSchemeを触った方がイイ、と言う事を明言しておきます。BASICに習熟すればするほど、関数型言語はどんどんどんどん分からなくなっていくでしょう。
一昔前だったらプログラミング言語を「買う」事で余計なコスト/リスクが生じて、こう言う「当たって砕けろ」式の学習法は勇気とお金のいる行動だったのですが、生憎、今は殆どのプログラミング言語は(Microsoft関係を除き)殆どタダで手に入るありがたい世の中になっています。分からなかったら分からなかったでうっちゃらかしておいて構わないので取りあえず触っておくだけ触っておけと言う事です。

では取りあえず、十進BASICを使って問題のソースコードを走らせてみましょうか。

	端末を使って十進BASICを起動する。
	十進BASICが立ち上がる。
	問題のソースコードを十進BASICにコピペする。
	[実行]ボタンを押してプログラムを走らせると、結果が表示される。

なるほどね。確かに $\sqrt{x^2+y^2}=z$ の表示になっていますね。
さて、なかなか十進BASICは賢いようで、[実行]した後、ソースコードをインデント付きに書き換えてくれています。以下はその「インデント付き」のソースコードです。

100 FOR x=1 TO 100
110    FOR y=x TO 100
120       LET a=x
130       LET b=y
140       DO
150          LET r=MOD(a,b)
160          IF r=0 THEN EXIT DO
170          LET a=b
180          LET b=r
190       LOOP
200       IF b=1 THEN
210          LET z=SQR(x^2+y^2)
220          IF INT(z)=z THEN PRINT x,y,z
230       END IF
240    NEXT y
250 NEXT x
260 END

上のインデント付きのソースコードだとどこからどこまでがブロック（一区切りの処理）なのかとても分かり易くなっていますね。行頭が揃っているトコロが1ブロックです。
何故ブロックが重要なのか?亀田は正直、全然BASICなんてやった事が無いですし、あまりハッキリとした事は言えないんですが、一般的に現代的な言語だとどれも、ある処理だけ取り出して単一のプログラムとして書くことが出来ます。これを専門的にはカプセル化と呼ぶらしいんですが、これがBASICには出来ないんです。非常に原始的と言わざるを得ない。
もちろん、BASICでもサブルーティンを設定して・・・・・と言うような事は出きるそうですが、もっとハッキリとしたGo To文なんかで明示しないと目標としたサブルーティンに飛べない。かつ、メインのプログラムに戻るときゃあどうすんだ?とか色々とメンド臭い事柄が生じます。従って、原則BASICの流儀としては一つのソースでは一つのプログラム、とならざるを得ない。ちょっと複雑な処理をしようとしたらたちまちソースが大きくなってしまって、たとえ自分がソース書いていても何やってんだか分からなくなりそうです。行数が32,768行なんかに肥大したらどうすんでしょうね(笑)?
一方、現代的なプログラミング言語の殆ど(例えばPerl、Python、Ruby等)はBASICの仲間であるインタプリタですが、こう言うメンド臭い作業は必要としません。同じ一枚のテキストファイルにプログラムを書き込む以上、どのプログラムからどのプログラムに飛ぼうが自動で見つけて処理してくれます。従ってGo To文なんて使う必要も無く、書く側から言うと「小さいプログラムを一つづつ書いて」全体として処理が一環していればいい、と言う利点があるんです。その方が書き間違いしても見つけやすいですしね。32,768行の大きな一つのソースを書くよりは8行程度の小さいプログラムが4,096個あった方がマシだ、と言う事です。そしてSchemeもこう言う特質を備えた言語です。
さて、では、まずは問題のDo〜LOOP構文(140〜190)を見ていきたいと思いますが、その前に一つプログラミング言語の約束事を押えておきましょう。
それはどんな言語(例えばC言語)でもそうですが、原則、

処理はソースの上から始まって下へと行われる

と言うことです。まあ、例外もひょっとしたらあるかもしれませんが、少なくとも亀田は下から上へ、ってのは知りませんね。あったとしてもそんなの使いづらくてしゃーないです(人間は横書きだったら上から下へと読んでいく、ってのが習慣だから、です)。
右から左へ・・・・・ってのも知りません(笑)。まあ、そんな言語作ったら是非ともムーディ勝山と名付けて欲しいトコなんですが(右から左へと受け流す言語・笑?)、いずれににせよ、今のトコ、そう言ったルールを採用している言語は無いと思います。
何が言いたいか、と言うと、原則Do〜LOOP構文(140〜190)の処理が終わらないとそれ以降の処理が為されない、と言う事です。つまり、200行目以降はDo〜LOOP構文(140〜190)の処理の結果を用いて「何か」を計算している。また、同様の理由で130行目までの処理が終わらないとDo〜LOOP構文(140〜190)の処理が始まらない、と言う事です。取りあえずBASICを知らない僕でもあくまでプログラミング言語の一般常識でそこまでは類推出きるのです。
さて、僕はBASICのDo〜LOOP構文は「繰り返し計算だろ」と言う予測は出来ましたが、ところが具体的な書式は知らない。そこで調べてみました。

◇ DO〜LOOP
　EXIT DO文が実行されるまで，DO行とLOOP行の間に書かれた文を繰り返す。
BASIC入門より

ああそうですか。なるほど。分かりました。
ではこの情報だけを元にDo〜LOOP構文(140〜190)だけをSchemeでカプセル化してみましょう。
ポイントとしてはa、bと言う数は何だか分からない。が、しかし、その数はDo〜LOOP構文(140〜190)以前のソースから渡される事だけは分かっています。従ってプログラム・・・・・名前はそのまんまdo-loopとしますが、do-loop内では定義する必要はない、と言う事です。
また繰り返し計算が何らかの条件を満たした場合、その計算結果を明示しないとなりません。その計算結果を利用して200行目以降のプログラムが処理してくれるわけですが、BASICの場合、EXIT DOだけ書けばいいようですが、Schemeの場合、明解な返り値を設定しなければならない、って事です。しかしこれは実はそんなに難しく無いです。
最初に言っておきますが、これはズバリ、再帰構造です。再帰構造に付いてはあとで説明するとして、では、Schemeで書いたプログラムdo-loopのソースをご紹介します。

恐らく、局所変数letに関しては、BASICもSchemeも同じようなものでしょう。ですからそれに付いては説明しません。また、if構文に関してもBASICでも似たような構造でしょう。その辺は上のソースを今まで培ってきたBASICの知識で読んでみてください。そしてそのあたりは特にポイントじゃないんです。
まず、一つ目のポイントとしては、BASICのソースにあるMOD、そしてSchemeで言うmoduloと言う命令です。
これは原則同じ命令を表していて、剰余を計算する命令です。例えば、BASICでは

MOD(3,2)→1

となるでしょうし、Schemeでも

(modulo 3 2)→1

となります。何故なら、3を2で割った余りは1だから、ですよね。単純に余りを求めているんです。
さて、BASICではrが0だったらEXIT DOしろ、と読めます。この部分ですよね。

160          IF r=0 THEN EXIT DO

この部分がSchemeで言うと以下の部分です。

b ;bを返す

SchemeがEXIT DOの代わりに何故bを返しているのか、と言うのは後で説明しますが、取りあえずここで分かるのは、aがbで割り切れる時、つまりrが0だった時にDo〜Loopを脱出しろ、って命令になっている。言い換えるとこれが脱出条件で、その時Do〜Loopが繰り返し計算を終えるのです。(つまり、これが無いと、プログラムはDo〜Loop内で延々と計算を繰り返す事となるんです)。
では問題はaがbで割り切れない場合はどうなるか、って事です。今、ここのブロックをカプセル化した時、a、bがどんな数かは問わない事としました。故にこの部分だけ見ると、a、bはどんな数を代入してもOKです。従って一般にaがbで割り切れるとは限らない。
さて、もう一度Schemeのソースに戻って良く見てほしいんですが、擬似コードとしては次のようになってるんです。

プログラムdo-loopを定義する

プログラムdo-loopの引数はaとbの二つの数とする

局所変数としてrを定義する

rが0だったらbを返す

それ以外だったらプログラムdo-loopを引数b、rとして呼び出す

分かりますか?ポイントは5番です。今、プログラムdo-loopを作っていますが、プログラムdo-loop内でdo-loopを呼び出しています。つまり、自分の中で自分を呼び出していて、こう言うのを再帰的定義と呼ぶんです。
つまり、(do-loop a b)と言う形でプログラムを呼び出すと、rが0でない限り、中で(do-loop b r)が呼び出される。そして(do-loop b r)の中ではまた別のrが定義されて、それが0で無い限り・・・・とどっかで剰余計算の解が0にならない限り、延々とそう言う引数の書き換えだけが生じてdo-loopが呼び出され続けるんです。
これがBASICのソースで言うと、170行目と180行目のコードの意味です。

170          LET a=b
180          LET b=r

Schemeのように明示的な再帰呼び出しを示してはいませんが、この2行の命令の意味は、Schemeで言うトコの引数書き換えで、その状態のまま150行目に作業が戻ってるんです。従って、Do〜Loopの部分がまた計算されてrが0じゃなかったらまた引数が書き換えられて・・・・・・と、原理的にはSchemeの明示的な再帰呼び出しとまったく同じ作業を展開してるんです。
これが設問のDo〜LOOP構文(140〜190)の意味です。
なお、どうして返り値をbにしたのか、と言うと、元々のBASICのプログラムの200行目にその答えがあります。

200       IF b=1 THEN

先ほど、「プログラム言語は上から下に向かって実行される」と言いました。従って、Do〜LOOP構文の下に来て、なおかつDo〜LOOP構文に関わりのある引数が指定されている場所と言うのはここしかありません。aもrも他にはどこにも見当たらないのです。
と言うことは、一番欲しい数はbである、と言う事です。従って、計算結果としての返り値はbを指定しておけばいい、と言う事になります。

さて、ではついでに200行から240行までもSchemeでカプセル化してみましょう。ここではプログラム名をそのまま200-240とします。
プログラム200-240はちょっとしたBASICの欠点と、同じくSchemeの欠点を垣間見る事が出来るでしょう。お互いの長所、短所を比較するには面白いブロックだと思います。
ただし、プログラムとしてはそんなに難しくありません。基本の範疇だと思います。よって、ソースをチャチャッと書き下してみましょう。

基本的にはBASICでもお馴染みの単なるif-then構文ですね。
プログラム200-240は4つの引数x、y、a、bを持ちます。先ほどbだけが必要だ、と言ったのにaも引数として設定しているのはプログラム200-240内でdo-loopを呼び出す為です。do-loopはa、bの二つの引数が必要でした。
さて、Schemeの欠点その1。局所変数でzを書いていますが、まずその式が分かりづらいですね(苦笑)。これは演算子を最初に必ず置くと言う約束事、すなわち前置記法を採用しているSchemeの欠点です。もちろん前置記法には利点も多いんですが、その代わり、

$z=\sqrt{x^2+y^2}$

なんて書かなきゃならない場合はちょっと大変です。少し考え込んじゃいますね(笑)。
まあ、丁寧に書いていけば決して中置記法(普通の数式の書き方)を前置記法に直すのは決して難しくないんですが、ちょっとした慣れが必要です。
なお、Schemeでは、sqrtと言う命令がBASICのSQRにあたり、また、(expt s t)と言う命令で $s^t$ を計算させます。
次はBASICの欠点です。BASICのソースコードでは

200       IF b=1 THEN
210          LET z=SQR(x^2+y^2)
220          IF INT(z)=z THEN PRINT x,y,z
230       END IF

となっていて、実は条件自体は

bが1でかつzが整数の時

と2つの条件を同時に考慮している筈なんですが、途中で局所変数によるzの定義が挿入されてたりしてあまりスマートではありません。最初にzを定義して、まとめて条件を記述してIF〜THEN構文に持ち込んだ方が感覚的にはキレイな筈なんですが、少々ゴチャゴチャしています。何故なんでしょう?
調べてみたら、BASICでは複数行にわたってしか書けないものを実行させたい場合、GOTO命令を使い行を飛ばす必要があるらしく、要するに一行で複数の条件を記述出来ないようです。従って、少々不格好なソースとならざるを得ません。一行には一つの条件、と言うキツい制約があるらしい。
その点、Schemeの方がソースとしては明解です。

(integer? z)) ;整数を確かめる

とif節の中にandを使って上手く2つの条件節を纏めています。
なお、一つ目の条件節で先ほど作ったdo-loopを呼び出しています。BASICのオリジナルのソースでは、単にbを使って判定していましたが、Schemeヴァージョンでは関数丸ごと呼び出すようにしています。
と言うのも、bだけ記入しても何が何だか分かりませんし、明示的に返却されたbが必要だから、と言う理由に依ります。この条件内で先ほど書いた再帰定義プログラムdo-loopが実行されて、返り値が1かどうかここで判定されているわけです。プログラム同士が有機的に結合しているんですね。
もう一つがinteger?と言う命令で局所変数で定義されたzが整数かどうか判定しています。ここがBASICのオリジナルのソースでは220行目でのINT(z)=zと言う場所の部分なんですが、若干意味が違います。
元々BASICのINTと言う命令は、zを整数化せよ、と言う命令だそうです。すなわち、小数を四捨五入する命令なのでしょう。zを整数化したモノとzが同じだったら元々zは整数であり、数値が食い違えばzは整数ではない、と言う事です。この辺りはBASICでは結構まだるっこしい判定法を用いているようです。Schemeのinteger?に比べるとかなり回りくどい判定法ですね。
なお、Schemeではこのテの「判定用命令」は大体最後に「?」がくっついています。
Schemeの欠点その2。BASICのPRINTにあたるSchemeの命令がdisplayなんですが、原則displayは一つ、ないしは二つの引数しか表示出来ません。BASICの場合は一回PRINT命令を送れば複数の文字を出力できますが、displayの場合複数の文字を表示させるとなるとそれなりの行数の命令を書かないとなりません。従って、BASICでは

PRINT x, y, z

と一行で済むところをSchemeでは

(display x) ;xを出力
(display " ") ;スペースを出力
(display y) ;yを出力
(display" ") ;スペースを出力
(display z) ;zを出力
(newline) ;改行命令

と羅列しまくらないといけません。
一般にSchemeの入出力系列の命令は結構貧弱なんですね。と言うのも、教育用言語と言うことで必要最小限の入出力命令しか持ってないから、なんです。これがSchemeの欠点のうちの一つだと思います。
なお、beginと言う命令は、中に入っている命令を「順番に」実行せよ、と言う意味です。ここでx〜zまでの出力と改行までの命令を順次実行させています。そして大事なのは「次のyが何なのか」ここで決定しないといけないと言うことです。
もう一度プログラム200-240の擬似コードを見てみましょう。

プログラム200-240を定義する

引数x、y、a、bを設定する

局所変数 $z=\sqrt{x^2+y^2}$ を定義する

プログラムdo-loopの結果が1で、かつzが整数だった場合、x、スペース、y、スペース、z、改行の順で出力してプログラムnext-yを引数を一つ増やして呼び出す

そうじゃなくてもプログラムnext-yを引数を一つ増やして呼び出す

となっています。
ここでポイントとなってるのは、BASICのオリジナルのプログラムで見れば240行目のNEXT yにあたる部分で、ここでyの数を一個増やしてアタマの110行に戻っているんです。従って、ここでScheme版でも新しくnext-yと言う名前のプログラムを作成して呼び出す事、とします。また、条件節の結果が真であろうと偽であろうと、next-y自体は呼び出されなければならない、と言う事です(じゃないとプログラム全体が止まってしまいます)。
では次にプログラムnext-yを作ってみましょう。BASICオリジナルのソースの110行〜130行、そして240行目にあたります。
設計にあたって気をつけることは、

プログラムnext-yはx、yの二つの引数を持つ

yの値が100を越えたら引数xを一つ増やして、また引数yを一つ増やしたxの値をもって初期化する

局所変数aをxとし、また局所変数bをyとする

プログラム200-240を呼び出す

と言う流れです。
ポイントとしては、プログラムnext-yからはプログラムdo-loopは呼び出さないで、敢えてプログラム200-240を直接呼び出している、と言う事です。と言うのも、プログラム200-240内でdo-loopを呼び出すようにしているので、それ以上呼び出す必要がないから、です。
また、問題設定から言うと、yが100に達したとき、xの数を1増やして、またその値をyの初期値としてセットしなおしています。この作業をプログラムnext-xを新しく作って呼び出す形にしています。
この2つのポイントを押えてプログラムnext-yを書くと以下のようになります。

また新しいプログラムnext-xが出てきたので、これを作ります。これはオリジナルのBASICのソースの100行と250行にあたります。もうここまで来れば、xが一つづつ増えて行った末の終了条件さえハッキリ分かっていれば構いません。

(next-y x y)))) ;プログラムnext-yを呼び出す

andと言う命令は内側に含まれる命令が偽であった時、偽を返して終了します。従って、これによりxが100以下の時に限ってnext-yを呼び出し続けるのです。
最後にxとyに初期値を与えましょう。初期値は両者とも1でしたね。これをプログラムQ3628として定義します。

(next-x 1 1))) ;プログラムnext-xの引数を1、1として呼び出す

これでプログラムQ3628を呼び出した時点でプログラムnext-xが引数を1、1として呼び出され、それがまた別のプログラムを呼び出して・・・・・とまるでドミノ倒しのように全てが一つのプログラムとして動きます。
もう一回全部のソースコードを見ておきましょう。

(next-x 1 1)))

(next-y x y))))

そして全体的には次のような流れになっています。


Q3628→呼び出し→next-x→呼び出し→next-y→呼び出し→200-240→呼び出し→do-loop
　　　　　　　　　　　↑         ↓    ↑          ↓
　　　　　　　　　　　←←呼び出し←←     ←←呼び出し←←

このようにBASICのインデントに着目すれば、行頭が同じ位置にあるソースコード群をまとめてカプセル化する事が出来ます。また、プログラム実行の流れは「上から下へ」と言うのは事実なんですが、カプセル化するにあたっては特に時系列で書き連ねなければならない、って事はありません。気になった部分、好きな部分、ないしは簡単そうな部分からプログラムを書き始めて行って、最終的に整合性さえ取れていればいいのです。これが「現代的な」プログラムの書き方だそうです。「出来る部分から書く」のがワリに今では当たり前になってるんですね。
さて、ではSchemeでのソースの実行結果を見てみましょうか。

はい。全く同じ計算結果が表示されていますね。簡単でした。
取りあえず、今回のDo〜Loop構文のポイントは再帰構造です。そこだけ押えておけば取りあえずは難しくないでしょう。
また、このように「全く違う発想の」言語へ翻訳してみることによって、色々なプログラムの発想が得れるでしょう。勉強方法としてはメンド臭いように見えますが、意外とこの方が効率的に勉強できる、と言う事を付け加えておきます。

以上です。

さて、ここから余談です。
上の本編の方では再帰構造にこだわって解説しました。何故ならDo〜Loop構文が行ってる意味が分からない、と言う事だからです。
このテの問題の解説が難しいのは、数学的に意味が分からないのか、それともプログラムの部分で意味が分からないのか見えづらい、って事があるんです。どっちつかずなんですね。
それでDo〜Loop構文に絞って解説したんですが、一方、どうして剰余計算MOD(Schemeではmodulo)が出てくるのか意味が分からない、ってのも事実です。そこでまずはそれを解説したいと思います。
次に、BASICのソースコードをSchemeに翻訳してみせる事により、「プログラムとしては何をやってるのか?」明示する戦略を取ったんですが、しかし出来上がったSchemeのコードはあまりキレイではありません。
本編の方で

「開発効率の良さで関数型言語が注目を集めている」

と書きましたが、これじゃあんまり開発効率が良い、とは言えませんよね。
通常、開発効率の良さ、と言うのは

コードの読みやすさ

コードの量

で計られます。
読みやすさに関しては「慣れ」の問題が大きいのですが、「コードの量」ってのは別の指標を与えてくれます。同じ動作をするにあたって、書く量が増えるのは人間にとってたまったもんじゃありません。
どうしてC言語は動作は速いのに開発効率が悪いのか、と言う一つの理由がここにあります。何故なら「同じ事をやらせるのに」書く量が半端無く多いのです。ライブラリの呼び出しから始まって使われる変数の型の定義、その他諸々・・・・・・。コンピュータにとっては問題無い効率的な処理ですが（と言うよりC言語はコンピュータだけにとって効率的な命令になるように設計されている）「指令を出す」人間に取って大変なのです。人間にとって「効率的」じゃないんです（難しいのはコンピュータにとって効率的な事が人間にとっても効率的とは限らない辺りです！！！）。
何故今回Schemeで書いたコードが長くて開発効率が悪いように見えるのか?その理由は単純に一つです。それはBASICで書いたソースの構造をそのまま流用して書いたコードだからです。要するに、単純な手続き型言語の構造をそのまま関数型言語に当てはめてしまった。それがやたら冗長なコードになってしまった理由です。つまり、冗長なのはSchemeのせい、と言うより元々のBASICのソースが冗長なんです。
あくまで亀田個人の意見ですが、オリジナルのBASICのソースのように、内側にxのループがあり、その中にyのループがあり、そしてDo〜Loopの構文がある、なんてのは汚くて嫌です。これしかBASICでは書きようが無いのかもしれませんが、Schemeなら原則そんな書き方はしません。どうせやるんだったら、一回のループ構文で全てを表現した方がカッコいいのではないか、と思います。再帰構造を用いるならそっちの方が本来スマートな筈です。
この2点に絞って「余談」として、もっと効率的なSchemeのソースを提供してみたいと思います。

まずは最初のDo〜Loop構文の「数学的な意味」を考えてみましょう。と言うより、実は「数学的」って程のネタじゃないんですね。
多分、元々問題の発想としては、

$1\le x\le 100$ 、 $1\le y\le 100$ の範囲で $x^2+y^2=z^2$ が成り立つ整数x、y、zを求めよ

だと思っているでしょう?いわゆる3平方の定理ですよね。
それは基本的には間違っていないんです。しかしながら、上のような問題だと、わざわざDo〜Loop構文を使ってBASICのソースの内側に「何かを」忍ばせる必要が無いんです。
論より証拠。何故あそこでDo〜Loop構文が必要になるのか?次の表を見てみれば一発で分かると思います。これらが $1\le x \le 100$ 、 $1\le y \le 100$ の範囲で $x^2+y^2=z^2$ が成り立つ整数の組です。

はい。実は上の表のようになるんですね。単純に $0\le x\le 100$ 、 $0\le y\le 100$ で $x^2+y^2=z^2$ が成り立つ整数x、y、zの組み合わせを数えると‥・・・・実は59組も存在するんです。ちょっと見てみてください。
確かにBASICのソースを実行した時に示されている組も入っていますが、多すぎますね。何が違いかお分かりでしょうか?
そうですね、実は互いに素であるx、yの組み合わせ、って言う条件が付加されていないといけないんです。
例えば、 $3^2+4^2=5^2$ ってのは成り立っています。同様に $6^2+8^2=10^2$ ってのは成り立っています。しかしながら問題のBASICプログラムは3、4、5の組を計算ではじき出してくれますが、一方6、8、10の組は無視です。何故なら $(2\times 3)^2+(2\times 4)^2=(2\times 5)^2$ だからですよね。全部を4で割れば結果 $3^2+4^2=5^2$ と変わりありません。つまり、6、8、10の組合わせは互いに素ではないのです。
互いが素である為には何が必要か?x、yの最大公約数が1である、ってのが条件となりますね。だから、返り値b＝1の時、と言う判定条件が付いたのです。
もうお分かりですか?実は問題のDo〜Loop構文は、平たく言うと、xとyの最大公約数を調べるプログラムなんです。 →参考：ユークリッドの互除法
一方、Schemeでは実は最大公約数を計算する命令、gcd(Greatest Common Diviser＝最大公約数の事)があります。これを上手く使ってプログラムQ3628を書き直してみたいと思います。
もう一つ、これは亀田の好みかもしれませんが、xを1から変化させていって100に到達させて、またyをxの値から変化させていって100に到達させる、と言う構造は好きくないです。僕だったら100から逆に辿っていきます。何故なら、一々yの値を設定しなおすのが面倒臭いから、ですよね。
条件としてはxが100から0に向かって変わっていき、0で全体の計算が終了する。また、yも100からxの値に向かって行ってx＝yになったときまた100に戻る、って考えた方が分かりやすいと思います。一々xの値が何なのか、チェックしてそれによってyの初期値が決まる、ってのはバカバカしいでしょう?後者だったらどの道100からスタートすれば良いのが自明です。
以上を考慮して、プログラムQ3628-newを作りますが、まずは大まかな再帰プログラムエンジン、Q3628-engineを記述します。ここでバラバラだったx、yの変化、そしてDo〜Loop構文を完全に一つの大きな再帰構造の中で記述する事になります。

(= (gcd x y) 1))

これが完全に一つの再帰構造で書かれたQ3628-engineです。
まずはポイントとしては今回は引数をx、y、lsの三つにしました。x、y、は問題のBASICソースにある通りですが、ここでは新しくリスト用の引数lsと言うのを設定しています。これは、条件にしたがったx、y、zの計算結果を次々と突っ込む為のスペースです。
全体の流れとしては次のようになっています。

プログラムQ3628-engineを定義する

x、y、lsの3つを引数として設定する

xが0の時、プログラムprint-engineを呼び出し、引数lsを渡す

それ以外の場合は局所変数zを計算し、Q3628-engineを呼び出す

たったこれだけ、です。非常にシンプルな構造になっています。
問題は再帰的に呼び出された4番のプロセスです。ここで呼び出されたQ3628-engineの引数を工夫してるんですね。
プログラムQ3628-engineは3つの引数を持っていました。この3つの引数が繰り返し計算中に書き換わっていくのですが、そこにif節を突っ込む事により繰り返し計算を効率的に表現しているんです(こう言う事ができるのが、手続き型言語と違った関数型言語の柔軟な所です)。
すなわち、再帰的に呼び出されたQ3628-engineのそれぞれの引数は、

x:もしx＝yなら、xを1減らす。そうじゃなければxのまま。

y:もしx＝yなら、yは100に戻る。そうじゃなければyを1減らす。

ls:もし、zが整数で、かつ、xとyの最大公約数が1だったら、x、y、zのリストを作って、それを引数lsの先頭に突っ込む。そうじゃなければlsのまま。

註:consと言う命令はリストの最初に何かを突っ込む命令。また、listは任意の数のリストを生成する命令。両者とも質問＜3609＞参照。これらはSchemeの基本的な命令である。なお、リストとはBASICで言うと一種の配列にあたる。

と言うif構文によって制御されているのです。明解でしょ?かつオリジナルのBASICの制御構造を完璧に表している事が分かると思います。一々ループ構造に悩まないでスッキリ書けるのがSchemeの強みなのです。
なお、print-engineと言うプログラムはまだ書いていません。これは本編を読んでたら何となくどう言うプログラムになりそうかは想像が付くでしょう。その通りです(笑)。
取りあえずprint-engineも記述してみましょうか。

これも原則、質問＜3609＞に出てきたプログラムwrite-lsと同じものです。やっぱり再帰構造で書かれていますね。ある程度のリストをdisplayした後にリストの残り(cdr ls)にprint-engineを適用しています。
特に難しくない筈なんですが、新しく出てきたのは、まずfirst、second、thirdと言う命令です。これはつまり、リストの最初の部分、2番目の部分、3番目の部分、と言うのを表しています。意味的には簡単でしょう。
ところで、どうしてそうしてるのか、と言うと、プログラムQ3628-engineの返り値であるlsは、基本的には結局、次のようなリストを出力するから、です。

((3 4 5) (5 12 13) (7 24 25)・・・・・・)

つまり「リストのリスト」ですね。これをバラけさせてdisplayに渡さないといけない。
従って、例えば最初の出力3、4、5を得るためには、lsの最初のリストである(3 4 5)を取って、その中のfirst、second、thirdを出力した後改行、と言う命令にしないといけないのです。これがカラクリです。
ここで勘のイイ人は気づいたかもしれませんが、実はcarと言う命令と、firstと言う命令は全く同じモノです。また、リストの先頭を除去したリストを返す命令がcdrなので、実はsecondは(car (cdr リスト))と同じモノです。単に省略形ですね。
このように、どうして基本的なリスト操作命令であるcons、carやcdrがSchemeでは大事なのか、と言うと、この3つの命令を組み合わせるだけで色々なプログラム(命令)を簡単に書くことが可能だから、なんです。
まあいずれにせよ、プログラムprint-engineは質問＜3609＞のwrite-lsと原理的には全く同じコードなんで、そちらに詳しい説明を付けているのでそれを参照して下さい。
最後にプログラムQ3628-engineに引数の初期値を与えるプログラムQ3628-newを作って全て終了です。初期値はそれぞれ、xが100、yが100、そしてlsに空リストである()を与えて終わり、です。

(Q3628-engine 100 100 ())))

ご覧の通り、Q3628-newは特に引数は必要としません。Q3628-newを走らせれば、すぐに結果が返ってきます。
以下がQ3628-newを走らせた結果の画面写真です。

はい。全くオリジナルのBASICのソース実行と同じ結果が返ってきますね。そして、こちらの方がよりSchemeらしいコードの書き方です。
まあ、人によって感想は変わるかもしれませんが、BASICのDo〜Loop構文やFOR文の煩わしさよりよっぽどシンプル、かつ直感的にSchemeではコードを書くことが出来ます。これが「関数型言語」の強力なトコロですね。
また、BASICは初心者向けでとっつきが良い、と一般的には思われていますが、実は複雑な計算をさせようとすればするほど、扱いが極端に難しくなっていく言語だと思います。反面、Schemeは奥が深いのは確かですが、と同時にどんなに問題が複雑化してもあまり構文的には複雑にならない(と言うよりワンパターン)ので、むしろ初心者にとっては扱いが簡単な言語じゃないか、と思います。ハッキリ言ってBASICの方が難しいです。
まあ、こんな感じでSchemeのパワーを垣間見て下さい。また、BASICの問題をSchemeで書くことにより、かなり良質なプログラミングの練習（※）になると思います。

以上です。

※：これは必ずしもSchemeにとって良い練習、と言う意味ではなくってBASICにとって良い練習になるだろう、って意味です。もう一つの言語をBASICと同時に勉強して見比べた方が、逆にBASICへの理解が深まるでしょう。

追記:本編中でBasicの元ネタとなった世界で初めて作られた高級言語、Fortranに付いて書きましたが、そのFortranのオリジナルの作者、John Warner Backus 氏が2007年10月17日にお亡くなりになったようです。
ご冥福をお祈りいたします。

FORTRAN の父 John Warner Backus 氏死去

高校数学の窓LaTeX版

高校数学の窓過去問検索

質問＜３６２８＞２００７／１０／１９from=BOXY「DO〜LOOPのBASICプログラム」

0 コメント:

New

分類

ツール

数学ガール

たけしのコマ大数学科

ガスコン研究所

数学系ブログ記事