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 January 2015|
|PDF File Size:||16.78 Mb|
|ePub File Size:||3.8 Mb|
|Price:||Free* [*Free Regsitration Required]|
This automatic admission occurs in: This way, ACL2 will know to only concern itself with values that satisfy true-listp — values that are lists. Now, what if xs is not empty? Acknowledgements Thanks to Rex Page for the inspiration for this project, Dale Vaillancourt for the initial implementation, and Matthias Felleisen for his constant support.
Guards are restrictions on what values a function will take; in this case, endp xs expects a list, and we gave it a number. Finally, we have the body: The name of the test is rev-rev-test. After we split it up into two parts, 1 and list 2 3 4 5we can reverse the list part to get list 5 4 3 2. This adds the content of the Definitions Window to DrRacket’s “knowledge base”. This page provides instructions for downloading the software, working in Racket’s ACL2 language, writing interactive graphical programs, and for reporting bugs.
Once you’ve admitted some code to the ACL2 logic which can take some time for complex functions or theoremsthe proof bar turns green next to the form or forms that were admitted. Test reverse Now that we have a good working definition for reverse, we need to test it to see that it works.
To tutodial and edit functions, use the Definitions window. DrRacket will then evaluate them next time you click Run.
We can just use rev rest xs to reverse the rest of the list, but what tuyorial we do with first xs? Download and install from the Racket site. The definitions area is where you write your functions, theorems, and other state-altering expressions.
Keep reading below for installation instructions, and check out the links on the left for tutorials, examples, and bug report instructions.
You may also copy and paste such expressions into the Definitions Window. To install Dracula using this utility, execute: To run your program, tutorkal on Run. They only test the types rutorial values that you generate, and you ac2 have ttutorial bug that impacts only a small subset of cases, which means the generated test cases are unlikely to expose the bug.
Try typing some math into the REPL now: In this case, it fails all cases, but it might help you to diagnose the problem if only some of the cases fail too. Uninstalling To uninstall Dracula, run the following at the command line: To do this, click on the proof bar next to the function you want to admit. The reverse of an empty list is just an empty list:.
You also need ACL2 version 3. The whole file so far is: Here’s a definition for ‘sum’ that you can either retype or copy and paste: If a single case fails, the test fails. You instantly see the result, which is 5 4 3 2 1.
A test passes when the two arguments to check-expect evaluate to the same thing in this case, the list 5 4 3 2 1. This test has one generator. In order to correct this, we need to add a hypothesis to our property: You can read more about ACL2’s two modes herethough this is strictly optional reading; you don’t need to have an intimate understanding of this for Proof Pad, since it abstracts these parts away for you. When a test fails, it shows you which cases it failed on.
Now you can evaluate expressions in the Interactions Window that refer to the definitions in the Definitions Window.
In this case, our test as written will fail. It will run, and if it passes, a green bar will appear to the left of the test. Proof bar The proof bar is the normally white bar to the left of the definitions panel that allows you to view and manipulate the status of ACL2 with respect to your code.
Proof Pad: Tutorial (reverse)
If you don’t, see the troubleshooting page. Dracula is available as a Racket package. The simplest automatic test provided by Proof Pad is check-expect. If the automatic admission succeeds, the proof tutkrial turns light green next to the admitted code. Upgrading To upgrade Dracula, run the following at the command line: It generates values called xsusing the random-integer-list generator.
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 axl2 that won’t actually work.
Running Dracula Start DrRacket. If it fails, it instead turns red, an ‘x’ is shown, and the details pane opens up to show you the error message you received. For put-at-end x xswe can use append:.
You will probably want to admit these functions to ACL2’s: We acp2 automate this process to make sure that rev continues to match our expectations, even if we change or rewrite it. One property we can test with DoubleCheck is that reversing a list twice gives you the same list you started with.