程式語言期末
===

Chapter 5
---
- ### Imperative Language : abstraction of von Neumann architecture
- 主要成分 : memory , processor
- ### Variables
- 分類 : Name , Address , Value , Type , LifeTime , Scope
- ### Binding
- Binding time : time at which a binding takes place
:::success
1. Language design time : operator symbol -> operation
2. Language implementation time : bind floating point type to a representation
3. Compile time : variable -> particular data type or 決定運算元的型態
4. Load time : variable -> memory cell (or c static variable)
5. Runtime : non-static local variable -> memory cell
:::

- Static binding : binding第一次出現在runtime之前在執行過程中一直保持不變
:::success
1.explicit declaration : 以陳述式明確宣告變數
2.implicit declaration : 使用某個變數前不用宣告即可使用
:::
- Dynamic binding : binding第一次出現在執行的時候或者在執行過程中會改變

- ### Storage bindings
- allocation : getting a cell from some pool of available cell and assigning it to a variable
- deallocation : putting a cell back into pool

- ### Lifetime
-定義 : 一個變數從allocation到deallocation的時間
:::success
**類型**
1. Static variable : 執行前已配置記憶體空間，執行結束後才釋放記憶體空間
2. Stack-Dynamic variable : 執行宣告時才配置記憶體空間，函式結束後回收記憶體空間
3. Explicit Heap-Dynamic varia : allocated and deallocated by explicit directive(指示) , only referenced through pointer(*) or references(&)
4. Implicit Heap-Dynamic variable : allocation and deallocation by assignment statements
:::

- ### Scope
- 定義 : range of statements over which it is visible
:::success
1. Static scope : find declaration -> increasingly larger enclosing scopes until one is found for the given name
2. Global scope : variable definition appearing outside any function
> definition
> declaration : 避免變數被重複定義(extern)
3. Dynamic scope : based on calling sequences , searching back through the chain of subprogram calls
:::
---
Chapter 6 - 1
---
- ### String length
:::success
1. Static : length is static and set when string is created
2. limited dynamic length : varying length up to a declared maximum
3. dynamic : no maximum
:::

- ### String implementation
:::success
1. Static length : compile - time
2. Limited dynamic length : run - time
3. dynamic length : run - time
:::

- ### User-Defined Ordinal Types
- e.g : enumeration 、 subrange
- 定義 : values can be counted , values can be put in a one - to - one correspondence with the positive integers.

- ### Array
- Static array : subscript statically bound and storage allocation is static
>e.g. static int a[20]; ( C )
- Fixed Stack - Dynamic : subscript statically bound , storage allocation is done at declaration during executione
>e.g.func(){ int a[20]; }; ( C )
- Stack - Dynamic : subscript and storage allocation are dynamic bound at elaboration time but fixed during lifetime
>e.g. List : array(1 .. List_Len) of Integer; (Ada)
- Fixed Heap - Dynamic : subscript statically bound , storage allocation is dynamic but fixed after allocation
>e.g. int *a = new int[20]; (C++)
- Heap - Dynamic : subscript and storage allocation are dynamic bound and can change during array's lifetime
>e.g. a = [0 , 1 , 2] (JS)

- ### Rectanguular Array
- 定義 : 每個row的element數量一樣，每個column的element數量一樣

- ### Jagged matrix
- 定義 : 每個row會有不一樣的element數量

- ### Access function for one-dimention array:
`address(list[k])`
` = address(list[lower_bound]) `
`+ ((k - lower_bound) * element_size)
`

- ### Access function for two-dimention array:
`location(a[i , j])`
`= address of a[row_lb , col_lb]`
`+ (((i - row_lb) * n) + (j - col_lb)) * element_size`
---
Chapter 6 - 2
---
- ### Record Type
- 定義 : 不同的資料型態的element，由name辨識
- 與array比較 : 陣列是由index去找資料，record由name去找資料，讀取資料的速度record會比array快因為array的subscript是動態record是靜態
- references to record
1. Fully qualified reference : include所有的record name
2. Elliptical reference : 只要不ambiguous就可以使用
- implementation
1. filed access using offset
2. offset : field和record開頭的相對位置
- ### Union Type
- 定義 : 可以在不同的執行時間儲存不同的資料型態，並共用相同的記憶體
- free union v.s. discriminated union : 前者沒有type checking，後者多一個tag來紀錄資料型態

- ### Pointer
- 定義 : 一段範圍的memory address和一個special value(nil)，可用於dynamic memory management like heap
- opearation :
1. assign : 指定一個值到memory address
2. dereference(反參照) : 取出存在指標表示的位置其值
- problem with pointer
:::success
1. Dangling pointer : 指標指向一個已經deallocated的heap-dynamic變數
>e.g.兩個指標指向同一個變數，我們對指標一deallocate，這樣指標二就會變成dangling pointer
2. Lost heap-dynamic variable : 一個allocated heap-dynamic變數已無法被程式使用，造成memory leakage(又稱為garbage)
>e.g.指標指向變數一，後來指標改指向變數二，而變數一就會變成garbage
:::

- Dangling pointer solution
:::success
1. Tombstone : 額外的heap cell，它可以指向heap-dynamic變數，當變數被deallocated的時候tombstone會設為nil
2. Locks - and - keys : 一個pointer被改成key和address組合，並在allocated heap-dynamic變數將key放入。當pointer的key和變數的key不相等時代表變數已被deallocated
:::
- ### Reference
- 定義 : always implicitly dereferenced

- ### Type Checking
- 定義 : 確保operands有被operator兼容
- Compatible type :兼容的type，對於一個operator(運算符)是合法的，或是可以被compilper 隱性轉型的(coercion)
- Type binding : 影響type checking是static or dynamic
- Strong type : 當遇到函式參數和預設的不同時，或是不同type做運算，就跳type error，Strong Typing相對於weak typing 也就是compiler會幫你做強制轉型
- Type compatibility :
:::success
問題 : 如何決定兩個變數是否是相容的?
-> 先預設好是一種
-> Name type equivalence : same declaration , same type name
or
-> Structure type equivalence : have identical structure
:::

- ### Heap management
- Reference counter : 每一個cell都有counter，當counter變為0時，cell變成garbage並回收成可用空間
- Mark-Sweep : 初始所有cell -> all pointers are traced into heap , reachable cells are marked as not garbage -> all garbage cells are returned to list of available cells
---
Chapter 7
---
- ### Arithmetic expressions
1.operator(運算子)
2.operand(運算元)
3.parenthese(括號)
4.function call

- ### Operator
- e.g. unary operator has one operand，以此類推
- Precedence rule : 決定運算子的優先順序
>parenthese -> unary operator -> 指數 -> * / -> + -
- Associativity rule : 決定鄰近且相同優先順序的運算子的優先順序
- Evaluation order :
1.Varialbe
2.Constant
3.Parenthesized expression
4.Function reference

- ### Functional side effect
- 定義 : 當函式的某個參數改變或者某個全域變數改變，可能會產生不同的結果
- Solution :
1. No two-way parameters in function : 不允許function改變傳入的參數
2. No access to globals in function : 不允許function存取全域變數
3. Write the language definition to demand that operand evaluation order be fixed

- ### Referential transparency
任兩個expression如果有相同的值的話，在不影響程式形況下可以互相代替

- ### Overload operator
有兩個功能以上的operator被稱為operator overloading

- ### Type conversion
- Narrowing conversion : 轉換資料型態之後原本的資料型態範圍沒有包含轉換後的資料型態範圍
- Widening conversion : 轉換資料型態之後原本的資料型態範圍包含轉換後的資料型態範圍
- Mixed mode : expression中operand有不同資料型態(透過coercion)

- ### Error in expression
1. 除以0
2. overflow or underflow
以上狀況會出現run-time error(exception)

- ### Short circuit evaluation
expression的結果不用跑完所有的operand/operator就可以得到結果
---
Chapter 8
---
- ### Guarded command
- basic idea : if the order of evaluation is not important , the program should not specify one
- semantic : when the construct is reached
Evaluate all boolean expression ->
if more than one are true , choose one non-deterministically ->
if none are true , it is a runtime error