Comments (7)
@MSoegtropIMC I have no idea about what the bottleneck could be here, but if you need an expert opinion, you may want to consider trying to contact one of the original authors, Damien Pous: https://perso.ens-lyon.fr/damien.pous/
from aac-tactics.
@palmskog : if PRs messing with the guts of the tactic are welcome, I can also have a look. As I said I have some experience with this.
from aac-tactics.
PRs are welcome in general, but my priority is to preserve the "regular" behavior of AAC Tactics on the tutorial examples and the "caveat" examples. Standalone examples/benchmarks are also very welcome and encouraged as part of PRs.
from aac-tactics.
I expect that a single well placed "eval lazy" with a tailored delta does the trick. It might be, that I have to duplicate some standard library functions like list append in case such things are used in the interpretation function. If the interpretation uses Z arithmetic, things might get messy.
from aac-tactics.
@palmskog : I wasn't aware that the tactic is written in OCaml - I have little experience with this. What - as far as I can see - needs to be done is to do an explicit lazy eval in the type of decision_thm
after:
aac-tactics/src/aac_rewrite.ml
Line 127 in 3fc2fb1
expanding eval
, eval_aux
, fold_map
and the projections of the record Bin.pack
+ maybe a few things I overlooked, but it looks all very neat and clean.
This should make the proof statement identical to the original goal - not just unifiable. What likely happens here is that the kernel unifier chokes on terms which are the arguments of the AAC relation. If the type of decision_thm
is identical to the goal, the unifier has nothing to do.
from aac-tactics.
Consider this example of blowup:
From Coq Require ZArith.
From AAC_tactics Require Import AAC.
From AAC_tactics Require Instances.
Import ZArith.
Import Instances.Z.
Fixpoint mkevil n := match n with 0%nat => 1 | S k => 2 * mkevil k end.
(* 2 ^ n in Z *)
Definition evil := mkevil 25%nat.
Time Eval vm_compute in evil.
(* ~instant *)
Lemma test a : a + evil = evil + a.
Proof.
Time aac_reflexivity.
(* n = 32 -> 0.015s
n = 25 -> 0.016s
n = 20 -> 0.015s
n = 16 -> 0.014s
*)
Time Qed.
(* (memory usage seems negligible)
n = 32 -> too long
n = 25 -> 37s
n = 20 -> 1.15s
n = 16 -> 0.08s
*)
The proof is
test =
fun a : Z =>
@lift_reflexivity Z (@eq Z) (@eq Z)
(@aac_lift_subrelation Z (@eq Z) (@eq Z) (@eq_equivalence Z) (@eq_Transitive Z)
(@subrelation_refl Z (@eq Z))) (@eq_Reflexive Z) (Z.add a evil) (Z.add evil a)
(let env_sym :=
sigma_get
{| Internal.Sym.ar := 0; Internal.Sym.value := evil; Internal.Sym.morph := proper_eq evil |}
(sigma_add 1%positive
{| Internal.Sym.ar := 0; Internal.Sym.value := a; Internal.Sym.morph := proper_eq a |}
(sigma_empty Internal.Sym.pack)) in
let env_bin :=
sigma_get
{|
Internal.Bin.value := Z.add;
Internal.Bin.compat := reflexive_proper Z.add;
Internal.Bin.assoc := aac_Z_add_Assoc;
Internal.Bin.comm := Some aac_Z_add_Comm;
Internal.Bin.idem := None
|} (sigma_empty Internal.Bin.pack) in
let env_units :=
sigma_get
{|
Internal.u_value := 0;
Internal.u_desc := {| Internal.uf_idx := 1; Internal.uf_desc := aac_Z_add_0_Unit |} :: nil
|} (sigma_empty (Internal.unit_pack env_bin)) in
let tty := Internal.T env_sym in
let rsum := Internal.sum (e_sym:=env_sym) in
let rprd := Internal.prd (e_sym:=env_sym) in
let rsym := Internal.sym (e_sym:=env_sym) in
let vnil := Internal.vnil env_sym in
let vcons := Internal.vcons (e_sym:=env_sym) in
let eval := Internal.eval (e_sym:=env_sym) env_units in
let left :=
rsum 1%positive
(Utils.cons (rsym 1%positive vnil, 1%positive) (Utils.nil (rsym 2%positive vnil, 1%positive)))
in
let right :=
rsum 1%positive
(Utils.cons (rsym 2%positive vnil, 1%positive) (Utils.nil (rsym 1%positive vnil, 1%positive)))
in
Internal.decide env_units left right
(eq_refl : Internal.compare (Internal.norm env_units left) (Internal.norm env_units right) = Eq)
<: (* VM CAST HERE, inferred type "Internal.eval env_units left = Internal.eval env_units right" *)
a + evil = evil + a)
: forall a : Z, a + evil = evil + a
Using vm cast here seems just wrong, it should be a default cast (or even nothing since this is an argument of lift_reflexivity so the expected type is already known).
The eq_refl : Internal.compare ... = Eq
maybe should be vmcast, OTOH in cbv it will end up computing evil
(eg left
uses rsum
uses env_sym
uses evil
) so maybe not.
from aac-tactics.
from aac-tactics.
Related Issues (20)
- Please pick the version you prefer for Coq 8.15 in Coq Platform 2022.02 HOT 5
- Please pick the version you prefer for Coq 8.16 in Coq Platform 2022.09
- Transfer general Instances.v lemma to Stdlib HOT 3
- Please pick the version you prefer for Coq 8.17 in Coq Platform 2023.03
- Please pick the version you prefer for Coq 8.18 in Coq Platform 2023.10
- aac tactics don't handle goal selectors properly HOT 3
- Please pick the version you prefer for Coq 8.19 in Coq Platform 2024.01
- aac_congruence HOT 20
- [warnings] Please fix OCaml warnings
- Deprecated functions to interface with Coq-side of the plugin
- Ugly retyping-hack to solve universe-constrains HOT 4
- Deprecation of Pervasives in OCaml 4.08 and later HOT 1
- num is a dependency for Nix CI HOT 16
- Tag for Coq 8.12.0 HOT 4
- Please create a tag for the upcoming release of Coq 8.13 HOT 2
- Build fails with Nix on Coq 8.11 HOT 5
- Quantifying over Type HOT 1
- Please create a tag for the upcoming release of Coq 8.14 HOT 6
- Support for idempotent operations HOT 7
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from aac-tactics.