<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@vertical+block@Reading_10_Objectives" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Reading 10 Objectives</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.1x+3T2016+type@video+block@video_9a0a81eaab85">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@video+block@video_9a0a81eaab85" data-block-type="video" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video</h3>
<div
id="video_video_9a0a81eaab85"
class="video closed"
data-metadata='{"prioritizeHls": false, "sources": ["https://d2f1egay8yehza.cloudfront.net/MIT600512016-V005700_DTH.mp4", "https://d2f1egay8yehza.cloudfront.net/MIT600512016-V005700/MIT600512016-V005700.m3u8"], "autoplay": false, "transcriptLanguage": "en", "lmsRootURL": "https://openlearninglibrary.mit.edu", "transcriptTranslationUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_9a0a81eaab85/handler/transcript/translation/__lang__", "speed": null, "generalSpeed": 1.0, "streams": "1.00:DkeO3FR6e5M", "autoAdvance": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionPercentage": 0.95, "start": 0.0, "savedVideoPosition": 0.0, "autohideHtml5": false, "saveStateEnabled": false, "recordedYoutubeIsAvailable": true, "publishCompletionUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_9a0a81eaab85/handler/publish_completion", "saveStateUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_9a0a81eaab85/handler/xmodule_handler/save_user_state", "poster": null, "duration": 32.56, "captionDataDir": null, "showCaptions": "true", "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_9a0a81eaab85/handler/transcript/available_translations", "ytTestTimeout": 1500, "transcriptLanguages": {"en": "English"}, "completionEnabled": false, "ytMetadataEndpoint": "", "end": 0.0}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="video_9a0a81eaab85"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_video_9a0a81eaab85">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_video_9a0a81eaab85">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_9a0a81eaab85/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_9a0a81eaab85/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_111f99e1977b">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_111f99e1977b" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<h4>Software in 6.005</h4>
<table class="table table-striped no-markdown">
<tbody>
<tr>
<th width="33%">Safe from bugs</th>
<th>Easy to understand</th>
<th>Ready for change</th>
</tr>
<tr>
<td>
Correct today and correct in the unknown future
</td>
<td>
Communicating clearly with future programmers, including future you
</td>
<td>
Designed to accommodate change without rewriting
</td>
</tr>
</tbody>
</table>
<h4>Objectives for Today</h4>
<p>Today's reading introduces several ideas:</p>
<ul>
<li>invariants</li>
<li>representation exposure</li>
<li>abstraction functions</li>
<li>representation invariants</li>
</ul>
<p>In this reading, we study a more formal mathematical idea of what it means for a class to implement an ADT, via the notions of <em>abstraction functions</em> and <em>rep invariants</em>. These mathematical notions are eminently practical in software design. The abstraction function will give us a way to cleanly define the equality operation on an abstract data type (which we'll discuss in more depth in a future class). The rep invariant will make it easier to catch bugs caused by a corrupted data structure.</p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@vertical+block@vertical-invariants" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Invariants</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.1x+3T2016+type@video+block@video_ede119d0ebba">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@video+block@video_ede119d0ebba" data-block-type="video" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video</h3>
<div
id="video_video_ede119d0ebba"
class="video closed"
data-metadata='{"prioritizeHls": false, "sources": ["https://d2f1egay8yehza.cloudfront.net/MIT600512016-V007500_DTH.mp4", "https://d2f1egay8yehza.cloudfront.net/MIT600512016-V007500/MIT600512016-V007500.m3u8"], "autoplay": false, "transcriptLanguage": "en", "lmsRootURL": "https://openlearninglibrary.mit.edu", "transcriptTranslationUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_ede119d0ebba/handler/transcript/translation/__lang__", "speed": null, "generalSpeed": 1.0, "streams": "1.00:TE50l0StS6c", "autoAdvance": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionPercentage": 0.95, "start": 0.0, "savedVideoPosition": 0.0, "autohideHtml5": false, "saveStateEnabled": false, "recordedYoutubeIsAvailable": true, "publishCompletionUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_ede119d0ebba/handler/publish_completion", "saveStateUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_ede119d0ebba/handler/xmodule_handler/save_user_state", "poster": null, "duration": 669.92, "captionDataDir": null, "showCaptions": "true", "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_ede119d0ebba/handler/transcript/available_translations", "ytTestTimeout": 1500, "transcriptLanguages": {"en": "English"}, "completionEnabled": false, "ytMetadataEndpoint": "", "end": 0.0}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="video_ede119d0ebba"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_video_ede119d0ebba">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_video_ede119d0ebba">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_ede119d0ebba/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_ede119d0ebba/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_014094ae5f01">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_014094ae5f01" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<h2 id="invariants">Invariants</h2>
<div data-outline="invariants">
<p>Resuming our discussion of what makes a good abstract data type, the final, and perhaps most important, property of a good abstract data type is that it <strong>preserves its own invariants</strong>. An <em>invariant</em> is a property of a program that is always true, for every possible runtime state of the program. Immutability is one crucial invariant that we've already encountered: once created, an immutable object should always represent the same value, for its entire lifetime. Saying that the ADT <em>preserves its own invariants</em> means that the ADT is responsible for ensuring that its own invariants hold. It doesn't depend on good behavior from its clients.</p>
<p>When an ADT preserves its own invariants, reasoning about the code becomes much easier. If you can count on the fact that Strings never change, you can rule out that possibility when you're debugging code that uses Strings — or when you're trying to establish an invariant for another ADT that uses Strings. Contrast that with a string type that guarantees that it will be immutable only if its clients promise not to change it. Then you'd have to check all the places in the code where the string might be used.</p>
<h3 id="immutability">Immutability</h3>
<div data-outline="immutability">
<p>Later in this reading, we'll see many interesting invariants. Let's focus on immutability for now. Here's a specific example:</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/**
* This immutable data type represents a tweet from Twitter.
*/</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Tweet</span> </span>{
<span class="hljs-keyword">public</span> String author;
<span class="hljs-keyword">public</span> String text;
<span class="hljs-keyword">public</span> Date timestamp;
<span class="hljs-comment handout-javadoc-comment">/**
* Make a Tweet.
* <span class="hljs-doctag">@param</span> author Twitter user who wrote the tweet
* <span class="hljs-doctag">@param</span> text text of the tweet
* <span class="hljs-doctag">@param</span> timestamp date/time when the tweet was sent
*/</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Tweet</span><span class="hljs-params">(String author, String text, Date timestamp)</span> </span>{
<span class="hljs-keyword">this</span>.author = author;
<span class="hljs-keyword">this</span>.text = text;
<span class="hljs-keyword">this</span>.timestamp = timestamp;
}
}</code></pre>
<p>How do we guarantee that these Tweet objects are immutable — that, once a tweet is created, its author, message, and date can never be changed?</p>
<p>The first threat to immutability comes from the fact that clients can — in fact must — directly access its fields. So nothing's stopping us from writing code like this:</p><pre><code class="language-java hljs">Tweet t = <span class="hljs-keyword">new</span> Tweet(<span class="hljs-string">"justinbieber"</span>,
<span class="hljs-string">"Thanks to all those beliebers out there inspiring me every day"</span>,
<span class="hljs-keyword">new</span> Date());
t.author = <span class="hljs-string">"rbmllr"</span>;</code></pre>
<p>This is a trivial example of <strong>representation exposure</strong>, meaning that code outside the class can modify the representation directly. Rep exposure like this threatens not only invariants, but also representation independence. We can't change the implementation of Tweet without affecting all the clients who are directly accessing those fields.</p>
<p>Fortunately, Java gives us language mechanisms to deal with this kind of rep exposure:</p><pre><code class="language-java hljs"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Tweet</span> </span>{
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> String author;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> String text;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> Date timestamp;
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Tweet</span><span class="hljs-params">(String author, String text, Date timestamp)</span> </span>{
<span class="hljs-keyword">this</span>.author = author;
<span class="hljs-keyword">this</span>.text = text;
<span class="hljs-keyword">this</span>.timestamp = timestamp;
}
<span class="hljs-comment handout-javadoc-comment">/** <span class="hljs-doctag">@return</span> Twitter user who wrote the tweet */</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">getAuthor</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">return</span> author;
}
<span class="hljs-comment handout-javadoc-comment">/** <span class="hljs-doctag">@return</span> text of the tweet */</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">getText</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">return</span> text;
}
<span class="hljs-comment handout-javadoc-comment">/** <span class="hljs-doctag">@return</span> date/time when the tweet was sent */</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> Date <span class="hljs-title">getTimestamp</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">return</span> timestamp;
}
}</code></pre>
<p>The <code>private</code> and <code>public</code> keywords indicate which fields and methods are accessible only within the class and which can be accessed from outside the class. The <code>final</code> keyword also helps by guaranteeing that the fields of this immutable type won't be reassigned after the object is constructed.</p>
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/debab6dd1c1292bd0781864985c83811/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/10-retweetLater.png" alt="retweetLater breaking Tweet's immutability" width="300"></div>
<p>But that's not the end of the story: the rep is still exposed! Consider this perfectly reasonable client code that uses <code>Tweet</code>:</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/** <span class="hljs-doctag">@return</span> a tweet that retweets t, one hour later*/</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> Tweet <span class="hljs-title">retweetLater</span><span class="hljs-params">(Tweet t)</span> </span>{
Date d = t.getTimestamp();
d.setHours(d.getHours()+<span class="hljs-number">1</span>);
<span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> Tweet(<span class="hljs-string">"rbmllr"</span>, t.getText(), d);
}</code></pre>
<p><code>retweetLater</code> takes a tweet and should return another tweet with the same message (called a <em>retweet</em>) but sent an hour later. The <code>retweetLater</code> method might be part of a system that automatically echoes funny things that Twitter celebrities say.</p>
<p>What's the problem here? The <code>getTimestamp</code> call returns a reference to the same Date object referenced by tweet <code>t</code>.
<code>t.timestamp</code> and <code>d</code> are aliases to the same mutable object. So when that Date object is mutated by <code>d.setHours()</code>, this affects the date in <code>t</code> as well, as shown in the snapshot diagram.</p>
<p><code>Tweet</code>'s immutability invariant has been broken. The problem is that <code>Tweet</code> leaked out a reference to a mutable object that its immutability depended on. We exposed the rep, in such a way that <code>Tweet</code> can no longer guarantee that its objects are immutable. Perfectly reasonable client code created a subtle bug.</p>
<p>We can patch this kind of rep exposure by using defensive copying: making a copy of a mutable object to avoid leaking out references to the rep. Here's the code:</p><pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">public</span> Date <span class="hljs-title">getTimestamp</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> Date(timestamp.getTime());
}</code></pre>
<p>Mutable types often have a copy constructor that allows you to make a new instance that duplicates the value of an existing instance. In this case, <code>Date</code>'s copy constructor uses the timestamp value, measured in milliseconds since January 1, 1970. As another example, <code>StringBuilder</code>'s copy constructor takes a <code>String</code>. Another way to copy a mutable object is <code>clone()</code>, which is supported by some types but not all. There are unfortunate problems with the way <code>clone()</code> works in Java. For more, see Josh Bloch, <a href="https://books.google.com/books?id=ka2VUBqHiWkC&hl=en"><em>Effective Java</em></a>, item 11. </p>
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/248d6fa4a54cc2f5ed0b39610b9efd0f/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/10-tweetEveryHourToday.png" alt="tweetEveryHourToday breaking Tweet's immutability" width="300"></div>
<p>So we've done some defensive copying in the return value of <code>getTimestamp</code>. But we're not done yet! There's still rep exposure. Consider this (again perfectly reasonable) client code:</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/** <span class="hljs-doctag">@return</span> a list of 24 inspiring tweets, one per hour today */</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> List<Tweet> <span class="hljs-title">tweetEveryHourToday</span> <span class="hljs-params">()</span> </span>{
List<Tweet> list = <span class="hljs-keyword">new</span> ArrayList<Tweet>();
Date date = <span class="hljs-keyword">new</span> Date();
<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i < <span class="hljs-number">24</span>; i++) {
date.setHours(i);
list.add(<span class="hljs-keyword">new</span> Tweet(<span class="hljs-string">"rbmllr"</span>, <span class="hljs-string">"keep it up! you can do it"</span>, date));
}
<span class="hljs-keyword">return</span> list;
}</code></pre>
<p>This code intends to advance a single Date object through the 24 hours of a day, creating a tweet for every hour. But notice that the constructor of Tweet saves the reference that was passed in, so all 24 Tweet objects end up with the same time, as shown in this snapshot diagram.</p>
<p>Again, the immutability of Tweet has been violated. We can fix this problem too by using judicious defensive copying, this time in the constructor:</p><pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Tweet</span><span class="hljs-params">(String author, String text, Date timestamp)</span> </span>{
<span class="hljs-keyword">this</span>.author = author;
<span class="hljs-keyword">this</span>.text = text;
<span class="hljs-keyword">this</span>.timestamp = <span class="hljs-keyword">new</span> Date(timestamp.getTime());
}</code></pre>
<p>In general, you should carefully inspect the argument types and return types of all your ADT operations. If any of the types are mutable, make sure your implementation doesn't return direct references to its representation. Doing that creates rep exposure.</p>
<p>You may object that this seems wasteful. Why make all these copies of dates? Why can't we just solve this problem by a carefully written specification, like this?</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/**
* Make a Tweet.
* <span class="hljs-doctag">@param</span> author Twitter user who wrote the tweet
* <span class="hljs-doctag">@param</span> text text of the tweet
* <span class="hljs-doctag">@param</span> timestamp date/time when the tweet was sent. Caller must never
* mutate this Date object again!
*/</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Tweet</span><span class="hljs-params">(String author, String text, Date timestamp)</span> </span>{</code></pre>
<p>This approach is sometimes taken when there isn't any other reasonable alternative — for example, when the mutable object is too large to copy efficiently. But the cost in your ability to reason about the program, and your ability to avoid bugs, is enormous. In the absence of compelling arguments to the contrary, it's almost always worth it for an abstract data type to guarantee its own invariants, and preventing rep exposure is essential to that.</p>
<p>An even better solution is to prefer immutable types. If -- as recommended in <a href="/courses/course-v1:MITx+6.005.1x+3T2016/jump_to_id/vertical-invariants#mutation-risky-2">Mutability & Immutability's Groundhog Day example</a> -- we had used an immutable date object, like <code>java.time.ZonedDateTime</code>, instead of the mutable <code>java.util.Date</code>, then we would have ended this section after talking about <code>public</code> and <code>private</code>. No further rep exposure would have been possible.</p>
</div>
<h3 id="immutable_wrappers_around_mutable_data_types">Immutable Wrappers Around Mutable Data Types</h3>
<div data-outline="immutable_wrappers_around_mutable_data_types">
<p>The Java collections classes offer an interesting compromise: immutable wrappers. We talked about these before in the reading on <a href="/courses/course-v1:MITx+6.005.1x+3T2016/jump_to_id/vertical-mutation-and-contracts#useful_immutable_types">Mutabilty and Immutability</a>.</p>
<p><code>Collections.unmodifiableList()</code> takes a (mutable) List and wraps it with an object that looks like a List, but whose mutators are disabled — set(), add(), remove() throw exceptions. So you can construct a list using mutators, then seal it up in an unmodifiable wrapper (and throw away your reference to the original mutable list), and get an immutable list.</p>
<p>The downside here is that you get immutability at runtime, but not at compile time. Java won't warn you at compile time if you try to sort() this unmodifiable list. You'll just get an exception at runtime. But that's still better than nothing, so using unmodifiable lists, maps, and sets can be a very good way to reduce the risk of bugs.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@vertical+block@vertical_Questions_e76aa28563fe" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_fff67ba8819a">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_fff67ba8819a" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/3e6443fb95285d2dc06e8ffc448b9bdf/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism.js"></script>
<script src="/assets/courseware/v1/2ba76f8bdfef4e2d45e31a3dc5208470/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-rep-exposure-46">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-rep-exposure-46" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_10-rep-exposure-46" class="problems-wrapper" role="group"
aria-labelledby="10-rep-exposure-46-problem-title"
data-problem-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-rep-exposure-46" data-url="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-rep-exposure-46/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="10-rep-exposure-46-problem-title" aria-describedby="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-rep-exposure-46-problem-progress" tabindex="-1">
rep exposure
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-rep-exposure-46-problem-progress"></div>
<div class="problem">
<div>
<p>Consider the following problematic datatype:</p>
<pre class="code">
/** Represents an immutable right triangle. */
class RightTriangle {
/*A*/ private double[] sides;
// sides[0] and sides[1] are the two legs,
// and sides[2] is the hypotenuse, so declare it to avoid having a
// magic number in the code:
/*B*/ public static final int HYPOTENUSE = 2;
/** Make a right triangle.
* @param legA, legB the two legs of the triangle
* @param hypotenuse the hypotenuse of the triangle.
*C* * Requires hypotenuse^2 = legA^2 + legB^2
* (within the error tolerance of double arithmetic)
*/
public RightTriangle(double legA, double legB, double hypotenuse) {
/*D*/ this.sides = new double[] { legA, legB, hypotenuse };
}
/** Get all the sides of the triangle.
* @return three-element array with the triangle's side lengths
*/
public double[] getAllSides() {
/*E*/ return sides;
}
/** @return length of the triangle's hypotenuse */
public double getHypotenuse() {
return sides[HYPOTENUSE];
}
/** @param factor to multiply the sides by
* @return a triangle made from this triangle by
* multiplies all side lengths by factor.
*/
public RightTriangle scale(double factor) {
return new RightTriangle (sides[0]*factor, sides[1]*factor, sides[2]*factor);
}
/** @return a regular triangle made from this triangle.
* A regular right triangle is one in which
* both legs have the same length.
*/
public RightTriangle regularize() {
double bigLeg = Math.max(side[0], side[1]);
return new RightTriangle (bigLeg, bigLeg, side[2]);
}
}
</pre>
<p>Which of the following statements are true? Check all that apply.</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_10-rep-exposure-46_2_1">
<fieldset aria-describedby="status_10-rep-exposure-46_2_1">
<div class="field">
<input type="checkbox" name="input_10-rep-exposure-46_2_1[]" id="input_10-rep-exposure-46_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="10-rep-exposure-46_2_1-choice_0-label" for="input_10-rep-exposure-46_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_10-rep-exposure-46_2_1"> The line marked /*A*/ is a problem for rep exposure because arrays are mutable.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-rep-exposure-46_2_1[]" id="input_10-rep-exposure-46_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="10-rep-exposure-46_2_1-choice_1-label" for="input_10-rep-exposure-46_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_10-rep-exposure-46_2_1"> The line marked /*B*/ is a problem for representation independence because it reveals how the sides array is organized.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-rep-exposure-46_2_1[]" id="input_10-rep-exposure-46_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="10-rep-exposure-46_2_1-choice_2-label" for="input_10-rep-exposure-46_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_10-rep-exposure-46_2_1"> The line marked *C* is a problem because creator operations should not have preconditions.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-rep-exposure-46_2_1[]" id="input_10-rep-exposure-46_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="10-rep-exposure-46_2_1-choice_3-label" for="input_10-rep-exposure-46_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_10-rep-exposure-46_2_1"> The line marked /*D*/ is a problem because it puts legA, legB, and hypotenuse into the rep without doing a defensive copy first.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-rep-exposure-46_2_1[]" id="input_10-rep-exposure-46_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="10-rep-exposure-46_2_1-choice_4-label" for="input_10-rep-exposure-46_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_10-rep-exposure-46_2_1"> The line marked /*E*/ is a problem because it threatens the class's immutability.
</label>
</div>
<span id="answer_10-rep-exposure-46_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_10-rep-exposure-46_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_10-rep-exposure-46_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="rep exposure" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_10-rep-exposure-46" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_10-rep-exposure-46">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-rep-exposure-46-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-rep-exposure-46-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-rep-exposure-46-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@vertical+block@Rep_Invariant_and_Abstraction_Function" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Rep Invariant and Abstraction Function</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.1x+3T2016+type@video+block@video_9ef9e30baf25">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@video+block@video_9ef9e30baf25" data-block-type="video" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video</h3>
<div
id="video_video_9ef9e30baf25"
class="video closed"
data-metadata='{"prioritizeHls": false, "sources": ["https://d2f1egay8yehza.cloudfront.net/MIT600512016-V006800_DTH.mp4", "https://d2f1egay8yehza.cloudfront.net/MIT600512016-V006800/MIT600512016-V006800.m3u8"], "autoplay": false, "transcriptLanguage": "en", "lmsRootURL": "https://openlearninglibrary.mit.edu", "transcriptTranslationUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_9ef9e30baf25/handler/transcript/translation/__lang__", "speed": null, "generalSpeed": 1.0, "streams": "1.00:PXvTLQ5488o", "autoAdvance": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionPercentage": 0.95, "start": 0.0, "savedVideoPosition": 0.0, "autohideHtml5": false, "saveStateEnabled": false, "recordedYoutubeIsAvailable": true, "publishCompletionUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_9ef9e30baf25/handler/publish_completion", "saveStateUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_9ef9e30baf25/handler/xmodule_handler/save_user_state", "poster": null, "duration": 628.31, "captionDataDir": null, "showCaptions": "true", "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_9ef9e30baf25/handler/transcript/available_translations", "ytTestTimeout": 1500, "transcriptLanguages": {"en": "English"}, "completionEnabled": false, "ytMetadataEndpoint": "", "end": 0.0}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="video_9ef9e30baf25"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_video_9ef9e30baf25">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_video_9ef9e30baf25">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_9ef9e30baf25/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_9ef9e30baf25/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_218d52ef8dc4">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_218d52ef8dc4" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<h2 id="rep_invariant_and_abstraction_function">Rep Invariant and Abstraction Function</h2>
<div data-outline="rep_invariant_and_abstraction_function">
<p>We now take a deeper look at the theory underlying abstract data types. This theory is not only elegant and interesting in its own right; it also has immediate practical application to the design and implementation of abstract types. If you understand the theory deeply, you'll be able to build better abstract types, and will be less likely to fall into subtle traps.</p>
<p>In thinking about an abstract type, it helps to consider the relationship between two spaces of values.</p>
<p>The space of representation values (or rep values for short) consists of the values of the actual implementation entities. In simple cases, an abstract type will be implemented as a single object, but more commonly a small network of objects is needed, so this value is actually often something rather complicated. For now, though, it will suffice to view it simply as a mathematical value.</p>
<p>The space of abstract values consists of the values that the type is designed to support. These are a figment of our imaginations. They're platonic entities that don't exist as described, but they are the way we want to view the elements of the abstract type, as clients of the type. For example, an abstract type for unbounded integers might have the mathematical integers as its abstract value space; the fact that it might be implemented as an array of primitive (bounded) integers, say, is not relevant to the user of the type.</p>
<p>Now of course the implementor of the abstract type must be interested in the representation values, since it is the implementor's job to achieve the illusion of the abstract value space using the rep value space.</p>
<p>Suppose, for example, that we choose to use a string to represent a set of characters:</p><pre><code class="language-java hljs"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">CharSet</span> </span>{
<span class="hljs-keyword">private</span> String s;
...
}</code></pre>
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/6078fe956f797efe4dd7d3b07049f0ef/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/10-charset-af-ri.png" alt="the abstract space and rep space of CharSet" width="300"></div>
<p>Then the rep space R contains Strings, and the abstract space A is mathematical sets of characters. We can show the two value spaces graphically, with an arc from a rep value to the abstract value it represents. There are several things to note about this picture:</p>
<ul>
<li><strong>Every abstract value is mapped to by some rep value</strong>. The purpose of implementing the abstract type is to support operations on abstract values. Presumably, then, we will need to be able to create and manipulate all possible abstract values, and they must therefore be representable.</li>
<li><strong>Some abstract values are mapped to by more than one rep value</strong>. This happens because the representation isn't a tight encoding. There's more than one way to represent an unordered set of characters as a string.</li>
<li><strong>Not all rep values are mapped</strong>. In this case, the string “abbc” is not mapped. In this case, we have decided that the string should not contain duplicates. This will allow us to terminate the remove method when we hit the first instance of a particular character, since we know there can be at most one.</li>
</ul>
<div class="clearfix"></div>
<p>In practice, we can only illustrate a few elements of the two spaces and their relationships; the graph as a whole is infinite. So we describe it by giving two things:</p>
<p>1. An <em>abstraction function</em> that maps rep values to the abstract values they represent: </p>
<blockquote>
<p>AF : R → A</p>
</blockquote>
<p>The arcs in the diagram show the abstraction function. In the terminology of functions, the properties we discussed above can be expressed by saying that the function is surjective (also called <em>onto</em>), not necessarily injective (also called <em>one-to-one</em>), and often partial.</p>
<p>2. A <em>rep invariant</em> that maps rep values to booleans: </p>
<blockquote>
<p>RI : R → boolean</p>
</blockquote>
<p>For a rep value <em>r</em>, <em>RI(r)</em> is true if and only if <em>r</em> is mapped by <em>AF</em>. In other words, <em>RI</em> tells us whether a given rep value is well-formed. Alternatively, you can think of <em>RI</em> as a set: it's the subset of rep values on which <em>AF</em> is defined.</p>
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/2066c6dd5027a68345d715a16b74fdc7/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/10-charset-norepeats.svg" alt="the abstract space and rep space of CharSet using the NoRepeatsRep" width="300"></div>
<p>Both the rep invariant and the abstraction function should be documented in the code, right next to the declaration of the rep itself:</p><pre><code class="hljs cs"><span class="hljs-keyword">public</span> <span class="hljs-keyword">class</span> <span class="hljs-title">CharSet</span> {
<span class="hljs-keyword">private</span> String s;
<span class="hljs-comment">// Rep invariant:</span>
<span class="hljs-comment">// s contains no repeated characters</span>
<span class="hljs-comment">// Abstraction Function:</span>
<span class="hljs-comment">// represents the set of characters found in s</span>
...
}</code></pre>
<div class="clearfix"></div>
<p>A common confusion about abstraction functions and rep invariants is that they are determined by the choice of rep and abstract value spaces, or even by the abstract value space alone. If this were the case, they would be of little use, since they would be saying something redundant that's already available elsewhere.</p>
<p>The abstract value space alone doesn't determine AF or RI: there can be several representations for the same abstract type. A set of characters could equally be represented as a string, as above, or as a bit vector, with one bit for each possible character. Clearly we need two different abstraction functions to map these two different rep value spaces.</p>
<p>It's less obvious why the choice of both spaces doesn't determine AF and RI. The key point is that defining a type for the rep, and thus choosing the values for the space of rep values, does not determine which of the rep values will be deemed to be legal, and of those that are legal, how they will be interpreted. Rather than deciding, as we did above, that the strings have no duplicates, we could instead allow duplicates, but at the same time require that the characters be sorted, appearing in nondecreasing order. This would allow us to perform a binary search on the string and thus check membership in logarithmic rather than linear time. Same rep value space — different rep invariant:</p>
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/e5013513b5b5f77c8864183b40d7eba3/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/10-charset-sorted.svg" alt="the abstract space and rep space of CharSet using the SortedRep" width="300"></div><pre><code class="language-java hljs"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">CharSet</span> </span>{
<span class="hljs-keyword">private</span> String s;
<span class="hljs-comment">// Rep invariant:</span>
<span class="hljs-comment">// s[0] <= s[1] <= ... <= s[s.length()-1]</span>
<span class="hljs-comment">// Abstraction Function:</span>
<span class="hljs-comment">// represents the set of characters found in s</span>
...
}</code></pre>
<p>Even with the same type for the rep value space and the same rep invariant RI, we might still interpret the rep differently, with different abstraction functions AF. Suppose RI admits any string of characters. Then we could define AF, as above, to interpret the array's elements as the elements of the set. But there's no <em>a priori</em> reason to let the rep decide the interpretation. Perhaps we'll interpret consecutive pairs of characters as subranges, so that the string rep <code>“acgg”</code> is interpreted as two range pairs, [a-c] and [g-g], and therefore represents the set {a,b,c,g}. Here's what the AF and RI would look like for that representation:</p>
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/c040983a4a71c62af758f3f5c43c59a0/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/10-charset-sortedrange.svg" alt="the abstract space and rep space of CharSet using the SortedRangeRep" width="300"></div><pre><code class="language-java hljs"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">CharSet</span> </span>{
<span class="hljs-keyword">private</span> String s;
<span class="hljs-comment">// Rep invariant:</span>
<span class="hljs-comment">// s.length is even</span>
<span class="hljs-comment">// s[0] <= s[1] <= ... <= s[s.length()-1]</span>
<span class="hljs-comment">// Abstraction Function:</span>
<span class="hljs-comment">// represents the union of the ranges</span>
<span class="hljs-comment">// {s[i]...s[i+1]} for each adjacent pair of characters </span>
<span class="hljs-comment">// in s</span>
...
}</code></pre>
<p>The essential point is that designing an abstract type means <strong>not only choosing the two spaces</strong> — the abstract value space for the specification and the rep value space for the implementation — <strong>but also deciding what rep values to use and how to interpret them</strong>.</p>
<p>It's critically important to write down these assumptions in your code, as we've done above, so that future programmers (and your future self) are aware of what the representation actually means. Why? What happens if different implementers disagree about the meaning of the rep?</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@vertical+block@vertical_Questions_eb13979ba699" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_fff67ba8819a">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_fff67ba8819a" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/3e6443fb95285d2dc06e8ffc448b9bdf/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism.js"></script>
<script src="/assets/courseware/v1/2ba76f8bdfef4e2d45e31a3dc5208470/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-42">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-42" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_10-af-ri-42" class="problems-wrapper" role="group"
aria-labelledby="10-af-ri-42-problem-title"
data-problem-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-42" data-url="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-42/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="10-af-ri-42-problem-title" aria-describedby="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-42-problem-progress" tabindex="-1">
AF &amp; RI
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-42-problem-progress"></div>
<div class="problem">
<div>
<p>Which of the following should be known (visible and documented) to the client of an abstract data type? Check all that apply.</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_10-af-ri-42_2_1">
<fieldset aria-describedby="status_10-af-ri-42_2_1">
<div class="field">
<input type="checkbox" name="input_10-af-ri-42_2_1[]" id="input_10-af-ri-42_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="10-af-ri-42_2_1-choice_0-label" for="input_10-af-ri-42_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-42_2_1"> abstract value space
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-42_2_1[]" id="input_10-af-ri-42_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="10-af-ri-42_2_1-choice_1-label" for="input_10-af-ri-42_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-42_2_1"> abstraction function
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-42_2_1[]" id="input_10-af-ri-42_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="10-af-ri-42_2_1-choice_2-label" for="input_10-af-ri-42_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-42_2_1"> creators
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-42_2_1[]" id="input_10-af-ri-42_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="10-af-ri-42_2_1-choice_3-label" for="input_10-af-ri-42_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-42_2_1"> observers
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-42_2_1[]" id="input_10-af-ri-42_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="10-af-ri-42_2_1-choice_4-label" for="input_10-af-ri-42_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-42_2_1"> rep
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-42_2_1[]" id="input_10-af-ri-42_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="10-af-ri-42_2_1-choice_5-label" for="input_10-af-ri-42_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-42_2_1"> rep invariant
</label>
</div>
<span id="answer_10-af-ri-42_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_10-af-ri-42_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_10-af-ri-42_solution_1"/>
</div><p>Which of the following should be known (visible and documented) to the maintainer of an abstract data type? Check all that apply.</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_10-af-ri-42_3_1">
<fieldset aria-describedby="status_10-af-ri-42_3_1">
<div class="field">
<input type="checkbox" name="input_10-af-ri-42_3_1[]" id="input_10-af-ri-42_3_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="10-af-ri-42_3_1-choice_0-label" for="input_10-af-ri-42_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-42_3_1"> abstract value space
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-42_3_1[]" id="input_10-af-ri-42_3_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="10-af-ri-42_3_1-choice_1-label" for="input_10-af-ri-42_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-42_3_1"> abstraction function
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-42_3_1[]" id="input_10-af-ri-42_3_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="10-af-ri-42_3_1-choice_2-label" for="input_10-af-ri-42_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-42_3_1"> creators
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-42_3_1[]" id="input_10-af-ri-42_3_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="10-af-ri-42_3_1-choice_3-label" for="input_10-af-ri-42_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-42_3_1"> observers
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-42_3_1[]" id="input_10-af-ri-42_3_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="10-af-ri-42_3_1-choice_4-label" for="input_10-af-ri-42_3_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-42_3_1"> rep
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-42_3_1[]" id="input_10-af-ri-42_3_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="10-af-ri-42_3_1-choice_5-label" for="input_10-af-ri-42_3_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-42_3_1"> rep invariant
</label>
</div>
<span id="answer_10-af-ri-42_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_10-af-ri-42_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_10-af-ri-42_solution_2"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="AF &amp; RI" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_10-af-ri-42" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_10-af-ri-42">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-af-ri-42-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-af-ri-42-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-af-ri-42-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-43">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-43" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_10-af-ri-43" class="problems-wrapper" role="group"
aria-labelledby="10-af-ri-43-problem-title"
data-problem-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-43" data-url="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-43/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="10-af-ri-43-problem-title" aria-describedby="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-43-problem-progress" tabindex="-1">
AF &amp; RI, part 2
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-43-problem-progress"></div>
<div class="problem">
<div>
<p>Suppose C is an abstract data type whose representation has two String fields:</p>
<pre class="code">
class C {
private String s;
private String t;
...
}
</pre>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_10-af-ri-43_2_1">
<fieldset aria-describedby="status_10-af-ri-43_2_1">
<legend id="10-af-ri-43_2_1-legend" class="response-fieldset-legend field-group-hd">Assuming you don't know anything about C's abstraction, which of the following might be part of a rep invariant for C?</legend>
<div class="field">
<input type="checkbox" name="input_10-af-ri-43_2_1[]" id="input_10-af-ri-43_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="10-af-ri-43_2_1-choice_0-label" for="input_10-af-ri-43_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-43_2_1"> s contains only letters
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-43_2_1[]" id="input_10-af-ri-43_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="10-af-ri-43_2_1-choice_1-label" for="input_10-af-ri-43_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-43_2_1"> s.length() == t.length()
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-43_2_1[]" id="input_10-af-ri-43_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="10-af-ri-43_2_1-choice_2-label" for="input_10-af-ri-43_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-43_2_1"> s represents a set of characters
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-43_2_1[]" id="input_10-af-ri-43_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="10-af-ri-43_2_1-choice_3-label" for="input_10-af-ri-43_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-43_2_1"> C's observers
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-43_2_1[]" id="input_10-af-ri-43_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="10-af-ri-43_2_1-choice_4-label" for="input_10-af-ri-43_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-43_2_1"> s is the reverse of t
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-43_2_1[]" id="input_10-af-ri-43_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="10-af-ri-43_2_1-choice_5-label" for="input_10-af-ri-43_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-43_2_1"> s+t
</label>
</div>
<span id="answer_10-af-ri-43_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_10-af-ri-43_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_10-af-ri-43_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="AF &amp; RI, part 2" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_10-af-ri-43" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_10-af-ri-43">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-af-ri-43-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-af-ri-43-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-af-ri-43-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-44">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-44" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_10-af-ri-44" class="problems-wrapper" role="group"
aria-labelledby="10-af-ri-44-problem-title"
data-problem-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-44" data-url="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-44/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="10-af-ri-44-problem-title" aria-describedby="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-44-problem-progress" tabindex="-1">
AF &amp; RI, part 3
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-44-problem-progress"></div>
<div class="problem">
<div>
<p>Suppose we are implementing CharSet with the following rep:</p>
<pre class="code">
public class CharSet {
private String s;
...
}
</pre>
<p>But we neglect to write down the abstraction function (AF) and rep invariant (RI). Here are four possible AF/RI pairs, which were also mentioned in the reading.</p>
<p>SortedRep:</p>
<pre class="code">
// AF: represents the set of characters found in s
// RI: s[0] &lt; s[1] &lt; ... &lt; s[s.length()-1]
</pre>
<p>SortedRangeRep: </p>
<pre class="code">
// AF: represents the union of the ranges {s[i]...s[i+1]} for each adjacent pair of characters in s
// RI: s.length is even, and s[0] &lt; s[1] &lt; ... &lt; s[s.length()-1]
</pre>
<p>NoRepeatsRep:</p>
<pre class="code">
// AF: represents the set of characters found in s
// RI: s contains no character more than once
</pre>
<p>AnyRep:</p>
<pre class="code">
// AF: represents the set of characters found in s
// RI: true
</pre>
<p>Three programmers are working on CharSet, each on a different method: add(), remove(), and contains().</p>
<p>Which possible AF/RI pairs are consistent with this programmer's implementation of <code>add()</code>?</p>
<pre class="code">
public void add(char c) {
s = s + c;
}
</pre>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_10-af-ri-44_2_1">
<fieldset aria-describedby="status_10-af-ri-44_2_1">
<div class="field">
<input type="checkbox" name="input_10-af-ri-44_2_1[]" id="input_10-af-ri-44_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="10-af-ri-44_2_1-choice_0-label" for="input_10-af-ri-44_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-44_2_1"> SortedRep
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-44_2_1[]" id="input_10-af-ri-44_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="10-af-ri-44_2_1-choice_1-label" for="input_10-af-ri-44_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-44_2_1"> SortedRangeRep
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-44_2_1[]" id="input_10-af-ri-44_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="10-af-ri-44_2_1-choice_2-label" for="input_10-af-ri-44_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-44_2_1"> NoRepeatsRep
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-44_2_1[]" id="input_10-af-ri-44_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="10-af-ri-44_2_1-choice_3-label" for="input_10-af-ri-44_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-44_2_1"> AnyRep
</label>
</div>
<span id="answer_10-af-ri-44_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_10-af-ri-44_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_10-af-ri-44_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="AF &amp; RI, part 3" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_10-af-ri-44" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_10-af-ri-44">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-af-ri-44-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-af-ri-44-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-af-ri-44-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-4" data-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-45">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-45" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_10-af-ri-45" class="problems-wrapper" role="group"
aria-labelledby="10-af-ri-45-problem-title"
data-problem-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-45" data-url="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-45/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="10-af-ri-45-problem-title" aria-describedby="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-45-problem-progress" tabindex="-1">
AF &amp; RI, part 4
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-45-problem-progress"></div>
<div class="problem">
<div>
<p>Which possible AF/RI pairs are consistent with this programmer's implementation of <code>remove()</code>?</p>
<pre class="code">
public void remove(char c) {
int position = s.indexOf(c);
if (position &gt;= 0) {
s = s.substring(0, position) + s.substring(position+1, s.length());
}
}
</pre>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_10-af-ri-45_2_1">
<fieldset aria-describedby="status_10-af-ri-45_2_1">
<div class="field">
<input type="checkbox" name="input_10-af-ri-45_2_1[]" id="input_10-af-ri-45_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="10-af-ri-45_2_1-choice_0-label" for="input_10-af-ri-45_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-45_2_1"> SortedRep
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-45_2_1[]" id="input_10-af-ri-45_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="10-af-ri-45_2_1-choice_1-label" for="input_10-af-ri-45_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-45_2_1"> SortedRangeRep
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-45_2_1[]" id="input_10-af-ri-45_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="10-af-ri-45_2_1-choice_2-label" for="input_10-af-ri-45_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-45_2_1"> NoRepeatsRep
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-45_2_1[]" id="input_10-af-ri-45_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="10-af-ri-45_2_1-choice_3-label" for="input_10-af-ri-45_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-45_2_1"> AnyRep
</label>
</div>
<span id="answer_10-af-ri-45_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_10-af-ri-45_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_10-af-ri-45_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="AF &amp; RI, part 4" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_10-af-ri-45" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_10-af-ri-45">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-af-ri-45-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-af-ri-45-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-af-ri-45-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-5" data-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-46">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-46" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_10-af-ri-46" class="problems-wrapper" role="group"
aria-labelledby="10-af-ri-46-problem-title"
data-problem-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-46" data-url="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-46/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="10-af-ri-46-problem-title" aria-describedby="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-46-problem-progress" tabindex="-1">
AF &amp; RI, part 3
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-af-ri-46-problem-progress"></div>
<div class="problem">
<div>
<p>Finally, which possible AF/RI pairs are consistent with this programmer's implementation of <code>contains()</code>?</p>
<pre class="code">
public boolean contains(char c) {
for (int i = 0; i &lt; s.length(); i += 2) {
char low = s.charAt(i);
char high = s.charAt(i+1);
if (low &lt;= c &amp;&amp; c &lt;= high) {
return true;
}
}
return false;
}
</pre>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_10-af-ri-46_2_1">
<fieldset aria-describedby="status_10-af-ri-46_2_1">
<div class="field">
<input type="checkbox" name="input_10-af-ri-46_2_1[]" id="input_10-af-ri-46_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="10-af-ri-46_2_1-choice_0-label" for="input_10-af-ri-46_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-46_2_1"> SortedRep
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-46_2_1[]" id="input_10-af-ri-46_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="10-af-ri-46_2_1-choice_1-label" for="input_10-af-ri-46_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-46_2_1"> SortedRangeRep
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-46_2_1[]" id="input_10-af-ri-46_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="10-af-ri-46_2_1-choice_2-label" for="input_10-af-ri-46_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-46_2_1"> NoRepeatsRep
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-af-ri-46_2_1[]" id="input_10-af-ri-46_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="10-af-ri-46_2_1-choice_3-label" for="input_10-af-ri-46_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_10-af-ri-46_2_1"> AnyRep
</label>
</div>
<span id="answer_10-af-ri-46_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_10-af-ri-46_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_10-af-ri-46_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="AF &amp; RI, part 3" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_10-af-ri-46" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_10-af-ri-46">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-af-ri-46-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-af-ri-46-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-af-ri-46-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@vertical+block@Checking_the_Rep_Invariant" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Checking the Rep Invariant</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.1x+3T2016+type@video+block@video_838406b42bc2">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@video+block@video_838406b42bc2" data-block-type="video" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video</h3>
<div
id="video_video_838406b42bc2"
class="video closed"
data-metadata='{"prioritizeHls": false, "sources": ["https://d2f1egay8yehza.cloudfront.net/MIT600512016-V007200_DTH.mp4", "https://d2f1egay8yehza.cloudfront.net/MIT600512016-V007200/MIT600512016-V007200.m3u8"], "autoplay": false, "transcriptLanguage": "en", "lmsRootURL": "https://openlearninglibrary.mit.edu", "transcriptTranslationUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_838406b42bc2/handler/transcript/translation/__lang__", "speed": null, "generalSpeed": 1.0, "streams": "1.00:pRUbBt9_XTA", "autoAdvance": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionPercentage": 0.95, "start": 0.0, "savedVideoPosition": 0.0, "autohideHtml5": false, "saveStateEnabled": false, "recordedYoutubeIsAvailable": true, "publishCompletionUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_838406b42bc2/handler/publish_completion", "saveStateUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_838406b42bc2/handler/xmodule_handler/save_user_state", "poster": null, "duration": 227.2, "captionDataDir": null, "showCaptions": "true", "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_838406b42bc2/handler/transcript/available_translations", "ytTestTimeout": 1500, "transcriptLanguages": {"en": "English"}, "completionEnabled": false, "ytMetadataEndpoint": "", "end": 0.0}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="video_838406b42bc2"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_video_838406b42bc2">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_video_838406b42bc2">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_838406b42bc2/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_838406b42bc2/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_99cc6b9cac89">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_99cc6b9cac89" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<h3 id="example_rational_numbers">Example: Rational Numbers</h3>
<div data-outline="example_rational_numbers">
<p>Here's an example of an abstract data type for rational numbers. Look closely at its rep invariant and abstraction function. </p><pre><code class="language-java hljs"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">RatNum</span> </span>{
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> numer;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> denom;
<span class="hljs-comment">// Rep invariant:</span>
<span class="hljs-comment">// denom > 0</span>
<span class="hljs-comment">// numer/denom is in reduced form</span>
<span class="hljs-comment">// Abstraction Function:</span>
<span class="hljs-comment">// represents the rational number numer / denom</span>
<span class="hljs-comment handout-javadoc-comment">/**
* Make a new Ratnum == n.
* @param n value
*/</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">RatNum</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span> </span>{
numer = n;
denom = <span class="hljs-number">1</span>;
checkRep();
}
<span class="hljs-comment handout-javadoc-comment">/**
* Make a new RatNum == (n / d).
* <span class="hljs-doctag">@param</span> n numerator
* <span class="hljs-doctag">@param</span> d denominator
* <span class="hljs-doctag">@throws</span> ArithmeticException if d == 0
*/</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">RatNum</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n, <span class="hljs-keyword">int</span> d)</span> <span class="hljs-keyword">throws</span> ArithmeticException </span>{
<span class="hljs-comment">// reduce ratio to lowest terms</span>
<span class="hljs-keyword">int</span> g = gcd(n, d);
n = n / g;
d = d / g;
<span class="hljs-comment">// make denominator positive</span>
<span class="hljs-keyword">if</span> (d < <span class="hljs-number">0</span>) {
numer = -n;
denom = -d;
} <span class="hljs-keyword">else</span> {
numer = n;
denom = d;
}
checkRep();
}
}</code></pre>
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/3c6fccd73e94dc5aac884a2585445db9/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/10-ratnum-af-ri.png" alt="the abstraction function and rep invariant of RatNum" width="500"></div>
<p>Here is a picture of the abstraction function and rep invariant for this code. The RI requires that numerator/denominator pairs be in reduced form (i.e., lowest terms), so pairs like (2,4) and (18,12) above should be drawn as outside the RI.</p>
<p>It would be completely reasonable to design another implementation of this same ADT with a more permissive RI. With such a change, some operations might become more expensive to perform, and others cheaper.</p>
<div class="clearfix"></div>
</div>
<h3 id="checking_the_rep_invariant">Checking the Rep Invariant</h3>
<div data-outline="checking_the_rep_invariant">
<p>The rep invariant isn't just a neat mathematical idea. If your implementation asserts the rep invariant at run time, then you can catch bugs early. Here's a method for RatNum that tests its rep invariant:</p><pre><code class="language-java hljs"><span class="hljs-comment">// Check that the rep invariant is true</span>
<span class="hljs-comment">// *** Warning: this does nothing unless you turn on assertion checking</span>
<span class="hljs-comment">// by passing -enableassertions to Java</span>
<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">checkRep</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">assert</span> denom > <span class="hljs-number">0</span>;
<span class="hljs-function"><span class="hljs-keyword">assert</span> <span class="hljs-title">gcd</span><span class="hljs-params">(numer, denom)</span> </span>== <span class="hljs-number">1</span>;
}</code></pre>
<p>You should certainly call checkRep() to assert the rep invariant at the end of every operation that creates or mutates the rep — in other words, creators, producers, and mutators. Look back at the RatNum code above, and you'll see that it calls checkRep() at the end of both constructors.</p>
<p>Observer methods don't normally need to call checkRep(), but it's good defensive practice to do so anyway. Why? Calling checkRep() in every method, including observers, means you'll be more likely to catch rep invariant violations caused by rep exposure.</p>
<p>Why is checkRep private? Who should be responsible for checking and enforcing a rep invariant — clients, or the implementation itself?</p>
</div>
<h3 id="no_null_values_in_the_rep">No Null Values in the Rep</h3>
<div data-outline="no_null_values_in_the_rep">
<p>Recall from the <a href="/courses/course-v1:MITx+6.005.1x+3T2016/jump_to_id/vertical-specification-structure#null_references">Specifications reading</a> that null values are troublesome and unsafe, so much so that we try to remove them from our programming entirely. In 6.005, the preconditions and postconditions of our methods implicitly require that objects and arrays be non-null.</p>
<p>We extend that prohibition to the reps of abstract data types. By default, in 6.005, the rep invariant implicitly includes <code>x != null</code> for every reference <code>x</code> in the rep that has object type (including references inside arrays or lists). So if your rep is:</p><pre><code class="language-java hljs"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">CharSet</span> </span>{
String s;
}</code></pre>
<p>then its rep invariant automatically includes <code>s != null</code>, and you don't need to state it in a rep invariant comment.</p>
<p>When it's time to implement that rep invariant in a checkRep() method, however, you still must <em>implement</em> the <code>s != null</code> check, and make sure that your checkRep() correctly fails when <code>s</code> is <code>null</code>. Often that check comes for free from Java, because checking other parts of your rep invariant will throw an exception if <code>s</code> is null. For example, if your checkRep() looks like this: </p><pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">checkRep</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">assert</span> s.length() % <span class="hljs-number">2</span> == <span class="hljs-number">0</span>;
...
}</code></pre>
<p>then you don't need <code>assert s!= null</code>, because the call to <code>s.length()</code> will fail just as effectively on a null reference. But if <code>s</code> is not otherwise checked by your rep invariant, then assert <code>s != null</code> explicitly.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@vertical+block@vertical_Questions_605f5006e298" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_fff67ba8819a">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_fff67ba8819a" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/3e6443fb95285d2dc06e8ffc448b9bdf/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism.js"></script>
<script src="/assets/courseware/v1/2ba76f8bdfef4e2d45e31a3dc5208470/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-checking-the-rep-invariant-45">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-checking-the-rep-invariant-45" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_10-checking-the-rep-invariant-45" class="problems-wrapper" role="group"
aria-labelledby="10-checking-the-rep-invariant-45-problem-title"
data-problem-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-checking-the-rep-invariant-45" data-url="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-checking-the-rep-invariant-45/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="10-checking-the-rep-invariant-45-problem-title" aria-describedby="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-checking-the-rep-invariant-45-problem-progress" tabindex="-1">
checking the rep invariant
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-checking-the-rep-invariant-45-problem-progress"></div>
<div class="problem">
<div>
<p>Which of the following are true? Check all that apply.</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_10-checking-the-rep-invariant-45_2_1">
<fieldset aria-describedby="status_10-checking-the-rep-invariant-45_2_1">
<div class="field">
<input type="checkbox" name="input_10-checking-the-rep-invariant-45_2_1[]" id="input_10-checking-the-rep-invariant-45_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="10-checking-the-rep-invariant-45_2_1-choice_0-label" for="input_10-checking-the-rep-invariant-45_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_10-checking-the-rep-invariant-45_2_1"> checkRep() is the abstraction function
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-checking-the-rep-invariant-45_2_1[]" id="input_10-checking-the-rep-invariant-45_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="10-checking-the-rep-invariant-45_2_1-choice_1-label" for="input_10-checking-the-rep-invariant-45_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_10-checking-the-rep-invariant-45_2_1"> checkRep() asserts the rep invariant
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-checking-the-rep-invariant-45_2_1[]" id="input_10-checking-the-rep-invariant-45_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="10-checking-the-rep-invariant-45_2_1-choice_2-label" for="input_10-checking-the-rep-invariant-45_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_10-checking-the-rep-invariant-45_2_1"> it's good to call checkRep() just before returning from a public method of an ADT class
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-checking-the-rep-invariant-45_2_1[]" id="input_10-checking-the-rep-invariant-45_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="10-checking-the-rep-invariant-45_2_1-choice_3-label" for="input_10-checking-the-rep-invariant-45_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_10-checking-the-rep-invariant-45_2_1"> it's good to call checkRep() just after calling a public method of an ADT class
</label>
</div>
<span id="answer_10-checking-the-rep-invariant-45_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_10-checking-the-rep-invariant-45_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_10-checking-the-rep-invariant-45_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="checking the rep invariant" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_10-checking-the-rep-invariant-45" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_10-checking-the-rep-invariant-45">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-checking-the-rep-invariant-45-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-checking-the-rep-invariant-45-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-checking-the-rep-invariant-45-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@vertical+block@Documenting_the_AF_RI_and_Safety_From_Rep_Exposure" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Documenting the AF, RI, and Safety From Rep Exposure</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.1x+3T2016+type@video+block@video_61c89f78503c">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@video+block@video_61c89f78503c" data-block-type="video" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video</h3>
<div
id="video_video_61c89f78503c"
class="video closed"
data-metadata='{"prioritizeHls": false, "sources": ["https://d2f1egay8yehza.cloudfront.net/MIT600512016-V006000_DTH.mp4", "https://d2f1egay8yehza.cloudfront.net/MIT600512016-V006000/MIT600512016-V006000.m3u8"], "autoplay": false, "transcriptLanguage": "en", "lmsRootURL": "https://openlearninglibrary.mit.edu", "transcriptTranslationUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_61c89f78503c/handler/transcript/translation/__lang__", "speed": null, "generalSpeed": 1.0, "streams": "1.00:d88RmcinEZQ", "autoAdvance": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionPercentage": 0.95, "start": 0.0, "savedVideoPosition": 0.0, "autohideHtml5": false, "saveStateEnabled": false, "recordedYoutubeIsAvailable": true, "publishCompletionUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_61c89f78503c/handler/publish_completion", "saveStateUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_61c89f78503c/handler/xmodule_handler/save_user_state", "poster": null, "duration": 132.98, "captionDataDir": null, "showCaptions": "true", "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_61c89f78503c/handler/transcript/available_translations", "ytTestTimeout": 1500, "transcriptLanguages": {"en": "English"}, "completionEnabled": false, "ytMetadataEndpoint": "", "end": 0.0}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="video_61c89f78503c"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_video_61c89f78503c">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_video_61c89f78503c">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_61c89f78503c/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_61c89f78503c/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_dfaec5b556dc">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_dfaec5b556dc" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<h2 id="documenting_the_af_ri_and_safety_from_rep_exposure">Documenting the AF, RI, and Safety from Rep Exposure</h2>
<div data-outline="documenting_the_af_ri_and_safety_from_rep_exposure">
<p>It's good practice to document the abstraction function and rep invariant in the class, using comments right where the private fields of the rep are declared. We've been doing that above.</p>
<p>Another piece of documentation that 6.005 asks you to write is a <strong>rep exposure safety argument</strong>. This is a comment that examines each part of the rep, looks at the code that handles that part of the rep (particularly with respect to parameters and return values from clients, because that is where rep exposure occurs), and presents a reason why the code doesn't expose the rep.</p>
<p>Here's an example of <code>Tweet</code> with its rep invariant, abstraction function, and safety from rep exposure fully documented:</p><pre><code class="language-java hljs"><span class="hljs-comment">// Immutable type representing a tweet.</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Tweet</span> </span>{
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> String author;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> String text;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> Date timestamp;
<span class="hljs-comment">// Rep invariant:</span>
<span class="hljs-comment">// author is a Twitter username (a nonempty string of letters, digits, underscores)</span>
<span class="hljs-comment">// text.length <= 140</span>
<span class="hljs-comment">// Abstraction Function:</span>
<span class="hljs-comment">// represents a tweet posted by author, with content text, at time timestamp </span>
<span class="hljs-comment">// Safety from rep exposure:</span>
<span class="hljs-comment">// All fields are private;</span>
<span class="hljs-comment">// author and text are Strings, so are guaranteed immutable;</span>
<span class="hljs-comment">// timestamp is a mutable Date, so Tweet() constructor and getTimestamp() </span>
<span class="hljs-comment">// make defensive copies to avoid sharing the rep's Date object with clients.</span>
<span class="hljs-comment">// Operations (specs and method bodies omitted to save space)</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Tweet</span><span class="hljs-params">(String author, String text, Date timestamp)</span> </span>{ ... }
<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">getAuthor</span><span class="hljs-params">()</span> </span>{ ... }
<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">getText</span><span class="hljs-params">()</span> </span>{ ... }
<span class="hljs-function"><span class="hljs-keyword">public</span> Date <span class="hljs-title">getTimestamp</span><span class="hljs-params">()</span> </span>{ ... }
}</code></pre>
<p>Notice that we don't have any explicit rep invariant conditions on <code>timestamp</code> (aside from the conventional assumption that <code>timestamp!=null</code>, which we have for all object references). But we still need to include <code>timestamp</code> in the rep exposure safety argument, because the immutability property of the whole type depends on all the fields remaining unchanged.</p>
<p>Compare the argument above with an example of a broken argument involving mutable <code>Date</code> objects:</p>
<pre><code class="language-java hljs"><span class="hljs-keyword">public class</span> Timespan {
<span class="hljs-keyword">private final</span> Date start;
<span class="hljs-keyword">private final</span> Date end;
<span class="hljs-comment">// Rep invariant:
// !end.before(start)
// Abstraction Function:
// represents the time interval from start to end, inclusive
// Safety from rep exposure:
// All fields are private and immutable. (<=== oops, false! Date is mutable)</span>
...
}</code></pre>
<p>Here are the arguments for <code>RatNum</code>.</p><pre><code class="language-java hljs"><span class="hljs-comment">// Immutable type representing a rational number.</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">RatNum</span> </span>{
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> numer;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> denom;
<span class="hljs-comment">// Rep invariant:</span>
<span class="hljs-comment">// denom > 0</span>
<span class="hljs-comment">// numer/denom is in reduced form, i.e. gcd(|numer|,denom) = 1</span>
<span class="hljs-comment">// Abstraction Function:</span>
<span class="hljs-comment">// represents the rational number numer / denom</span>
<span class="hljs-comment">// Safety from rep exposure:</span>
<span class="hljs-comment">// All fields are private, and all types in the rep are immutable.</span>
<span class="hljs-comment">// Operations (specs and method bodies omitted to save space)</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">RatNum</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span> </span>{ ... }
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">RatNum</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n, <span class="hljs-keyword">int</span> d)</span> <span class="hljs-keyword">throws</span> ArithmeticException </span>{ ... }
...
}</code></pre>
<p>Notice that an immutable rep is particularly easy to argue for safety from rep exposure.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@vertical+block@vertical_Questions_1c550ac6c94a" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_fff67ba8819a">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_fff67ba8819a" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/3e6443fb95285d2dc06e8ffc448b9bdf/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism.js"></script>
<script src="/assets/courseware/v1/2ba76f8bdfef4e2d45e31a3dc5208470/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-arguing-against-rep-exposure">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-arguing-against-rep-exposure" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_10-arguing-against-rep-exposure" class="problems-wrapper" role="group"
aria-labelledby="10-arguing-against-rep-exposure-problem-title"
data-problem-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-arguing-against-rep-exposure" data-url="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-arguing-against-rep-exposure/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="6"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="10-arguing-against-rep-exposure-problem-title" aria-describedby="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-arguing-against-rep-exposure-problem-progress" tabindex="-1">
arguing against rep exposure
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-arguing-against-rep-exposure-problem-progress"></div>
<div class="problem">
<div>
<p>Consider the following ADT:</p>
<pre class="code">
// Mutable type representing Twitter users' followers.
public class FollowGraph {
private final Map&lt;String,Set&lt;String&gt;&gt; followersOf;
// Rep invariant:
// all Strings in followersOf are Twitter usernames
// (i.e., nonempty strings of letters, digits, underscores)
// no user follows themselves, i.e. x is not in followersOf.get(x)
// Abstraction function:
// represents the follower graph where Twitter user x is followed by user y
// if and only if followersOf.get(x).contains(y)
// Safety from rep exposure:
// All fields are private, and ..???..
// Operations (specs and method bodies omitted to save space)
public FollowGraph() { ... }
public void addFollower(String user, String follower) { ... }
public void removeFollower(String user, String follower) { ... }
public Set&lt;String&gt; getFollowers(String user) { ... }
}
</pre>
<p>For each statement below: assuming the omitted method bodies are consistent with the statement, can we use the statement in place of <code>..???..</code> to make a persuasive safety-from-rep-exposure comment?</p>
<p>1. "Strings are immutable."</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="inputtype option-input ">
<select name="input_10-arguing-against-rep-exposure_2_1" id="input_10-arguing-against-rep-exposure_2_1" aria-describedby="status_10-arguing-against-rep-exposure_2_1">
<option value="option_10-arguing-against-rep-exposure_2_1_dummy_default">Select an option</option>
<option value="Yes"> Yes</option>
<option value="No"> No</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_10-arguing-against-rep-exposure_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_10-arguing-against-rep-exposure_2_1"/>
</div></div>
<p>2. "<code>followersOf</code> is a mutable <code>Map</code> containing mutable <code>Set</code> objects, but <code>getFollowers()</code> makes a defensive copy of the <code>Set</code> it returns, and all other parameters and return values are immutable <code>String</code> or <code>void</code>."</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="inputtype option-input ">
<select name="input_10-arguing-against-rep-exposure_3_1" id="input_10-arguing-against-rep-exposure_3_1" aria-describedby="status_10-arguing-against-rep-exposure_3_1">
<option value="option_10-arguing-against-rep-exposure_3_1_dummy_default">Select an option</option>
<option value="Yes"> Yes</option>
<option value="No"> No</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_10-arguing-against-rep-exposure_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_10-arguing-against-rep-exposure_3_1"/>
</div></div>
<p>3. "This class is mutable, so rep exposure isn't an issue."</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="inputtype option-input ">
<select name="input_10-arguing-against-rep-exposure_4_1" id="input_10-arguing-against-rep-exposure_4_1" aria-describedby="status_10-arguing-against-rep-exposure_4_1">
<option value="option_10-arguing-against-rep-exposure_4_1_dummy_default">Select an option</option>
<option value="Yes"> Yes</option>
<option value="No"> No</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_10-arguing-against-rep-exposure_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_10-arguing-against-rep-exposure_4_1"/>
</div></div>
<p>4. "<code>followersOf</code> is a mutable Map, but it is never passed or returned from an operation."</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 4" role="group"><div class="inputtype option-input ">
<select name="input_10-arguing-against-rep-exposure_5_1" id="input_10-arguing-against-rep-exposure_5_1" aria-describedby="status_10-arguing-against-rep-exposure_5_1">
<option value="option_10-arguing-against-rep-exposure_5_1_dummy_default">Select an option</option>
<option value="Yes"> Yes</option>
<option value="No"> No</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_10-arguing-against-rep-exposure_5_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_10-arguing-against-rep-exposure_5_1"/>
</div></div>
<p>5. "<code>FollowGraph()</code> does not expose the rep; <code>addFollower()</code> does not expose the rep; <code>removeFollower()</code> does not expose the rep; <code>getFollowers()</code> does not expose the rep."</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 5" role="group"><div class="inputtype option-input ">
<select name="input_10-arguing-against-rep-exposure_6_1" id="input_10-arguing-against-rep-exposure_6_1" aria-describedby="status_10-arguing-against-rep-exposure_6_1">
<option value="option_10-arguing-against-rep-exposure_6_1_dummy_default">Select an option</option>
<option value="Yes"> Yes</option>
<option value="No"> No</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_10-arguing-against-rep-exposure_6_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_10-arguing-against-rep-exposure_6_1"/>
</div></div>
<p>6. "<code>String</code> is immutable, and the <code>Set</code> objects in the rep are made immutable by unmodifiable wrappers. The <code>Map</code> type is mutable, but that type is never passed or returned from an operation."</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 6" role="group"><div class="inputtype option-input ">
<select name="input_10-arguing-against-rep-exposure_7_1" id="input_10-arguing-against-rep-exposure_7_1" aria-describedby="status_10-arguing-against-rep-exposure_7_1">
<option value="option_10-arguing-against-rep-exposure_7_1_dummy_default">Select an option</option>
<option value="Yes"> Yes</option>
<option value="No"> No</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_10-arguing-against-rep-exposure_7_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_10-arguing-against-rep-exposure_7_1"/>
</div></div>
<div class="solution-span">
<span id="solution_10-arguing-against-rep-exposure_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="arguing against rep exposure" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_10-arguing-against-rep-exposure" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_10-arguing-against-rep-exposure">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-arguing-against-rep-exposure-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-arguing-against-rep-exposure-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-arguing-against-rep-exposure-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@vertical+block@How_to_Establish_Invariants" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">How to Establish Invariants</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.1x+3T2016+type@video+block@video_c1310f785dd8">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@video+block@video_c1310f785dd8" data-block-type="video" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video</h3>
<div
id="video_video_c1310f785dd8"
class="video closed"
data-metadata='{"prioritizeHls": false, "sources": ["https://d2f1egay8yehza.cloudfront.net/MIT600512016-V005800_DTH.mp4", "https://d2f1egay8yehza.cloudfront.net/MIT600512016-V005800/MIT600512016-V005800.m3u8"], "autoplay": false, "transcriptLanguage": "en", "lmsRootURL": "https://openlearninglibrary.mit.edu", "transcriptTranslationUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_c1310f785dd8/handler/transcript/translation/__lang__", "speed": null, "generalSpeed": 1.0, "streams": "1.00:d3NhbWmrWOc", "autoAdvance": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionPercentage": 0.95, "start": 0.0, "savedVideoPosition": 0.0, "autohideHtml5": false, "saveStateEnabled": false, "recordedYoutubeIsAvailable": true, "publishCompletionUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_c1310f785dd8/handler/publish_completion", "saveStateUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_c1310f785dd8/handler/xmodule_handler/save_user_state", "poster": null, "duration": 77.63, "captionDataDir": null, "showCaptions": "true", "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_c1310f785dd8/handler/transcript/available_translations", "ytTestTimeout": 1500, "transcriptLanguages": {"en": "English"}, "completionEnabled": false, "ytMetadataEndpoint": "", "end": 0.0}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="video_c1310f785dd8"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_video_c1310f785dd8">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_video_c1310f785dd8">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_c1310f785dd8/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_c1310f785dd8/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_95d995a0124c">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_95d995a0124c" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<h3 id="how_to_establish_invariants">How to Establish Invariants</h3>
<div data-outline="how_to_establish_invariants">
<p>An invariant is a property that is true for the entire program — which in the case of an invariant about an object, reduces to the entire lifetime of the object.</p>
<p>To make an invariant hold, we need to:</p>
<ul>
<li>make the invariant true in the initial state of the object; and</li>
<li>ensure that all changes to the object keep the invariant true.</li>
</ul>
<p>Translating this in terms of the types of ADT operations, this means:</p>
<ul>
<li>creators and producers must establish the invariant for new object instances; and</li>
<li>mutators and observers must preserve the invariant.</li>
</ul>
<p>The risk of rep exposure makes the situation more complicated. If the rep is exposed, then the object might be changed anywhere in the program, not just in the ADT's operations, and we can't guarantee that the invariant still holds after those arbitrary changes. So the full rule for proving invariants is:</p>
<p><strong>Structural induction</strong>. If an invariant of an abstract data type is </p>
<ol>
<li>established by creators and producers; </li>
<li>preserved by mutators, and observers; and</li>
<li>no representation exposure occurs, </li>
</ol>
<p>then the invariant is true of all instances of the abstract data type.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@vertical+block@vertical_Questions_5dffbf07c7b9" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_fff67ba8819a">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_fff67ba8819a" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/3e6443fb95285d2dc06e8ffc448b9bdf/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism.js"></script>
<script src="/assets/courseware/v1/2ba76f8bdfef4e2d45e31a3dc5208470/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-structural-induction-47">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-structural-induction-47" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_10-structural-induction-47" class="problems-wrapper" role="group"
aria-labelledby="10-structural-induction-47-problem-title"
data-problem-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-structural-induction-47" data-url="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-structural-induction-47/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="10-structural-induction-47-problem-title" aria-describedby="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-structural-induction-47-problem-progress" tabindex="-1">
structural induction
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-structural-induction-47-problem-progress"></div>
<div class="problem">
<div>
<p>Recall this data type from the first exercise in this reading:</p>
<pre class="code">
/** Represents an immutable right triangle. */
class RightTriangle {
private double[] sides;
// sides[0] and sides[1] are the two legs,
// and sides[2] is the hypotenuse, so declare it to avoid having a
// magic number in the code:
public static final int HYPOTENUSE = 2;
/** Make a right triangle.
* @param legA, legB the two legs of the triangle
* @param hypotenuse the hypotenuse of the triangle.
* Requires hypotenuse^2 = legA^2 + legB^2
* (within the error tolerance of double arithmetic)
*/
public RightTriangle(double legA, double legB, double hypotenuse) {
this.sides = new double[] { legA, legB, hypotenuse };
}
/** Get all the sides of the triangle.
* @return three-element array with the triangle's side lengths
*/
public double[] getAllSides() {
return sides;
}
/** @return length of the triangle's hypotenuse */
public double getHypotenuse() {
return sides[HYPOTENUSE];
}
/** @param factor to multiply the sides by
* @return a triangle made from this triangle by
* multiplies all side lengths by factor.
*/
public RightTriangle scale(double factor) {
return new RightTriangle (sides[0]*factor, sides[1]*factor, sides[2]*factor);
}
/** @return a regular triangle made from this triangle.
* A regular right triangle is one in which
* both legs have the same length.
*/
public RightTriangle regularize() {
double bigLeg = Math.max(side[0], side[1]);
return new RightTriangle (bigLeg, bigLeg, side[2]);
}
}
</pre>
<p>This datatype has an important invariant: the relationship between the legs and hypotenuse, as stated in the Pythagorean theorem.</p>
<p>Assuming the client obeys the contracts when using RightTriangle, which of the following statements are true about this invariant? Check all that apply.</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_10-structural-induction-47_2_1">
<fieldset aria-describedby="status_10-structural-induction-47_2_1">
<div class="field">
<input type="checkbox" name="input_10-structural-induction-47_2_1[]" id="input_10-structural-induction-47_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="10-structural-induction-47_2_1-choice_0-label" for="input_10-structural-induction-47_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_10-structural-induction-47_2_1"> The creator RightTriangle() establishes the invariant if the client obeys all contracts.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-structural-induction-47_2_1[]" id="input_10-structural-induction-47_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="10-structural-induction-47_2_1-choice_1-label" for="input_10-structural-induction-47_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_10-structural-induction-47_2_1"> The observer getAllSides() preserves the invariant if the client obeys all contracts.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-structural-induction-47_2_1[]" id="input_10-structural-induction-47_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="10-structural-induction-47_2_1-choice_2-label" for="input_10-structural-induction-47_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_10-structural-induction-47_2_1"> The observer getHypotenuse() preserves the invariant if the client obeys all contracts.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-structural-induction-47_2_1[]" id="input_10-structural-induction-47_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="10-structural-induction-47_2_1-choice_3-label" for="input_10-structural-induction-47_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_10-structural-induction-47_2_1"> The producer scale() preserves the invariant if the client obeys all contracts.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-structural-induction-47_2_1[]" id="input_10-structural-induction-47_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="10-structural-induction-47_2_1-choice_4-label" for="input_10-structural-induction-47_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_10-structural-induction-47_2_1"> The producer regularize() preserves the invariant if the client obeys all contracts.
</label>
</div>
<span id="answer_10-structural-induction-47_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_10-structural-induction-47_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_10-structural-induction-47_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="structural induction" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_10-structural-induction-47" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_10-structural-induction-47">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-structural-induction-47-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-structural-induction-47-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-structural-induction-47-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@vertical+block@ADT_Invariants_Replace_Preconditions" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">ADT Invariants Replace Preconditions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.1x+3T2016+type@video+block@video_bcb5635d3656">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@video+block@video_bcb5635d3656" data-block-type="video" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video</h3>
<div
id="video_video_bcb5635d3656"
class="video closed"
data-metadata='{"prioritizeHls": false, "sources": ["https://d2f1egay8yehza.cloudfront.net/MIT600512016-V006100_DTH.mp4", "https://d2f1egay8yehza.cloudfront.net/MIT600512016-V006100/MIT600512016-V006100.m3u8"], "autoplay": false, "transcriptLanguage": "en", "lmsRootURL": "https://openlearninglibrary.mit.edu", "transcriptTranslationUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_bcb5635d3656/handler/transcript/translation/__lang__", "speed": null, "generalSpeed": 1.0, "streams": "1.00:yGCaeMRFneQ", "autoAdvance": false, "ytApiUrl": "https://www.youtube.com/iframe_api", "completionPercentage": 0.95, "start": 0.0, "savedVideoPosition": 0.0, "autohideHtml5": false, "saveStateEnabled": false, "recordedYoutubeIsAvailable": true, "publishCompletionUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_bcb5635d3656/handler/publish_completion", "saveStateUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_bcb5635d3656/handler/xmodule_handler/save_user_state", "poster": null, "duration": 79.18, "captionDataDir": null, "showCaptions": "true", "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_bcb5635d3656/handler/transcript/available_translations", "ytTestTimeout": 1500, "transcriptLanguages": {"en": "English"}, "completionEnabled": false, "ytMetadataEndpoint": "", "end": 0.0}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="video_bcb5635d3656"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_video_bcb5635d3656">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_video_bcb5635d3656">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_bcb5635d3656/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@video+block@video_bcb5635d3656/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_0deeb91ce56d">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_0deeb91ce56d" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<h2 id="adt_invariants_replace_preconditions">ADT invariants replace preconditions</h2>
<div data-outline="adt_invariants_replace_preconditions">
<p>Now let's bring a lot of pieces together. An enormous advantage of a well-designed abstract data type is that it encapsulates and enforces properties that we would otherwise have to stipulate in a precondition. For example, instead of a spec like this, with an elaborate precondition:</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/**
* <span class="hljs-doctag">@param</span> set1 is a sorted set of characters with no repeats
* <span class="hljs-doctag">@param</span> set2 is likewise
* <span class="hljs-doctag">@return</span> characters that appear in one set but not the other,
* in sorted order with no repeats
*/</span>
<span class="hljs-function"><span class="hljs-keyword">static</span> String <span class="hljs-title">exclusiveOr</span><span class="hljs-params">(String set1, String set2)</span></span>;</code></pre>
<p>We can instead use an ADT that captures the desired property:</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/** <span class="hljs-doctag">@return</span> characters that appear in one set but not the other */</span>
<span class="hljs-function"><span class="hljs-keyword">static</span> SortedSet<Character> <span class="hljs-title">exclusiveOr</span><span class="hljs-params">(SortedSet<Character> set1, SortedSet<Character> set2)</span></span>;</code></pre>
<p>This is easier to understand, because the name of the ADT conveys all the programmer needs to know. It's also safer from bugs, because Java static checking comes into play, and the required condition (sorted with no repeats) can be enforced in exactly one place, the <code>SortedSet</code> type.</p>
<p>Many of the places where we used preconditions on the problem sets would have benefited from a custom ADT instead.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@vertical+block@vertical_Questions_dae6de9bb0a2" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_fff67ba8819a">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_fff67ba8819a" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/3e6443fb95285d2dc06e8ffc448b9bdf/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism.js"></script>
<script src="/assets/courseware/v1/2ba76f8bdfef4e2d45e31a3dc5208470/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-encapsulating-preconditions">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-encapsulating-preconditions" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_10-encapsulating-preconditions" class="problems-wrapper" role="group"
aria-labelledby="10-encapsulating-preconditions-problem-title"
data-problem-id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-encapsulating-preconditions" data-url="/courses/course-v1:MITx+6.005.1x+3T2016/xblock/block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-encapsulating-preconditions/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="10-encapsulating-preconditions-problem-title" aria-describedby="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-encapsulating-preconditions-problem-progress" tabindex="-1">
encapsulating preconditions in ADTs
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.1x+3T2016+type@problem+block@10-encapsulating-preconditions-problem-progress"></div>
<div class="problem">
<div>
<p>Consider this method:</p>
<pre class="code">
/**
* Find tweets written by a particular user.
*
* @param tweets a list of tweets with distinct timestamps, not modified by this method.
* @param username Twitter username (a nonempty sequence of letters, digits, and underscore)
* @return all and only the tweets in the list whose author is username,
* in the same order as in the input list.
*/
public static List&lt;Tweet&gt; writtenBy(List&lt;Tweet&gt; tweets, String username) { ... }
</pre>
<p>Which ADTs would you create to eliminate the preconditions of this method? Check all that apply.</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_10-encapsulating-preconditions_2_1">
<fieldset aria-describedby="status_10-encapsulating-preconditions_2_1">
<div class="field">
<input type="checkbox" name="input_10-encapsulating-preconditions_2_1[]" id="input_10-encapsulating-preconditions_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="10-encapsulating-preconditions_2_1-choice_0-label" for="input_10-encapsulating-preconditions_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_10-encapsulating-preconditions_2_1"> TweetsAndUsername
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-encapsulating-preconditions_2_1[]" id="input_10-encapsulating-preconditions_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="10-encapsulating-preconditions_2_1-choice_1-label" for="input_10-encapsulating-preconditions_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_10-encapsulating-preconditions_2_1"> TweetList
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-encapsulating-preconditions_2_1[]" id="input_10-encapsulating-preconditions_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="10-encapsulating-preconditions_2_1-choice_2-label" for="input_10-encapsulating-preconditions_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_10-encapsulating-preconditions_2_1"> Username
</label>
</div>
<div class="field">
<input type="checkbox" name="input_10-encapsulating-preconditions_2_1[]" id="input_10-encapsulating-preconditions_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="10-encapsulating-preconditions_2_1-choice_3-label" for="input_10-encapsulating-preconditions_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_10-encapsulating-preconditions_2_1"> UsernameCharacter
</label>
</div>
<span id="answer_10-encapsulating-preconditions_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_10-encapsulating-preconditions_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_10-encapsulating-preconditions_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="encapsulating preconditions in ADTs" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_10-encapsulating-preconditions" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_10-encapsulating-preconditions">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-encapsulating-preconditions-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-encapsulating-preconditions-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="10-encapsulating-preconditions-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@vertical+block@Reading_10_Summary" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Reading 10 Summary</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_e32aee528562">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="b226bd2c682f11ef86000214bd5530e3" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_e32aee528562" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<h2 id="summary">Summary</h2>
<div data-outline="summary">
<ul>
<li>An invariant is a property that is always true of an ADT object instance for the lifetime of the object.</li>
<li>A good ADT preserves its own invariants. Invariants must be established by creators and producers and preserved by observers and mutators.</li>
<li>The rep invariant specifies legal values of the representation and should be checked at runtime with <code>checkRep()</code>.</li>
<li>The abstraction function maps a concrete representation to the abstract value it represents.</li>
<li>Representation exposure threatens both representation independence and invariant preservation.</li>
</ul>
<p>The topics of today's reading connect to our three properties of good software as follows:</p>
<ul>
<li>
<p><strong>Safe from bugs.</strong> A good ADT preserves its own invariants, so that those invariants are less vulnerable to bugs in the ADT's clients, and violations of the invariants can be more easily isolated within the implementation of the ADT itself. Stating the rep invariant explicitly, and checking it at runtime with checkRep(), catches misunderstandings and bugs earlier, rather than continuing on with a corrupt data structure. </p>
</li>
<li>
<p><strong>Easy to understand.</strong> Rep invariants and abstraction functions explicate the meaning of a data type's representation and how it relates to its abstraction.</p>
</li>
<li>
<p><strong>Ready for change.</strong> Abstract data types separate the abstraction from the concrete representation, which makes it possible to change the representation without having to change client code. </p>
</li>
</ul>
</div>
<div class="license">This reading was collaboratively authored with contributions from: Saman Amarasinghe, Adam Chlipala, Srini Devadas, Michael Ernst, Max Goldman, John Guttag, Daniel Jackson, Rob Miller, Martin Rinard, and Armando Solar-Lezama. This work is licensed under <a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/">CC BY-SA 4.0</a>.</div>
</div>
</div>
</div>
</div>