---
# System prepended metadata

title: 程式語言期末考前抱佛腳共筆

---

# 程式語言期末考前抱佛腳共筆

## 助教說LISP 考一題

[TOC]

![yjyu2](https://www.csie.nuk.edu.tw/elfinder/files/teacherProfile/yjyu2.JPG =250x)
> 想抱佛腳啊 [name=yjyu]

![](https://i.imgur.com/Ssizaah.png =250x)
> 全部當掉 [name=yjyu]
> >我是馬雲[name=xxxddd]
> > >Dancin[name=Rsiwater]
> > > > WOw[name=unknown]

Before
![](https://i.imgur.com/n0mKAtL.png =300x)
After
![](https://i.imgur.com/NAWU8fh.png =300x)

> 我就爛 [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的做法 用"."分隔![](https://i.imgur.com/1colAdv.png)
    * 由內而外 利用"OF"表示 從最小的元素開始![](https://i.imgur.com/hr0ggYL.png)
:::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 開頭的相對位置![](https://i.imgur.com/xTg7baE.png)

* Unions Types(神奇的東西)
    * 允許在執行時間變換存取的 type values![](https://i.imgur.com/NwuYqRU.png)
    * 想法:假設有很多**相似但不完全一樣的record**，為了使用這些record就必須設計不同版本的function去對應record![](https://i.imgur.com/meD1UgC.png =400x)![](https://i.imgur.com/iyMxHT2.png)
    * 若都放進record又浪費空間，因為不會同時使用<br>![](https://i.imgur.com/5Ck9SAV.png)
    * 所以將C、D、E定義成一個union(U)，並佔用相同記憶體空間![](https://i.imgur.com/9FhtcNl.png)
    * Free Unions
        * 此程式語言給用，但不會type checking
    * 有些程式語言可以type checking，但就需要多花空間去存一個tag(discriminant)，表明現在的type![](https://i.imgur.com/yyjpiRN.png)![](https://i.imgur.com/GTQtb0u.png)
    * 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![](https://i.imgur.com/h5OwkKO.png =300x)
* 如果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)
    * ![](https://i.imgur.com/Zu2yHEC.png)
    * 解決方案
        * **Ada** 在 deallocated heap-dynamic variable時自動釋放pointer

* C++ Reference Types
    * 總是 implicitly dereferenced 
    * 並且宣告後無法轉換Reference的目標
    * 簡而言之，可以直接當作兩個變數是一樣的，更動內容兩個會一起被更動![](https://i.imgur.com/8xY6osG.png)![](https://i.imgur.com/ANoPwxA.png =400x)

* Dangling Pointer Problem Solutions
    * **Tombstone**:一個額外的heap cell，是heap-dynamic variable的指標，而使用者的pointer指向Tombstone，當 variable is de-allocated，那就將tombstone改成**nil**![](https://i.imgur.com/P7aU8ca.png)
        * 缺點Tombstone不會被de-allocated，並且也比較花時間
    * Locks-and-keys:一個pointer改成key和address的組合，並且在allocated Heap-dynamic variables時也將key放到裡面，就可以檢查目前pointer的key和Heap-dynamic variables的key相不相同，不一樣就代表已經被deallocated了![](https://i.imgur.com/niRjAFB.png)

### Type Checking
* 確保operands有被operator兼容![](https://i.imgur.com/YI6Ohfb.png)
* 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**宣告![](https://i.imgur.com/kcwj02x.png)
    *  利於實作但限制高
        *  Subranges of integer types are not equivalent with integer types![](https://i.imgur.com/xPzripE.png)![](https://i.imgur.com/CzdbbMp.png)

* Structure Type Equivalence
    * two variables have equivalent types if their types have **identical structures**
    * 彈性高但難以實作
        * 問題一:兩record有著相同的結構，但意義不同，那算是Type Equivalence嗎?![](https://i.imgur.com/8Y1iBre.png)
        * 問題二:兩個array幾乎相同，除了index的range不同![](https://i.imgur.com/zbqHNnu.png)
        * 問題三:若兩個enumeration types數量相同，但內容不同，那算一樣嘛?![](https://i.imgur.com/6XydTAa.png)

### 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![](https://i.imgur.com/WpWqLjn.png)

## 小考考古題
### 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%)
    ![](https://i.imgur.com/K4EQdsQ.png)
    Ans : a=2, b=1
    a = b = 1
    b++ = 2
    TRUE
    b = a = 1
    a++ = 2
    TRUE
    
    ![](https://i.imgur.com/mocRzge.png)
    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?
![](https://i.imgur.com/svkvUPy.png)
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%)
![](https://i.imgur.com/iIOaSKY.png)
> 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;
```

![](https://i.imgur.com/8J3cY4l.png)

* Lost heap-dynamic (Memory Leakage)
```
int *arrayPtr1 = new int[100];
int *arrayPtr2 = new int[100];
arrayPtr1 = arrayPtr2;
// Origin arrayPtr1 leaked;
```
![](https://i.imgur.com/2GqTWuf.png)


### 2019 Ch6-part1小考
![1.](https://i.imgur.com/l0x1jAY.png)
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
![](https://i.imgur.com/nsURFl6.png =300x)

```
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]
```
![2.](https://i.imgur.com/gDPmCMx.png)
> |Static String|
> |:-:|
> |Length| 
> |Address|
> 
> |Limited dynamic String|
> |:-:|
> |Maximum length|
> |Current Length| 
> |Address|

![3.a](https://i.imgur.com/c8YuODw.png)
![3.b](https://i.imgur.com/R8adqgv.png)
> a. legal
> b. illegal
> c. illegal
> d. illegal
> e. illegal

![4.](https://i.imgur.com/jYB2GZQ.png)
- 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?

