Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add constraints #13

Open
effectfully opened this issue Jul 16, 2019 · 3 comments
Open

Add constraints #13

effectfully opened this issue Jul 16, 2019 · 3 comments

Comments

@effectfully
Copy link
Owner

We want to be able to impose various invariants like "an external variable v can't be zero". Perhaps the best way to do this is to have a grammar like this:

@effectfully effectfully added enhancement New feature or request Test and removed Test labels Jul 16, 2019
@effectfully
Copy link
Owner Author

effectfully commented Aug 7, 2019

Partially implemented in d662c72. Currently we only support equality constraints over field elements. The grammar is

i = j; <expr>

There is a problem, though. Consider

if i == 0 then 0 = i; 1 else 1

Here we check whether i is equal to 0 and if it is, then require it to be equal to 0 and return 1. And if i was not 0, then we simply return 1 without requiring anything. This makes perfect sense in this repo, but not downstream, because we do not have any branching downstream. Thus, whenever we enter a local scope, we should ban using constraints there.

Or we can compile 0 = i as

0 = i OR False = (i == 0)

(where OR is the same as or, but defined over constraints rather than boolean values). So we invert the performed check and add it to the constraint to ensure that regardless of how control flow goes, the constraint will be satisfied. This is weird and I don't think we can define OR over constraints, so we just should ban constraints in local scopes.

@effectfully
Copy link
Owner Author

In fact, we can probably handle constraints in local scopes actually. So consider

if i == 0 then 0 = i; 1 else 1

We can represent the constraint as

let b = i == 0;
0 * b = i * b

So whenever i is equal to 0 we get 0 = i and 0 = 0 otherwise (which is trivially satisfied).

@effectfully
Copy link
Owner Author

Range constraints (and any boolean expressions in general) were added in #28.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant