Re: [問題] letrec 為何可以成立？ (In scheme, ma …
※ 引述《SansWord (是妳)》之銘言：
: 課程上正在用scheme實作一個interpreter(mini-scheme),有environment機制
: 概念上是先訂一組global environment
: 另外這個interpreter也支援high order function.
: 在這interpreter裡面，lambda function evaluation的實作是:
: (eval (lambda ( arguments ) (function body) ) env )
Ok ok... 由於東西比較多，我用我比較熟悉的 "pseudo Haskell" 的
語法混合一些你的符號解釋一下，希望看得懂....
假設我們定義一個小語言，有數字、加減法、lambda, LET, LETREC
等等（我把被解譯的語言的關鍵字寫成大寫）。函數 eval 大約是像這樣
eval n env = n -- 看到數字就傳回數字
eval a env = lookup a env -- 看到變數就去環境裡查查看
eval (\a.e) env = (%func a e, env)
--%func 應該是某個資料結構，表示這個 closure, 把目前的環境記下來
eval (e1 e2) env =
let (%func a body, env') = eval e1 env
v2 = eval e2 env
in eval body ((a,v2):env')
-- 把 env' (而不是 env) 擴充後去執行 body
Let 怎麼做呢？大約是這樣
eval (LET a=e1 IN e2) env =
let v1 = eval e1 env
in eval e2 ((a,v1):env)
其實 LET 的 case 像是前面兩個 case 的合體。確實有些函數語言
中會說
LET a = e1 IN e2
其實就是
(\a. e1) e2
另外我們會發現我們是用 host 語言的 let 在定義被解譯的語言的 let.
那 LETREC 呢？如你所說，我們需要一個遞迴的環境。遞迴的環境怎麼產生呢？
既然 host 語言有 letrec, 那就用吧:
eval (LETREC a=e1 IN e2) env =
letrec env' = (a,v1) : env
v1 = eval e1 env'
in eval e2 env'
e1 要在 env' 這個環境中 eval, 而 env' 之中必須把
a 指到 e1 求值的結果 v1.
這麼做的條件是 host 語言已經有 letrec, 可以用來取遞迴定義的
解。如果沒有，「沒有 type」的 lambda calculus 也有辦法取
取遞迴定義的 fixed-point (例如前面說的 Y combinator).
: 文章一開始提到的那個發問裡面
: 有提到說如果語言機制裡面允許 "mutable references" 就可以做到我正在做的事情
: 可是我想這也只是工具上的不同
這樣則是比較「操作」的作法，直接用副作用去改環境。
如果是為了效率也許這樣做比較好（不是很確定）。
避免用副作用則是讓這個直譯器有比較清楚的數學定義，
可以知道更多的性質。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.192.160.134
討論串 (同標題文章)
PLT 近期熱門文章
PTT數位生活區 即時熱門文章