Git Product home page Git Product logo

arend's Introduction

Arend proof assistant

JetBrains offical project Actions Status Gitter

Arend is a theorem prover and a programming language based on Homotopy Type Theory.

Usage

As a binary

You can find release version of Arend binary (a jar file named "Arend.jar") in the release page. The Arend jar can be used to typecheck a library:

$ java -jar Arend.jar [path-to-library]

You can also start a REPL:

$ java -jar Arend.jar -i

If you start the REPL at the root directory of a library, the REPL will load the library. For more information and usage about command line usage of Arend, please refer to --help:

$ java -jar Arend.jar -h

As a library

Arend is under active development, so you may expect to depend your project on a development version of Arend, either a certain git revision or the SNAPSHOT version. This is possible via JitPack, simply add this to your build.gradle:

repositories {
    maven { url 'https://jitpack.io' }
}
dependencies {
    // The version of Arend -- can be a short revision, "[branch]-SNAPSHOT",
    // "-SNAPSHOT", or a tag (or a release, like "v1.4.0").
    String arendVersion = "master-SNAPSHOT"
    // Open API for writing Arend extensions
    implementation "com.github.JetBrains.Arend:api:$arendVersion"
    // The generated ANTLR parser
    implementation "com.github.JetBrains.Arend:parser:$arendVersion"
    // The generated protobuf classes
    implementation "com.github.JetBrains.Arend:proto:$arendVersion"
    // The main compiler
    implementation "com.github.JetBrains.Arend:base:$arendVersion"
}

In case you prefer Gradle Kotlin DSL, use the following syntax in your build.gradle.kts:

repositories {
    maven("https://jitpack.io")
}
dependencies {
    // The version of Arend
    val arendVersion = "master-SNAPSHOT"
    implementation("com.github.JetBrains.Arend:api:$arendVersion")
    implementation("com.github.JetBrains.Arend:parser:$arendVersion")
    implementation("com.github.JetBrains.Arend:proto:$arendVersion")
    implementation("com.github.JetBrains.Arend:base:$arendVersion")
}

arend's People

Contributors

akuklev avatar i-walker avatar ice1000 avatar kirelagin avatar knisht avatar marat-rkh avatar part-xx avatar pschuprikov avatar solomatov avatar sxhya avatar valis avatar xamgore avatar

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  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  avatar  avatar  avatar  avatar

Watchers

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

arend's Issues

Same goal printed twice

\static \data Lol (xs : List Nat)
    | Lol xs => lol Nat

\static \function
test-case : Lol nil => lol (\case (0 =? 0)
              | inl x-ne-x' => {?}
              | inr x-eq-x' => {?})

First goal appears twice in error messages:

[ERROR] test.Data.List.In.test-case: 110:32: Goal
    Expected type: Nat
    Context:
        x-ne-x' : (~~) (0 = 0)
[ERROR] test.Data.List.In.test-case: 110:32: Goal
    Expected type: Nat
    Context:
        caseA0 : Either ((~~) (0 = 0)) (0 = 0)
        x-ne-x' : (~~) (0 = 0)
[ERROR] test.Data.List.In.test-case: 111:32: Goal
    Expected type: Nat
    Context:
        caseA0 : Either ((~~) (0 = 0)) (0 = 0)
        x-eq-x' : 0 = 0

Interestingly, goal is printed only once if I change definition to

\static \function
test-case : Nat => suc (\case (0 =? 0)
              | inl x-ne-x' => {?}
              | inr x-eq-x' => {?})

Fix normalization

Normalize visitor is too messy. Clean it up, remove eta normailzation. Make it into an interface maybe.

Error reporting works differently in different modules

Put following code to two different modules: Logic and Data.Nat.

\static \function
test-unit : Unit => zero

In case of Data.Nat error is reported correctly:

[ERROR] 62:21: Type mismatch:
    Expected type: Unit
      Actual type: Nat
    In expression: 0

But in Logic there is no error at all.

Exception in \case

Следующий код бросает IllegalStateException.

\open Data.Bool

\static \function tp : \Pi (x : Bool) -> \Type0 => \lam x => \case x
| true => Bool
| false => Nat

\static \function f (x : Bool) : tp x <= \elim x
| true => x
| false => zero

Typechecking of datatypes with several occurences of same var in clause patterns

Consider following "second index is a successor of first index" predicate.

\static \data Next Nat Nat
    | Next n (suc n) => next

\static \function
next-test : Next (suc zero) (suc zero) => next

Obviously, no term with type Next 1 1 exists but typechecker accepts current definition as correct.

For a more complex example you can check this "list contains element" predicate which also typechecks without errors: here successfully fills the goal with type ListIn A x (x' :: xs').

\open Data.List
\close Data.List (concat)

\static \data ListIn (A : \Type0) (x : A) (xs : List A)
    | ListIn A x ((::) x xs) => here
    | ListIn A x ((::) y xs) => there (y : A) (p : ListIn A x xs)

\open Logic
\open Data.Either

\static \function
list-in-concat (A : \Type0) (xs ys : List A) (x : A) (in : ListIn A x (xs ++ ys))
               : (ListIn A x xs) || (ListIn A x ys) <= \elim xs
    | nil => inr in
    | (::) x' xs' => inl here

No error is reported in typeCheckApps

\static \function
test (x y : Nat) : y = 0 <= \elim x, y
| _, zero => idp
| zero, suc y' => test x y'
| suc x', suc y' => test x y'

\static \function
zero-is-one : 1 = 0 => test 0 1

Bonus: put suc (test x y'), (test x y) @ zero, test x @ suc or (I think) any expression with test x as subexpr instead of test x y' in either of two last cases.

Get rid of resolved names

Replace resolved names in Abstract.DefCallExpression and other Abstract.* classes with Abstract.Definition or some parent of it.

Issues with dynamic name resolving

Dynamic name resolving (during type-checking) has its downsides:

  • Poor UX with projectional editors: some names are not resolved by the editor.
  • Interfers with implicit parameters.

We currently have the following language constructions that result in dynamic resolving:

  • a.f field call
  • constructors in elim patterns (?)

There are three options:

  1. Do nothing.
  2. Drop those constructions altogether.
  3. Alter name resolution rules by requiring fields, constructors, etc. to be in scope.

Module Data.List.In is ignored

(see code in JetBrains/arend-lib#1)

File Data/List/In.vc exists in filesystem but ignored by compiler:

[OK] test.Paths
[OK] test.Hlevel
[OK] test.Data.Unit
[OK] test.Data.Empty
[OK] test.Data.Bool
[OK] test.Data.Either
[OK] test.Data.Maybe
[OK] test.Combinators
[OK] test.Data.Nat.Base
[OK] test.Data.List
[OK] test.Logic
[OK] test.Relation
[OK] test.Data.Nat.Properties
[OK] test.Data.Nat.Compare
[OK] test.Data.Vector
[OK] test.Data.Fin
[OK] test.Data.List.Properties
[OK] test.Data.Fin.Properties
[OK] test.Examples
[OK] test.Fac
[OK] test.Algebra.Semigroup

Better inference of implicit arguments

When expected an expression of a pi type or of a sigma type, but expected type depends on other inference variables, generate new inference variables ?A and ?B, and add equation expectedType = Pi ?A ?B (or Sigma ?A ?B)

De Brujin indices are wrong when processing `case` statement

\static \function
diff (a b : Nat) : Nat => \case (a =<? b)
  | inl gt => a - b
  | inr leq => b - a

\static \function
diff-prop (a b : Nat) : diff a b = (a - b) + (b - a) => \case (a =<? b)
  | inl gt => {?}
  | inr leq => {?}

Gives

[ERROR] Data.Nat.Gcd.diff-prop: 55:15: Goal
    Expected type: (
    \let | caseF (caseA0 : Either ((~~) (b =< gt)) (b =< gt)) <= \elim caseA0
             | inl gt => b - gt
             | inr leq => gt - b
             ;
    \in caseF (b - gt =? 0) = b - gt + (gt - b)
    Context:
        a : Nat
        b : Nat
        gt : (~~) (a =< b)
        caseF : \Pi (caseA0 : Either ((~~) (a =< b)) (a =< b)) -> Nat
[ERROR] Data.Nat.Gcd.diff-prop: 56:16: Goal
    Expected type: (
    \let | caseF (caseA0 : Either ((~~) (b =< leq)) (b =< leq)) <= \elim caseA0
             | inl gt => b - leq
             | inr leq => leq - b
             ;
    \in caseF (b - leq =? 0) = b - leq + (leq - b)
    Context:
        a : Nat
        b : Nat
        leq : a =< b
        caseF : \Pi (caseA0 : Either ((~~) (a =< b)) (a =< b)) -> Nat

where in case expansion all occurrences of a are substituted with b, and all occurrences of b are substituted with gt (or leq). (a, b) and (b, gt) are neighbours in context so I thing de Brujin indices are computed incorrectly.

Better error messages

Add to error messages an information about free variables (both inference and ordinary) of expressions that appear in the message.

Normalization changes type

  @Test
  public void testEquivSymm2() {
    NamespaceMember member = typeCheckClass("" +
            "\\static \\function pmap {A B : \\Type0} (f : A -> B) {a a' : A} (p : a = a')\n" +
            "    => path (\\lam i => f (p @ i))\n" +
            "\\static \\function transport {A : \\Type0} (B : A -> \\Type0) {a a' : A} (p : a = a') (b : B a)\n" +
            "    <= coe (\\lam i => B (p @ i)) b right\n" +
            "\\static \\function concat {A : I -> \\Type0} {a : A left} {a' a'' : A right} (p : Path A a a') (q : a' = a'')\n" +
            "    <= transport (Path A a) q p\n" +
            "\\static \\function \\infixr 9\n" +
            "(*>) {A : \\Type0} {a a' a'' : A} (p : a = a') (q : a' = a'')\n" +
            "    <= concat p q\n" +
            "\\static \\function id {X1 : \\Type0} (x : X1) => x\n" +
            "\\static \\function \\infixr 1\n" +
            "($) {X2 Y : \\Type0} (f : X2 -> Y) (x : X2) => f x\n" +
            "\\static \\function \\infixr 8\n" +
            "o {X3 Y Z : \\Type0} (g : Y -> Z) (f : X3 -> Y) (x : X3) => g $ f x\n" +
            "\\static \\function \\infix 2\n" +
            "(~) {A B : \\Type0} (f : A -> B) (g : A -> B) <= \\Pi (x : A) -> f x = g x\n" +
            "\\static \\function linv {A B : \\Type0} (f : A -> B) <= \\Sigma (g : B -> A) (g `o` f ~ id)\n" +
            "\\static \\function rinv {A B : \\Type0} (f : A -> B) <= \\Sigma (g : B -> A) (f `o` g ~ id)\n" +
            "\\static \\function isequiv {A B : \\Type0} (f : A -> B) <= \\Sigma (linv f) (rinv f)\n" +
            "\\static \\function \\infix 2\n" +
            "(=~=) (A : \\Type0) (B : \\Type0) <= \\Sigma (f : A -> B) (isequiv f)\n" +
            "\\static \\function qinv {A B : \\Type0} (f : A -> B) <= \\Sigma (g : B -> A) (g `o` f ~ id) (f `o` g ~ id)\n" +
            "\\static \\function equiv-to-qinv {A B : \\Type0} (f : A -> B) (x : isequiv f) : qinv f => \n" +
            "  (x.1.1 `o` f `o` x.2.1, \n" +
            "   \\lam x' => pmap x.1.1 (x.2.2 (f x')) *> x.1.2 x',\n" +
            "   \\lam x' => pmap f (x.1.2 (x.2.1 x')) *> x.2.2 x'\n" +
            "  )\n" +
            "\\static \\function equiv-symm-2 {A B : \\Type0} (e : A =~= B) : B -> A =>\n" +
            "  (equiv-to-qinv e.1 e.2).1 \n"
    );
    FunctionDefinition equivSymm2 = (FunctionDefinition) member.namespace.getMember("equiv-symm-2").definition;
    ProjExpression e = (ProjExpression) ((LeafElimTreeNode)equivSymm2.getElimTree()).getExpression();
    Expression type1 = e.getType();
    Expression type2 = e.normalize(NormalizeVisitor.Mode.NF).getType();
    Assert.assertEquals(type1, type2);
  }

Everything here, except equiv-symm-2 is copy-pasted from standard library. equiv-symm-2 is a subexpression of equiv-symm from standard library.

This is correct code and it typechecks normally. But when we try to normalize body of equiv-symm-2, it changes type from B -> A to X3 -> A. X3 here came from function composition o. Same issue occurs even with WHNF normalization strategy.

Termination check failed on decreasing second arg with increasing first

The following code fails to termination check:

\static \function
plus' (x y : Nat) : Nat <= \elim y
  | zero => x
  | suc y' => plus' (suc x) y'

However, if we remove suc from first argument, or swap arguments, termination checker accepts the definitions:

\static \function
plus'' (x y : Nat) : Nat <= \elim y
  | zero => x
  | suc y' => suc (plus'' x y')

\static \function
plus''' (x y : Nat) : Nat <= \elim x
  | zero => y
  | suc x' => plus''' x' (suc y)

Typechecking of case expressions

Attempting to typecheck the following (flawless) code piece

\data Geq (x y : Nat)
| Geq m zero => EqBase 
| Geq (suc n) (suc m) => EqSuc (p : Geq n m)

\function f (x y : Nat) (p : Geq x y) : Nat <=
  \case x, y, p
    | m, zero, EqBase <= zero 
    | zero, suc _, x <= \elim x ;
    | suc _, suc _, EqSuc q <= suc zero

returns the following typechecking errors

Constructor is not appropriate, failed to match data type parameters.
Expected (zero), got <4> in (EqBase)
Constructor is not appropriate, failed to match data type parameters. 
Expected (suc n), got <6> in (EqSuc q)

These errors disappear if "case" is replaced by "elim"

ArrayIndexOutOfBoundsException during pattern expansion

\static \data \infix 4
(=<) (n m : Nat)
  | (=<) zero m => le_z
  | (=<) (suc n) (suc m) => le_ss (n =< m)

\static \function
leq-trans {n m k : Nat} (nm : n =< m) (mk : m =< k) : n =< k <= \elim n, nm, m
  | zero, le_z, _ => {?}
  | suc n', le_ss nm', suc m' => {?}
Caused by: java.lang.ArrayIndexOutOfBoundsException: -1
    at java.util.ArrayList.elementData(ArrayList.java:418)
    at java.util.ArrayList.get(ArrayList.java:431)
    at com.jetbrains.jetpad.vclang.term.expr.visitor.CheckTypeVisitor.expandPatternOn(CheckTypeVisitor.java:1303)
    at com.jetbrains.jetpad.vclang.term.expr.visitor.CheckTypeVisitor.visitElim(CheckTypeVisitor.java:1385)
    at com.jetbrains.jetpad.vclang.term.expr.visitor.CheckTypeVisitor.visitElim(CheckTypeVisitor.java:30)
    at com.jetbrains.jetpad.vclang.term.Concrete$ElimExpression.accept(Concrete.java:656)
    at com.jetbrains.jetpad.vclang.term.expr.visitor.CheckTypeVisitor.typeCheck(CheckTypeVisitor.java:141)
    at com.jetbrains.jetpad.vclang.term.expr.visitor.CheckTypeVisitor.checkType(CheckTypeVisitor.java:542)
    at com.jetbrains.jetpad.vclang.term.definition.visitor.DefinitionCheckTypeVisitor.visitFunction(DefinitionCheckTypeVisitor.java:239)
    at com.jetbrains.jetpad.vclang.term.definition.visitor.DefinitionCheckTypeVisitor.visitFunction(DefinitionCheckTypeVisitor.java:33)
    at com.jetbrains.jetpad.vclang.term.Concrete$FunctionDefinition.accept(Concrete.java:875)
    at com.jetbrains.jetpad.vclang.term.definition.visitor.DefinitionCheckTypeVisitor.typeCheck(DefinitionCheckTypeVisitor.java:57)
    at com.jetbrains.jetpad.vclang.typechecking.TypecheckingOrdering.typecheck(TypecheckingOrdering.java:117)
    at com.jetbrains.jetpad.vclang.typechecking.TypecheckingOrdering.typecheck(TypecheckingOrdering.java:134)
    at com.jetbrains.jetpad.vclang.ConsoleMain.main(ConsoleMain.java:119)
    ... 6 more

`InvocationTargetException` when undefined data name coincide with module's name part

Currently library has file named Data/Vector.vc which defines Vector datatype. Create file Data/Vec/Properties.vc with following content:

\open Data.Vector

\static \function
append-vnil-right {n : Nat} {A : \Type0} (xs : Vec n A) 
                  : xs +^ vnil = xs => {?}

Here, I mistyped Vector as Vec and got an exception:

    at com.jetbrains.jetpad.vclang.term.expr.ExpressionFactory.DefCall(ExpressionFactory.java:55)
    at com.jetbrains.jetpad.vclang.typechecking.TypeCheckingDefCall.typeCheckDefCall(TypeCheckingDefCall.java:55)
    at com.jetbrains.jetpad.vclang.term.expr.visitor.CheckTypeVisitor.typeCheckDefCall(CheckTypeVisitor.java:563)
    at com.jetbrains.jetpad.vclang.term.expr.visitor.CheckTypeVisitor.visitDefCall(CheckTypeVisitor.java:569)
    at com.jetbrains.jetpad.vclang.term.expr.visitor.CheckTypeVisitor.visitDefCall(CheckTypeVisitor.java:30)
    at com.jetbrains.jetpad.vclang.term.Concrete$DefCallExpression.accept(Concrete.java:331)
    at com.jetbrains.jetpad.vclang.term.expr.visitor.CheckTypeVisitor.typeCheck(CheckTypeVisitor.java:147)
    at com.jetbrains.jetpad.vclang.term.expr.visitor.CheckTypeVisitor.typeCheckFunctionApps(CheckTypeVisitor.java:281)
    at com.jetbrains.jetpad.vclang.term.expr.visitor.CheckTypeVisitor.visitApp(CheckTypeVisitor.java:559)
    at com.jetbrains.jetpad.vclang.term.expr.visitor.CheckTypeVisitor.visitApp(CheckTypeVisitor.java:30)
    at com.jetbrains.jetpad.vclang.term.Concrete$AppExpression.accept(Concrete.java:202)
    at com.jetbrains.jetpad.vclang.term.expr.visitor.CheckTypeVisitor.typeCheck(CheckTypeVisitor.java:147)
    at com.jetbrains.jetpad.vclang.term.expr.visitor.CheckTypeVisitor.checkType(CheckTypeVisitor.java:548)
    at com.jetbrains.jetpad.vclang.term.definition.visitor.DefinitionCheckTypeVisitor.visitFunction(DefinitionCheckTypeVisitor.java:179)
    at com.jetbrains.jetpad.vclang.term.definition.visitor.DefinitionCheckTypeVisitor.visitFunction(DefinitionCheckTypeVisitor.java:33)
    at com.jetbrains.jetpad.vclang.term.Concrete$FunctionDefinition.accept(Concrete.java:880)
    at com.jetbrains.jetpad.vclang.term.definition.visitor.DefinitionCheckTypeVisitor.typeCheck(DefinitionCheckTypeVisitor.java:57)
    at com.jetbrains.jetpad.vclang.typechecking.TypecheckingOrdering.typecheck(TypecheckingOrdering.java:117)
    at com.jetbrains.jetpad.vclang.typechecking.TypecheckingOrdering.typecheck(TypecheckingOrdering.java:134)
    at com.jetbrains.jetpad.vclang.ConsoleMain.main(ConsoleMain.java:119)
    ... 6 more

If you change Vec here with other word that is also non-datatype (Ve, Vect, XXX,...) error will not arise, but for other module parts (Algebra, Fac, ...) it will.

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.