Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

So, this is basically what dynamic languages do because they _can_ go back an allocate more memory transparently to the developer. However, static languages cannot change the size of the values dynamically at runtime without additional memory allocations. In fact, this would likely mean that all numbers must be heap allocated, which will likely be a performance penalty when working in high-performance systems. In these cases, using an algorithm that produces correct results without error with constant memory usage is preferred.


This should be possible for static languages? Since the width of the operands are known ahead of time, a wider integer can be unconditionally reserved on the stack for the result of the operation.

I'm curious which dynamic language reallocates to store larger integers? All of the dynamic languages that I'm familiar with simply store numbers as doubles, with variable width integers being handled by opt-in types.


But if you do this in a static language you’d quickly run out of space anyway.

Say you start with two Int16’s. Any addition would result in an Int17. Adding a pair of those together would result in an Int18, and so forth.

You’d blow past Int64 in no time.


I'm pretty sure their intent was to demote the value back to an int16 after completing the midpoint operation.


> You’d blow past Int64 in no time.

Not really. You only need to preserve according to the msb of each number. If you are adding 0(Int18)+1(Int18), you don't need 1(Int36) anymore than you need 1(Int18) or even 1(Int1).


But you don't know the MSB at compile time in the general case.


> If you are adding 0(Int18)+1(Int18), you don't need 1(Int36)

No, you’d need an Int19. We were talking about statically typed languages, so you need to decide the type at compile-time. If you add two UInt16’s they could both contain up to 0xFFFF, you need 17 bits to store that answer. Basically, with every addition you need 1 more bit than the largest of the two (types, not values) you are adding together to prevent a potential overflow. It’s even worse for multiplication.


Couldn't you have a constraining operation in there to assert that you have enough bits? You are right that we don't know if `a + b` would need more bits than either a or b. However, we could have an assert that allows us to ensure the static constraints are satisfied. And the type system could be used as a place to know where we haven't checked the constraint.

(Note that I'm not too clear how valuable this would be. Just asking why that isn't a valid path.)


> No, you’d need an Int19.

No, that's completely false. You don't need an Int19 but an Int1.


How do you figure that you can store the result of adding 2 Int18s in an Int1 ? Remember, we’re talking about static types and you don’t know the values at compile time.


Static languages can have types which have an unboxed value part (of fixed size) that manages a boxed heap part.

  class bignum {
  private:
    digit_t *limbs;
  public:
    bignum(int val);
    ~bignum();
    bignum operator +(const bignum &rhs);
    ...
  };


> Since the width of the operands are known ahead of time

Not so for loops and accumulator constructs.


I think it would be reasonable to also have overflowing and checked versions of the operators, for cases where the compiler can't guarantee the size (e.g. mutable variables in loops).


> Since the width of the operands are known ahead of time, a wider integer can be unconditionally reserved on the stack for the result of the operation.

What is the width of `i` in:

    foo(int count) {
      int i = 0;
      for (int j = 0; j < count; j++) {
        i = i + i;
      }
    }


You probably want i=1 since i=0 is an answer you can predict:

i = 0 implies that i = 0 + 0 = 0; so the loop doesn’t evolve, and the whole thing can be optimized to just i = 0.

For i=1, the loop simplifies to 2^count and a count-length type, which is the point I think you wanted.


Heh, oops, yes. :)


Python, common lisp, and perl for starters.


Also scheme and prolog

The problem you can then run into is that a mathematical operation can OOM


I've not seen this in practice.

You need some numeric accident involving a higher power operator like exponentiation.

In TXR Lisp I made exponentiation n-ary: you can do (expt x y z ...).

The associativity is right to left: it means

         ...
       z
     y
   x
rather than the less useful cumulative exponentiation of the same base:

  yz...
 x
which can easily be obtained as (expt x (* y z ..)).

So, anyway, if you apply expt to small list of small operands, you can cons up a big number in rather a hurry.

If it is important to prevent a problem like this, a limit can be imposed on bignums (say, large enough for common cryptography to still work).


I didn't know python could do that, that's pretty cool.

I gotta disagree on perl, though, even though it can represent numbers outside of the range of a double, it can't manipulate them without converting them into doubles.


“use bignum;” and you can.


The result of any expression would still be assigned to a variable or function parameter that has a defined type, so it would be limited to that size. However, intermediate values could automatically use larger registers, the CPU's carry flag, or some other mechanism to expand the range.

It would be desirable that every expression either produces the mathematically correct result, or a runtime exception.

In many cases it would be easy for the compiler to limit intermediate results to some number of bits (since it knows the maximum allowed range for the final result), but it may be a problem to guarantee this.


> However, static languages cannot change the size of the values dynamically at runtime without additional memory allocations.

That is false; a static language could have bignum integers. E.g. you can easily have a bignum class in C++, which is static.

You can't have a variable-length bignum as an unboxed value type.

"Language with unboxed value types" and "statically typed language" are separate, somewhat related concepts.


They're right that this would require additional allocations though, no?

As you indicate though there's no need for this to be something the user of the type needs to think about.


Haskell is both compiled and has arbitrarily large integers. Granted, Haskell isn't used for high performance systems, but it can be used to generate programs for high performance systems.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: