4

So I just started out with Frege and Haskell as well. I have experience with functional languages, since I was using Clojure for a couple of years now. The first thing I wanted to try out is my usual approach at the Fibonacci numbers.

next_fib (a, b) = (b, a + b)
fibs = map fst $ iterate next_fib (0, 1)
fib x = head $ drop x fibs

This is how it turned out in Frege. It works, but for very high numbers for fib, e.g. (fib 4000), it throws StackOverflow errors. This surprised me, because same functions in Clojure would work just fine. Is this a Frege bug or am I getting the whole lazy evaluation thing wrong?

4

1 回答 1

7

您可能不会“把整个懒惰的评估弄错”,但是在这种情况下,您会被懒惰的评估咬了两次。

而且虽然 GHC 在这方面的工作原理与弗雷格基本相同,但结果却不同,而且似乎对弗雷格不利。

但是 Haskell 可以通过非常大的 thunk 获得 awya 的原因 [见下文],而 Frege 由于堆栈溢出而提前中止是运行时系统管理堆和堆栈的方式。Haskell RTS 非常灵活,如果需要,可以将大部分可用内存用于堆栈。而 Frege 的运行时系统是 JVM,它通常以一个很小的堆栈开始,足以容纳几百个调用深度。正如您所观察到的,为 JVM 提供足够的堆栈空间使 think 工作正常,就像在 GHC 中一样。

由于 JVM 中的堆栈空间一直稀缺,我们在 Frege 中开发了一些技术来避免不必要的和不必要的惰性。下面将解释其中的两个。最后,在 Frege 中,您被迫及早控制懒惰的不良影响,而 GHC 开发人员可以愉快地编写代码而无需注意。

为了理解下面的内容,我们需要引入“thunk”这个概念。thunk 首先是一些尚未被评估的表达式。例如,由于元组是惰性的,所以像这样的表达式

(b, b+a)

被编译到元组构造函数的应用程序中,(,)为了讨论b{a+b}符号{ e }表示某个 thunk 的实现依赖表示,该表示承诺e在评估时计算表达式。此外,thunk评估时会记住其结果,因此当再次评估相同的 thunk 时,它只会返回预先计算的结果。(当然,这只有在纯函数式语言中才有可能。)

例如,在 Frege 中,为了表示 thunk,有一个类Delayed<X>实现Callable<X>并安排结果的记忆。

我们现在将调查结果是什么

next_fib (next_fib (0, 1)) 

是。内部应用程序导致:

(1, {0+1})

然后外部计算:

({0+1}, {1+{0+1}})

我们在这里看到 thunk 可以嵌套在其他 thunk 中,这就是这里的问题,因为每个应用程序next_fib都会生成一个元组,该元组将具有嵌套在其中的先前迭代的 thunk 作为其元素的 thunk。

现在考虑当第 4000 个 fib 编号的 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已经被评估并立即返回结果。一般来说,我们只需要足够的堆栈深度就可以达到之前评估的第一个术语。这是直接来自 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 个数字,但这没关系,因为有足够的堆栈空间。一旦完成,我们甚至可以计算fib 4000!因为现在,所有高达 6000 的 thunk 都已被评估。

但是我们可以使用更好的 iterate 版本做得更好,它使用 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

好吧,我们现在需要更多的堆空间来保存超过 100.000 个巨大的数字。但请注意,在最后一步计算 32.000 个新数字不再存在堆栈问题。

我们可以通过一个不需要标记所有这些数字的简单尾递归定义来摆脱堆空间问题:

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),而且长列表会占用大量空间。因此,如果你需要缓存一些东西并且有一个上限,你最好使用数组。以下是构造 10000 个 fib 数组的两种方法:

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

这甚至避免了中间列表、所有元组等等。

这样,您可以保持优先使用组合器而不是显式递归的好习惯。请试一试。

于 2015-08-26T18:45:31.463 回答