程式語言介紹/程式語言正規化
程式語言可以粗略地分為兩類：命令式和宣告式。然而，這種分類並不嚴格。它僅僅意味著一些程式語言更自然地促進了開發程式的特定方式。指令式程式設計側重於如何做某事，而宣告式程式設計則表達了給定問題的解決方案是什麼。宣告式語言可以進一步細分為函式式和邏輯語言。函式式語言將計算視為數學函式的求值，而邏輯語言將計算視為公理和推導規則。
命令式語言遵循在圖靈機中描述的計算模型；因此，它們保留了狀態的基本概念。在該形式化中，程式的狀態由儲存器磁帶的配置以及規則表中的指標給出。在現代計算機中，狀態由儲存在記憶體和暫存器中的值給出。特別是，一個特殊的暫存器，即程式計數器，定義了要執行的下一條指令。指令是指令式程式設計中的一個非常重要的概念。命令式程式向機器發出定義要執行的下一個操作的命令。這些操作會改變機器的狀態。換句話說，命令式程式類似於食譜，其中定義並排序了執行某事的必要步驟。指令組合在一起構成命令。命令主要有三種類型：賦值、分支和序列。
- 一個賦值透過使用新值更新其記憶體來改變機器的狀態。通常，賦值由一個表示記憶體位置的左值和一個表示將儲存在該位置的值的右值表示。
- 一個分支透過更新程式計數器來改變程式的狀態。分支的示例包括諸如 if、while、for、switch 等命令。
- 序列用於將命令串聯在一起，從而構建更具表現力的程式。某些語言需要一個特殊符號來指示命令的結束。例如，在C中，我們必須用分號來結束它們。其他語言，如Pascal，需要在構成序列的命令之間使用一個特殊符號。在 Pascal 中，這個特殊符號也是分號。
下面是用 C 編寫的程式說明了這些概念。此函式描述瞭如何獲得一個整數的階乘。要實現這一目標，我們首先要做的就是將數字 1 賦值到名為 f 的記憶體單元中。接下來，當名為 n 的記憶體單元中儲存的值大於 1 時，我們必須使用該單元的值乘以 n 的當前值來更新 f，並且我們必須將儲存在 n 中的值減少 1。在這些迭代結束時，我們得到了輸入 n 的階乘，儲存在 f 中。
int fact(int n) {
int f = 1;
while (n > 1) {
f = f * n;
n = n - 1;
}
return f;
}
命令式語言是工業界占主導地位的程式設計正規化。有很多假設可以解釋這種主導地位，對於良好的討論，我們可以推薦 Philip Wadler 的優秀論文。命令式語言的例子包括C、Pascal、Basic、彙編器。
還有一些其他多正規化語言也部分甚至完全支援命令式正規化，例如 C++、JavaScript，但作為多正規化語言，它們不是很好的例子，因為這些語言的實際使用並不符合描述。
宣告式語言中的程式宣告一個真理。換句話說，這樣的程式描述了某個真理成立的證明。這些程式更關心問題的解決方案“是什麼”，而不是“如何”獲得該解決方案。這些程式由表示式構成，而不是命令。表示式是程式語言中任何返回值的有效語句。這些語言具有一個非常重要的特性：引用透明性。此屬性意味著任何表示式都可以用其值替換。例如，計算 5 的階乘的函式呼叫可以被其結果 120 替換。宣告式語言進一步細分為兩個非常重要的類別：函式式語言和邏輯語言。
函數語言程式設計基於稱為lambda 演算的形式化。與圖靈機一樣，lambda 演算也被用來定義哪些問題可以透過計算機解決。函式式正規化中的程式類似於我們在數學中使用的符號。函式沒有狀態，所有資料都是不可變的。程式是許多函式的組合。這些語言已經普及了一些技術，例如高階函式和引數多型性。下面是用Standard ML編寫的程式，是階乘函式。請注意，這個版本的階乘與我們之前用 C 編寫的程式有很大不同。這一次，我們沒有解釋如何獲得階乘。我們只是說明給定數字 n 的階乘是什麼。在宣告式世界中，通常使用事物來解釋自身。數字n的階乘是乘法鏈n * (n-1) * (n-2) * ... * 3 * 2 * 1。我們事先不知道n有多大。因此，為了提供n的階乘的一般描述，我們說這個量是n乘以n-1的階乘。歸納地，我們知道如何計算最後一個階乘。鑑於我們也知道如何將兩個整數相乘，我們得到了最終的量。
fun fact n = if n < 1 then 1 else n * fact(n-1)
如今，有許多函式式語言在使用。除了Standard ML之外，值得注意的例子還包括Ocaml、Lisp、Haskell和F Sharp等語言。函式式語言在軟體行業中沒有被廣泛使用。然而，已經有一些用這些語言編寫的非常成熟的專案。例如，Facebook 社交網路的聊天服務是用函式式語言Erlang編寫的。
邏輯程式設計是宣告式程式設計正規化中的第二個子類別。邏輯程式將問題描述為公理和推導規則。它們依賴於稱為統一的強大演算法來證明關於公理的屬性，給定推理規則。邏輯語言建立在稱為霍恩子句的形式化之上。邏輯程式語言家族中只有少數成員。其中最著名的是Prolog。函數語言程式設計中發現的引用透明性的關鍵屬性也存在於邏輯程式設計中。這個正規化中的程式並沒有描述如何找到問題的解決方案。相反，它們解釋了這個解決方案是什麼。下面是用 Prolog 編寫的程式，計算階乘函式。就像 SML 程式一樣，這個版本的階乘函式也描述了數字的階乘是什麼，而不是必須執行哪些計算才能獲得它。
fact(N, 1) :- N < 2.
fact(N, F) :- N >= 2, NX is N - 1, fact(NX, FX), F is N * FX.
Prolog 和相關語言在工業界中的使用甚至比函式式語言更少。然而，邏輯程式設計在學術界仍然非常重要。例如，Prolog 和 Lisp 是人工智慧愛好者首選的語言。
在某些語言中，開發命令式程式更加自然。同樣地，在某些程式語言中，開發宣告式程式（無論是函式式還是邏輯式）更加自然。
正規化選擇可能取決於多種因素。從解決問題的複雜性（面向物件程式設計部分起源於簡化和建模複雜問題的需要）到程式設計師和程式碼可互換性、一致性和模式化等問題，都是為了持續努力將程式設計變成一種工程化和工業化的活動。
然而，在決策的最後階段，可以說程式設計哲學更多的是程式設計師的決策，而不是程式語言本身的強加。例如，以下用 C 編寫的函式以非常宣告式的方式找到了階乘
int fact(int n) { return n > 1 ? n * fact(n - 1) : 1; }
另一方面，也可以在宣告式語言中建立階乘函式的命令式實現。例如，下面我們有一個用 SML 編寫的命令式實現。在這個例子中，結構 ref 表示對記憶體位置的引用。感嘆號 ! 讀取儲存在該位置的值，而命令 while 與命令式語言中的語義相同。
fun fact n =
let
val fact = ref 1
val counter = ref n
in
while (!counter > 1) do
(fact := !fact * !counter;
counter := !counter - 1);
!fact
end;
順便說一句，我們觀察到函式式語言的許多特性最終在命令式語言的設計中找到了作用。例如，Java 和 C++ 今天依賴於引數多型性，以泛型或模板的形式，為開發人員提供構建更可重用軟體的方法。引數多型性是靜態型別函式式語言中常見的特性。這種遷移的另一個例子是型別推斷，今天在 C# 和Scala 等語言中不同程度地存在。 型別推斷 是靜態型別函式式語言中常見的另一個特性。這種最後一種程式語言 Scala 是不同程式設計正規化在現代程式語言設計中如何相遇的一個很好的例子。以下用 Scala 編寫的函式，取自該語言的教程，是著名的快速排序演算法的命令式實現
def sort(a: Array[Int]) {
def swap(i: Int, j: Int) { val t = a(i); a(i) = a(j); a(j) = t }
def sort1(l: Int, r: Int) {
val pivot = a((l + r) / 2)
var i = l
var j = r
while (i <= j) {
while (a(i) < pivot) i += 1
while (a(j) > pivot) j -= 1
if (i <= j) {
swap(i, j)
i += 1
j -= 1
}
}
if (l < j) sort1(l, j)
if (j < r) sort1(i, r)
}
if (a.length > 0)
sort1(0, a.length - 1)
}
下面我們用相同的語言以更宣告式的方式實現了這個演算法。很容易看出宣告式方法更加簡潔。一旦我們習慣了這種正規化，可以說宣告式版本也更加清晰。然而，命令式版本效率更高，因為它在原地進行排序；也就是說，它沒有分配額外的空間來執行排序。
def sort(a: List[Int]): List[Int] = {
if (a.length < 2)
a
else {
val pivot = a(a.length / 2)
sort(a.filter(_ < pivot)) ::: a.filter(_ == pivot) ::: sort(a.filter(_ > pivot))
}
}