PL Lecture 10/28
Sub Programs Functional Abstraction
之前幾週停課，終於再次開始隔週的 PL Lecture。
順便做個整理，感恩爽燈。
PL Lecture — Subprogram 1
今天影片只談 Scoping, Coroutine, Parameter Passing Method 這三個主題，其他額外的會在後面補充。
Scoping
(主要以 Javascript 程式碼做舉例。)
這邊定義一個 sub1 ，接著呼叫 sub1。
Sub1 裡面有 定義 sub2, sub3, sub4 接著呼叫 sub3。
Javascript 最後的輸出只會有一種正確答案，但因為有兩種可能的語言設計，影片內兩種模式都來進行討論。
這邊順便定義之後會用的 notation。
黃色的框框：是 function 的 call stack ，也就是呼叫一個 function call 會 allocate run-time memory 給它。如果看到 global 就不屬於任何 function 。框框內會有 stack 存在的變數。
黑色的箭頭：Calling sequence ，就是從哪個 stack 網上長。
藍色的箭頭：今天的主題，Reference Environment。當一個 function 執行時，如何找他自己 scope 內找不到的變數、有哪些策略、這件事情會如何影響程式設計和 memory allocation 。
以這個例子來看，global 能看到一個 sub1 的東西，因為是在 global scope 定義的，因此長出一個 sub1 的 stack。
在 sub1 內其實 sub2, sub3, sub4 都是 visible 的，這邊老師手寫補上，不過因為只有呼叫 sub3 所以往上長 sub3 的 stack。
這時候 Reference Environment 要指回上一個 stack 還是第一個 stack ，就是程式設計可以不同的地方。
使用 Shallow Binding 會如何？
這個例子是一種 Shallow Binding ，也就是會指回 caller ，也就是 stack 從哪裡長就指回哪裡。（sub3 藍色箭頭指回去 sub1）
回到例子，sub3 呼叫 sub4 的時候會把 sub2 當作參數帶入。
因此 sub4 的 subx 是指向 sub2 的，再長一個 sub2 的 stack。
最終呼叫 subx （也就是 sub2） ，然後 sub2 的 stack 要去 log x ，但此時要去找 x 在哪。
這時候根據 Shallow Binding 就會往上一個 caller 找，此時找到 x=4。
但是，Javascript 和大部分的語言實作並不用 Shallow Binding。
這跟之前提到 Dynamic Scoping 、 Static Scoping 是一模一樣的概念。
使用 Deep binding 會如何？
Deep binding 的 Reference Environment 會指向 function 被 define 時的 scope。 因此 compiler 在 compile 時就知道 Reference Environment 在哪裏。
Stack 前面的部分都一樣，global 的 sub1 被呼叫，因此會長一個 sub1 的 stack 。接著 sub1 呼叫 sub3，而 sub3 和接下來的 sub2, sub4 的 Reference Environment 會指向 sub1。
因此會找到 x=1。
Function Scoping 的例子
例子兩個 f ，外面一個，裡面一個。
裡面的 f 用一個左括號、右括號，製造一個 local scope ，避免 name conflict。
一些Immediately Invoked Function Expression (IIFE) or Self Executing Anonymous Function 討論補充
https://en.wikipedia.org/wiki/Closure_(computer_programming)
https://www.tutorialspoint.com/Why-are-parenthesis-used-to-wrap-a-JavaScript-function-call
Global 會有一個 f ，也就是 x => x+1 的 f 。
而 => 的左手邊代表 argument ，箭頭右手邊代表 body。
https://en.wikipedia.org/wiki/Function_type
如果左手邊的 arguments 沒有需要的變數，就需要透過 Reference Environment 。
Global 定義了 f，接著為了 evaluate 括弧內的 expression ，會往上長一個 stack ， anon 我猜是 anonymous 。
這裡面定義的 f 是指向這段 code （影片裡面的少 n*）n => n<= 0 ? 1 : n* f(n-1); ，為一個 recursion 關係。
接著 evaluate 的 f(2) 在 global 所以這裡面的 f 是指向 x => x+1 ，f(2) 會得到 n=3。
因為要繼承 function 被定義的 scope ，所以最上面 stack 的 f 的 Reference Environment 會指向 anon 。
判斷之後會 recursive 的找 f 也就是這個 function 被定義的 scope，最後得到 6 。
此時，最認真上課的 KK 發問了，就是之前關於 IIFE 的相關討論，這邊就先略過。
Function as Parameter 的例子
這個還算滿單純直覺，就先不紀錄。
Function as Return Value 的例子
這邊會先看到 addx ，是一個 Curry function。
https://en.wikipedia.org/wiki/Currying
addx 會吃一個 x 後 return 一個 function，因此可以用 addx 去創造一個什麼都 +5 的 add5 function 。
Add5 被定義的時候會長出一個 addx 的 stack ，return 值會是 y => x+y 這個 function 。
這個 function 是被這個 addx 的 stack 定義出來，因此之後 add5 被呼叫，Reference Environment （藍色箭頭）就要指向 function 被 define 的 Reference Environment。
很溫暖的爽燈還問大家有沒有問題。
接著執行 add5 ，長出一個 add5 的 stack ，因為是用 y => x+y 這個 function 因此 Reference Environment （藍色箭頭）也是指向同一個地方。
爽燈說這邊跟一般的 C 或 C++ 的程式不同，執行完 stack 不會被回收。
當允許 Function as Return Value 的時候， stack 必須要保留一些 被包起來的 Environment。
在描述這些的關鍵字：Curry function, higher order function, Closure
幾個重點：
如果程式語言要支援 Functions as Returned Values…
Run-time stack 必須用 linked list 實作（不能是 array structure）。原本不支援的 JavaScript 透過包一層來支援 arrow function。
Run-time stack 不會直直往上長，比較像 tree。
Object 要看 run-time 或 interpreter 怎麼實作 garbage collector。
目前大部分的熱門語言都用 Deep Binding ，以上就是 Scoping 的一些討論。
未來遇到一個程式語言，知道他是 Dynamic 或 Static Scoping, Deep 或 Shallow binding 就比較好掌握這個語言的行為。
