Guile Scheme 解释器中的奇怪乘法行为

Question

我在 OS X 上使用 Guile 1.8.8 解释器练习 Scheme。我注意到了一些有趣的事情。

这是一个 expt 函数，它基本上执行幂运算 expt(b,n) = b^n：

 (define (square x) (* x x))
 (define (even? x) (= (remainder x 2) 0))
 (define (expt b n) 
      (cond ((= n 0) 1)
        ((even? n) (square (expt b (/ n 2))))
        (else (* b (expt b (- n 1))))
      ))

如果我用一些输入尝试它

 > (expt 2 10)
 1024
 > (expt 2 63)
 9223372036854775808

这里来了个奇怪的部分：

 > (expt 2 64)
 0

更奇怪的是，直到n=488时它仍保持为0：

 > (expt 2 487)
 0
 > (expt 2 488)
 79916762888089401123.....
 > (expt 2 1000)
 1071508607186267320948425049060....
 > (expt 2 10000)
 0

当我使用repl.it在线编译器运行这段代码时，它按预期工作。那么Guile到底出了什么问题？

（注意：在某些方言中，remainder函数被称为mod。）

- ahmet alp balkan

---

尝试将您的 expt 重命名为 my-expt。这样可以排除问题是您的 expt 还是内置的 expt 的任何混淆。 - soegaard

如果有用的话，进一步的信息是：我刚在运行FreeBSD的x64机器上尝试了guile 1.8.8，一切都正常。Ahmet Alp Balkan，你的机器是64位的吗？（大多数最新的Mac都是。）如果是这样，也许问题与OS X有关。 - Gareth McCaughan

看起来 guile 的大整数打印代码只是 GMP 的 mpz_get_str 的一个非常薄的包装器，而 mpz_get_str 又是 GMP 的 mpn_get_str 的一个非常薄的包装器，后者对于不同大小的数字执行不同的操作，相当复杂。因此，这将是我第一个猜测任何问题可能存在的地方。 - Gareth McCaughan

在我的64位MacPorts guile 1.8.8上，运行在MacOS 10.6.8上，它能够正常工作。 - gpvos

所以我拿到了一台运行Guile（实际上是版本1.6.8）的Mac，在该系统上（expt 2 488）报告为零...（expt 2 244）也是如此，但（expt 2 122）不是。因此，我猜测Ahmed Alp Balkan的原始报告有误，它并没有从64到487一直给出零。因此，我现在同意这是一个乘法错误而不是数字转换错误。 - Gareth McCaughan

Answer 1

我最近在 Guile 2.0 中修复了这个 bug。这个 bug 的产生是因为 C 编译器开始优化溢出检查，理论上，如果发生有符号整数溢出，则行为未指定，因此编译器可以自由处理。

- Mark H Weaver

---

马克，只是为了澄清一下，你的意思是你已经验证了那个错误是这里问题的原因吗？ - Gareth McCaughan

我们确定(expt 2 244)返回了0吗？有人可以确认一下吗？如果是这样的话，那么我会同意Gareth的看法，即错误很可能在number->string中。对于bignums，Guile使用GNU MP的mpz_get_str，因此如果是bignum显示错误，我很想看到Homebrew上GNU MP版本的“make check”的结果。尝试使用-fwrapv编译GNU MP和Guile也是值得的。 - Mark H Weaver

Here comes the hero! Thanks! - ahmet alp balkan

我在一个非常简单的语句中观察到了这种不良行为，例如 (* 10000 100000000000000000000000)。 - ahmet alp balkan

Ahmet Alp Balkan，你在那时到底看到了什么？而且，在那些（显然）会误报为零的情况下，如果你使用 zero? 进行明确测试会发生什么？如果问题不是在计算数字而是在将数字转换为字符串上，则 zero? 应该返回 false，即使该数字被显示为零。 - Gareth McCaughan

Answer 2

我可以在OS X上使用guile 2.0.6重现该问题。问题的本质是：

> (* 4294967296 4294967296)
$1 = 0

我的猜测是guile使用本地int类型来存储小数字，当本地int太小时，则切换到由GNU MP支持的bignums。也许在这种特殊情况下，检查失败，计算溢出了本地int。

有趣的是，以下循环显示，在2^32和2^60之间平方2的幂结果为0：

(let loop
    ((x 1)
     (exp 0))
  (format #t "(2^~s) ^ 2 = ~s\n" exp (* x x))
  (if (< exp 100)
      (loop (* 2 x) (+ 1 exp))))

导致结果：

(2^0) ^ 2 = 1
(2^1) ^ 2 = 4
(2^2) ^ 2 = 16
(2^3) ^ 2 = 64
(2^4) ^ 2 = 256
(2^5) ^ 2 = 1024
(2^6) ^ 2 = 4096
(2^7) ^ 2 = 16384
(2^8) ^ 2 = 65536
(2^9) ^ 2 = 262144
(2^10) ^ 2 = 1048576
(2^11) ^ 2 = 4194304
(2^12) ^ 2 = 16777216
(2^13) ^ 2 = 67108864
(2^14) ^ 2 = 268435456
(2^15) ^ 2 = 1073741824
(2^16) ^ 2 = 4294967296
(2^17) ^ 2 = 17179869184
(2^18) ^ 2 = 68719476736
(2^19) ^ 2 = 274877906944
(2^20) ^ 2 = 1099511627776
(2^21) ^ 2 = 4398046511104
(2^22) ^ 2 = 17592186044416
(2^23) ^ 2 = 70368744177664
(2^24) ^ 2 = 281474976710656
(2^25) ^ 2 = 1125899906842624
(2^26) ^ 2 = 4503599627370496
(2^27) ^ 2 = 18014398509481984
(2^28) ^ 2 = 72057594037927936
(2^29) ^ 2 = 288230376151711744
(2^30) ^ 2 = 1152921504606846976
(2^31) ^ 2 = 4611686018427387904
(2^32) ^ 2 = 0
(2^33) ^ 2 = 0
(2^34) ^ 2 = 0
(2^35) ^ 2 = 0
(2^36) ^ 2 = 0
(2^37) ^ 2 = 0
(2^38) ^ 2 = 0
(2^39) ^ 2 = 0
(2^40) ^ 2 = 0
(2^41) ^ 2 = 0
(2^42) ^ 2 = 0
(2^43) ^ 2 = 0
(2^44) ^ 2 = 0
(2^45) ^ 2 = 0
(2^46) ^ 2 = 0
(2^47) ^ 2 = 0
(2^48) ^ 2 = 0
(2^49) ^ 2 = 0
(2^50) ^ 2 = 0
(2^51) ^ 2 = 0
(2^52) ^ 2 = 0
(2^53) ^ 2 = 0
(2^54) ^ 2 = 0
(2^55) ^ 2 = 0
(2^56) ^ 2 = 0
(2^57) ^ 2 = 0
(2^58) ^ 2 = 0
(2^59) ^ 2 = 0
(2^60) ^ 2 = 0
(2^61) ^ 2 = 5316911983139663491615228241121378304
(2^62) ^ 2 = 21267647932558653966460912964485513216
(2^63) ^ 2 = 85070591730234615865843651857942052864
(2^64) ^ 2 = 340282366920938463463374607431768211456
(2^65) ^ 2 = 1361129467683753853853498429727072845824
(2^66) ^ 2 = 5444517870735015415413993718908291383296
(2^67) ^ 2 = 21778071482940061661655974875633165533184
(2^68) ^ 2 = 87112285931760246646623899502532662132736
(2^69) ^ 2 = 348449143727040986586495598010130648530944
(2^70) ^ 2 = 1393796574908163946345982392040522594123776
(2^71) ^ 2 = 5575186299632655785383929568162090376495104
(2^72) ^ 2 = 22300745198530623141535718272648361505980416
(2^73) ^ 2 = 89202980794122492566142873090593446023921664
(2^74) ^ 2 = 356811923176489970264571492362373784095686656
(2^75) ^ 2 = 1427247692705959881058285969449495136382746624
(2^76) ^ 2 = 5708990770823839524233143877797980545530986496
(2^77) ^ 2 = 22835963083295358096932575511191922182123945984
(2^78) ^ 2 = 91343852333181432387730302044767688728495783936
(2^79) ^ 2 = 365375409332725729550921208179070754913983135744
(2^80) ^ 2 = 1461501637330902918203684832716283019655932542976
(2^81) ^ 2 = 5846006549323611672814739330865132078623730171904
(2^82) ^ 2 = 23384026197294446691258957323460528314494920687616
(2^83) ^ 2 = 93536104789177786765035829293842113257979682750464
(2^84) ^ 2 = 374144419156711147060143317175368453031918731001856
(2^85) ^ 2 = 1496577676626844588240573268701473812127674924007424
(2^86) ^ 2 = 5986310706507378352962293074805895248510699696029696
(2^87) ^ 2 = 23945242826029513411849172299223580994042798784118784
(2^88) ^ 2 = 95780971304118053647396689196894323976171195136475136
(2^89) ^ 2 = 383123885216472214589586756787577295904684780545900544
(2^90) ^ 2 = 1532495540865888858358347027150309183618739122183602176
(2^91) ^ 2 = 6129982163463555433433388108601236734474956488734408704
(2^92) ^ 2 = 24519928653854221733733552434404946937899825954937634816
(2^93) ^ 2 = 98079714615416886934934209737619787751599303819750539264
(2^94) ^ 2 = 392318858461667547739736838950479151006397215279002157056
(2^95) ^ 2 = 1569275433846670190958947355801916604025588861116008628224
(2^96) ^ 2 = 6277101735386680763835789423207666416102355444464034512896
(2^97) ^ 2 = 25108406941546723055343157692830665664409421777856138051584
(2^98) ^ 2 = 100433627766186892221372630771322662657637687111424552206336
(2^99) ^ 2 = 401734511064747568885490523085290650630550748445698208825344
(2^100) ^ 2 = 1606938044258990275541962092341162602522202993782792835301376

- Thomas

---

那么为什么2^488能够正确运行，但在2^(64..487)范围内的任何内容都无法正常工作呢？2^65也不起作用，可能是因为2^64被解释为0，但是在2^488发生了什么变化呢？ - ahmet alp balkan

此外，(* 4294967297 4294967295) 的结果为-1，(* 4294967296 4294967295) 的结果为-4294967296，而(* 4294967297 4294967297) 的结果为8589934593。这是在Homebrew的Guile 1.8.8上得出的结果。 - Lloeki

Answer 3

我无法在Arch上重现您的结果。

这是我的终端会话日志：

$ uname -r
3.6.10-1-ARCH
$ guile --version
Guile 1.8.8
Copyright (c) 1995, 1996, 1997, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation
Guile may be distributed under the terms of the GNU General Public Licence;
certain other uses are permitted as well.  For details, see the file
`COPYING', which is included in the Guile distribution.
There is no warranty, to the extent permitted by law.
$ guile
guile> (define (square x) (* x x))
guile> (define (even? x) (= (remainder x 2) 0))
guile> (define (expt b n)
        (cond ((= n 0) 1)
            ((even? n) (square (expt b (/ n 2))))
            (else (* b (expt b (- n 1))))))
guile> (expt 2 10)
1024
guile> (expt 2 64)
18446744073709551616
guile> (expt 2 487)
399583814440447005616844445413525287135820562261116307309972090832047582568929999375399181192126972308457847183540047730617340886948900519205142528
guile> (expt 2 488)
799167628880894011233688890827050574271641124522232614619944181664095165137859998750798362384253944616915694367080095461234681773897801038410285056
guile> (expt 2 1000)
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
guile> (expt 2 10000)
19950631168807583848837421626835850838234968318861924548520089498529438830221946631919961684036194597899331129423209124271556491349413781117593785932096323957855730046793794526765246551266059895520550086918193311542508608460618104685509074866089624888090489894838009253941633257850621568309473902556912388065225096643874441046759871626985453222868538161694315775629640762836880760732228535091641476183956381458969463899410840960536267821064621427333394036525565649530603142680234969400335934316651459297773279665775606172582031407994198179607378245683762280037302885487251900834464581454650557929601414833921615734588139257095379769119277800826957735674444123062018757836325502728323789270710373802866393031428133241401624195671690574061419654342324638801248856147305207431992259611796250130992860241708340807605932320161268492288496255841312844061536738951487114256315111089745514203313820202931640957596464756010405845841566072044962867016515061920631004186422275908670900574606417856951911456055068251250406007519842261898059237118054444788072906395242548339221982707404473162376760846613033778706039803413197133493654622700563169937455508241780972810983291314403571877524768509857276937926433221599399876886660808368837838027643282775172273657572744784112294389733810861607423253291974813120197604178281965697475898164531258434135959862784130128185406283476649088690521047580882615823961985770122407044330583075869039319604603404973156583208672105913300903752823415539745394397715257455290510212310947321610753474825740775273986348298498340756937955646638621874569499279016572103701364433135817214311791398222983845847334440270964182851005072927748364550578634501100852987812389473928699540834346158807043959118985815145779177143619698728131459483783202081474982171858011389071228250905826817436220577475921417653715687725614904582904992461028630081535583308130101987675856234343538955409175623400844887526162643568648833519463720377293240094456246923254350400678027273837755376406726898636241037491410966718557050759098100246789880178271925953381282421954028302759408448955014676668389697996886241636313376393903373455801407636741877711055384225739499110186468219696581651485130494222369947714763069155468217682876200362777257723781365331611196811280792669481887201298643660768551639860534602297871557517947385246369446923087894265948217008051120322365496288169035739121368338393591756418733850510970271613915439590991598154654417336311656936031122249937969999226781732358023111862644575299135758175008199839236284615249881088960232244362173771618086357015468484058622329792853875623486556440536962622018963571028812361567512543338303270029097668650568557157505516727518899194129711337690149916181315171544007728650573189557450920330185304847113818315407324053319038462084036421763703911550639789000742853672196280903477974533320468368795868580237952218629120080742819551317948157624448298518461509704888027274721574688131594750409732115080498190455803416826949787141316063210686391511681774304792596709376
guile> (exit)

- cmt