-
Notifications
You must be signed in to change notification settings - Fork 639
Add formal contracts #4682
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 formal contracts #4682
Conversation
1814feb
to
aa0b06f
Compare
it should "support contracts with a single operand" in { | ||
class Foo extends RawModule { | ||
val a = IO(Input(Bool())) | ||
val b = Contract(a) { x => |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
i am missing the basic user understanding of when something should go into the argument list of the Contract
or just be captured in the closure of the body.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Your actual hardware would go into the argument list. And the body then describes what your hardware does:
val z_impl = Instance(new MyFancyMultiplier(a, b))
val z = FormalContract(z_impl) { case z =>
EnsureProperty(z === a * b)
}
This will turn into a AssertProperty(z_impl === a * b)
to check that the multiplier works, and a separate val z = a * b
during formal verification.
* // Contract with single argument: "(a<<3)+a is equivalent to a*9". | ||
* // During formal verification, this is interpreted as: | ||
* // - "assert((a<<3)+a === a*9)" as a proof that the contract holds | ||
* // - "assume(b === a*9)" as a simplification of other proofs | ||
* val b = Contract((a<<3)+a) { b => |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
what is the user intuition for why you put the (a << 3) + a
term into the argument list for the Contract but the a*9
term is only used in the body of the contract?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
The example is a bit simplistic, but you would pass the actual implementation of your circuit, for example a radix-4 Booth multiplier, to the contract as an argument. The rationale is that you want the contract to act as a cutpoint, detaching the implementation and replacing it with a symbolic value during formal verification. You'd then use a simpler expression inside the contract to characterize your circuit, for example a * b
for your multiplier.
* // Contract with single argument: "(a<<3)+a is equivalent to a*9". | ||
* // During formal verification, this is interpreted as: | ||
* // - "assert((a<<3)+a === a*9)" as a proof that the contract holds | ||
* // - "assume(b === a*9)" as a simplification of other proofs | ||
* val b = Contract((a<<3)+a) { b => |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
kind of a nit but using the same variable b
both inside and as the return value of the contract is a little confusing. What is the point of the return value b
, how does one use that returned value?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
The body of the contract wants to talk about the result of the contract, which is either what you pass into the argument list (during synthesis and when checking that your hardware upholds the contract), or it's a symbolic value (during formal verification when you assume that the contract holds). There isn't really a good way to do this in Scala... so the contract passes the value it produces as a result to the body as well.
* // as a simplification of other proofs | ||
* val csa_s = p^q^r | ||
* val csa_c = (p&q | (p^q)&r) << 1 | ||
* val (u,v) = Contract(csa_c, csa_s) { case (u,v) => |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
again, what is the point of val (u, v)
that is returned here? what are they and what do you do with them?
/** Create a `contract` block with one or more arguments and results. | ||
* | ||
* Outside of verification uses, the arguments passed to the contract are | ||
* simply returned as contract results. During formal verification, the |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
what are "the contract results"? what does that mean? If I am passing the arguments anyway, why do i need the contract to return them again, couldn't i just use that myself like:
val a = ...
Contract(a) { b =>
assume (b == ...)
}
AssertProperty(a)
i guess if you didn't to have to give a named variable to a before you pass it to the contract, this can help
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This is due to the cutpoint behaviour of a contract during formal verification. When doing formal verification, the contract doesn't just forward its argument list to its results, but instead creates symbolic values as its results that are then constrained by the contract body. (Which is why the body takes arguments as well: it needs to constrain either the hardware, or the symbolic value, depending on which part you're verifying.)
Builder.forcedUserModule.withRegion(contract.region)(layer.elideBlocks(body(mapped))) | ||
mapped | ||
} | ||
} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
What about Scala 3? The code that can be shared should be in src/main/scala
. The macro is cool and I do think it's better, but if you just did the annoying thing and write the method for 1 to N arguments (e.g. DataProduct support for Tuples), then it would work for both Scala 2 and 3.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Good call. I've moved the common code into scala/chisel3
and added an explicit scala-3/chisel3
with the Scala 3 specific stuff.
1f33850
to
dffa141
Compare
dffa141
to
61b1a80
Compare
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Superficial nits. Land whenever you're ready.
*/ | ||
private[chisel3] trait ObjectFormalContractImpl { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This is fantastic Scaladoc. It's on a private trait, though. Where is it expected to show up? Is there some other place it should go?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
My hope was that this would show up on Scala 2 and Scala 3 object FormalContract
which extends ObjectFormalContractImpl
. Let me check how doc inheritance works for private base classes/traits -- otherwise I can always factor this into a public dummy base as we do for some of the source location macro stuff.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I just realized that this should actually be public. The apply
and mapped
functions are supposed to be available to users of the API. That should also fix the doc issue.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I just realized that this should actually be public
This should not be public--we don't want the Scala 2 / Scala 3 split visible in the public API.
The apply and mapped functions are supposed to be available to users of the API.
Even wit the trait package private, apply
and mapped
are public on any classes/objects that mix the trait in so no problem there.
That should also fix the doc issue.
That won't really fix the doc issue because users would still have to click through to the trait to see the doc which isn't what we want, we want it to show up on the object FormalContract
.
I think you need to put /** @inheritdoc */
on each object FormalContract
to make inheritance work. Now if that can't work from a package private trait, then you could move the Scala doc to a public trait that is nothing but the doc, but I think the implementations of mapped
and apply
should stick around on a private trait.
All of this being said
I'd like to invert the public/private relationship such that the public classes and objects lives in src/main/scala
and only package private traits that provide the public methods using macros live in src/main/scala-2
and src/main/scala-3
. So here's what I think you should really do.
Create a new package private trait (probably called FormalContract$VirtualMethods
1) in this file (core/src/main/scala/chisel3/FormalContractImpl.scala
) that just defines the virtual method mapped
. Change the code in src/main/scala-2
and src/main/scala-3
to be package private traits (probably called FormalContract$Intf
) that extend FormalContract$VirtualMethods
and self-typed on FormalContract.type
2 but still provide the public methods that use macros. Then back in this file, make object FormalContract extends FormalContract$Intf
and you'll just need the ScalaDoc there. It's more clear than the old pattern IMO, I need to roll out this new approach to the rest of the code base.
Footnotes
-
The
$
is because in Scala, an object's underlying type is named with a trailing$
in Java bytecode. This is mostly hidden in the Scala API but leaks at times in errors. @seldridge and I discussed that the patternObjectModuleImpl
is confusing that it's referring toobject module
and thatModule$Impl
would be more clear so that's the new style I'm proposing. ↩ -
FormalContract.type
is technically the type forobject FormalContract
, but as stated above, it desugars/lowers toFormalContract$
in Java bytecode. ↩
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
A lot of this FormalContractIntf
vs. FormalContract$Intf
may feel silly since there's no class FormalContract
, but elsewhere in the code base we have classes and companion objects so I want to define a single style that works across the board.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I've laid this out more explicitly and with an example in #4768
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Really nice. I've moved the contracts to this new pattern.
It would be super cool to add some mdoc-based documentation for the contract + hierarchical formal example! |
Add the `Contract` API which allows users to express the pre and post-conditions of a piece of hardware. These can be used during formal verification to prove that the hardware upholds the conditions laid out in the contract. Additionally, contracts may be used to implement a divide-and-conquer strategy to simplify larger proofs since they act like a cutpoint and an assume-guarantee substitution.
29f9e86
to
5cda8c8
Compare
Thanks for the reviews and great suggestions. Going to land this now. |
Add the
Contract
API which allows users to express the pre and post-conditions of a piece of hardware. These can be used during formal verification to prove that the hardware upholds the conditions laid out in the contract. Additionally, contracts may be used to implement a divide-and-conquer strategy to simplify larger proofs since they act like a cutpoint and an assume-guarantee substitution.Contributor Checklist
docs/src
?Type of Improvement
Desired Merge Strategy
Release Notes
Reviewer Checklist (only modified by reviewer)
3.6.x
,5.x
, or6.x
depending on impact, API modification or big change:7.0
)?Enable auto-merge (squash)
and clean up the commit message.Create a merge commit
.