第一章　程式語言與系統開發入門

1-1-1 程式語言發展的5大階段: 程式語言programming language是我們和電腦溝通的工具,用程式可以讓人類指揮電腦工作

第1代語言: 機器語言,完全以電腦能夠直接處理的1與0的位元串來表示運算的步驟,不同的電腦使用的機器語言也都不一樣

第2代語言: 以一般人比較好理解的字元來表示機器執行的指令,不過處理時會多所謂的「組譯」的動作,將組合語言轉換成機器語言

第3代語言: 高階語言,在語法上更容易理解,設計上具有通用的特性,所以用高階語言寫的程式能在不同的電腦上執行

第4代語言: 以使用者為中心,以解決問題為導向的語言,目的是希望達到簡單易用,提高設計者的生產力, ex. 整合性的CASE(Computer-aided software engineering)工具,資料庫系統的SQL語言

第5代語言: 自然語言,代表語言本身在使用上接近一般的口語,大幅降低使用上的技術門檻

1-1-2

為什麼需要學程式語言？ 從理論上的學習可以幫助人們設計出更好用的程式語言。 學習使用實際的程式語言可寫出解決問題的程式來。

和電腦溝通: 進行的工作或是要解決的問題必須有很明確的描述,同時也有預期達成的結果。 把工作進行的程序詳細的寫出來。 把程序轉化為以程式語言寫成的程式 (Program),就可以交由電腦來幫我們完成所要進行的工作。

1-2-1-1

1. 寫好的程式儲存在周邊設備的儲存設備, 2. 程式執行前,要先放到記憶體中, 3. 程式一行一行地交由CPU執行,透過算術與邏輯運算,register儲存執行的指令與資料,4.程式執行的結果可以列印或是經由網路傳送出去,先經由匯流排儲存在主記憶體,再傳送至列印或網路設備

1-2-1-2語言的抽象化: 以機器語言層次的程式來處理比較簡單的語言寫出來的程式。 用一種比較平易親和的程式語言來撰寫程式。 轉換成機器語言，交由CPU 來執行。

程式語言與機器語言之間的轉譯: 以機器語言存在的系統程式能做程式語言與機器語言之間的轉譯。 這一類的程式被稱為「編譯器」(Compiler)或是「直譯器」(Interpreter)。 Fortran、COBOL、Pascal、C、C++、Basic、 Java、Ada等都是有名的程式語言。

也有自然語言(Natural language)方面的研發，希望能把與電腦之間的溝通更進一步地簡化。

1-2-2-1 程式語言發展史

1950年代中期就有高階語言出現, ex. Fortran, APL.

1960-1970年代初期, ALGOL的發展對程式語言產生很大的影響

1980年代是物件導向程式語言盛行的時期,雖然觀念早就有了,真正把它應用在程式開發上還是由於程式語言的發展

1990年代很多程式成為整合開發工具的一部分, ex. Object-PASCAL, VBASIC, C++, Java, script language.

1-2-2-2 各種程式語言

ALGOL60對於程式語言的發展有相當深遠的影響, ALGOL(ALGorithmic Orientic Language)的出現產生了以BNF來表示程式語言語法的方式,ALGOL60的特徵,向結構化的程式片斷、遞迴等,都影響了後來程式語言的發展

BASIC(Beginners All-purpose Symbolic Instruction Code)是大眾熟知的語言,語法簡易,早期在PC上幾乎人人都曾以BASIC撰寫過小程式,現在的Visual BASIC就保持了BASIC的風格

程式語言C在1970年代早期產生於貝爾實驗室,曾用來撰寫UNIX的作業系統,由於UNIX在學術界和工商應用上的普及率很高,使C語言的重要性大增,成為很多系統程式的語言,C++是C加上物件導向特性以後發展出來的語言

COBOL(COmmon Business Oriented Language)在商業應用的資料處理上跟著IBM的大型主機一起盛行,雖然已有式微的趨勢,仍然可看到Object-oriented COBOL這種重新包裝過的現代COBOL語言

FORTRAN(FORmula TRANslation)用來解決科學計算問題,是很多理工專業的人最早接觸的程式語言,在運算的表示上有特殊的功用

Java與C#是近年來相當熱門的程式語言,Java是從C++改進而來的,具有相當完整的物件導向特性,由昇陽Sun主導其發展;C#在語法上也跟C++很類似,但是兼具Visual BASIC的簡易性,C#由微軟主導其發展,與Java形成軟體開發市場上兩大主流

LISP(List Processing)和其他語言比較有很大的差異,以函數的表示法為基礎,LISP程式的執行完全是函數的計算,整個程式看起來就像一個大串列List,裡頭函數傳出的值成為外頭函數處理的參數

PASCAL和ALGOL很類似,是結構化程式設計盛行的主要助力,1980年代最常用的程式語言, turbo PASCAL早期提供了相當簡單又好用的PASCAL開發環境

Prolog是有名的AI語言,以邏輯為程式設計的基礎,使用者用Prolog的語法描述事實與規則,程式執行時會依照規則做邏輯式的推論與結論

Smalltalk也是一種特殊的語言,以物件導向模型為基礎,同時運用圖形化的介面讓使用者進行程式設計,具有極佳的互動性, ex. Transcript show: ̀́hello world!́

1-2-3 透過使用來了解一種語言

不同的程式語言表現出不同風味，引發的不同的思考模式。

能讓我們看到解決問題的各種方式。

程式語言的開發環境很多，有不少是公用程式。

1-3-1-1程式語言的組成

一個程式語言最主要的組成是其語法 (Syntax)與語意 (Semantics)。 語法代表程式語言所提供的語言，會決定寫出來的程式的外觀。 語意代表各種語法所描述的功能，以及被執行時 產生的作用。

簡單的程式實例 X:＝Y;

X和Y 代表程式變數(program variable)的名稱。 在語法上我們使用了指定(Assignment)的描述，即符號 「:＝」。 在語意上表示將Y 的值指定給X。 執行的時候，系統會把儲存在Y 位址的值寫入X 位址所對應的儲存空間，也就是記憶體中特定的位置。

程式語言文法主要的成分: 終結符號 (Terminal symbol), 非終結符號 (Non-terminalsymbol), 產生規則 (Production), 目標符號 (Goal symbol)

文法規則的觀念

1-3-1-2 BNF表示法的實例: 兩條文法規則說明一個有效的語法可由[x]y{<money>}組成,非終結符號money可以是10, 20或是30. 垂直分隔線(|)代表「或」的意思。從這兩條文法規則中可以看到x, y, 10, 20, 30為終結符號, goal為目標符號。

<goal>:=[x]y{<money>}

<money>:=10|20|30

文法必須遵守的法則: 1. 非終結符號在文法規則的左半部必須至少出現過一次,這樣我們才知道非終結符號由那些其他的符號組成。2. 目標符號不能出現在任何文法規則的右半部,因為目標符號是由其他的非終結符號及終結符號來描述的,也是一個有效語法的代稱。

1-3-1-3 運算式的文法:

1. <運算子句>::=<運算式>=

2. <運算式>::=<數值>[<運算元><運算式>]

3. <數值>::=[<正負號>]<位元組>[<位元組>]

4. <位元組>::=<位元>[<位元組>]

5. <位元>::=0|1|2|3|4|5|6|7|8|9

6. <正負號>::=+|-

7. <運算元>::=+|-|*|/

運算公式的推演: 從目標符號開始,也就是<運算子句>,把25-37=當成一個<運算子句>,依照規則1,25-37必須是一個運算式,因為這樣25-37=才能取代成規則1右邊的表示法。依照規則2, 25可看成一個數值, -37可拆成運算元-與運算式37. 依照規則3與規則4,發現25的確是個數值。依照規則2,可繼續將37看成是數值3、運算元與運算式7的組合(單一的數值也可看成是一個運算式). 25-37=

1-3-1-4 文法分析的實例:

<goal>::=I-<verb>-<person>-{<amount>}-[dollars]

<verb>::=own|lend

<person>::=you|her|him

<amount>::=1|2|3|4|5

判定下面的句子是否合乎上面的文法:

I-own-her-21232-dollars. (V)

I-lend-you-12600-dollars. (V)

you-own-him-25-dollars. (X)

I-lend-her-255. (V)

1-3-2-1 方法論

每一種語言的語法都會有差異,從程式語言所做的方法論Paradigm來做分類,比較容易找到同一類的語言;常見的程式語言方法論有4種: 1. 命令式的imperative, 2. 函數式的functional, 3. 邏輯式logic, 4. 物件導向的object-oriented.

這些方法論決定了程式語言的運算模型

1. 以「下指令」的方式來引導程式的執行,像Pascal, C等都屬於這一類的語言,大多數的開發語言都具有這種特徵; 物件導向式的程式語言多了物件object及類別class的觀念,同時也加上了一些物件導向的特性,smalltalk和C++就屬於物件導向式的程式語言,以C++來說,和C非常類似,原本就具有命令式語言的特徵,只是又比C多了物件導向的特性

2. 以函式的呼叫與傳回參數的方式來描述運算,下面的LISP程式的邏輯在於若不是a<0與a=0的兩種情況,則傳回afactorial(a-1)的值,這個程式使用了遞迴的觀念

(defun factorial (a)

(cond ((<a 0) nil)

((=a 0) 1)

(t (times a (factorial (minus a 1))))))

3. Prolog是邏輯式程式語言的一種,利用語法來描述事實facts及推理的規則rules,程式執行時就以邏輯的理論為根本,以事實作基礎,用規則來推理出更多的結論

4. 物件導向式的程式語言具有3種主要的特性: 封裝、繼承、多元性, smalltalk、C++、Java、C#都算是這一類的語言

1-3-2-2

1. 宣告式的語言不必詳細描述運算的步驟，像資料庫系統常用的結構化查詢語言（SQL, Structured Query Language）就是一種宣告式的語言。

2. 程序式的語言層一步一步地描述運算的過程，像 Pascal、C、C++ 等就可算是程序式的程式語言，這一類的語言能將各種運算描述的非常清楚，具有運算上的完整性（Computational-completeness）。 Java屬於此類!

1-4 程式語言的功能與處理的方式

一般程式被處理的過程: 直譯interpret、編譯compile,處理的目的是讓程式能轉換成可以在電腦上執行的型式。

直 譯: 原始程式碼為直譯器(Interpreter)的輸入。每譯完一個指令就馬上執行，然後再處理下一個指令。直譯的方式感覺上效率比較高，但是實際上不見得如此。

編 譯: 原始程式碼為編譯器(Compiler)的輸入。全部轉換成目標程式 (object program)，這個過程叫做編譯時期(Compile-time)。目標程式可直接對應成機器語言在電腦上執行，這個過程叫做執行時期(Run-time)。

直譯 vs. 編譯

通常編譯時期會花掉一些時間，但是編譯完之後的程式執行起來會比直譯的情況有效率。

一旦程式除錯完畢，只要編譯過一次，就可反覆地執行。

直譯程式每次執行都要再直譯一次。目前大多數的程式語言在處理上主要仍採用編譯 的方式。

1-5-1 名稱的連結(繫結)

繫結(binding) 發生的時機: 語言設計的時候(資料型態、控制語法、語意特徵)、語言製作的時候(資料值域、例外處理、輸出入介面)、寫程式的時候(資料型態、資料結構、演算法)、編譯時期(結構與機器語言對應、靜態配置)、連結時期(模組配置與引用)、載入時期(load time)(資料物件vs.記憶體位址)、執行時期(run time)(變數vs.值、副程式呼叫)

繫結(binding) 的種類: 靜態繫結(static binding) 表示繫結發生在執行時期之前。 假如繫結發生在執行時期則稱為動態繫結(dynamic binding) 。 繫結的時間 (binding times) 在程式語言的設計上是很重要的問題，提早的繫結時間 (early binding  times) 有助於提昇程式效能，延後的繫結時間(late  binding times) 則容許比較大的彈性。

1-5-2 進階的重要觀念

懸置的引用dangling reference: 程式中所引用的物件在執行時期會產生,物件的內涵與其名稱會繫結在一起,在這過程中,除了物件本身的建立之外,物件透過繫結得到了名稱;執行過程中現有的繫結可能會改變,等到不再用該物件時,繫結與物件都會被移除,這就是繫結與物件的生命週期.假如物件已經不存在,而仍有繫結到此物件的名稱在使用,這樣的名稱叫做懸置的引用

物件生命週期儲存空間的配置方式:

靜態的物件(static objects)有絕對的位置, ex. 全域變數global variables和基本字、

堆疊物件(stack objects): 後進先出的資料結構,適合副程式的呼叫與回傳、

堆積物件(heap objects):需要演算法的動態配置,因為牽涉碎片fragmentation.

副程式的靜態配置

範圍法則(scope rule): 某個名稱的繫結 (binding) 只在程式的某個範圍(scope) 內才有效,這是繫結的範圍(scope of binding) 的由來。通常繫結的範圍是在編譯時期就決定的,所以屬於靜態的。有些語言支援動態的範圍 (dynamic scope) ,則繫結會與執行時期的流程控制有關。在程式執行的過程中,有效繫結(active binding) 形成目前的引用環境(referencing environment)。

分開編譯(separate compilation) 的觀念: 大型的程式通常都要慢慢地擴充與測試,假如要一次編譯將會花費很多時間。因此大多數的程式語言都會支援所謂的分開編譯 (separate compilation) 的功能。編譯的單位常稱為模組 (module), C語言早期將宣告的部分放在「.h」的 header file 中,讓其他的檔案也能共用。但是當 header file 改變時將需要重新編譯共用該檔案的所有程式。 Java 以包裹(package)來代替模組的觀念,除了公用類別之外,Java類別只能讓相同包裹中的其他類別引用。

1-6-1 用程式語言描述資料

程式所描述的資料: 資訊本身可以分成數種資料型態 (data types)，不同的資料型態有不一樣的格式與儲存方式。寫程式的時候要依照資訊的特性來決定資訊所屬的資料型態。資料型態也可以依需要組合成資料結構 (data structure)，在各種場合中運用。

基本資料型態: 一般程式語言寫出來的程式處理的最基本的資料常稱為基本值(Literals)，例如整數值(Integer literals)、浮點數值(Floating-Point literals)、布林值(Boolean literals, true or false）、字元值(Character literals)、字串值(String literals) 等。基本值可以指定成變數(Variable)的值，該變數就具有基本值所屬的資料型態。例如變數X＝20，X是程式變數，20是整數值，則X的資料型態就是整數資料型態(Integer data type)。

認識運算子(operator): 各種資料型態都有一些相關的運算子，用來描述 數值的運算。例如常見的加 (＋)、減 (－)、乘 ( * )、除 (／) 和取餘數的算術運算子。布林值可以使用於布林運算，也就是邏輯運算。

程式中資料的使用: 常數constant的值在程式執行的過程中不會改變, ex. 圓周率; 變數variable的值在程式執行的過程中會改變,所以變數也可以看成一個儲存資料的空間,裡面儲存的值會改變

1-6-2-1 描述問題

程式的邏輯(program logic): 程式的邏輯是程式執行順序的依據。解決任何的問題除了需要完整的資料之外，還要有解決問題的方法與步驟，這就是程式邏輯的由來。假如寫出來的程式沒有按照程式的邏輯來執行，代表所寫的程式沒有正確地描述解決問題的方法。若是寫出來的程式的確按照程式的邏輯來執行，但是結果不正確，就表示原來的解決方法不對。

閏年的判定方法以口語的方式描述: 我們在判定某一年份是不是閏年時，會先看看能否能被4整除，若不能被4整除，則不是閏年；若是能被4整除但不能被100整除(ex. 2004)，就算是閏年；若是能被4與100整除，但不能被400整除(ex. 1900)，則不能算閏年；假使可以被400整除(ex. 2000)，則也算是閏年。

1-6-1-2 控制結構

常見的控制結構可以分門別類,當然以實際的程式語言來說,語法和語意各不相同,不過多半有支援各種常見的控制結構;對於程式設計者來說,在思考上可以只有一種模式,不必因為程式語言不同而需要重新認識這些控制結構:

順序sequencing: 敘述statement或運算式expression依照既定的順序來執行,通常是以在程式中出現的順序為執行的順序

選擇selection: 依照執行時期所得到的條件condition來決定該執行哪一個敘述,也稱為交替alternation. 選擇會形成程式執行流程的分岔branch.

反覆iteration: 重複執行某一段程式碼,可設定執行的次數或是以條件condition決定是否繼續執行

遞迴recursion: 程式自己呼叫自己或是運算式自己用來定義自己的情況

程序抽象化procedural abstraction: 將一些控制結構寫成的副程式以名稱來代稱或引用,甚至用來定義其他的副程式,稱為程序抽象化;也可以用參數化parameterization的方法讓抽象化的程序更具有通用性, ex. C++支援的template.

並行concurrency: 多個程式片斷同時執行的情況,所謂「同時執行」在電腦中有幾個不同的涵義: 有可能在不同的處理器上真正地同時執行,或是在相同的處理器上交錯地interleave執行

1-6-2-3 控制流程圖

1-6-3 程式開發的環境

1. 做簡單的語法上的檢查。

2. 顯示提示文字幫助程式設計者找到要使用的語法。

3. 讓使用者在程式中快速地來回瀏覽，找到需要修改或新增內容的地方。

4. 程式組態的管理(configuration management) ，例如各程式模組的相關性與編譯的先後記錄。

重點: 程式語言的功能、程式語言的理論基礎、學習程式語言的要領。