Coder Social home page Coder Social logo

coq-community / autosubst Goto Github PK

View Code? Open in Web Editor NEW
49.0 11.0 12.0 913 KB

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

Makefile 1.96% Coq 59.49% TeX 38.55%
coq variable-binding debruijn-indices ssreflect mathcomp coq-ci

autosubst's People

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

autosubst's Issues

Nested types

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?

Why is `Ids_outer` necessary for `HSubstLemmas`?

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?

still maintained?

Hi,

are there plans to update this library and keep it alive or is it abandoned?

cheers
Philipp

Prevent HSubst ? ? instance from being resolved arbitrarily with Hint Mode.

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.

Build examples on CI

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

Doesn't build with Coq 8.6

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

[feature request] Support operation with assuming function extensionality

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

Problem with use of ssrfun

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

Bump max Coq version?

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?

question about languages with recursion

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?

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.