我正在阅读 Shriram 的 PLAI,这让我陷入了以下问题:
你能证明急切和懒惰的政权总是会产生相同的答案吗?(Shriram 要求查看他开发的语言,但还有其他方法可以证明这一点以及如何证明吗?)
急切的评估总是会随着更少的步骤而减少吗?
这是 Clojure 中的替换代码和热切评估代码。
;; Gets W-lang and returns the computed number
;; (evaluate (let x (num 10) (let y x x)) -> 10
;; (evaluate (let x (num 10) (let y (add x (num 10)) y)) ->20
;; (evaluate (let x 10 (let x x x ))) -> 10
;; (evaluate (let x 10 (let x (+ 10 x)
;; (let y (let y (+ 10 x) y)
;; (+ x y))))-> 50
(defn evaluate[W-lang]
(condp = (first W-lang)
'num (second W-lang)
'add (+ (evaluate (second W-lang))
(evaluate (third W-lang)))
'sub (- (evaluate (second W-lang))
(evaluate (third W-lang)))
'let (evaluate (subst (second W-lang)(third W-lang)
(forth W-lang)))))
;; subst: symbol value W-Lang -> W-lang
;; substitutes the symbol and returns a W-Lang
(defn subst[id value W-lang]
(cond
(symbol? W-lang) (if (= id W-lang) value W-lang)
(seq? W-lang)
(condp = (first W-lang)
'num (list 'num (first (rest W-lang)))
'add (list 'add (subst id value (second W-lang))
(subst id value (third W-lang)))
'sub (list 'sub (subst id value (second W-lang))
(subst id value (third W-lang)))
'let
(if (= (second W-lang) id)
(list 'let (second W-lang)
(subst id value (third W-lang))
(forth W-lang))
(list 'let(second W-lang)
(subst id value (third W-lang))
(subst id value (forth W-lang))))
W-lang)))