Entries

スポンサーサイト
[EDIT]
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
論理プログラミング
[EDIT]
OCamlの記事の途中ですが、溜めに溜めたデータをすべて吹っ飛ばしてしまったので、気力が帰ってくるまでほかの記事を、ということで論理プログラミングについて書きながら待つことにします(^^;
最近記事も重くなってきてますし、ちょっと気分転換というか(笑)
論理プログラミングに関する知識はほとんどないので、間違いなどあったら指摘していただければと思います。

論理プログラミングは数理論理学をプログラミングに取り入れ、さらに人工知能と密接に関わっているため、関数型言語以上に異質な存在に映るでしょう。
ある仮説・問題(=命題)について、すでに証明された問題(=定理・前提)で証明できるかをプログラミングで行うということが論理プログラミングの背景にあります。

例えば、コンピュータによって証明された有名な問題として、
ある図形について「隣り合った図形同士は同じ色にならない」という条件の下、できる限り少ない色数で図形を塗り分けるには「4色あれば十分」
という「4色問題」があります。これは過去の経験則から導き出された「5色で塗り分けられる」という前提が活用されました。

論理プログラミングは命題と定理の関係を記述するのに利用されます。例えば「AとはBとCである」とか、「CはDかEの何れかである」といったことを記述するわけですね。
この二つの前提から、「AはDかEの何れかである。これはAがCと等しいからである」ということが導き出せます。命題を証明したり、新しい解を導き出したりするのは自動です。
もうちょっと具体的な例を、論理プログラミング言語の代表格であるPrologのソースコードとともに挙げてみます。

まずは先ほどの例をプログラミングしてみましょう。%のうしろはコメントになります。
%AとはBとCである
a :- b, c.
%CはDかEの何れかである
c :- d.
c :- e.
:- の左辺を頭部(命題)、右辺を本体(すでに証明された命題)と呼びます。
実際のところは関数型言語のように、それぞれの項に付随する情報を書き加えることが多いです。
cat(tama). %tamaはcatである
cat(tom). %tomもcatである
pet(X) :- cat(X) %catはpetである。Xは変数である
ここでPrologに対して、タマはペットかどうか質問してみます。
?- pet(tama).
Yes
Prologがpetはcatであり、catがtamaと結びつけられているかどうかを判断してYesと答えます。つまり逆説的に答えを導き出したことになります。論理プログラミングは「本体がすべて真であれば頭部は真である」という解釈をするため、この辿りかたが普通になります。
今度はペットに誰がいるかを答えさせてみます。
?- pet(X).
X=tama
pet(X)を満たすcat(X)を導き出し、さらにcat(X)を満たす項を見つけてタマを変数Xに代入しました。
一般的なプログラミング言語ではここで終わってしまうでしょう。でもトムもこの条件を満たします。この問題に対応できるよう、論理プログラミングは複数の答えを導き出すことができます。
X=tamaで止まっているところでセミコロンを入力すると、次の答えを導き出します。
X=tama;
X=tom
ほかの答を求める機能を「バックトラック」、複数の答を持ちえることを「非決定性」といいます。

バックトラックについては「やりなおし」という意味合いがあって、先ほどの例では
pet(X)はcat(X)であり、cat(X)を満たすのは最初に見つかるcat(tama)である
でバックトラックを行うとcat(tama)を答えから取り除いて、もういちどcat(X)を満たす項を探してcat(tom)に辿り着いた、という形になります。
Prologは木という表現でデータを保持し、答えを探しています。数学にある木と同じと考えても差し支えありません。
→ pet(X)
 |
cat(X)
/ \
cat(tama) cat(tom)
pet(X)という入力があると、pet(X) = cat(X)であることから矢印が左に移動します。
pet(X)
 |
 → cat(X)
/ \
cat(tama) cat(tom)
さらにcat(X) = cat(tama) or cat(tom)であり、木の辿り方は左に近い方からというルールから、さらに左に移動し、末端であることから答えとして出力します。
pet(X)
 |
  cat(X)
/ \
→ cat(tama) cat(tom)
ここでバックトラックを行うと選択肢からcat(tama)を取り除いて、矢印は一旦上に戻ります。
pet(X)
 |
 → cat(X)
/ \
  cat(tom)
再びcat(X)を満たすものを探し、cat(tom)に辿り着きます。
pet(X)
 |
  cat(X)
/ \
   → cat(tom)
この状態でさらにバックトラックを行うと答えがなくなります。答がなくなってもエラーとしてプログラムを止めることはなく、答が見つからないと表示してユーザの入力を待ちます。

論理プログラミングにおけるもうひとつの重要な機能がユニフィケーションと呼ばれるものです。ユニフィケーションは先ほどの木構造の探索や入力とソースコードの比較、変数への代入など、論理プログラミングを成り立たせるほとんどの処理を行います。ユニフィケーションは次のようなルールの下で処理を行っていきます。
1. 入力された項と定義された項において、項の片方が変数でもう一方が変数でない場合、変数はもう一方の項と同一と見なす(変数への代入)
2. 同様にそれぞれの項において項の両方が変数ならば、両方の変数は同一と見なす
3. それぞれの項がアトム(変数でないもの)の場合、それぞれが完全に一致した場合に成功する
4. それぞれの項が複合項(f(A)という形式)で、引数(括弧の中。アリティという)が同じ形式である場合、すべての要素で1~4のユニフィケーションが成功する場合に成功する

member(X, [X|_]). % Xがリストの先頭要素と同じ場合
member(X, [_|Y]) :- member(X, Y) % それ以外の場合
この定義に対して次のように質問してみます。
?- member(Z, [tama,tom]).
Z=tama
変数Zにtamaが代入されました。

まずひとつめの定義member(X, [X|_])において、入力member(Z, [tama, tom])との関係は
・ZはXと同じものである………ユニフィケーション2
・Xと[tama, tom]についてはXを[tama, tom]とみなす………ユニフィケーション1
・入力と定義は複合項でアリティは互いに変数とリストである………ユニフィケーション4
 - 変数Zと変数Xは同一………ユニフィケーション1
 - リスト[X|_]とリスト[tama, tom]は互いにリストというアトムである………ユニフィケーション3
 - リスト[X|_]とリスト[tama, tom]はX=tama, _=tom………ユニフィケーション2
・アリティの全要素が満されるから複合項もtrueである………ユニフィケーション4が成功
・変数 _ は捨てて、これまでのユニフィケーションの結果からZ=tamaである
という結論に至り出力します。この状態でバックトラックを行うと
・member([X|_])の項から探査木を一段戻る
・ユニフィケーションが成功する次の頭部を探す
 - member(X, [_|Y])とmember(Z, [tama, tom])でユニフィケーションに成功
 - [_|Y]と[tama, tom]は_=tama, Y=tomで、変数 _ は捨てる………ユニフィケーション1
 - 本体がmember(X, Y)であり、_ が捨てられたmember(Z, [tom])とユニフィケーションに成功
・この結果を引き継いでmember(X, [X|_])とmember(Z, [tom])をユニフィケーション
・X=Zで、[X|_]と[tom]はX=tom, _=nil………ユニフィケーション1
・_ を捨ててX=tom、X=ZよりZ=tomである

論理プログラミングに込み入った条件に見合った答えを導き出す機能を付け加えたのが制約論理プログラミングで、制約プログラミングの始祖です。
論理プログラミングの根本的な制約は「ユニフィケーションできるか」だけで、それ以外の制約を付け加えるために制約プログラミングが考案されたということができます。
スポンサーサイト
OCaml
[EDIT]
最近になってちらほら耳にする機会が増えてきた関数型言語についてもう少し触れてみようと思います。
今回はLISPではなく、Objective Caml(OCamlと略)というプログラミング言語を使います。
OCamlはML(Meta Language)と呼ばれる関数型言語から派生した方言Camlがオブジェクト指向を持つようになったもので、関数型言語の中では比較的シンプルで処理速度にも秀で、日本語の文献もそれなりに整っているという理由から選択しました。
ちなみに元のCamlはCaml-lightとして開発が続けられています。
また、教育用としてMinCamlと呼ばれるOCamlのサブセットが日本人の手によって開発されています。すべてOCamlで書かれていて、コンパイラの学習にも適しています。そしてとくに注目すべきなのは、Microsoftの.NETフレームワーク用のプログラミング言語のひとつとして、OCamlをベースにしたF#という言語が用意されています。つまり、今後OCamlが爆発的に普及する可能性を秘めているということができるでしょう。

まずは難しいことを考えずにちょこっとコードを書いて試してみましょう。関数型言語は難しい用語が出てくるからわけがわからなくなるのです。
xtermなりターミナル.appなりを起動してocamlコマンドを実行します。
Objective Caml version 3.12.0

#

こんな感じに表示されればOKです。うまくいかないときはインストールしなおしてみましょう。
終了させるときは#quit;;と入力してreturnです。quit;;だけではエラーになるので要注意。
ちなみにこの対話環境をトップレベルと呼びます。BASICのようにコードを入力すればその場で実行結果などを表示してくれます。関数型言語の大多数はトップレベルを持っていて、小さなコードを打ち込んでテストを繰り返しつつテキストファイルで全体を組み立てていき、最終的にコンパイラに通してアプリケーションを作り上げます。

それでは例によって階乗を求めるプログラムからはじめます。
let rec fac n =
if n <= 1 then 1 else n * fac (n - 1);;

let recは名前定義のためのキーワード、関数名の指定、引数の定義、=を挟んで次の行に関数本体を記述して、2つのセミコロンで終わっています。トップレベル環境(Perlのように対話的にプログラムをテストする環境)ではダブルセミコロンで式の終端と見なすようになっていて、これによってトップレベル環境での改行を可能にしています。ファイルにソースコードを記述するときは無くても問題ないです。

ifはこれまでさんざん使ってきたので説明するまでもないでしょう...といいたいところですが、気をつけなければならない点をいくつか。
then ... else ... はthenが整数ならelseも整数、thenが小数ならelseも小数というように、値の種類(型)を統一しなければなりません。
もうひとつ、ifはthenもしくはelseを実行して最後に得られた値がif全体の値になります(C言語で言えば?:の三項演算子と同じです)。大ざっぱに言えば、returnを使わなくても、最後に計算した結果を関数の戻り値として返してくれるということです。そのためreturnそのものが存在しません。
ML系の言語で一番厄介なのは、elseを省略したい場合です。関数型言語においてifは途中のプログラムをスキップするというより、条件によって値を選択するという意味合いの方が強くなっています。MLではelseを省略した場合、elseがユニットという値を返す式であると決められています(ユニットはほかの言語でいうnilやnullという値に近いものです)。
ほかの関数型言語ではそれだけで「はいおしまい」と相成りますが、MLではそういうわけにはいきません。MLでの式は常に決まった型の値を返す必要があります。ということで、thenでもユニットを返すようにする必要があります。ユニットは空の括弧()として表されます。

さて、このままでは関数を定義したに過ぎません。実際に関数を使うには引数を与えて呼び出す必要があります。今回の例で4の階乗を求めるときは
fac 4;;
とします。変数に格納したいのであれば、例えば
let answer = fac 4;;
とします。letで変数名を決めて、関数の結果をそのまま変数に格納しています。この辺はBASICにも通じるところがありますね。ただしOCamlではletを省略できないので注意してください。変数名も最初の1文字は小文字かアンダースコア_という制限があります。ということは、OCamlは大文字と小文字を区別するということですね。

四則演算もほかの言語と大差はありません。
let i = (1 + 2) * (3 + 4);;
計算通り21と表示されます。

小数ももちろん使えます。円の面積を求めてみましょう。円の面積はπr2でした。OCamlは円周率が定義されていないので、自分で定義してあげる必要があります。
let pi = 3.14159
let circle r = pi * r * r
circle 2;;

This expression has type float but an expression was expected of type int
最後の最後でエラーが出てしまいました。「この式はfloat型だけどint型を使ってます」というエラーです。
そのほかにも気になる点があると思います。勘のいい人なら2行目は関数定義であることに気付くでしょう。実際、3行目のcircle 2;;がいかにも関数呼び出しであるといわんばかりです。そうすると、let recじゃないと関数にならないんじゃないか?という疑問が出てきます。recとはrecursionの略で、再帰という意味です。ちょうどfac関数は再帰を利用して階乗を求めていました。OCamlの関数定義は、再帰関数でなければrecは不要になります。

ではOCamlは何に対してエラーといっているのか。問題のある部分に下線を引いてくれることを思い出してください。piに下線が引かれています。それからfloatは小数、intは整数です。つまり小数を使うべきところで整数を使ってしまったことが問題となっています。circle 2.0とすれば直るかというと残念ながら直りません。
表示関数で整数用と文字列用とを使い分けたように、演算子も整数用と小数用で使い分けてあげる必要があります。乗算演算子 * は両辺が整数であるときに正しく機能します。片方か両方かを問わず、違う種類の値がくるとエラーになってしまいます。小数同士の乗算は *. 演算子を使います。右下はゴミではなくピリオドです。つまり
let pi = 3.141592
let circle r = pi *. r *. r
circle 2.0;;

とすることで直せます。circle 2;;ではなくcircle 2.0;;であることにも注意してください。勝手に小数に変換してくれないので、引数として与える半径も小数である必要があります。
piを手入力でなく計算式からの近似値を求めたい場合、6.0 *. asin 0.5(逆正弦の1/2の展開)や4.0 *. atan 1.0(逆正接の1の展開)などとするとよいでしょう。また小数に限って冪乗演算子(**)が定義されているので、
let pi = 6.0 *. asin 0.5
let circle r = pi *. r ** 2.0
circle 2.0;;

とするとよりスマートです。
小数には専用の演算子があるということは乗算に限らず四則演算すべてにいえます。
この辺がOCamlの厄介なところですが、慣れるしかありません。型についてものすごく厳格である分、でき上がったプログラムはプログラマー本人でさえ意図していなかったミスも非常に小さくなります。
例えば、Javaでは
System.out.println("2+3= " + 2 + 3);
というコードを書いたとき、プログラマーは"2+3= 5"と表示されるものだと思ってしまうでしょう。しかし、+演算子は左辺の優先順位が高いので、まず"2+3= " + 2を実行して"2+3= 2"という文字列を作ってしまいます。すると残りも自明ですね。これを回避するためには2 + 3を括弧で括って先に足し算を実行させる必要があります。
OCamlでは
print_string ("2+3= " + 2 + 3);;
とすること自体不可能です。整数の表示にはprint_intがあるので
print_string "2+3= "
print_int 2 + 3;;

で...解決しません。関数の引数はスペースで区切って複数列挙します。が、print_intが受け付ける引数はひとつです。print_int関数と引数2があって、ほかに+ 3という余分な引数があると勘違いしてしまうので
print_string "2+3= "
print_int (2 + 3);;

のように括弧で括ってあげます。最後に改行がほしいときはprint_newline ();;を付け足せばOKです。
なんとも面倒くさい言語ですが、とにかく慣れです。

さて、ここまで簡単なサンプルを見てきましたが、あまりにもありふれたコードで、わざわざ関数型言語を学ぶメリットを見出すことはまず無理でしょう。それもそのはず、取っつきやすいように関数型言語らしい部分を隠して説明してきたのですから。
それではより深く掘り下げてみましょう。

関数型言語は、関数さえも変数に割り当てたひとつの値であるかのように扱うことが可能です。たとえばこんな関数を考えてみます。
let calc f x y = f x y;;
これだけでは当然役に立ちませんが、引数fに関数を割り当てることができて、引数xとyが適用された関数fが評価されたら、かなり汎用的な関数になりそうです。高階関数はそれを可能にします。適当にこんな関数を作ってみましょう。
let add x y = x + y
let multi x y = x * y
let div x y = x / y
let sub x y = x - y;;

今定義した関数を引数にして、先ほどのcalcを使って呼び出してみます。まず足し算から。
calc add 1 2;;
これで引数fにaddが、xに1、yに2が渡され、さらにaddが呼び出されて1 + 2を計算します。結局、calcの結果として3が返ってきます。
ではmultiを渡してみましょう。
calc multi 1 2;;
1 * 2が実行されて2が返ってきます。ほかの関数についても試してみてください。
このくらいではいまひとつ魅力が伝わらないでしょうか。たしかにこのような関数はC言語でも可能ですが、ポインタを使う必要があり、潜在的なバグを作り込んでしまう可能性があります。関数型言語はポインタを使うことなく高階関数を書くことができます。

面倒くさい制限がたくさんありますが、関数型言語といってもそこらにある言語と大差ない、むしろかなりシンプルにコードを書けることがわかっていただけたかと思います。
※この面倒くささはMLという言語特有のもので、関数型言語そのものの特徴ではないことにも注意してください

おまけ
wikipediaのアルゴリズムを用いた累乗関数
1. 指数を n とし、2乗していく値 p := a 、結果値 v := 1 とする。
2. n が 0 なら、v を出力して終了する。
3. n の最下位桁が 1 なら、v := v * p とする。
4. n := [n/2] とし(端数切り捨て)、 p := p * p として、2. に戻る。
アルゴリズムの疑似コード
fun pow n, p, v
2: if n = 0 then return v
3: if (n bitAnd 1) = 1 then v := v * p
4: pow (n / 2), (p * p), v
end
1: i = pow n, a, 1

実装結果(整数専用)
let rec pow p n v =
match n with
0 -> v
| y -> let new_v =
if (y land 1) = 1 then v * p else v in
pow (p * p) (y / 2) new_v
let pow x y = pow x y 1


次回はさらに深く掘り下げていく予定です。
関数型言語
[EDIT]
それはFORTRANコンパイラが登場して3年後のこと。ジョン・マッカーシーが、配列を操作するためのプログラミング言語としてLISP(LISt Processing)が登場しました。歴史的に見れば3番目の高級言語です。

LISPのソースコードはそれ自身が配列であり、データでもあります。またプログラミングにおいてソースコードは、ただ実行するだけの「ステートメント=文」と、実行すると一意の値になる「式」が存在しますが、LISPではすべてが式で表されます。よって、サブルーチンを作るとき、値を返さないようなサブルーチンを作ることはできません。
例えばC言語において、以下のソースコード
int main(){
int i = 1;
int j = 0;
return (i > j) ? i : j;
}
の main関数と (i > j) ? i : j; は式であり、ほかは文です。mainは最終的に i か j の値を表すようになり、(i > j) ? i : j; も i か j の値を表します。今回の例であれば i > j は成立し、? の直後の i が式の結果になり、mainはreturn文に続く式 (i > j) ? i : j; の結果である i を表すようになります。
ちなみにreturn (i > j) ? i : j; は
if(i > j){
return i;
}else{
return j;
}
と等価です。

これとまったく同じものをLISPで書くとどうなるか。
(defun main ()
(setq i 1)
(setq j 0)
(if (> i j) i j))
defunは関数に名前を付ける特殊な式で、関数名・引数・関数の定義と続けます。defunはすべてを評価した後、関数名を式の結果とします。
引数は単純な変数のリストという形で書き、その変数に引数の値が渡されます。空の括弧は何もないことを表すnilと評価され、すなわち引数がないことを表します。
setqはいわゆる変数宣言と代入です。setqは第1引数を変数名として変数に第2引数を割り当て、第2引数をそのまま返します。
ifも特殊な式で、比較を行う式・その結果が真(t)だったときの式・偽(nil)だったときの式と並んでいて、比較した式の結果が真だったときの式か偽だったときの式の結果がifの結果となって表されます。
>は続く引数リスト(今回なら i と j)に対して大小比較を行い、第1引数が第2引数より大きければ t、そうでなければnilを式の結果とします。
このように、すべて何かしらの値を返しています。
LISPはこのままでは関数名を返すだけで、実際にその関数を呼び出すことはしてくれません。どこかで呼び出す必要があります。今回の例なら、defunのあとに次のように書きます。
(main)
これでようやく関数が実行され、結果として0が返ってきます。実行する際、まずsetqを順に評価し、i には 0、j は1が割り当てられます。次に (> i j) が評価されます。これは i > j と等価で、今回この式は正しいのでt(真)と評価されます。すると今度はifが評価され、真の場合の式である i の結果を返します。これがmainの結果となって0が返ってきたわけです。

このようにLISPで自作の関数を実行するには自分で呼び出さなければならないので、引数を与える形で関数を作成した方が良い場合が多々あります。今回の例なら以下のように作る方が便利でしょう。
(defun main (i j) (if (> i j) i j))
(main 0 1)
2行目はは引数として0と1を渡しています。引数はそれぞれdefunの第2引数のリスト、今回は i と j に格納されます。引数がsetqと同じような役割を果たすので、関数は前回とまったく同じように評価されます。

関数型言語の古参でかつ定番中の定番とも言えるLISPで説明してきましたが、ほかの関数型言語も大体通用します(当然、構文などは異なりますが)。LISPは数多ある関数型言語の中でも直感的で、学習が容易だと思います。
LISPはLISPだけをつかってLISPそのものを自在に改造できる(メタプログラミング)ので、様々な方言が存在します。ここでいう方言とは、これまでも何度か扱ってきたBASICのように、おなじ言語でも処理系によって拡張されたりしている言語がある、という意味です。
方言としてはEmacsに特化されたEmacs LISP(elisp)、教育向けとして使われているらしいscheme、相次いで現れる方言を統一し、ANSIで標準規格が策定されたCommon LISP、ゼロックスのAltoに採用され一世を風靡したInterLispなどが有名です。この記事では主にCommon LISPを前提としています。例えばschemeでは真と偽の値として#tと#fを用いていて、先ほどの解説をそのまま適用することはできないようです。

それではいよいよ階乗を求めるプログラムです。ほかの言語だと大抵は2桁を超える数値から階乗を求めようとすると桁あふれで求められなかったりしますが(電卓に桁数の上限があるのと一緒)、LISPは数学の問題を解くことを得意としているので、言語レベルで何十桁にも及ぶ数値が扱えます。
(defun fact (n)
(if (<= n 1)
1
(* n (fact (- n 1)))))
関数の定義はこれで終わりです。LISPはリストや関数をすべて括弧で括って表現するので、このように括弧だらけになることで有名です。
実際に階乗を求めるときは例えば次のようにします。
(fact 120)
乗算、減算、比較などすべての演算子が先頭に来るという以外は構造化プログラミングで説明したことが通用します。その際、(fact (- n 1))は再帰になっているのも自明でしょう。

演算子が先頭に来る(前置記法)のはLISP特有のもので、演算子も関数であり、関数名は必ずリストの先頭(LISPではCAR: Contents of Address part of Register と呼ぶのが一般的です)に存在している必要があるからです。
また、LISPではリストのすべての項目に対して関数を適用することができるものもあります。例えば1+2+3+4+5は
(+ 1 2 3 4 5)
とすることで求めることができます。

 すべて表示

構造化プログラミング
[EDIT]
前回は非構造化プログラミングについて実例を使ってみてみましたが、ほかのパラダイムのサンプルがないので比較のしようがありませんでした。今回は構造化プログラミングを、前回のBASICと比べながら見てみます。
言語は引き続きcbasです。というのも、cbasはMinimal BASICを前提としながら構造化とオブジェクト指向に対応しているからです。
いきなりで申し訳ないのですが、階乗を求めるプログラムは以下の通りです。

call main


sub main
num = getFactNumber
max = num


num = fac(num)
print str$(max) + "'s factorial is " + str$(num)
quit
end sub


sub getFactNumber
while
input "Please input factorial number >$", num$
wend num$ = ""
getFactNumber = val(num$)
end sub


sub fac(i)
if i <= 1 then
fac = 1
return
endif
i = i * fac(i - 1)
fac = i
end sub

こんな感じです。別ウィンドウで前回のコードと比較してみてください。やってることは同じなんですが、長くなったわりにはすっきりしたコードに見えるはずです。前回のコードの方が見やすいという人はFORTRANあたりでも苦労することはないでしょう。とはいえ、人気のあるプログラミング言語は進化を続けていて、命令型言語はどれも構造化・オブジェクト指向化の道をたどっているのが現状です。

それはさておいて、順を追って解説しましょう。今回は行番号がないので、コードの先頭を1行目とします。
1行目はサブルーチンコールです。サブルーチンとは、ソースコードを小分けにして再利用しやすくしたもの、サブルーチンコールはサブルーチンに飛んでいく、いわばGOTOです。
call mainとあるのでsub mainまで飛んでいきます。cbasの場合sub ~ end subまでがサブルーチンになります。sub xxx というのはサブルーチンコールしたときの目標です。前回のコードで言えば行番号と同じような役割をしているわけです。

mainサブルーチンの1行目は数値変数numにgetFactNumberを代入しています。が、コードの先を見ていくと、もう一つgetFactNumberが見つかります。subではじまっているので、サブルーチンです。
構造化プログラミングでは、=演算子で代入するときにサブルーチン名を見つけると、サブルーチンコールして処理した結果を直接代入することができます。

では途中にあるコードを飛ばして先にgetFactNumberサブルーチンを見てみましょう。
getFactNumber サブルーチンの1行目にはwhileとあります。これはwendまでに書かれたコードを繰り返し実行するためのキーワードで、while文やwhileループと呼びます。
その次の行に、前回のコードでも出てきたinputがありますね。ユーザーの入力を待つ命令です。

その次の行にwendがあります。ここまでがループの本体となります。後ろにあるnum$ <> ""は見覚えがあるでしょう。前回のプログラムではこんなふうになっていました。
20 IF NUM$ = "" THEN 105
構造化プログラミングでは、たいていこのように、IF(if文)だけに頼ることなく条件判定できるのも特徴のひとつです。
ということは、wend num$ <> ""は空文字であるかどうかの判定をしています。
wendはIFの一種とも言えますから条件判定を行います。ただし、IFとは逆の挙動を示します。IFでは条件が正しいときにTHENまでを実行しますが、wendはIFで言えば、指定した条件が正しくないときにwhileに戻っていきます。したがってnum$ <> ""が正しくない(num$が空でない)と判断するとwhileに戻っていきます。正しいと判断すると、ループを抜け出しwendの次の行に戻っていきます。
前回のコードは該当部分だけを抜粋するとこんな感じでした。

5 LET FLAG = 0 : LET FAC = 1 : LET I =1
10 INPUT "Please input factorial number >", NUM$
20 IF NUM$ = "" THEN 105
105 LET FLAG = 1
125 IF FLAG = 1 THEN 5

処理が一致する部分に同じ行番号を付けて今回のコードを見ると

while
5, 10 input "Please input factorial number >", num$
125, 20 wend num$ <> ""

前回のコードに当てはめると、実行する順番は10→20→125→(5)行目です。125行目は強制的にTHENの後ろまで飛ばされますが。

ではいよいよ次の行に進みましょう。
getFactNumber = val(num$)
はてさて何だこれは。サブルーチンに対して値を代入しているか、サブルーチンとnum$を整数に変換した値を代入しているかのように見えます。これはcbas特有の構文で、サブルーチンを関数のように値を返すものにしたい場合、このようにして戻り値を与えます。
サブルーチンを抜け出したとき、mainサブルーチンの1行目、
num = getFactNumber
においてgetFactNumberに与えておいた値がnumに代入されます。

end subはサブルーチンの終わりです。構造化プログラミングの大多数はこのようにend subなどでサブルーチンを抜け出すか、returnで抜け出します。returnはサブルーチンの途中で何らかの理由で抜け出したいとき、また大部分のプログラミング言語ではサブルーチンの戻り値をreturnに渡します。

getFactNumberサブルーチンを抜けるとmainルーチンの2行目に移ります。変数maxに入力された値が入っているnumを代入しています。前回の30行目のコード
30 LET MAX = VAL(NUM$)
にあたりますが、サブルーチンを抜け出すときにVALで数値に変換しているので、VALがなくなっています。

1行開けて、やっと階乗を求める部分です。
num = fac(num)
どうやら、facというサブルーチンに、3行前で入力された値を与えて(渡して)、それを同じ変数に代入しているようです。というわけでsub fac(i)まで飛んでみましょう。
sub fac(i)
sub xxxがサブルーチンの移動先というのは解説していましたが、括弧の中身までは説明していませんでしたね。
括弧の中身は、先ほどnum = fac(num)の括弧で与えられた値が入っています。つまり i にはnumの値が入っています。この i を引数といいます。
その次は前回も見た、1以下かどうかを判定するIF文ですね。しかしthenの後ろが改行になっていて複数行にまたがっています。構造化プログラミングでは、thenからendifまでを複数行にまたがらせることができます。この中では i が1以下だったときの処理をしていて、サブルーチンの戻り値を強制的に1にしています。returnはサブルーチンを途中で抜け出す命令でした。
i が2以上であればthenからendifまでを飛ばし、endifの次の行に移動します。
ここまでを前回のコードと比較してみましょう
前回:

40 IF MAX <= 1 THEN LET MAX = 1 ELSE GOTO 50
45 GOTO 210
50 LET FAC = FAC * I
55 LET I = I + 1
60 IF I > MAX THEN GOTO 210 ELSE GOTO 50
210

今回:

40 if i <= 1 then
40 fac = 1
45 return
50 endif
50..60 i = i * fac(i - 1)

コードの実行順序は、i が1以下のときは40→40→45で、2以上のときは最初の40→50..60です。
endifの次の行が階乗を求める本体です。i とfacサブルーチンの値とを乗算して、facサブルーチンを呼び出します。このときの引数は i から1を引いた値です。i が1になるまで繰り返されます。サブルーチンの中で自分のサブルーチンを呼出し、頭から実行し直すことを「再帰」といいます。
動作を、変数の中身を見ながら追ってみましょう。i は4とします。それと矢印は関数や変数が返す値を表しています。

3←fac(4 - 1) : REM すべての i = i * fac(i - 1)
2←fac(3 - 1) : REM が先に実行される
1←fac(2 - 1)
if i <= 1 then→true
1←fac = 1
end sub
sub fac(2(i) - 1)
2←i 2← i * 1←fac()
2←fac = 2← i
end sub
sub fac(3(i) - 1)
6←i = 3← i * 2←fac()
6←fac = 6← i
end sub
sub fac(4)
24←i = 4← i * 6←fac()
24←fac = i
end sub

分かりやすくなったでしょうか?かえってわかりにくい?
まずは再帰呼出しになっているfac()をひたすら繰り返し、引数が 1 になったところで(3行目)if i <= 1 thenがtrueになり(4行目)、戻り値として1を返して(5行目)end sub(6行目)で1つ上のsub fac()の再帰呼出し部分に戻ります(7行目=3行目)。ここで i = i * fac(i -1)の i * fac()を実行します(8行目)。fac()の戻り値が1で、このサブルーチンに入ったときに実行されるsub fac(i)の i に与えられた値が i = i * fac(i -1)のすべての i に入っています。サブルーチンの引数を受け取る変数(ここでは i)を用意すると、その名前の変数すべてに引数が割り当てられるからです。

ということで一番最初の再帰呼出しで4 - 1が与えられていますが、一番最後に呼び出された再帰を抜け出すと3行目の状態(i = 2)から継続されます。fac i = i * fac(i -1)は i(2) = i(2) * fac()になっています。facは1を戻り値として返しているのでつまりi = 2(i) * 1(fac())です(8行目)。これを戻り値としてサブルーチンを抜け出します(fac = 2)。
同じようにしてサブルーチンを抜け出しsub fac(3 - 1)(11行目=2行目)のサブルーチンを続行します。fac i = i * fac(i -1)は i = i(3) * fac()でfacの戻り値は2ですから i =3(i) * 2(fac())と等価です。そしてfac = 6として再帰を抜け出します。
最後に再帰の一番上に帰ってきます。一番最初のサブルーチンに与えた引数はsub fac(4)でした。したがってfac i = i * fac(i -1)は i = i(4) * fac()で、facの戻り値は6ですから i = 4(i) * 6(fac())です。これを実行してfac = 24、end subで抜け出してmainに戻り、num = fac(num)を実行します。左辺のnumには24が代入され、printではれて答えが表示され、quitでプログラムを抜け出します。

最後までおつきあいありがとうございました。いかがでしょう?あまり複雑なプログラムではないので実際のところどっちがいいかわからないかもしれませんね。
非構造化プログラミング
[EDIT]
非構造化プログラミング言語がどのようなものか、非構造化プログラミング言語の代表格、BASICで見てみましょう。
BASICは1964年に米ダートマス大学で産声を上げました。コンピュータの教育用としてジョン・ケメニーとトーマス・カーツが開発し、同大学のコンピュータに組み込まれました。このBASICはコンパイラを通して実行されるよう設計されていて、ダートマスBASICと呼ばれるようになります。
1970年代には自作の8ビットコンピュータ、1980年代には8~16ビットパソコンで爆発的に普及します。とくに当時のパソコンにはOSが存在せず、代わりに大幅に機能を削ったBASICを利用していた関係で広く使われ、インタープリタやコンパイラも多数販売されていました。その中の筆頭となるのがMicrosoftで、MS-BASIC、GW-BASIC、QuickBASICといった製品が同社の飛躍に繋がります。後者ふたつはやがてVisual Basicへの足がかりにもなっています。
BASICはFORTRANやCOBOLに次いで標準規格が策定されましたが、将来性をまったく考慮しない限定的なものでした。パソコンの成長は目覚ましく、標準規格はあっけなく陳腐化し、各社で独自の拡張を施すことが流行り、様々なバリエーションが存在します。
その中でも無料で、makeなどすることなくすぐに利用できる、マルチプラットフォームのChipmunk Basic(以下cbasと略)を使ってみます。Mac版は歴史的な経緯でGUIバージョンが存在しますが、コマンドラインバージョン前提で解説します。もちろん中身はほぼ同じどころかGUI用に機能が拡張されているくらいですので、GUIバージョンのコマンドラインウィンドウで実行しても構いません。ターミナル.appから利用する場合はCarbon_window_versionフォルダかcommand-line-versionフォルダにあるbasicというファイルをインストールします。
まずHello,world!の次くらいに定番であろう練習プログラム、階乗を求めます。

5 LET FLAG = 0 : LET FAC = 1 : LET I =1
10 INPUT Please input factorial number >", NUM$
20 IF NUM$ = "" THEN 105
30 LET MAX = VAL(NUM$)
40 IF MAX <= 1 THEN LET MAX = 1 ELSE GOTO 50
45 GOTO 210
50 LET FAC = FAC * I
55 LET I = I + 1
60 IF I > MAX THEN GOTO 210 ELSE GOTO 50
100 REM エラー処理
105 LET FLAG = 1
110 PRINT "ERROR: No input."
120 INPUT "Please input any key to retry >", K$
125 IF FLAG = 1 THEN 5
130 QUIT
200 REM 計算終了
210 PRINT NUM$ + " factorial is " + MAX
220 GOTO 120

テキストエディタで入力し終えたら、アルファベットのファイル名に拡張子.basを付けて保存します。今回はfactor.basとでもしましょう。実行はxtermやターミナル.appなどから
basic factor.bas
でreturnキー。すると10行目(1行目ですが10を指定したため)のPlease input factorial number.が表示され、入力を求めてきます。半角で階乗を求めたい値を適当に入力してください。ただしあまり大きな値は入力しないように。
returnキーを押すと結果が返ってきます。

その前にある5行目は変数の初期化(初めて変数に値を代入すること)です。
LETはLet's GO!などでもおなじみの「~しよう」、「~しなさい」という命令です。つまるところLET FLAG = 0は「変数FLAGと0を等しくしなさい」という意味で、プログラミングでは代入といいます。
実はこのLET、省略することが可能で、FLAG = 0だけでもかまいません。何で省略できるのにわざわざ付けたかというと、プログラミングに慣れていないとFLAG = 0だけでは「変数 FLAGと0は同じである」と勘違いして混乱してしまいます。「変数 FLAGと0は等しくないかもしれないのに同じなのか。等しくなかったらどうなるんだ?」といった感じですね。LET FLAG = 0なら「変数FLAGと0を同じにしなさい」と読むことができ、すんなり理解できるわけです。この辺は教育向けに設計されたゆえのおせっかいというわけです。
BASICは1行1命令といいましたが、コロン : を使うことで1行にまとめることができます。ただし、古いBASICだと1行何文字、と決まっていることが多いので、今回のような短い命令をまとめる程度にしましょう。
というわけで、ここでは変数FLAGは0、残りの変数FACとIは1を代入します。

20行目は入力が空だった(returnだけを押した)場合にエラーとして処理させます。そのときはTHENに続く行番号、ここでは105行目に飛びます。入力が空の場合、変数に格納された文字は空(空文字)になっています。空文字は""と、ダブルクオート2つ「だけ」で表現されます。入力が空かどうかの判定は、変数と空文字が同じであるという比較 IF NUM$ = "" THEN で行います。
NUM$ = "" は一見「変数NUM$を""にする」と思ってしまいますが、手前にあるIFが続く式を比較するという意味を持っているので「変数NUM$と""は等しい」と読むことができるわけです。IFは文字通り「もしも」、THENも「ならば」という意味ですから、「もしも変数NUM$と""が等しいならば」と読みます。すっかり英文になってしまいました。これがBASICのよいところです。
THENの後の数字は、移動する行を指定しています。つまり105行目(実際に105行なくても、頭に付けた数字が行番号です!)に移動する(ジャンプする、飛ぶ)ということになります。入力が空でなかった場合、THENの後の数字は無視して次の行を実行します。

30行目は数値を受け取る変数に、入力された文字を数値に変換してから代入します。入力された数字は文字であり、数値変換しないと数学的な演算が正しくできなくなることがあります。これはプログラムを実行するプログラムが、文字で受け取ったものは文字であり、数字でも計算に使うものではない、数値として受け取ったものは数値であり計算のために使う、というように区別しているからです(実際のところは全然違うんですが、そういうものだと思ってください。ややこしい話ですので)。
VAL(NUM$) というのが文字を数値に変換する関数です。()の中に与えた文字列変数(引数=ひきすうといいます)を数値に変換して、= の左側(左辺)の数値変数に代入します。

40行目に再びIFが出てきました。ここでは変数 MAXが1以下(未満ではない)かどうかを調べます(大小・等不等を比較することを比較演算といいます)。数学では以下を表す不等号として≦がありますが、これは古いコンピュータで使用することができなかったた、また他言語かが進んだ現在でも手軽に入力できるようにするため、<=で代用しています。
閑話休題。比較演算でMAXが1未満とわかったらTHENの後ろが実行されます。前回出てきたIF~THENでは行番号を指定していましたが、今回は LET MAX = 1 ELSE GOTO 50 と書かれています。古いBASICではこのように、行番号を指定して実行する行を移動したり、なんらかの処理を行わせることも可能になっています。
つまりMAXが1以下であれば LET MAX = 1 が実行されてMAXは1を保持し(0および1の階乗は1)、ELSE以降を無視して次の行に移ります。
ELSE以降はMAXが1以上のときに初めて効力を発揮します。THENとELSEの間を無視してELSEに続く1つの命令を実行します。GOTOはBASIC最大の汚点と言われた命令で、指定の行番号かラベルに飛びます。ここでは行番号をしていしているので50行目に飛ぶわけです。

45行目はあとから50行目の前に挿入したのでこうなっています。行番号を2桁以上、通常は10とか100単位で増えるようにして、挿入時は1や5単位で行番号を割り当てておくと、何処に修正を加えたかが分かりやすくなります。ここには40行目でMAXが1以下だったときに、ELSEで飛ばされてくる場所です。GOTO 210と書いてあるので210行目に飛んでいきます。

50行目はいよいよ階乗を求める部分です。階乗の数学的な式は、たとえば4の階乗を求めたいなら1×2×3×4=24です。乗算を繰り返し行うのでループを使います。
まず、階乗の途中計算を入れておくFACに、FACとIを乗じた値を代入します。5行目でFACとIを1に初期化しているので、LET FAC = 1 * 1をやっていることになります。たいていのプログラミング言語は、≦と同じ理由で、×のかわりにアスタリスク * を使います。
55行目でLET I = I + 1を行ってIは2になります。
60行目はIがMAXを超えたかを調べ、等しければ210行目へ抜け出し、そうでなければ50行目に戻ります。この場合LET FAC = FAC + 2なのでFACは1 * 2の結果が代入され、55行目でIが3になります。
MAXを4とすれば、Iはまだ3なので50行目に戻り、LET FAC = 2 * 3が実行されます。55行目でIがMAXと同じ4になりますが、このままではFACは6で、まだ1×2×3までしか計算していないことになります。60行目でIがMAXを超えたかを調べているのはこのためです。50行目と55行目を入れ替えればIとMAXが等しくなったかを調べるようにすることができます。
さて、IはまだまだMAXを超えていないので、再び50行目に飛ばされます。LET FAC = 6 * 4を実行して晴れてFACが24になりました。55行目でIもMAXを超えることになり、ループを抜け出します。

100行目はREMの後ろに「エラー処理」と書かれています。REMはreminderの略で、コメントとか注釈という意味です。Cをご存知なら/* エラー処理 */ですし、HTMLなら<!-- エラー処理 -->と書いたのと同じで、cbasはREMより後ろを無視して次の行に進みます。つまりcbasにとっては何が書いてあるかなど知ったことではないので、日本語を書いても問題ありません。その時はUTF-8Shift-JISで保存しましょう。

105行目はフラグを立てます。フラグというのは、簡単に言えばプログラムの状態を表すものです。例えばエラーが起きているか正常か、といった状態です。105行目には20行目で入力が空だったときに飛んでくる場所でした。つまりエラーが起きたということなので、フラグ変数FLAGに1を入れます。別に1じゃなきゃいけないわけではないのですが、フラグにはたいてい何もなかった(フラグが立っていない)ときは0、何かしらあった(フラグが立った)ときは1を入れます。
110行目はエラーが起きたことを画面に表示します。
120行目はメッセージを確認したかどうかを調べるため、キー入力を待つことでプログラムが勝手に進まないように防いでいます。
125行目はエラーが発生したかどうかを調べています。ここではとりあえず入力が空であることを再度調べています。何度も同じことを調べるのは変な話ですが、あとで理由がわかるでしょう。
エラーが発生していた場合は5行目まで戻ってもう一度計算するチャンスを与えています。

130行目を飛ばして200行目です。コメントとして「計算終了」とあります。つまり階乗の計算が終わったらここに来て色々行うわけです。
210行目では入力された値に対する階乗の結果を表示します。実は文字同士も一応足し算はできます。ただし足し算といっても、文字と文字とを繋ぎ合わせるだけですが。こうすることでいくつもの変数の内容を1つの命令だけで表示させることができます。
220行目はGOTOで120行目に飛ぶよう指定しています。120行目はメッセージを確認するまで待つ処理を入れていました。計算結果を表示したら、やはり一旦実行が止まってほしいですからね。
その次の125行目も存在意義が発揮されます。200番台の行に飛んできた場合、FLAG変数は5行目で0に初期化したままなので、THENの後ろは無視されて130行目に移動します。
130行目のQUITはアプリケーションを終了させる命令です。

いかがでしたか?プログラミングがどのようなものかを理解できる一助になれば幸いです。
非構造化と構造化の違いは次の記事で理解することができるはずです。お楽しみに。

Appendix

プロフィール

さくらゆーな

Author:さくらゆーな
鉄道熱が再燃して、撮影に模型にいろいろやってます。
最近反核運動に偏ってるのを反省したいけど
知れば知るほど極悪非道な界隈で止まらない…

カレンダー

08 | 2017/09 | 10
- - - - - 1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

+ アーカイブ
 

最近の記事

カテゴリー

検索フォーム


キーワード

カウンター

トータルカウンター
現在の閲覧者数:

ads3

Mac ソフトのことなら act2.com

Make a donate

もしこのブログを気に入っていただけたら上記アフィリエイトプログラムか下のPayPalでブログ・サイトの維持にご協力ください。

donationPrice

ブロとも申請フォーム

この人とブロともになる

ブログランク

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。