[Agda] Raw natural numbers
Alan Jeffrey
ajeffrey at bell-labs.com
Thu Oct 21 20:44:55 CEST 2010
I'm building the new compiler now... Fingers crossed!
A more general solution to the problem of unsafeCoerce getting in the
way would be for Agda to use its own coerce function, defined something
like:
{-# INLINE [1] coerce #-}
coerce = Unsafe.Coerce.unsafeCoerce
{-# RULES "coerce-id" forall (x :: a) . coerce x = x #-}
This would at least remove all the identity coercions, and would allow
other FFI bindings to define their own RULES.
A.
On 10/21/2010 04:48 AM, Ulf Norell wrote:
>
> On Thu, Oct 21, 2010 at 12:22 AM, Alan Jeffrey <ajeffrey at bell-labs.com
> <mailto:ajeffrey at bell-labs.com>> wrote:
>
> Hi everyone,
>
> I did some simple bindings for raw natural numbers:
>
> http://github.com/agda/agda-system-io/tree/master/src/Data/Natural
>
> The interesting thing is that we can almost optimize away many of
> the uses of unary numbers -- in particular to get constants such as
> #1000000 to be represented in native form rather than unary.
>
> The idea would be to add a rule to Haskell's rewrite engine:
>
> {-# RULES "int2nat2int" forall x .
> MAlonzo.Data.Nat.mazNatToInteger (MAlonzo.Data.Nat.mazIntegerToNat x)
> = x #-}
>
> This almost works. The two things stopping it are:
>
> a) There isn't an FFI binding for Nat (grr) which means the compiler
> inserts some unsafeCoerce operations which then stop rewrites from
> firing.
>
> b) The definitions of mazNatToInteger and mazIntegerToNat define a
> local variable, which isn't in scope for rewriting.
>
>
> I removed the unnecessary coercion of integer literals, so now you get
>
> Unsafe.Coerce.unsafeCoerce (mazIntegerToNat ((10) :: Integer))
>
> instead of
>
> Unsafe.Coerce.unsafeCoerce (mazIntegerToNat
> (Unsafe.Coerce.unsafeCoerce ((10) :: Integer)))
>
> when using natural number literals. I also changed the implementation of
> mazNatToInteger/IntegerToNat to
>
> mazNatToInteger
> = \ x -> case x of { C2 -> 0 :: Integer; C3 x -> 1 + (mazNatToInteger
> (Unsafe.Coerce.unsafeCoerce x)) }
> mazIntegerToNat
> = \ x -> if x <= (0 :: Integer) then C2 else C3
> (Unsafe.Coerce.unsafeCoerce (mazIntegerToNat (x - 1)))
>
> (where C2 and C3 are the constructor names for zero and suc). Hopefully
> this will help a little.
>
> / Ulf
More information about the Agda
mailing list