※ 引述《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