[Agda] Externally vs internally consistent exensions of Agda
Alan Jeffrey
ajeffrey at bell-labs.com
Fri Oct 21 16:51:28 CEST 2011
On 10/21/2011 07:48 AM, Nils Anders Danielsson wrote:
> On 2011-10-11 03:20, Alan Jeffrey wrote:
> Cheating? I'd say the important question is whether you get guarantees
> that are strong enough for your intended purpose, and I guess the answer
> isn't always the same.
Indeed. There are (at least) two possible goals: run-time safety (memory
safety, maintaining program invariants, not inhabiting empty types, etc)
and external equivalence (e.g. correctness of compiler optimizations).
I'm primarily interested in the former, but I can understand that people
might expect beta-eta equivalence to imply observable equivalence.
> Your question made me think of QuickCheck. The Arbitrary monad doesn't
> satisfy the monad laws if you interpret equality as ordinary
> observational equality (because the monad uses random numbers), but
> presumably it satisfies the monad laws for some other, reasonable notion
> of equality.
Hmm, it may be that there's a way of thinking about program semantics in
terms of underspecification. Normally underspecification is modeled as
nondeterminism, but this would be a restricted form of nondeterminism
which is modeled as being resolved at top level, and so the execution of
a program is deterministic.
A.
More information about the Agda
mailing list