面向表達式語言也稱為套用式語言(App!icative Language)或函式式語言(Functional Language),是一種全新的程式設計語言。函式式程式沒有諸如指令計數器、數據存儲器和程式當前狀態之類的概念。這種語言的程式是純數學意義上的函式,它作用於程式的輸入,得到的結果值就是程式的輸出。因此它不具有副作用,保證了程式各部分的並發執行,不會影響正確結果的獲得,對高度並行的系統結構,更適宜於採用函式式語言來設計並發程式。
基本介紹
- 中文名:面向表達式語言
- 外文名:Expression oriented language
- 別稱:套用式語言或函式式語言
- 定義:作用於程式的輸入
- 系統:計算機
- 套用學科:計算機原理
概述,特點,函式式語言的歸約機結構,串歸約機,圖歸約機,
概述
面向表達式語言也稱為套用式語言(App!icative Language)或函式式語言(Functional Language),是一種全新的程式設計語言。函式式程式沒有諸如指令計數器、數據存儲器和程式當前狀態之類的概念。這種語言的程式是純數學意義上的函式,它作用於程式的輸入,得到的結果值就是程式的輸出。因此它不具有副作用,保證了程式各部分的並發執行,不會影響正確結果的獲得,對高度並行的系統結構,更適宜於採用函式式語言來設計並發程式。
在函式式程式設計系統中,程式是一個表達式,計算過程僅由函式來描述。對運算的順序並無顯式的描寫,運算順序只蘊涵於各函式調用之間的依賴關係中,且與運行程式的實際運算結構無關。
構成函式程式的主要成分是原函式(Primitive Functions)、複合函式和定義。原函式的主要功能是實現由對象到對象的映射,或是把一個對象變換成另一個對象。常用的原函式有選擇函式,算術函式,交叉置換函式,比較、測試函式,加1、減1函式,附加序列函式,分配函式,取序列尾函式等。複合函式的主要功能是利用函式構成算符,將已有的函式構成新的複雜函式,常用的程式構成算符有:組合算符“O”,構造算符“[]”,條件算符“→”,插入算符“/”,作用於全體(Apply to A11)算符“α”等。複合函式只有經定義“f”並輸入到機器後方能套用。用戶定義的函式由形式參數表和函式體兩部分組成。函式定義的過程也就是建立形式參數表中形式參數與函式體中的變數之間約束關係的過程。
歸約機是一種面向函式式程式設計語言的計算機,屬於需求驅動的系統結構。指令的執行順序取決於對這些指令產生結果數據的需求,而這種需求又源於函式式程式設計語言對表達式的歸約。歸約操作主要是函式作用和子表達式變換。歸約過程就是將每個最內層可歸約表達式用其值來替換,這樣又形成了新的最內層可歸約表達式,然後再對其進行歸約,最後,整個程式全部被歸約,僅留下最終結果。
特點
函式式語言的主要特點是:
1)直接由原函式構成,層次分明。所編程式為靜態的、非重複的,便於錯誤檢測。
2)程式與數據分開,數據結構不是程式的組成部分,同一個函式程式可處理不同的對象,程式具有通用性。
3)程式中包括了固有並行性,便於檢測和並行。
4)程式無狀態並採用數據存儲單元。
5)無賦值語句,不使用GOTO類控制語句,所使用的程式構成算符,遵從許多基本代數定理,因而由函式式語言所編寫的程式的正確性,易於得到證明。
函式式語言的歸約機結構
歸約機按其歸約模型可分為串歸約機和圖歸約機兩類,兩者的區別主要是對函式表達式所使用的存儲方式不同,串歸約機以字元串形式存儲,圖歸約機以圖的形式存儲。
串歸約機
串歸約機的例子是Mago提出的細胞樹形結構多處理機FFP。FFP規約機的結構如圖所示。
圖中線性L單元陣列是一個帶有邏輯功能的存儲系統,L單元不僅存放FFP表達式(程式和數據),還執行機器中大部分的工作,因而它又是一個PE(處理單元)。相鄰的L單元互聯成一個線性陣列,這一線性連線僅為了進行存儲管理。前端機控制整個系統,包括對FFP機使用的基本操作進行定義,控制輔助存儲器與管理I/O。輔助存儲器同L陣列的兩端相連,隨後機器從輔助存儲器取出信息到陣列,使其開始工作。若L陣列中的信息超出其存儲容量,把溢出部分移入輔助存儲器,L單元間經由網際網路進行通信,並具有某些處理功能。
FFP機的實現方案有多種,下圖所示的二叉樹網際網路結構是最簡單的方案,二叉樹網路的內部節點稱T單元,葉節點稱L單元,樹根連到前端機。這種結構具有易於構造和易於擴展的優點。
FFP機的工作過程可分為多個操作周期,每個周期又可分為三個階段:分解階段、執行階段和存儲管理階段。FFP機能較好地完成程式自動分解,機器運行時按程式的實際需要可不斷重構系統。機器以函式式語言FFP編程,無需程式設計師干預而自動地開發並行性。
下圖表示向量(3,2,5,1)各元素平方和與各元素相除的計算過程。
圖歸約機
圖歸約機將函式定義、表達式和目標以圖的形式存儲於機器中,因此進行歸約的對象是圖,最常用的是二叉樹和N叉樹。英國帝國理工學院的ALICE多處理器系統,其目標語言HOPE是純函式式語言,程式由函式定義集組成。函式通過重寫來加以歸約,由存放在函式定義資料庫中的代碼替換函式加以實現。ALICE圖歸約機樣機的結構如圖1所示,它是一個由16個處理器和24個存儲模組構成的多處理器系統,由全互連的Delta交叉開關網實現處理器和存儲模組之間的互連。圖2中示出了處理器及存儲模組的內部結構。每個處理器含有五個Transputer,其中兩個從事重寫操作,每個帶有64KB Cache;第三個用作Cache的管理;另外兩個分別作接受和傳送信息包用。存儲模組的內部較簡單,只有一個Transputer進行信息包的傳送和接收操作,存儲容量為2MB。