Haskell 的无限列表, 底层实现是怎样的?

Question

看到一个 Scheme 的实现, 用了 delay 这个函数...
https://www.shido.info/lisp/scheme_lazy_e.html
但是底层, 比如说编译到 IR 或者汇编, 这种功能怎样实现?

Answer 1

惰性求值的底层其实是借助了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来表达无穷的部分，就不会耗尽内存了。

Answer 2

惰性计算（Lazy Evaluation）是haskell的一大特点之一。无限列表也是Lazy Evaluation的一种表现。它的底层实现感觉上没那么重要吧。了解概念就OK了，反正它很快，O(1)的时间复杂度、空间复杂度。

Answer 3

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")))))

我写的一个很简陋的实现，就是把一个表达式用一个函数封装一下……

Answer 4

丢链接跑 If Haskell were strict, what would the laziness be like?
其实大意就是在Haskell这种Immutable语言里一个lazy的值a和一个() -> a函数等价