ホーム » 「関数型プログラミング」タグがついた投稿

タグアーカイブ: 関数型プログラミング

2024年2月
 123
45678910
11121314151617
18192021222324
2526272829  

検索・リンク

オブジェクト指向/2022/ガイダンス

専攻科2年のオブジェクト指向プログラミングの授業の1回目。

最近のプログラミングの基本となっているオブジェクト指向について、その機能についてC++言語を用いて説明し、後半では対象(オブジェクト)をモデル化して設計するための考え方(UML)について説明する。

評価は、3つの課題と最終テストを各25%づつで評価を行う。

オブジェクト指向プログラミングの歴史

最初のプログラム言語のFortran(科学技術計算向け言語)の頃は、処理を記述するだけだったけど、 COBOL(商用計算向け言語)ができた頃には、データをひとまとめで扱う「構造体」(C言語ならstruct {…}の考えができた。(データの構造化)

// C言語の構造体
struct Person { // 1人分のデータ構造をPersonとする
   char name[ 20 ] ;             // 名前
   int  b_year, b_month, b_day ; // 誕生日
} ;

一方、初期のFortranでは、プログラムの処理順序は、繰り返し処理も if 文と goto 文で記載し、処理がわかりにくかった。その後のALGOLの頃には、処理をブロック化して扱うスタイル(C言語なら{ 文 … }の複文で 記述する方法ができてきた。(処理の構造化)

      // ブロックの考えがない時代の雰囲気をC言語で表すと
      int i = 0 ;
LOOP: if ( i >= 10 ) goto EXIT ;
         if ( i % 2 != 0 ) goto NEXT ;
            printf( "%d " , i ) ;
NEXT:    i++ ;
      goto LOOP ;   // 処理の範囲を字下げ(インデント)で強調
EXIT:
--------------------------------------------------- 
      // C 言語で書けば
      int i ;
      for( i = 0 ; i < 10 ; i++ ) {
         if ( i % 2 == 0 ) {
            printf( "%d¥n" , i ) ;
         }
      }
---------------------------------------------------
      ! 構造化文法のFORTRANで書くと
      integer i
      do i = 0 , 9
        if ( mod( i , 2 ) == 0 ) then
          print * , i
        end if
      end do

このデータの構造化・処理の構造化により、プログラムの分かりやすさは向上し、このデータと処理をブロック化した書き方は「構造化プログラミング(Structured Programming)」 と呼ばれる。

雑談

ここで紹介した、最古の高級言語 Fortran や COBOL は、今でも使われている。Fortran は、スーパーコンピュータなどで行われる数値シミュレーションでは、広く利用されている。また COBOL は、銀行などのシステムでもまだ使われている。しかしながら、新システムへの移行で COBOL を使えるプログラマーが定年を迎え減っていることから、移行トラブルが発生している。特に、CASEツール(UMLなどの図をベースにしたデータからプログラムを自動生成するツール)によって得られた COBOL のコードが移行を妨げる原因となることもある。

この後、様々なプログラム言語が開発され、C言語などもできてきた。 一方で、シミュレーションのプログラム開発(例simula)では、 シミュレーション対象(object)に対して、命令するスタイルの書き方が生まれ、 データに対して命令するという点で、擬人法のようなイメージで直感的にも分かりやすかった。 これがオブジェクト指向プログラミング(Object Oriented Programming)の始まりとなる。略記するときは OOP などと書くことが多い。

この考え方を導入した言語の1つが Smalltalk であり、この環境では、プログラムのエディタも Smalltalk で記述したりして、オブジェクト指向がGUIのプログラムと親和性が良いことから、この考え方は多くのプログラム言語へと取り入れられていく。

C言語にこのオブジェクト指向を取り入れ、C++が開発される。さらに、この文法をベースとした、 Javaなどが開発されている。最近の新しい言語では、どれもオブジェクト指向の考えが使われている。

この授業の中ではオブジェクト指向プログラミングにおける、隠蔽化, 派生と継承, 仮想関数 などの概念を説明する。

構造体の導入

C++でのオブジェクト指向は、C言語の構造体の表記がベースになっているので、まずは構造体の説明。詳細な配布資料を以下に示す。

// 構造体の宣言
struct Person {      // Personが構造体につけた名前
   char name[ 20 ] ; // 要素1
   int  phone ;      // 要素2
} ;                  // 構造体定義とデータ構造宣言を
                     // 別に書く時は「;」の書き忘れに注意
// 構造体変数の宣言
struct Person saitoh ;
struct Person data[ 10 ] ;
// 実際にデータを参照 構造体変数.要素名
strcpy( saitoh.name , "t-saitoh" ) ;
saitoh.phone = 272925 ;
for( int i = 0 ; i < 10 ; i++ ) {
   scanf( "%d%s" , data[ i ].name , &(data[ i ].phone) ) ;
}

構造体に慣れていない人のための課題

  • 以下に、C言語の構造体を使った基本的なプログラムを示す。このプログラムでは、国語,算数,理科の3科目と名前の5人分のデータより、各人の平均点を計算している。このプログラムを動かし、以下の機能を追加せよ。レポートには プログラムリストと動作結果の分かる結果を付けること。
    • 国語の最低点の人を探し、名前を表示する処理。
    • 算数の平均点を求める処理。
#include <stdio.h>

struct Student {
  char name[ 20 ] ;
  int  kokugo ;
  int  sansu ;
  int  rika ;
} ;

struct Student table[5] = {
  // name ,      kokugo , sansu , rika                                          
  { "Aoyama" ,   56 ,     95 ,    83 } ,
  { "Kondoh" ,   78 ,     80 ,    64 } ,
  { "Saitoh" ,   42 ,     78 ,    88 } ,
  { "Sakamoto" , 85 ,     90 ,    36 } ,
  { "Yamagosi" ,100 ,     72 ,    65 } ,
} ;

int main() {
  int i = 0 ;
  for( i = 0 ; i < 5 ; i++ ) {
    double sum = table[i].kokugo + table[i].sansu + table[i].rika ;
    printf( "%-10.10s %3d %3d %3d %6.2lf\n" ,
            table[i].name , table[i].kokugo , table[i].sansu , table[i].rika ,
            sum / 3.0 ) ;
  }
  return 0 ;
}

値渡し,ポインタ渡し,参照渡し

C言語をあまりやっていない学科の人向けのC言語の基礎として、関数との値渡し, ポインタ渡しについて説明する。ただし、参照渡しについては電子情報の授業でも細かく扱っていない内容なので電子情報系学生も要注意。

オブジェクト指向のプログラムでは、構造体のポインタ渡し(というよりは参照渡し)を多用するが、その基本となる関数との値の受け渡しの理解のため、以下に値渡し・ポインタ渡し・参照渡しについて説明する。

ポインタと引数

値渡し(Call by value)

// 値渡しのプログラム
void foo( int x ) {  // x は局所変数(仮引数は呼出時に
                     // 対応する実引数で初期化される。
   x++ ;
   printf( "%d¥n" , x ) ;
}
int main() {
   int a = 123 ;
   foo( a ) ;  // 124
               // 処理後も main::a は 123 のまま。
   foo( a ) ;  // 124
   return 0 ;
}

このプログラムでは、aの値は変化せずに、124,124 が表示される。ここで、関数 foo() を呼び出しても、関数に「値」が渡されるだけで、foo() を呼び出す際の実引数 a の値は変化しない。こういった関数に値だけを渡すメカニズムは「値渡し」と呼ぶ。

値渡しだけが使われれば、関数の処理後に変数に影響が残らない。こういった処理の影響が残らないことは一般的に「副作用がない」という。

大域変数を使ったプログラム

でも、プログラムによっては、124,125 と変化して欲しい場合もある。どのように記述すべきだろうか?

// 大域変数を使う場合
int x ;
void foo() {
   x++ ;
   printf( "%d¥n" , x ) ;
}
int main() {
   x = 123 ;
   foo() ;  // 124
   foo() ;  // 125
   return 0 ;
}

しかし、このプログラムは大域変数を使うために、間違いを引き起こしやすい。大域変数はどこでも使える変数であり、副作用が発生して間違ったプログラムを作る原因になりやすい。

// 大域変数が原因で予想外の挙動をしめす簡単な例
int i ;
void foo() {
   for( i = 0 ; i < 2 ; i++ )
      printf( "A" ) ;
}
int main() {
   for( i = 0 ; i < 3 ; i++ )  // このプログラムでは、AA AA AA と
      foo() ;                   // 表示されない。
   return 0 ;
}

ポインタ渡し(Call by pointer)

C言語で引数を通して、呼び出し側の値を変化して欲しい場合は、変更して欲しい変数のアドレスを渡し、関数側では、ポインタ変数を使って受け取った変数のアドレスの示す場所の値を操作する。(副作用の及ぶ範囲を限定する) こういった、値の受け渡し方法は「ポインタ渡し」と呼ぶ。

// ポインタ渡しのプログラム
void foo( int* p ) {  // p はポインタ
   (*p)++ ;
   printf( "%d¥n" , *p ) ;
}
int main() {
   int a = 123 ;
   foo( &a ) ;  // 124
                // 処理後 main::a は 124 に増えている。
   foo( &a ) ;  // 124
   return 0 ;   // さらに125と増える
}

ポインタを利用して引数に副作用を与える方法は、ポインタを正しく理解していないプログラマーでは、危険な操作となる。

参照渡し(Call by reference)

C++では、ポインタ渡しを極力使わないようにするために、参照渡しを利用する。ただし、ポインタ渡しも参照渡しも、機械語レベルでは同じ処理にすぎない。

// ポインタ渡しのプログラム
void foo( int& x ) {  // xは参照
   x++ ;
   printf( "%d¥n" , x ) ;
}
int main() {
   int a = 123 ;
   foo( a ) ;  // 124
               // 処理後 main::a は 124 に増えている。
   foo( a ) ;  // 124
   return 0 ;  // さらに125と増える。
}

大きなプログラムを作る場合、副作用のあるプログラムの書き方は、間違ったプログラムの原因となりやすい。そこで関数の呼び出しを中心としてプログラムを書くものとして、関数型プログラミングがある。

リスト構造について

データ処理において、配列は基本的データ構造だが、動的メモリ確保の説明で述べたように、基本の配列では大きさを変更することができない。これ以外にも、配列は途中にデータを挿入・削除を行う場合、の処理時間を伴う。以下にその問題点を整理し、その解決策であるリスト構造について説明する。

配列の利点と欠点

今までデータの保存には、配列を使ってきたが、配列は添字で場所を指定すれば、その場所のデータを簡単に取り出すことができる。配列には苦手な処理がある。例えば、配列の中から目的のデータを高速に探す方式として、2分探索法を用いる。

int find( int array[] , int left , int right , int key ) {
   // データは left から right-1までに入っているとする。
   while( left < right ) {
      int mid = (left + right) / 2 ; // 中央の場所
      if ( array[ mid ] == key )
         return mid ;                // 見つかった
      else if ( array[ mid ] > key )
         right = mid ;               // 左半分にある
      else
         left = mid + 1 ;            // 右半分にある
   }
   return -1 ; // 見つからない
}

しかし、配列の中に新たに要素を追加しようとするならば、データは昇順に並んでいる必要があることから、以下のようになるだろう。

void entry( int array[] , int* psize , int key ) {
   // データを入れるべき場所を探す処理
   for( int i = 0 ; i < *psize ; i++ ) // O(N) の処理だけど、
      if ( array[ i ] > key )          // O(log N) でも書けるけど
         break ;                       // 単純に記載する。
   if ( i < *psize ) {
      // 要素を1つ後ろにずらす処理
      for( int j = *psize ; j > i ; j-- ) //  O(N)の処理
         array[ j ] = array[ j - 1 ] ;
      array[ i ] = key ; 
   } else {
      array[ *psize ] = key ;
   }
   (*psize)++ ;
}

これで判るように、データを配列に追加する場合、途中にデータを入れる際にデータを後ろにずらす処理が発生する。

この例は、データを追加する場合であったが、不要となったデータを取り除く場合にも、データの場所の移動が必要である。

順序が重要なデータ列で途中へのデータ挿入削除

例えば、アパート入居者に回覧板を回すことを考える。この中で、入居者が増えたり・減ったりした場合、どうすれば良いか考える。
通常は、自分の所に回覧板が回ってきたら、次の入居者の部屋番号さえわかっていれば、回覧板を回すことができる。

  101   102   103   104   105   106
[ 105 | 106 |  -1 | 102 | 104 | 103 ]

このように次のデータの場所という概念を使うと、データの順序を持って扱うことができる。

struct LIST {
   int data ;
   int next ;
} ;
struct LIST array[] = {
   /*0*/ { 11 ,  2 } , 
   /*1*/ { 67 ,  3 } ,  // 末尾にデータ34を加える
   /*2*/ { 23 ,  4 } ,  // { 23 , 5 } ,
   /*3*/ { 89 , -1 } ,  // 末尾データの目印
   /*4*/ { 45 ,  1 } ,
   /*5*/ {  0 ,  0 } ,  // { 34 , 4 } ,
} ;
for( int idx = 0 ; idx >= 0 ; idx = array[ idx ].next ) {
   printf( "%d¥n" , array[ idx ].data ) ; 
}

この方法を取れば、途中にデータ入れたり、抜いたりする場合に、データの移動を伴わない。

しかし、配列をベースにしているため、配列の上限サイズを超えて格納することはできない。

リスト構造

リスト構造は、データと次のデータへのポインタで構成され、必要に応じてメモリを確保することで、配列の上限が制限にならないようにする。また、次のデータへのポインタでつなげているため、途中へのデータ挿入が簡単にできるようにする。

struct List {
   int          data ;
   struct List* next ;
} ;
struct List* top ;

top = (struct List*)malloc( sizeof( struct List ) ) ;
top->data = 111 ;
top->next = (struct List*)malloc( sizeof( struct List ) ) ;
top->next->data = 222 ;
top->next->next = (struct List*)malloc( sizeof( struct List ) ) ;
top->next->next->data = 333 ;
top->next->next->next = NULL ; // 末尾データの目印

struct List*p ;
for( p = top ; p != NULL ; p = p->next ) {
   printf( "%d¥n" , p->data ) ;
}

補助関数

上記のプログラムでは、(struct…)malloc(sizeof(…))を何度も記載し、プログラムが分かりにくいので、以下に示す補助関数を使うと、シンプルに記載できる。

struct List* cons( int x , struct List* n ) {
   struct List* ans ;
   ans = (struct List*)malloc( sizeof( struct List ) ) ;
   if ( ans != NULL ) {
      ans->data = x ;
      ans->next = n ;
   }
   return ans ;
}
struct List* top ;
top = cons( 111 , cons( 222 , cons( 333 , NULL ) ) ) ;

授業アンケートで板書の字が読みづらいといわれつつも、パッパッパッってコードを書いていると「その関数名読めない…」とツッコミが。cons : constructor の意味ですがな…と話しつつ、例年どおり「どーでもいいウンチク」を話す。

今日以降説明していくリスト構造は、古くから使われていて、LISP というプログラム言語があり、この言語でリスト(セル)を生成する関数が cons 。

LISPと関数型プログラミング言語

LISPの歴史は長く、最古のFORTRAN,COBOLに次ぐ3番目ぐらい。最初は、人工知能のプログラム開発のための関数型プログラミング言語として作られた。特徴として、データもプログラムもすべてリスト構造(S式)で表すことができ、プログラムは関数型に基づいて作られる。

関数型プログラミングは、Ruby や Python でも取り入れられている。関数型プログラミングは、処理を関数をベースに記述することで「副作用を最小限にすることができ」、極端な話をすればループも再帰呼出しで書けばいい…。

LISPの処理系は、最近では Scheme などが普通だが、プログラムエディタの Emacs は、内部処理が LISP で記述されている。

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー