On Sep 28, 2009, at 10:10 PM, Ray Dillinger wrote:
> On Mon, 2009-09-28 at 23:16 +0100, David Rush wrote:
>> 2009/9/28 Alaric Snell-Pym <[email protected]>:
>>> On 28 Sep 2009, at 5:31 pm, John Cowan wrote:
>
>>>> and it should not be a requirement that Scheme implementations
>>>> signal
>>>> an error on fixnum overflow -- returning an inexact result should
>>>> still be fine.
>>
>> That gives me the screaming heebie-jeebies. It really does.
>
> I think we have to look at dire failure conditions. And really, we
> have to make a choice between some horrible ones here.
>
> With bignums limited by the size of machine memory, the dire failure
> condition (particularly easy to hit with rationals) is that the
> execution of your program consumes all memory and aborts or crashes.
> The pernicious part is that the system may not even have room to
> open a debugger to handle the abort.
You might as well argue against `cons' and `vector' on the same grounds.
I am willing to accept a reasonable upper bound on the range of exact
integers, and I think this bound can be much smaller than memory
allows. 32-bit Gambit in particular only allows bignums up to 2^2^26
or ~8MB with optimal representation, even though the heap is much,
much larger than that. For what it's worth, arithmetic on integers of
about this size is still reasonably fast:
(time (exact? (* (expt 2 (expt 2 25)) (expt 2 (expt 2 25)))))
68 ms real time
67 ms cpu time (42 user, 25 system)
8 collections accounting for 9 ms real time (4 user, 5 system)
25171520 bytes allocated
5412 minor faults
no major faults
#t
Of course, trying to print one of these integers takes a lot longer :-)
Gambit has a very good performing bignum implementation, but even
implementations with much more naive implementations of bignums can
work with numbers up to 2^2^15 or so (or 32K in optimal
representation) without any issues:
; Scheme48 1.8
> ,time (exact? (* (expt 2 (expt 2 15)) (expt 2 (expt 2 15))))
Run time: 0.02 seconds; Elapsed time: 0.01 seconds
#t
$ time ./chibi-scheme -e '(display (exact? (* (expt 2 (expt 2 15))
(expt 2 (expt 2 15)))))'
#t
real 0m0.169s
user 0m0.156s
sys 0m0.009s
This is a reasonable limit, but these numbers are still
222436505926331847258111945770970380214828829364942677145335567091654522
759593010438006880456033681270459982297949792860094814159990096754534406
194277090465978856878228192738063556357302245173100061971139235871338675
134429823057587257958101268120129033984534313023050306378314945494283091
954435006195774227318443112516271310220769532137831585110490203137673308
062822809870901924778044527356016826601504496175181620806920906119992273
799966898207576306182872834256433861795242759749580557102949793303744539
141832349627835543126873170022548297822931916663291591681325132873375455
329960497411419400287085378635483383928230158158477570017841493080208261
064458322780718281825384377306884596997659950930363001487507184527965099
364454085606583237686740336094390898543125430300255182850667688815490880
446617561717949354815844540702559534179326029026824635642195304491996261
414933357846379638383056821161871656807211769212752735471482230091813890
020301382759617369050523623819837009143383475144365045406862297135940508
055380400371743421299482137398329168968525192081298072222477479041326130
881957507015463667241344543009059598213833257971751888539020886651421570
425974881341127151005829372060462177407023082634615278988511726661470689
562096065511747067454261720660922968811135839136601837597770302700176667
416475042049459118509784135129397054608379020807461679086779336732347360
075618521496042368107130616345792027983797434189053806401943578184906055
141126919544711723041463895126190334688589652205181781427588455708189614
462632034606250952556126037056688081319713924370576192949468506948398288
959657103116636731700059415484016899447351115067183159231588070072291745
022985156672232707070451384534617018449915966479189491461654686290167877
641453292390921993372778069187710145800250856008249619924889124819164186
607287678559078435949053545524043212858729250561740744199559768491298978
811652781426110026483388384199852836420549577281207276337976275427184199
972006239890678936775820047471952965644260305945941059509090082003126295
228509290736135166513864068956441604189193741502288234592219564507920119
145826478670041693467757289978073422905715879378457663570388744740529311
727241213809891911873003659994130864205514380254151511316978345169391079
774979504478243857735224311398206119601565178058878298721175857114554251
056929724412894587271025016237650862480242794746626295071015516364909594
899786172832236845152553087712212383406243601310846849778044865949587440
650572719173586161581782864863659019514125634715929420995955048773847444
384607004015221164803958819849834934743151744274624434943950129690593547
355986038512412989137079969057180429357484781306576264345831513002952055
804643908532273328382660728602940733592650016975473357804245241815329046
193058805758970247064428613298919800338904005294314904548141180612142285
195831735582660430168970828097311851168675420643186211930537608266887793
876634575460869407261070792655853912660305774770457682846342887663913483
940802545202939037019995542082981529838156352425838719134714014447581876
646525952000289403894838359061603684513963399545649054340385064896761370
089593178374700512399464929072716467693190584550114234576018190596666313
391664801174907972757942285987774786496784115504360835177520473468580241
551525644549763488295794031878845474041074545390088648108897366872910577
784603415152291836315999195320017157706377235400173942259912041921744771
490765201648317163659717376093146491915474444009482439566460777449018828
700531066338740455544354733598765011075077727282607878396612738188399652
653944440216029213205516676074694296754738369211650781719643731202156084
625407848487359495862538929010348665290916850021676514077277975381623969
639517304905394366911783229348724499927745928893794443852827774790646816
471170447338745325470341948273025025001674867535685361079551910412369551
018516549759222588192303156505728452993416287467182086880453429141076378
017207808146804950623940027106681667617912902967745910207911282907245150
236267585849616395495449363769680348136164352958081290497895286762772410
951425369929937739072085717845147431834636661001715959507099808802086432
528713631468918292477179084237836148442948501845132185189394239402224780
872043183659226911315113966977533299344106111920179594149561465123301245
285979568514343744045472224022179062308628185553765368125255022430096165
499749857463577619774160712070634363727439114348262657711622861260348889
519115311009787011504356247728180619849419498128577856012013996124498508
085259920038059492454830943756456902534613397278019809201750501625946971
042498419001953627361309822443887404463909153379178945847990709702604967
011701210117015224209111659660362125772864165978252415384023458268275595
973428552826430741681678440507885624495484082555966185967612564492499855
690131353582518249872885318228147853582656127473093528246871368304913429
539242591222262767628196294522803972183869060905969028320713636144498444
668309555569360045712425603899274749709820487961409213954576083390172825
537007056690652770799768496763846284294863836287520041578483634572708812
709906612803084195660600874547744391278362597998544519508110337304257667
421682101726830447776997212991183730576016051435871660056590791188831584
292253261806880132924592446240785841648769266246767281758318826659295658
966479507036664956907446309557917773849531419378040859352275657192414102
496670572104729836496538675689014019202054425914331259878887827927042516
442138026149591062259067240805898442706335256067698194330457480085840397
305591173015971520711052972845016190275378103340043102892650129792047080
512973418609967917312703851226101630500157396725940609287842333226998969
174948188102741216395398782688766162145549227846715027109215161512253036
822951096516946967052985390285773579439933798396317390463343286761895656
757389934619216418677134654291471415428718699357682273588846560738721129
211094946186578881197370388480219206076493594003538478898102930225781641
808078900555895712463833187635769072381008894033367972466313629126850241
861792218922767265039520953382413811321589998966897478392234476206414531
832460479514197085430988422364404270061437797943173316392159836651707944
693339256502506727385368563820155297924666249261029110093322431409856479
841853128035871272266567994094575392595077828897894546101759144247575421
535028997822690133225596008610059982294108644969820764059019573037326077
210598729943221217812930923959920457749548518111244182154179904273413380
122557289985275402830226916227621584077590528892403532552558806178445744
231048344907886556600545649882306370114271610040170416874355350936890372
999989049568948291282303447654974840368065891494154985877585875213959326
859456313102226461193224958969250324118183125024990020807449058690939076
141753295756986259797948335965762727531390346133045176625338481752155540
594709672591256682898223075627839098602767408071372688871326601374367969
075756263253811630586251812127764285181342624844483397001411181459966251
905011145051613397649137381800481060255201103352459504380717914753975227
604557940384050848609606718143975764448027680641360380241102224553552688
565701673056250659975905821192145114478463462878326746191965776121445814
964926731028020496026946048012502044437140353515333377757303485359795343
494914526651023487532158532129148947463991926100476130739633441173488684
851804637684081561855925137994700820281705754339201509019810610058322675
295426284761249106707307952421010316384061607590448280282902176218817425
295206555948680860683693743409624451990905610070238044544042042774368127
709610053605382242226891472261306182323699902279393695088855744404022395
730143389451969530897346832283671130182834623412204983796387297718657580
866030927363688947537817003243715764593326840382234427508500108981729813
001287252219130319115902118906393326546458192228474899624394443584676136
104895598645963291973086416705686333494409140370599271667226298280361026
377599012667761574107203801086564145263430217112478790603670752583121804
729631488446856524954557975914254465115770082799692196164281730524368005
774365551324787727421346352370447938886841543969491351629595719699518190
195777277561533144443483062413534441679525460739668320130028165942141414
268457373004985209175519716448660746063330702223368716030947618214581883
442184464485559509940990329410449355949494868852545585317765170448300552
203789696770836052400703468701386409492080670077985124405014113818510632
590414171725642769742542823404047548876954664799822123169324876884385577
266321152814262190317198492263925571307255165198941062256714779191706572
151188633761095540735762993641057330868447057042529565392432311934375393
752410898873864744657231017928827572366059303592653604139638797204352020
584026585540083691363205325584988600781348577897824581464070685490027391
040126564939337954161259037868520897990120863202085035995921989907105167
117679261112815675534554688392091387758379595891972624181567846656303325
882593358438624511593176072932934551763242919242506091911199027125229967
087523383374736941345307795673647315024873344702608093267280606261329946
623769103039773997013212342519835437170971592396596157136238490206753183
651596591967600961175006323328282128635188691988058720312291853710509951
654950834923991228556463201702911198834625326565045467947666063764469043
101356808330517297926667444982603109552338223589277639834634959769896398
088037283410252304840021249796874628276619710018797780258584027390213652
240373745559266972150887748223016649714496636377333599420763187208826729
854794993362978532664575875211018433901432187648878465541678405133994461
156089641985906793538988475687115660886341989148008645820433369376121141
920848888694222628840312296224465746153102547054165876431078272662220867
043860813227451856317488864771652057156621323671380134207329301605713629
476188855629142017518687586843826395628592508541871702484485669851116823
656068022726189844072151062612206004585345834435252670092070460153973677
655656387876972107254509040078923001519459006834814975083989315225128623
637655140277087329565884697631551094379118965594049339703844010889063415
423747062153837131194580623418560628074811274074865261909967718308883189
819390482943109603467792435470293958734071803985347193960382603459485686
418375337491289426550135815094942736753196559040450224217515840596922093
061493370155255607212014410521733884291374727712332722036394078525238257
502200709304924879154342784840784661818763548450302411821837421085909064
147482125476406386329102125305391882815860143735469207558085192632658708
672179735596656778570900482615427526486500099032175833211141502513014105
941666677624809560714004335131107593169556996232596078664645562537898786
571487475782126555154341038378850719325545870869777381175872325400472968
920698793037224766236606199166589875956444796909357121011054598590895291
534246420693931320584945842975694017421199309273965388965234720313262342
577112935639639458927068476000974423243789459967347789251923097419081086
977701671171256739648226153947183791451571823163402380249959183895855128
667834884558248456938812824241547127387987854123765516072084832940821875
155569300173768788753337742200898458337292919240777732907530279661843289
851253589196843568725341069908704289701960271355857319704022439359620936
865273031980209992476604046032195565165875490554704183587377389044525626
609494990029172535722661380129389143176797731029970915474222977671972003
936140749255016851618407467336616271306002646075907846986278195272487781
911015369113851207039793227982259544559707906168564556288018266420142570
275248063302117872441804275222969010212415459463229156363920650415661197
701300880688439583056501272292357100945119538404839781632768577827188214
243413362686638234301677271568127618515080013444968985783663640465016715
095261057174918084070183981607471470249971622802547841276142069951854483
233941450544415458987144778746228073072522623135364070065909816442093595
773409530457130689940272240155237486883541349163711113344052787784179061
760475654793983471019520024098670301335442036266192508015283953368046964
746376379790802990640475232584925507569109010098517650783199121704270705
518642457004934987964281256625811710512615503977486607023031889263716276
609862099483764770182830238497853561898807823542085917210719142944066149
916315489976885528792165851702697865630910118892963517540443670574974402
077973129955719088837742563854979401792536722512002500451342930882917407
904126603737396569530155169888455008077805993860062706866303531208355159
137093883178997162575942409820422641409367665533900658390917294601400193
303736878201765234082880694512447118362749596772017259537162401347729026
463368473557743691208219415930624086076607760748575763208968399234932953
917748139052730549116223209156285854112469826539373379748117988528225633
855602853687055999634963575788787584287736635953660410598791469195741897
946555406011477891561086299612259681023854462658359165915319420914472132
960879427127769644246420192176620535857042991977564117021977320495256400
483268028415711955356030576465143763753190301734381370394170802667207272
222785840661189844907652682721864122371002562067238011354144604439394995
938672870046721520781925647284592641868332607830316632272576816724703673
866141897679149592446004999746775338058076006907619353057227415478431890
015819303006753699067768214275383692131821708891697704467989459510103211
989448404635598203026395338352861025610585788927206305887029243645540832
273056573388843012761291692239928629904742945046297416372098567294802399
242081494149940869850644383235116570281285538425209570940492557732095509
928310747104347201692682081875719985852840902159175194465401485340269797
120348515795725240985006653838395105942327473587467226089501005533675942
824794035614287328229243281302124222910294107825004631299653328917321256
475841811839264529368006069785756012549196030378017312508161056723282088
813576488318736915981783888306307720884119913438825730466606860137266882
505754575336497024036314499497264716171329273988025386679886975608089990
575176633012525884593808014585537667435027311092218344603571135786815990
192885972063073849340769931895208379695473420096400694496004193843188886
744021515474756030893551110780040090179655639394406136419811019522831935
816789130961713744873966739547862503860655459558909944012944118949520127
830061816913368818365527770454850295244339172824692563462524419455701945
952222305948725960286800864105040213130688834231609868951524272864709188
028226532967270608014077299987052413007479200328041999096030325670487902
181614060687394973773216841554474842556490524093332718861241469552443120
082436425826811064061753696962065800379575819504401625636944540837378870
923728330252653183864895721411105635887605825132006986339848332368811381
900210951152704067783701388325686813018286931483135512290420416795058721
716385324079296189544696988383243342734956892487786786784578431833687124
711299011571411468937556221688469282715365918537734558361887564272201868
884232984751013583111426750468095903330621669035837826283944676085370712
491350772026928993074111761498373122476825918427501448202822675151017386
732114172777457056307510736557818184225742215745222831703769054345047533
047055135156463794479526234912991682558917077677120122398083599974371732
639372352450066109337834237120466286902280499775353985317769052334011662
086177467513469694304785312741825770685523190658648802793613052353930835
421963164792285096739252360890743622123612351663219843509785960283282234
414376535244316386110807062629579924164970301939979897284229195670063290
213673289702797855660981257043324021154762672133759636466376692758998605
083513614452763059432463791119710552242270161422128066575841793654269818
058413610342798921360672207264503650677433947449086163254882176592544220
637480368074289309262900258025736883473828966900769794645901522200520684
944086142488260463155449268436805011385746963743949086853415051809076718
557805611920389392252225696570912311892022635506270644021418763418963533
641577652208901070526904521257299976666802676679505915584799757575891124
576409470188970539511621163239189907574856843121296466888335822000058503
719757706139247304245723768784914440453004689588312962316597243123865209
784471958494744068447301425604045628207177009425721709960472781787141234
411332452238365869865589730199419890852992871072113604659850326254736283
477542535540731611121985772721357689729135901316918564724265783257263079
536359391072253051695317243696092334391901552565694749745862944190817569
228294138444797726024165890420600601101778505939512826920801044838711701
523355943076620251933990080845428942308489596765746353237466319263152361
821137726953549471702402579990500482727092152805596603933818849868879583
702348391234416358755894270815162354231200158807316227594621117492614480
184915979039914386942225112602776185922840424092852049058506774948365212
942145913072603807177560445203360141178842848608387042163152911313122732
897368156019748052322913932420388269232174912874119763219277843054546746
772387241200893690894795475325981749223000968274092075150702193563902307
087991882422642501827095330365970344066999618002842233744568957659004751
681086905626903927420052064190361741180834382100764010356374544199921617
590351197471572198533900282601141134729297239323297604241334487314711935
542360243109214892332397162179497471527209754598408984515433991478739695
856209200269873657181193380407813915110038095091061858336461226045907388
765719064092211215007529228428226381771468500993548569640672114364008753
884884055509327375426404989611306579037222824675271373413081011426033674
841632228335812931432453123361143115539700356998614672571140652680066994
867665640306132852433302856722082261102494242226427404629467875905489645
808437016215232987478331120635077962592818466849735818013824030126599142
889122329054614873901261693815498988422364462783485229576681130696823604
365940087130991485116163016028097034266381019090607403528150148393838785
681105812205020426776550363378307433464813267615160177837899467413162031
149835400569121576526609059158575912596134825243227076168233395432832775
979217068905483148289164692512479056113146008084029797025019675931481478
823021667600262275776476331507212726981676813641015119241674458034897672
669130032514486966796636192294675283841676831842731035552809415203692004
122850369318710053846704820896949736994199485875321605615651921015770961
439962603747849942121411614699671475661102290192145163940151356761312152
165832268281751198043425091902174809078657065913412989817114717213064673
964243228351951940494992295150588701798892098301975746854721173306630096
789687577933012022821798502574600783978422007866867229170348736247339756
317194229673486867177268855490209110741926353332713128578199019632505220
529366584545000420405880681488707390774365457195115507437597299348084938
094234097025905554846580813388526589745938992529669146939233288602255537
970662731984730308716576526795896146719164026674470688435646695507927634
861715542853370907118931233270889695344276879154687055491679368687789342690784348149209508766629555114808530953747665697085350306019309477827983482829802768775601735842913052287803575454759969815315968948458040250927829329941843799617441536499431871279544308454229723981707925664710983853657702555541999121163124381625975564185301480284072145605494978199317419891560586103936255697932474182595237354583083017522924320912543459982726015117468488508983298641596061022504160155767281897991231450914910096749338777205073009477513565408231823174941891273707303535723728845083966651542228747470008848582388674538271703041052068185896200151125143735199826129699292366964163424341549867186496266350061293905926185127471437131703032427353439283765115201550085899015347654174049154060179871156119948541820259114716890347250171435179654775343941380347312269558371915654761644074218224018208588951594532894224334428099066459909521408
times too large to fit in the exact range of an IEEE double, which
precludes exact -> inexact overflow semantics.
> With fixnums limited by the size of the machine words and no error
> reporting a la Stalin, the dire failure condition is that you are
> getting your answer but have hit an unknown number of modulus
> operations at unknown steps of the intervening computation and thus
> the answer you get may bear no relation to reality, and you have
> no warning of this fact at all. This is the scenario that gives
> me the worst heebie-jeebies.
Yes. If I want modular semantics, I will write modular semantics
explicitly.
> With fixnums limited by the size of the machine word and error
> reporting, the dire failure condition is that ythe execution of
> your program halts -- but at least it does so before consuming
> all memory and without giving you a wrong answer, and you can open
> a debugger without dumping the aborted image out of memory.
>
> With overflow to an inexact number, the first failure condition is
> that you get your answer but it may be off by one part per million
> or so, which is not so dire.
Unless you're depending on (not (eqv? x (- x 1))), in which case your
program loops infinitely.
> But at the same moment, your program has lost the ability to use
> it in further operations requiring exact integers, such as using
> its modulus as a vector index, etc, and this may result in a dire
> failure later -- usually an execution abort when the program
> attempts something it just isn't allowed to do with inexact
> numbers.
>
> None of these options are pretty. I think "consume all memory and
> crash" is the worst of them, so I don't want to wind up using
> bignums (particularly big ratios) accidentally. I definitely
> want the ability to request a signal if I exceed fixnum bounds in
> my integer calculations, especially including the numerators and
> denominators of ratios.
>
> Don't get me wrong; I think bignums are valuable, and should
> definitely
> be available to use with due caution; but I don't want to ever get
> into bignums by accident, because that happens just seconds before
> the worst kind of crash.
I think that's flat wrong. On a 32-bit system, 2^30 is a bignum on
most implementations because at least three tag bits are reserved for
objects. I work with numbers larger than that frequently and have
absolutely no issues with using bignums. As far as I can tell, there
are essentially no negative consequences to fixnum->bignum overflow.
You can work with bignums at least 32738 times larger in
representation size without dire problems on all implementations of
Scheme that I have tested.
Once again, I'm having trouble understanding what all of these really
horrible problems associated with a full numeric tower are. I have not
run into any of them on implementations of Scheme that support a full
tower, nor in any of my years of using Common Lisp commercially. I
have, on the other hand, counted past a 24-bit or 29-bit fixnum
frequently. If you could at least point me to a real life scenario on
where these terrible bignum semantics have caused problems, I'd like
to hear about it.
--
Brian Mastenbrook
[email protected]
http://brian.mastenbrook.net/
_______________________________________________
r6rs-discuss mailing list
[email protected]
http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
