簡介
算法設計自動化是軟體自動化的核心和難點所在,其含義是:從“做什麼”的軟體功能規格說明自動或半自動地生成“如何做”的軟體設計規格說明直至機器可執行的程式。傳統的規格說明語言和程式設計語言由於結構單一而難以適應算法設計自動化的需要。因此,必須設計一種能夠刻劃軟體功能規格說明、軟體設計規格說明、可執行程式以及相應算法設計過程的廣譜語言。光譜語言是指提供規約級到實現級的數據結構和控制結構的構造,並提供結構間語義等價的轉換規則,用於自動轉換或驗證低級結構的相對高級結構的正確性的語言。典型代表語言CIP-L語言。
特點
廣譜性:廣譜性是指語言既能刻化“做什麼”的功能規格說明,又能表達“如何做”的設計規格說明與可執行程式,並能反映其間的轉換過程。
緊耦合性:緊耦合性是指語言中多種語言層次的語言成分必須具有統一的語法表示和共同的語義基礎,而不是簡單地將各種語言成分組合在一起。
嚴密性:嚴密性是指語言具有良好的數學基礎,便於轉換過程的語義分析和自動實現。
實用性:實用性是指語言結構簡明與表示方便,其數學背景儘量對用戶隱蔽,便於學習和使用 。
1.廣譜性:廣譜性是指語言既能刻化“做什麼”的功能規格說明,又能表達“如何做”的設計規格說明與可執行程式,並能反映其間的轉換過程。
2.緊耦合性:緊耦合性是指語言中多種語言層次的語言成分必須具有統一的語法表示和共同的語義基礎,而不是簡單地將各種語言成分組合在一起。
3.嚴密性:嚴密性是指語言具有良好的數學基礎,便於轉換過程的語義分析和自動實現。
4.實用性:實用性是指語言結構簡明與表示方便,其數學背景儘量對用戶隱蔽,便於學習和使用 。
需求
問題表示的需要
軟體規格說明語言區別於傳統程式設計語言的本質是其面向問題的特徵,即它能簡明而清晰地表達待解問題而不必涉及問題的求解過程與功效。問題表示的多樣性導致軟體規格說明的廣譜性。前後斷言是一種用於刻劃軟體功能的形式化方法,在可以隨意使用謂詞的情況下,前後斷言可以清晰而方便地描述各種問題。然而,基於前後斷言方法的軟體規格說明語言所能提供的基本謂詞集是有限的。為使這樣有限的基本謂詞集能滿足前後斷言方法刻劃軟體功能的需要,途徑之一是採用構造性的方法。提供一定的結構手段,如各種邏輯聯結詞和量詞,使之能對基本謂詞加以組合而構成新的滿足需要的謂詞,這一途徑的難點在於提供具有一定抽象級別的、通用的、便於自動化的、有限的、相對完備的基本謂詞集;並且對於刻劃大型軟體來說,複雜的邏輯公式特別難以書寫和理解。大型軟體的主要特徵是其複雜性,而分解和抽象是克服複雜性的兩個關鍵手段,在某種意義下,功能規格說明具有抽象性,而分解手段具有設計性。因此,有必要將功能規格說明與設計規格說明有機地結合起來。途徑之二是面向特定的套用領域,即提供面向特定套用領域的相對完備的基本謂詞集;這條途徑我們在設計FGSPEC語言中已進行了初步嘗試,結果表明:確定合適的範圍與相關的基本謂詞取決於對特定套用領域的透徹理解。並且,對於某些問題,特別是超出領域的用歸納方式定義的問題(如求階乘)等,如無專用謂詞,便難以刻劃。因此,必須提供設計規格說明作為功能規格說明的補充手段,使語言具有較強的表達能力。
刻划算法設計過程的需要
傳統的程式設計語言為了增加程式的易讀性,曾試圖用程式正文來反映程式設計過程,但未能奏效。主要問題在於單一的程式正文難以權衡表示的清晰性和實現的功效性,更難以反映其間的轉換過程。這就要求規格說明語言不僅能刻劃“嵌什麼”的功能規格說明與“如何做,的設計規格說明,而且還必須能刻劃其間的轉換過程。亦即,要求具有廣譜性,以此作為研究和實現算法設計自動化的基礎。
實現算法設計自動化的需要
和傳統的編譯實現技術不同,算法設計自動化的實現涉及多層次語言間的轉換,如從功能性的規格說明到設計性的規格說明以及從設計性的規格說明到可執行的程式,如果對不同層次設計不同的語言,那么,一方面,多種語言需多種分析程式,增加了實現的負擔;另一方面,由於各語言層次間的轉換,特別是從功能規格說明到設計規格說明的完全自動轉換尚難做到,因此,須有人工千預。如果在規格說明語言中不能反映其間的逐步轉換過程,使人和實現系統在統一的轉換模式下進行算法設計,則勢必使用戶要了解自動化系統的內部細節,不便於人機互動。
CIP-L語言
CIP-L語言(CIP-L language)是一種支持轉換 式程式設計的廣譜語言。CIP-L可描述從軟體功能 規約、設計規約、作用式程式到過程式或面向機器的 高效程式等不同的抽象級;提供了從高抽象級向低 抽象級轉換的語言結構和語義規則。它是70年代 中期由德國慕尼黑技術大學F.L.Bauer主持開發的“直覺引導的計算機輔助程式設計”項目的主要部分,用以支持轉換式程式設計方法,保證程式轉換的正確性。 作為廣譜語言,CIRL用代數類型描述功能規約,用計算結構刻畫代數類型的模型,用模式描述算法和控制結構。代數類型也就是抽象數據類型,其公理用一階邏輯公式表示。CIP-L要求,代數類型中的任一對象均可經有限步基本運算生成。這種生成結構可用CIP-L的計算結構刻畫。模式是一個算法架構,用以描述算法策略和控制策略,將一個模式中的代數類型名賦予具體的語義解釋後即可得到具體的算法。模式語言又分成核心層和多個擴展層。 核心層定義了表達式子語言,可按邏輯式或函式式風格書寫程式,採用模型論方法定義其語義。擴展層包含了申述式子語言,命令式子語言,並行子語言和控制子語言,它們的語義刻畫採用轉換語義方法,即每一語法結構的語義均可由轉換規則在有限步內歸結到核心層語義。 CIP-L針對轉換式程式設計的需要而設計。語 言覆蓋了從功能規約到過程實現各個層次,功能很 ,但同時造成結構繁雜,不易掌握。