Links table
1 Introduction
2 dance links
3 Rust programming language
4 RAC: Hardware/Software Widely Shared Assurance
Rust 5 and RAR
5.1 Constrained Algorithmic Rust
6 Dancing in Rust links and 6.1 definitions
6.2 Translation to ACL2
6.3 Theories of dance connections
7 related works
8 Conclusion
9 Acknowledgments and references
“Dancing links” implies an improved implementation of a double-linked circular list data structure that provides quick removal and restoration of list items. Dancing Links optimization is mainly used in fast algorithms for finding exact covers, and was popularized by Knuth in Volume 4B of his seminal series The Art of Computer Programming. We describe the implementation of the Dancing Links optimization in the Rust programming language, as well as its formal verification using the ACL2 theorem prover. Rust has gained a lot of support in the past few years as a modern, memory-safe successor to C/C++ at companies like Amazon, Google, and Microsoft, and is integrated into both the Linux and Windows operating system kernels. Our interest in Rust stems from its potential as a common hardware/software assurance language, with application to critical systems. We have designed a subset of Rust, inspired by the Rusinov Restricted Algorithm C (RAC), which we have innovatively named Restricted Algorithmic Rust, or RAR. In previous work, we described our initial implementation of the RAR toolchain, where we simply port the RAR source to RAC. In doing so, we leverage a number of existing hardware/software co-assurance tools with a minimal investment of time and effort. In this paper, we describe the RAR Rust subset, describe our improved prototype of the RAR toolchain, and detail the design and verification of a doubly linked circular list data structure using the Dancing Links optimization in RAR, with full proofs of functional correctness accomplished using the ACL2 theorem prover.
1 Introduction
Exactly the problem with the cover [17]in its simplest form, attempts to find, for an n × m matrix with binary elements, all subsets of the rows of the matrix such that all column sums are exactly the same. This basic idea extends naturally to array elements in a given numerical range; In fact, the popular puzzle game Sudoku is an exact dilated covering problem of a 9×9 matrix with element values ranging from 1 to 9 inclusive.
The microsphere problem is NP-complete, but computer scientists have devised non-deterministic iterative backflow algorithms to find the microsphere. One such procedure is Knuth’s X algorithm, described in [17]. In this algorithm, the elements of the array are connected via doubly linked circular lists, and individual elements are removed or restored, as the algorithm continues, undergoes backtracking, and so on. Since out/into list removals and restores are so common making these processes efficient is a laudable goal. This is where Knuth’s “dancing links” come in, resulting in an improved algorithm for finding exact shells that Knuth calls DLX (dancing links applied to Algorithm
2 dance links
The concept behind Dancing Links is very simple: when a certain item Y is removed from the list in the exact wrapper algorithm, it is very likely that that same item will be restored later. Rather so
Instead of “removing” the “previous” and “next” links associated with element Y, as good programming hygiene usually dictates, in Dancing Links, the programmer leaves the link values in place for the removed element. Thus, the delink operator deletes element Y from the list, maps the “next” element of the previous element Remove it. Later, if Y needs to be restored, it will simply be linked back to the list using a simple restore operator. In Knuth’s words, if one observes the menu links while the DLX algorithm is ongoing, the links appear to “dance,” hence the name. The function of Knuth’s Dancing Links is summarized in Figure 1.
