看到一个 Scheme 的实现, 用了 delay
这个函数...
https://www.shido.info/lisp/scheme_lazy_e.html
但是底层, 比如说编译到 IR 或者汇编, 这种功能怎样实现?
delay不是一个函数,而是一个宏(macro),它的具体实现,可以看一下R5RS标准后面的附录,记得是有delay的实现的
scheme
(define-syntax mydelay (syntax-rules (define) ((mydelay (define expr ...)) (error "can't delay define -- macro mydelay")) ((mydelay expr ...) (cons 'promise (lambda () (begin expr ...)))))) (define-syntax myforce (syntax-rules () ((myforce delayed-expr) (if (and (pair? delayed-expr) (eq? 'promise (car delayed-expr))) ((cdr delayed-expr)) (error "not a promise")))))
我写的一个很简陋的实现,就是把一个表达式用一个函数封装一下……
惰性求值的底层其实是借助了thunk。粗浅的解释就是一个求值用的函数和它的自由变量环境的结合。
每一个表达式在其值被需要之前,总是先存储为一个thunk,一旦其值必须要被求解出来,就强迫执行求值过程。
比如说,如果有这样的列表:
list :: [Integer]
list = [1..]
它首先会被实现为对系统函数enumFrom的调用,调用的结果类似这样:
enumFrom :: Integer -> [Integer]
enumFrom n = n : enumFrom (n + 1)
list = enumFrom 1
= 1 : enumFrom 2
= 1 : 2 : enumFrom 3
= 1 : 2 : 3 : enumFrom 4
-- on and on ...
其中每个enumFrom的调用都会被实现为一个thunk。
我们以take 5 list为例。
take函数用(:)进行模式匹配,类似于:
take :: Int -> [a] -> [a]
take 0 _ = []
take n (x:xs) = x : take (n-1) xs
take _ _ = error "Invalid call of take."
需要对列表进行模式匹配时,将要求从thunk中匹配一个(:)运算符(构造器),这时thunk求值一层,从list展开成1 : thunk2,模式匹配成功,取出了1。take函数会要求进一步匹配,新thunk(即thunk2)也会被求值,又产生新的thunk。当thunk中的值不再需要时,就不会进一步求值了。这样,无穷的求解步骤就被拆分开来,总是用一个thunk来表达无穷的部分,就不会耗尽内存了。
丢链接跑 If Haskell were strict, what would the laziness be like?
其实大意就是在Haskell这种Immutable语言里一个lazy的值a
和一个() -> a
函数等价
惰性计算(Lazy Evaluation)是haskell的一大特点之一。无限列表也是Lazy Evaluation的一种表现。它的底层实现感觉上没那么重要吧。了解概念就OK了,反正它很快,O(1)的时间复杂度、空间复杂度。