[Agda] tweaking evaluation
Peter Selinger
selinger at mathstat.dal.ca
Tue Aug 11 17:30:26 CEST 2015
This may be a newbie question. I have a program whose type-checking
requires the evaluation of some moderately large terms. The fact that
Agda uses normal order (or call-by-name) evaluation makes the
evaluations very slow. Is there a way to force certain terms to be
evaluated to normal form?
Here's a toy example (adapted from
http://stackoverflow.com/questions/21210569/is-the-evaluation-strategy-of-agda-specified-anywhere):
open import Data.Product
open import Relation.Binary.PropositionalEquality
-- using a unary implementation of ℕ for illustration purposes.
data ℕ : Set where
zero : ℕ
suc : ℕ → ℕ
{-# BUILTIN NATURAL ℕ #-}
infixl 4 _+_
infixl 5 _*_
infixr 6 _^_
_+_ : (m n : ℕ) → ℕ
zero + n = n
suc m + n = suc (m + n)
_*_ : (m n : ℕ) → ℕ
zero * n = zero
suc m * n = n + m * n
_^_ : (m n : ℕ) → ℕ
m ^ zero = suc zero
m ^ suc n = m * m ^ n
-- naive diagonal function
Δ : {A : Set} -> A -> A × A
Δ x = (x , x)
-- checking takes about 11 seconds
slow : 2 ^ 13 * 0 ≡ 0
slow = refl
-- takes about 22 seconds
slower : Δ (2 ^ 13 * 0) ≡ Δ 0
slower = refl
Naturally, "slower" takes about twice as long to type-check than
"slow".
It is stated here that using "with" on an expression causes the
expression to be evaluated to normal form:
https://lists.chalmers.se/pipermail/agda/2012/004443.html
Therefore, I figured the following could be a way to speed up the
diagonal function:
-- better diagonal function?
Δ' : {A : Set} -> A -> A × A
Δ' x with x
Δ' x | y = (y , y)
However, this doesn't work at all, as the result still takes 22
seconds to evaluate:
-- takes about 22 seconds
slower' : Δ' (2 ^ 13 * 0) ≡ Δ' 0
slower' = refl
Is there a way to force some term to be evaluated strictly?
Thanks, -- Peter
More information about the Agda
mailing list