# 程式語言期末考前抱佛腳共筆
## 助教說LISP 考一題
[TOC]
> 想抱佛腳啊 [name=yjyu]
> 全部當掉 [name=yjyu]
> >我是馬雲[name=xxxddd]
> > >Dancin[name=Rsiwater]
> > > > WOw[name=unknown]
Before
After
> 我就爛 [name=全班]
## 留言
## LISP
## ch5
### lifetime & scope
- 定義
- 我懶得打了
- e.g.
```cpp=
int fun1(int a, float b)
{
static int cnt;
int i, j;
…
}
```
- cnt:
- scope is local
- lifetime is global
### Named constant
## 阿翔的第六章part2 不知道到底對不對
### Record Types
:::success
- 可能由不同的type資料所組成
- 各個元素都通過name辨識
- 比較：
- Union type
- 在**不同程式執行時間**，儲存不同type值。
- all fields are stored in **the same** location
:::
* 就是**struct**
* 可以包含很多用**名字**分辨的individual elements
* 相比於array
* array使用index找資料
* record使用"name" ex apple.weight
* 呼叫差異
* 由外而內 就是一般C的做法 用"."分隔
* 由內而外 利用"OF"表示 從最小的元素開始
:::warning
* References to Records
* Fully qualified references
* 一般的呼叫方式
* 需include所有的record name
* Elliptical references 假設是上面由內而外的例子，**只要不要ambiguous**，就可以直接 **mid of EMPLOYEE-RECORD**
:::
* access一個array element比access一個 record fields慢，因為index是動態的，但field是靜態的
* Record的實踐
* offect表示此field與record 開頭的相對位置
* Unions Types(神奇的東西)
* 允許在執行時間變換存取的 type values
* 想法:假設有很多**相似但不完全一樣的record**，為了使用這些record就必須設計不同版本的function去對應record
* 若都放進record又浪費空間，因為不會同時使用<br>
* 所以將C、D、E定義成一個union(U)，並佔用相同記憶體空間
* Free Unions
* 此程式語言給用，但不會type checking
* 有些程式語言可以type checking，但就需要多花空間去存一個tag(discriminant)，表明現在的type
* Unions有些安全漏洞(type cheak)，因此其實有程式語言是不允許使用的(java、c#)
### Pointer and Reference Types
* 一段範圍中的memory addresses and a special value
* 可以用於dynamic memory management，heap
* Pointer Operations
* assignment:指定一個值到memory address
* dereferencing:用於將存在指標表示的位置的值取出
* j = *ptr 就是將ptr位置的值放到J
* 如果point指向record 可以用兩種方法表示
```cpp=
(*p).age
p->age
```
* Problems with Pointers
* Dangling pointers:一個potint指向的位置已經被de-allocated
* Allocate a heap-dynamic variable並用一號指標和二號指標指向他
* 利用一號指標Deallocate variable
* 二號指標就會變成dangling pointer
* 如果同樣位置被reallocated，那就會更多問題 型態等等
* Lost heap-dynamic variable:一個 allocated heap-dynamic variable，不再有辦法被access到，就會變成垃圾
* 用point P1去指向一個新的heap-dynamic variable
* P1指向別的地方，原本的variable就變垃圾(memory leakage)
* 
* 解決方案
* **Ada** 在 deallocated heap-dynamic variable時自動釋放pointer
* C++ Reference Types
* 總是 implicitly dereferenced
* 並且宣告後無法轉換Reference的目標
* 簡而言之，可以直接當作兩個變數是一樣的，更動內容兩個會一起被更動
* Dangling Pointer Problem Solutions
* **Tombstone**:一個額外的heap cell，是heap-dynamic variable的指標，而使用者的pointer指向Tombstone，當 variable is de-allocated，那就將tombstone改成**nil**
* 缺點Tombstone不會被de-allocated，並且也比較花時間
* Locks-and-keys:一個pointer改成key和address的組合，並且在allocated Heap-dynamic variables時也將key放到裡面，就可以檢查目前pointer的key和Heap-dynamic variables的key相不相同，不一樣就代表已經被deallocated了
### Type Checking
* 確保operands有被operator兼容
* compatible types:兼容的type，對於一個operator(運算符)是合法的，或是可以被compilper 隱性轉型的
* 這種自動轉型被稱為 **coercion**(強制轉型)
* Type binding 影響type checking是static or dynamic
* 如果所有type都是靜態binding，那 Type Checking就可以是靜態的
* 反之如果所有type是動態binding，那 Type Checking就要是動態(done at run time)
* Strong Typing
* 當遇到函式參數和預設的不同時，或是不同type做運算，就跳type error
* Strong Typing相對於weak typing 也就是compiler會幫你做強制轉型
* Type Compatibility
* 如何決定兩個變數是否是相容的
* 預先設定好是一種
* Name type equivalence: judge by name
* Structure type equivalence: judge by structure
* Name Type Equivalence
* 在同一個宣告式中宣告
* 用相同 **type name**宣告
* 利於實作但限制高
* Subranges of integer types are not equivalent with integer types
* Structure Type Equivalence
* two variables have equivalent types if their types have **identical structures**
* 彈性高但難以實作
* 問題一:兩record有著相同的結構，但意義不同，那算是Type Equivalence嗎?
* 問題二:兩個array幾乎相同，除了index的range不同
* 問題三:若兩個enumeration types數量相同，但內容不同，那算一樣嘛?
### Heap Management
* 複雜的run-time process
* Single-size cells
* 兩種方法回收垃圾
* Reference counters:每個cell都有計時器，當計時器歸零，cell就變成garbage，並且可以被回收，變回可用space
* Reference counters的問題:需要額外空間存放counter，並且在像是chain的cell群時，若其中一個被刪除了，那後面的cell就無法被access
* Garbage collection:
* mark-sweep標記掃描三步驟
* 把所有cell都初始化成garbage
* Marking phase:所有pointer被trace到heap，將reachable cells標記成不是garbage
* 最後將garbage cells are returned to list of available cells
## 小考考古題
### 2017 7~8
1. Please describe what function side effects are (10%). Then, please describe ONE possible solution to solve the functional side effects (10%).
fun的執行影響a的數值，所以a先算還是fun先算會影響b的結果。
```
a = 10;
b = a + fun(&a);
```
* 不允許function改變傳入參數的值
* 不允許function存取全域變數
2. (20%) There are two type conversions, narrowing conversion and widening conversion. Please describe what the narrowing and widening conversion are
* Narrowing conversion:
converts an object to a type that cannot include all of the values of the original type
轉換的目標型態無法容納原始型態的所有資訊
e.g., float to int
* Widening conversion
an object is converted to a type that can include at least approximations to all of the values of the original type
轉換的目標型態可以容納原始型態的所有資訊
e.g., int to float
3. What is the short-circuit evaluation? (10%) What are the results of variables, a and b? (10%)
Ans : a=2, b=1
a = b = 1
b++ = 2
TRUE
b = a = 1
a++ = 2
TRUE
Ans : a=2, b=1
a = b = 1
b++ = 2
b = 1
a ++ = 2
4. (20%) What is the basic idea of guarded commands?
好像沒教
- 非範圍
5. (20%) What is the result in the console after the following java code executes?
1 2 3 4 6 7 8 9 10
### 2017 6-part2
1. Consider the following Ada program. What are the types of Days, Weekdays and Nodes,respectively?(15%) What is the usage of Tag?(10%)
```
type Days is (mon, tue, wed, thu, fri, sat, sun);
subtype Weekdays is Days range mon…fri;
type Node (Tag : Boolean) is record
day: Days;
case Tag is
when True => Count : Integer;
when False => Sum : Float;
end case;
end record;
```
- Days: enumeration
- Weekdays: subrange
- Nodes: record or discriminant record
- the usage go Tag: 判斷record type的discriminant union要宣告哪種變數
2. What is the output n of the following C++ program?(10%)
> n = 10
>
3. There are two different references to records, fully qualified references and elliptical references. Please describe what are the fully qualified references and elliptical references.
- fully qualified references: 就是你要存取record的變數，必需完整的寫出record的變數
- elliptical references: 存取record的變數，在不會矛盾的情況下，可以只寫出record中部份的變數名稱
4. There are two problems for pointers, dangling pointer and lost heap-dynamic variable. Please describe what the two problems are and how the two problems happen.
* Dangling pointer
```
int *arrayPtr1;
int *arrayPtr2 = new int[100];
arrayPtr1 = arrayPtr2;
Delete [] arrayPtr2;
```
* Lost heap-dynamic (Memory Leakage)
```
int *arrayPtr1 = new int[100];
int *arrayPtr2 = new int[100];
arrayPtr1 = arrayPtr2;
// Origin arrayPtr1 leaked;
```
### 2019 Ch6-part1小考
1. Static array
Storage allocation is static (before run-time)
```c
float b[30];
int fun1(){
static int a[20];
};
```
2. Fixed Stack-dynamic array
Storage allocation is done at declaration time during execution
```
int fun1(){
int a[20];
};
```
3. Stack-dynamic array
Get user input n and allocate a n size array
```
Ada 的 array
```
4. Fixed heap-dynamic array
* subscript ranges are statically bound
* storage binding is dynamic but fixed after allocation
```
int *a;
a = new int[20];
a[1] = 18;
```
5. heap-dynamic array
binding of subscript ranges and storage allocation is dynamic and can change any number of times during the array’s lifetime
```
# Python
lst = [1,2,3]
lst.append(4)
print(lst)
# [1,2,3,4]
```
> |Static String|
> |:-:|
> |Length|
> |Address|
>
> |Limited dynamic String|
> |:-:|
> |Maximum length|
> |Current Length|
> |Address|
> a. legal
> b. illegal
> c. illegal
> d. illegal
> e. illegal
- Is an enumeration constant allowed to appear in more than one type definition, and if so, how is the type of an occurrence of that constant checked?
- Are enumeration values coerced to integer?
- Any other type coerced to an enumeration type?
Sign in with Wallet
Connect another wallet