ホーム » スタッフ » 斉藤徹 (ページ 34)

斉藤徹」カテゴリーアーカイブ

2025年6月
1234567
891011121314
15161718192021
22232425262728
2930  

検索・リンク

オブジェクト指向とソフトウェア工学

オブジェクト指向プログラミングの最後の総括として、 ソフトウェア工学との説明を行う。

トップダウン設計とウォーターフォール型開発

ソフトウェア工学でプログラムの開発において、一般的なサイクルとしては、 専攻科などではどこでも出てくるPDCAサイクル(Plan, Do, Check, Action)が行われる。 この時、プログラム開発の流れとして、大企業でのプログラム開発では一般的に、 トップダウン設計とウォーターフォール型開発が行われる。

トップダウン設計では、全体の設計(Plan)を受け、プログラムのコーディング(Do)を行い、 動作検証(Check)をうけ、最終的に利用者に納品し使ってもらう(Action)…の流れで開発が行われる。設計(Plan)の中身は、要件定義機能仕様動作仕様…といった細かなフェーズになることも多い。 この場合、コーディングの際に設計の不備が見つかり設計のやり直しが発生すれば、 全行程の遅延となることから、前段階では完璧な設計が必要となる。 このような、上位設計から下流工程にむけ設計する方法は、トップダウン設計などと呼ばれる。また、処理は前段階へのフィードバック無しで次工程へ流れ、 川の流れが下流に向かう状態にたとえ、ウォーターフォールモデルと呼ばれる。

引用:Think IT 第2回開発プロセスモデル

このウォーターフォールモデルに沿った開発では、横軸時間、縦軸工程とした ガントチャートなどを描きながら進捗管理が行われる。

引用:Wikipedia ガントチャート

V字モデル

一方、チェック工程(テスト工程)では、 要件定義を満たしているかチェックしたり、基本設計や詳細設計が仕様を満たすかといったチェックが存在し、テストの前工程とそれぞれ対応した機能のチェックが存在する。 その各工程に対応したテストを経て最終製品となる様は、V字モデルと呼ばれる。

引用:@IT Eclipseテストツール活用の基礎知識

しかし、ウォーターフォールモデルでは、(前段階の製作物の不備は修正されるが)前段階の設計の不備があっても前工程に戻るという考えをとらないため、全体のPDCAサイクルが終わって次のPDCAサイクルまで問題が残ってしまう。巨大プロジェクトで大量の人が動いているだから、簡単に方針が揺らいでもトラブルの元にしかならないことから、こういった手法は大人数巨大プロジェクトでのやり方である。

ボトムアップ設計とアジャイル開発

少人数でプログラムを作っている時(あるいはプロトタイプ的な開発)には、 部品となる部分を完成させ、それを組合せて全体像を組み上げる手法もとられる。 この方法は、ボトムアップ設計と呼ばれる。このような設計は場当たり的な開発となる場合があり設計の見直しも発生しやすい。

また、ウォーターフォールモデルでは、前工程の不備をタイムリーに見直すことができないが、 少人数開発では適宜前工程の見直しが可能となる。 特にオブジェクト指向プログラミングを実践して隠蔽化が正しく行われていれば、 オブジェクト指向によるライブラリの利用者への影響を最小にしながら、ライブラリの内部設計の見直しも可能となる。 このような外部からの見た挙動を変えることなく内部構造の改善を行うことリファクタリングと呼ばれる。

一方、プログラム開発で、ある程度の規模のプログラムを作る際、最終目標の全機能を実装したものを 目標に作っていると、全体像が見えずプログラマーの達成感も得られないことから、 機能の一部分だけ完成させ、次々と機能を実装し完成に近づける方式もとられる。 この方式では、機能の一部分の実装までが1つのPDCAサイクルとみなされ、 このPDCAサイクルを何度も回して機能を増やしながら完成形に近づける方式とも言える。 このような開発方式は、アジャイルソフトウェア開発と呼ぶ。 一つのPDCAサイクルは、アジャイル開発では反復(イテレーション)と呼ばれ、 短い開発単位を反復し製品を作っていく。この方法では、一度の反復後の実装を随時顧客に見てもらうことが可能であり、顧客とプログラマーが一体となって開発が進んでいく。

引用:コベルコシステム

エクストリームプログラミング

アジャイル開発を行うためのプログラミングスタイルとして、 エクストリームプログラミング(Xp)という考え方も提唱されている。 Xpでは、5つの価値(コミュニケーション,シンプル,フィードバック,勇気,尊重)を基本とし、 開発のためのプラクティス(習慣,実践)として、 テスト駆動開発(コーディングでは最初に機能をテストするためのプログラムを書き、そのテストが通るようにプログラムを書くことで,こまめにテストしながら開発を行う)や、 ペアプログラミング(2人ペアで開発し、コーディングを行う人とそのチェックを行う人で役割分担をし、 一定期間毎にその役割を交代する)などの方式が取られることが多い。

リーン・ソフトウェア開発は、トヨタ生産方式を一般化したリーン生産方式をソフトウェア開発に導入したもの。ソフトウェアでよく言われる話として「完成した機能の64%は使われていない」という分析がある。これでは、開発に要する人件費の無駄遣いとみることもできる。そこで、品質の良いものを作る中で無駄の排除を目的とし、本当にその機能は必要かを疑いながら、優先順位をつけ実装し、その実装が使われているのか・有効に機能しているのかを評価ながら開発をすすことが重要であり、リーン生産方式がソフトウェア開発にも取り込まれていった。

伽藍(がらん)とバザール

これは、通常のソフトウェア開発の理論とは異なるが、重要な開発手法の概念なので「伽藍とバザール」を紹介する。

伽藍(がらん)とは、優美で壮大な寺院のことであり、その設計・開発は、優れた設計・優れた技術者により作られた完璧な実装を意味している。バザールは有象無象の人の集まりの中で作られていくものを意味している。

たとえば、伽藍方式の代表格である Microsoft の製品は、優秀なプロダクトだが、中身の設計情報などを普通の人は見ることはできない。このため潜在的なバグが見つかりにくいと言われている。

これに対しバザール方式の代表格の Linux は、インターネット上にソースコードが公開され、誰もがソースコードに触れプログラムを改良してもいい(オープンソース)。その中で、新しい便利な機能を追加しインターネットに公開されれば、良いコードは生き残り、悪いコードは自然淘汰されていく。

このオープンソースを支えているツールとしては、プログラムの変更履歴やバージョン管理を行う分散型バージョン管理システム git が有名であり、Linux のソフトウェア管理などで広く利用されている。。

オープンソースライセンス

バザール方式は、オープンソースライセンスにより成り立っていて、このライセンスが適用されていれば、改良した機能はインターネットに公開する義務を引き継ぐ。このライセンスの代表格が、GNU パブリックライセンス(GPL)であり、公開の義務の範囲により、BSD ライセンスApacheライセンスといった違いがある。

コピーレフト型 GNU ライセンス(GPL) 改変したソースコードは公開義務,
組み合わせて利用で対応箇所の開示。
準コピーレフト型 LGPL, Mozilla Public License 改変したソースコードは公開義務。
非コピーレフト型 BSDライセンス, Apacheライセンス ソースコードを改変しても公開しなくてもいい。

GPLライセンスのソフトウェアを組み込んで製品を開発した場合に、ソースコード開示を行わないとGPL違反となる。大企業でこういったGPL違反が発生すると、大きな風評被害による損害をもたらす場合がある

スタックと待ち行列

前回の授業では、リストの先頭にデータを挿入する処理と、末尾に追加する処理について説明したが、この応用について説明する。

計算処理中に一時的なデータの保存として、スタック(stack)待ち行列・キュー(queue)がよく利用される。それを配列を使って記述したり、任意の大きさにできるリストを用いて記述することを示す。

スタック

配列を用いたスタック

一時的な値の記憶によく利用されるスタック(stack)は、データの覚え方の特徴からLIFO( Last In First out )とも呼ばれる。配列を使って記述すると以下のようになるであろう。

#define STACK_SIZE 32
int stack[ STACK_SIZE ] ;
int sp = 0 ;

void push( int x ) { // データをスタックの一番上に積む
    stack[ sp++ ] = x ;
}
int pop() { // スタックの一番うえのデータを取り出す
    return stack[ --sp ] ;
}
void main() {
    push( 1 ) ; push( 2 ) ; push( 3 ) ;
    printf( "%d\n" , pop() ) ; // 3
    printf( "%d\n" , pop() ) ; // 2
    printf( "%d\n" , pop() ) ; // 1
}

++,–の前置型と後置型の違い

// 後置インクリメント演算子
int i = 100 ;
printf( "%d" , i++ ) ;
// これは、
printf( "%d" , i ) ;
i++ ;
// と同じ。100が表示された後、101になる。

// 前置インクリメント演算子
int i = 100 ;
printf( "%d" , ++i ) ;
//   これは、
i++ ;
printf( "%d" , i ) ;
// と同じ。101になった後、101を表示。

リスト構造を用いたスタック

しかし、この中にSTACK_SIZE以上のデータは貯えられない。同じ処理をリストを使って記述すれば、配列サイズの上限を気にすることなく使うことができるだろう。では、リスト構造を使ってスタックの処理を記述してみる。

struct List* stack = NULL ;

void push( int x ) { // リスト先頭に挿入
    stack = cons( x , stack ) ;
}
int pop() { // リスト先頭を取り出す
    int ans = stack->data ;
    struct List* d = stack ;
    stack = stack->next ;      // データ 0 件で pop() した場合のエラー対策は省略
    free( d ) ;
    return ans ;
}

キュー(QUEUE)

2つの処理の間でデータを受け渡す際に、その間に入って一時的にデータを蓄えるためには、待ち行列(キュー:queue)がよく利用される。 データの覚え方の特徴からFIFO(First In First Out)とも呼ばれる。

配列を用いたQUEUE / リングバッファ

配列にデータを入れる場所(wp)と取り出す場所のポインタ(rp)を使って蓄えれば良いが、配列サイズを超えることができないので、データを取り出したあとの場所を循環して用いるリングバッファは以下のようなコードで示される。

#define QUEUE_SIZE 32
int queue[ QUEUE_SIZE ] ;
int wp = 0 ; // write pointer(書き込み用)
int rp = 0 ; // read  pointer(読み出し用)

void put( int x ) { // 書き込んで後ろ(次)に移動
    queue[ wp++ ] = x ;
    if ( wp >= QUEUE_SIZE )  // 末尾なら先頭に戻る
        wp = 0 ;
}
int get() { // 読み出して後ろ(次)に移動
    int ans = queue[ rp++ ] ;
    if ( rp >= QUEUE_SIZE )  // 末尾なら先頭に戻る
        rp = 0 ;
    return ans ;
}
void main() {
    put( 1 ) ; put( 2 ) ; put( 3 ) ;
    printf( "%d\n" , get() ) ; // 1
    printf( "%d\n" , get() ) ; // 2
    printf( "%d\n" , get() ) ; // 3
}

このようなデータ構造も、get() の実行が滞るようであれば、wp が rp に循環して追いついてしまう。このため、上記コードはまだエラー対策としては不十分である。どのようにすべきか?

リスト構造を用いたQUEUE

前述のリングバッファもget()しないまま、配列上限を越えてput()を続けることはできない。

この配列サイズの上限問題を解決したいのであれば、リスト構造を使って解決することもできる。この場合のプログラムは、以下のようになるだろう。

struct List* queue = NULL ;
struct List** tail = &queue ;

void put( int x ) { // リスト末尾に追加
    *tail = cons( x , NULL ) ;
    tail = &( (*tail)->next ) ;
}
int get() { // リスト先頭から取り出す
    int ans = queue->data ;
    struct List* d = queue ;
    queue = queue->next ;
    free( d ) ;
    return ans ;
}

ただし、上記のプログラムは、データ格納後にget()で全データを取り出してしまうと、tail ポインタが正しい位置になっていないため、おかしな状態になってしまう。
また、このプログラムでは、rp,wp の2つのポインタで管理することになるが、 2重管理を防ぐために、リストの先頭と末尾を1つのセルで管理する循環リストが使われることが多い。

理解確認

  • 配列を用いたスタック・待ち行列は、どのような処理か?図などを用いて説明せよ。
  • リスト構造を用いたスタック・待ち行列について、図などを用いて説明せよ。
  • スタックや待ち行列を、配列でなくリスト構造を用いることで、どういう利点があるか?欠点があるか説明せよ。

シェルスクリプトの演習

今回は、前回までのシェルの機能を使って演習を行う。

プログラムの編集について

演習用のサーバに接続して、シェルスクリプトなどのプログラムを作成する際のプログラムの編集方法にはいくつかの方式がある。

  • サーバに接続しているターミナルで編集
    • nano , vim , emacs などのエディタで編集
  • パソコンで編集してアップロード
    • scp 命令で編集したファイルをアップロード
  • パソコンのエディタのリモートファイルの編集プラグインで編集
    • VSCode の remote-ssh プラグインを使うのが簡単だけど、サーバ側の負担が大きいので今回は NG

リモート接続してエディタで編集

今回の説明では、emacs で編集する方法を説明する。

((( Emacs を起動 )))
guest00@nitfcei.mydns.jp:~$ emacs helloworld.sh

エディタが起動すると、以下のような画面となる。

scpでファイルをアップロード

scpコマンドは、ssh のプロトコルを使ってネットワークの先のコンピュータとファイルのコピーを行う。前述の emacs などのエディタが使いにくいのなら scp を使えばいい。

((( scp 命令の使い方 )))
$ scp ユーザ名@ホスト名:ファイルの場所 

((( サーバの helloworld.sh をダウンロード )))
C:\Users\t-saitoh> scp -P 443 guest00@nitfcei.mydns.jp:helloworld.sh .
C:\Users\t-saitoh> scp -P 443 guest00@nitfcei.mydns.jp:/home0/Challenge/3-shellscript/helloworld.sh .
((( パソコンの hoge.sh をアップロード )))
C:\Users\t-saitoh> scp -P 443 hoge.sh guest00@nitfcei.mydns.jp:
((( パソコンの hoge.html を public_html にアップロード ))) 
C:\Users\t-saitoh> scp -P 443 hoge.html guest00@nitfcei.mydns.jp:public_html

シェルスクリプトの命令

条件式の書き方

シェルには、test コマンド( [ コマンド ) で条件判定を行う。動作の例として、テストコマンドの結果を コマンドの成功/失敗 を表す $? を使って例示する。

guest00@nitfcei:~$ [ -f helloworld.sh ] ; echo $?    # [ -f ファイル名 ]
0                                                    # ファイルがあれば0/なければ1
guest00@nitfcei:~$ [ -x /bin/bash ]; echo $?         # [ -x ファイル名 ]
0                                                    # ファイルが存在して実行可能なら0/だめなら1
guest00@nitfcei:~$ [ -d /opt/local/bin ] ; echo $?   # [ -d ディレクトリ名 ]
1                                                    # ディレクトリがあれば0/なければ1
guest00@nitfcei:~$ [ "$PATH" = "/bin:/usr/bin" ] ; echo $?   # [ "$変数" = "文字列" ]
1                                                    # $変数が"文字列"と同じなら0/違えば1

シェルの制御構文

((( シェルの if 文 )))
if [ -f helloworld.sh ]; then
   echo "exist - helloworld.sh"
elif [ -f average.c ]; then
   echo "exist - average.c"
else
   echo "みつからない"
fi
((( シェルの for 文 )))
for user in /home0/guests/*   # ワイルドカード文字 * があるので、/home0/guests/ のファイル一覧
do                            # が取り出されて、その1つづつが、$user に代入されながら繰り返し。
    echo $user
done
---
結果: /home0/guests/guest00, /home0/guests/guest01 ... 
((( while 文 )))
/bin/grep ^guest < /etc/passwd \    # passwd ファイルでguestで始まる行を抜き出し、
| while read user                   # read コマンドで その 行データを $user に代入しながらループ
  do
      echo $user
  done

シェル演習向けのコマンド一例

`コマンド`と$(コマンド)

((( コマンドの結果を使う )))
guest00@nitfcei:~$ ans=`whoami`     # whoami コマンドの結果を ans に代入
guest00@nitfcei:~$ echo $ans        # バッククオートに注意 ' シングルクオート " ダブルクオート ` バッククオート
guest00
guest00@nitfcei:~$ ans=$(pwd)       # pwd コマンドの結果を ans に代入
guest00@nitfcei:~$ echo $ans        # 最近は、$(コマンド) の方が良く使われている
/home0/guest00

コマンドライン引数

シェルの中でコマンドライン引数を参照する場合には、”$数字“, “$@” を使う。$1 , $2 で最初のコマンドライン引数, 2番目のコマンドライン引数を参照できる。すべてのコマンドライン引数を参照する場合には、$@ を使う。

((( argv.sh : コマンドライン引数を表示 )))
#!/bin/bash
echo "$@"
for argv in "$@"
do
    echo "$argv"
done
((( argv.sh を実行 )))
guest00@nitfcei:~$ chmod 755 argv.sh
guest00@nitfcei:~$ ./argv.sh abc 111 def
abc 111 def          # echo "$@" の結果
abc                  # for argv ... の結果
111
def

cutコマンドとawkコマンド

((( 行の特定部分を抜き出す )))
guest00@nitfcei:~$ cut -d: -f 1 /etc/passwd   # -d:  フィールドの区切り文字を : で切り抜き
root                                          # -f 1 第1フィールドだけを出力
daemon
adm
:
guest00@nitfcei:~$ awk -F: '{print $1}' /etc/passwd  # -F: フィールド区切り文字を : で切り分け
root                                                 # ''
daemon
adm
:

lastコマンド

((( ログイン履歴を確認 )))
guest00@nitfcei:~$ last
t-saitoh pts/1        64.33.3.150      Thu Jul  7 12:32   still logged in
最近のログインした名前とIPアドレスの一覧
:
((( guest* がログインした履歴 )))
guest00@nitfcei:~$ last | grep guest
guest15  pts/11       192.156.145.1    Tue Jul  5 16:00 - 16:21  (00:21)
:
((( 7/5にログインしたguestで、名前だけを取り出し、並び替えて、重複削除 )))
guest00@nitfcei:~$ last | grep guest | grep "Jul  5" | awk '{print $1}' | sort | uniq
7/5("Jul  5")の授業で演習に参加していた学生さんの一覧が取り出せる。
### あれ、かなりの抜けがあるな!?!? ###

whoisコマンド

((( IPアドレスなどの情報を調べる )))
guest00@nitfcei:~$ whois 192.156.145.1
:
inetnum:        192.156.145.0 - 192.156.148.255
netname:        FUKUI-NCT
country:        JP
:
guest00@nitfcei:~$ whois 192.156.145.1 | grep netname:
netname:   FUKUI-NCT
netname:   ANCT-CIDR-BLK-JP

シェルスクリプトのセキュリティ

ここまでのプログラムの動作例では、a.out などのプログラムを実行する際には、先頭に “./” をつけて起動(./a.out)している。これは「このフォルダ(“./“)にある a.out を実行せよ」との意味となる。

いちいち、カレントフォルダ(“./”)を先頭に付けるのが面倒であっても、環境変数 PATH を “export PATH=.:/bin:/usr/bin” などと設定してはいけない。こういった PATH にすれば、”a.out” と打つだけでプログラムを実行できる。しかし、”ls” といったファイル名のプログラムを保存しておき、そのフォルダの内容を確認しようとした他の人が “ls” と打つと、そのフォルダの中身を実行してしまう。

guest00@nitfcei:~$ export PATH=".:/bin:/bin/bash"
guest00@nitfcei:~$ cat /home0/Challenge/1-CTF.d/Task5/Bomb/ls
#!/bin/bash

killall -KILL bash
guest00@nitfcei:~$ cd /home0/Challenge/1-CTF.d/Task5/Bomb
guest00@nitfcei:~$ ls
# 接続が切れる(bashが強制停止となったため)

こういったシェルスクリプトでのセキュリティのトラブルを防ぐために、

  • 環境変数PATHに、カレントフォルダ”./”を入れない
  • シェルスクリプトで外部コマンドを記述する際には、コマンドのPATHをすべて記載する。
    コマンドのPATHは、which コマンドで確認できる。echo とか [ といったコマンドは、bash の組み込み機能なので、コマンドのPATHは書かなくていい。

演習問題

シェルスクリプトの練習として、以下の条件を満たすものを作成し、スクリプトの内容の説明, 機能, 実行結果, 考察を記載したワードファイル(or PDF)等で、こちらのフォルダに提出してください。

  • スクリプトとして起動して結果が表示されること。(シバン,実行権限)
  • コマンドライン引数を使っていること。
  • 入出力リダイレクトやパイプなどを使っていること。
  • 以下の例を参考に。
((( 第1コマンドライン引数指定したユーザが、福井高専からアクセスした履歴を出力する。)))
#!/bin/bash

if [ -x /usr/bin/last -a -x /bin/grep ]; then   # [ ... -a ... ] は、複数条件のAND
    /usr/bin/last "$1" | /bin/grep 192.156.14
fi
-------------------------------------------------------------------------
((( guest グループで、$HOME/helloworld.sh のファイルの有無をチェック )))
#!/bin/bash

for dir in /home0/guests/*
do
   if [ -f "$dir/helloworld.sh" ]; then      # PATHの最後の部分を取り出す
      echo "$(/usr/bin/basename $dir)"       # $ basename /home0/guests/guest00
   fi                                        # guest00                  ~~~~~~~basename
done

UMLと振る舞い図

前回の講義で説明した構造図に続いて、処理の流れを説明するための振る舞い図の説明。

講義の後半は、UML作成のレポートの課題時間とする。

振る舞い図

参考資料をもとに振る舞い図の説明を行う。

ユースケース図

1507131131_211x192.png

ユーザなど外部からの要求に対する、システムの振る舞いを表現するための活用事例や機能を表す図がユースケース図。 システムを構築する際に、最初に記述するUMLであり、システムに対する処理要件の全体像や機能を理解するために記述する。 ユーザや外部のシステムは、アクターとよび人形の絵で示す。楕円でシステムに対する具体的な処理をユースケースとして楕円で記述する。 関連する複数のユースケースをまとめて、サブジェクトとして示す場合もある。

アクティビティ図

処理順序を記述するための図にはフローチャートがあるが、上から下に処理順序を記述するため、縦長の図になりやすい。また、四角枠の中に複雑なことを書けないので、UMLではアクティビティ図を用いる。

初期状態●から、終了状態◉までの手順を示すためのものがアクティビティ図。 フローチャートに無い表現として、複数の処理を並行処理する場合には、フォークノードで複数の処理を併記し、最終的に1つの処理になる部分をマージノードで示す。 通常の処理は、角丸の長方形で示し、条件分岐はひし形で示す。

ステートチャート図(状態遷移図)

ステートチャート図は、処理内部での状態遷移を示すための図。 1つの状態を長丸長方形で示し、初期状態●から終了状態◉までを結ぶ。 1つの状態から、なんらかの状態で他の状態に遷移する場合は、分岐条件となる契機(タイミング)とその条件、およびその効果(出力)を「契機[条件]/効果」で矢印に併記する。 複数の状態をグループ化して表す場合もある。

シーケンス図

複数のオブジェクトが相互にやり取りをしながら処理が進むようなもののタイミングを記述するためのものがシーケンス図。 上部の長方形にクラス/オブジェクトを示し、その下に縦軸にて時系列の処理の流れの線(Life Line)を描く。 オブジェクトがアクティブな状態は、縦長の長方形で示し、そのLife Line間を、やり取り(メッセージ)の線で相互に結ぶ。 メッセージは、相手側からの返答を待つような同期メッセージは、黒塗り三角矢印で示す。 返答を待たない非同期メッセージは矢印で示し、返答は破線で示す。

コミュニケーション図

クラスやオブジェクトの間の処理とその応答(相互作用)と関連の両方を表現する図。

応答を待つ同期メッセージは -▶︎、非同期メッセージは→で表す。複数のオブジェクト間のやりとりの相互作用を表現する。

タイミング図

タイミング図は、クラスやオブジェクトの時間と共に状態がどのように遷移するのかを表現する図。

状態変化の発生するタイミングや、時間的な遅れや時間的な制約を図で明記するために使われる。

IT専科・UML入門より引用

リストへの追加処理

最初のリスト生成の説明では、補助関数 cons を用いて、直接リストを生成していた。
しかし、実際にはデータを入力しながらの処理となるであろう。今回は、前回のリスト操作のプログラムの確認などと合わせ、リストへのデータの追加処理について説明する。

ループによるリスト操作・再帰によるリスト操作

ループによるリスト操作のプログラム例を以下に示す。

// リストの全要素を出力
void print( struct List* p ) {
   for( ; p != NULL ; p = p->next )
      printf( "%d " , p->data ) ;
   printf( "¥n" ) ;
}
// リストの件数を返す
int count( struct List* p ) {
   int c = 0 ;
   for( ; p != NULL ; p = p->next )
      c++ ;
   return c ;
}
// リストの合計を返す
int sum( struct List* p ) {
   int s = 0 ;
   for( ; p != NULL ; p = p->next )
      s += p->data ;
   return s ;
}
// リストの最大値を返す
int max( struct List* p ) {
   if ( p == NULL ) {
      return 0 ;
   } else {
      int m = p->data ;
      for( p = p->next ; p != NULL ; p = p->next )
         if ( p->data > m )
            m = p->data ;
      return m ;
   }
}
// リストの中から指定したkeyが含まれるか探す
int find( struct List* p , int key ) {
   // 要素を見つけたら 1 、見つからなかったら 0 を返す
   for( ; p != NULL ; p = p->next )
      if ( p->data == key )
         return 1 ;
   return 0 ;
}

同じプログラムを再帰呼び出しで書いた場合。

// リストの全要素を再帰処理で出力
void print( struct List* p ) {
   if ( p == NULL ) {
      printf( "¥n" ) ;
   } else {
      printf( "%d " , p->data ) ;
      print( p->next ) ;
   }
}
// リストの件数を再帰処理でカウント
int count( struct List* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return 1 + count( p->next ) ;
}
// リストの合計を再帰処理で求める
int sum( struct List* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return p->data + sum( p->next ) ;
}
// リストの最大値を再帰処理で求める
int max( struct List* p ) {
   if ( p == NULL ) {
      return 0 ;
   } else {
      int tm = p->data ;
      int rm = max( p->next ) ;
      return tm > rm ? tm : rm ;          // if ( tm > rm )
   }                                      //    return tm ;
}                                         // else
                                          //    return rm ;
// リストの中から指定した値 key を再帰処理で探す
int find( struct List* p , int key ) {
   if ( p == NULL )
      return 0 ; // 見つからなかった
   else if ( p->data == key )
      return 1 ; // 見つかった
   else
      return find( p->next , key ) ;
}

最も単純なリスト先頭への挿入

リスト構造を使うと、必要に応じてメモリを確保しながらデータをつなげることができるので、配列のように最初に最大データ件数を想定した入れ物を最初に作って保存するような処理をしなくて済む。

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

// 保存するリストの先頭
struct List* top = NULL ;

void print( struct List* p ) {
   for( ; p != NULL ;  p = p->next )
      //  ~~~~~~~~~(A)     ~~~~~~~(B)
      printf( "%d " ,  p->data ) ;
           // ~~~~~(C) ~~~~~~~(D)
   printf( "¥n" ) ;
}//~~~~~~~~~~~~~~(E)
int main() {
   int x ;
   while( scanf( "%d" , &x ) == 1 ) {
      //  ~~~~~~~~~~~~~~~~~~(F)
      top = cons( x , top ) ;
   }     // ~~~~~~~~~~~~~~~(G)
   print( top ) ; // 前回示したリスト全要素表示
// ~~~~~~~~~~~~(H)
   return 0 ; // (生成したリストの廃棄処理は省略)
}
// (1) 入力で、11 , 22 を与えるとどうなる? - 下図参照
// (2) 練習問題(A)~(H)の型は?
// (3) 入力で、11,22 の後に 33 を与えるとどうなる?

ここで示したコードは、新しい要素を先頭に挿入していく処理となる。このため、作られたリストは、与えられた要素順とは逆順となる。この方法は、リストを管理するポインタが1つで分かりやすい

授業では、C言語のプログラムを示しているが、C++を使うと LIST 処理もシンプルに記述できるようになっている。参考資料として、C++で同様の処理を示す。テンプレートを使ったコンテナクラスを使うと、struct List {…} といった記述は不要で、std::forward_list<int> という型を使うだけで書けてしまう。

// C++ コンテナクラスで書くと...(auto を使うには C++11 以上)
#include <iostream>
#include <forward_list>
#include <algorithm>
int main() {
   std::forward_list<int> top ;
   int x ;
   while( std::cin >> x )
      top.push_front( x ) ;
   for( auto i = top.cbegin() ; i != top.cend() ; ++i )
      std::cout << *i << std::endl ;
   return 0 ;
}

要素を末尾に追加して追加順序で保存

前に示した方法は、逆順になるので、追加要素が常に末尾に追加される方法を示す。

struct List* top = NULL ;
struct List** tail = &top ;

int main() {
   int x ;
   while( scanf( "%d" , &x ) == 1 ) {
      //  ~~~~~~~~~~~~~~~~~~~~~~~(A)
      *tail = cons( x , NULL ) ;
      tail = &((*tail)->next) ;
   }//~~~~~~~~~~~~~~~~~~~~~~~(B) 下記の解説参照
   print( top ) ; // 前回示したリスト全要素表示
// ~~~~~~~~~~~~(C)
   return 0 ;  // (生成したリストの廃棄処理は省略)  
}
// (1) 入力で 11,22 を与えるとどうなる? - 下図参照 
// (2) 練習問題(A),(C)の型は?
// (3) 11,22の後に、さらに 33 を与えるとどうなる?

この方法は、次回にデータを追加する場所(末尾の目印のNULLが入っているデータの場所)を覚える方式である。ただし、リストへのポインタのポインタを使う方法なので、少しプログラムがわかりづらいかもしれない。

理解の確認のために、末尾のポインタを動かす部分の式を、型で解説すると以下のようになる。

途中でデータ挿入・データ削除

リスト構造の特徴は、途中にデータを入れたり、途中のデータを抜くのが簡単にできる所。そのプログラムは以下のようになるだろう。

// 指定した途中の場所に要素を挿入
void insert( struct List*p , int data ) {
   // p    は要素を入れる前のポインタ
   // data は追加する要素
   //      あえて、補助関数consを使わずに書いてみる
   struct List* n ;
   n = (struct List*)malloc( sizeof( struct List ) ) ;
   //  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(A)
   if ( n != NULL ) {
      n->data = data ;
      //        ~~~~(B)
      n->next = p->next ;
      //        ~~~~~~~(C)
      p->next = n ;
   }
   // consを使って書けば、簡単
   //  p->next = cons( data , p->next ) ;
}

int main() {
   struct List* top = cons( 11 , cons( 22 , cons( 44 , NULL ) ) ) ;
   //                                      ↑
   insert( top->next , 33 ) ;           // ここに33を挿入したい

   return 0 ;  // (生成したリストの廃棄処理は省略)
}

// 指定した場所のデータを消す
void remove_after( struct List* p ) {
   struct List* del = p->next ;
   p->next = del->next ;
   free( del ) ;
}

int main() {
   struct List* top = cons( 11 , cons( 22 , cons( 33 , cons( 44 , NULL ) ) ) ) ;
   remove_after( top->next ) ;                //  ↑
                                              // これを消したい
   return 0 ;  // リストの廃棄処理は省略)
}

理解度確認

上記プログラムinsert() の中の、下線部(A),(B),(C)の型は何か答えよ。

レポート課題

以下に示すようなデータを扱うリスト構造を作り、そのリストを扱うプログラムを作成せよ。
( 出席番号 % 3 ) の番号の課題に取り組むこと。

  1. 緯度(latitude)経度(longitude)とその場所の都市名(city)
  2. 名前(name)と誕生日(month,day)(1つの変数に2月7日を0207のように保存するのは禁止)
  3. 複素数(re,im)

このようなプログラムを作るのであれば、以下の例を参考に。

struct NameAgeList {
   char                name[ 20 ] ; // 名前
   int                 age ;        // 年齢
   struct NameAgeList* next ;       // 次のデータへのポインタ
} ;
struct NameAgeList* na_cons( char* nm, int ag,
                             struct NameAgeList*p )
{  struct NameAgeList* ans ;
   ans = (struct NameAgeList*)malloc(
               sizeof( struct NameAgeList ) ) ;
   if ( ans != NULL ) {
      strcpy( ans->name , nm ) ;
      ans->age  = ag ;
      ans->next = p ;
   }
   return ans ;
}

int main() {
   struct NameAgeList* top = NULL ;
   struct NameAgeList* p ;
   char buff[ 1024 ] ;
   // 1行読み込みの繰り返し
   while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
      char nm[ 100 ] ;
      int ag ;
      // 1行の中から名前と年齢があったら na_cons で挿入保存
      if ( sscanf( buff , "%s%d" , nm , &ag ) == 2 ) {
         top = na_cons( nm , ag , top ) ;
      }     
   }
   // 読み込んだデータを全部出力
   for( p = top ; p != NULL ; p = p->next )
      printf( "%s %d¥n" , p->name , p->age ) ;
   return 0 ;  // リストの廃棄処理は省略)
}

シェルスクリプト

前回の授業では、OSでのリダイレクト・パイプの概念とプロセスの概念について説明を行ってきた。これによりプログラムの実行結果を他のプログラムに渡すことができる。これらの機能を使うと、いくつかのプログラムを次々と実行させるなどの自動化をしたくなってくる。そこで、今回の授業では、OSとプログラムの間の情報を伝え合う基本機能の説明や、プログラムの起動をスクリプトとしてプログラム化するためのシェルスクリプト(shell script)について説明する。

環境変数

OSを利用していると、その利用者に応じた設定などを行いたい場合が多い。このような情報を管理する場合には、環境変数が使われる。環境変数はプロセス毎に管理され、プロセスが新しく子供のプロセス(子プロセス)を生成すると、環境変数は子プロセスに自動的に引き渡される。代表的な環境変数を以下に示す。

  • HOME – ユーザがログインした際の起点となるディレクトリであり、/home/ユーザ名 となっているのが一般的。
    シェルの中では”~” で代用できる。( “cd ~” で、最初のディレクトリに戻る )
  • LC_ALL, LANG – ユーザが使う言語。OSからのメッセージなどを日本語で表示したい場合には、ja_JP.UTF-8 などを指定。
  • TZ – ユーザの時差の情報(Time Zone) 日本であれば、”JST-9″ を設定するのが一般的。
    日本標準時 “JST” で、グリニッジ標準時(GMT)との時差を表す “-9” の組み合わせ。
  • PATH – ユーザがよく使うコマンドの保存されているディレクトリの一覧。/bin:/usr/bin の様にディレクトリ名を”:”区切りで書き並べる。
  • LD_LIBRARY_PATH – 共有ライブラリの保存されているディレクトリの一覧。

環境変数と同じように、シェルの中で使われるものはシェル変数と呼ぶ。この変数は、子プロセスに引き渡されない。

環境変数を表示するには、env コマンド(環境変数を表示)や、set コマンド(環境変数やシェル変数を表示)を用いる。シェルの中で特定の環境変数を参照する場合には、$変数名 とする。echo コマンドで PATH を表示するなら、”echo $PATH” とすればいい。

guest00@nitfcei:~$ env
SHELL=/bin/bash
:
guest00@nitfcei:~$ echo $PATH
/bin:/usr/bin:/usr/local/bin

変数に値を設定する場合には、“変数名=値” の様に設定する。この変数を環境変数にするには、export コマンドを用いるか、“export 変数名=値” を用いる。

((( 環境変数の設定 )))
guest00@nitfcei:~$ PATH=/bin:/usr/bin
guest00@nitfcei:~$ echo $PATH
guest00@nitfcei:~$ export PATH
guest00@nitfcei:~$ export PATH=/bin:/usr/bin:/usr/local/bin

((( PATHの確認 )))
guest00@nitfcei:~$ which zsh       # which はコマンドの場所を探してくれる
/bin/zsh
guest00@nitfcei:~$ export PATH=/usr/local/bin:/usr/bin:/bin
guest00@nitfcei:~$ which zsh
/usr/bin/zsh

((( LC_ALL,LANG の確認 )))
guest00@nitfcei:~$ export LC_ALL=C
guest00@nitfcei:~$ man man
(英語でマニュアルが表示される)
guest00@nitfcei:~$ export LC_ALL=ja_JP.UTF-8
guest00@nitfcei:~$ man man
(日本語でマニュアルが表示される)

((( TZタイムゾーンの確認 )))
guest00@nitfcei:~$ export TZ=GMT-0
guest00@nitfcei:~$ date
2022年 7月 4日 月曜日 05:23:23 GMT       # イギリスの時間(GMT=グリニッジ標準時間)が表示された
guest00@nitfcei:~$ export TZ=JST-9
guest00@nitfcei:~$ date                 # 日本時間(JST=日本標準時間)で表示された
2022年 7月 4日 月曜日 14:23:32 JST
guest00@nitfcei:~$ TZ=GMT-0 date ; date # 環境変数を一時的に変更して date を実行
2022年 7月 4日 月曜日 05:23:23 GMT
2022年 7月 4日 月曜日 14:23:32 JST

プログラムとコマンドライン引数と環境変数

この後に説明するシェルスクリプトなどの機能を用いる場合は、自分のプログラムとのデータのやり取りにコマンドライン引数と環境変数を使う。また、プログラムの実行に失敗した時に別の処理を実行するためには、main関数の返り値を使うことができる。

コマンドライン引数

コマンドライン引数は、プログラムを起動する時の引数として書かれている情報であり、C言語でこの情報を用いる時には、main関数の引数”int main( int argc , char** argv ) …” により値をもらうことができ、以下のようなプログラムを記述することで受け取ることができる。

((( argv.c )))
#include <stdio.h>

int main( int argc , char** argv ) {
    for( int i = 0 ; i < argc ; i++ ) {
        printf( "argv[%d] = %s\n" , i , argv[ i ] ) ;
    }
    return 0 ;
}
((( argv.c を実行してみる )))
guest00@nitfcei:~$ cp /home0/Challenge/3-shellscript/argv.c .
guest00@nitfcei:~$ gcc argv.c
guest00@nitfcei:~$ ./a.out 111 aaa 234 bcdef
argv[0] = ./a.out
argv[1] = 111
argv[2] = aaa
argv[3] = 234
argv[4] = bcdef

注意点:コマンドライン引数の0番目には、プロセスを起動した時のプロセス名が入る。

環境変数の参照

C言語のmain関数は、コマンドライン引数のほかに環境変数も参照することができる。envpの情報は、getenv関数でも参照できる。

((( argvenvp.c )))
#include <stdio.h>
int main( int argc , char** argv , char** envp ) {
    // コマンドライン引数argc,argvの処理
    for( int i = 0 ; i < argc ; i++ ) {
        printf( "argv[%d] = %s\n" , i , argv[ i ] ) ;
    }
    // 環境変数envpの処理
    for( int i = 0 ; envp[i] != NULL ; i++ ) {
        printf( "envp[%d] = %s\n" , i , envp[ i ] ) ;
    }
    return 0 ;
}
((( argvenvp.c を実行してみる )))
guest00@nitfcei:~$ cp /home0/Challenge/3-shellscript/argvenvp.c .
guest00@nitfcei:~$ gcc argvenvp.c
guest00@nitfcei:~$ ./a.out
argv[0] = ./a.out
envp[0] = SHELL=/bin/bash
:

プロセスの返す値

プログラムによっては、処理が上手くいかなかったことを検知して、別の処理を実行したいかもしれない。
こういう場合には、C言語であれば main の返り値に 0 以外の値で return させる。( exit関数を使ってもいい )
以下の例では、入力値の平均を出力するが、データ件数が0件であれば平均値を出力できない。こういう時に、”return 1 ;” のように値を返せば、シェル変数 $? (直前のコマンドの返り値) に return で返された値を参照できる。

((( average.c )))
#include <stdio.h>
int main() {
    int count = 0 ;
    int sum = 0 ;
    char buff[ 1024 ] ;
    while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
        int value ;
        if ( sscanf( buff , "%d" , &value ) == 1 ) {
            sum += value ;
            count++ ;
        }
    }
    if ( count == 0 ) {
        // データ件数が0の場合は平均が計算できない。
        fprintf( stderr , "No data\n" ) ;
        // プログラムが失敗したことを返すには 0 以外の値を return する。
        return 1 ;      // exit( 1 ) ;
    } else {
            printf( "%lf\n" , (double)sum / (double)count ) ;
    }
    return 0 ;
}

((( average.c を動かしてみる )))
guest00@nitfcei:~$ gcc average.c
guest00@nitfcei:~$ ./a.out
12
14
^D        # Ctrl-D で入力を終わらせる
13.00000
guest00@nitfcei:~$ echo $?       # プロセスの実行結果の値を参照するためのシェル変数 $?
0
guest00@nitfcei:~$ ./a.out
^D        # データを入力せずにすぐに終了させる。
No data
guest00@nitfcei:~$ echo $?
1

シェルスクリプト

今まで、コマンドラインで命令の入力をしてきたが、こういったキーボードと対話的処理を行うプログラムは shell (シェル) と呼ばれ、今回の演習では、/bin/bash を用いている。 shell は、キーボードとの対話的処理だけでなく、shell で入力するような処理をファイルに記録しておき、そのファイルに記載されている順に処理を実行することができる。

guest00@nitfcei:~$ cp /home0/Challenge/3-shellscript/helloworld.sh .
guest00@nitfcei:~$ cat helloworld.sh
#!/bin/bash

echo "Hello World"

message="こんにちは"                       # シェル変数への代入
echo "Hello World = $message"             # シェル変数の参照

guest00@nitfcei:~$ bash helloworld.sh     # bash で helloworld.sh を実行する
Hello World
Hello World = こんにちは

シェルスクリプトの基本は、キー入力で実行するようなコマンドを書き並べればいい。

しかし、プログラムを実行する度に、bash ファイル名 と入力するのは面倒。こういう時には以下の2つの設定を行う。

  1. シェルスクリプトの先頭行に 実行させる shell の名前の前に “#!” をつける。
    この行は、通称”シバン shebang (シェバン)“と呼ばれ、bashで実行させたいのなら”#!/bin/bash“、プログラミング言語 Perl で実行させたいのなら “#!/usr/bin/perl” とか、Python で実行させたいのなら、”#!/usr/bin/python” のようにすればいい。(今回のサンプルはすでに記入済み)
  2. 保存したスクリプトに対して、実行権限を与える。
    “ls -al “で “rw-r–r–” のようなファイルの書き込みパーミッションが表示されるが、通常ファイルの場合は、“x”の表示があると、プログラムとして実行可能となる。(フォルダであれば、rwxr-xr-x のように”x”の表示があると、フォルダの中に入ることができる)
((( 実効権限の設定 )))
guest00@nitfcei:~$ chmod 755 helloworld.sh
guest00@nitfcei:~$ ./helloworld.sh
Hello World
Hello World = こんにちは

$HOME/.bashrc

シェルスクリプトは、Linux の環境設定を行うためのプログラム言語として使われている。

例えば、ユーザがログインする際には、そのユーザがどういった言語を使うのか(LC_LANG,LANG)や、どういったプログラムをよく使うのか(PATH,LD_LIBRARY_PATH)などは、そのユーザの好みの設定を行いたい。こういう時に、shell に bash を使っているのであれば、$HOME/.bashrc に、shell を使う際の自分好みの設定を記載すればいい。

((( $HOME/.bashrc の例 )))
#!/bin/bash

# PATHの設定
export PATH=/usr/local/bin:/usr/bin:/bin

# MacOS でインストールされているソフトで PATH を切り替える
if [ -d /opt/homebrew/bin ]; then  # /opt/homebrew/bin のディレクトリがあるならば...
        # HomeBrew
        export PATH=/opt/homebrew/bin:$PATH
elif [ -d /opt/local/bin ]; then   # /opt/local/bin のディレクトリがあるならば...
        # MacPorts
        export PATH="/opt/local/bin:$PATH"
fi

ユーザ固有の設定以外にも、OSが起動する時に、起動しておくべきプログラムの初期化作業などにもシェルスクリプトが使われている。
例えば、/etc/init.d/ フォルダには、Webサーバ(apache2)やsshサーバ(ssh) といったサーバを起動や停止をするための処理が、シェルスクリプトで記載してあり、OS 起動時に必要に応じてこれらのシェルスクリプトを使ってサーバソフトを起動する。(ただし最近は systemd が使われるようになってきた)

理解度確認小テスト

D/A・A/D変換回路と誤差

小型コンピュータを使った制御では、外部回路に指定した電圧を出力(D/A変換)したり、外部の電圧を入力(A/D変換)したりすることが多い。以下にその為の回路と動作について説明する。

D/A変換回路

ラダー抵抗回路によるD/A変換の仕組みを引用

このような回路で、D0,D1,D2 は、デジタル値の0=0[V] , 1=5[V] であった場合、Output 部分の電圧は、(D0,D1,D2)の値が、(0,0,0),(0,0,1),…(1,1,1)と変化するにつれ、5/8[V]づつ増え、(1,1,1)で 5*(7/8)=4.4[V]に近づいていく。最後に、Output が出力によって電圧が変化しないように、アンプ回路を通す。

DCモータをアナログ量で制御しないこと

このように、電圧をコンピュータから制御するようになると、ロボットで模型用の直流モータの回転速度をこれで制御したい…と考えるかもしれない。
しかし、直流モータは、ブラシとコイル(電磁石)を組み合わせたものだが、モーターが回転しだす瞬間でみれば、コイルは単なる導線である。このため、小さい電流でゆっくりモータを回転させようとすると、たとえ小さい電圧でも導線(抵抗はほぼ0[Ω])には大量の電流が流れ、モータをスイッチングする回路は焼き切れるかもしれない。



PWM変調

こういう場合には、PWM変調(Pulse Width Modulation) を行う。電圧の高さは一定で、高速回転させるときは長時間電圧をONにするが、低速回転させるときはONとOFFを繰り返し信号でONの時間を短くする。

このような波形であれば、低速度でも電流が流れる時間が短く、大量の電流消費は避けられ、モーターをまわす力も安定する。

A/D変換回路

D/A変換とは逆に、アナログ量をデジタル値に変換するには、どのようにするか?

このような場合には、A/D変換回路を用いる。一般的な回路では、以下のような逐次比較型A/D変換を用いる。

この回路では、変換開始と共に入力値をサンプル保持回路でアナログ量を保存する。
その後、Registerの中のデジタル値を、D/A 変換回路でアナログ量に変換した結果を、比較器(Comparator)でどちらが大きいか判断し、その結果に応じて2分探索法とかハイアンドローの方式のように、比較を繰り返しながらデジタル値を入力値に近づけていく。

ハイアンドロー(数あてゲーム)

数あてゲームで、デタラメな0〜127までの整数を決めて、ヒントを元にその数字を当てる。回答者は、数字を伝えると、決めた数よりHighかLowのヒントをもらえる。
最も速い回答方法は…

例えば決めた数が55だとすると

・初期状態    ???????  0..127
・64 - Low   0??????  0..63
・32 - High  01????? 32..63
・48 - High  011???? 48..63
・56 - Low   0110??? 48..55
・52 - High  01101?? 52..55
・54 - High  011011? 54..55
・55 - Bingo 0110111 55確定

どんな値でも、7回(27=127)までで当てることができる。

量子化と量子化誤差

アナログデータ(連続量)デジタルデータなどの離散的な値で近似的に表すことを、量子化という。

量子化誤差とは、信号をアナログからデジタルに変換する際に生じる誤差のことをいう。

アナログ信号からデジタル信号への変換を行う際、誤差は避けられない。アナログ信号は連続的で無限の正確さを伴うが、デジタル信号の正確さは量子化の解像度やアナログ-デジタル変換回路のビット数に依存する。

偶然誤差

アナログ信号がA/D変換回路に入るまでに、アナログ部品の電気的変動(ノイズ)が原因で値が変動することもある。ノイズが時間的に不規則に発生し、値が増えてしまったり減ってしまったり偶然に発生するものは偶然誤差という。偶然誤差を加えると相殺されてほぼ0になるのであれば、統計的な手法で誤差の影響を減らすことができる

なぜデジタル信号を使うのか

コンピュータが信号処理でなぜ使われるのか?例えば、下の信号のように、電圧の低い/高いで0/1を表現したとする。

ノイズが混入しづらい

このデータ”01011100″を通信相手に送る場合、通信の途中でノイズ(図中の赤)のような信号が加わった場合、アナログ信号では、どれがノイズなのか判別することはできない。しかしデジタル信号であれば、真ん中青線より上/下か?で判別すれば、小さいノイズの影響は無視して、元どおりの”01011100″を取り出せる。この0か1かを判別するための区切り(図中青線)は、しきい値と呼ばれる。

ノイズを見つける・治す

また、”01011100″のデータを送る通信の途中で、しきい値を越えるような大きなノイズが混ざって、受信したとする。この場合、単純に受け取るだけであれば、”01010100″で間違った値を受け取っても判別できない。しかし、データを送る際にパリティビット(偶数パリティであれば全データの1の数が偶数になるように)1ビットのデータを加える。このデータを受け取った際に、ノイズで1ビット反転した場合、1の数が奇数(3個)なので、ノイズでビット反転が発生したことがわかる。これをパリティチェックと言う。

このように、デジタル信号を使えば、しきい値を越えない程度のノイズならノイズの影響を無視できるし、たとえ大きなノイズでデータに間違いがあっても、パリティチェックのような方法を使えば間違って伝わったことを判別できる。

パリティチェックは、元のデータに1bitの信号を追加することで誤り検出ができるが、2bit同時に変化してしまうと誤りを見つけられない。そこで、元データにさらに多くのbit情報を追加すると、1bitの間違いを元に戻すようにもできる。誤り検出・訂正

電子回路で制御するかコンピュータで制御するか

これ以外にも、デジタル信号にする理由がある。

アナログ回路(電子回路)で制御しようとすると、抵抗やコイルやコンデンサといった受動素子が必要となるが、その中でもコイルは小型化がしづらい部品で、制御回路全体の小型化が難しい。大量生産ができるような回路なら小型化ができるかもしれないが、多品種少量の生産物では小型化のための開発費用の元がとれない。しかし、大量生産された安価な小型コンピュータで制御すれば、制御回路全体の小型化も可能となる。

また、電子回路の特性を調整するには、抵抗などの部品をはんだ付けをしながら部品を交換することになるかもしれない。しかしながら、アナログ信号をデジタル信号にしてしまえば、ノイズを減らすための平均化処理などは計算で実現できるし、特性を変化させるための調整もプログラムの数値を変更するだけで可能となる。

UMLと構造図

前回の説明のUMLのできたころの話を踏まえ、UMLの中のプログラムの構造図の説明を行う。

UML(Unified Modeling Language)記法が生まれるまで

巨大なプロジェクトでプログラムを作る場合、対象となるシステムを概念として表現する場合、オブジェクト指向分析(OOA: Object Oriented Analysis)オブジェクト指向設計(OOD: Object Oriented Design)とよばれるソフトウェア開発方法が重要となる。(総称して OOAD – Object Oriented Analysis and Design)

これらの開発方法をとる場合、(1)自分自身で考えを整理したり(2)グループで設計を検討したり(3)ユーザに仕様を説明したりといった作業が行われる。この時に、自分自身あるいはチームメンバーあるいはクライアントに直感的に図を用いて説明する。この時の図の書き方を標準化したものが UML であり、(a)処理の流れを説明するための振る舞い図(以前であればフローチャートやPAD)と、(b)データ構造を説明するための構造図を用いる。

UMLは、ランボーによるOMT(Object Modeling Technique どちらかというとOOA中心)と、 ヤコブソンによるオブジェクト指向ソフトウェア工学(OOSE)を元に1990年頃に 発生し、ブーチBooch法(どちらかというとOOD中心)の考えをまとめ、 UML(Unified Modeling Language)としてでてきた。

UMLでよく使われる図を列記すると、以下の物が挙げられる。

  • 構造図
    • クラス図
    • コンポーネント図
    • 配置図
    • オブジェクト図
    • パッケージ図
  • 振る舞い図
    • アクティビティ図
    • ユースケース図
    • ステートチャート図(状態遷移図)
    • 相互作用図
    • シーケンス図
    • コミュニケーション図(コラボレーション図)

UMLを正しく使うことができるようになれば、UMLで仕様書を書けばそれがそのままプログラムになることが理想的な姿かもしれない。ソフトウェア開発やソフトウェアの保守にソフトウェアツールを利用することは、CASE(Computer Aided Software Engineering)と呼ばれ、そのようなツールをCASEツールと呼ぶ。地元福井の永和システムマネジメントでは、astar* というCASEツールを開発している。


UMLの構造図の書き方の説明。 詳しくは、参考ページのUML入門などが、分かりやすい。

クラス図

クラス図は、構造図の中の基本的な図で、 枠の中に、上段:クラス名、中段:属性(要素)、下段:メソッド(関数)を記載する。 属性やメソッドの可視性を示す場合は、”-“:private、”+”:public、”#”:protected 可視性に応じて、”+-#”などを記載する。

関連

クラスが他のクラスと関係がある場合には、その関係の意味に応じて、直線や矢印で結ぶ。
(a)関連(association):単純に関係がある場合、
(b)集約(aggregation):部品として持つが、弱い結びつき。関係先が消滅しても別に存在可能。(has-a)
(c)コンポジション(composition):部品として持つが強い結びつき。関係先と一緒に消滅。(has-a)
(d)依存(dependency):依存関係にあるだけ
(e)派生(generalization):派生・継承した関係(is-a)
(f)実現(realization): Javaでのinterfaceによる多重継承

上図の例では、乗り物クラスVehicleから自動車Carが派生し(CarからVehicleへの三角矢印―▷)、 自動車は、エンジン(Engine)を部品として持つ(EngineからCarへのひし形矢印―◆)。エンジンは車体と一緒に廃棄なら、コンポジション(C++であれば部品の実体を持つ)で実装する。

自動車は、同じく車輪(Wheel)を4つ持つが、自動車を廃棄してもタイヤは別に使うかもしれないので、集約(部品への参照を持つ)で実装する(WheelからCarへのひし形矢印―◇)。 集約で実装する場合は、C++などであれば、ポインタで部品を持ち、部品の廃棄(delete)は、別に行うことになる。

Javaなどのプログラム言語では、オブジェクトはデータの実体へのポインタで扱われるため、コンポジションと集約を区別して表現することは少ない。

is-a 、has-a の関係

前の課題でのカモノハシクラスで、羽や足の情報をどう扱うべきかで、悩んだ場合と同じように、 クラスの設計を行う場合には、部品として持つのか、継承として機能を持つのか悩む場合がある。 この場合には、“is-a”の関係“has-a”の関係で考えると、部品なのか継承なのか判断しやすい。

たとえば、上の乗り物(Vehicle)クラスと、車(Car)のクラスは、”Car is-a Vehicle” といえるので、is-a の関係。 “Car is-a Engine”と表現すると、おかしいことが判る。 車(Car)とエンジン(Engine)のクラスは、”Car has-a Engine”といえるので、has-a の関係となる。 このことから、CarはVehicleからの派生であり、Carの属性としてEngineを部品として持つ設計となる。

オブジェクト図

クラス図だけで表現すると、複雑なクラス関係では、イメージが分かりづらい場合がでてくる。 この場合、具体的な値を図に書き込んだオブジェクトで表現すると、説明がしやすい場合がある。 このように具体的な値で記述するクラス図は、オブジェクト図と言う。 書き方としては、クラス名の下に下線を引き、中段の属性の所には具体的な値を書き込んで示す。

パッケージ図

パッケージ図は、クラス図をパッケージ毎に分類して記載する図。 パッケージのグループを、フォルダのような図で記載する。


IT専科から引用

コンポーネント図とコンポジット構造図

コンポジット構造図は、クラスやコンポーネントの内部構造を示すもので、コンポーネント図は、複数のクラスで構成される処理に、 インタフェースを用意し、あたかも1つのクラスのように扱ったもの。 接続するインタフェースを飴玉と飴玉を受けるクチのイメージで、提供側を◯───で表し、要求側を⊃──で表す。


IT専科から引用

配置図

配置図は、システムのハードウェア構成や通信経路などを表現するための図。 ハードウェアは直方体の絵で表現し、 デバイスの説明は、”≪device≫”などを示し、実行環境には、”≪executionEnvironment≫” などの目印で表現する。


IT専科から引用

リスト処理

リスト構造

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

まずは、メモリ確保とポインタをつなげるイメージを確実に理解してもらうために、1つ1つのデータをポインタでつなげる処理を示す。

#include <stdio.h>
#include <stdlib.h>

// List構造の宣言
struct List {
   int          data ;  // データ保存部
   struct List* next ;  // 次のデータへのポインタ
} ;

int main() {
   struct List* top ;   // データの先頭
   struct List* p ;

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

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

このようなメモリーの中のポインタの指し示す番地のイメージを、具体的な番地の数字を書いてみると、以下のような図で表せる。先頭の111が入った部分が1000番地であったなら、topというポインタには1000番地が入っている。

NULLって何?

前回の授業で説明した、次の配列の添え字の番号を使う方式では、データの末尾を示すためには、-1 を使った。-1 は、配列の添え字で通常ありえない値であり、次のデータはないという目印とした。

同じように、C言語では、通常あり得ないポインタとして、0 番地を示す NULL が定義されている。NULLポインタの先を参照してはいけない。このリスト処理では、末尾を表す目印として使っている。

#define NULL 0

補助関数

上記のプログラムでは、(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 ;
}

int main() {
   struct List* top ;
   top = cons( 111 , cons( 222 , cons( 333 , NULL ) ) ) ;
   :
   return 0 ; // Listの開放free()は省略
}

補助関数の名前の cons は、constructor の略であり、古くから使われている List Processor(LISP) というプログラム言語でのリスト(セル)を生成する関数が cons 。

typedefを使った書き方

List構造の宣言は、古い書き方では typedef を使うことも多い。typedef は、型宣言において新しい型の名前をつける命令。

// typedef の使い方
//    typedef 型宣言 型名 ;
typedef unsigned int uint32 ; // 符号なし32bit整数をシンプルに書きたい
uint32 x = 12345 ;

typedef struct LIST {     // 構造体のタグ名と新しくつける型名と重複できない
      int   data ;        // のでこの時点のタグ名は "LIST" としておく
      struct LIST* next ;
   } List ;

List* cons( int x , List* n ) {  // C++なら struct List { ... } ; と書く
   List* ans ;                   // だけでこういう表記が可能
   ans = (List*)malloc( sizeof( List ) ) ;
   :
   ((略))
}
int main() {
   List* top ;
   top = cons( 111 , cons( 222 , cons( 333 , NULL ) ) ) ;
   :
   ((略))
}

最近のC言語(C++)では、構造体のタグ名がそのまま型名として使えるので、こういう書き方をする必要はなくなってきている。

// 最近のC++なら...
struct List {
public:
   int   data ;
   List* next ;
public:
   List( int x , List* n )
     : data( x ) , next( n ) {}
} ;

int main() {
   List* top = new List( 111 , new List( 222 , new List( 333 , NULL ) ) ) ;
   :
   // Listの開放deleteは省略
}

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

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

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

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

古いAI※※と最近のAIの違い

最近では、AI(Artificial Intelligence) という言葉が復活してきたが、LISP が開発された頃の AI と最近注目されている AI は、微妙に異なる点がある。

LISPが開発された頃の AI は、関数型のプログラム言語で論理的思考を表現することが目標であった。頭脳を左脳と右脳の違いで表現することが多いが、どちらかというとLISPの時代のAI「分析的で論理的に優れ、言語力や計算機能が高い」とされる左脳を作り出すことを目指していた。しかしながら、この時代では、漠然としたパターンを認識したりするような「感覚的、直感的な能力に優れ総合判断力を司る右脳」のような処理は苦手であった。

しかしながら、最近注目されている AI は、脳神経を真似たニューラルネットワークから発展した機械学習ディープラーニングという技法により今まで難しかった右脳の機能を実現することで、最近のAIでは左脳と右脳の機能を兼ね備えたものとなっている。

将棋のプログラミングで例えるなら、左脳(古いAI)に例えられるのが正確に先の手を読む機能であり、右脳に例えられる機能が大局観(全体の良し悪しを見極める判断能力)といえる。

簡単なリスト処理の例

先に示したリスト構造について簡単なプログラム作成を通して、プログラミングに慣れてみよう。

// 全要素を表示する関数
void print( struct List* p ) {
   for( ; p != NULL ; p = p->next )
      printf( "%d " , p->data ) ;
   printf( "¥n" ) ;
}
// データ数を返す関数
int count( struct List* p ) {
   int c = 0 ;
   for( ; p != NULL ; p = p->next )
      c++ ;
   return c ;
}
int main() {
   struct List* top = cons( 111 , cons( 444 , cons( 333 , NULL ) ) ) ;
   print( top ) ;
   printf( "%d¥n" , count( top ) ) ; 
   return 0 ;
}

リスト処理を自分で考えて作成

以下のようなプログラムを作ってみよう。意味がわかって慣れてくれば、配列の部分の for の回し方が変わっただけということに慣れてくるだろう。

// 全要素の合計
int sum( struct List* p ) {
   // sum( top ) → 888
   自分で考えよう
}
// リストの最大値を返す
int max( struct List* p ) {
   // max( top ) → 444 (データ件数0の場合0を返す)
   自分で考えよう
}
// リストの平均値を返す
double mean( struct List* p ) {
   // (111+444+333)/3=296.0
   自分で考えよう
}
// リストの中から指定した値の場所を返す
int find( struct List* p , int key ) {
   // find( top , 444 ) = 1 (先頭0番目)
   // 見つからなかったら -1
   自分で考えよう
}

再帰呼び出しでリスト処理

リスト処理の応用のプログラムを作るなかで、2分木などのプログラミングでは、リスト処理で再帰呼出しを使うことも多いので、先に示したプログラムを再帰呼び出しで書いたらどうなるであろうか?

// 全データを表示
void print( struct List* p ) {
   if ( p == NULL ) {
      printf( "¥n" ) ;
   } else {
      printf( "%d " , p->data ) ;
      print( p->next ) ; // 末尾再帰
   }
}
// データ数を返す関数
int count( struct List* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return 1 + count( p->next ) ; // 末尾再帰
}
// 全要素の合計
int sum( struct List* p ) {
   // sum( top ) → 888
   自分で考えよう
}
// リストの最大値を返す
int max( struct List* p ) {
   // max( top ) → 444 (データ件数0の場合0を返す)
   自分で考えよう
}
// リストの中から指定した値を探す。
int find( struct List* p , int key ) {
   // find( top , 444 ) = 1 
   // 見つかったら1 , 見つからなかったら 0
   自分で考えよう
}

理解度確認

上記プログラム中の sum() , max() , find() を再帰呼び出しをつかって記述せよ。

リダイレクト・パイプ

Linuxを使う上で、キーボードでコマンドを入力しているが、こういうコマンドの管理を行うプログラムshell と呼ぶ。shell には、色々なものがある(sh, csh, bash, zsh)が、広く使われている bash( born-again shell )について説明する。最初に、コマンドの入出力を組み合わせるために重要となるリダイレクトとパイプについて説明し、次にコマンドなどの処理単位となるジョブやプロセスの考え方について説明を行う。

標準入出力とリダイレクト

出力リダイレクト

C言語のプログラミングで、プログラムの実行結果をレポートに張り付ける時はどのように行っているだろうか?多くの人は、実行画面を PrintScreen でキャプチャした画像を張り付けているかもしれない。しかし、数十行にわたる結果であれば何度もキャプチャが必要となる。
そこで、今日の最初はリダイレクト機能について説明する。

“gcc ファイル.c” は、C言語のプログラムをコンパイルし、a.out という実行ファイルを生成する。”./a.out” にてプログラムを実行する。実行する命令に、“> ファイル名” と書くと、通常の出力画面(標準出力) をファイル名に記録してくれる。これを出力リダイレクトと呼ぶ。また、“>> ファイル名” と書くと、既存ファイルの後ろに追記してくれる。

guest00@nitfcei:~$ cat helloworld.c
#include <stdio.h>
int main() {
    printf( "Hello World\n" ) ;
    return 0 ;
}

guest00@nitfcei:~$ gcc helloworld.c
guest00@nitfcei:~$ ./a.out
Hello World

guest00@nitfcei:~$ ./a.out > helloworld.txt

guest00@nitfcei:~$ cat helloworld.txt
Hello World

guest00@nitfcei:~$ ./a.out >> helloworld.txt

guest00@nitfcei:~$ cat helloworld.txt 
Hello World
Hello World 

入力リダイレクト

次に、1行に名前と3教科の点数が書いてある複数行に渡るデータの各人の平均点を求めるプログラムを考える。

guest00@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/avg-each-low.c .
guest00@nitfcei:~$ cat avg-each-low.c
#include <stdio.h>
// ((input))           ((output))
// saitoh  43  54 82   saitoh 59.67
// tomoko  89 100 32   tomoko 73.67
// mitsuki 79  68 93   mitsuki 80.00
int main() {
   char name[ 100 ] ;
   int point[ 3 ] ;
   while( scanf( "%s%d%d%d" ,
                 name , &point[0] , &point[1] , &point[2] ) == 4 ) {
      double sum = 0.0 ;
      for( int i = 0 ; i < 3 ; i++ )
         sum += point[i] ;
      printf( "%s %6.2f\n" , name , sum / 3.0 ) ;
   }
   return 0 ;
}

guest00@nitfcei:~$ gcc avg-each-low.c
guest00@nitfcei:~$ ./a.out
saitoh 43  54 82    入力
saitoh 59.67        出力
tomoko 89 100 32    入力
tomoko 73.67        出力
^D             ← Ctrl-D を押すとファイル入力を終了

しかし、プログラムの書き方を間違えてプログラムを修正していると、動作確認のたびに何度も同じデータを入力するかもしれないが、面倒ではないだろうか?

プログラムを実行する時に、“< ファイル名” をつけると、通常はキーボードから入力する所を、ファイルからの入力に切り替えて実行することができる。このようなscanf()を使う時のようなプログラムの入力を標準入力といい、それをファイルに切り替えることを入力リダイレクトと呼ぶ。

guest00@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/name-point3.txt .

guest00@nitfcei:~$ cat name-point3.txt
saitoh  43  54 82
tomoko  89 100 32
mitsuki 79  68 93 

guest00@nitfcei:~$ ./a.out < name-point3.txt
saitoh  59.67
tomoko  73.67
mitsuki 80.00

この入力リダイレクトと出力リダイレクトを合わせて使うこともできる。

guest00@nitfcei:~$ ./a.out < name-point3.txt > name-avg.txt

guest00@nitfcei:~$ cat name-avg.txt
saitoh  59.67
tomoko  73.67
mitsuki 80.00

パイプ

先の名前と3教科のプログラムの結果から、全員の平均点をも計算したい場合、どのようなプログラムを作るだろうか?C言語だけの知識なら、各人の行のデータを計算するループの中に、全員の合計と人数を求めるプログラムを書いて、最後に平均点を出力するだろう。

一方で、複数人の名前と平均点のデータから平均点を求めるプログラムを書いて、前述のプログラムの実行結果を使う人もいるだろう。

以下の例では、“gcc -o avg-each-row avg-each-row.c” で、avg-each-row という実行ファイル、“gcc -o avg-all avg-all.c” で、avg-all という実行ファイルを生成し、avg-each-row で入力リダイレクト・出力リダイレクトを使って、name-avg.txt を作り、avg-all を入力リダイレクトで、最終結果を表示している。

guest00@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/avg-all.c .
guest00@nitfcei:~$ cat avg-all.c
#include <stdio.h>
// ((input))      ((output))
// saitoh  59.67  73.11
// tomoko  73.67
// mitsuki 80.00
int main() {
   char name[ 100 ] ;
   double point ;
   double sum = 0 ;
   int count = 0 ;
   while( scanf( "%s%lf" , name , &point ) == 2 ) {
      sum += point ;
      count++ ;
   }
   printf( "%6.2f\n" , sum / (double)count ) ;
   return 0 ;
}

guest00@nitfcei:~$ gcc -o avg-each-low avg-each-low.c
guest00@nitfcei:~$ gcc -o avg-all avg-all.c

guest00@nitfcei:~$ ./avg-each-low < name-point3.txt > name-avg.txt

guest00@nitfcei:~$ ./avg-all < name-avg.txt
71.11

しかし、いちいち入出力の結果を name-avg.txt を作るのは面倒である。であれば、以下の様なイメージで処理をすれば答えが求まる。

name-point3.txt(avg-each-row)name-avg.txt(avg-all)結果

これは、パイプ機能を使って以下の様に動かすことができる。

guest00@nitfcei:~$ ./avg-each-low < name-point3.txt | ./avg-all
71.11

guest00@nitfcei:~$ cat name-point3.txt | ./avg-each-low | ./avg-all
71.11

プログラムを実行する時に、“A | B” ように書くと、プログラムA の標準出力結果を、プログラムB の標準入力に接続させて、2つのプログラムを実行できる。このような機能を、パイプと呼ぶ。上記例の2つめ “cat… | ./avg-each-low | ./avg-all” では3つのプログラムをパイプでつないでいる。


リダイレクトのまとめ

 

入力リダイレクト(標準入力) 実行コマンド < 入力ファイル
出力リダイレクト(標準出力) 実行コマンド > 出力ファイル
 出力リダイレクト(標準出力の追記) 実行コマンド >> 出力ファイル
 標準エラー出力のリダイレクト 実行コマンド 2> 出力ファイル
パイプ
コマンドAの標準出力をコマンドBの標準入力に接続
コマンドA | コマンドB

C言語のコンパイルまとめ

 

C言語のコンパイル(実行ファイルはa.out) gcc ソースファイル
 実行ファイル名を指定してコンパイル gcc -o 実行ファイル ソースファイル

システム

最新の投稿(電子情報)

最近の投稿(斉藤 徹)

アーカイブ

カテゴリー