Code Monkey home page Code Monkey logo

Comments (7)

palmskog avatar palmskog commented on July 18, 2024

@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.

MSoegtropIMC avatar MSoegtropIMC commented on July 18, 2024

@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.

palmskog avatar palmskog commented on July 18, 2024

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.

MSoegtropIMC avatar MSoegtropIMC commented on July 18, 2024

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.

MSoegtropIMC avatar MSoegtropIMC commented on July 18, 2024

@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:

let decision_thm = mkApp (Coq.get_efresh Theory.Stubs.decide_thm,

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.

SkySkimmer avatar SkySkimmer commented on July 18, 2024

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.

SkySkimmer avatar SkySkimmer commented on July 18, 2024

#134

from aac-tactics.

Related Issues (20)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo 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.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.