Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!dali.cs.montana.edu!caen!sdd.hp.com!spool.mu.edu!munnari.oz.au!bruce!goanna!ok From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) Newsgroups: comp.lang.scheme Subject: Re: ML-like type-checker for Scheme subset? Message-ID: <5817@goanna.cs.rmit.oz.au> Date: 18 May 91 09:49:19 GMT References: <5710@goanna.cs.rmit.oz.au> <1065@sys.uea.ac.uk> Organization: Comp Sci, RMIT, Melbourne, Australia Lines: 76 In article , ted@nmsu.edu (Ted Dunning) writes: > the terribly sad thing is that there are really two camps, one that > assumes that doing arithmetic modulo 2^32 is natural, and one that > assumes it is a *SIN*. > > the result is that when programming in c, i miss bignums in a terrible > way, but when programming in prolog or lisp and trying to `simulate' > real hardware, i take a _big_ hit in performance because i have to do > a silly and redundant mod operation. > > why can't both sides realize that both options are important. But the Lisp side *does* realise that both options are important. Any number of Lisp systems provide something like, oh, (%fixnum-+ e1 ... en) (%fixnum-* e1 ... en) (%fixnum-< e1 ... en) and so on. Do, however, remember that there is nothing particularly natural or "real" about 32-bit integers. Due to my particular history, I have come to think of 40-bit (B6700, sign and magnitude, integers look like floats with exponent 0, hence the missing 8 bits), 24-bit (B1700), 16-bit (CAI Alpha-LSI-2), and 36-bit (DEC-10) integers are "natural" and "real". This is _hardware_ I'm talking about. (Actually, the B6700 could support 79-bit integers, but one normally didn't bother.) In a few years I expect to learn to think of 64 bits as the "obvious" size for hardware "integers". I've also had to live with programming languages which implemented 14-bit, 28-bit, 29-bit, and 30-bit integers, as well as one rather nice system where SMALLPs were 17 bits (love that Xerox 1109). There is precisely *one* "major" current language which comes even close to realising that both options are important (correct implementation of integer arithmetic + access to the restricted hardware), and that is C. "unsigned" arithmetic in C is defined to be 2s-complement, and must _not_ signal overflow. "signed" arithmetic in C is defined as integer arithmetic; the fact that it _may_ signal overflow comes as an unpleasant surprise to many C programmers. Note that in many Lisp implementations, full machine-word-length fixnums are nearly as expensive to manage as bignums, because they'd really like to "borrow" a few bits for a tag. I don't think anybody in the "please give us correct answers" camp would call it "a *SIN*" to do arithmetic modulo 2^32. The sin is to make the false, deceptive, lying, and risky claim that doing so is INTEGER arithmetic. Have all the modular arithmetic you want, just don't mistake it for *integer* arithmetic. A further point about the naturalness of modular arithmetic: on the B6700 where I learned to program, integer arithmetic was NOT modular. If the hardware couldn't represent the right answer, you got an "integer overflow" interrupt. There weren't _any_ instructions for modular arithmetic. And do you know what? Nobody solving their physics problems, or their chemistry problems, or their OR problems, or their mathematics problems, or their accounting problems, ..., ever missed modular arithmetic. Indeed, people who moved their programs to the B6700 from an IBM/360 often discovered that the results they had been getting in the past were wildly wrong. The rising number of requests for C routines to do 64-bit or 128-bit integer arithmetic on comp.lang.c suggests that many C programmers aren't finding "modulo 2^32" all that natural either. Something worth noting: the "mod" operator is NOT silly (it is after all what you _want_) nor is it redundant (the Lisp system in which you are asking for "mod 2^32" may prefer to work in units of 30 bits) nor need it be a cause of inefficiency. This is what the C crowd call "a quality-of- implementation issue"; in the presence of suitable declarations (which are not _standard_ in Scheme, but are available in several Scheme implementations; CL has an entirely adequate declaration system) a compiler could notice that the operation you want can be done directly by the hardware. No doubt someone will write in to tell us of a Scheme or CL compiler (Python?) which does this already. -- There is no such thing as a balanced ecology; ecosystems are chaotic.