迭代产生 StackOverflow 错误
Iterate produces StackOverflow errors
所以我刚开始学习 Frege 和 Haskell。我有使用函数式语言的经验，因为我现在已经使用 Clojure 几年了。
我想尝试的第一件事是我在斐波那契数列上的惯用方法。
next_fib (a, b) = (b, a + b)
fibs = map fst $ iterate next_fib (0, 1)
fib x = head $ drop x fibs
这就是弗雷格的结果。它有效，但对于 fib 的数字非常高，例如(fib 4000)，它会抛出 Whosebug 错误。这让我感到惊讶，因为 Clojure 中的相同功能可以正常工作。这是 Frege 错误还是我把整个惰性评估都弄错了？
你可能不会"get the whole lazy evaluation thing wrong"，但在这种情况下你被太懒惰的评估咬了两次。
虽然GHC在这方面本质上与弗雷格完全一样，但结果却不同，似乎对弗雷格不利。
但是 Haskell 可以通过非常大的 thunk 获得 awya [见下文]，而 Frege 早期中止堆栈溢出的原因是运行时系统管理堆和堆栈的方式。 Haskell RTS 非常灵活，可以在需要时将大部分可用内存分配给堆栈。而 Frege 的运行时系统是 JVM，它通常以一个很小的堆栈开始，刚好足以容纳几百个调用深度。正如您所观察到的，为 JVM 提供足够的堆栈 space 可以使思考工作，就像在 GHC 中一样。
由于 JVM 中的堆栈 space 一直很稀缺，我们在 Frege 中开发了一些技术来避免不必要的和不必要的懒惰。下面将解释其中的两个。最后，在 Frege 中，您被迫及早控制懒惰的不良影响，而 GHC 开发人员可以愉快地编写代码而无需注意。
为了理解下面的内容，需要引入概念"thunk"。 thunk 首先是一些尚未评估的表达式。例如，由于元组是惰性的，所以像
这样的表达式
(b, b+a)
被编译为元组构造函数 (,) 到 b 和 {a+b} 的应用程序，其中符号 { e } 出于本次讨论的目的意味着一些依赖于实现的表示承诺在计算时计算表达式 e 的 thunk。此外，一个 thunk memoizes 它在评估时的结果，所以无论何时再次评估同一个 thunk，它只是 returns 预先计算的结果。 （当然，这只有在纯函数式语言中才有可能。）
例如，在 Frege 中，为了表示 thunk，有一个 class Delayed<X> 实现了 Callable<X> 并安排了结果的记忆。
我们现在来调查
的结果是什么
next_fib (next_fib (0, 1))
是。内部应用程序导致：
(1, {0+1})
然后外层计算：
({0+1}, {1+{0+1}})
我们在这里看到 thunk 可以嵌套在其他 thunk 中，这就是这里的问题，因为 next_fib 的每个应用程序都会产生一个元组，该元组的元素 thunk 具有先前的迭代嵌套在其中。
现在考虑当第 4000 个 fib-number 的 thunk 被求值时发生了什么，例如，当您打印它时。它必须执行加法，但要加的数字实际上都是 thunk，必须在加法发生之前对其进行评估。这样，每个嵌套的 thunk 都意味着调用该 thunk 评估方法，除非 thunk 已经被评估。因此，要打印第 4000 个数字，我们需要至少 4000 的堆栈深度，以防 之前没有评估该系列的其他 thunk。
所以第一个措施是用严格的元组构造函数替换惰性元组构造函数：
(b; a+b)
它不构建 thunk，而是立即计算参数。这在 Haskell 中不可用，要在那里做同样的事情，您需要这样说：
let c = a+b in b `seq` c `seq` (b,c)
但这并不是故事的结局。原来计算fib 4000还是溢出了栈。
原因是 iterate 的实现是这样的：
iterate f x = x : iterate f (f x)
这将构建一个无限列表
[ x, f x, f (f x), f (f (f x)), ...]
不用说了，除了第一个，其他词都是thunk！
当列表元素按顺序求值时，这通常不是问题，因为，例如，当第 3 项时
{f {f x}}
得到评估，内部 thunk 是 已经评估并且 returns 立即得到结果。一般来说，我们只需要足够的堆栈深度来达到第一个先前评估的术语。这是直接来自 try.frege-lang.org
的 frege 在线 REPL 的演示
frege> next (a,b) = (b; a+b) :: (Integer, Integer)
function next :: (Integer,Integer) -> (Integer,Integer)
frege> fibs = map fst $ iterate next (0,1)
function fibs :: [Integer]
frege> fib = (fibs!!)
function fib :: Int -> Integer
frege> map (length . show . fib) [0,500 ..]
[1,105,209,314,418,523,627,732,836,941,1045,1150,...]
frege> fib 4000
39909473435004422792081248094960912600792...
在这里，使用地图，我们强制对每 500 个数字进行评估（就 REPL 要求输出而言，它只会打印无限列表的初始部分），并计算每个数字的十进制表示的长度（只是为了不显示大的结果数字）。这反过来会强制评估前面的 500 个数字，但这没关系，因为有足够的堆栈 space。一旦完成，我们甚至可以计算 fib 4000！因为现在，所有 thunk 到 6000 都已经被评估了。
但是我们可以使用稍微更好的迭代版本做得更好，它使用 head strict 构造函数 (!:):
a !: as = a `seq` (a:as)
这会立即评估列表的头部，这在我们的例子中是合适的。
通过这两个变化，我们得到了一个程序，它的堆栈需求不再依赖于 fib 的参数。证明如下：
frege> iterate' f x = x !: iterate' f (f x)
function iterate' :: (a->a) -> a -> [a]
frege> fibs2 = map fst $ iterate' next (0,1)
function fibs2 :: [Integer]
frege> (length . show . (fibs2 !!)) 4000
836
frege> (length . show . (fibs2 !!)) 8000
1672
frege> (length . show . (fibs2 !!)) 16000
3344
frege> (length . show . (fibs2 !!)) 32000
6688
frege> (length . show . (fibs2 !!)) 64000
13375
frege> (length . show . (fibs2 !!)) 128000
java.lang.OutOfMemoryError: Java heap space
好吧，我们现在需要更多 堆 space 来保存超过 100.000 个巨大的数字。但请注意，在最后一步计算 32.000 个新数字时不再有堆栈问题。
我们可以通过不需要标记所有这些数字的简单尾递归定义来摆脱堆 space 问题：
fib :: Int -> Integer
fib n = go n 0 1 where
go :: Int -> Integer -> Integer -> Integer
go 0 !a !b = a
go n !a !b = go (n-1) b (a+b)
我想这会比遍历列表更快。
与 Clojure 中的 (?) 不同，直接列表访问是 O(n)，长列表会消耗大量 space。因此，如果需要缓存的东西和有一个上限，你最好使用数组。以下是构造 10000 个 fib 数组的 2 种方法：
frege> zzz = arrayFromList $ take 10000 $ map fst $ iterate (\(a,b) -> (b; a+b)) (0n,1)
function zzz :: JArray Integer
frege> elemAt zzz 4000
39909473435004422792081248094960912600792570982820257 ...
这是有效的，因为中间列表不应该作为一个整体存在。一旦创建，访问是 O(1)
而且还有一个特殊的函数可以像这样创建缓存：
yyy = arrayCache f 10000 where
f 0 a = 0n
f 1 a = 1n
f n a = elemAt a (n-1) + elemAt a (n-2)
fib = elemAt yyy
这甚至避免了中间列表、所有元组等。
这样，您可以保持优先使用组合器而不是显式递归的好习惯。请试一试。
所以我刚开始学习 Frege 和 Haskell。我有使用函数式语言的经验，因为我现在已经使用 Clojure 几年了。 我想尝试的第一件事是我在斐波那契数列上的惯用方法。
next_fib (a, b) = (b, a + b)
fibs = map fst $ iterate next_fib (0, 1)
fib x = head $ drop x fibs
这就是弗雷格的结果。它有效，但对于 fib 的数字非常高，例如(fib 4000)，它会抛出 Whosebug 错误。这让我感到惊讶，因为 Clojure 中的相同功能可以正常工作。这是 Frege 错误还是我把整个惰性评估都弄错了？
你可能不会"get the whole lazy evaluation thing wrong"，但在这种情况下你被太懒惰的评估咬了两次。
虽然GHC在这方面本质上与弗雷格完全一样，但结果却不同，似乎对弗雷格不利。
但是 Haskell 可以通过非常大的 thunk 获得 awya [见下文]，而 Frege 早期中止堆栈溢出的原因是运行时系统管理堆和堆栈的方式。 Haskell RTS 非常灵活，可以在需要时将大部分可用内存分配给堆栈。而 Frege 的运行时系统是 JVM，它通常以一个很小的堆栈开始，刚好足以容纳几百个调用深度。正如您所观察到的，为 JVM 提供足够的堆栈 space 可以使思考工作，就像在 GHC 中一样。
由于 JVM 中的堆栈 space 一直很稀缺，我们在 Frege 中开发了一些技术来避免不必要的和不必要的懒惰。下面将解释其中的两个。最后，在 Frege 中，您被迫及早控制懒惰的不良影响，而 GHC 开发人员可以愉快地编写代码而无需注意。
为了理解下面的内容，需要引入概念"thunk"。 thunk 首先是一些尚未评估的表达式。例如，由于元组是惰性的，所以像
这样的表达式(b, b+a)
被编译为元组构造函数 (,) 到 b 和 {a+b} 的应用程序，其中符号 { e } 出于本次讨论的目的意味着一些依赖于实现的表示承诺在计算时计算表达式 e 的 thunk。此外，一个 thunk memoizes 它在评估时的结果，所以无论何时再次评估同一个 thunk，它只是 returns 预先计算的结果。 （当然，这只有在纯函数式语言中才有可能。）
例如，在 Frege 中，为了表示 thunk，有一个 class Delayed<X> 实现了 Callable<X> 并安排了结果的记忆。
我们现在来调查
的结果是什么next_fib (next_fib (0, 1))
是。内部应用程序导致：
(1, {0+1})
然后外层计算：
({0+1}, {1+{0+1}})
我们在这里看到 thunk 可以嵌套在其他 thunk 中，这就是这里的问题，因为 next_fib 的每个应用程序都会产生一个元组，该元组的元素 thunk 具有先前的迭代嵌套在其中。
现在考虑当第 4000 个 fib-number 的 thunk 被求值时发生了什么，例如，当您打印它时。它必须执行加法，但要加的数字实际上都是 thunk，必须在加法发生之前对其进行评估。这样，每个嵌套的 thunk 都意味着调用该 thunk 评估方法，除非 thunk 已经被评估。因此，要打印第 4000 个数字，我们需要至少 4000 的堆栈深度，以防 之前没有评估该系列的其他 thunk。
所以第一个措施是用严格的元组构造函数替换惰性元组构造函数：
(b; a+b)
它不构建 thunk，而是立即计算参数。这在 Haskell 中不可用，要在那里做同样的事情，您需要这样说：
let c = a+b in b `seq` c `seq` (b,c)
但这并不是故事的结局。原来计算fib 4000还是溢出了栈。
原因是 iterate 的实现是这样的：
iterate f x = x : iterate f (f x)
这将构建一个无限列表
[ x, f x, f (f x), f (f (f x)), ...]
不用说了，除了第一个，其他词都是thunk！
当列表元素按顺序求值时，这通常不是问题，因为，例如，当第 3 项时
{f {f x}}
得到评估，内部 thunk 是 已经评估并且 returns 立即得到结果。一般来说，我们只需要足够的堆栈深度来达到第一个先前评估的术语。这是直接来自 try.frege-lang.org
的 frege 在线 REPL 的演示frege> next (a,b) = (b; a+b) :: (Integer, Integer)
function next :: (Integer,Integer) -> (Integer,Integer)
frege> fibs = map fst $ iterate next (0,1)
function fibs :: [Integer]
frege> fib = (fibs!!)
function fib :: Int -> Integer
frege> map (length . show . fib) [0,500 ..]
[1,105,209,314,418,523,627,732,836,941,1045,1150,...]
frege> fib 4000
39909473435004422792081248094960912600792...
在这里，使用地图，我们强制对每 500 个数字进行评估（就 REPL 要求输出而言，它只会打印无限列表的初始部分），并计算每个数字的十进制表示的长度（只是为了不显示大的结果数字）。这反过来会强制评估前面的 500 个数字，但这没关系，因为有足够的堆栈 space。一旦完成，我们甚至可以计算 fib 4000！因为现在，所有 thunk 到 6000 都已经被评估了。
但是我们可以使用稍微更好的迭代版本做得更好，它使用 head strict 构造函数 (!:):
a !: as = a `seq` (a:as)
这会立即评估列表的头部，这在我们的例子中是合适的。
通过这两个变化，我们得到了一个程序，它的堆栈需求不再依赖于 fib 的参数。证明如下：
frege> iterate' f x = x !: iterate' f (f x)
function iterate' :: (a->a) -> a -> [a]
frege> fibs2 = map fst $ iterate' next (0,1)
function fibs2 :: [Integer]
frege> (length . show . (fibs2 !!)) 4000
836
frege> (length . show . (fibs2 !!)) 8000
1672
frege> (length . show . (fibs2 !!)) 16000
3344
frege> (length . show . (fibs2 !!)) 32000
6688
frege> (length . show . (fibs2 !!)) 64000
13375
frege> (length . show . (fibs2 !!)) 128000
java.lang.OutOfMemoryError: Java heap space
好吧，我们现在需要更多 堆 space 来保存超过 100.000 个巨大的数字。但请注意，在最后一步计算 32.000 个新数字时不再有堆栈问题。
我们可以通过不需要标记所有这些数字的简单尾递归定义来摆脱堆 space 问题：
fib :: Int -> Integer
fib n = go n 0 1 where
go :: Int -> Integer -> Integer -> Integer
go 0 !a !b = a
go n !a !b = go (n-1) b (a+b)
我想这会比遍历列表更快。
与 Clojure 中的 (?) 不同，直接列表访问是 O(n)，长列表会消耗大量 space。因此，如果需要缓存的东西和有一个上限，你最好使用数组。以下是构造 10000 个 fib 数组的 2 种方法：
frege> zzz = arrayFromList $ take 10000 $ map fst $ iterate (\(a,b) -> (b; a+b)) (0n,1)
function zzz :: JArray Integer
frege> elemAt zzz 4000
39909473435004422792081248094960912600792570982820257 ...
这是有效的，因为中间列表不应该作为一个整体存在。一旦创建，访问是 O(1)
而且还有一个特殊的函数可以像这样创建缓存：
yyy = arrayCache f 10000 where
f 0 a = 0n
f 1 a = 1n
f n a = elemAt a (n-1) + elemAt a (n-2)
fib = elemAt yyy
这甚至避免了中间列表、所有元组等。
这样，您可以保持优先使用组合器而不是显式递归的好习惯。请试一试。