← Back to branch summary

~ubuntu-branches/ubuntu/wily/coq-doc/wily

« back to all changes in this revision

Viewing changes to dev/doc/notes-on-conversion

  • Committer: Bazaar Package Importer
  • Author(s): Stéphane Glondu, Stéphane Glondu, Samuel Mimram
  • Date: 2010-01-07 22:50:39 UTC
  • mfrom: (1.2.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20100107225039-n3cq82589u0qt0s2
Tags: 8.2pl1-1
http://bugs.debian.org/563669
http://bugs.debian.org/543545
[ Stéphane Glondu ]
* New upstream release (Closes: #563669)
  - remove patches
* Packaging overhaul:
  - use git, advertise it in Vcs-* fields of debian/control
  - use debhelper 7 and dh with override
  - use source format 3.0 (quilt)
* debian/control:
  - set Maintainer to d-o-m, set Uploaders to Sam and myself
  - add Homepage field
  - bump Standards-Version to 3.8.3
* Register PDF documentation into doc-base
* Add debian/watch
* Update debian/copyright

[ Samuel Mimram ]
* Change coq-doc's description to mention that it provides documentation in
  pdf format, not postscript, closes: #543545.

Show diffs side-by-side

added added

removed removed

Lines of Context:
dev/doc/notes-on-conversion
 
1
(**********************************************************************)
 
2
(* A few examples showing the current limits of the conversion algorithm *)
 
3
(**********************************************************************)
 
4
 
 
5
(*** We define (pseudo-)divergence from Ackermann function ***)
 
6
 
 
7
Definition ack (n : nat) :=
 
8
  (fix F (n0 : nat) : nat -> nat :=
 
9
     match n0 with
 
10
     | O => S
 
11
     | S n1 =>
 
12
         fun m : nat =>
 
13
         (fix F0 (n2 : nat) : nat :=
 
14
            match n2 with
 
15
            | O => F n1 1
 
16
            | S n3 => F n1 (F0 n3)
 
17
            end) m
 
18
     end) n.
 
19
 
 
20
Notation OMEGA := (ack 4 4).
 
21
 
 
22
Definition f (x:nat) := x.
 
23
 
 
24
(* Evaluation in tactics can somehow be controled *)
 
25
Lemma l1 : OMEGA = OMEGA.
 
26
reflexivity.  (* succeed: identity *)
 
27
Qed.          (* succeed: identity *)
 
28
 
 
29
Lemma l2 : OMEGA = f OMEGA.
 
30
reflexivity.  (* fail: conversion wants to convert OMEGA with f OMEGA *)
 
31
Abort.        (* but it reduces the right side first! *)
 
32
 
 
33
Lemma l3 : f OMEGA = OMEGA.
 
34
reflexivity.  (* succeed: reduce left side first *)
 
35
Qed.          (* succeed: expected concl (the one with f) is on the left *)
 
36
 
 
37
Lemma l4 : OMEGA = OMEGA.
 
38
assert (f OMEGA = OMEGA) by reflexivity. (* succeed *)
 
39
unfold f in H.   (* succeed: no type-checking *)
 
40
exact H.         (* succeed: identity *)
 
41
Qed.             (* fail: "f" is on the left *)
 
42
 
 
43
(* This example would fail whatever the preferred side is *)
 
44
Lemma l5 : OMEGA = f OMEGA.
 
45
unfold f.
 
46
assert (f OMEGA = OMEGA) by reflexivity.
 
47
unfold f in H.
 
48
exact H.
 
49
Qed. (* needs to convert (f OMEGA = OMEGA) and (OMEGA = f OMEGA) *)
 
50
 
 
51
(**********************************************************************)
 
52
(* Analysis of the inefficiency in Nijmegen/LinAlg/LinAlg/subspace_dim.v *)
 
53
(* (proof of span_ind_uninject_prop *)
 
54
 
 
55
In the proof, a problem of the form   (Equal S t1 t2)
 
56
is "simpl"ified, then "red"uced to    (Equal S' t1 t1)
 
57
where the new t1's are surrounded by invisible coercions.
 
58
A reflexivity steps conclude the proof.
 
59
 
 
60
The trick is that Equal projects the equality in the setoid S, and
 
61
that (Equal S) itself reduces to some (fun x y => Equal S' (f x) (g y)).
 
62
 
 
63
At the Qed time, the problem to solve is (Equal S t1 t2) = (Equal S' t1 t1)
 
64
and the algorithm is to first compare S and S', and t1 and t2.
 
65
Unfortunately it does not work, and since t1 and t2 involve concrete
 
66
instances of algebraic structures, it takes a lot of time to realize that
 
67
it is not convertible.
 
68
 
 
69
The only hope to improve this problem is to observe that S' hides
 
70
(behind two indirections) a Setoid constructor. This could be the
 
71
argument to solve the problem.
 
72
 
 
73