第 1 回プログラムの分割

本日の内容

1-1. 講義の前に
1-2. プログラムの分割
1-3. 関数

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

1-1. 講義の前に

この講義の狙い

この講義ではオブジェクト指向言語 Java のデータ構造であるオブジェクトに焦点をあて、オブジェクト指向におけるデータ構造とアルゴリズムについて学びます。特に、継承という仕組みを重点的に学びます。継承を理解せずにこの科目を習得することは難しいでしょう。前半はオブジェクト指向の基礎と、継承を学びます。後半はコレクションクラスライブラリと数学的な補足を行います。

期末試験は行わず、評価はレポート二通で行います。

なお、大学院を他大学で学びたい人は、昨年までのデータ構造とアルゴリズムの方が入学試験範囲をカバーしていると思われます。この講義の後半部分とデータ構造とアルゴリズム II の一部が若干重複していますが、ほぼ関連はありません。したがって、他大学大学院へ行くには昨年までの講義資料も学習する必要があるでしょう。

データ構造とアルゴリズムII の内容

この講義を終えた後、引き続いて「データ構造とアルゴリズム II」という選択科目が始まります。内容は XML の構造と処理をメインテーマに、前半部分は処理の原理を、後半部分は XML を使用するアプリケーションの作成をテーマに行います。この科目を履修すると XML のアプリケーションに関する基礎知識が身につけられます。

講義の進め方

この講義では Java 言語を主に使用しますが、対比のために C 言語も多少取り上げます。本講義を受講すると C 言語がどのような機能を持つ言語かは分かるようになりますが、昨年までの講義と違い C 言語のプログラミングテクニックを多く説明したりはしません。

Java に関しても、本講義で重要と思われることのみを説明します。つまり、 Java の全ての機能を説明するわけではありません。機能の一部やクラスライブラリの一部しか紹介しません。つまり、この講義では Web アプリケーションや、データベースとのやりとりなどは行いません。これらに関しては対応する講義で学んでください。

講義の受け方

今年度は初年度なので、講義資料を書き下ろすことになります。したがって、講義直前まで講義資料の推敲を行うことになると思うので、予習はしづらいです。そのため、復習に力を入れてください。講義で紹介したプログラムを動かしたり、自分の好みな形に改造したりして、プログラムの動作を完全に把握してください。又、参考文献に挙げた書籍を読むのも良いでしょう。但し、 Java は Version 5 から大きく変わり、プログラミングテクニックも変化しています。しかし、それに対応した書籍は少ないです。 Version 1.4 以前の書籍を読む場合は、サンプルプログラムのコンパイル時にワーニングすら出る場合があります。

レポート課題は例年通り、講義の資料にある演習問題を組み合わせたような内容を出題します。

この講義は勉強せずに単位を取ることは難しいです。他人に頼らずプログラムを書けるようになるよう目指してください。

1-2. プログラムの分割

大規模なコンピュータプログラムは多人数で作られたり、複数の工程で作られたりと、必ず分割して段階的に作成されます。今回ははじめにこのプログラムの分割法を学びます。

Turing Complete

プログラミングに必要な最低限の知識とは何でしょうか？実は、あらゆるプログラムは次の三要素の組み合わせで作れることが分かっています。

if 文
繰り返し文
変数による配列変数のアクセスなどの、変数による間接的なアクセス

このあらゆるプログラムが作れるという性質をTuring Completeと言います。

これらの要素は既に 1 年次で学んだことです。つまり、プログラムを書く上で最低限の学習は済んでいます。これ以上のプログラミングテクニックは「より良いプログラムを書く」ためのものです。

この講義におけるプログラミング手法を学ぶ目的は、複雑なプログラムを組むためと、大量のデータを扱えるようになることです。講義の前半は複雑なプログラムを扱うため、プログラムに構造を与えて分割する方法を学びます。

プログラムの分割

例えば、ある小説に対して、その小説の続編を書くことを考えましょう。すると、小説すべてを読まないと、続編を書くことが難しいことがわかります。

一方でWindows Vista は数千万行のプログラムでできていると言われています。これが一本のプログラムでできているとすると、修正、拡張、改良などを行うにはすべてを把握しなければならず、とても困難な作業になります。しかし、実際には Windows のプログラムを作る際に Windows そのもののプログラムをすべて読んだりはしません。さらに、 Java では一旦プログラムを組むと、Windows で動くばかりでなく、 MacOSX や Java 対応の携帯電話など、全く異なる装置や搭載されている OS の異なるコンピュータで、同じプログラムが動作します。

この違いはなにかと言うと、小説は先頭から最後まで一直線に読むということのみを想定して書かれているのに対して、コンピュータのプログラムは小さなプログラムの部品からなっていて、それらの部品を組み合わせて一つのプログラムができているからです。つまり、これは、異なる装置が接続されているコンピュータに対してでも、「画面に字を書く」、「キー入力」などの同等の操作で、同じように使用できるようなプログラムがそれぞれに用意されています。そして、さらに Java ではその操作の組合せだけでプログラムを組むことができます。

この考え方の重要なポイントは次の通りです。コンピュータは CPU にキーボードや画面などの I/O が接続されていますが、これらを制御するには「メモリ XXXX 番地に、メモリ YYYY 番地の値をコピーする」というような操作をします。この操作はコンピュータの設計毎に異なりますので、機種ごとに異なって当然です。例えば画面に点を打つというような操作を行うためのメモリの番地は機種ごとに異なります。しかし、ほとんどのアプリケーションプログラムでは画面の解像度やフォントの美しさなどという機種毎の性能を追求するよりは、機種間の相違を吸収して「文字列を画面に書く」というような抽象的な概念で操作したい場合がほとんどです。そのため、画面に点を打つような機種毎に異なる装置の操作は、その機種専用のプログラムを用意し(これをデバイスドライバと呼びます)、それを利用して画面に文字を出すようなプログラムをさらに共通に用意し(これをアプリケーションプログラムインターフェイス、 APIと呼びます)、アプリケーションプログラムを組む際はこの API を利用してプログラムを書きます。 API の例としては C 言語の printf などがあります。 printf を C 言語から呼び出すと、どんな解像度のコンピュータでもコンソール画面と呼ばれる領域に文字列を出力することができます。このコンソール領域に目を近づけて見ると、文字列自体はすべて点の集まりであることがわかります。

コンピュータプログラムは人間が作るもので、人間のために、人間が使うように作られます。そのため、プログラムが指示する動作自体は人間の思考が記述されています。そのため、プログラミング言語は人間の考え易いように抽象化の方法が備わっています。人間の思考には「複数の事柄に一つの名前を付ける」などの抽象化が行われますが、プログラミング言語でも複数のことがらをまとめて一つの名前で取り扱う仕組が用意されています。この機能を使って書かれている長いプログラムは、単に長いのではなくて、様々な抽象的な事柄が事柄毎に分割されて記述されています。

さて、この講義の当初の目的はプログラムを分割し、抽象化して書く手法を紹介することです。分割をする目的は、分割したプログラム同士が抽象的な意味を持ち、互いのプログラムの細部をすべて読まなくても、機能を理解できて相互に活用できるようにすることです。

1-3. 関数

多くのプログラミング言語が実現しているプログラムの構造として、サブルーチンや関数と呼ばれるプログラムの分割手法があります。これは、大きなプログラムのうち、まとまった処理を抽象化するものです。関数とは処理に必要な入力値に対して、処理の結果得られる出力値を計算するという部分を切り出したものです。

なお、関数には名前を付けますが、この名前に関しては何をするものか具体的に分かるように比較的長い名前を付けます。

C 言語の関数

関数の例を示すため、 n 個のものから m 個のものを取り出す組合せの数を考えます。この組合せの数は次の式で表せます。

_{n} C_{m} = \frac{n!}{m! (n - m)!}

これを素朴に定義通り計算することを考えます。つまり、階乗を求め、その階乗を使って組合せの数の計算をします。下記のようなプログラムを作成したいという意図ではありません。

例1-1


#include <stdio.h>
main(){
  int n,m;
  int i;
  int f1, f2, f3;
  printf("Input n and m: ");
  scanf("%d%d",&n,&m);
  f1=1;
  for(i=2;i<=n;i++){
    f1*=i;
  }
  f2=1;
  for(i=2;i<=m;i++){
    f2*=i;
  }
  f3=1;
  for(i=2;i<=n-m;i++){
    f3*=i;
  }
  printf("%dC%d =  %d\n",n,m,f1/f2/f3);
}

このプログラムでは階乗を 3 回にわたって似たようなプログラムにより計算しています。データの流れとしては確かに階乗を計算して、組合せの数を計算していることになっていますが、プログラム的には「階乗を計算する部分」や、「組合せの数を計算する部分」といった、人間の思考に相当する部分には分割できていません。今回の目標はこのようなプログラムではなく、「階乗を計算する部分」「組合せの数を計算する部分」「入力値にしたがって、計算値を出力する部分」に分割することです。

プログラムの分割法として、C 言語では関数という仕組みがあります。これを使うことにより、この計算をするのに階乗を計算してから最終的な値を求めることができます。プログラムの構成は、階乗を計算する関数、その関数を元に組合せの数を求める関数、さらに入力値にしたがって、計算値を出力する関数の 3 つの部分に分割できます。

階乗を計算する関数
階乗を計算する関数を呼び出し、組合せの数を求める関数
求めたい値を定め、組合せの数を求める関数を呼び出し、結果を出力する部分

ここでは階乗を表す関数を factorial(n) と表すことにしましょう。この関数は整数 n 与えられると、 n! の値となる整数を一つ返します。 C 言語で関数を使用するには、このように入力する値を丸カッコの中に入れます。そして、得られた値は sin(x) などの数学の関数と同じように数式内で使うことができます。

factorial(n) の定義は、次のように行います。


int factorial(int n){
 n から factorial の値を計算する仕方
 return 求めた値;
}

最初の int は出力される値の型を表し、カッコの中の int は入力される値の型を表しています。 factorial の計算法の中では入力された値は n を使って計算します。

さらに、組合せの数の計算も関数で書くと次のようになります。


int combination(int n, int m){
  n と m と factorial 関数を使った組合せの数の計算の仕方
  return 求めた値;
}

プログラムをまとめて書くと次のようになります。


#include <stdio.h>

int factorial(int n){
 factorial の計算法
 return 求めた値;
}
int combination(int n, int m){
  factorial 関数を使った組合せの数の計算
  return 求めた値;
}
main(){
  int n,m;
  printf("Input n and m: ");
  scanf("%d%d",&n,&m);
  printf("%dC%d =  %d\n",n,m,combination(n,m));
}

このようにプログラムを 3 分割できました。 main() は combination(n,m) を呼び出し、 combination(n,m) は factorial(n) を呼び出します。このようにすると、factorial や combination や main をそれぞれ別々に作ることができますし、場合によっては複数の人間で作ることもできます。また、それぞれの関数をテストすることも可能になります。

なお、今までプログラムを実行させるためにおまじないとして main() というものを書いて来ました。しかし、実は C 言語ではプログラムは全て関数の形で書きます。つまり main() も実は関数の一種です。 main という名前の関数はプログラム実行時に呼び出されると言う特別な関数です。なぜこの記述で main 関数が定義されるかですが、次の二つの省略のルールがあるからです。

C 言語では関数の出力の型が int である場合、省略できます
入力される値がない場合、空の括弧を書くこともできます。

この、出力の型を省略することは、本来は値を返すべき定義であることを隠してしまうので良い記述法ではありません(が、記述がシンプルになるという利点はあります)。さて、main 関数は int 型であると決まっているので、本来は値を返す必要があります。値はプログラムが正常に終了したか、異常に終了したかを返します。そのために return 文を書く必要があります。この、正常終了、異常終了を表す値は stdlib.h に登録されています。正常に main 関数を終了するには EXIT_SUCCESS, 異常終了するには EXIT_FAILURE を返します。但し、EXIT_SUCCESS の代わりに 0 も使って良いので、 stdlib.h を読み込んで return EXIT_SUCCESS; とする代わりに、単純に return 0; と返しても良いです。なお、この返した値は OS から参照できます。 Windows の場合 ERROR_LEVEL 環境変数に値が渡されます。ここで、もし、 return を記述しないと値は不定になります。

例1-2


int main(){
  return 5;
}

このプログラムをコンパイルし、下記のように実行すると 5 が出力されます。


c:\work> .\a.exe
c:\work> echo %ERROR_LEVEL%
5
c:\work>

次に、 2 の説明をします。 C++ や Java では引数がない場合は何も書かないのが流儀ですが、 C 言語の場合は、後で説明する古いプロトタイプ宣言と互換性がなくなります。そのため、通常の関数で引数なしを示すには void を記述すべきです。 main 関数にプロトタイプ宣言は要りませんが、記述を統一するためにも C 言語では main 関数でも void を記述した方が良いです。

以上をまとめると、以下の 1 のように記述していた main 関数は、今後、 2 のように記述するよう改めるべきです。

1. 従来の C 言語の書き方

main(){
  /* プログラム */
}

2. 今後の C 言語の書き方

int main(void){
  /* プログラム */
  return 0;
}

なお、この他に C で作ったプログラムを起動する際に、引数を与えることができます。その場合、main 関数は次のように記述します。


int main(int argc, char *argv[]){
  /* プログラム */
  return 0;
}

つまり、 C 言語では main関数の引数にはこのように void のみと、 int, char *[] の組の二種類の宣言の仕方があります。

プログラム

以下は例に対して動作するようにプログラムを作成したものです。


#include <stdio.h>

int factorial(int n){
  int result,i;
  result=1;
  for(i=2; i<=n; i++){
    result*=i;
  }
  return result;
}
int combination(int n, int m){
  return factorial(n)/factorial(m)/factorial(n-m);
}
int main(void){
  int n,m;
  printf("Input n and m: ");
  scanf("%d%d",&n,&m);
  printf("%dC%d =  %d\n",n,m,combination(n,m));
  return 0;
}

Java 言語の(静的)関数

さて、次に Java での関数の記述法についてついて学びます。基本的には Java の文法は C 言語と同等です。しかし、 Java における関数などは class に属していないといけません。また、 main 関数自体が static 宣言されているので、 main から呼び出される関数は static 宣言がされてなければなりません。

また、 Java では関数にアクセス修飾子を付ける必要があります。アクセス修飾子には次のような種類があります。

アクセス修飾子	効能
private	同一クラス内のみでアクセス可能
protected	同一クラス、派生クラスのみでアクセス可能
なし	同一パッケージ(同じフォルダ内)のみでアクセス可能
public	どこからでもアクセス可能

ここで、どのアクセス修飾子を選ぶかですが、先に述べたように、プログラムのすべてを読まずにプログラムを作っていくには、各部分部分が抽象化されて一まとまりの部品になる必要があります。そのため、同一クラス内で使うだけの関数は、外部に見えないようにするべきです。そのため、このアクセスはできるだけ厳しく、つまり基本的には private 修飾をするようにします。


class Rai1 {
  private static int factorial(int n){
   factorial の計算法
   return 求めた値;
  }
  private static int combination(int n, int m){
    factorial 関数を使った組合せの数の計算
    return 求めた値;
  }
  public static void main(String[] arg){
    int n,m;
    n と m の入力
    System.out.println(n+"C"+m+"=  "+combination(n,m));
  }
}

補足

Java プログラムでは「 java クラス名」で起動させるとクラスに所属している public static 修飾された main 関数が実行されます。 main 関数の引数は java.lang.String の配列型のみになります。また、main は C 言語と違い OS に何も返さないので、引数の宣言は void 型になります。

static 修飾されている関数から別の関数を呼ぶには static 修飾されている必要があります。したがって、 main から combination を呼ぶために combination も static 修飾、 combination から factorial を呼ぶために factorial も static 修飾をしなければなりません。

Java でプログラムを動作させるには、 C 言語のように変数宣言が実行文の前に無いとならないという制約がありません。そのため使う直前に変数宣言をした方がプログラムがみやすくなります。

また、 Java には C 言語の scanf のような便利な入力関数はありません。ここでは、一行文字列を読み込んで、数値に変換するようにします。この手法に関しては次回以降詳しく説明します。とりあえず下記の定石を使うこととします。


    java.io.BufferdReader br =
      new java.io.BufferedReader(
        new java.io.InputStreamReader(java.lang.System.in));

このようにすると、変数 br は readLine メソッドを使って System.in(標準入力) から一行ずつ文字列を読み込むことができます。これを java.lang.Integer.parseInt 関数を使って整数を取り出します。


    int n = java.lang.Integer.parseInt(br.readLine());

入力された値を保持する変数を表す意味で、入力時に変数宣言するようにしています。

プログラム

以下はこれまで述べた説明を元に動作するように作ったプログラムです。


import java.io.*;
class Rai1 {
  private static int factorial(int n){
    int result=1;
    for(int i=2; i<=n; i++){
      result*=i;
    }
    return result;
  }
  private static int combination(int n, int m){
    return factorial(n)/factorial(m)/factorial(n-m);
  }
  public static void main(String[] arg) throws IOException {
    BufferdReader br =
      new BufferedReader(
        new InputStreamReader(System.in));
    System.out.print("Input n: ");
    int n = Integer.parseInt(br.readLine());
    System.out.print("Input m: ");
    int m = Integer.parseInt(br.readLine());
    System.out.println(n+"C"+m+"=  "+combination(n,m));
  }
}

クラスライブラリの利用

Java には標準で様々な関数が提供されています。例えば、数学関数は java.lang.Math クラスに定義されています。平方根は次のように定義されています。


package java.lang;
public class Math {
  public static double sqrt(double x){...}
}

これを呼び出すには java.lang.Math.sqrt(x) のように書くのが原則です。但し、次のような場合はパッケージ名を省略できます。

java.lang パッケージ
import で宣言されたクラス

そのため、平方根は Math.sqrt(x) とだけ書けば良いことになります。また、import java.io.*; とすることで、標準入力から一行読み込むためのオブジェクトの宣言を次のようにできます。


    BufferdReader br =
      new BufferedReader(
        new InputStreamReader(System.in));

関数化によるリファクタリング

プログラムを見やすく、保守しやすくするためのプログラムの書き換えをリファクタリングと言います。ここでは関数を利用したリファクタリングの手法を紹介します。

長いプログラムはそのもの自体が一つの機能を表しているわけではなく、ほとんどの場合いくつかの部分に分割できます。その場合、プログラムを読みやすくするための手軽な方法として次の方法がとられることがあります。

変数名を工夫して、何が入っているかを示す
コメントをつけてプログラムの意味を補足する

これはプログラマーが性善説に基づいている場合は有効な手法ですが、仮に自分一人でプログラムを書いていても裏切られることがあります。これはそれぞれ次のような理由によります。

変数は値を取り出す他に、いつでも代入ができます。また、計算途中の変数の内容が変数名が表しているわけではありません。


int sum=0; //sum は合計を表してない
for(int i=1; i<=n ; i++){
  sum+=i; //sum は合計を表してない
}
// ここで初めて sum は示すべき合計の値を持っている

コメントが間違っていてもプログラムは動作します。したがって、たとえ自分自身だけでプログラムを作っている場合でも、プログラムを修正する際にコメントが正確に修正される保証がない時があります。例えば、細かくプログラムを変えながら繰り返しテストをするような状況では、正しいコメントを付けなくなりがちです。

そこで出てくるのが、たとえ一回しか使わなくても、プログラムの適当な部分を取り出して、意味のある長い名前の関数にしてしまう方法です。さらに、計算に使う変数が計算が終わるまで意図した値にならないことを避けるために、変数を使う代わりに関数を使用します。

例を示します。

例1-3


class Re12 {
    public static void main(String[] arg){
	int num=10;
	int sum=0;
	for(int i=1; i<=num ; i++){
	    sum+=i;
	}
	Sysmtem.out.print("1 から "+n+"までの合計は");
	System.out.println(sum);
    }
}

これをリファクタリングすると次のようになります。


class Re12 {
    private static int sum(int n){
        int s=0;
        for(int i=1; i<=n ; i++){
	    s+=i;
	}
        return s;
    }    
    public static void main(String[] arg){
	int num=10;
	Sysmtem.out.print("1 から "+n+"までの合計は");
	System.out.println(sum(num));
    }
}

このようにすると main が短くなります。さらに、入力、出力と計算法が main で混在していましたが、 sum(num) が num の合計を表すことが直感的に分かり計算法を分離できました。そして計算用変数 sum を main から取り除けます。又、関数 sum は合計を計算するだけのプログラムです。さらに、この中の変数 i や s は外部から決して影響を受けない、合計を求めるためだけに使われる変数であるということが、関数の中で宣言しているために保証されます。さて、この sum の部分は入力が n で出力が 1 から n までの合計を返すという仕様がはっきりしています。そこで、他に効率が良い方法があれば入力と出力だけ合っていれば別の計算法に置き換えても問題ありません。


    private static int sum(int n){
        return n*(n+1)/2;
    }

関数に置き換えることで、計算途中の変数の保護、主プログラムからの変数の削除などができます。また、コメントや変数名と違い、計算内容にそぐわない誤った関数名によるプログラムは間違ったアルゴリズムに読めるため、誤った関数名を直そうという動機が保たれ、保守の優先順位は高くなるはずです。

関数を一回しか使わないとか、一行で終わるとかは関係ありません。このようなリファクタリングはプログラムが読みやすくなるだけではなく、後に説明するようにオブジェクト指向につながります。

演習問題

今回はプログラムの計算部分を取り出して関数化し、 main から計算用の変数を取り除く練習をします。

演習1-1

次のプログラムのうち、判別式を計算する関数 double discriminant(double x, double y, double z) を作り、変数 d を無くしなさい。


class Enshu1 {
    public static void main(String[] arg){
	double a=1;b=2;c=3;
	double d=b*b-4*a*c;
	Sysmtem.out.print("方程式"+a+"x^2+"+b+"x+"+c+"=0");
	System.out.println("の判別式は"+d);
    }
}

演習1-2

次のプログラムで、判別式を計算する関数 double discriminant(double x, double y, double z) を作り、変数 d を無くしたあと、さらに、その関数を利用して実根判定をする関数 boolean hasRealRoots(double x, double y, double z) を作り、 if 文の中の条件式を取り除きなさい。


class Enshu2 {
    public static void main(String[] arg){
	double a=1;b=2;c=3;
	double d=b*b-4*a*c;
	Sysmtem.out.print("方程式"+a+"x^2+"+b+"x+"+c+"=0");
	if(d>=0){
	    System.out.println("は実根を持つ");
	}else{
	    System.out.println("は実根を持たない");
	}
    }
}

演習1-3

次のプログラムで、判別式を計算する関数 double discriminant(double x, double y, double z) を作り、変数 d を無くしたあと、さらに、その関数を利用して実根の数を計算する関数 int numberOfRoots(double x, double y, double z) を作り、変数 num を取り除きなさい。


class Enshu3 {
    public static void main(String[] arg){
	double a=1;b=2;c=3;
	double d=b*b-4*a*c;
	int num;
	if(d>0){
	    num=2;
	}else if(d==0){
	    num=1;
	}else{
	    num=0;
	}
	Sysmtem.out.print("方程式"+a+"x^2+"+b+"x+"+c+"=0");
	System.out.println("の実根の数は"+num);
    }
}

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 1 回 プログラムの分割

本日の内容

1-1. 講義の前に

この講義の狙い

データ構造とアルゴリズムII の内容

講義の進め方

講義の受け方

1-2. プログラムの分割

Turing Complete

プログラムの分割

1-3. 関数

C 言語の関数

例1-1

例1-2

プログラム

Java 言語の(静的)関数

補足

プログラム

クラスライブラリの利用

関数化によるリファクタリング

例1-3

演習問題

演習1-1

演習1-2

演習1-3

第 1 回プログラムの分割