2013年12月1日 星期日

University: Course work

問題 -- University 2:Acme大學提供許多課程(course)讓學生選修。每一個課程有它的名稱(name)、代碼(code)、學分(credit)及描述(description)。每個學期,學系開設若干課程(course offerings)。開課相關資訊有:課程代碼、學系代碼、年度(year)及學期(semester)。一門課在開課後,將擁有其開課代碼(course offering code)-由年、學期、系代碼、與課程代碼組成,例如2013 Fall semester Computer Science 開的課程comp_100,其開課代碼為 2013F_CS_comp_100並非每一個課程在每一學期都會被開設;同時,有些課程會有一個學系以上開設。在University 1程式的基礎上,為程式增加載入課程及開課的資料自檔案載入、顯示的功能。輸入檔案格式如下:

課程 courses.txt
Introduction to Computing;comp_100;3;Fundamentals of computing…
Computer Programming;comp_101;3;Programming using an imperative language such as C...
Object-oriented programming;comp_201;3;Programming using an OO language such as C++ or Java...

開課 courseofferings.txt
comp_100;CS;2013;Fall
comp_100;MU;2013;Fall
comp_100;CH;2013;Fall
comp_101;CS;2013;Fall
comp_201;CS;2014;Spring

載入資料後,行政人員可以選擇顯示特定學系指定學期的所有開課資訊,其順序按課程代碼遞增排序。隨後,行政人員可以選擇新增或刪除開課,例如:選CS系2013年 Fall學期後增加開課,


Select department: CS
Select year semester: 2013 Fall


Fall 2013 Course offerings:

Computer Science (CS): 2 courses, 6 credits
=================================

2013F_CS_comp_100; Introduction to Computing; 3 credits
2013F_CS_comp_101; Computer Programming; 3 credits

Add (+)/delete(-) course offering or anything else to go back:+
You selected adding a new course offering.
Input course id:comp_201

程式輸出:

Name: Object-oriented programming
ID: comp_201
Credits: 3 
Description: Programming using an OO language such as C++ or Java...
Is this correct Y/N: Y
Done adding course offering.

Fall 2013 Course offerings:
Computer Science (CS): 3 courses, 9 credits
=================================
2013F_CS_comp_100; Introduction to Computing; 3 credits
2013F_CS_comp_101; Computer Programming; 3 credits
2013F_CS_comp_201; Object-oriented programming; 3 credits

Add (+)/delete(-) course offering or anything else to go back:x
Select department:

如果新增的開課已有同一開課代號的課程存在,則通知使用者並忽略該項作業。

離開程式時,提示行政人員是否將開課資料寫回courseofferings.txt






University: sorting students a responsibility for Department?

Task 4 的 sorting 該交給哪個物件負責?明顯的選項是Department,因為它認得所有學生。但是,如Matrix例子,我們選擇以其他C function處理linear transformation,目的在讓Matrix維持簡單、易懂。

所以,按照同一個想法,我將先以一個C函數處理這件工作。
先寫測試:

TEST (NameDec, sort){
Department cs("Computer Science","CS");
Student mary("Alan","U20130003", &cs);
Student john("Betty","U20130002", &cs);
Student paul("Carol","U20130001", &cs);

vector<Student *> stus(cs.students());
sort (stus.begin(),stus.end(),nameDec);
CHECK(string("Carol")==stus[0]->name());
CHECK(string("Betty")==stus[1]->name());
CHECK(string("Alan")==stus[2]->name());
}

需要寫Department::students、Student::name、nameDec等函數,其中:

bool nameDec(Student *s1, Student * s2){
return s1->name() > s2->name();
}

為了強調這個函數用於依姓名排序Student,可將它定義為Student的member function。如宣告成一般 method,則需透過
Student物件才能找到這個函數:

Student s(...);

sort (stus.begin(),stus.end(), s.nameDec);

邏輯上有些怪。解決的作法是將它定義成static member function:

class Student {
public:
...
static bool nameDec(Student *s1, Student * s2){...}
};

static 的意義是宣告nameDec為Student class共用。static函數無法取用 instance variable或呼叫非static 之 member function(原因與 this 有關)。

如此,可直接使用該函數

sort (stus.begin(),stus.end(),Student::nameDec);

接著,完成依ID排序。

學習議題: static member function。


L步驟:請試著以user與programmer的角度回顧,增加必要的improvement round。

2013年11月17日 星期日

University: Students and departments

問題 -- University 1:在Acme大學,每個學生除有其姓名(name)之外,並在入學時取得一個學號(ID),每個學生有一個主修系(major department)。每個學系有名稱(name),並有一個代碼(code)。

Acme大學需要一個程式供行政人員使用。啟動時,程式將自三個檔案分別讀入學生、學系與學生主修學系資料,格式如下:

學生資料 
Jagger,Mick;U20130001
Carey,Mariah.;U20130002
Johnson,John;U20130003
Savitch,Sam;U20130004
Bass,Lenos;U20130005
Kazman,Rick;U20130006
Lippman,Stanley;U20130007

學系資料 
Computer Science;CS
Music;MU
Chemistry;CH

學生與主修學系資料 
U20130001;CS
U20130002;MU
U20130003;CH
U20130004;CS
U20130005;CH
U20130006;MU
U20130007;CS

程式啟動後,需顯示操作指引。在這個問題裡,行政人員將能依所選擇學系,並選擇名單按照學號或姓名增冪(increasing)或降冪(decreasing),依據下列格式(以學號升冪排序)列出主修該學系的學生名單。

Computer Science (CS): 3 students
U20130001 Jagger, Mick
U20130004 Savitch, Sam
U20130007  Lippman, Stanley

U步驟:這是一個典型的資訊處理程式。這些資訊為現實世界(real world)中,個體(學生、學系)的模型(model)。除了讀檔與顯示之外,程式並涉及排序(sorting)的問題。

D步驟:列出工作如下。

1. Create a student given a name and ID.
2. Create a department given its name and code.
3. Add a student to a department.
4. Sort the list of students in a department.
5. Set up students from a file.
6. Set up departments from a file.
7. Set up relationships between students and departments according to relationships  specified in a file.
8. Produce a list of students by department in the specified format.  
C步驟:

相信你已經能處理工作1~2, 5~6,8了,工作7只要在知道工作3如何處理後,應當也無問題。所以,我們看看如何處理工作3與工作4。

工作3:回答兩個問題,(1)學生需不需要記得他的主修學系?(2)學系需不需要記得它的學生?在現實世界裡,一個學生一定記得他的主修學系;一般而言,學系也會記得學生(通常透過學系的職員查詢學生名冊,這裡先不考慮這個細節)。程式中為他們建立模型,而設計反映這個模型。由無其他特殊考量因素(例如可測試性),故以符合現實世界的模型為依據進行設計,如下:

剩下的事就是「按圖施工」了--寫測試、建立Student 與 Department 類別相關的data與function。

Student以一個data member「記住」他的主修學系。有三種作法:

1. Department _major:將Department視為Student的一部分,在Student物件destructor執行時(例如going out of scope),_major 所代表的Department物件將一併被解構。由於Department物件可能關係著其他學生,故此作法不適用。

2. Department & _major:將Department視為Student參考的一個物件,_major 所參考的Department物件在Student物件destructor執行時(例如going out of scope),並不會被解構。這個做法的限制是 a. 學生物件 constructor執行時 department物件必須已存在且在 constructor initialization list中加以初值化:

   Student(... Department & dept): ... _major(dept) {}

b. Student物件不應變更 _major 所參考的Department物件,

   // semantics error
   void setMajor (Department & dept) {_major = dept;} 

因為如此一來,原先 _major所參考的 Department物件將被 dept覆蓋。解決之道是更改宣告為

   const Department & _major;

如此一來編譯時就會有錯:

   // syntax error
   void setMajor (Department & dept) {_major = dept;} 

這意味著學生將不得轉系!基於b.的限制,此作法亦不適用。

3. Department * _major將Department視為Student指標方式參考的一個物件,_major 在Student物件destructor執行時(例如going out of scope),並不會被解構。這個做法最具彈性,Student constructor執行時可將 _major預設為 NULL:

   Student(... Department * dept=NULL): ... _major(dept) {}

稍後再加以設定:

 void setMajor (Department *dept) {_major = dept;} // OK

這個做法的缺點是在Student的函數中,你得視情況先確認 _major不為NULL再加以使用。

 _major->name(); // 有 NULL pointer exception的危險

接著,Department得記住它的學生。用上面同樣的作法,但Department物件通常有多個學生,且題目涉及sorting,所以記住的方法為

vector<Student *> _students;

學習課題:reference variable, vector (C++  standard template library STL)。

工作4:將學生按照學號或姓名作升冪或降冪排序。由於學號、姓名都適合以string表示,所以要了解如何對string排序。在Department中,我們已使用std::vector存放pointer to Student,
  
  vector<Student *> _students;

所以,工作4就是按照學號或姓名,以升冪或降冪排序 _students的內容。

對vector內容排序的函數,C++已有提供。下面我用測試的方式試試看:

#include <vector>
#include <algorithm>
...
TEST (intVector, vector){
int a[]={3,2,1,4};
vector<int> v(a,a+4);
std::sort (v.begin(), v.begin()+4);
LONGS_EQUAL(1,v[0]);
LONGS_EQUAL(2,v[1]);
LONGS_EQUAL(3,v[2]);
LONGS_EQUAL(4,v[3]);
}

std::sort內建為升冪。如要降冪排序則可傳入一個比較函數:


bool decrease(int i, int j) {return i>j;}

TEST (intVectorDecrease, vector){
int a[]={3,2,1,4};
vector<int> v(a,a+4);
sort (v.begin(), v.begin()+4, decrease);
LONGS_EQUAL(4,v[0]);
LONGS_EQUAL(3,v[1]);
LONGS_EQUAL(2,v[2]);
LONGS_EQUAL(1,v[3]);
}

請試試完成工作4。

學習課題: list, iterator, sort (C++ standard template library STL)。
 

© Y C Cheng, 2013. All rights reserved.

2013年11月10日 星期日

Round 9: Exceptions - involve the users

當使用者有可能因操作引發例外時,程式處理例外的方式應為:適度提示使用者,讓他有機會更正此項錯誤,並繼續正常執行

U步驟:

檢視innerProduct程式,可發現可能引發innerProduct計算的dimension error。同此,檢視linearTransform程式,亦可發現同樣的問題。

SP8:處理innerProduct與linearTransform的dimension error。

D步驟:

T37:寫innerProduct測試innerProduct dimension檢查,及拋出例外;決定如何處理innerProduct dimension例外,做必要的程式修改。


T38:寫linearTransform測試、linearTransform dimension檢查,及拋出例外;決定如何處理linearTransform dimension例外,做必要的程式修改。

C步驟:

T37:寫innerProduct測試innerProduct dimension檢查,及拋出例外;決定如何處理innerProduct dimension例外,做必要的程式修改。

利用overload特性,先不修改既有的innerProduct,寫測試如下:

TEST (dimension_exception, innerProduct){
double a[2]={0,1};
double c[3]={1,2,3};
vector u(2,a);
vector w(3,c);

try {
innerProduct(u,w);
}
catch (string s){
CHECK(string("innerProduct: dimension error!") == s);
}

}

innerProduct函數如下:

double innerProduct(const vector &u, const vector &v){
if (u.dim() != v.dim()){
throw std::string("innerProduct: dimension error!");
}
double p=0;
for (int i=1; i <= u.dim(); ++i)
p = p+u[i]*v[i];
return p;
}

事關使用者,故在main中處理,

try {
cout << "inner product is " << innerProduct(u,v)<< endl;
}
catch (string s){
cout << s << endl;
}

我寫的程式請你參考。T38請你試試看。

L步驟:比較原有innerProdct

  bool innerProduct(double & p,const vector &u, const vector &v)

可見新的innerProduct介面

  double innerProduct(const vector &u, const vector &v)

較為直覺、簡約;此一特性充分顯示在innerProduct的使用上。

原innerProduct

1. 內積計算牽涉兩個向量,但innerProduct有三個參數,閱讀程式者須花一些額外的功夫判斷才知道第一個參數的為輸出參數
2. 呼叫原先innerProduct處,需要檢查還傳值為true或false,強迫programmer在每一個呼叫innerProduct處作錯誤處理,使正常處理與錯誤處理的code混合在一起,不易閱讀。

相對的,新innerProduct

1. 內積計算牽涉兩個向量,innerProduct有二個輸入參數,傳回值為double,閱讀程式者較容易理解。
2. 新的innerProduct可直接呼叫。惟當dimension例外需要被處理時,programmer才使用try statement。如果dimension例外應被視為bug而須採用fail fast處理方式終止程式,則程式碼將能維持乾淨、簡單。

這些優點來自於C++ 例外處理機制,它讓例外狀況自有管道,不需借用function的介面回傳,並讓programmer有具體的方法分離正常處理與例外處理的code。

繼續回顧的工作。程式還有哪些可以改善的地方?

首先,以使用者觀點回顧,SP2尚未解決,使用者可能輸入格式不正確的向量、矩陣。現在,你處理的手段變多了,例如使用例外,且因該問題面向使用者(user facing),所以你需要讓程式繼續執行,並讓使用者有修正的機會。處理這個問題的方法之一是以字串方式取得使用者輸入,再加以解析(parse)以偵測是否格式錯誤;請你試試看。

其次,以programmer觀點回顧,你可以試著review現有的code,發現值得改善之處。例如,尋找重複的code (duplicated code),以函數取代之;請你也試試看。



© Y C Cheng, 2013. All rights reserved.

2013年10月31日 星期四

Round 8: Exception - fail fast

Backlog中仍有SP2與SP7,這一 round 我們選SP7:建立vector與matrix超限功能與測試。

U步驟:

超限測試是vector::operator [] 與 matrix::at極為重要的面向。以vector::operator []為例,由於當初我選擇以operator [] 取用向量的分量,一開始向量v的第一分量為v[0],後來認錯修正為v[1],這樣的歷程即便是你自己都有可能記錯。於是,你有可能仍用v[0]表達向量v的第一分量 -- 超限了。

簡單的說起來,我們需要在取用向量的分量之前檢查operator []的傳入參數是否超限。如是,則應避免傳值回去。這種情況類似於先前計算innerProduct的函數,


bool innerProduct(double &product, const vector &u, const vector &v);

所以,一種解法是仿照innerProduct的函數的做法,傳回bool並引進一個參數作為回傳結果。

問題來了,由於operator []是C++ 內建運算子,只能接受一個輸入參數,且返回型態在這裡必須是 double:


double & operator [](int i) const;

所以無法套用innerProduct的函數的做法!我們得另想辦法。

幸運的是C++及其他較新的程式語言如Java、Python、Scala等,均提供表達與處理例外狀況的機制(exception handling mechanism)如果將超限視為一種例外狀況,則 operator []可檢查(detect)是否超限,如是則拋出例外(throw an exception),表示超限已發生, 並終止正常函數執行:

double & vector::operator [](int i) const {
if (i <=0 || i > _dim )
throw std::string("Index to vector out of bound!");
return _v[i-1];
}

C++ 提供一個exception class,用來表達例外。我們可以利用這個型態,但是代價為較為複雜些。幸好,C++容許拋出任意型態的例外,例如int、const char* (C string)、string等。這裡,vector::operator[]可拋出的例外型態為string。

呼叫operator []的敘述,則可放置在 try 敘述 (try statement)try block之中,並由緊跟在後的catch block加以捕捉:

try {
double component = u[0];
}
catch (string s) {
CHECK(string("Index to vector out of bound!") == s);
}

注意 catch敘述是以型態比對的方式捕捉例外。

如超限例外未被捕捉(例如,呼叫operator []的敘述未被放置於try statement或無對應的catch block加以捕捉),則該例外將繼續上傳至前一個做出呼叫的的函數,依此類推,直到到達main。如main未加以捕捉,則C++ runtime將會終結程式。

D步驟:

我們將以string作為operator []超限例外。工作列出如下

T31:寫vector::operator []超限測試。
T32:vector::operator []超限檢查,及拋出例外
T33:決定如何處理vector::operator []超限例外,做必要的程式修改
T34:寫matrix:at超限測試。
T35:matrix:at超限檢查,及拋出例外
T36:決定如何處理matrix:at超限例外,做必要的程式修改

C步驟:

T31:operator []超限測試。

增加兩個超限測試,期望超限發生時,拋出的例外物件為string("Index to vector out of bound!")。

TEST (index_outofbound_low, vector){
vector u(2);
try {
double ccomponent = u[0];
}
catch (string s) {
CHECK(string("Index to vector out of bound!") == s);
}
}

TEST (index_outofbound_high, vector){
vector u(2);
try {
double ccomponent = u[3];
}
catch (string s) {
CHECK(string("Index to vector out of bound!") == s);
}

}


T32:operator []超限檢查,及拋出例外

double & vector::operator [](int i) const {
if (i <=0 || i > _dim )
throw std::string("Index to vector out of bound!");
return _v[i-1];

}

注意到 throw std::string(...)了嗎?如果只寫 throw string("...")則發生compilation error,原因是vector有一個同名的函數 string(),故以std::string(...)加以區別。另一種做法是將vector::string()改名,例如改為vector::str()。

T33:決定如何處理超限例外,做必要的程式修改
operator []變更,影響innerProduct.exe 與 linearTransform.exe。我們需要決定當vector index超限發生時,該如何處理?

首先,我們先問,使用者會不會引發超限例外?如果會,則超限例外處理的方式,需要顯考慮使用者。

以innerProduct.exe為例,程式並不會讓使用者有直接引發這個例外的機會

接著我們問,使用vector::operator []的programmer會不會所引發超限例外?注意,這裡programmer可能是你,或者其他使用你寫的vector class的programmer。同時,這個超限例外極容易發生:由於後來從1開始的使用方法顯然與operator [] 的從0開始慣用法不合,發生超限的機率就更大了。

Programmer引發這個超限例外時,我們可以說這個例外使因為程式的bug造成的。有bug的程式不該給客戶用。所以,這個決定很容易做:提示programmer這個情形後終結程式,讓programmer修復造成超限的code。

決定了超限例外處理方針之後,下一個決定是由哪一個函數來提示programmer這個情形後終結程式被賦予責任處理這個例外的函數,它的code將因增加try statement而變複雜。根據前面關於例外處理的描述,最簡單的作法是不要做任何事:
超限例外發生時,任由C++ runtime 異常終止 main函數。

以下在main中使用者輸入第一個向量之後,故意讓超限發生,程式執行不正常終止的畫面:




我寫的程式提供你參考。畫面中告訴我們程式在拋出 'std::string' 之後異常終結,並請我們連繫開發者。不論對使用者或programmer,以此方式處置一個bug,應屬恰當。

T34、T35、T36的工作請你試試看。

L步驟:

1. vector::operator [] index 由1而非0開始,有違慣例,對programmer而言,vector::operator []的使用已成bug的溫床。請將vector::operator []改名,例如vector::component(int i)或vector::at(int i)。請你試試看。

2. 前述超限例外,如果我們讓使用者輸入特定維度,為它取得向量在該維度分量,則使用者將有直接引發這個例外的機會,如果這種情形發生,程式應適度提示使用者,使他有機會更正此項錯誤,並繼續正常執行。同理,innerProduct程式有哪些地方會有此類使用者引發的錯誤?這些地方都可以改以例外的方式處理。 

© Y C Cheng, 2013. All rights reserved.

2013年10月27日 星期日

Round 7: Testing improves design

U步驟:

在測試議題上,根據Round 6回顧,列出問題如下:
SP6:建立vector與matrix輸出的單元測試。
SP7:建立vector與matrix超限功能與測試。

讓我們先解決SP6。vector物件的輸出函數在實作上讀取u的分量,適當的符號裝飾,直接使用C++ 輸出物件 cout 進行輸出:


void outputVector(vector u){
cout << "[";
for (int i=1; i<u.dim(); ++i)
cout << u[i] << ",";
cout << u[u.dim()] << "]" << endl;
return;
}

我們的問題是如何測試?前次L步驟說不該直接讓cout輸出「污染」測試輸出畫面,所以不能直接在測試中呼叫 outputVector。

結論:outputVector的可測試性(testability)不佳。SP6的目標就是改善outputVector與outputMatrix的可測試性。

D步驟:

如何改善outputVector的testability?解決方法之一,是以間接的方式測試:先讓vector u轉成一個可測試且容易輸出到cout的中間表示型式(intermediate form),再將該型式輸出到cout。假設後者均能以C++內建的方式做到,則能測試vector u轉出的中間表示型式,即能測試outputVector!

有了這個解決方案,接下來就是決定vector u轉出的中間表示型式。由於outputVector輸出是給使用者看的,直覺上字串(string)就是一個適用的中間表示型式。

列出待辦工作如下:

T23 測試 vector轉成字串。
T24 撰寫vector轉成字串的函數。
T25 修改 outputVector。
T26 迴歸測試。
T27 測試 matrix轉成字串。
T28 撰寫 matrix轉成字串的函數。
T29 修改 outputMatrix
T30 迴歸測試。

相信你已經知道如何列出這些工作了,同時這些工作已經難不倒你了!

C步驟:

完成T23、T24、T25的相關程式片段如下。
(學習課題:string, ostringstream)

T23:
TEST (outputVector, vector){

double a[3]={1,2,3};

vector u(3,a);

CHECK(string("[1,2,3]")==u.string()); }

T24:in vector.h

class vector {

...

public:
...
std::string string() const;
};

in vector.cpp

string vector::string() const {

ostringstream oss;

oss << "[";
for (int i=1; i<= dim()-1; ++i)
oss << (*this)[i] << ",";
oss << (*this)[dim()] << "]";
return oss.str();
}

T25:
void outputVector(vector u){
cout << u.string() << endl;
return;
}


T25得到的 outputVector 對當前程式功能似乎夠了,但稍加思考,不難發現它有些限制,例如輸出兩個向量

vector u(...);
vector v(...);
outputVector(u);
outputVector(v);

後二行code看起來有些小題大作。為什麼不寫成

cout << u << "\n" << v << endl; // u v 間有換行
或者
cout << u << " " << v << endl; // u v 間無換行

這看起來是個好想法,而且並不難做到,我只要 overload operator << 即可:

ostream & operator << (ostream & os, const vector & u){
return os << u.string();
}

同意嗎?matrix相關工作請自己試試看,可參考我寫的程式

L步驟:

此round我們出發時,面對的是一個測試的問題。不容易測試的函數,通常隱含著其他的問題。工作T24完成後,outputVector函數變得可測;T25完成後,你可以將 vector透過標準的operator << 輸出到 cout以外的輸出串流(output stream),如檔案(使用ofstream)、字串(使用ostringstream)等。此時outputVector即無存在的必要!故有本篇的title: 

Testing improves design.

此外,我可以說

Design to enable testing. 

© Y C Cheng, 2013. All rights reserved.

2013年10月11日 星期五

Round 6 continued: Member function or ordinary function?

接下來實作T20,線性轉換的unit test。我們需要決定線性轉換函數為matrix的member function

matrix m(...);
vector v(...);
vector u = m.transform(v);

或者一般函數

matrix m(...);
vector v(...);
vector u = transform(m, v);

功能上二者完全一樣,何者較佳?

  • 如採member function,則matrix 認得(knows) vector :vector v被當成參數傳入transform,且transform需傳回一型態為vector的值。當vector有變動時,vector test專案與matrix test專案均需被編譯、執行。
  • 如採一般函數,則matrix與vector維持獨立(independent)當vector有變動時,matrix test專案不需被編譯、執行。

下圖顯示這兩種相依關係(dependency)。左手邊的作法增加matrix對vector的耦合度(coupling),右邊則無。因此,我們決定transform將以一般函數型式存在。套用物件導向設計的說法,左手邊的作法將transform的責任(responsibility)指派(assign)給matrix,右邊則無。由此可知,

     是否增加class耦合度乃為責任指派的重要考慮因素。




接下來的問題是將transform函數放置在哪一個檔案?如與matrix同置(collocate),需在matrix.h 引入vector.h

#include "vector.h"

經過前一項不增加耦合度的設計決定後,這看起來不是一個好的安排。所以:將transform函數安置放在另二個新的檔案 linearAlgebra.h 與 linearAlgebra.cpp,建立 linearAlgebra test專案。這個專案在vector或matrix有變動時,需被編譯、執行以確保正確。

接著實作T19,含transform與rowVector兩個一般函數。transform的演算法如下(設輸入矩陣為M向量為v,輸出向量為u):

for i in 1 to M.row()
  get ith row vector of M
  u[i] = inner product(ith row vector,  v)

這是根據線性代數教科書的所寫的算法。設M為3x2矩陣,則它有三個列向量:第1、2、3列向量。u的第1個分量為第1列向量與v的內積,etc.

你發現問題了嗎?先前vector u 的第一個分量為u[0]而非u[1],或許當時受了使用index operator []的影響,並不覺得是一個問題,現在做線性轉換,卻有些出入。如何解決?有兩個方法:
  • 實作transform的演算法如下
    for i in 0 to M.row()-1
      get (i+1)th row vector of M
      u[i] = inner product((i+1)th row vector,  v)
  • 承認過去的設計有誤,修改vector::operator [],使第一分量為u[1],第二分量為u[2], 依此類推。
選擇第一個,則演算法不易被看懂(特別是對使用你的程式的工程師們),選擇第二個,則對現有使用到vector::operator[]的code有直接的衝擊。如何選擇?

我選擇承認過去的設計有誤,修改vector::operator [],雖然衝擊較大,但更正了一項意外的錯誤,並使得transform演算法的實作易懂。T19可細分為下列工作:

1. 修改vector test中直接關於operator []的測試。修改後,這些測試應會fail。
2. 修改operator [],直到operator []的測試通過。
3. 修改其他使用到operator []的測試。
4. 修改被測函數、成員函數,直至所有測試通過。
5. 測試、修正innerProduct專案,直至通過。
6. 實作transform與rowVector函數,直至linearAlgebra test通過。

最後完成T21, 建立 linear transformation project,實作主程式。

現在我們用了 vectorTest、matrixTest、linearAlgebraTest、inner product與 linearTransform等五個專案。這五個專案在DEV C++各自存在,但共用一些檔案。例如在專案vectorTest下改變了vector.cpp,則需將其他使用vector.cpp的專案,分別重新編譯、執行;這將會造成一定程度的不便,例如執行迴歸測試。我們需要的是在vector.cpp有所改變時,所有使用vector.cpp的程式自動被重建。

著眼於減少工作上的不便,追加一個工作:

T22:將五個合併專案為一個專案,建立makefile,讓Dev C++使用這個makefile而不每次重新產生 makefile。

我的做法是使用在C/C++程式開發中最常用的建置工具make。 make 讓你將程式建置的指令以目標(target)與相依關係(dependency)編寫在於一個建置腳本(build script),按照慣例,這腳本放在一個名稱為makefile的檔案中。

事實上,之前的五個專案,Dev C++根據你提供的專案資訊自動為你產生一個檔名為 Makefile.win的建置腳本。我提供makefile 即是參考這個檔案修改所得。

有了makefile以後,建立一個新專案 LinearAlgebra,加入所有延伸檔名為 .h 與 .cpp的所有檔案,並在Project options-> Makefile選項下勾選 "use custom makefile"並設定建置腳本檔名(即 makefile)即可。

你可以試著修改vector.cpp檔案。按下Dev C++ compile 鍵,所有依賴vector.cpp的建置目標vectorTest.exe、linearAlgebraTest.exe、innerProduct.exe與linearTransform.exe將會自動被重新產生。相對的,matrixTest.exe則與vector.cpp無關而不會被重新產生。

最後,記得移除原先的五個專案檔 (即延伸檔名為.dev的案),T22即告完成。

(學習課題:make)

L步驟:雖然功能不多,但程式越來越複雜(專案多、檔案多)。我們努力的控制dependency,讓變動發生時受影響的範圍盡量縮小。我們也順利地重複使用vector及inner product函數。儘管如此,我們仍需要認真地檢視有無可改善之處。目前,我們的程式具備容易測的架構,讓我們來檢視單元測試的議題。

 1. 單元測試須獨立運作。但我們測試vectorToFile 時,使用了vectorFromFile。雖然vectorFromFile被測過,但並不能保證它完全正確。E W Dijkstra的關於測試的名言:

Program testing can be used to show the presence of bugs, but never to show their absence!

測試只能用來證明bug的存在,而不能證明bug的不存在!

2. 函數outputVector與outputMatrix(m)仍未被測試,事關輸出,如果真的在console輸出,我們的單元測試 Silent unless broken的特性豈不被破壞了?

3. vector::operator []() 與 matrix::at()都未有超限 (out of bound)測試,而其實作亦未偵測。

© Y C Cheng, 2013. All rights reserved.

2013年10月10日 星期四

Round 6: Enters matrix

目前為止,我的例子只有一個class,vector。接下來,我將讓例子裡有兩個class。我仍取材自簡單的線性代數運算。



問題P2:寫一個程式,提示使用者輸入兩個分別存放一個矩陣M與一個向量v的檔案的名稱,其中矩陣M代表一個線性轉換。請計算對向量v施以該轉換所得之向量u。

u= Mv

並將u輸出到第三個使用者指定名稱的檔案。提示使用者可重複執行或結束程式。

限制:你必須儘量使用為inner product所開發的vector類別及相關函數,並在必要時增加相關函數。

U步驟:

問題P2要求的檔案輸入輸出均有C++ library可供使用,且牽涉的計算不複雜,所以我暫時將不分解成數個更小的問題。當然,如同前5輪U-D-C-L,我們後續仍有可能提出改善的sub-problem。

你可能要問我,為什麼不在一開始(round 1)的時候就把問題P2一併提出來?你的疑問很合理,我的確可以在一開始就一併提出向量內積與線性轉換等二個問題。即便如此,我並不需要一次面對個不同的問題;因為這個問題彼此間的邊界(boundary)相當清楚,分開來解是合理的做法。同時,因為解線性轉換問題時須使用向量內積,故這個解題順序仍屬合理。

除此之外,現實世界中,客戶追加需求是相當常見的情形。追加的需求,當然需要站在既有的基礎上,正像前述問題限制我們必須儘量重複使用(reuse)為inner product所開發的vector類別及相關函數。問題P2中,線性轉換u = Mv的算法,u的分量為M相同位置的列向量(row vector)與v的內積。


D步驟:


我們需要針對matrix運算與測試、線性轉換主程式建立相關專案。

由於問題要求重複使用且我們也可能需要修改或新增inner product所開發的code,在專案的安排上,我們需要繼續讓
project inner product、 project vector test維持在開發中的狀態。雖然問題P2並未要求與 inner product有關係,由於vector可能有所變動,所以project inner product需要連帶被編譯、執行以確保其正確性。

列出工作如下:


T13 設計 vector在檔案中的儲存格式,編寫讀/寫檔案函數。
T14 測試vector讀/寫檔案函數。
T15 設計matrix在檔案中的儲存格式,編寫讀/寫檔案函數。
T16 測試matrix讀/寫檔案函數。
T17 編寫 matrix類別,含data members 與 member functions。
T18 測試matrix類別。
T19 編寫線性轉換函數。
T20 測試線性轉換函數。
T21 編寫main函數。

C步驟:
先做哪個task?基於round 5結果,我們有vector test專案,因此可以先顯選擇範圍限制在處理T13(先寫 vector讀寫檔函數)或T14(先寫 vector讀寫檔函數單元測試)。 

我採取 測試先行(test first)策略,先選擇T14。好處有二:

  • 當unit test code完成時,已初步完成vector讀寫檔函數的函數原型設計。
  • unit test執行無誤時,你知道已初步完成vector讀寫檔函數的函數的實作。

T14與T13完成後,編譯、執行inner product project,確認無誤。這個動作為inner product project進行迴歸測試(Regression testing)原有的inner product 執行已達預期狀況,但它使用的class vector與函數變動了,我們需重新加以確認。

(學習課題:ifstream, ofstream, fstream)

接著,完成matrix相關測試、類別與函數,仍採測試先行,依序執行T18、T17、T16、T15。在此之前,我們仿照先前vector的做法,建立matrix test專案。

下篇繼續。

© Y C Cheng, 2013. All rights reserved.

2013年10月3日 星期四

Round 5: Unify when you can; separate when you must

U步驟:第四輪結束時,所有class與function均存放在同一個file main.cpp,如下:

main函數是一個劇烈變動點,經常透過編輯code的方式主功能(production code)測試(test code)間切換。將此問題具體敘述如下:

SP5:分割程式碼,建立測試專案,與production專案分立。

D步驟:要解決SP5,必須要使test code與product code不共用 main function。具體的做法是自innerProduct專案拆出另一個測試專案,暫時稱為 vectorTest專案,並設法讓兩個專案共用 vector, inputVector, outputVector 與 innerProduct,示意如下:


建立待辦工作如下:
T11 分割test code、vector與相關函數
T12 建立test project, 修訂inner product project。

C步驟:

T11 分割test code、vector與相關函數

1. 將main.cc中vector與相關的函數搬到二個檔案,vector.h與vector.cpp,在main.cc中引用 vector.h。編譯,修正錯誤。

2. main.cc中test code搬移至另一個檔案,vectorTest.cpp
vectorTest.cpp中引用 vector.h,編譯,修正錯誤。

(學習課題:為class與函數分別建立 header file(宣告)與 implementation file(定義),亦即 interface in .h file, implementation in .cpp file)
(學習課題:#ifndef, #define, #endif的使用)

T12 建立test project。

1. 建立 test project:vectorTest.cpp code併入 main function所在的mainTest.cpp;設定CppUnitLite 路徑;在test project中加入 vector.h、 vector.cpp;編譯,修正錯誤。

2. 移除原 innerProduct專案之CppUnitLite 路徑設定,移除並刪除vectorTest.cpp。

L步驟:現在,你已擁有 a production project and a test project各一個!接下來將能更容易的為vector及相關函數做更多測試。再度檢視待辦工作,我們發現只剩SP2了。解或不解?請你自己決定。inner product問題,將暫告一個段落。





© Y C Cheng, 2013. All rights reserved.

2013年9月26日 星期四

Round 4: Forget main; unit testing is better

第三輪結束時,我們找到一個議題:讓test code脫離 main函數存在。按照round 3的做法,test code寄生在main之下,則innerProduct函數的test code可如下:




第四輪將分離這些test code。

U步驟:檢視test code,可了解做的是針對innerProduct函數的局部測試,分別為可計算內積與不可計算內積的兩種情形。我們採取的方式是將結果輸出到console,然後自行判讀執行結果是否符合期望。用同樣的方法做更多局部測試,將出現下面的現象:
  • 當我們做的局部測試更多時,console輸出將會越來越多,不易判讀結果是否符合期望。
  • 為了省寫些test code,你可能會重複使用某些變數,例如前列中的向量u出現在兩個測試裡。你必須很確定u第一次被使用後,仍然有原來的值,否則第二次測試的test code本身就很難說是對的了。
根據測試分類,我們所做的測試屬於單元測試(unit testing),每一個目的不同的測試則稱為一個test case,所以前述test code含兩個 test case。

執行一個單元測試的test case,具備下列四步驟:
  1. 建立測試用資料
  2. 呼叫待測函數,得到結果值
  3. 比對預期值與結果值
  4. 撤掉測試用資料
C++程式單元測試框架如CppUnit、CppUnitLite等提供對test case依上述四步驟自動執行機制必要的library(例如第三步驟的比對),並提供組織test case的具體方法。使用後,將能一舉解決這些問題。 我將使用簡單易用的CppUnitLite

SP4:以CppUnitLite重作test case。

SP2與SP4二選一,我們將先解SP4。


D步驟:將SP4分割成兩個task:

T9:安裝CppUnitLite。
T10:搬移(與新增)test cases。

C步驟
依序進行T9(參考資料)與T10。完成T10後,原先在main的test code改變如下:

...
#include "C:\Program Files (x86)\Dev-Cpp\MinGW64\include\cppunitlite\TestHarness.h"
...

int main(int argc, char** argv) {
TestResult tr;
TestRegistry::runAllTests(tr);
/* 
... what main should do here
*/
return 0;
}

TEST (computable, innerProduct){
  double a[2]={0,1};
  double b[2]={1,0};
  vector u(2,a);
  vector v(2,b);
  double prod;
  CHECK_EQUAL(true,innerProduct(prod,u,v));
  DOUBLES_EQUAL(0,prod,0.00001);
}

TEST (dimension_error, innerProduct){
  double a[2]={0,1};
  double c[3]={1,2,3};
  vector u(2,a);
  vector w(3,c);
  double prod;
  CHECK_EQUAL (true,innerProduct(prod,u,w))
}

main 中兩行紅色的code使用CppUnitLite中的API,執行所有test case(這裡只有兩個)。

蓄意讓第二個test case驗證失敗: 向量u的 dimension為2,向量w的 dimension為3,所以innerProduct還傳的實際值(return value)為false,但我將期望值設為true執行後,console畫面如下:



看畫面第一列,我們的得到驗證失敗的原因(Failure: "expected true but was false")、發生的地方(line 123 in main.cpp)。值得注意的是第一個test case驗證通過,故無任何訊息。最後總計失敗的次數,共計一次

比較原test code執行後console畫面,好壞立見:



console上每一列輸出,都需要靠你自己判讀是否正確。如果判定為有錯,你得自己尋找錯誤發生在哪裡。想像你跑了100個測試,這個判讀/尋找的任務看起來還挺辛苦且易錯的!

L步驟:OK,test code與main函數已分開再次以programmer的觀點進行回顧。現在,這個功能簡單的程式達到120 Lines的規模。在裡面進行修改、新增code,經常需滾動IDE編輯視窗,programmer犯錯的機率升高。此外,啟動unit testing的API仍然與佔據main函數,需與main該做的事互相切換。

© Y C Cheng, 2013. All rights reserved.