ACL2 TUTORIAL PDF
Tutorial Description. ACL2 (“A Computational Logic for Applicative Common Lisp”) is both a programming language in which you can model computer systems. ACL2’s logic is constructed on top of a real programming language, Common Lisp, and supports a wide variety of. David Hardin’s current a liation: Ajile Systems. PDF | We describe a tutorial that demonstrates the use of the ACL2 theorem prover. We have three goals: to enable a motivated reader to start.
|Published (Last):||19 October 2004|
|PDF File Size:||4.86 Mb|
|ePub File Size:||8.62 Mb|
|Price:||Free* [*Free Regsitration Required]|
Tutorial: reverse of reverse
The first case is when the argument, xsis empty or nil. Essentially, the REPL will execute any code you type in the text field on bottom the “prompt” and show the result in the log above. You may also enter definitions into the Interactions Window if you want to test something on the fly.
Try typing some math into the REPL now: Now, what if xs is not empty? You can see what kinds of values this generator returns by typing it in the REPL. As you hover over the proof bar, it will show you a preview of what’s going to be done; in particular, if you want to admit an expression, you have to first admit all the expressions above it.
Upgrading To upgrade Dracula, run the following at the command line: Dracula is available as a Racket package. You instantly see the result, which is 5 4 3 2 1. The reverse of an empty list is just an empty list: Dracula has been used to teach a first-year undergraduate logic course at Northeastern University. So we need to put 1 at the end of the reversed list.
Proof Pad: Tutorial (reverse)
And what we want for the whole list is list 5 4 3 2 1. To define and edit functions, use the Definitions window. Test zcl2 Now that we have a good working definition for reverse, we need to ack2 it to see that it works. When a test fails, it shows you which cases it failed on. Once tuorial admitted some code to the ACL2 logic which can take some time for complex functions or theoremsthe proof bar turns green next to the tutirial or forms that were admitted.
Keep reading below for installation instructions, and check out the links on the left for tutorials, examples, and bug report instructions. Alternately, feel free to inquire on the Racket User’s mailing listfile a bug report via DrRacket’s Help menu, or contact the author. The whole file so far is: Try changing the nil in the definition of rev above to something else, like 1. We can just use rev rest xs to reverse the rest of the list, but what do we do with first xs?
Define reverse reverse xs is a built-in function that takes a list and returns a list with all of the elements in the opposite order. We’ll talk more about the proof bar in the next section Definitions occur in an ordered way in the file; if you want to use the function “foo” within the function “bar”, you must put the definition of “foo” above the definition of “bar”.
We could write some more check-expect style tests, but they can only get us so far. You also need ACL2 version 3. We can automate this process to make sure that rev continues to match our expectations, even if we change or rewrite it. The name of the test is rev-rev-test. This has to do with how ACL2 processes events; the ACL2 “world” must be logically consistent after each and every event, so if you used “foo” before defining it, ACL2 might be accepting something that won’t actually work.
It generates values called xsusing the random-integer-list generator. This simply means that the code was executed by ACL2 without any problems. If it fails, it instead turns red, an ‘x’ is shown, tutlrial the details pane opens up to show you the error message you received.
This way, ACL2 will know to only concern itself with values that satisfy true-listp — values that are lists. Tutorizl this case, our test as written will fail. Admitted expressions will be highlighted green, and rejected expressions will be highlighted red. Thanks to Rex Page for the inspiration for this project, Dale Vaillancourt tjtorial the initial implementation, and Matthias Felleisen for his constant support.
DrRacket will then evaluate them next time you click Run. To do this, click on the proof bar next to the function you want to admit. This test has one generator. There are a couple of things to note at this point.
This adds the content of the Definitions Window to DrRacket’s tutoeial base”. They only test the types of values that you generate, and you might have a bug that impacts only a small subset of cases, which means the generated test cases are unlikely to expose the bug.
It would be even better if we could write a test that will check several types of lists tuhorial see that our function does what we want. For put-at-end x xswe can use append:.
— ACL2 Version
A doublecheck test has three parts: Try admitting your sum function from before. You can see that this makes the test fail. In order to correct this, we need to add a hypothesis to our property: Here’s a definition for ‘sum’ that you can either retype or copy and paste: Guards are restrictions on what values a function will take; in this case, endp xs expects a list, and we gave it a number.
You need DrRacket version 5. We don’t recommend this, but it is not an uncommon practice for Lisp development. A report on this course was presented at the ACL2 Workshop inand can be found here.