プログラムの難しさの階層

プログラムを理解するのは、まあ難しいです。
でも、その難しさには階層があります。


よく、変数は箱だとか箱じゃないとか議論になりますが、何人か初心者に教えた感じでは、変数自体でつまづくことはあまりないので、実際はそんな例えをしなくても「変数は変数だ」で充分だったりします。
デバッガでステップ実行しながら変数の内容を見ればいい。
で、条件分岐くらいは結構つまづくことはなくて、単純な演算と条件分岐だけが必要なプログラムであればまあそれなりに書けるようです。
ぼくも、一番最初に自分の意図で作ったプログラムは

input "ワカレミチガアル。ドウスル? 1:ミギ 2:ヒダリ"; a
if a = 1 then
  print "ガケニオチテシニマシタ"
else
  print "ライオンニカマレテシニマシタ"

みたいなものでした。こういった条件分岐をたくさん並べてアドベンチャーゲームっぽいものを作った人は、ぼくの世代には結構いる気がします。そしてそれ以上のプログラムを作ろうとしたところで挫折した人も・・・


つまづくのはループからで、これはCスタイルのループ構文が難しいというのもあるんですが、やはりループ自体が難しいようです。
プログラムで書いたことが何度も実行されるというのが難しい。
イベントスタイルでのUIプログラミングが少し難しさをやわらげてくれるのは、ループを隠蔽してくれるからではないかと思います。


ただ、ここまでは文法の話の範囲で進めれるのですけど、状態管理が入ってくると「プログラムが組める人」と「プログラムが組めない人」の差が明確になるくらい、理解のハードルが高くなるようです。たとえば[0]〜[9]までと[+][-][=]のボタンを置いて電卓を作るような問題。
状態管理には変数が使われますが、変数が難しいといわれるのは、変数そのものの機能ではなくて、状態管理が難しいのではないかとも思います。
実のところ、逐次実行でも「どこを実行しているか」という状態が必要になるのですが、そのような状態をプログラムカウンタとして隠蔽するのがCPUのひとつの役割だと思います。
また、Cスタイルでの

for(i = 1; i <= 10; ++i){
  ・・・
}

というループが

loop(i = 1..10){
  ・・・
}

のようなループに比べてむずかしいのは、Cスタイルでのループはiの状態遷移について考えないといけないからじゃないかと思います。結局、Cスタイルでのループも「この書き方で i = 1..10 のような、1から10まで繰り返すという意味になる」というイディオムだと捉えて、状態を追わなくなると理解しやすくなります。


そして、さらに難しいのがスタックです。処理としては入れ子構造の扱いです。
よく、再帰関数は理解が難しいといいますが、本質的にはスタックを使うループの理解が難しいのだと思います。
ただ一度スタックを理解できてしまうと、生のスタックとループで処理を書くよりも、再帰関数のほうが書きやすいことが多いです。これは、関数呼び出しがスタックを隠蔽して、スタック操作を明示的に行わなくてよくなるからだと思います。
そして、スタックさえ使えれば、可能なプログラムはすべて構造として記述できるようになります。あとはアルゴリズムやアプリケーションの問題。
なので、プログラムの構造の難しさとしてはここまで。
もちろん一般的なデータ構造である配列などが使えると、よりプログラムが組みやすくなります。

ハードウェアとの対応

このような難しさは、ハードウェアの構成にもあらわれます。
入力に対して条件によって演算をおこなって出力するだけであれば、論理素子の組み合わせ回路だけで構成できます。
プログラムカウンタが必要な逐次実行やループになると、クロックとレジスタが必要になってきます。
そして、スタックが必要になると、インデックスアクセス可能なレジスタ列やメモリが必要になります。

実際の例題

それでは、実際のプログラム課題として見てみます。実装が難しくなっていくことが実感できると思います。
実際に回答してもらうための問題ではないので、問題の記述の甘さなどにはご容赦を。

演算

入力に文字列を受け取って、「が入力されました」を付け加えて返す。

条件分岐

入力に文字「1」か「2」を受け取って、「1」なら「ガケに落ちました」、「2」なら「ライオンに食われました」を返す。

ループ

入力に一文字以上の文字列を受け取って、すべて「A」ならtrue、「A」以外の文字があればfalseを返す。

状態管理

入力に大文字アルファベットからなる一文字以上の文字列を受け取って、「A」が一文字以上続いたあとで、「A」以外の文字が続けばtrue、「A」で始まらなかったり、「A」が続くだけで終わったり、「A」以外の文字のあとで再び「A」が来た場合はfalseを返す。
AAAABBBCCBB → true
BAAAABBBCB → false 「A」以外の文字で始まっている)
AAAAAAA → false(「A」が続くだけで終わっている)
AAAABBBCCBA → false (「A」以外の文字のあとにふたたび「A」が来ている)
正規表現であらわせば、 A+[^A]+にあてはまればtrue。スタックを使わない判定であれば、正規表現的に判定できます。

スタック

「状態管理」でtrueが返ってくるものであればtrue。ただし「A」と「A」以外の文字の間に「(」〜「)」で囲んで、このルールを適用してtrueになる文字列をひとつはさむことができる。そうでないものはfalse。
AAAABBBCCBB → true
AAAA(AABBB)BBCC → true
AAA(AAA(AB)B)BCC → true(入れ子はOK)
AAABB(AAB)BB → false( 「A」以外の文字のあとに「(」がきている)
AAA(AAB)ABB → false( 「(」〜「)」のあとに「A」がきている)
AAA(AAB → false( 「(」〜「)」が閉じていない )
AAA)BB → false( 「(」がなく「)」が来ている )
AAA(AAB) → false( 「(」〜「)」のあとに「A」以外の文字がない)
AA(AB)(AB)BB →false( 「(」〜「)」が2回続いている )


一般には、ツリー構造の処理になります。

計算モデル

こういった計算モデルは、一度は勉強しておいたほうがいいと思います。
今回の話は、次の本の1章の例を、プログラムの理解の話につなげたものです。