跳至內容

傑克遜結構化編程

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
JSP圖的範例

傑克森結構化程式設計Jackson structured programming)簡稱JSP,是一種結構化編程方法,以資料流結構及程式結構之間的對應關係為基礎。JSP會將程式及資料用序列(sequence)結構、迭代(iteration)結構及選擇(selection)結構的組合來表示,適合用來設計程式的細部控制結構,若是較高層次的控制則會使用物件導向程式設計[1][2]

簡介

[編輯]

邁克爾·安東尼·傑克遜英語Michael A. Jackson在1975年在《Principles of Program Design》一書中提出傑克森結構化程式設計。[3]。傑克森的目的是要使COBOL批次檔處理程式更容易更改及維護,但此程式設計方式可用在任何有結構化流程控制的程式語言,例如C語言JavaPerl。雖然JSP已有很長的歷史,不過像微軟的Visio及像是Jackson Workbench的電腦輔助軟體工程工具仍支援JSP[4]

JSP中的許多內容和Warnier/Orr圖英語Warnier/Orr diagram有關[5][6],不過後者專注在輸出流的結構。JSP和Warnier/Orr圖都將程式及資料由序列、迭代及選擇三個結構來表示,基本上創立了正規表示式語法剖析器程式,可同時符合程式輸入及輸出的資料流。

JSP著重資料流,因此所產生的程式的結構和用其他利用像維爾特戴克斯特拉的逐步細化方法所產生程式的結構不同。JSP所設計程式的主要特點是在程式碼中會有多個輸入指令,而使用其他逐步細化方法的程式一般只有一個輸入指令。傑克森在《Principles of Program Design》的第三章,列出了二個程式以說明不同結構化程式設計的差異[3]

結構等效的二個程式

[編輯]

此程式的JSP版本如下

String line;

line = in.readLine();
while (line != null) {
    int count = 0;
    String firstLineOfGroup = line;

    while (line != null && line.equals(firstLineOfGroup)) {
        count++;
        line = in.readLine();
    }
    System.out.println(firstLineOfGroup + " " + count);
}

使用其他結構化設計方式的程式如下

String line;

int count = 0;
String firstLineOfGroup = null;
while ((line = in.readLine()) != null) {
    if (firstLineOfGroup == null
            || !line.equals(firstLineOfGroup)) {
        if (firstLineOfGroup != null) {
            System.out.println(firstLineOfGroup + " " + count);
        }
        count = 0;
        firstLineOfGroup = line;
    }
    count++;
}
if (firstLineOfGroup != null) {
    System.out.println(firstLineOfGroup + " " + count);
}

傑克遜認為使用其他結構化設計方式的程式無法表達輸入資料行之間的關係,例如將第一行的處理視為一個特例,最後一行的輸出也要用特例來處理,影響程式的可理解性及可維護性。

方法

[編輯]

JSP使用半型式化步驟來找出程式輸入輸出資料的結構,以及程式本身的結構。

其目的是建立在整個生命週期都方便修改的程式。傑克遜主要的見解是需求變更多半是針對現有結構的微小調整,針對用JSP撰寫的程式,其輸入資料結構、輸出資料結構及程式內在結構皆可對應,因此輸入及輸出的微小變化只會對應為程式的微小變化。

JSP將程式分為四種不同的元件:

  • 基本程式
  • 序列(sequences)
  • 迭代(iterations)
  • 選擇(selections)

JSP一開始會以上述四個元件來描述程式的輸入,隨後以類似的方式處理程式的輸出,每一個輸入及輸出都以獨立的資料結構圖英語Data structure diagram(DSD)來表示。針對一些密集運算的應用(例如數位訊號處理),也需要繪製演算法結構圖,著重在內部資料的結構,而不是輸入或輸出資料的結構。

輸入及輸出的結構之後會整合成最終的程式結構,稱為程式結構圖(PSD)。其中可能包括加入少許的高階控制結構,整合輸入及輸出的特性。一部份程式是處理產生輸出前的所有輸入資料,其他程式則是以迴圈的方式,先讀取資料再輸出資料,在產生程式結構圖時需找到類似的結構。

隨後程式結構圖會以程式語言來實現。JSP著重在程式的控制結構,因此實現時只會用到基本程式、序列、迭代及選擇。JSP沒有使用類別及物件及層次來架構程式,不過使用類別的方法也有助控制流程的結構化。

JSP使用圖像的表示法來描述輸入、輸出及程式的結構。

基本程式會以方塊來表示。

一個標示為A的步驟
一個標示為A的步驟

一連串的程式會用以直線相連的方塊表示,圖例中,步驟A之後為步驟B、C、D。

一個標示為A的步驟,之後是B、C、D的步驟
一個標示為A的步驟,之後是B、C、D的步驟

迭代的步驟也是用相連的方塊來表示,要迭代的步驟方塊右上角會有一個星號。圖例中,步驟A包括執行0次或多次的步驟B。

一個標示為A的步驟,下方的B步驟右上角有一個星號,表示B步驟會進行迭代
一個標示為A的步驟,下方的B步驟右上角有一個星號,表示B步驟會進行迭代

選擇的步驟也是用相連的方塊來表示,待選擇的步驟方塊右上角會有一個圓形。圖例中,步驟A會選擇執行步驟B、C或D中的一個步驟。

一個標示為A的步驟,下方的B、C和D步驟右上角有一個星號,表示會由這些步驟中選擇一個執行
一個標示為A的步驟,下方的B、C和D步驟右上角有一個星號,表示會由這些步驟中選擇一個執行

實例

[編輯]

以下以一個遊程編碼的程式來說明JSP的設計方式。遊程編碼是指一個程式的輸入是位元組的資料流,其輸出的資料由位元組及此位元組連續出現的次數所組成,遊程編碼常用在點陣圖的壓縮。

利用JSP設計程式,首先是描述程式輸入的結構,遊程編碼只有一種輸入,是由零個或多個「遊程」所組成的資料流,每個「遊程」為一個位元組,或是多個相同數值的位元組,上述結構可以用以下的JSP圖表示:

遊程編碼的輸入
遊程編碼的輸入

第二步則是描述程式輸出的結構,遊程編碼的輸出可視為零到多對資料的資料流,每一對資料包括一個位元組和其出現的次數,在此例中,次數也用位元組來表示:

遊程編碼的輸出
遊程編碼的輸出

下一個步驟是描述輸入結構及輸出結構之間程式的相關性:

輸入和輸出之間的關係
輸入和輸出之間的關係

有時程式設計者在此階段會遇到結構衝突的問題,也就是輸入及輸出結構之間沒有明顯的關係。若出現結構衝突的問題,可以將程式分為二部份,二部份程式之間有共通的資料,二部份的程式可以用共通的資料作為共同的控制框架,這二部份程式常常會用行程協程的方式來實現。

此例沒有結構衝突的問題,因此二個資料結構可以合併為以下的程式結構:

此時程式可以加入對應的基本程式來充實其內容,基本程式如下:

  1. 讀一個位元組
  2. 記錄一個位元組
  3. 設定計數器為零
  4. 計數器遞增
  5. 輸出記錄的位元組
  6. 輸出計數器

也需要找到程式中迭代的部份,迭代的部份如下:

  1. 當還有位元組時
  2. 當還有位元組、位元組和記錄的位元組相同、而且計數器數值仍可以用位元組表示時

若整合上述所有的資料,可以將圖和基本程式以C語言來表示,並且在程式碼、動作及程式設計圖的結構之間建立一對一的對應關係。

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

int main(int argc, char *argv[])
{
    char c;

    c = getchar();
    while (c != EOF) {
        char count = 1;

        char first_byte = c;

        c = getchar();

        while (c != EOF && c == first_byte && count < 255) {
            count++;
            c = getchar();
        }

        putchar(first_byte);
        putchar(count);
    }
    return EXIT_SUCCESS;
}

相關條目

[編輯]

參考資料

[編輯]
  1. ^ R. Wieringa (1998). "A survey of structured and object-oriented software specification methods and techniques". in: ACM Comput. Surv. 30, 4 (Dec. 1998), 459-527. DOI= http://doi.acm.org/10.1145/299917.299919
  2. ^ Brian Henderson-Sellers and J.M. Edwards (1990). "The object-oriented systems life cycle". In: Commun. ACM 33, 9 (Sep. 1990), 142-159. DOI= http://doi.acm.org/10.1145/83880.84529
  3. ^ 3.0 3.1 M.A. Jackson (1975). Principles of Program Design. Academic Press. 1975
  4. ^ Nicholas Ourusoff. Using Jackson Structured Programming (JSP) and Jackson Workbench to Teach Program Design (PDF). InSite 2003. Informing Science. 2003 [2008-02-18]. (原始內容 (pdf)存檔於2011-07-26). 
  5. ^ K.T. Orr (1980). "Structured programming in the 1980s". In: Proceedings of the ACM 1980 Annual Conference ACM '80. ACM Press, New York, NY, 323-326. DOI= http://doi.acm.org/10.1145/800176.809987
  6. ^ J.D. Warnier (1974). Logical Construction of Programs. Van Nostrand Reinhold, N.Y., 1974

外部連結

[編輯]