/usr/share/doc/racket/guide/contracts-struct.html is in racket-doc 6.1-4.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"/><title>7.5 Contracts on Structures</title><link rel="stylesheet" type="text/css" href="../scribble.css" title="default"/><link rel="stylesheet" type="text/css" href="../racket.css" title="default"/><link rel="stylesheet" type="text/css" href="../manual-style.css" title="default"/><link rel="stylesheet" type="text/css" href="../manual-racket.css" title="default"/><link rel="stylesheet" type="text/css" href="../manual-racket.css" title="default"/><link rel="stylesheet" type="text/css" href="../doc-site.css" title="default"/><script type="text/javascript" src="../scribble-common.js"></script><script type="text/javascript" src="../manual-racket.js"></script><script type="text/javascript" src="../manual-racket.js"></script><script type="text/javascript" src="../doc-site.js"></script><script type="text/javascript" src="../local-redirect/local-redirect.js"></script><script type="text/javascript" src="../local-redirect/local-user-redirect.js"></script><!--[if IE 6]><style type="text/css">.SIEHidden { overflow: hidden; }</style><![endif]--></head><body id="doc-racket-lang-org"><div class="tocset"><div class="tocview"><div class="tocviewlist tocviewlisttopspace"><div class="tocviewtitle"><table cellspacing="0" cellpadding="0"><tr><td style="width: 1em;"><a href="javascript:void(0);" title="Expand/Collapse" class="tocviewtoggle" onclick="TocviewToggle(this,"tocview_0");">►</a></td><td></td><td><a href="index.html" class="tocviewlink" data-pltdoc="x"><span style="font-weight: bold">The Racket Guide</span></a></td></tr></table></div><div class="tocviewsublisttop" style="display: none;" id="tocview_0"><table cellspacing="0" cellpadding="0"><tr><td align="right">1 </td><td><a href="intro.html" class="tocviewlink" data-pltdoc="x">Welcome to Racket</a></td></tr><tr><td align="right">2 </td><td><a href="to-scheme.html" class="tocviewlink" data-pltdoc="x">Racket Essentials</a></td></tr><tr><td align="right">3 </td><td><a href="datatypes.html" class="tocviewlink" data-pltdoc="x">Built-<wbr></wbr>In Datatypes</a></td></tr><tr><td align="right">4 </td><td><a href="scheme-forms.html" class="tocviewlink" data-pltdoc="x">Expressions and Definitions</a></td></tr><tr><td align="right">5 </td><td><a href="define-struct.html" class="tocviewlink" data-pltdoc="x">Programmer-<wbr></wbr>Defined Datatypes</a></td></tr><tr><td align="right">6 </td><td><a href="modules.html" class="tocviewlink" data-pltdoc="x">Modules</a></td></tr><tr><td align="right">7 </td><td><a href="contracts.html" class="tocviewselflink" data-pltdoc="x">Contracts</a></td></tr><tr><td align="right">8 </td><td><a href="i_o.html" class="tocviewlink" data-pltdoc="x">Input and Output</a></td></tr><tr><td align="right">9 </td><td><a href="regexp.html" class="tocviewlink" data-pltdoc="x">Regular Expressions</a></td></tr><tr><td align="right">10 </td><td><a href="control.html" class="tocviewlink" data-pltdoc="x">Exceptions and Control</a></td></tr><tr><td align="right">11 </td><td><a href="for.html" class="tocviewlink" data-pltdoc="x">Iterations and Comprehensions</a></td></tr><tr><td align="right">12 </td><td><a href="match.html" class="tocviewlink" data-pltdoc="x">Pattern Matching</a></td></tr><tr><td align="right">13 </td><td><a href="classes.html" class="tocviewlink" data-pltdoc="x">Classes and Objects</a></td></tr><tr><td align="right">14 </td><td><a href="units.html" class="tocviewlink" data-pltdoc="x">Units (Components)</a></td></tr><tr><td align="right">15 </td><td><a href="reflection.html" class="tocviewlink" data-pltdoc="x">Reflection and Dynamic Evaluation</a></td></tr><tr><td align="right">16 </td><td><a href="macros.html" class="tocviewlink" data-pltdoc="x">Macros</a></td></tr><tr><td align="right">17 </td><td><a href="languages.html" class="tocviewlink" data-pltdoc="x">Creating Languages</a></td></tr><tr><td align="right">18 </td><td><a href="concurrency.html" class="tocviewlink" data-pltdoc="x">Concurrency and Synchronization</a></td></tr><tr><td align="right">19 </td><td><a href="performance.html" class="tocviewlink" data-pltdoc="x">Performance</a></td></tr><tr><td align="right">20 </td><td><a href="parallelism.html" class="tocviewlink" data-pltdoc="x">Parallelism</a></td></tr><tr><td align="right">21 </td><td><a href="running.html" class="tocviewlink" data-pltdoc="x">Running and Creating Executables</a></td></tr><tr><td align="right">22 </td><td><a href="More_Libraries.html" class="tocviewlink" data-pltdoc="x">More Libraries</a></td></tr><tr><td align="right">23 </td><td><a href="dialects.html" class="tocviewlink" data-pltdoc="x">Dialects of Racket and Scheme</a></td></tr><tr><td align="right">24 </td><td><a href="other-editors.html" class="tocviewlink" data-pltdoc="x">Command-<wbr></wbr>Line Tools and Your Editor of Choice</a></td></tr><tr><td align="right"></td><td><a href="doc-bibliography.html" class="tocviewlink" data-pltdoc="x">Bibliography</a></td></tr><tr><td align="right"></td><td><a href="doc-index.html" class="tocviewlink" data-pltdoc="x">Index</a></td></tr></table></div></div><div class="tocviewlist"><table cellspacing="0" cellpadding="0"><tr><td style="width: 1em;"><a href="javascript:void(0);" title="Expand/Collapse" class="tocviewtoggle" onclick="TocviewToggle(this,"tocview_1");">▼</a></td><td>7 </td><td><a href="contracts.html" class="tocviewlink" data-pltdoc="x">Contracts</a></td></tr></table><div class="tocviewsublist" style="display: block;" id="tocview_1"><table cellspacing="0" cellpadding="0"><tr><td align="right">7.1 </td><td><a href="contract-boundaries.html" class="tocviewlink" data-pltdoc="x">Contracts and Boundaries</a></td></tr><tr><td align="right">7.2 </td><td><a href="contract-func.html" class="tocviewlink" data-pltdoc="x">Simple Contracts on Functions</a></td></tr><tr><td align="right">7.3 </td><td><a href="contracts-general-functions.html" class="tocviewlink" data-pltdoc="x">Contracts on Functions in General</a></td></tr><tr><td align="right">7.4 </td><td><a href="contracts-first.html" class="tocviewlink" data-pltdoc="x">Contracts:<span class="mywbr"> </span> A Thorough Example</a></td></tr><tr><td align="right">7.5 </td><td><a href="" class="tocviewselflink" data-pltdoc="x">Contracts on Structures</a></td></tr><tr><td align="right">7.6 </td><td><a href="contracts-exists.html" class="tocviewlink" data-pltdoc="x">Abstract Contracts using <span class="RktPn">#:<span class="mywbr"> </span>exists</span> and <span class="RktPn">#:<span class="mywbr"> </span>∃</span></a></td></tr><tr><td align="right">7.7 </td><td><a href="contracts-examples.html" class="tocviewlink" data-pltdoc="x">Additional Examples</a></td></tr><tr><td align="right">7.8 </td><td><a href="contracts-gotchas.html" class="tocviewlink" data-pltdoc="x">Gotchas</a></td></tr></table></div></div><div class="tocviewlist"><table cellspacing="0" cellpadding="0"><tr><td style="width: 1em;"><a href="javascript:void(0);" title="Expand/Collapse" class="tocviewtoggle" onclick="TocviewToggle(this,"tocview_2");">►</a></td><td>7.5 </td><td><a href="" class="tocviewselflink" data-pltdoc="x">Contracts on Structures</a></td></tr></table><div class="tocviewsublistbottom" style="display: none;" id="tocview_2"><table cellspacing="0" cellpadding="0"><tr><td align="right">7.5.1 </td><td><a href="#%28part._contracts-single-struct%29" class="tocviewlink" data-pltdoc="x">Guarantees for a Specific Value</a></td></tr><tr><td align="right">7.5.2 </td><td><a href="#%28part._contracts-define-struct%29" class="tocviewlink" data-pltdoc="x">Guarantees for All Values</a></td></tr><tr><td align="right">7.5.3 </td><td><a href="#%28part._contracts-lazy-contracts%29" class="tocviewlink" data-pltdoc="x">Checking Properties of Data Structures</a></td></tr></table></div></div></div><div class="tocsub"><div class="tocsubtitle">On this page:</div><table class="tocsublist" cellspacing="0"><tr><td><span class="tocsublinknumber">7.5.1<tt> </tt></span><a href="#%28part._contracts-single-struct%29" class="tocsubseclink" data-pltdoc="x">Guarantees for a Specific Value</a></td></tr><tr><td><span class="tocsublinknumber">7.5.2<tt> </tt></span><a href="#%28part._contracts-define-struct%29" class="tocsubseclink" data-pltdoc="x">Guarantees for All Values</a></td></tr><tr><td><span class="tocsublinknumber">7.5.3<tt> </tt></span><a href="#%28part._contracts-lazy-contracts%29" class="tocsubseclink" data-pltdoc="x">Checking Properties of Data Structures</a></td></tr></table></div></div><div class="maincolumn"><div class="main"><div class="navsettop"><span class="navleft"><form class="searchform"><input class="searchbox" style="color: #888;" type="text" value="...search manuals..." title="Enter a search string to search the manuals" onkeypress="return DoSearchKey(event, this, "6.1", "../");" onfocus="this.style.color="black"; this.style.textAlign="left"; if (this.value == "...search manuals...") this.value="";" onblur="if (this.value.match(/^ *$/)) { this.style.color="#888"; this.style.textAlign="center"; this.value="...search manuals..."; }"/></form> <a href="../index.html" title="up to the documentation top" data-pltdoc="x" onclick="return GotoPLTRoot("6.1");">top</a></span><span class="navright"> <a href="contracts-first.html" title="backward to "7.4 Contracts: A Thorough Example"" data-pltdoc="x">← prev</a> <a href="contracts.html" title="up to "7 Contracts"" data-pltdoc="x">up</a> <a href="contracts-exists.html" title="forward to "7.6 Abstract Contracts using #:exists and #:∃"" data-pltdoc="x">next →</a></span> </div><h4 x-source-module="(lib "scribblings/guide/guide.scrbl")" x-part-tag=""contracts-struct"">7.5<tt> </tt><a name="(part._contracts-struct)"></a>Contracts on Structures</h4><p>Modules deal with structures in two ways. First they export
<span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define-struct.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._struct%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct</a></span> 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.</p><h5 x-source-module="(lib "scribblings/guide/guide.scrbl")" x-part-tag=""contracts-single-struct"">7.5.1<tt> </tt><a name="(part._contracts-single-struct)"></a>Guarantees for a Specific Value</h5><p>If your module defines a variable to be a structure, then you can
specify the structure’s shape using <span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fstruct-dc..rkt%2529._struct%252Fc%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct/c</a></span>:</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><a href="Module_Syntax.html#%28part._hash-lang%29" class="RktModLink" data-pltdoc="x"><span class="RktMod">#lang</span></a><span class="hspace"> </span><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=index.html&version=6.1" class="RktModLink Sq" data-pltdoc="x"><span class="RktSym">racket</span></a></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=require.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._require%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">require</a></span><span class="hspace"> </span><span class="RktSym">lang/posn</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktSym">origin</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">make-posn</span><span class="hspace"> </span><span class="RktVal">0</span><span class="hspace"> </span><span class="RktVal">0</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=require.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._provide%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">provide</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=attaching-contracts-to-values.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fbase..rkt%2529._contract-out%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">contract-out</a></span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktSym">origin</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fstruct-dc..rkt%2529._struct%252Fc%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct/c</a></span><span class="hspace"> </span><span class="RktSym">posn</span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=number-types.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._zero%7E3f%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">zero?</a></span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=number-types.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._zero%7E3f%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">zero?</a></span><span class="RktPn">)</span><span class="RktPn">]</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr></table></blockquote><p>In this example, the module imports a library for representing positions, which
exports a <span class="RktSym">posn</span> structure. One of the <span class="RktSym">posn</span>s it creates
and exports stands for the origin, i.e., <span class="stt">(0,0)</span>, of the grid.</p><blockquote class="refpara"><blockquote class="refcolumn"><blockquote class="refcontent"><p>See also <span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528def._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fvector..rkt%2529._vector%252Fc%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">vector/c</a></span> and similar contract
combinators for (flat) compound data.</p></blockquote></blockquote></blockquote><h5 x-source-module="(lib "scribblings/guide/guide.scrbl")" x-part-tag=""contracts-define-struct"">7.5.2<tt> </tt><a name="(part._contracts-define-struct)"></a>Guarantees for All Values</h5><p>The book <span style="font-style: italic"><a href="http://www.htdp.org">How to Design Programs</a></span> teaches that <span class="RktSym">posn</span>s should contain only
numbers in their two fields. With contracts we would enforce this
informal data definition as follows:</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><a href="Module_Syntax.html#%28part._hash-lang%29" class="RktModLink" data-pltdoc="x"><span class="RktMod">#lang</span></a><span class="hspace"> </span><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=index.html&version=6.1" class="RktModLink Sq" data-pltdoc="x"><span class="RktSym">racket</span></a></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define-struct.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._struct%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct</a></span><span class="hspace"> </span><span class="RktSym">posn</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">x</span><span class="hspace"> </span><span class="RktSym">y</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=require.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._provide%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">provide</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=attaching-contracts-to-values.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fbase..rkt%2529._contract-out%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">contract-out</a></span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define-struct.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._struct%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct</a></span><span class="hspace"> </span><span class="RktSym">posn</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktPn">(</span><span class="RktSym">x</span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=number-types.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._number%7E3f%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">number?</a></span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">y</span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=number-types.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._number%7E3f%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">number?</a></span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">]</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktSym">p-okay</span><span class="hspace"> </span><span class="RktSym">posn?</span><span class="RktPn">]</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktSym">p-sick</span><span class="hspace"> </span><span class="RktSym">posn?</span><span class="RktPn">]</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktSym">p-okay</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">posn</span><span class="hspace"> </span><span class="RktVal">10</span><span class="hspace"> </span><span class="RktVal">20</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktSym">p-sick</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">posn</span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">a</span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">b</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr></table></blockquote><p>This module exports the entire structure definition: <span class="RktSym">posn</span>,
<span class="RktSym">posn?</span>, <span class="RktSym">posn-x</span>, <span class="RktSym">posn-y</span>,
<span class="RktSym">set-posn-x!</span>, and <span class="RktSym">set-posn-y!</span>. Each function enforces
or promises that the two fields of a <span class="RktSym">posn</span> structure are
numbers —<wbr></wbr> when the values flow across the module boundary. Thus, if
a client calls <span class="RktSym">posn</span> on <span class="RktVal">10</span> and <span class="RktVal">'</span><span class="RktVal">a</span>, the
contract system signals a contract violation.</p><p>The creation of <span class="RktSym">p-sick</span> inside of the <span class="RktSym">posn</span> module,
however, does not violate the contracts. The function <span class="RktSym">posn</span> is
used internally, so <span class="RktVal">'</span><span class="RktVal">a</span> and <span class="RktVal">'</span><span class="RktVal">b</span> don’t cross the module
boundary. Similarly, when <span class="RktSym">p-sick</span> crosses the boundary of
<span class="RktSym">posn</span>, the contract promises a <span class="RktSym">posn?</span> and nothing
else. In particular, this check does <span style="font-style: italic">not</span> require that the
fields of <span class="RktSym">p-sick</span> are numbers.</p><p>The association of contract checking with module boundaries implies that
<span class="RktSym">p-okay</span> and <span class="RktSym">p-sick</span> look alike from a client’s
perspective until the client extracts the pieces:</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><a href="Module_Syntax.html#%28part._hash-lang%29" class="RktModLink" data-pltdoc="x"><span class="RktMod">#lang</span></a><span class="hspace"> </span><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=index.html&version=6.1" class="RktModLink Sq" data-pltdoc="x"><span class="RktSym">racket</span></a></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=require.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._require%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">require</a></span><span class="hspace"> </span><span class="RktSym">lang/posn</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span></td></tr><tr><td><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=stx-patterns.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fstxcase-scheme..rkt%2529._......%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">...</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">posn-x</span><span class="hspace"> </span><span class="RktSym">p-sick</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=stx-patterns.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fstxcase-scheme..rkt%2529._......%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">...</a></span></td></tr></table></blockquote><p>Using <span class="RktSym">posn-x</span> is the only way the client can find out what
a <span class="RktSym">posn</span> contains in the <span class="RktSym">x</span> field. The application of
<span class="RktSym">posn-x</span> sends <span class="RktSym">p-sick</span> back into the
<span class="RktSym">posn</span> module and the result value – <span class="RktVal">'</span><span class="RktVal">a</span> here – back to
the client, again across the module boundary. At this very point, the contract
system discovers that a promise is broken. Specifically, <span class="RktSym">posn-x</span>
doesn’t return a number but a symbol and is therefore blamed.</p><p>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 <span class="RktSym">posn</span> module. The bad news is that the
explanation is misleading. Although it is true that <span class="RktSym">posn-x</span>
produced a symbol instead of a number, it is the fault of the programmer who
created a <span class="RktSym">posn</span> from symbols, i.e., the programmer who added</p><blockquote class="SCodeFlow"><p><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktSym">p-sick</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">posn</span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">a</span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">b</span><span class="RktPn">)</span><span class="RktPn">)</span></p></blockquote><p>to the module. So, when you are looking for bugs based on contract
violations, keep this example in mind.</p><p>If we want to fix the contract for <span class="RktSym">p-sick</span> so that the error
is caught when <span class="RktSym">sick</span> is exported, a single change suffices:</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=require.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._provide%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">provide</a></span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=attaching-contracts-to-values.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fbase..rkt%2529._contract-out%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">contract-out</a></span></td></tr><tr><td><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=stx-patterns.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fstxcase-scheme..rkt%2529._......%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">...</a></span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktSym">p-sick</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fstruct-dc..rkt%2529._struct%252Fc%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct/c</a></span><span class="hspace"> </span><span class="RktSym">posn</span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=number-types.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._number%7E3f%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">number?</a></span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=number-types.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._number%7E3f%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">number?</a></span><span class="RktPn">)</span><span class="RktPn">]</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr></table></blockquote><p>That is, instead of exporting <span class="RktSym">p-sick</span> as a plain
<span class="RktSym">posn?</span>, we use a <span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fstruct-dc..rkt%2529._struct%252Fc%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct/c</a></span> contract to enforce
constraints on its components.</p><h5 x-source-module="(lib "scribblings/guide/guide.scrbl")" x-part-tag=""contracts-lazy-contracts"">7.5.3<tt> </tt><a name="(part._contracts-lazy-contracts)"></a>Checking Properties of Data Structures</h5><p>Contracts written using <span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fstruct-dc..rkt%2529._struct%252Fc%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct/c</a></span> 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.</p><p>As an example, consider 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.</p><p><div class="SIntrapara">We can implement a search function <span class="RktSym">in?</span> that takes
advantage of the structure of the binary search tree.
</div><div class="SIntrapara"><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><a href="Module_Syntax.html#%28part._hash-lang%29" class="RktModLink" data-pltdoc="x"><span class="RktMod">#lang</span></a><span class="hspace"> </span><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=index.html&version=6.1" class="RktModLink Sq" data-pltdoc="x"><span class="RktSym">racket</span></a></td></tr><tr><td><span class="hspace"> </span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define-struct.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._struct%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct</a></span><span class="hspace"> </span><span class="RktSym">node</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">val</span><span class="hspace"> </span><span class="RktSym">left</span><span class="hspace"> </span><span class="RktSym">right</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span></td></tr><tr><td><span class="RktCmt">;</span><span class="RktCmt"> </span><span class="RktCmt">determines if `n' is in the binary search tree `b',</span></td></tr><tr><td><span class="RktCmt">;</span><span class="RktCmt"> </span><span class="RktCmt">exploiting the binary search tree invariant</span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">in?</span><span class="hspace"> </span><span class="RktSym">n</span><span class="hspace"> </span><span class="RktSym">b</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=if.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fletstx-scheme..rkt%2529._cond%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">cond</a></span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=pairs.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._null%7E3f%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">null?</a></span><span class="hspace"> </span><span class="RktSym">b</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktVal">#f</span><span class="RktPn">]</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=if.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fletstx-scheme..rkt%2529._else%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">else</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=if.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fletstx-scheme..rkt%2529._cond%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">cond</a></span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=generic-numbers.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._%7E3d%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">=</a></span><span class="hspace"> </span><span class="RktSym">n</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">node-val</span><span class="hspace"> </span><span class="RktSym">b</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktVal">#t</span><span class="RktPn">]</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=generic-numbers.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._%7E3c%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x"><</a></span><span class="hspace"> </span><span class="RktSym">n</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">node-val</span><span class="hspace"> </span><span class="RktSym">b</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">in?</span><span class="hspace"> </span><span class="RktSym">n</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">node-left</span><span class="hspace"> </span><span class="RktSym">b</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">]</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=generic-numbers.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._%7E3e%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">></a></span><span class="hspace"> </span><span class="RktSym">n</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">node-val</span><span class="hspace"> </span><span class="RktSym">b</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">in?</span><span class="hspace"> </span><span class="RktSym">n</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">node-right</span><span class="hspace"> </span><span class="RktSym">b</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">]</span><span class="RktPn">)</span><span class="RktPn">]</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span></td></tr><tr><td><span class="RktCmt">;</span><span class="RktCmt"> </span><span class="RktCmt">a predicate that identifies binary search trees</span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">bst-between?</span><span class="hspace"> </span><span class="RktSym">b</span><span class="hspace"> </span><span class="RktSym">low</span><span class="hspace"> </span><span class="RktSym">high</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=if.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fletstx-scheme..rkt%2529._or%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">or</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=pairs.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._null%7E3f%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">null?</a></span><span class="hspace"> </span><span class="RktSym">b</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=if.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fletstx-scheme..rkt%2529._and%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">and</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=generic-numbers.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._%7E3c%7E3d%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x"><=</a></span><span class="hspace"> </span><span class="RktSym">low</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">node-val</span><span class="hspace"> </span><span class="RktSym">b</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktSym">high</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">bst-between?</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">node-left</span><span class="hspace"> </span><span class="RktSym">b</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktSym">low</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">node-val</span><span class="hspace"> </span><span class="RktSym">b</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">bst-between?</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">node-right</span><span class="hspace"> </span><span class="RktSym">b</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">node-val</span><span class="hspace"> </span><span class="RktSym">b</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktSym">high</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">bst?</span><span class="hspace"> </span><span class="RktSym">b</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">bst-between?</span><span class="hspace"> </span><span class="RktSym">b</span><span class="hspace"> </span><span class="RktVal"><span class="nobreak">-i</span>nf.0</span><span class="hspace"> </span><span class="RktVal">+inf.0</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=require.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._provide%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">provide</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=require.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._struct-out%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct-out</a></span><span class="hspace"> </span><span class="RktSym">node</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=require.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._provide%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">provide</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=attaching-contracts-to-values.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fbase..rkt%2529._contract-out%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">contract-out</a></span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktSym">bst?</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528def._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fmisc..rkt%2529._any%252Fc%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">any/c</a></span><span class="hspace"> </span><span class="RktPn">. </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=function-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fbase..rkt%2529._-%7E3e%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x"><span class="nobreak">-></span></a></span><span class="RktPn"> .</span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=booleans.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._boolean%7E3f%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">boolean?</a></span><span class="RktPn">)</span><span class="RktPn">]</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktSym">in?</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=number-types.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._number%7E3f%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">number?</a></span><span class="hspace"> </span><span class="RktSym">bst?</span><span class="hspace"> </span><span class="RktPn">. </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=function-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fbase..rkt%2529._-%7E3e%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x"><span class="nobreak">-></span></a></span><span class="RktPn"> .</span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=booleans.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._boolean%7E3f%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">boolean?</a></span><span class="RktPn">)</span><span class="RktPn">]</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr></table></blockquote></div></p><p>In a full binary search tree, this means that
the <span class="RktSym">in?</span> function only has to explore a
logarithmic number of nodes.</p><p>The contract on <span class="RktSym">in?</span> 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 <span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=if.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fletstx-scheme..rkt%2529._cond%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">cond</a></span> in the <span class="RktSym">in?</span>
function. This is where the <span class="RktSym">in?</span> function gets
its speed: it avoids searching an entire subtree at each
recursive call. Now compare that to the <span class="RktSym">bst-between?</span>
function. In the case that it returns <span class="RktVal">#t</span>, it
traverses the entire tree, meaning that the speedup
of <span class="RktSym">in?</span> is lost.</p><p>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 <span class="RktSym">in?</span> looks at, we can still guarantee that
the tree is at least partially well-formed, but without
changing the complexity.</p><p>To do that, we need to use <span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fstruct-dc..rkt%2529._struct%252Fdc%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct/dc</a></span> to define
<span class="RktSym">bst-between?</span>. Like <span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fstruct-dc..rkt%2529._struct%252Fc%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct/c</a></span>, <span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fstruct-dc..rkt%2529._struct%252Fdc%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct/dc</a></span> defines a
contract for a structure. Unlike
<span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fstruct-dc..rkt%2529._struct%252Fc%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct/c</a></span>, it allows fields to be marked as lazy, so that
the contracts are only checked when the matching selector is called.
Also, it does not allow mutable fields to be marked as lazy.</p><p>The <span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fstruct-dc..rkt%2529._struct%252Fdc%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct/dc</a></span> form accepts a contract for each
field of the struct and returns a contract on the
struct. More interestingly, <span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fstruct-dc..rkt%2529._struct%252Fdc%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct/dc</a></span> 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:</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><a href="Module_Syntax.html#%28part._hash-lang%29" class="RktModLink" data-pltdoc="x"><span class="RktMod">#lang</span></a><span class="hspace"> </span><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=index.html&version=6.1" class="RktModLink Sq" data-pltdoc="x"><span class="RktSym">racket</span></a></td></tr><tr><td><span class="hspace"> </span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define-struct.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._struct%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct</a></span><span class="hspace"> </span><span class="RktSym">node</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">val</span><span class="hspace"> </span><span class="RktSym">left</span><span class="hspace"> </span><span class="RktSym">right</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span></td></tr><tr><td><span class="RktCmt">;</span><span class="RktCmt"> </span><span class="RktCmt">determines if `n' is in the binary search tree `b'</span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">in?</span><span class="hspace"> </span><span class="RktSym">n</span><span class="hspace"> </span><span class="RktSym">b</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=stx-patterns.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fstxcase-scheme..rkt%2529._......%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">...</a></span><span class="hspace"> </span><span class="RktSym">as</span><span class="hspace"> </span><span class="RktSym">before</span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=stx-patterns.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fstxcase-scheme..rkt%2529._......%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">...</a></span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span></td></tr><tr><td><span class="RktCmt">;</span><span class="RktCmt"> </span><span class="RktCmt">bst-between : number number -> contract</span></td></tr><tr><td><span class="RktCmt">;</span><span class="RktCmt"> </span><span class="RktCmt">builds a contract for binary search trees</span></td></tr><tr><td><span class="RktCmt">;</span><span class="RktCmt"> </span><span class="RktCmt">whose values are between low and high</span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">bst-between/c</span><span class="hspace"> </span><span class="RktSym">low</span><span class="hspace"> </span><span class="RktSym">high</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528def._%2528%2528lib._racket%252Fcontract%252Fbase..rkt%2529._or%252Fc%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">or/c</a></span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=pairs.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._null%7E3f%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">null?</a></span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fstruct-dc..rkt%2529._struct%252Fdc%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct/dc</a></span><span class="hspace"> </span><span class="RktSym">node</span><span class="hspace"> </span><span class="RktPn">[</span><span class="RktSym">val</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528def._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fmisc..rkt%2529._between%252Fc%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">between/c</a></span><span class="hspace"> </span><span class="RktSym">low</span><span class="hspace"> </span><span class="RktSym">high</span><span class="RktPn">)</span><span class="RktPn">]</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktSym">left</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">val</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktPn">#:lazy</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">bst-between/c</span><span class="hspace"> </span><span class="RktSym">low</span><span class="hspace"> </span><span class="RktSym">val</span><span class="RktPn">)</span><span class="RktPn">]</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktSym">right</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">val</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktPn">#:lazy</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">bst-between/c</span><span class="hspace"> </span><span class="RktSym">val</span><span class="hspace"> </span><span class="RktSym">high</span><span class="RktPn">)</span><span class="RktPn">]</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktSym">bst/c</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">bst-between/c</span><span class="hspace"> </span><span class="RktVal"><span class="nobreak">-i</span>nf.0</span><span class="hspace"> </span><span class="RktVal">+inf.0</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=require.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._provide%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">provide</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=require.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._struct-out%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct-out</a></span><span class="hspace"> </span><span class="RktSym">node</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=require.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._provide%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">provide</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=attaching-contracts-to-values.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fbase..rkt%2529._contract-out%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">contract-out</a></span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktSym">bst/c</span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=contract-utilities.html%23%2528def._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fmisc..rkt%2529._contract%7E3f%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">contract?</a></span><span class="RktPn">]</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktSym">in?</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=number-types.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._number%7E3f%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">number?</a></span><span class="hspace"> </span><span class="RktSym">bst/c</span><span class="hspace"> </span><span class="RktPn">. </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=function-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fbase..rkt%2529._-%7E3e%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x"><span class="nobreak">-></span></a></span><span class="RktPn"> .</span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=booleans.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._boolean%7E3f%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">boolean?</a></span><span class="RktPn">)</span><span class="RktPn">]</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr></table></blockquote><p>In general, each use of <span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fstruct-dc..rkt%2529._struct%252Fdc%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct/dc</a></span> must name the
fields and then specify contracts for each field. In the
above, the <span class="RktSym">val</span> field is a contract that accepts
values between <span class="RktSym">low</span> and <span class="RktSym">high</span>.
The <span class="RktSym">left</span> and <span class="RktSym">right</span> fields are
dependent on the value of the <span class="RktSym">val</span> field,
indicated by their second sub-expressions. They are
also marked with the <span class="RktPn">#:lazy</span> keyword to indicate
that they should be checked only when the appropriate
accessor is called on the struct instance. Their contracts
are built by recursive calls to
the <span class="RktSym">bst-between/c</span> function. Taken together,
this contract ensures the same thing that
the <span class="RktSym">bst-between?</span> function checked in the
original example, but here the checking only happens
as <span class="RktSym">in?</span> explores the tree.</p><p>Although this contract improves the performance
of <span class="RktSym">in?</span>, 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 <span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=contract-utilities.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fopt..rkt%2529._define-opt%252Fc%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define-opt/c</a></span> that brings
down that constant factor by optimizing its body. Its shape
is just like the <span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define</a></span> above. It expects its
body to be a contract and then optimizes that contract.</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=contract-utilities.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fopt..rkt%2529._define-opt%252Fc%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">define-opt/c</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">bst-between/c</span><span class="hspace"> </span><span class="RktSym">low</span><span class="hspace"> </span><span class="RktSym">high</span><span class="RktPn">)</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528def._%2528%2528lib._racket%252Fcontract%252Fbase..rkt%2529._or%252Fc%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">or/c</a></span><span class="hspace"> </span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=pairs.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._null%7E3f%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">null?</a></span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528form._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fstruct-dc..rkt%2529._struct%252Fdc%2529%2529&version=6.1" class="RktStxLink Sq" data-pltdoc="x">struct/dc</a></span><span class="hspace"> </span><span class="RktSym">node</span><span class="hspace"> </span><span class="RktPn">[</span><span class="RktSym">val</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528def._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fmisc..rkt%2529._between%252Fc%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">between/c</a></span><span class="hspace"> </span><span class="RktSym">low</span><span class="hspace"> </span><span class="RktSym">high</span><span class="RktPn">)</span><span class="RktPn">]</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktSym">left</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">val</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktPn">#:lazy</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">bst-between/c</span><span class="hspace"> </span><span class="RktSym">low</span><span class="hspace"> </span><span class="RktSym">val</span><span class="RktPn">)</span><span class="RktPn">]</span></td></tr><tr><td><span class="hspace"> </span><span class="RktPn">[</span><span class="RktSym">right</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">val</span><span class="RktPn">)</span><span class="hspace"> </span><span class="RktPn">#:lazy</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym">bst-between/c</span><span class="hspace"> </span><span class="RktSym">val</span><span class="hspace"> </span><span class="RktSym">high</span><span class="RktPn">)</span><span class="RktPn">]</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr></table></blockquote><div class="navsetbottom"><span class="navleft"><form class="searchform"><input class="searchbox" style="color: #888;" type="text" value="...search manuals..." title="Enter a search string to search the manuals" onkeypress="return DoSearchKey(event, this, "6.1", "../");" onfocus="this.style.color="black"; this.style.textAlign="left"; if (this.value == "...search manuals...") this.value="";" onblur="if (this.value.match(/^ *$/)) { this.style.color="#888"; this.style.textAlign="center"; this.value="...search manuals..."; }"/></form> <a href="../index.html" title="up to the documentation top" data-pltdoc="x" onclick="return GotoPLTRoot("6.1");">top</a></span><span class="navright"> <a href="contracts-first.html" title="backward to "7.4 Contracts: A Thorough Example"" data-pltdoc="x">← prev</a> <a href="contracts.html" title="up to "7 Contracts"" data-pltdoc="x">up</a> <a href="contracts-exists.html" title="forward to "7.6 Abstract Contracts using #:exists and #:∃"" data-pltdoc="x">next →</a></span> </div></div></div><div id="contextindicator"> </div></body></html>
|