7.4 Contracts on Structures
Modules deal with structures in two ways. First they export struct definitions, i.e., the ability to create structs of a certain kind, to access their fields, to modify them, and to distinguish structs of this kind against every other kind of value in the world. Second, on occasion a module exports a specific struct and wishes to promise that its fields contain values of a certain kind. This section explains how to protect structs with contracts for both uses.
7.4.1 Promising Something About a Specific Structure
Yes. If your module defines a variable to be a structure, then on export you can specify the structures shape:
(require lang/posn) |
|
(define origin (make-posn 0 0)) |
|
In this example, the module imports a library for representing positions, which exports a posn structure. One of the posns it creates and exports stands for the origin, i.e., (0,0), of the grid.
7.4.2 Promising Something About a Specific Vector
Yes, again. See the help desk for information on vector/c and similar contract combinators for (flat) compound data.
7.4.3 Ensuring that All Structs are Well-Formed
The book How to Design Programs teaches that posns should contain only numbers in their two fields. With contracts we would enforce this informal data definition as follows:
(define-struct posn (x y)) |
|
[p-okay posn?] |
[p-sick posn?]) |
|
(define p-okay (make-posn 10 20)) |
(define p-sick (make-posn 'a 'b)) |
This module exports the entire structure definition: make-posn, posn?, posn-x, posn-y, set-posn-x!, and set-posn-y!. Each function enforces or promises that the two fields of a posn structure are numbers – when the values flow across the module boundary.
Thus, if a client calls make-posn on 10 and 'a, the contract system signals a contract violation.
The creation of p-sick inside of the posn module, however, does not violate the contracts. The function make-posn is used internally so 'a and 'b don’t cross the module boundary. Similarly, when p-sick crosses the boundary of posn, the contract promises a posn? and nothing else. In particular, this check does not require that the fields of p-sick are numbers.
The association of contract checking with module boundaries implies that p-okay and p-sick look alike from a client’s perspective until the client extracts the pieces:
(require lang/posn) |
|
Using posn-x is the only way the client can find out what a posn contains in the x field. The application of posn-x sends p-sick back into the posn module and the result value – 'a here – back to the client, again across the module boundary. At this very point, the contract system discovers that a promise is broken. Specifically, posn-x doesn’t return a number but a symbol and is therefore blamed.
This specific example shows that the explanation for a contract violation doesn’t always pinpoint the source of the error. The good news is that the error is located in the posn module. The bad news is that the explanation is misleading. Although it is true that posn-x produced a symbol instead of a number, it is the fault of the programmer who created a posn from symbols, i.e., the programmer who added
(define p-sick (make-posn 'a 'b))
to the module. So, when you are looking for bugs based on contract violations, keep this example in mind.
Exercise 1 Use your knowledge from the Promising Something About a Specific Structure section on exporting specific structs and change the contract for p-sick so that the error is caught when sick is exported.
Solution to exercise 1
A single change suffices:
Instead of exporting p-sick as a plain posn?, we use a struct/c contract to enforce constraints on its components.
7.4.4 Checking Properties of Data Structures
Contracts written using struct/c immediately check the fields of the data structure, but sometimes this can have disastrous effects on the performance of a program that does not, itself, inspect the entire data structure.
As an example, consider the the binary search tree search algorithm. A binary search tree is like a binary tree, except that the numbers are organized in the tree to make searching the tree fast. In particular, for each interior node in the tree, all of the numbers in the left subtree are smaller than the number in the node, and all of the numbers in the right subtree are larger than the number in the node.
We can implement a search function in? that takes advantage of the structure of the binary search tree.
|
(define-struct node (val left right)) |
|
; determines if `n' is in the binary search tree `b', |
; exploiting the binary search tree invariant |
(define (in? n b) |
(cond |
[(null? b) #f] |
[(= n (node-val b)) |
#t] |
[(< n (node-val b)) |
(in? n (node-left b))] |
[(> n (node-val b)) |
(in? n (node-right b))])])) |
|
; a predicate that identifies binary search trees |
(define (bst-between? b low high) |
(bst-between? (node-left b) low (node-val b)) |
(bst-between? (node-right b) (node-val b) high)))) |
|
(define (bst? b) (bst-between? b -inf.0 +inf.0)) |
|
(provide (struct node (val left right))) |
In a full binary search tree, this means that the in? function only has to explore a logarithmic number of nodes.
The contract on in? guarantees that its input is a binary search tree. But a little careful thought reveals that this contract defeats the purpose of the binary search tree algorithm. In particular, consider the inner cond in the in? function. This is where the in? function gets its speed: it avoids searching an entire subtree at each recursive call. Now compare that to the bst-between? function. In the case that it returns #t, it traverses the entire tree, meaning that the speedup of in? is lost.
In order to fix that, we can employ a new strategy for checking the binary search tree contract. In particular, if we only checked the contract on the nodes that in? looks at, we can still guarantee that the tree is at least partially well-formed, but without changing the complexity.
To do that, we need to use define-contract-struct in place of define-struct. Like define-struct, define-contract-struct defines a maker, predicate, and selectors for a new structure. Unlike define-struct, it also defines contract combinators, in this case node/c and node/dc. Also unlike define-struct, it does not allow mutators, making its structs always immutable.
The node/c function accepts a contract for each field of the struct and returns a contract on the struct. More interestingly, the syntactic form node/dc allows us to write dependent contracts, i.e., contracts where some of the contracts on the fields depend on the values of other fields. We can use this to define the binary search tree contract:
|
(define-contract-struct node (val left right)) |
|
; determines if `n' is in the binary search tree `b' |
|
; bst-between : number number -> contract |
; builds a contract for binary search trees |
; whose values are betweeen low and high |
(define (bst-between/c low high) |
(node/dc [val (between/c low high)] |
[left (val) (bst-between/c low val)] |
[right (val) (bst-between/c val high)]))) |
|
(define bst/c (bst-between/c -inf.0 +inf.0)) |
|
(provide make-node node-left node-right node-val node?) |
[bst/c contract?] |
In general, each use of node/dc must name the fields and then specify contracts for each field. In the above, the val field is a contract that accepts values between low and high. The left and right fields are dependent on the value of the val field, indicated by their second sub-expressions. Their contracts are built by recursive calls to the bst-between/c function. Taken together, this contract ensures the same thing that the bst-between? function checked in the original example, but here the checking only happens as in? explores the tree.
Although this contract improves the performance of in?, restoring it to the logarithmic behavior that the contract-less version had, it is still imposes a fairly large constant overhead. So, the contract library also provides define-opt/c that brings down that constant factor by optimizing its body. Its shape is just like the define above. It expects its body to be a contract and then optimizes that contract.
(define-opt/c (bst-between/c low high) |
(node/dc [val (between/c low high)] |
[left (val) (bst-between/c low val)] |
[right (val) (bst-between/c val high)]))) |