PL真有意思(五):數據類型

前言

現在大多數程序設計語言中都有表達式和/或對象的類型概念。類型起着兩種主要作用:

  • 為許多操作提供了隱含的上下文信息,使程序員可以在許多情況下不必显示的描述這種上下文。比如int類型的兩個對象相加就是整數相加、兩個字符串類型的對象相加就是拼接字符串、在Java和C#中new object()隱含在背後的就是要分配內存返回對象的引用等等。

  • 類型描述了其對象上一些合法的可以執行的操作集合。類型系統將不允許程序員去做一個字符和一個記錄的加法。編譯器可以使用這個合法的集合進行錯誤檢查,好的類型系統能夠在實踐中捕獲很多錯誤

類型系統

從編譯方面的知識我們可以知道,計算機硬件可以按多種不同的方式去解釋寄存器里的一組二進制位。處理器的不同功能單元可能把一組二進制位解釋為指令、地址、字符、各種長度的整數或者浮點數等。當然,二進制位本身是無類型的,對存儲器的哪些位置應該如何解釋,大部分硬件也無任何保留信息。彙編語言由於僅僅是對一些二進制指令的“助記符號”翻譯,它也是這種無類型情況。高級語言中則總是關聯值與其類型,需要這種關聯的一些原因和用途就如前面說到的上下文信息和錯誤檢測。

一般來說,一個類型系統包含一種定義類型並將它們與特定的語言結構關聯的機制;以及一些關於類型等價、類型相容、類型推理的規則。 必須具有類型的結構就是那些可以有值的,或者可以引用具有值得對象的結構。類型等價規則確定兩個值得類型何時相同;類型相容規則確定特定類型的值是否可以用在特定的上下文環境里;類型推理規則基於一個表達式的各部分組成部分的類型以及其外圍上下文來確定這個表達式的類型。

在一些多態性變量或參數的語言中,區分表達式(如一個名字)的類型與它所引用的那個對象的類型非常重要,因為同一個名字在不同時刻有可能引用不同類型的對象。

在一些語言中,子程序也是有類型的,如果子程序是一級或者二級值,其值是動態確定的子程序,這時語言就需要通過類型信息,根據特定的子程序接口(即參數的個數和類型)提供給這種結構的可接受的值集合,那麼子程序就必須具有類型信息。在那些不能動態創建子程序引用的靜態作用域語言(這種語言中子程序是三級值),編譯器時就能確定一個名字所引用的子程序,因此不需要子程序具有類型就可以保證子程序的正確調用。

類型檢查

類型檢查時一個處理過程,其目的就是保證程序遵循了語言的類型相容規則,違背這種規則的情況稱為類型衝突。說一個語言是強類型的,那麼就表示這個語言的實現遵循一種禁止把任何操作應用到不支持這種操作的類型對象上的規則。說一個語言是靜態類型化(statically type)的,那麼它就是強類型的,且所有的類型檢查都能在編譯時進行(現實中很少有語言是真正的靜態類型,通常這一術語是指大部分類型檢查可以在編譯器執行,其餘一小部分在運行時檢查)。如C#我們通常都認為它是靜態類型化的語言。

動態(運行時)類型檢查是遲約束的一種形式,把大部分的檢查操作都推遲到運行的時候進行。採用動態作用域規則的語言大部分都是動態類型語言,因為它的名字和對象的引用都是在運行時確定的,而確定引用對象的類型則更是要在引用確定之後才能做出的。

類型檢查是把雙刃劍,嚴格的類型檢查會使編譯器更早的發現一些程序上的錯誤,但是也會損失一部分靈活性;動態類型檢查靈活性大大的,但是運行時的代價、錯誤的推遲檢查,各種語言的實現也都在這種利弊上進行權衡。

多態性

多態性使得同一段代碼體可以對多個類型的對象工作。它意味着可能需要運行時的動態檢查,但也未必一定需要。在Lisp、Smalltalk以及一些腳本語言中,完全的動態類型化允許程序員把任何操作應用於任何對象,只有到了運行時採取檢查一個對象是否實現了具體的操作。由於對象的類型可以看作它們的一個隱式的(未明確聲明的,一個不恰當的比喻就如C#中的this)參數,動態類型化也被說成是支持隱式的參數多態性。

雖然動態類型化具有強大的威力(靈活性),但卻會帶來很大的運行時開銷,還會推遲錯誤報告。一些語言如ML採用了一種複雜的類型推理系統,設法通過靜態類型化支持隱式的參數多態性。

在面向對象語言里,子類型多態性允許類型T的變量X引用了從T派生的任何類型的對象,由於派生類型必定支持基類型的所有操作,因此編譯器完全可以保證類型T的對象能接受的任何操作,X引用的對象也都能接受。對於簡單的繼承模型,子類型多態的類型檢查就能完全在編譯時實現。採用了這種實現的大多數語言(如C++,JAVA和C#)都提供另一種显示的參數化類型(泛型),允許程序員定義帶有類型參數的類。泛型對於容器(集合)類型特別有用,如T的列表(List )和T的棧(Stack )等,其中T只是一個類型佔位符,在初始化的這個容器對象時提供具體的類型來代替它。與子類型多態類似,泛型也可以在編譯時完成類型檢查。比如C++的模板完全就是編譯期間的東西,編譯后就完全沒有了模板的痕迹;JAVA則是利用一種“擦除”的技術實現的泛型,需要在運行時做一些檢查。

類型的含義

現在至少存在三種不同的考慮類型問題的方式,分別稱之為指稱的、構造的和基於抽象的

  • 指稱的

按照指稱的觀點,一個類型就是一組值,一個值具有某個類型的條件是他屬於這個值集合,一個對象具有某個類型的條件是他的值保證屬於這個值集合

  • 構造的

從構造的觀點看,一個類型或者是以一小組內部類型,或者是通過對一個或幾個更簡單些的類型,應用某個類型的構造符構造出來的

  • 基於抽象的

從基於抽象的角度來看,一個類型就是一個接口,由一組定義良好而且具有相互協調的語義的操作組成。

類型的分類

在不同語言里,有關類型的術語也不相同,這裏說的通常都是常用的術語,大部分語言多提供的內部類型差不多就是大部分處理器所支持的類型:整數、字符、布爾和實數。

一般語言規範中都會規定數值類型的精度問題,以及一些字符的編碼規定。通常特殊的一個數值類型是枚舉類型,具體的語法在不同的語言中略有差異,但是其也都是一個目的(用一個字符友好的表示一個數值)。

關於枚舉類型,由一組命名元素組成。在C中可以這樣寫:

enum weekday { sun, mon, tue, wed, thu, fri, sat };

在C中這樣的寫法和直接對裏面的元素直接賦值除了語法上效果完全一樣。但是在之後的許多語言中,枚舉類型是一個真正的類型

還有一些語言中提供一種稱為子界的類型,它表示一種基於基本數值的一個連續的區間。比如Pascal中表示1到100:

type test_score = 0..100

複合類型:由一些簡單的基本類型組合成的一些類型稱為複合類型,比如常見的記錄、變體記錄、數組、集合、指針、表等,具體的都會在後面詳細介紹。

類型檢查

大多數的靜態類型語言中,定義一個對象都是需要描述清楚它的類型,進一步講,這些對象出現的上下文也都是有類型的,也就是說語言中的一些規則限制了這種上下文中可以合法出現的對象類型。

類型相容確定了一個特定類型的對象的能否用在一個特定上下文中。在最極端的情況下,對象可使用的條件就是它的類型與上下文所期望的類型等價。但是在大多數語言中,相容關係都比等價更寬鬆一些,即使對象與上下文的類型不同,它們也可以相容。

而類型推理想回答的是從一個簡單的表達式出發構造另一個表達式時,這整個的表達式的類型是什麼

類型等價

在用戶可以定義新類型的語言中,類型等價的定義一般基於兩種形式。

type R2 = record
    a : integer
    b : integer
end;

type R2 = record
    b : integer
    a : integer
end;
  • 結構等價

基於類型定義的內容,就是它們由同樣的組成部分且按照同樣的方式組合而成

它的準確定義在不同的語言中也不一樣,因為它們要決定類型之間的哪些潛在差異是重要的,哪些是可以接受的(比如上面的兩個定義,是否還認為是等價的)。結構等價是一種很直接的認識類型的方式,早期的一些語言(Algol 68、Modula-3、ML)有些事基於結構等價的,現在的大部分語言(Java、C#)大都是基於名字等價了,為何呢?因為從某種意義上看,結構等價是由底層、由實現決定的,屬於比較低級的思考方式。就如一個上下文,如果你傳遞了一個結構等價但是不是所期待對象,實施結構等價的編譯器是不會拒絕這種情況的(假如這不是你希望的,那麼你也不會得到任何提示或者錯誤信息,很難排查的)。

  • 名字等價

基於類型的詞法形式,可以認為是每一個名字都引進一個新的類型;

它基於一種假設,就是說程序員花時間定義了兩個類型,雖然它們的組成部分可能相同,但是程序員要表達的意思就是這是兩個不同的類型。名字等價的常規判斷就非常簡單了,看看聲明兩個對象的類型是否是一個就是了。但是也會有一些特殊的情況出現,比如類型別名(C、C++的程序員很熟悉這種東西吧),比如 typedef int Age; 就為int類型重新定義了一個別名”Age”。那些認為int不等價越Age的語言稱為嚴格名字等價,認為等價的稱為寬鬆名字等價。其實這兩種也是很容易區分的,只要能區分聲明和定義兩個概念的差異就可以區分。在嚴格名字等價中看待typedef int Age是認為定義了一個新類型Age,在寬鬆名字等價看來這就是一個類型聲明而已,int和Age共享同一個關於整數的定義。

類型變換和轉換

在靜態類型的語言中,如果“a=b”,那麼我們會期望b的類型和a的相同;現在假定所提供的類型和期望的類型和所提供的類型相同,那麼我們在要求某個類型的上下文中使用另外一個類型時就需要显示的寫出類型變換(或稱為類型轉換)。根據具體的變換的具體情況,在運行時執行這種變化會有以下三種主要的情況出現:

  • 所涉及的類型可以認為是結構等價的,這種情況裏面因為涉及的類型採用了相同的底層的表示,則這種變換純粹就是概念上的操作,不需要運行時執行任何代碼。

  • 所涉及的類型具有不同的值集合,但它們的值集合具有相同的表示形式。比如一個類型和它的子類型,一個整數和一個無符號的整數。拿無符號整數變換為整數來說,由於無符號整數的最大值是整數類型所容納不了的,則運行時就必須執行一些代碼來保證這種變換的合法性,如果合法則繼續下去,否則會產生一個動態語義錯誤。

  • 所涉及的類型具有不同的底層表示,但是我們可以在它們的值之間定義某種對應關係。比如32位整數可以變換到IEEE的雙精度浮點數,且不會丟失精度。浮點數也可以通過舍入或割斷的形式變換成整數,但是會丟失小數部分。

非變換的類型轉換

有這麼一種情況,我們需要改變一個值,但是不需要改變它的二進製表示形式,更通俗點說就是我們希望按照另外一個類型的方式去解釋某個類型的二進制位,這種情況稱為非變換類型轉換。最簡單的一個例子比如說,一個byte類型的數值65,按byte類型來解釋它是65,如果按照char類型來解釋它就是字符“A”。比如C++中的static_cast執行類型變換,reinterpret_cast執行非變換的類型轉換。c中出現的union形式的結構,就可以認為是這種非變換的類型轉換的合法的安全的語言結構。在比如下面C中一般性非變換類型轉換代碼:

r=*((float *) &n);

任何非變換的類型轉換都極其危險的顛覆了語言的類型系統。在弱類型系統的語言中,這種顛覆可能很難發現,在強類型系統的語言中显示的使用這種非變換的類型轉換,起碼從代碼上可以看得出來它是這麼一回事,或多或少的有利於排查問題。

類型相容

大多數語言的上下文中並不要求類型等價,相應的一般都是實施較為“寬鬆”的類型相容規則。比如賦值語句要求右值相容與左值、參數類型相容,實際返回類型與指定的返回類型相容。在語言中,只要允許把一個類型的值用到期望的另外一個類型的上下文中,語言都必須執行一個到所期望類型的自動隱式變換,稱為類型強制(比如int b;double a=b;)。就像前面說的显示的類型變換一樣,隱式的類型變換也可能需要執行底層代碼或者做一些動態類型檢查。

重載

一個重載的名字可能引用不同類型的對象,這種歧義性需要通過上下文信息進行解析。比如a+b這個表達式可以表示整數或者浮點數的加法運算,在沒有強制的語言中,a和b必須都是整數或都是浮點數。如果是有強制的語言,那麼在a或者b有一個是浮點數的情況下,編譯器就必須使用浮點數的加法運算(另外一個整數強制轉換為浮點數)。如果語言中+只是進行浮點數運算,那麼即使a和b都是整數,也會被全部轉成浮點數進行運算(這代價就高了好多了)。

通用引用類型

通用引用類型:一些語言根據實習需求,設計有通用的引用類型,比如C中的void*、C#中的Object,任意的值都可以賦值給通用引用類型的對象。但是問題是存進去容易取出來難,當通用引用類型是右值的時候,左值的類型可能支持某些操作,然而這些操作右值對象是不具備的。為了保證通用類型到具體類型的賦值安全,一種解決辦法是讓對象可以自描述(也就是這個對象包含其真實類型的描述信息),C++,JAVA,C#都是這種方式,C#中如果賦值的類型不匹配則會拋出異常,而C++則是使用dynamic_cast做這種賦值操作,具體的後果呢,也是C++程序員負責。

類型推理

通過前面的類型檢查我們可以保證表達式的各各組成部分具有合適的類型,那麼這整個表達式的類型是什麼來着?其實在大多數的語言中也是比較簡單的,算術表達式的類型與運算對象相同、比較表達式總是布爾類型、函數調用的結果在函數頭聲明、賦值結果就是其左值的類型。在一些特殊的數據類型中,這個問題並不是那麼清晰明了,比如子界類型、複合類型。比如下面的子界類型問題(Pascal):

type Atype=0..20;
type Btype=10..20;

var a: Atype;
var b: Btype;

那麼a+b什麼類型呢???它確實是不能是Atype或者Btype類型,因為它可能的結果是10-40。有人覺得那就新構造一個匿名的子界類型,邊界時10到40。實際情況是Pascal給的答案是它的基礎類型,也就是整數。

在Pascal中,字符串’abc’的類型是array[1..3] of char、而Ada則認為是一種未完全確定的類型,該類型與任何3個字符數組相容,比如在Ada中’abc’ & ‘defg’其結果是一個7字符的數組,那麼這個7字符數組的類型是array[1..7] of cahr呢還是某一個也是7個字符組成的類型array (weekday) of character呢,更或者是其他任意一個也是包含七個字符數組的另外一個類型。這種情況就必須依賴表達式所處的上下文信息才能推到出來具體的類型來。

記錄(結構)與變體(聯合)

一些語言中稱記錄為結構(struct),比如C語言。C++把結構定義為class的一種特殊形式(成員默認全局可見),Java中沒有struct的概念,而C#則對struct採用值模型,對class採用引用模型。

語法與運算

一個簡單的結構體在C中可以這樣定義:

struct element{
    char name[2];
    int number;
    double weight;
    Bool merallic;    
}; 

等價於Pascal中的:

 type two_chars=packed array [1..2] of char;
 type element - record
     name:two_chars;
     number:integer;
     weight:real;
     metallic:Boolean
 end

記錄裏面的成員(如name,number…)稱為域(field)。在需要引用記錄中的域時,大部分語言使用“.”記法形式。比如Pascal中:

 var copper:eement;
 copper.name=6.34;

大部分語言中還允許記錄的嵌套定義,比如在Pascal中:

 type short_string=packed array[1..30] of char;
 type ore=record
      name:short_string;
      element_yielded:record /*嵌套的記錄定義*/
          name:two_chars;
          number:integer;
          weight:real;
          metallic:Boolean
      end
 end

存儲布局及其影響

一個記錄的各個域通常被放入內存中的相鄰位置。編譯器在符號表中保存每個域的偏移量,裝載和保存的時候通過基址寄存器和偏移量即可得到域的內存地址。類型element在32位的機器中可能的布局如下:

此處有圖

(圖在最後面,因為markdown的這個畫表格不符合這個要求,又不想引圖了,就直接用html寫了,會被擠到最後去)

(table標籤和我博客園的樣式生成的時候會出bug,刪除了)

在對結構體的存儲布局方案上,如果使用正常排序,結構中的空洞會浪費空間。但是如果通過壓縮來節省空間,但是可能很帶來很嚴重的訪問時間的代價

數組

數組是最常見也是最重要的複合數據類型。記錄用於組合一些不同類型的域在一起;而數組則不同,它們總是同質的。從語義上看,可以把數組想象成從一個下標類型到成員(元素)類型的映射。

有些語言要求下標類型必須是integer,也有許多語言允許任何離散類型作為下標;有些語言要求數組的元素類型只能是標量,而大多數語言則允許任意類型的元素類型。也有一些語言允許非離散類型的下標,這樣產生的關聯數組只能通過散列表的方式實現,而無法使用高效的連續位置方式存儲,比如C++中的map,C#中的Dictionary。在本節中的討論中我們假定數組的下標是離散的。

語法和操作

大多數的語言都通過數組名后附加下標的方式(圓括號|方括號)來引用數組裡的元素。由於圓括號()一般用於界定子程序調用的實際參數,方括號在區分這兩種情況則有易讀的優勢。Fortran的數組用圓括號,是因為當時IBM的打卡片機器上沒有方括號

維數、上下界和分配

對於數組的形狀在聲明中就已經描述,對於這種有靜態形狀的數組,可以用通常的方式來管理內存:生存期是整個程序的數組使用棧分配,具有更一般的生存期的動態生成數組使用堆分配。但是對於在加工之前不知道其形狀的數組,或其形狀在執行期間可能改變的數組,存儲管理就會更複雜一點。

  • 內情向量

在編譯期間,符號表維護者程序中的每個數組的維度和邊界信息。對於每個記錄,它還維護着每個域的偏移量。如果數組維度的數目和邊界是靜態已知的,編譯器就可以在符號表中找出它們,以便計算數組元素的地址。如果這些值不是靜態已知的,則編譯器就必須生成代碼,在運行時從一個叫內情向量的數據結構來查找它

  • 棧分配

子程序參數是動態形狀數組最簡單的例子,其中數組的上下界在運行時才確定,調用方都會傳遞數組的數據和一個適當的內情向量,但是如果一個數組的形狀只能到加工時才知道,這種情況下仍可以在子程序的棧幀里為數組分配空間,但是需要多做一層操作

  • 堆分配

在任意時間都可以改變形狀的數組,有時被稱為是完全動態的。因為大小的變化不會以先進先出的順序進行,所以棧分配就不夠用了。完全動態的數組必須在堆中分配。比如Java中的ArrayList

#### 內存布局

大多數語言的實現里,一個數組都存放在內存的一批連續地址中,比如第二個元素緊挨着第一個,第三個緊挨着第二個元素。對於多維數組而言,則是一個矩陣,會出現行優先和列優先的選擇題,這種選擇題對於語言使用者而言是透明的,而對語言的實現者則需要考慮底層方面的優化問題了。

在一些語言中,還有另外一種方式,對於數組不再用連續地址分配,也不要求各行連續存放,而是允許放置在內存的任何地方,再創建一個指向各元素的輔助指針數組,如果數組的維數多於兩維,就再分配一個指向指針數組的指針數組。這種方式稱為行指針布局,這種方式需要更多的內存空間,但是卻有兩個優點:

  • 首先,可能加快訪問數組裡單獨元素的速度;
  • 其次,允許創建不用長度的行,而且不需要再各行的最後留下對齊所用的空洞空間,這樣節省下來的空間有時候可能會超過指針佔據的空間。C,C++和C#都支持連續方式或行指針方式組織多維數組,從技術上講,連續布局才是真正的多維數組,而行指針方式則只是指向數組的指針數組。

字符串

許多語言中,字符串也就是字符的數組。而在另一些語言中,字符串的情況特殊,允許對它們做一些其他數組不能用的操作,比如Icon以及一些腳本語言中就有強大的字符串操作功能。

字符串是編程中非常重要的一個數據類型,故而很多語言都對字符串有特殊的處理以便優化其性能以及存儲(比如C#中的字符串不可變性保證了性能,字符串駐留技術照顧了存儲方面的需要),由於這些特殊的處理,故而各各語言中為字符串提供的操作集合嚴重依賴語言設計者對於實現的考慮。

集合

程序設計語言中的一個集合,也就是具有某個公共類型的任意數目的一組值的一種無序彙集。集合的元素所具有的類型叫做元類型或者基類型。現在的大多數程序設計語言都對集合提供了很大的支持,為集合提供了很多相關的操作

指針和遞歸類型

所謂的遞歸類型,就是可以在其對象中包含一個或多個本類型對象的引用類型。遞歸類型用於構造各種各樣的“鏈接”數據結構,比如樹。在一些對變量採用引用模型的語言中,很容易在創建這種遞歸類型,因為每個變量都是引用;在一些對變量採用值模型的語言中,定義遞歸類型就需要使用指針的概念,指針就是一種變量,其值是對其他對象的引用。

對於任何允許在堆里分配新對象的語言,都存在一個問題:若這種對象不在需要了,何時以及以何種方式收回對象佔用的空間?對於那些活動時間很短的程序,讓不用的存儲留在那裡,可能還可以接受,畢竟在它不活動時系統會負責回收它所使用的任何空間。但是大部分情況下,不用的對象都必須回收,以便騰出空間,如果一個程序不能把不再使用的對象存儲回收,我們就認為它存在“內存泄漏”。如果這種程序運行很長一段時間,那麼它可能就會用完所有的空間而崩潰。許多早期的語言要求程序員显示的回收空間,如C,C++等,另一些語言則要求語言實現自動回收不再使用的對象,如Java,C#以及所有的函數式語言和腳本語言。显示的存儲回收可以簡化語言的實現,但會增加程序員忘記回收不再使用的對象(造成內存泄漏),或者不當的回收了不該回收的正在使用的對象(造成懸空引用)的可能性。自動回收可以大大簡化程序員的工作,但是為語言的實現帶來了複雜度。

語法和操作

對指針的操作包括堆中對象的分配和釋放,對指針間接操作以訪問被它們所指的對象,以及用一個指針給另一個指針賦值。這些操作的行為高度依賴於語言是函數式還是命令式,以及變量/名字使用的是引用模型還是值模型。

函數式語言一般對名字採用某種引用模型(純的函數式語言里根本沒有變量和賦值)。函數式語言里的對象傾向於採取根據需要自動分配的方式。

命令式語言里的變量可能採用值模型或引用模型,有時是兩者的某種組合。比如 A=B;

  • 值模型: 把B的值放入A。
  • 引用模型: 使A去引用B所引用的那個對象。

Java的實現方式區分了內部類型和用戶定義的類型,對內部類型採用值模型,對用戶定義的類型採用則採用引用模型,C#的默認方式與Java類似,另外還提供一些附加的語言特性,比如“unsafe”可以讓程序員在程序中使用指針。

懸空引用

在前兩篇的名字、作用域和約束中我們列舉了對象的3種存儲類別:靜態、棧和堆。靜態對象在程序的執行期間始終是活動的,棧對象在它們的聲明所在的子程序執行期間是活動的,而堆對象則沒有明確定義活動時間。

在對象不在活動時,長時間運行的程序就需要回收該對象的空間,棧對象的回收將作為子程序調用序列的一部分被自動執行。而在堆中的對象,由程序員或者語言的自動回收機制負責創建或者釋放,那麼如果一個活動的指針並沒有引用合法的活動對象,這種情況就是懸空引用。比如程序員显示的釋放了仍有指針引用着的對象,就會造成懸空指針,再進一步假設,這個懸空指針原來指向的位置被其他的數據存放進去了,但是實際卻不是這個懸空指針該指向的數據,如果對此存儲位置的數據進行操作,就會破壞正常的程序數據。

那麼如何從語言層面應對這種問題呢?Algol 68的做法是禁止任何指針指向生存周期短於這個指針本身的對象,不幸的是這條規則很難貫徹執行。因為由於指針和被指對象都可能作為子程序的參數傳遞,只有在所有引用參數都帶有隱含的生存周期信息的情況下,才有可能動態的去執行這種規則的檢查。

廢料收集

對程序員而已,显示釋放堆對象是很沉重的負擔,也是程序出錯的主要根源之一,為了追蹤對象的生存軌跡所需的代碼,會導致程序更難設計、實現,也更難維護。一種很有吸引力的方案就是讓語言在實現層面去處理這個問題。隨着時間的推移,自動廢料收集回收都快成了大多數新生語言的標配了,雖然它的有很高的代價,但也消除了去檢查懸空引用的必要性了。關於這方面的爭執集中在兩方:以方便和安全為主的一方,以性能為主的另一方。這也說明了一件事,編程中的很多地方的設計,架構等等方面都是在現實中做出權衡。

廢料收集一般有這兩種思想,就不詳細說了。

  • 引用計算
  • 追溯式收集

表具有遞歸定義的結構,它或者是空表,或者是一個有序對,有序對由一個對象和另一個表組成。表對於函數式或者邏輯式語言程序設計非常適用,因為那裡的大多數工作都是通過遞歸函數或高階函數來完成的。

在Lisp中:

(cons 'a '(b))  => (a b)
(car '(a b))    => a
(cdr '(a b c))  => (b c)

在Haskell和Python還由一個非常有用的功能,叫做列表推導。在Python中可以這樣推導出一個列表

[i * i for i in range(1, 100) if i % 2 == 1]

文件和輸入/輸出

輸入/輸出(I/O)功能使程序可以與外部世界通信。在討論這種通信時,將交互式I/O和文件I/O分開可能有些幫助。交互式IO通常意味着與人或物理設備通信,人或設備都與運行着的程序并行工作,送給程序的輸入可能依賴程序在此之前的輸出。文件通常對應於程序的地址空間之外的存儲器,由操作系統實現。

有些語言提供了內置的File數據類型,另外一些語言將IO工作完全委託給庫程序包,這些程序包導出一個file類型。所以IO也算作是一種數據類型

相等檢測和賦值

對於簡單的基本數據類型,如整數、浮點數和字符,相等檢測和賦值相對來說都是直截了當的操作。其語義和實現也很明確,可以直接按照二進制位方式比較或複製,但是,對於更加複雜或抽象的數據類型,就可能還需要其它的比較方式

  • 相互是別名?
  • 二進制位是否都相等?
  • 包含同樣的字符序列?
  • 如果打印出來,看起來完全一樣?

就許多情況下,當存在引用的情況下,只有兩個表達式引用相同的對象時它們才相等,這種稱為淺比較。而對於引用的對象本身存在相等的含義時,這種比較稱為深比較。對於複雜的數據結構,進行深比較可能要進行遞歸的遍歷。所以相對來說,賦值也有深淺之分。深賦值時是進行完整的拷貝。

大多數的語言都使用淺比較和淺賦值

小結

本文從語言為何需要類型系統出發,解釋了類型系統為語言提供了那些有價值的用途:1是為許多操作提供隱含的上下文,使程序員在許多情況下不必显示的描述這種上下文;2是使得編譯器可以捕捉更廣泛的各種各樣的程序錯誤。 然後介紹了類型系統的三個重要規則:類型等價、類型相容、類型推理。以此3個規則推導出的強類型(絕不允許把任何操作應用到不支持該操作的對象上)、弱類型以及靜態類型化(在編譯階段貫徹實施強類型的性質)、動態類型化的性質以及在對語言的使用方面的影響。以及後續介紹了語言中常見的一些數據類型的用途以及語言在實現這種類型方面所遇到的問題以及其大致的實現方式。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

3c收購,鏡頭 收購有可能以全新價回收嗎?

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

賣IPHONE,iPhone回收,舊換新!教你怎麼賣才划算?