[Agda] how does BUILTIN work - practical programming in Agda

Alan Jeffrey ajeffrey at bell-labs.com
Tue Dec 6 19:42:36 CET 2011


Lennart also said "Also, as a compiler writer I love the idea that 
evaluation order is left up to me rather than the language spec."

Since Agda is total (ignoring for now code which switches off 
termination checking) the difference between strict and lazy ordering is 
just space and time usage. Should the Agda language specification say 
anything about space/time complexity? Or is that implementation-specific?

If we're going to address higher-order combinators, then I think there 
are bigger issues (cough cough nested uses of combinators cough sized 
types cough) than short-circuiting.

A.

On 12/06/2011 11:08 AM, Nils Anders Danielsson wrote:
> On 2011-12-05 19:35, Alan Jeffrey wrote:
>> Yes, I can see how such a library could be used, but I can also imagine
>> it getting pretty hairy pretty quickly. It's not obvious to me that the
>> benefit outweighs the cost though, given that users can always write:
>>
>>      f xs with b
>>      ... | true = g
>>      ... | false = h
>>
>> instead of (if b then g else h) and get laziness without any explicit
>> thunking.
>
> I wonder if the thunking needs to be explicit—could one use some kind of
> implicit coercions? I don't think Coq's implicit coercion mechanism can
> handle coercions of type
>
>     {A : Set} → A → Thunk A.
>
> Lennart Augustsson describes some of the drawbacks of working in a
> strict language:
>
>     More points for lazy evaluation
>     http://augustss.blogspot.com/2011/05/more-points-for-lazy-evaluation-in.html
>
> His main point is that you can't write things like
>
>     any p = or ∘ map p,
>
> because this definition doesn't short-circuit in the right way.
>
> With a Thunk type we could handle this situation:
>
>     data Thunked-list (A : Set) : Set where
>       []  : Thunked-list A
>       _∷_ : A → Thunk (Thunked-list A) → Thunked-list A
>
>     or  : Thunked-list Bool → Bool
>     map : {A B : Set} → (A → B) → Thunked-list A → Thunked-list B
>
> The standard library already contains a large number of variants of
> lists, so I'm not too keen on adding another dimension—strictness—to the
> design space. However, being able to control the strictness on a
> case-by-case basis seems to be quite important, so we should probably
> support this in some way.
>


More information about the Agda mailing list