【PL理論深化】(13) 變量與環境：文法結構 | 真假表達式：isZero E | let 表達式疊放 | 定義的規則

【PL理論深化】(13) 變量與環境：文法結構 | 真假表達式：isZero E | let 表達式疊放 | 定義的規則 | 條件語句的使用

💬?寫在前面：從現在開始，讓我們正式設計和實現編程語言。首先，讓我們擴展在之前定義的整數表達式語言，以便可以使用變量和條件表達式。

0x00 文法結構

0x01 真假表達式：isZero E

0x02 let 表達式疊放

0x03 定義的規則

0x04 條件語句的使用

0x00 文法結構

擴展后的語言的文法結構如下，在整數表達式語言中增加了四種文法：

在程序中，可以在任意可以出現表達式的位置使用變量 $x$ ?(隨機變量)

let $x$ ?= $E_1$ in? $E_2$ 是一個聲明變量 $x$ ?的表達式。

它先將 $E_1$ ?的值賦給 $x$ ，然后計算 $E_2$ ?的值。在此期間，變量 $x$ ?的有效范圍是 $E_2$ 。

if $E_1$ ?then $E_2$ ?else? $E_3$ ? 是一個條件表達式，其計算方式如下。

此后，我們約定符號? $\top$ ?表示?true，符號? $\bot$ ?表示 false。

首先計算表達式 $E_1$ ，其結果必須是 $\perp$ ?或 $\top$ 。

如果 $E_1$ ?的值是 $\top$ ，則計算 $E_2$
如果 $E_1$ ?的值是 $\bot$ ，則計算 $E_1$ 。

0x01 真假表達式：isZero E

為了使用條件表達式，需要創建產生 真/假 的表達式，因此我們添加了語法：

$\textrm{iszero}\,\, E$

它計算表達式 $E$ ?的值，如果值為 0，則計算為 $\top$ ，否則為 $\bot$ 。

由于它類似于 OCaml 的語法，可以很容易感受到可以編寫哪些程序，舉幾個例子：

下面是一個程序，首先變量 $x:= 1$ ，然后計算? $x+2$ 的值，結果是 3

let x = 1 in x + 2

0x02 let 表達式疊放

在 let 表達式的? $E_2$ 位置上可以放置另一個 let 表達式

let x = 1
in let y = 2in x + y

表達式 $x+y$ ?中， $x$ ?和 $y$ ?分別代表 1 和 2，因此程序的計算結果是 3。

也可以在 let?表達式的? $E_1$ 位置上放置另一個 let?表達式，如下所示。

let x = let y = 2in y + 1
in x + 3

表達式 let y = 2 in y + 1?的值為 3，將其命名為 $x$ ?后，計算表達式? $x+3$ 的結果為 6。

在計算表達式? $x+3$ 時，請注意變量 $y$ ?不可用。

變量 $y$ ?的作用范圍僅限于表達式 $y+1$ ，因此在其他地方無法使用。

因此，下面的程序在語法上沒有問題，但在執行時會出現問題。

let x = let y = 2in y + 1
in x + y

0x03 定義的規則

可以多次使用相同的名稱進行定義，如下所示。

let x = 1
in let y = 2in let x = 3in x + y

在最后一行計算 $x+y$ ?時， $x$ ?表示最后定義的值 3，因此? $x+y$ 的值是 5。

重新定義具有相同名稱的變量并不會改變先前變量的值。

使用 let 定義變量并不是修改現有變量的值，而是創建一個新名稱，在其作用域內具有意義。

例如下面的程序：

let x = 1
in let y = let x = 2in x + xin x + y

上述程序計算的結果是 5。第一行定義變量 $x:= 1$ ，第二行定義的 $x:= 2$ 。

因此第三行的? $x+x$ 的值是 4，因此變量 $y$ ?的值為 4。

在最后一行的表達式? $x+y$ 中，變量 $x$ ?指的是第一行定義的 $x$ ，因此? $x+y$ 的值為 5。

0x04 條件語句的使用

條件語句的使用如下所示。這是一個計算整數 1 的程序。

let x = 1
in let y = 2in if iszero (x - 1) then y - 1 else y + 1

現在，由于程序不僅可以計算整數，還可以計算真 / 假值，因此存在一些由于類型不匹配而無法執行的程序，即存在 類型錯誤 (type error) 的程序。例如，看下面的程序。

let x = 1
in let y = iszero xin x + y

加法是針對兩個整數定義的操作，但由于? $y\in \left \langle bool \right \rangle$ ，因此在計算? $x+y$ 時會發生類型錯誤。

由于我們的語言目前沒有靜態類型系統，所以無法在執行前發現這類類型錯誤。

如果在運行過程中發生類型錯誤，程序將會因此而非正常終止。

📌 [ 筆者 ]? ?王亦優
📃 [ 更新 ]? ?2022.9.14
? [ 勘誤 ]?? /* 暫無 */
📜 [ 聲明 ]? ?由于作者水平有限，本文有錯誤和不準確之處在所難免，本人也很想知道這些錯誤，懇望讀者批評指正！

📜 參考資料?

- R. Neapolitan, Foundations of Algorithms (5th ed.), Jones & Bartlett, 2015.

- T. Cormen《算法導論》（第三版），麻省理工學院出版社，2009年。

- T. Roughgarden, Algorithms Illuminated, Part 1~3, Soundlikeyourself Publishing, 2018.

- J. Kleinberg&E. Tardos, Algorithm Design, Addison Wesley, 2005.

- R. Sedgewick&K. Wayne，《算法》（第四版），Addison-Wesley，2011

- S. Dasgupta，《算法》，McGraw-Hill教育出版社，2006。

- S. Baase&A. Van Gelder, Computer Algorithms: 設計與分析簡介》，Addison Wesley，2000。

- E. Horowitz，《C語言中的數據結構基礎》，計算機科學出版社，1993

- S. Skiena, The Algorithm Design Manual (2nd ed.), Springer, 2008.

- A. Aho, J. Hopcroft, and J. Ullman, Design and Analysis of Algorithms, Addison-Wesley, 1974.

- M. Weiss, Data Structure and Algorithm Analysis in C (2nd ed.), Pearson, 1997.

- A. Levitin, Introduction to the Design and Analysis of Algorithms, Addison Wesley, 2003. - A. Aho, J. Hopcroft, and J. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983.

- E. Horowitz, S. Sahni and S. Rajasekaran, Computer Algorithms/C++, Computer Science Press, 1997.

- R. Sedgewick, Algorithms in C: 第1-4部分（第三版），Addison-Wesley，1998

- R. Sedgewick，《C語言中的算法》。第5部分（第3版），Addison-Wesley，2002

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/37251.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/37251.shtml
英文地址，請注明出處：http://en.pswp.cn/web/37251.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！