迭代会产生StackOverflow错误

Question

所以我刚刚开始使用Frege和Haskell.我有使用函数式语言的经验,因为我现在使用Clojure已有几年了.我想尝试的第一件事就是我在Fibonacci数字上的常用方法.

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

这就是弗雷格的结果.它有效,但对于非常高的数字,例如(fib 4000),它会抛出StackOverflow错误.这让我感到惊讶,因为Clojure中的相同功能可以正常工作.这是一个Frege错误还是我得到了整个懒惰的评估错误？

Answer 1

你可能没有"让整个懒惰的评价错误",但在这种情况下你被懒得评价两次.

虽然GHC在这方面基本上与弗雷格完全相同,但结果却不同,对弗雷格来说似乎是不利的.

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

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

要理解以下内容,我们需要引入"thunk"这个概念.thunk首先是一些尚未被评估的表达式.例如,因为元组是懒惰的,所以表达式就像

(b, b+a)

被编译成元组构造的应用(,),以b及{a+b}其中符号{ e }为讨论起见意味着承诺计算表达一个thunk的一些依赖于实现的表示e评价时.此外,thunk 在评估时会记住其结果,因此当再次评估相同的thunk时,它只返回预先计算的结果.(当然,这只能用纯函数式语言实现.)

例如,在Frege中,为了表示thunk,有一个类Delayed<X>实现Callable<X>并安排对结果进行memoization.

我们现在将调查结果

next_fib (next_fib (0, 1)) 

是.内部应用程序导致:

(1, {0+1})

然后外面的那个计算:

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

我们在这里看到thunks可以嵌套在其他thunk中,这就是问题所在,因为每个应用程序都next_fib将产生一个元组,它将具有嵌套在其中的前一次迭代的thunks作为其元素thunks.

现在考虑当评估第4000个fib-number的thunk时发生的情况,例如,当你打印它时.它必须执行添加,但要添加的数字实际上都是thunks,必须在添加之前进行评估.这样,每个嵌套thunk意味着调用该thunks评估方法,除非已经评估了thunk.因此,要打印第4000个数字,在此之前没有评估过该系列的其他任何一个thunk的情况下,我们需要至少4000的堆栈深度.

所以第一个措施是用严格的一个替换惰性元组构造函数:

(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 是已经评估,并返回结果的时候了.通常,我们只需要足够的堆栈深度来达到先前评估的第一个术语.这是一个直接来自frege在线REPL的试用版try.frege-lang.org

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的thunks.

但是我们可以用更好的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个fibs数组的两种方法:

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

这甚至可以避免中间列表,所有元组等.

通过这种方式,您可以保持优先考虑组合器而不是显式递归的良好习惯.请试一试.