Positive integers

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
31 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: Positive integers

Aaron Denney
On 2006-03-26, Daniel McAllansmith <[hidden email]> wrote:

> I was thinking about several things in this thread, torsors, overflow
> semantics, bounds checking...
> I wonder if there would be any merit in being able to define constrained
> subsets of integers and the semantics when/if they overflow.
>
> For example, take UNIX nice levels -20 to 19.  You could have
>   data ConstrainedInteger = CI {distToMax :: Natural, distToMin :: Natural}
> this would ensure only the 40 integers can be represented.
> Then you could have _something_ that defined what happened on overflow,
> whether it wraps, reflects, errors, truncates or whatever.
>
> When it comes to compile, or source preprocessing, time these numbers
> could be realigned to a primitive Int or Word representation of
> suitable size and have the appropriate overflow code written in.  And,
> in the case of error or wrap overflow semantics on a set of the right
> size, the overflow checks could be disabled, like other assertions, at
> runtime.

Now that is an interesting idea.

--
Aaron Denney
-><-

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Positive integers

John Meacham
In reply to this post by Aaron Denney
On Fri, Mar 24, 2006 at 06:54:54PM +0000, Aaron Denney wrote:
> > Without breaking compatibility?
> > But class instances become invalid if the hierarchy is modified.
>
> No, compatibility will be broken.  Hopefully not for most uses -- I
> don't think most people define new instances, and those that do will be
> able to do so more reasonably, so hopefully wouldn't mind.

The problem isn't with creating instances, it is with using the classes
at all.

well, in interfaces you are going to end up with some specific class or
another concretely mentioned in your type signatures, which means you
can't interact with code that only knows about the alternate class. like

genericLength :: Integral a => [b] -> a

if you have a different 'Integral' you can't call genericLength with it,
or anything built up on genericLength. basically there would be no way
for 'new' and 'old' polymorphic code to interact.

the inability to evolve the class hierarchy is a serious issue, enough
that it very well could be impractical for haskell' unless something
like class aliases were widely adopted.

        John


--
John Meacham - ⑆repetae.net⑆john⑈
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Positive integers

Jan-Willem Maessen
In reply to this post by Daniel McAllansmith

On Mar 26, 2006, at 4:35 PM, Daniel McAllansmith wrote:
> [Discussion of positive integers and Words]

> I was thinking about several things in this thread, torsors, overflow
> semantics, bounds checking...
> I wonder if there would be any merit in being able to define  
> constrained
> subsets of integers and the semantics when/if they overflow.

Oddly, I've just finished coding this up, with type-level bounds  
(represented by type-level ints).  It's a big pile of modules on top  
of John Meacham's type-level Nats library, which add type-level Ints  
(as non-normalized Nat pairs), unknown endpoints (permitting Integer  
to fit in the same framework), and the actual bounded ints themselves.

Naturally, I needed to define my own versions of the functionality in  
Eq, Ord, and Num.  These resolve statically as much as possible  
(including some possibly dubious behavior with singleton intervals).  
That said, I don't try to do everything at the type level---it became  
too tiring, with not enough plausible benefit.

Any and all: Drop me a line if you are interested, it's a stack of  
3-4 modules and at best half-baked.  I'd just gotten a mostly-
complete version.

-Jan-Willem Maessen


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Positive integers

Burton Samograd
In reply to this post by Daniel McAllansmith
> For example, take UNIX nice levels -20 to 19.  You could have
>   data ConstrainedInteger = CI {distToMax :: Natural, distToMin :: Natural}
> this would ensure only the 40 integers can be represented.
> Then you could have _something_ that defined what happened on overflow,
> whether it wraps, reflects, errors, truncates or whatever.

Doesn't Ada have constrained number types which have similar behaviour?

--
burton samograd                                                [hidden email]
kruhft.blogspot.com   www.myspace.com/kruhft   metashell.blogspot.com
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Positive integers

Dylan Thurston-3
In reply to this post by John Meacham
On Mon, Mar 27, 2006 at 05:02:20AM -0800, John Meacham wrote:
> well, in interfaces you are going to end up with some specific class or
> another concretely mentioned in your type signatures, which means you
> can't interact with code that only knows about the alternate class. like
>
> genericLength :: Integral a => [b] -> a
>
> if you have a different 'Integral' you can't call genericLength with it,
> or anything built up on genericLength. basically there would be no way
> for 'new' and 'old' polymorphic code to interact.

I think the idea would be that the source for genericLength would
compile using either class hierarchy with no change.  For the case of
genericLength, this is true for the proposed alternate prelude Hennig
Theilemann pointed to.  It would be mostly true in general for that
proposal, with the exception that you would sometimes need to add Show
or Eq instances.

> the inability to evolve the class hierarchy is a serious issue, enough
> that it very well could be impractical for haskell' unless something
> like class aliases were widely adopted.

I think that as long as you're not defining classes source compatibility
would not be hard.  Of course you couldn't hope to link code written
with one hierarchy against another.

Peace,
        Dylan Thursto

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

signature.asc (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Positive integers

Neil Mitchell
In reply to this post by Burton Samograd
> Doesn't Ada have constrained number types which have similar behaviour?

Yes. Just for comparison, the behaviour of the Ada number is to throw
an exception at runtime if a number overflows its bounds. If these
checks can be eliminated statically, then they are. If an operation
will always give a runtime error then this is given as a warning at
compile time.

Thanks

Neil
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Positive integers

Henning Thielemann

On Mon, 27 Mar 2006, Neil Mitchell wrote:

>> Doesn't Ada have constrained number types which have similar behaviour?
>
> Yes. Just for comparison, the behaviour of the Ada number is to throw
> an exception at runtime if a number overflows its bounds. If these
> checks can be eliminated statically, then they are. If an operation
> will always give a runtime error then this is given as a warning at
> compile time.

Quite similar to Modula (maybe also Pascal), as I indicated. There the
bounded integers are called sub-ranges.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Positive integers

ihope
In reply to this post by Henning Thielemann
On 3/24/06, Henning Thielemann <[hidden email]> wrote:
> A new type, say Cardinal as in Modula, would document for the user of a
> function that only non-negative numbers are allowed and the function
> writer can be sure, that only non-negative numbers are passed.
>
> ...
>
>   newtype Cardinal = Cardinal Integer deriving (Show, Read, Eq, Ord, Ix)
>   newtype Card     = Card     Int     deriving (Show, Read, Eq, Ord, Ix)

Has anybody tried to implement arbitrary- and machine-size natural
numbers (Cardinal and Card, respectively) in GHC using unboxed types?
It should be just a matter of tweaking Int, Integer and Word a bit.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Positive integers

Aaron Denney
In reply to this post by Dylan Thurston-3
On 2006-03-27, Dylan Thurston <[hidden email]> wrote:

>
> --===============0906829955==
> Content-Type: multipart/signed; micalg=pgp-sha1;
> protocol="application/pgp-signature"; boundary="3V7upXqbjpZ4EhLz"
> Content-Disposition: inline
>
>
> --3V7upXqbjpZ4EhLz
> Content-Type: text/plain; charset=us-ascii
> Content-Disposition: inline
> Content-Transfer-Encoding: quoted-printable
>
> On Mon, Mar 27, 2006 at 05:02:20AM -0800, John Meacham wrote:
>> well, in interfaces you are going to end up with some specific class or
>> another concretely mentioned in your type signatures, which means you
>> can't interact with code that only knows about the alternate class. like
>>=20
>> genericLength :: Integral a =3D> [b] -> a
>>=20
>> if you have a different 'Integral' you can't call genericLength with it,
>> or anything built up on genericLength. basically there would be no way
>> for 'new' and 'old' polymorphic code to interact.=20
>
> I think the idea would be that the source for genericLength would
> compile using either class hierarchy with no change.  For the case of
> genericLength, this is true for the proposed alternate prelude Hennig
> Theilemann pointed to.  It would be mostly true in general for that
> proposal, with the exception that you would sometimes need to add Show
> or Eq instances.

Right.

>> the inability to evolve the class hierarchy is a serious issue, enough
>> that it very well could be impractical for haskell' unless something
>> like class aliases were widely adopted.
>
> I think that as long as you're not defining classes source compatibility
> would not be hard.  Of course you couldn't hope to link code written
> with one hierarchy against another.

Wouldn't instance declaration also be problematic?

(And yes, we desperately need something like class aliases.)

--
Aaron Denney
-><-

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Positive integers

ihope
On 3/29/06, Aaron Denney <[hidden email]> wrote:
> (And yes, we desperately need something like class aliases.)

You mean like this?

class Foo a b where
  foo :: a -> b

class Foo a b => Bar a b where

instance Foo a b => Bar a b where

This will make every instance of Foo one of Bar, and make sure every
instance of Bar is an instance of Foo.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Positive integers

Aaron Denney
On 2006-04-02, ihope <[hidden email]> wrote:
> On 3/29/06, Aaron Denney <[hidden email]> wrote:
>> (And yes, we desperately need something like class aliases.)
>
> You mean like this?

Not quite, I meant something like John Meacham's proposal:
http://repetae.net/john/recent/out/classalias.html

--
Aaron Denney
-><-

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
12