coq-community / autosubst Goto Github PK
View Code? Open in Web Editor NEWAutomation for de Bruijn syntax and substitution in Coq [maintainers=@RalfJung,@co-dan]
Home Page: https://www.ps.uni-saarland.de/autosubst
License: MIT License
Automation for de Bruijn syntax and substitution in Coq [maintainers=@RalfJung,@co-dan]
Home Page: https://www.ps.uni-saarland.de/autosubst
License: MIT License
I'm trying to formalize first-order logic in Coq using Autosubst, and I'm running into a difficulty. Function symbols have a fixed arity, so I'm doing something like this:
Inductive term :=
| idx (v : var)
| app {n : arity} (f : function_symbol n) (a : vec term n).
Unfortunately, Autosubst now doesn't substitute in arguments of an application, presumably because of the nested recursion. I've also tried using a mutually inductive type; that didn't work either. How should I approach this?
I'm using HSubst
in a case where the outer type doesn't have variables of its own (first-order logic; terms are a separate type, variables are bound by quantifiers in the props). I want to derive HSubstLemmas
, but it depends on having an Ids
instance for the outer type, even though that's impossible here. I glanced at the source and I don't see any obvious reason why it has that dependency... Can it be removed?
Hi,
are there plans to update this library and keep it alive or is it abandoned?
cheers
Philipp
Instance search for HSubst vl ?X
picks an arbitrary solution instead of giving an ambiguity error, and that is only desirable for languages with one HSubst instance. So it's easy to accidentally declare lemmas for the wrong types and notice later.
This is a matter of design choice, but using Hint Mode
seems fairly common practice among typeclass users.
Below's an excerpt from some development of mine:
Instance Subst_vl : Subst vl := vl_subst.
Instance HSubst_tm : HSubst vl tm := tm_hsubst.
Instance HSubst_ty : HSubst vl ty := ty_hsubst.
Goal ∀ s x, x.|[s] = x.
(* x is inferred to have type [ty] because that was the last declared instance — swapping the instances changes the type. *)
Abort.
Hint Mode HSubst - +: typeclass_instances.
(* [Hint Mode HSubst - !: typeclass_instances.] would also work in this test, but I can't think of a case where that's preferable. *)
Fail Goal ∀ s x , x.|[s] = x.
Goal ∀ s (x: ty) , x.|[s] = x. Abort.
I'm aware the library is not actively developed, but it is actively used, so this might be useful to other readers.
@palmskog how can we make CI run make examples-plain
and not just make
? Would be nice to make sure that these examples keep working.
COQC Autosubst_MMap.v
File "./Autosubst_MMap.v", line 26, characters 0-37:
Error: Some argument names are duplicated: H
Full log:
make -C theories
make[1]: Entering directory 'src/autosubst-1.6/theories'
coq_makefile -R . Autosubst Autosubst_Derive.v Autosubst.v Autosubst_MMapInstances.v Autosubst_Classes.v Autosubst_Basics.v Autosubst_Lemmas.v Autosubst_MMap.v Autosubst_Tactics.v -o Makefile.coq
make -f Makefile.coq all
make[2]: Entering directory 'src/autosubst-1.6/theories'
COQDEP Autosubst_Lemmas.v
COQDEP Autosubst_Tactics.v
COQDEP Autosubst_MMap.v
COQDEP Autosubst_Classes.v
COQDEP Autosubst_Basics.v
COQDEP Autosubst_MMapInstances.v
COQDEP Autosubst.v
COQDEP Autosubst_Derive.v
COQC Autosubst_Basics.v
File "./Autosubst_Basics.v", line 76, characters 27-40:
Warning: appcontext is deprecated and will be removed in a future version
[deprecated-appcontext,deprecated]
File "./Autosubst_Basics.v", line 78, characters 29-42:
Warning: appcontext is deprecated and will be removed in a future version
[deprecated-appcontext,deprecated]
File "./Autosubst_Basics.v", line 119, characters 11-27:
Warning: appcontext is deprecated and will be removed in a future version
[deprecated-appcontext,deprecated]
fun (f : var -> var) (sigma : var -> list var) =>
nil .: nil .: f >>> f >>> nil .: nil .: f >>> f >>> nil .: nil .: sigma
: (var -> var) -> (var -> list var) -> var -> list var
File "./Autosubst_Basics.v", line 272, characters 10-26:
Warning: appcontext is deprecated and will be removed in a future version
[deprecated-appcontext,deprecated]
File "./Autosubst_Basics.v", line 276, characters 10-43:
Warning: appcontext is deprecated and will be removed in a future version
[deprecated-appcontext,deprecated]
File "./Autosubst_Basics.v", line 290, characters 6-22:
Warning: appcontext is deprecated and will be removed in a future version
[deprecated-appcontext,deprecated]
File "./Autosubst_Basics.v", line 294, characters 6-39:
Warning: appcontext is deprecated and will be removed in a future version
[deprecated-appcontext,deprecated]
COQC Autosubst_MMap.v
File "./Autosubst_MMap.v", line 26, characters 0-37:
Error: Some argument names are duplicated: H
make[2]: *** [Makefile.coq:272: Autosubst_MMap.vo] Error 1
make[2]: Leaving directory 'src/autosubst-1.6/theories'
make[1]: *** [Makefile:8: all] Error 2
make[1]: Leaving directory 'src/autosubst-1.6/theories'
make: *** [Makefile:21: lib] Error 2
it would be great if autosubst was available on Coq's opam at https://github.com/coq/opam-coq-archive/. That would make it much easier projects already using opam to also depend on autosubst.
I can help writing the opam file, if you want.
Right now, function extensionality as pulled in by asimpl
is the only axiom we use in our entire Coq development.
Considering that this is ultimately about proving equality of source terms, which have decidable equality, function extensionality should not be necessary here. It would be nice if the axiom could be avoided :)
I get:
Error: Notation "_ .[ _ ]" is already defined at level 2
with arguments constr at level 2, constr at level 200
while it is now required to be at level 2 with arguments constr
at level 2, constr Unknown level.
while compiling line:
From mathcomp Require Import ssreflect ssrfun ssrbool eqtype ssrnat seq.
from ./AutosubstSsr.v
I temporarily solved it by explicitly naming ssrfun.omap but this makes me rename the rest of the examples.
I'm using Coq 8.11.1
According to the .opam
file, the 1.7 release of Autosubst only supports Coq < 8.16 or dev. Can the max version requirement be bumped?
Is it possible to use this library to work with languages that support general recursive functions?
I want to define a function as
| Fun (s : {bind term in {bind term}})
such that during the beta reduction step, this function is first substituted in for its "first" argument.
When trying to prove that substitution respects parallel reduction, I'm left with a goal
s1, s2, t1, t2, u : term
A : forall sigma : var -> term, pstep s1.[sigma] s2.[sigma]
B : forall sigma : var -> term, pstep t1.[sigma] t2.[sigma]
sigma : var -> term
============================
s2.[Fun s2/].[t2/].[sigma] =
s2.[up sigma].[Fun s2.[up sigma]/].[t2.[sigma]/]
that basically tries to commute 3 substitutions. Autosubst tactic no longer work. Is there anyway to work around this?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.