[Agda] main, IO, agda -c, Nat and Float

Alan Jeffrey ajeffrey at bell-labs.com
Sat Oct 16 18:48:55 CEST 2010


On 10/16/2010 06:17 AM, Nils Anders Danielsson wrote:
> On 2010-10-16 11:24, Oscar Finnsson wrote:
>> Finally I got a question regarding Nat. Will
>>   >  value100000 : Nat
>>   >  value100000 = 100000
>> be stored as
>>   >  suc (suc (suc (suc (suc (suc (suc (suc (.... 100000 times ...)
>> or will the compiler realise that it can just store 100000?
>
> What does "just store 100000" mean? Unary numbers are represented in
> unary form also after compilation. One can probably do better: I've been
> told that Idris checks if a type is structurally isomorphic to the unary
> natural numbers, and if it is a different representation is used.

AFAICT, we can almost do this in out-of-the-box Agda: we could add a 
COMPILED_DATA pragma to bind Nat to an appropriate Haskell Natural type 
(e.g. an ADT wrapper round Integer).  Unfortunately there seems to be a 
deal-killer, in that Haskell allows (n+k) patterns, e.g.:

   f (x+1) = x
   f 0     = 0

but not (+k)n patterns, e.g.:

   g ((+1)x) = x
   g 0       = 0

The simplest language extension I can think of that would allow bindings 
of Agda datatypes to arbitrary Haskell types would be to support views 
in the FFI (e.g. http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns). 
  Recall:

    class View a b where
       view :: a -> b

The pragma declaration would be something like:

   COMPILED_VIEW Nat Natural Zero Suc

where we translate zero to (view Zero), suc x to (view (Suc x)) and a 
case expression to:

   case view y of Zero -> ... ; Suc x -> ...

that is, the same translation only with the magic word "view" on the 
front.  The FFI writer then provides the appropriate view instances:

   data Natural' = Zero | Suc Natural

   instance View Natural Natural' where
     view 0 = Zero
     view (n + 1) = Suc n

   instance View Natural' Natural where
     view Zero = 0
     view (Suc n) = n + 1

This would allow other nice binders, e.g. making Bytestring look like a 
list type to Agda, binding Agda integers to Haskell Integer, binding 
Agda products to Haskell products, etc.

The more extreme version would be to include view types in Agda, which 
would require some syntax for declaring a new type X with carrier Z to 
be an initial F-algebra (for an existing datatype F : Set -> Set) after 
which X can be treated as if it were declared as a datatype.  This would 
be very tricky to get right though, e.g. there is an iso X -> Z to worry 
about: which eta/beta properties should hold for it?  Also, what about 
other functors, not just Set -> Set?  What about terminal F-coalgebras? 
  etc. etc. etc.

A.

>
>> (btw, the source code (Builtin.hs) mention a bunch of builtins. Is
>> there any documentation over what the different buildins stand for?
>
> There is some documentation in the following file:
>
>     http://code.haskell.org/Agda/examples/Introduction/Built-in.agda
>
> --
> /NAD
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda



More information about the Agda mailing list