Round 3: All bundled -- vector as object

Round 2回顧中找到的議題：向量及其維度應能確保一致。我們將以C++的class加以解決。進入第三輪。

U步驟：我們需要一個策略。由於我們的目的是減少programmer犯錯的機會，因此採取策略：檢視program code，找出容易導致programmer犯錯的code。

先看一個程式片段：

上面main函數讀起來，可以說是以u這個變數表示向量；和向量u的定義、使用相關的敘述有 

• line 51: int dim_u; (向量的維度) 
• line 52: double * u; (double 指標，指到向量記憶體中的位置)
• line 55: u = new double[dim_u];(配置記憶體，佔用連續的dim_u個double，u為這塊記憶體的beginning address) 
• line 71: delete [] u; (釋放u佔用的記憶體)
• line 36 (and other lines): p += u[i]*v[i];(取用第i個分量)

簡單以下圖表示它們之間的關係：

我們發現programmer需自行關聯double vector[]、int dim；兩者也與 double * 宣告、new 運算子、delete運算子、與index 運算子 [] 等有關係，這些關係都得靠你自己記住；C幫不上忙！ 「C是個相對低階的語言」這種說法，果然不是隨便說說的。

好消息：C++可以幫上忙！C++的class可以讓我們把這些構成向量的變數、變數間的關係、變數與運算子間的關係做一個統合。

壞消息：你得學會如何將散落各處的資料、函數打包。(好吧，這算不上是一個壞消息 :) 

列出新的子問題如下：

SP3: 統合向量相關變數、運算、函數，以物件表達，修改相關函數，使其接受並使用向量物件。

當此問題解決後，programmer使用物件時不需自行關聯獨立的變數。

現在未解的問題有SP3 及 SP2，讓我們先解 SP3。

D步驟：如何列出工作？

T7 宣告新的向量型態，決定它打包的資料與函數。
T8 修改相關函數以使用新的向量型態

更新待辦工作如下：

C步驟：先做T7。將新的類別型態(class type)稱為vector，經過U步驟地分析得知，

• vector類別型態打包兩項資料double []與int (學習課題：class, data member, member functions, private, public)。
• 定義vector類別型態變數的建構元(constructor) (學習課題：constructor, initialization list, dynamic memory allocation, zeroing)
• 回收被vector類別型態變數佔用的記憶體用的解構元(destructor) (學習課題：scope and lifetime of a variable, destructor, memory deallocation)
• 向量分量取用函數(accessor function)(學習課題：operator overloading, return by reference) 
• 向量維度的讀取函數(getter function) (學習課題：const member function)

括弧中為C++ 相關的學習課題，你可以找任何一本C++書或任何C++ web site，直接閱讀與學習課題相關的頁數/內容，直到你可了解下面的code即可：

class vector {
private:
double * _v;
int _dim;
public:
vector(int dim):_dim(dim){
_v = new double[_dim];
for (int i=0; i<_dim; ++i)
_v[i]=0;
}
~vector() {
delete [] _v;
}
double & operator [](int i) const {
return _v[i];
}
int dim() const {
return _dim;
}
};

畫張類別圖(class diagram)來表示vector打包的資料與函數：

有了 vector class 型態，接著處理T8。

T8的學習課題：model of a variable in memory, runtime memory model of a program, call by reference vs call by value, copy constructor, deep copy vs shallow copy。

原 main函數片段

可修改如下：

新程式line 70

    vector u(dim_u)；

呼叫建構元，定義vector型態的物件u，它的維度為dim_u；line 70 取代原程式line 51, line 52及line 55。

新程式line 71

    inputVector(u);

取代舊程式line 56，

    inputVector(u, dim_u);

呼叫inputVector時只需傳入vector型態的物件u，而不傳入它的維度dim_u。

完成的程式請點連結下載。

L步驟：請檢查round 3的程式碼是否優於前一版，讓programmer犯錯的機會減少。

除此之外，讓我們再次以programmer的觀點進行回顧。這次，回想自round 1起，我們為求方便，每當完成一個工作時，(例如round 1中的innerProduct函數，)經常借用main函數來測試這個工作完成的code。(例如，準備好兩個向量，將作為參數他們傳給innerProduct函數做計算，然後將結果輸出到console：見round 3程式。)

/*
double a[2]={0,1};
double b[2]={1,0};
double c[3]={1,2,3};
vector u(2,a);
vector v(2,b);
vector w(3,c);

double prod;
if (innerProduct(prod,u,v))
cout << "inner product is " << prod << endl;
else
cout << "Dimension error!" << endl;

if (innerProduct(prod,u,w))
cout << "inner product is " << prod << endl;
else

cout << "Dimension error!" << endl;

*/

注意到這些code被註解掉了嗎？因為後來我們需要 main 函數做它該做的事！在HTSI的U-D-C-L迴授圈中的C步驟，這些測試碼 (test code)擔負著驗證工作是否完成的責任，但是它們卻「寄生」在main函數之下。

我們找到一個議題：讓test code脫離 main函數存在。

© Y C Cheng, 2013. All rights reserved.

Round 2: Look back as a programmer

L步驟：SP1已順利解決，程式處於可執行、可驗證的狀態。儘管SP2尚未解決，我們仍可(1)決定是否程式已達要求？如是，則表示程式將被釋出且暫時不解SP2。(2)探索有無其他議題。如有，則表示進入下一輪時，我們除SP2外，有選擇其他議題的空間。

此次，讓我們以programmer的觀點來回顧程式：看程式碼。

身為programmer，你在乎的事情必然與程式有關。手邊的程式的寫法是否容易讓自己或其他programmer寫出錯誤的程式碼？程式是否容易閱讀、編輯？程式是否容易維護(新增功能、修改或拿掉既有功能)？程式是否容易測試，會不會很耗時間、且經常造成遺漏一些該測而未測的項目？

山頭很多，你得決定要攻哪一座。由於現在程式規模仍小，測試也不太難〈雖然測使用者輸入時將會費一番功夫，但我們尚未深入考慮SP2，此時尚無具體可回顧的測試項目〉。所以讓我們選擇找出容易導致自己或其他programmer犯錯的程式碼。

檢視程式，可發現向量及其維度分別以double []型態與 int型態的兩個值表達。例如，

void outputVector(double v[], int dim);

呼叫時，你必須自行關聯這兩個值，確保它們的正確性：

outputVector(u,dim_u);

如果u=[1,1]而dim_u = 3，那麼ouputVector將會應出錯誤的向量(例如[1,1,-347292697])。

同樣的問題也發生在

bool inputVector(double v[], int dim);

及它的呼叫：

cin >> dim_u;
u = new double[dim_u];

inputVector(u,dim_u);

事實上，上面程式片段的代表維度的變數 dim_u 的值可被任意(有意或無意)修改；一旦被修改，則向量及其維度一致性即遭到破壞。我們因此找到一個議題：向量及其維度應能確保一致。 

讓我們進入下一輪。

© Y C Cheng, 2013. All rights reserved.

Round 2: Improvements

回顧(L)讓我們得知程式有使用者相關的議題仍待解決。這讓我們有理由進入第二輪U-D-C-L。

U步驟：這兩個議題都和使用者有關，但它們在第一輪進行時並不明顯。事實上，我們可以說透過操作第一輪得到的working software，我們發現了與原問題息息相關的新問題 -- 在正常操作下，程式必須強健；使用者犯錯時，程式必須能容忍並引導使用者。

我們將增加兩個子問題(sub-problem)：

SP1. 身為使用者，當我輸入的兩個向量維度不同時，程式在示警後，仍能正常執行。

SP2. 身為使用者，當我輸入的向量格式不對時，程式在示警後，仍能正常執行。

SP1與SP2屬於改善程式品質的需求。我們以使用者觀點寫下這些需求，前半段敘述使用者的動作：

        身為使用者，當我輸入向量格式不對時，...

後半段敘述程式採取的措施：

        .... 程式在示警後，仍能正常執行。

這種寫法稱為user stories，廣泛地使用於敏捷開發(agile development)，例如Scrum。你可以調整出自己的寫法，但以使用者觀點列出的需求，都應該包含這兩個元素。

先做哪個？SP1發生於原問題期待的正常操作下：
...
    [1,0] 與 [1,1,0] 提示無法計算內積。
...
而SP2則進一步涉及使用者犯的錯誤，需要能解析使用者的輸入，問題較為複雜。

在此第二輪，讓我們先處理SP1；SP2以後再說。

D步驟：為SP1增加兩個工作：

T5. 修改內積計算函數，使其在傳入的兩個向量維度不同時，避免結束程式的執行。
T6. 修改主程式，改用新的內積函數。

D步驟完成。我們的問題與工作列表如下：

C步驟：先做T5。

完成程式如下：

/* T2 inner product */
double innerProduct(double u[], int dim_u, double v[], int dim_v){
double p=0;
if (dim_u != dim_v){
cout << "Dimension error!" << endl;
exit(EXIT_FAILURE);
}
else {
for (int i=0; i < dim_u; ++i){
p += u[i]*v[i];
}
return p;  
}
}

/* T2(R1), T5(R2) inner product */
bool innerProduct(double *product, double u[], int dim_u, double v[], int dim_v){
double p=0;
if (dim_u != dim_v){
return false;
}
else {
for (int i=0; i < dim_u; ++i){
p += u[i]*v[i];
}
*product = p;
return true;  
}
}

原來的innerProduct回傳double，不能涵蓋兩向量維度不同時之回傳，選擇以exit(EXIT_FAILURE)結束程式。新
的innerProduct則回傳bool - 內積可計算時回傳true，否則回傳false - 並增加一個輸出參數 prod，在可計算時回傳內積值。

接著做T6，修改主程式如下：

/* T3(R1), T5(R2) main */
int main(int argc, char** argv) {
        ...
char ch = 'c';
while (ch == 'c'){
                            ...
double prod;
if (innerProduct(&prod,u,dim_u,v,dim_v))
cout << "inner product is " << prod << endl;
else
cout << "Dimension error!" << endl;
...
  }
cout << "bye..." << endl;
return 0;
}

新舊二版innerProduct可並存，因新版多了一個參數，C++認定二者是不同的函示。此稱為function overloading：一個function名稱，二(或以上)個意義。留下舊版？當然不，因為它有錯；有錯的程式不該被留下來，以免日後混淆！


編譯、執行程式以驗證達到預期改善：

L步驟下篇繼續。

© Y C Cheng, 2013. All rights reserved.

Look back to keep getting better

第一輪C步驟結束時，我們得到一個可執行、可驗證的程式。接著進行L步驟：回顧，其的目的是為了讓程式變得更好，找出值得改善的議題，為進入第二輪做好準備。如果程式已經無懈可擊，找不到改善議題，則可宣告做完。當然也有可能時間已經用盡，只好宣告結束。這時候，你會慶幸至少程式是可執行、可驗證。你不想只把程式的「屍體」交出去吧！

一個程式至少有兩種回顧的方式：其一是把自己當user，看看這個程式跑起來如何？其二是把自己當programmer，看看這個程式是否乾淨、易讀、好修改？這一篇我將以user觀點回顧目前的程式。

*   *   *

User拿到程式的自然反應：把它跑起來看看！前文中程式執行的畫面，當使用者一切均依據提示完美輸入，程式看起來相當好。眼尖的讀者會注意到最後一次計算內積，兩個向量維度不同，在印出"Dimension error!"後，程式就結束了。很顯然的程式強健度不夠。

  

再回到使用者的角色，使用者還會在哪裡遭遇困難？我們的程式要求輸入向量，使用者須打相當多個字。即使使用者極為小心，他可能犯各種錯誤，例如：

• 使用者說向量維度是m，卻提供一個n維向量，n  != m。
• 向量格式錯誤。

實驗一下即可知道，程式行為變得怪異，再次顯示其強健度不夠。

這樣的回顧可繼續下去，但我們先暫時打住。下一篇進行第二輪U-D-C-L。

Action! Round 1

問題：寫一個程式，提示使用者輸入兩個向量，計算它們的內積(inner product)。例如，
    [1, 0] * [1, 1] = 1
    [1, 1, 0] * [0, 1, 1] = 1
    [1,0] 與 [1,1,0] 提示無法計算內積。
提示使用者可重複執行或結束程式。

這個問題相當單純，並不需要拆解成子問題。以下實施第一輪How to solve it 四個步驟解題。

1. U：如題目中的例子，問題的輸入為兩個向量，維度未必相同；問題的輸出則如下：當輸入向量維度相同時，輸出向量的內積，否則提示無法計算。

2. D：列出解決該問題所需做的所有程式待辦工作及其驗證方法。初步列出的工作如下：

T1. 撰寫函數，使其能讀入向量。
T2. 撰寫函數，接受兩個向量，計算內積，或傳回錯誤訊息。
T3. 撰寫主程式，使其能讀入兩個向量、進行內積計算、呈現結果。

每個工作的設計表示我們對實施的方有了某種決定。工作T1表示，我們決定要「讀入一個向量」，並以適當的方式表達所讀入的向量。

如何驗證T1？我們先以輸出向量的方式，自行目視驗證；因此增加T4：

T4. 撰寫函數，接受一個向量，並加以輸出。

我們暫時以{T1,T2,T3,T4}為待辦工作。這四個工作並無特定的先後順序；理論上，你可以將這四個工作交給四個人同時去做。

3. C：在這個步驟裡，你須完成{T1,T2,T3,T4}這四樣待辦工作。雖然你可自由挑選，但我建議你一次只選一個工作加以完成並驗證。

以這個題目而言，我們將先挑看似最簡單的工作T4先加以完成。問題來了，我們需要一個協助驗證T4的手段。一個直接可行的方法即是在主程式呼叫它，在此先借用main。程式在Dev C++ 5.4.2 下完成。

#include <iostream>

using namespace std;

/* T4 Writing [0,1] */
void outputVector(double v[], int dim){
cout << "[";
for (int i=0; i<dim-1; ++i)
cout << v[i] << ",";
cout << v[dim-1] << "]" << endl;
return;
}

int main(int argc, char** argv) {

 /* scratch main: help to code up the tasks */
double a[2]={0,0};
outputVector(a,2);
    
    return 0;
}

程式中除了cin 與 cout為C++提供輸入、輸出的物件之外，只使用C language features。函式 outputVector (double v[], int dim) 以array v表示題目中的數學向量，dim為其維度。編譯、執行上述程式即可判斷T4是否初步完成。我說初步完成的原因是後續做其他工作時，可能需要修改其他初步程式。

接下來完成T1、T2與T3，程式如下:

#include <iostream>
#include <stdlib.h>

using namespace std;

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

/* T4 Writing [0,1] */
void outputVector(double v[], int dim){
    cout << "[";
    for (int i=0; i<dim-1; ++i)
cout << v[i] << ",";
cout << v[dim-1] << "]" << endl;
return;
}

/*T1 Reading [0,1]*/
void inputVector(double v[], int dim){
cout << "input a vector of dimension " << dim <<" :";
char s;
cin >> s;
for (int i=0; i<dim-1; ++i)
cin >> v[i] >> s;
cin >> v[dim-1] >> s;

return;
}

/* T2 inner product */
double innerProduct(double u[], int dim_u, double v[], int dim_v){
double p=0;
if (dim_u != dim_v){
cout << "Dimension error!" << endl;
exit(EXIT_FAILURE);
}
else {
for (int i=0; i < dim_u; ++i){
p += u[i]*v[i];
}
return p;  
}
}

/* T3: main */
int main(int argc, char** argv) {

/* scratch main: help to code up the tasks
double a[2]={0,0};
outputVector(a,2);

double b[2];
inputVector(b,2);
outputVector(b,2);

cout << "inner product is " << innerProduct(a,2,b,2) << endl;

double c[3];
inputVector(c,3);
outputVector(c,3);
cout << "inner product is " << innerProduct(b,2,c,3) << endl;
*/
cout <<"This is vector inner product program.\n"; 

char ch = 'c';
while (ch == 'c'){
int dim_u, dim_v;
double *u, *v;
cout <<"Input dimension of first vector:";
cin >> dim_u;
u = new double[dim_u];
inputVector(u,dim_u);
outputVector(u,dim_u);

cout <<"Now input dimension of second vector:";
cin >> dim_v;
v = new double[dim_v];
inputVector(v,dim_v);
outputVector(v,dim_v);

cout << "inner product is " << innerProduct(u,dim_u,v,dim_v) << endl;

delete [] u;
delete [] v;

cout << "Type c to continue, anything else to quit:";
cin >> ch;
cout << endl;
}
cout << "bye..." << endl;
return 0;
}

執行程式畫面如下:

4. L：程式執行畫面看起來似乎有達到要求？就算有，程式有無可改善之處？下回待續。

© Y C Cheng, 2013. All rights reserved.

The U-D-C-L feedback loop

應用 How To Solve It方法寫程式時，並不期望將四個步驟實施一次即能解決問題；通常這四個步驟需重複實施，構成一個U-D-C-L迴授圈(feedback loop)：

U--D--C--LU--D--C--LU ... U--D--C--L
1---------2---------3-... n--------done!               

每一U-D-C-L迴授圈為一輪(one iteration)。在每次實施L步驟時，手邊得到程式必須是一個可執行、可驗證是否完成的 working software。L步驟執行就是迴授：你想確認問題是否已經解決？如L步驟回顧的程式仍不能滿足做完(done)的條件，則找出待解決的議題，並進入下一輪 -- 仍以U步驟為首，因為前一次L可能讓你對問題有了新的理解。

你可能要問：為什麼不一次做完？原因很多，例如程式具相當規模，你想先完成關鍵架構，再完成其他部份；問題夠複雜，你決定先加以分解成數個子問題，逐步個別解決與整合，直到整個問題被解決為止；程式中使用到一個關鍵的技術，你仍不知道會花多少間才能完成，故你想先以一個簡單的作法實現；等等。

對已熟悉C語言但初學C++者而言，這個作法可讓他先以已知的C language features先將問題大致解決，暫不去理會C++特有的 language features，然後在回顧中，列出必要的C++ language features 學習議題，並在稍後的U-D-C-L迴授圈加以完成。從學習的角度來說，這讓學習者在學習相關C++ language features時有特定的目標。


舉個例子。初學者第一次撰寫C++ class時的建構元（constructor）時，經常會被引導去讀完不同建構元的定義方式與規則，如default constructor、copy constructor、data member 初值化等。這些規則可以輕易的塞滿教科書的一整章！你可以查看常見的C++教科書，輕易的印證這個觀察。


我並不是說C++教科書不應該把建構元相關的規則、例子集中在同一章，因為這樣作有它的好處，例如便於查閱。但身為學習者，你必須瞭解這樣的編排並非要你從 第一頁讀到最後一頁；在適度的引導下，你應該可以選擇性的閱讀必要的內容--以完成當下這一個工作為範圍--漸漸的學完大部分的C++ language features。

How To Solve It的目的之一是提供這樣的一個導引。下一篇文章，我將用一個例子來說明。

© Y C Cheng, 2013. All rights reserved.

Introducing "How to solve it: OOP"

寫軟體應該是一件有趣的活動，因為許多人自願的開發了許多軟體供眾人使用。寫軟體也可賺錢，許多人以此維生。世上有這麼多軟體、有這麼多人寫軟體， 也必然代表寫軟體這件事並不是相當困難。至少，寫軟體應不至於困難到僅僅有只有少數人知道如何做。但對一個初次學習寫軟體的人，不管他是科班的學生（如大 學裡的資訊、電機、電子、數學相關科系的學生）或是一般人仕（不要弄錯，很多傑出的軟體開發者為非本科畢業生），他需要一個簡單而且易學的方法，以支持他 學習寫軟體相關的技能。

個人多年來教授程式設計、軟體開發等相關課程，經常遇到學習者即便在撰寫簡單的程式時，仍遭遇極大的障礙。傳統上的障礙來自於程式語言本身的語法、語意挑戰，我們將這個現象稱為符號障礙(symbolic barrier)，如正確的撰寫一個迴圈、主程式與函數、參數的傳遞、區域變數與全域變數的使用等。如同學習一個外國語言，學習者需要為這些基本規則加以掌握，才能寫出使用該外國語言者看得懂得文章[1]。目前市面上已有許多優異的教科書或參考書，足以有效的解決symbolic barrier的問題。

除了符號障礙以外，寫軟體面臨的問題仍有：工作習慣養成、如何從程式到軟體、個人到團隊等問題。在學校養成良好工作習慣，有助於學習者日後發展。唯有解決這些問題，學習者才能在寫軟體的工作上漸漸的步入坦途，而能將其心力專注在解決實際問題上。

寫這個部落格的動機在於提出一個簡單、有效、且學習者可養成工作習慣的方法，以有效克服這些障礙。我將以數學家George Pólya著稱於世的How To Solve It解題方法中所揭櫫的四個步驟為基礎，提出一套簡單、易學、易養成習慣的方法，使學習者在極短的時間內即可開始寫出有意義的程式，不再只為學習克服程式語言的符號障礙而寫一些無用的程式。

How To Solve It的四個步驟為瞭解問題(understanding the problem)、規劃解法(devising a plan)、依規劃解題 (carrying out the plan)與回顧(looking back)。數學問題分成problem to prove 與 problem to solve兩大類；借用How To Solve It於寫軟體，則典型的問題為problem to solve：建造一個程式以解決問題。套用到寫程式，這四個步驟為 ：

1. 瞭解問題(U)：程式的需求為何？具體而言，程式的輸入資料為何？程式的輸出為何？限制為何？
2. 規劃解法(D)：列出解決該問題所需做的所有程式待辦工作。
3. 依規劃解題(C)：一次挑出一個待辦工作，加以完成並驗證。
4. 回顧(L)：並檢視程式，提出待改善之處，列入待辦工作中。

往後，我將分別以U, D, C, 與 L表示這四個步驟。這四個步驟如何實施將在後續文章中討論。由於這個部落格的目的是提供有程式經驗的學習者進一步學習，我想先指出我用的一個學習策略: 進行C步驟『依規劃解題』時，如需使用一個特定的程式construct時，我將不會假定學習者已經學過所有的相關的語言規則並能使用最好得寫法來完成程式。取而代之的，我將使用just-enough與just-in-time的學習策略，專注在解題上，即做出working software 。

舉例而言，後文中物件導向版的向量（vector）的例子裡，先只定義一個夠用的建構元（constructor），讓學習者能定義向量物件後，即開始 解決向量計算的問題，而避免進入所有形式的建構元的詳細介紹。在另一方面，這個策略下寫出來的程式可能不夠好甚至不正確。此時，How to solve it的L步驟『回顧』中，學習者將有機會檢視現況，並提出下一階段可進行的改善作法。

How to solve it 適用於所有語言的學習。這個部落格的短文中採用的例子裡，我將假設你已經寫過C程式，並準備學習C++語言。

---

[1] 這裡以『寫』取代一般的『聽、說、讀、寫』，以彰顯『寫』對語法、語意上的要求，高於聽、說、讀的要求。

© Y C Cheng, 2013. All rights reserved.