Re: Overflows (lisp fixnum-bignum conversion)

Re: Overflows (lisp fixnum-bignum conversion)

[Clayton Weaver]

(Is this nit-picking? Just a special case for the lisp fixnum to bignum
conversion:)

On Thu, 3 Apr 1997, Robert A Duff wrote:

> Analogy: Suppose you write a signed integer expression that overflows.
> In C, you get unpredictable results (exactly what Ada calls erroneous).
> In Ada, you get a run-time error.  In Lisp, you get the right answer.
> It seems to me that, as far as preventing bugs goes, with respect to
> this particular issue, C is worst, Ada is better (because it detects the
> error), and Lisp is better still (because it prevents the error).
> [Before somebody starts a three-way language war -- please note that I
> said "with respect to this particular issue"!]

Suppose the integer expression that overflows is used to determine the
index size for an array allocation.
 
Std lisp limits array indexes to fixnums. Lisp can transparently cast the
overflowing representation from fixnum to bignum, but it will still error
if it tries to allocate an array ("vector") with an index size beyond the
fixnum bound, unless you have a custom handler for that case that either
changes the array to some other storage type or virtualizes the data
structure into an array of arrays, and sets a flag that whatever function
accesses that array can read to change its lookup method.

Regards, Clayton Weaver  cgweav@eskimo.com  (Seattle)

Re: Overflows (lisp fixnum-bignum conversion)

[Robert Dewar]

Robert Duff said

<<> Analogy: Suppose you write a signed integer expression that overflows.
> In C, you get unpredictable results (exactly what Ada calls erroneous).
> In Ada, you get a run-time error.  In Lisp, you get the right answer.
> It seems to me that, as far as preventing bugs goes, with respect to
> this particular issue, C is worst, Ada is better (because it detects the
> error), and Lisp is better still (because it prevents the error).>>

I find this too facile. The trouble is that better means better according
to some metric. What are you interested in?

More flexibility
More efficiency
More simplicity
...


Sure, it is more convenient for a programmer if all integers have unlimited
length, including array subscripts, but there is a real cost for this (if
I remember, even in LISP standard arrays do not allow bignums as subscripts).
If you are interested in expressive power, and do not care about efficiency,
then Ada is not the apprropriate language level (neither is C++ or Java).
LISP is getting somewhere closer to where you want to be, but in general
you want to take a better look at very high level languages like SETL
(In SETL *all* integers, including those used for subscripts, are unlimited
in size, and indeed general mappings mean that you can do arbitrary things
with the equivalent of arrays like:

    a (1) := 0;
    a (1000000000000000000000000000000000000000000000000) := 0;

and it works fine -- BUT slowly! You pay a price for this kind of
flexibility. I often find that I can write things in SPITBOL (a
dialect of SNOBOL-4) in a fraction of the time that it would take
in a language like C++ or Ada. But I do not expect to use SPITBOL
for writing high efficiency general purpose code.

Someone who is interested in efficiency to the exclusion of any other
consideration may consider C to be the best language with respect to
overflow handling, since neither the language nor the compiler is
burdened by "useless" overflow checks.

In practice language design is a series of compromises, and we choose
different places on the scale depending on our purpose. In Ada we make
a concious decision to give up a small amount of efficiency in the
interests of safety, and Java makes a similar decision.

That's why arguing that one language is better than another is always
a confusing activity, where lack of communication is common!

Re: Overflows (lisp fixnum-bignum conversion)

[Robert A Duff]

In article <Pine.SUN.3.96.970405054237.22894A-100000@eskimo.com>,
Clayton Weaver  <cgweav@eskimo.com> wrote:
>Std lisp limits array indexes to fixnums. Lisp can transparently cast the
>overflowing representation from fixnum to bignum, but it will still error
>if it tries to allocate an array ("vector") with an index size beyond the
>fixnum bound, unless you have a custom handler for that case that either
>changes the array to some other storage type or virtualizes the data
>structure into an array of arrays, and sets a flag that whatever function
>accesses that array can read to change its lookup method.

I won't complain if I can't allocate an array bigger than 2**32 bytes on
a machine that has a 32-bit address space.  That's a lot different from
telling me I can't allocate a 1000-bit integer on such a machine.

- Bob

Re: Overflows (lisp fixnum-bignum conversion)

[Nick Roberts]

Robert A Duff <bobduff@world.std.com> wrote in article 
> I won't complain if I can't allocate an array bigger than 2**32 bytes on
> a machine that has a 32-bit address space.  That's a lot different from
> telling me I can't allocate a 1000-bit integer on such a machine.


In ten years time we'll all have 64-bit machines with hundreds of Gb of RAM
(as well as content-addressed memory etc.) and look back at 32-bit
addressing as ludicrously small. "How ever did we manage with such tiny
amounts of memory?" we will ask each other ;-)

Nick.

Re: Overflows (lisp fixnum-bignum conversion)

[Larry Kilgallen]

In article <dewar.860424609@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) writes:
> Bob Duff said
> 
> <<(By the way, in going from a 32-bit address to a 64-bit address, don't
> think in terms of doubling the size of the address.  In fact, you're
> multiplying the the size of the address space by about 4 billion, which
> is an awful lot.  Much bigger than the switch from 16 to 32.  It's hard
> for me to even imagine how big 2**64 bytes is.)>>
> 
> Yes, but this is address space, not actual data in a program, if you start
> mappiong entire file systems into virtual memory, you can be surprised how
> fast the 64 bits gets eaten up.

I don't see it going that fast.  Disks I use hold 1 GB, while others
can hold 4 or 9 GB.  64 bits allows me to address the contents of about
2,000,000,000 of the 9 GB drives.  How many disk drives have ever been
built ?

Larry Kilgallen

Re: Overflows (lisp fixnum-bignum conversion)

[Robert Dewar]

Bob Duff said

<<(By the way, in going from a 32-bit address to a 64-bit address, don't
think in terms of doubling the size of the address.  In fact, you're
multiplying the the size of the address space by about 4 billion, which
is an awful lot.  Much bigger than the switch from 16 to 32.  It's hard
for me to even imagine how big 2**64 bytes is.)>>

Yes, but this is address space, not actual data in a program, if you start
mappiong entire file systems into virtual memory, you can be surprised how
fast the 64 bits gets eaten up.

Re: Overflows (lisp fixnum-bignum conversion)

[Robert Dewar]

Larry said

<<I don't see it going that fast.  Disks I use hold 1 GB, while others
can hold 4 or 9 GB.  64 bits allows me to address the contents of about
2,000,000,000 of the 9 GB drives.  How many disk drives have ever been
built ?>>

First, the 10GB drives you are used to using on small machines are by no 
means the largest storage devices in use to day, many large mainframe
installations approach terabyte storage capacity, and some exceed it.

Second, your calculation assumes that you are linearly mapping the disks
into memory, that's not at all the way it works, instead you would map
them into a hierarchical arrangemnent, allowing LOTS of extra space for
expansion in each node. The whole idea of a 64-bit address space is that
you can "waste" it lavishly to allow for growth of structures, and not
run out. 

For instance, in an Ada environment in a 64-bit machine, it makes perfectly
good sense to give every task a gigabyte stack, even if you have thousands
of tasks, but you cannot use this approach at all on a 32-bit machine.

Re: Overflows (lisp fixnum-bignum conversion)

[Nick Roberts]

Larry Kilgallen <kilgallen@eisner.decus.org> wrote in article
<1997Apr7.130018.1@eisner>...
[...]
> [...]  Disks I use hold 1 GB, while others
> can hold 4 or 9 GB.  64 bits allows me to address the contents of about
> 2,000,000,000 of the 9 GB drives.  How many disk drives have ever been
> built ?


Already IBM scientists (at Boca Raton, is it?) are building prototype '3D'
computers - which use laser holography within a block of a very special
material which switches its angle of polarisation very fast at a certain
precise temperature - which promise to be able to store the equivalent of
2^64 bytes of information easily (probably a lot more). Such computers
would certainly have the potential for outsmarting humans by several orders
of magnitude. This is actually true. Sleep well!

Nick.

Re: Overflows (lisp fixnum-bignum conversion)

[Robert Dewar]

Nick said

<<Already IBM scientists (at Boca Raton, is it?) are building prototype '3D'
computers - which use laser holography within a block of a very special
material which switches its angle of polarisation very fast at a certain
precise temperature - which promise to be able to store the equivalent of
2^64 bytes of information easily (probably a lot more). Such computers
would certainly have the potential for outsmarting humans by several orders
of magnitude. This is actually true. Sleep well!!!>

Nick if you really think that simply providing computers with 2**64 bytes
of information will magically ensure that they can outsmart humans, you
have been watching too much Startrek. Yes, I know you said potential, but
still ....

Re: Overflows (lisp fixnum-bignum conversion)

[Robert A Duff]

In article <01bc42b0$a88691c0$90f482c1@xhv46.dial.pipex.com>,
Nick Roberts <Nick.Roberts@dial.pipex.com> wrote:
>
>
>Robert A Duff <bobduff@world.std.com> wrote in article 
>> I won't complain if I can't allocate an array bigger than 2**32 bytes on
>> a machine that has a 32-bit address space.  That's a lot different from
>> telling me I can't allocate a 1000-bit integer on such a machine.
>
>
>In ten years time we'll all have 64-bit machines with hundreds of Gb of RAM
>(as well as content-addressed memory etc.) and look back at 32-bit
>addressing as ludicrously small. "How ever did we manage with such tiny
>amounts of memory?" we will ask each other ;-)

Perhaps, but the typical Ada, C++, Pascal, etc. compiler will *still*
not handle my 1000-bit integer correctly!  Lisp and Smalltalk, which
never had any problem with 1000-bit integers on 16-bit machines, will
*still* have no problem.

(By the way, in going from a 32-bit address to a 64-bit address, don't
think in terms of doubling the size of the address.  In fact, you're
multiplying the the size of the address space by about 4 billion, which
is an awful lot.  Much bigger than the switch from 16 to 32.  It's hard
for me to even imagine how big 2**64 bytes is.)

- Bob

Re: Overflows (lisp fixnum-bignum conversion)

[Marin David Condic, 561.796.8997, M/S 731-93]

Robert Dewar <dewar@MERV.CS.NYU.EDU> writes:
><<Already IBM scientists (at Boca Raton, is it?) are building prototype '3D'
>computers - which use laser holography within a block of a very special
>material which switches its angle of polarisation very fast at a certain
>precise temperature - which promise to be able to store the equivalent of
>2^64 bytes of information easily (probably a lot more). Such computers
>would certainly have the potential for outsmarting humans by several orders
>of magnitude. This is actually true. Sleep well!!!>
>
>Nick if you really think that simply providing computers with 2**64 bytes
>of information will magically ensure that they can outsmart humans, you
>have been watching too much Startrek. Yes, I know you said potential, but
>still ....
>
    Seems I've heard this sort of claim by the AI croud before - just
    about every time there's a major advancement in the capacity of
    computer memory or processor throughput. And the claim has (so
    far) never materialized. The problem is not memory or throughput,
    but one of algorithm. Nobody has yet demonstrated a "thinking"
    algorithm that just needs more horsepower to make it work. (Of
    course, if we redefine "thinking" to stretch it far enough, we
    could probably demonstrate a box of rocks undertaking the task!)

    "You can lead a computer to data, but you can't make it think."

        --  M. D. Condic

    MDC

Marin David Condic, Senior Computer Engineer    ATT:        561.796.8997
M/S 731-96                                      Technet:    796.8997
Pratt & Whitney, GESP                           Fax:        561.796.4669
P.O. Box 109600                                 Internet:   CONDICMA@PWFL.COM
West Palm Beach, FL 33410-9600                  Internet:   CONDIC@FLINET.COM
===============================================================================
    "That which belongs to another."

        --  Diogenes, when asked what wine he liked to drink.
===============================================================================

Re: Overflows (lisp fixnum-bignum conversion)

[Robert A Duff]

In article <dewar.860257082@merv>, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
>Robert Duff said
>
><<> Analogy: Suppose you write a signed integer expression that overflows.
>> In C, you get unpredictable results (exactly what Ada calls erroneous).
>> In Ada, you get a run-time error.  In Lisp, you get the right answer.
>> It seems to me that, as far as preventing bugs goes, with respect to
>> this particular issue, C is worst, Ada is better (because it detects the
>> error), and Lisp is better still (because it prevents the error).>>
>
>I find this too facile. The trouble is that better means better according
>to some metric. What are you interested in?
>
>More flexibility
>More efficiency
>More simplicity
>...

I thought I made that clear: I said, "as far as preventing bugs goes".
I meant logic errors in the program.  In general, with respect to *this*
metric, the worst possible semantics is "erroneous", better is to detect
the error (either at compile time or run time), and best of all is to
prevent the error.  This is because it is easier to reason about the
program, if you don't have to worry about weird boundary conditions
involving numbers like 2**31-1, which (usually) have nothing to do with
the problem, and everything to do with the underlying hardware.  I am
well aware that other concerns (mainly efficiency) might produce a
different rating -- in particular, for efficiency, "erroneous" is best,
detection second best, and prevention (i.e. Lisp bignums) worst.

Remember that this was all in response to somebody who claimed that
declaring a certain feature of Ada 83 "erroneous" somehow made this
feature of Ada 83 safer, than corresponding features in other languages
that require the feature to "work" (such as Ada 95).  I disagree with
that.

I also made it clear I was talking about overflows of signed integer
numbers -- that is, on arithmetic.  For this particular feature, and
this particular metric (bug prevention), I stand by my statement that C
is worst, Ada better, and Lisp better still.  Note that I was *not*
talking about array bounds checking, nor about range checking.  Just
overflows.

Aside: It would be possible to design a language that had range checking
as in Ada, but prevented overflows as in Lisp.  In such a language, I
could write:

    type T is range 0 .. N;
    X: T := ...;
    Y: T := ...;
    Average: T := (X + Y) / 2;

and be guaranteed that Average will contain the "right" answer.  In Ada,
if N is 10, it will probably not overflow.  If N is 2**31, it will
overflow on some compilers in some cases, and if N is 2**32, some
compilers won't even accept it.  And don't beat me up about efficiency:
I understand that there would be an efficiency cost to such
functionality, in some cases.  (OTOH, the inefficiency could be pretty
much avoided by writing "(T'(X) + T'(Y)) / 2", and make sure the bounds
of T match the hardware bounds.)

Maybe I could also write:

    type T is range 0..Infinite;

or

    type T is range 0..<>;

or some such thing, meaning the upper bound is arbitrarily large.

Maybe I could also write:

    type T is range 0..<non-static-expression>;

- Bob

Re: Overflows (lisp fixnum-bignum conversion)

[Jon S Anthony]

In article <01bc43ae$811f1680$3ef882c1@xhv46.dial.pipex.com> "Nick Roberts" <Nick.Roberts@dial.pipex.com> writes:

> precise temperature - which promise to be able to store the equivalent of
> 2^64 bytes of information easily (probably a lot more). Such computers
> would certainly have the potential for outsmarting humans by several orders
> of magnitude. This is actually true. Sleep well!

Despite folks like Dennett, I would be willing to bet basically
anything that the probability of this is zero.

/Jon

-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Overflows (lisp fixnum-bignum conversion)

[Charles H. Sampson]

In article <E8Bvpy.Ixq@world.std.com>,
Robert A Duff <bobduff@world.std.com> wrote:
>
>Remember that this was all in response to somebody who claimed that
>declaring a certain feature of Ada 83 "erroneous" somehow made this
>feature of Ada 83 safer, than corresponding features in other languages
>that require the feature to "work" (such as Ada 95).  I disagree with
>that.
>
     Hold on!  I'm pretty sure you're referring to me, the guy who 
started this thread, and I said no such thing.  It's beyond me how what 
I originally said could have been interpreted that way, but I later 
elaborated.  Repeating: In my shop, erroneous means not checked by the 
compiler (maybe not checkable) and compiler dependent, ad hoc, seman-
tics; therefore don't use.

     Ada 83 had a pretty short list of erroneous constructs, so it was 
generally easy to avoid them.  Not always.  Some were treacherous, such 
as referencing an actual parameter directly and through its correspond-
ing formal parameter, which fortunately doesn't arise very often in a 
well-designed program.  In any case, that's an aliasing problem and my 
original complaint was that by adding overlays to Ada 95 another form of 
aliasing is made available, with its attendant impact on maintenance and 
enhancement.  Ada 83 had pretty well minimized aliasing to those cases 
that were unavoidable in any practical sense.

				Charlie

Re: Overflows (lisp fixnum-bignum conversion)

[Joel VanLaven]

Larry Kilgallen (kilgallen@eisner.decus.org) wrote:
: In article <dewar.860424609@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) writes:
: > Bob Duff said
: > 
: > <<(By the way, in going from a 32-bit address to a 64-bit address, don't
: > think in terms of doubling the size of the address.  In fact, you're
: > multiplying the the size of the address space by about 4 billion, which
: > is an awful lot.  Much bigger than the switch from 16 to 32.  It's hard
: > for me to even imagine how big 2**64 bytes is.)>>
: > 
: > Yes, but this is address space, not actual data in a program, if you start
: > mappiong entire file systems into virtual memory, you can be surprised how
: > fast the 64 bits gets eaten up.

: I don't see it going that fast.  Disks I use hold 1 GB, while others
: can hold 4 or 9 GB.  64 bits allows me to address the contents of about
: 2,000,000,000 of the 9 GB drives.  How many disk drives have ever been
: built ?

I aggree.  Given progress similar to history, 64 bits ought to be enough
for many decades.  Assuming that capacity doubles every two years and
that only highly specialized systems today would need more than 1 terrabyte
of disk space, the first time 64 bit addresses will not cover a very large
filesystem will be in about 48 years.  The average 4gig home system 
(extrapolated) won't hit that barrier for another 16 years after that.
Before either UNIX 32-bit times will wrap around.  In between we will
probably think that 32 bit addressing wasn't enough but 64 bits is more
than enough.

-- Joel.
-- 
-- Joel VanLaven

Re: Overflows (lisp fixnum-bignum conversion)

[Robert A Duff]

In article <dewar.860441935@merv>, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
>For instance, in an Ada environment in a 64-bit machine, it makes perfectly
>good sense to give every task a gigabyte stack, even if you have thousands
>of tasks, but you cannot use this approach at all on a 32-bit machine.

How about this scheme for a 32-bit machine?  Reserve half the address
space for code and heap.  Give the other half to the environment task.
If a second task is created, steal half of the unused address space from
the first task.  If a third task is created, steal half of the unused
address space from the task with the biggest unused stack space.  And so
on.

Thus, you can create lots of small tasks, or a few huge ones, without
ever having to say "pragma Storage_Size".  (Of course, you can't create
a huge number of huge tasks -- but that's a limitation of the machine,
not the run-time model.)

This seems better than having a particular default size for each task's
stack.  Has anybody done it?

(As Robert says, on a 64-bit machine, you can allocate, say, 16 G of
address space to each task, and still have enough address space for
about a billion task stacks.)

- Bob