我可以检查Haskell是如何分配内存的吗

Question

由于懒惰评估，Haskell可以在一瞬间处理以下表达式。

head.head $ let m = 1000000000000000 in map (n -> [m*n .. m*(n+1)]) [1 .. m] 

但我注意到下面的表达式并没有结束，但内存使用率一直很低。

last.last $ let m = 1000000000000000 in map (n -> [m*n .. m*(n+1)]) [1 .. m]

哈斯克尔能做到这一点并不奇怪。但我想知道它是如何运作的。更确切地说，haskell是如何分配内存的。有什么方法可以检查内存布局或类似的东西吗？

Answer 1

让我们稍微简化一下这个例子，看看会发生什么。你基本上可以通过思考懒惰评估和图形简化来解决这个问题，而不需要再低一层。让我们看看ourLast (mkList 3)的简化简化，代码是：

ourLast :: [a] -> a
ourLast [] = error "ourLast []"
ourLast (x:[]) = x
ourLast (_:xs) = ourLast xs
mkList :: Int -> [Int]
mkList 0 = []
mkList n = let rest = mkList (n-1) in n : rest

?foo的意思是"一个我们还没有看到的值"。我们用"let"创建这些。foo@bar的意思是"我们已经计算出的值，我们已经计算出来是bar"当我们检查?foo时，它变成了foo@barfoo := bar的意思是"我们还没有弄清楚foo是bar">

-- We start here by creating some value and giving it to ourLast to
-- look at.
let ?list3 = mkList 3
ourLast ?list3
-- At this point ourLast examines its argument to figure out whether
-- it's of the form (_:_) or []
-- mkList sees that 3 /= 0, so it can pick the second case, and it
-- computes the value for ?list3.
-- (I'll skip the arithmetic reductions and other boring things.)
let ?list2 = mkList 2
list3 := 3 : ?list2 -- we don't need to compute ?list2 yet, so
-- (mkList 3) is done and we can go back to ourLast
ourLast list3@(3 : ?list2)
-- ourLast needs to examine ?list2 to find out whether it's [] or not,
-- so mkList does the same thing again
let ?list1 = mkList 1
list2 := 2 : ?list1
ourLast list3@(3 : list2@(2 : ?list1))
-- Now ourLast has enough information to continue;
-- ourLast (_ : xs@(_ : _)) = ourLast xs
-- Notice how we don't need to compute list2 a second time; we save its
-- value the first time we compute it. This is what lazy evaluation is.
ourLast list2@(2 : ?list1)
-- at this point, there are no references to `list3` anywhere, so it
-- can be GCed.
-- Repeat (ourLast examines ?list1, mkList sees that 1 /= 0).
let ?list0 = mkList 0
list1 := 1 : ?list0
ourLast list2@(2 : list1@(1 : ?list0))
ourLast list1@(1 : ?list0)
-- Can GC list2.
-- Now mkList is being called with 0, so it just returns an empty list.
list0 := []
ourLast list1@(1 : list0@[])
1
-- We're done! (And we can GC list1.)

注意，在任何给定的时间，我们只需要实际分配几个thunk，其余的要么还没有计算出来，要么可以GCed。当我们评估ourLast list3时，评估在ourLast和mkList之间来回跳跃(有点像协程)。

如果你想更准确地了解Haskell编译器的工作方式，在"分配发生的时间和方式"的层面上，以下内容很有帮助：

• 在现有硬件上实现懒惰函数语言：Spineless Tagless G-机器(JFP论文)
• 函数式程序设计语言的实现(在线书籍)

仅仅从图约简的角度来理解懒惰评估是如何工作的——例如本文——是有用的。

Answer 2

我会按照这里的解释进行一些堆分析。为此，您需要使用cabal安装评测库。解释很全面，很容易理解。