<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-init="VerticalStudentView" data-graded="True" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-has-score="False" data-request-token="9b70f9f9682f11ef8c790e199eb5def5" data-runtime-version="1" data-block-type="vertical" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical-ps1-beta">
<h2 class="hd hd-2 unit-title">Problem Set 1</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_31dcf7c08a0c">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-init="XBlockToXModuleShim" data-graded="True" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-has-score="False" data-request-token="9b70f9f9682f11ef8c790e199eb5def5" data-runtime-version="1" data-block-type="html" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_31dcf7c08a0c">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/d93415c23438bb0217f0599a34bdff10/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<h1 class="handout-title col-sm-8 col-sm-offset-2">About the Problem Sets</h1>
<div>
<p>
Every problem set has two submission points: a beta submission and a final submission. The initial release of the problem set (e.g., this page about Problem Set 1) includes tests for the beta submission. After the beta deadline passes, additional tests will be released for you to download from edX. You can then run these final tests against your solution, fix any new problems that are found, and then submit your revised program for the final deadline.
</p>
<p>
For the problem sets, all the test cases are given to you, and you'll run the tests on your own machine before uploading your problem set, so you'll always know which tests are passing and which are failing before you submit. There are no hidden tests for the problem sets. You'll get checked off for the beta submission if it passes most of the beta tests (typically at least 80-85%), and you'll get checked off for the final submission if it passes most of the beta + final tests.
</p>
<h2>Install Java</h2>
<p>Java version 8 is required for this course. Don't just use whatever Java might already be installed on your system. Please install version 8.</p>
<ol>
<li>
<p>Go to the <a href="http://www.oracle.com/technetwork/java/javase/downloads/index.html" target="_install">Java JDK version 8 installation page</a>, and download and install the JDK for your platform. First click on the download button for Java Platform (JDK):</p>
<p><img style="width:200px" src="/assets/courseware/v1/d17c464d8a5899afb1a5aba0532cd96d/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/eclipse-setup-get-to-java-download.png" alt="Java Platform download button"></p>
<p>Find the first "Java SE Development Kit 8" section on the installation page. It doesn't matter whether you install 8u101, 8u102, or some other number, as long as it's 8. Then choose the right download for your computer's operating system:</p>
<p><img src="/assets/courseware/v1/d8f1a6d3ff342d61c3991d126d788600/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/eclipse-setup-java-download.png" alt="Java download choices"></p>
<p>For Windows, you have two choices: Windows x86 (which is for <strong>32-bit</strong> Windows) and Windows x64 (which means <strong>64-bit</strong>). If you aren't sure which one you have, see <a href="http://www.howtogeek.com/howto/21726/how-do-i-know-if-im-running-32-bit-or-64-bit-windows-answers/" target="_otherhelp">How Do I Know if I’m Running 32-bit or 64-bit Windows?</a>. If that page doesn't help, then choose Windows x86, because it works on both 32-bit and 64-bit Windows, just a little slower.</p>
<p>You don't need any of the other downloads on that page, like demos, samples, NetBeans, or Java EE. Just install Java SE Development Kit.</p>
</li>
<li>
<p>After downloading the Java installer, run it and follow the prompts to install Java on your computer.</p>
</li>
</ol>
<h2>Install Eclipse</h2>
<ol>
<li>
<p>Go to the <a href="http://www.eclipse.org/downloads/" target="_install">Eclipse Download page</a> and click on the orange Download button to get the latest Eclipse release for your platform. The latest version in 2016 is called Eclipse Neon.</p>
</li>
<li>
<p>After downloading the installer, run the installer. It will give you a choice like this:</p>
<p><img src="/assets/courseware/v1/53860a24378546855f2dae1b5b7049a7/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/eclipse-setup-which-eclipse.png" alt="Eclipse installer choices"></p>
<p>Choose the first option, Eclipse IDE for Java Developers, and follow the prompts to install Eclipse on your computer.</p>
</li>
<li>
<p>Run Eclipse. The first time you run it, Eclipse will ask where you want to put your workspace, which is where all your Java files will be stored. You can just accept its suggestion, and check "Use this as the default and do not ask again":</p>
<p><img src="/assets/courseware/v1/280b4dea3dd98bcb327da75f2082baee/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/eclipse-setup-workspacelauncher.png" alt="Workspace Launcher dialog box that appears when Eclipse starts"></p>
</li>
<li>
<p>Finally the Eclipse window will appear, with a Welcome tab showing:</p>
<p><img src="/assets/courseware/v1/3f83df8240f61d79290235f9c5697389/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/eclipse-setup-welcome.png" alt="Welcome tab that appears when Eclipse starts"></p>
<p>Close this Welcome tab, either using the X next to Welcome, or using the Workbench button in the upper right, so that you get to the Eclipse workbench:</p>
<p><img src="/assets/courseware/v1/9d3eb35b94e7d4c5a8ffdb321ec9aaf2/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/eclipse-setup-workbench.png" alt="Eclipse Workbench "></p>
</li>
</ol>
<h2 id="config-eclipse">Configure Eclipse</h2>
<div data-outline="config-eclipse">
<p>Eclipse is a powerful, flexible, and occasionally frustrating set of tools for developing and debugging programs, especially in Java.</p>
<blockquote><em style="font-size: 70%">Note: if you prefer, you can do the problem sets in another Java development environment, or using command-line tools. The problem sets require compiling Java, running JUnit, and running Ant, so if you know how to do those things some other way, go for it. The rest of these instructions will talk only about using Eclipse.</em></blockquote>
<p>When you run Eclipse, you will be prompted for a "workspace" directory, where Eclipse will store its configuration and metadata. The default location is a directory called <code>workspace</code> in your home directory. You should not run more than one copy of Eclipse at the same time with the same workspace.</p>
<p>On the left side of your Eclipse window is the Package Explorer, which shows you all the projects in your workspace.</p>
<ol>
<li>
<p>Open Eclipse preferences.</p>
<p><strong>Windows & Linux</strong>: go to <em>Window → Preferences</em>.</p>
<p><strong>OS X</strong>: go to <em>Eclipse → Preferences</em>.</p>
</li>
<li>
<p>Make sure Eclipse is configured to use <strong>Java 8</strong>.</p>
<ol style="list-style-type: lower-alpha;">
<li>
<p>In preferences, go to <em>Java → Installed JREs</em>. Ensure that "Java SE 8" or "JDK 1.8.0_71" is the only one checked. If it’s not listed, click Search.</p>
</li>
<li>
<p>Go to <em>Java → Compiler</em> and set "Compiler compliance level" to 1.8. Click OK and Yes on any prompts.</p>
</li>
</ol>
</li>
<li>
<p>Make sure <strong>assertions are always on</strong>. Assertions are a great tool for keeping your code safe from bugs, but Java has them off by default.</p>
<p>In preferences, go to <em>Java → Installed JREs</em>. Click "Java SE 8", click "Edit…", and in the "Default VM arguments" box enter: <code>-ea</code> (which stands for <em>enable assertions</em>).</p>
</li>
<li>
<p>Make sure your <strong>Eclipse workspace refreshes automatically</strong> whenever files are changed on the filesystem. This will be important when you run the grader script, so that you see the output files it generates.</p>
<p>In preferences, go to <em>General → Workspace</em>. Turn on both checkboxes that talk about refresh: "Refresh using native hooks or polling" and "Refresh on access."</p>
</li>
<li>
<p><strong>Tabs</strong>. If you configure the editor to use spaces instead of tabs, then your code will look the same in all editors regardless of how that editor displays tab characters.</p>
<p>In preferences, go to <em>Java → Code Style → Formatter</em>. Click the "Edit…" button next to the active profile. In the new window, change the Tab policy to "Spaces only." Keep the Indentation size and Tab size at 4. To save your changes, enter a new "Profile name" at the top of the window and click OK.</p>
</li>
</ol>
</div>
<h2 id="import">Download and Import the Problem Set Code</h2>
<div data-outline="import">
<ol>
<li>
<p>Download the starting code for this problem set:</p>
<blockquote>
<a href="/assets/courseware/v1/3d78f893ff6c225735235bfe50aa99a0/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/ps1.zip">ps1.zip</a>
</blockquote>
</li>
<li>
<p>Import the code into Eclipse:</p>
<ol style="list-style-type: lower-alpha;">
<li>In the Eclipse menubar, choose File → Import...</li>
<li>In the Select dialog, open General and choose Existing Projects Into Workspace.</li>
<li>In the Import Projects dialog, choose Select archive file, then click Browse and use the
file dialog to find where you downloaded ps1.zip.</li>
<li>Still in the Import Projects dialog, make sure ps1-expressivo is listed in the Projects, and that the checkbox next to it is checked</li>
<li>On "Import projects," make sure ps1-expressivo is checked.
<blockquote>
If ps1-expressivo is grayed and uncheckable, then the likely reason is that ps1-expressivo already exists in your Package Explorer (perhaps because you are following these directions a second time). You need to cancel the import, delete or rename ps1-expressivo in your Package Explorer, and try the import again.
</blockquote>
</li>
<li>Click Finish. ps1-expressivo should now appear in your Package Explorer.</li>
</ol>
</li>
</ol>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_d60ee6b38772">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-init="XBlockToXModuleShim" data-graded="True" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-has-score="False" data-request-token="9b70f9f9682f11ef8c790e199eb5def5" data-runtime-version="1" data-block-type="html" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_d60ee6b38772">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/d93415c23438bb0217f0599a34bdff10/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" />
<style>
.userin {
color: #006600;
background: #eeffee;
}
.panel-default.pull-right.pull-margin {
font-size: 90%;
max-width: 33%;
}
.pull-margin, .panel.pull-margin, .panel.panel-figure.pull-right.pull-margin {
margin-right: -25%;
position: relative;
}
.panel.pull-right {
margin: 0 0 10px 10px;
}
.pull-right {
float: right!important;
}
.panel-default {
border-color: #ddd;
}
.panel-default.pull-right.pull-margin .panel-body {
padding: 8px;
}
.panel {
margin-bottom: 20px;
background-color: #fff;
border: 1px solid;
border-radius: 4px;
-webkit-box-shadow: 0 1px 1px rgba(0,0,0,.05);
box-shadow: 0 1px 1px rgba(0,0,0,.05);
}
</style>
<h1 class="handout-title col-sm-8 col-sm-offset-2" id="problem_set_0">Problem Set 1: Expressivo</h1>
<h2 id="overview">Overview</h2>
<div data-outline="overview"><p>Wouldn’t it be nice not to have to differentiate all our calculus homework by hand every time?
Wouldn’t it be just lovely to type it into a computer and have the computer do it for us instead?
For example, we could interact with it like this (user input in <span class="userin no-markdown">green</span>):</p><div class="panel panel-default pull-right pull-margin"><div class="panel-body"><p>If the output is an expression, your system may output an equivalent expression, including variations in spacing, parentheses, simplification, and number representation.</p>
<p>If a number, your system may output an equivalent number, accurate to at least 4 decimal places.</p></div></div><pre class="no-markdown">> <span class="userin">x * x * x</span>
x*x*x
> <span class="userin">!simplify x=2</span>
8
> <span class="userin">!d/dx</span>
(x*x)*1+(x*1+1*x)*x
> <span class="userin">!simplify x=0.5000</span>
.75
> <span class="userin">x * y</span>
x*y
> <span class="userin">!d/dy</span>
0*y+x*1
</pre><p>In this system, a user can enter either an <strong>expression</strong> or a <strong>command</strong>.</p><p>An <em>expression</em> is a polynomial consisting of:</p><ul>
<li><code>+</code> and <code>*</code> (for addition and multiplication)</li>
<li>nonnegative numbers in decimal representation, which consist of digits and an optional decimal point (e.g. <code>7</code> and <code>4.2</code>)</li>
<li>variables, which are case-sensitive nonempty sequences of letters (e.g. <code>y</code> and <code>Foo</code>)</li>
<li>parentheses (for grouping)</li>
</ul><p>Order of operations uses the standard <a href="https://en.wikipedia.org/wiki/Order_of_operations#Mnemonics">PEMDAS</a> rules.</p><p>Space characters around symbols are irrelevant and ignored, so <code>2.3*pi</code> means the same as <code>2.3 * pi</code>. Spaces may not occur within numbers or variables, so <code>2 . 3 * p i</code> is not a valid expression.</p><p>When the user enters an expression, that expression becomes the <strong>current expression</strong> and is echoed back to the user (user input in <span class="userin no-markdown">green</span>):</p><div class="panel panel-default pull-right pull-margin"><div class="panel-body"><p>If the output is an expression, your system may output an equivalent expression, including variations in spacing, parentheses, simplification, and number representation.</p>
<p>If a number, your system may output an equivalent number, accurate to at least 4 decimal places.</p></div></div><pre class="no-markdown">> <span class="userin">x * x * x</span>
x*x*x
> <span class="userin">x + x * x * y + x</span>
x + x*x*y + x
</pre><p>A <em>command</em> starts with <code>!</code>.
The command operates on the current expression, and may also update the current expression.
Valid commands:</p><blockquote>
<p><strong><code class="no-markdown">d/d<em>var</em></code></strong> <br>
produces the derivative of the current expression with respect to the variable <em>var</em>, and updates the current expression to that derivative</p>
<p><strong><code class="no-markdown">simplify <em>var<sub>1</sub></em>=<em>num<sub>1</sub></em> ... <em>var<sub>n</sub></em>=<em>num<sub>n</sub></em></code></strong> <br>
substitutes <em class="no-markdown">num<sub>i</sub></em> for <em class="no-markdown">var<sub>i</sub></em> in the current expression, and evaluates it to a single number if the expression contains no other variables; does <strong>not</strong> update the current expression</p>
</blockquote><p>Entering an invalid expression or command prints an error but does not update the current expression.
The error should include a human-readable message but is not otherwise specified.</p><p>More examples:</p><div class="panel panel-default pull-right pull-margin"><div class="panel-body"><p>If the output is an expression, your system may output an equivalent expression, including variations in spacing, parentheses, simplification, and number representation.</p>
<p>If a number, your system may output an equivalent number, accurate to at least 4 decimal places.</p></div></div><pre class="no-markdown">> <span class="userin">x * x * x</span>
x*x*x
> <span class="userin">3xy</span>
ParseError: unknown expression
> <span class="userin">!d/dx</span>
(x*x)*1+(x*1+1*x)*x
> <span class="userin">!d/dx</span>
(x*x)*0+(x*1+1*x)*1+(x*1+1*x)*1+(x*0+1*1+x*0+1*1)*x
> <span class="userin">!d/d</span>
ParseError: missing variable in derivative command
> <span class="userin">!simplify</span>
(x*x)*0+(x*1+1*x)*1+(x*1+1*x)*1+(x*0+1*1+x*0+1*1)*x
> <span class="userin">!simplify x=1</span>
6.0
> <span class="userin">!simplify x=0 y=5</span>
0
</pre><p>The three things that a user can do at the console correspond to three provided method specifications in the code for this problem set:</p><ul>
<li><code>Expression.parse()</code></li>
<li><code>Commands.differentiate()</code></li>
<li><code>Commands.simplify()</code></li>
</ul><p>These methods are used by <code>Main</code> to provide the console user interface described above.</p><p><strong>Problem 1:</strong> we will create the <code>Expression</code> data type to represent expressions in the program.</p><p><strong>Problem 2:</strong> we will create the parser that turns a string into an <code>Expression</code>, and implement <code>Expression.parse()</code>.</p><p><strong>Problems 3-4:</strong> we will add new <code>Expression</code> operations for differentiation and simplification, and implement <code>Commands.differentiate()</code> and <code>Commands.simplify()</code>.</p><hr></div>
<h2 id="problem_1_representing_expressions">Problem 1: Representing Expressions</h2>
<div data-outline="problem_1_representing_expressions"><p>Define an immutable, recursive abstract data type to represent expressions as abstract syntax trees.</p><p>Your AST should be defined in the provided <code>Expression</code> interface (in <code>Expression.java</code>) and implemented by several concrete variants, one for each kind of expression.
Each variant should be defined in its own appropriately-named <code>.java</code> file.</p><p>Concrete syntax in the input, such as parentheses and whitespace, should not be represented at all in your AST. Parentheses should <i>not</i> have corresponding <code>Expression</code> variants, and should <i>not</i> be stored explicitly in the reps of any <code>Expression</code> variant. Instead, the structure of the AST should represent the order of operations directly.</p><h4>1.1 <code>Expression</code></h4><p>To repeat, your data type must be <strong>immutable</strong> and <strong>recursive</strong>.
Follow the recipe for creating an ADT:</p><ul>
<li><strong>Spec</strong>.
Choose and specify operations.
For this part of the problem set, the only operations <code>Expression</code> needs are creators and producers for building up an expression, plus the standard observers <code>toString()</code>, <code>equals()</code>, and <code>hashCode()</code>.
We are strengthening the specs for these standard methods; see below.</li>
<li><strong>Test</strong>.
Partition and test your operations in <code>ExpressionTest.java</code>, including tests for <code>toString()</code>, <code>equals()</code>, and <code>hashCode()</code>.
Note that we will not run your test cases on other implementations, just on yours.</li>
<li><strong>Code</strong>.
Write the rep for your <code>Expression</code> as a <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-recursive_datatype_definitions">data type definition</a> in a comment inside <code>Expression</code>.
Implement the variant classes of your data type.</li>
</ul><p>Remember to include a Javadoc comment above every class and every method you write; define abstraction functions and rep invariants, and write checkRep; and document safety from rep exposure.</p><h4>1.2 <code>toString()</code></h4><p>Define the <code>toString()</code> operation on <code>Expression</code> so it can output itself as a string.
This string must be a valid expression as defined above.
You have the freedom to decide how to format the output with whitespace and parentheses for readability, but the expression must have the same mathematical meaning.</p><p>Your <code>toString()</code> implementation must be recursive, and must not use <code>instanceof</code>.</p><p>Use the <code>@Override</code> annotation to ensure you are overriding the <code>toString()</code> inherited from <code>Object</code>.</p><p>Remember that your tests must obey the spec. If your <code>toString()</code> tests expect a certain formatting of whitespace and parentheses, you must specify this formatting in your spec.</p><h4>1.3 <code>equals()</code> and <code>hashCode()</code></h4><p>Define the <code>equals()</code> and <code>hashCode()</code> operations on your AST to implement <em>structural equality</em>.</p><p><strong>Structural equality</strong> defines two expressions to be equal if:</p><ol>
<li>the expressions contain the same variables, numbers, and operators;</li>
<li>those variables, numbers, and operators are in the same order, read left-to-right;</li>
<li>and they are grouped in the same way.</li>
</ol><p>For example, the AST for <code>1 + x</code> is <em>not</em> equal to the AST for <code>x + 1</code>, but it is equal to the ASTs for <code>1+x</code>, <code>(1+x)</code>, and <code>(1)+(x)</code>.</p><p>For <em>n</em>-ary groupings where <em>n</em> is greater than 2:</p><ul>
<li>Such expressions must be equal to themselves.
For example, the ASTs for <code>3 + 4 + 5</code> and <code>(3 + 4 + 5)</code> must be equal.</li>
<li>However, whether they are equal or not to different groupings with the same mathematical meaning is <em>not specified</em>, and you should choose an appropriate specification and implementation for your AST.
For example, you must determine whether the ASTs for <code>(3 + 4) + 5</code> and <code>3 + (4 + 5)</code> are equal.</li>
</ul><p>For equality of numbers, you have the freedom to choose a reasonable definition.
Integers that can be represented exactly as a <code>double</code> should be considered equal.
For example, the ASTs for <code>x + 1</code> and <code>x + 1.000</code> must be equal.</p><p>Remember: concrete syntax, including parentheses, should not be represented in your AST.
Grouping, for example, should be reflected in the AST’s structure.</p><p>Be sure that AST instances which are considered equal according to this definition and according to <code>equals()</code> also satisfy <a href="//courses.edx.org/courses/course-v1:MITx+6.005.1x+3T2016/jump_to_id/vertical-equality-of-immutable-types">observational equality</a>.</p><p>Your <code>equals()</code> and <code>hashCode()</code> implementations must be recursive. Only <code>equals()</code> can use <code>instanceof</code>, and <code>hashCode()</code> must not.</p><p>Remember to use the <code>@Override</code> annotation.</p><hr></div>
<h2 id="problem_2_parsing_expressions">Problem 2: Parsing Expressions</h2>
<div data-outline="problem_2_parsing_expressions"><p>Now we will create the parser that takes a string and produces an <code>Expression</code> value from it.
The entry point for your parser should be <code>Expression.parse()</code>, whose spec is provided in the starting code.</p><p>Examples of valid inputs:</p><pre><code>3 + 2.4
3 * x + 2.4
3 * (x + 2.4)
((3 + 4) * x * x)
foo + bar+baz
(2*x )+ ( y*x )
4 + 3 * x + 2 * x * x + 1 * x * x * (((x)))
</code></pre><p>Examples of invalid inputs:</p><pre><code>3 *
( 3
3 x
</code></pre><p>Examples of optional inputs:</p><pre><code>2 - 3
(3 * x) ^ 2
6.02e23
</code></pre><p>You may consider these inputs invalid, or you may choose to support additional features (new operators or number representations) in the input.
However, <em>your system may not produce an output with a new feature unless that feature appeared in its input</em>.
This way, a client who knows about your extensions can trigger them, but clients who don’t know won’t encounter them unexpectedly.</p><h4>2.1 Write a grammar</h4><p>Write a ParserLib grammar for polynomial expressions as described in the overview.
A starting ParserLib grammar file can be found in <code>src/expressivo/Expression.g</code>.
This starting grammar recognizes sums of integers, and ignores spaces.</p>
<p>See the reading on <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-parser-generators">parser generators</a> for more information about ParserLib.</p>
<p>The <a href="/assets/courseware/v1/1ef434a83e589f315a433298cef627c0/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/parserlib-api.pdf">API documentation for ParserLib</a> may also be helpful.</p>
<h4>2.2 Implement <code>Expression.parse()</code></h4><p>Implement <code>Expression.parse()</code> by following the recipe:</p><ul>
<li><strong>Spec</strong>.
The spec for this method is given, but you may strengthen it if you want to make it easier to test.</li>
<li><strong>Test</strong>.
Write tests for <code>Expression.parse()</code> and put them in <code>ExpressionTest.java</code>.
Note that we will not run your tests on any implementations other than yours.</li>
<li><strong>Code</strong>.
Implement <code>Expression.parse()</code> so that it calls the parser generated by your ParserLib grammar.
The reading on <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-parser-generators">parser generators</a> discusses how to call the parser and construct an abstract syntax tree from it, including code examples.</li>
</ul><p>A general note on precision: you are only required to handle nonnegative decimal numbers in the range of the <a href="http://docs.oracle.com/javase/8/docs/api/?java/lang/Double.html"><code>double</code></a> type.</p><h4>2.3 Run the console interface</h4><p>Now that <code>Expression</code> values can be both parsed from strings with <code>parse()</code>, and converted back to strings with <code>toString()</code>, you can try entering expressions into the console interface.</p><p>Run <code>Main</code>.
In Eclipse, the Console view will allow you to type expressions and see the result.
Try some of the expressions from the top of this handout.</p><hr></div>
<h2 id="problem_3_differentiation">Problem 3: Differentiation</h2>
<div data-outline="problem_3_differentiation"><p>The symbolic differentiation operation takes an expression and a variable, and produces an expression with the derivative of the input with respect to the variable.
The result does not need to be simplified.</p><div class="panel panel-default pull-right pull-margin"><div class="panel-body"><p>If the output is an expression, your system may output an equivalent expression, including variations in spacing, parentheses, simplification, and number representation.</p>
<p>If a number, your system may output an equivalent number, accurate to at least 4 decimal places.</p></div></div><p>For example, the following are correct derivatives :</p><blockquote>
<p><strong><code>x*x*x</code></strong> with respect to <strong><code>x</code></strong> <br>
<code>3 * x * x</code></p>
<p><strong><code>x*x*x</code></strong> with respect to <strong><code>x</code></strong> <br>
<code>x*x + (x + x)*x</code></p>
<p><strong><code>x*x*x</code></strong> with respect to <strong><code>x</code></strong> <br>
<code>( ( x*x )*1 )+( ( ( x*1 )+( 1*x ) )*x )+( 0 )</code></p>
</blockquote><p>Incorrect derivatives:</p><blockquote>
<p><strong><code>y*y*y</code></strong> with respect to <strong><code>y</code></strong> <br>
<code>3*y^2</code> <em>uses unexpected operator</em></p>
<p><strong><code>y*y*y</code></strong> with respect to <strong><code>y</code></strong> <br>
<code>0</code> <em>d/dx, should be d/dy</em></p>
</blockquote><p>To implement your recursive differentiation operation, use these rules:</p><table style="width:100%; text-align:center;" class="no-markdown"><tbody><tr>
<td width="15%"><img src="/assets/courseware/v1/803ad999ccbdd1111a4b6d64af061975/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/ps1-rule0.png"></td>
<td width="15%"><img src="/assets/courseware/v1/c4be05eb4fabee219d4e738b7fa48517/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/ps1-rule1.png"></td>
<td width="35%"><img src="/assets/courseware/v1/e12d1c631c00f99458e18b0d8e1388a8/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/ps1-rule2.png"></td>
<td width="35%"><img src="/assets/courseware/v1/60f8fdb42f965c5c97cfb959207831dc/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/ps1-rule3.png"></td>
</tr></tbody></table><p>where <em>c</em> is a constant or variable other than the variable we are differentiating with respect to (in this case <em>x</em>), and <em>u</em> and <em>v</em> can be anything, including <em>x</em>.</p><h4>3.1. Add an operation to <code>Expression</code></h4><p>You should implement differentiation as a method on your <code>Expression</code> datatype, defined recursively.
The signature and specification of the method are up to you to design.
Follow the recipe:</p><ul>
<li><strong>Spec</strong>.
Define your operation in <code>Expression</code> and write a spec.</li>
<li><strong>Test</strong>.
Put your tests in <code>ExpressionTest.java</code>.
Note that we will not run your test cases on other implementations, just on yours.</li>
<li><strong>Code</strong>.
The implementation must be recursive.
It must not use <code>instanceof</code>, nor any equivalent operation you have defined that checks the type of a variant.</li>
</ul><h4>3.2 Implement <code>Commands.differentiate()</code></h4><p>In order to connect your differentiation operation to the user interface, we need to implement the <code>Commands.differentiate()</code> method.</p><ul>
<li><strong>Spec</strong>.
The spec for this operation is given, but you may strengthen it if you want to make it easier to test.</li>
<li><strong>Test</strong>.
Write tests for <code>differentiate()</code> and put them in <code>CommandsTest.java</code>.
These tests will likely be very similar to the tests you used for your lower-level differentiation operation, but they must use <code>Strings</code> instead of <code>Expression</code> objects.
Note that we will not run your tests on any implementations other than yours.</li>
<li><strong>Code</strong>.
Implement <code>differentiate()</code>.
This should be straightforward: simply parsing the expression, calling your differentation operation, and converting it back to a string.</li>
</ul><h4>3.3 Run the console interface</h4><p>We’ve now implemented the <code>!d/d</code> command in the console interface.
Run <code>Main</code> and try some derivatives in the Console view.</p><hr></div>
<h2 id="problem_4_simplification">Problem 4: Simplification</h2>
<div data-outline="problem_4_simplification"><p>The simplification operation takes an expression and an environment (a mapping of variables to values).
It substitutes the values for those variables into the expression, and attempts to simplify the substituted polynomial as much as it can.</p><p>The set of variables in the environment is allowed to be different than the set of variables actually found in the expression.
Any variables in the expression but not the environment remain as variables in the substituted polynomial.
Any variables in the environment but not the expression are simply ignored.</p><p>The only required simplification is that if the substituted polynomial is a constant expression, with no variables remaining, then simplification must reduce it to a single number, with no operators remaining either.
Simplification for substituted polynomials that still contain variables is underdetermined, left to the implementer’s discretion.
You may strengthen this spec if you wish to require particular simplifications in other cases.</p><div class="panel panel-default pull-right pull-margin"><div class="panel-body"><p>If the output is an expression, your system may output an equivalent expression, including variations in spacing, parentheses, simplification, and number representation.</p>
<p>If a number, your system may output an equivalent number, accurate to at least 4 decimal places.</p></div></div><p>For example, the following are correct output for simplified expressions:</p><blockquote>
<p><strong><code>x*x*x</code></strong> with environment <strong><code>x=5</code>, <code>y=10</code>, <code>z=20</code></strong> <br>
<code>125</code></p>
<p><strong><code>x*x*x + y*y*y</code></strong> with environment <strong><code>y=10</code></strong> <br>
<code>x*x*x+10*10*10</code></p>
<p><strong><code>x*x*x + y*y*y</code></strong> with environment <strong><code>y=10</code></strong> <br>
<code>x*x*x+1000</code></p>
<p><strong><code>1+2*3+8*0.5</code></strong> with empty environment <br>
<code>11.000</code></p>
</blockquote><p>Incorrect simplified expressions:</p><blockquote>
<p><strong><code>x*x*y</code></strong> with environment <strong><code>x=1</code>, <code>y=3</code></strong> <br>
<code>1*1*3</code> <em>not a single number</em></p>
<p><strong><code>x*x*x</code></strong> with environment <strong><code>x=2</code></strong> <br>
<code>(8)</code> <em>includes parentheses</em></p>
<p><strong><code>x*x*x</code></strong> with empty environment <br>
<code>x^3</code> <em>uses unexpected operator</em></p>
</blockquote><p>Optional simplified expressions:</p><blockquote>
<p><strong><code>x*x*y + y*(1+x)</code></strong> with environment <strong><code>x=2</code></strong> <br>
<code>7*y</code></p>
<p><strong><code>x*x*x + x*x*x</code></strong> with empty environment <br>
<code>2*x*x*x</code></p>
</blockquote><h4>4.1 Add an operation to <code>Expression</code></h4><p>You should implement simplification as a method on your <code>Expression</code> datatype, defined recursively.
The signature and specification of the method are up to you to design.
Follow the recipe:</p><ul>
<li><strong>Spec</strong>.
Define your operation in <code>Expression</code> and write a spec.</li>
<li><strong>Test</strong>.
Put your tests in <code>ExpressionTest.java</code>.
Note that we will not run your test cases on other implementations, just on yours.</li>
<li><strong>Code</strong>.
The implementation must be recursive (perhaps by calling recursive helper methods).
It must not use <code>instanceof</code>, nor any equivalent operation you have defined that checks the type of a variant class.</li>
</ul><p>You may find it useful to add more operations to <code>Expression</code> to help you implement the simplify operation.
Spec/test/code them using the same recipe, and make them recursive as well where appropriate.
Your helper operations should not simply be a variation on using <code>instanceof</code> to test for a variant class.</p><h4>4.2 <code>Commands.simplify()</code></h4><p>In order to connect your simplify operation to the user interface, we need to implement the <code>Commands.simplify()</code> method.</p><ul>
<li><strong>Spec</strong>.
The spec for this operation is given, but you may strengthen it if you want to make it easier to test.</li>
<li><strong>Test</strong>.
Write tests for <code>simplify()</code> and put them in <code>CommandsTest.java</code>.
These tests will likely be very similar to the tests you used for your lower-level simplify operation, but they should use <code>Strings</code> instead of <code>Expression</code> objects.
Note that we will not run your tests on any implementations other than yours.</li>
<li><strong>Code</strong>.
Implement <code>simplify()</code>.
This should be straightforward: simply parsing the expression, calling your simplify operation, and converting it back to a string.</li>
</ul><h4>4.3 Run the console interface</h4><p>We’ve now implemented the <code>!simplify</code> command in the console interface.
Run <code>Main</code> and try using it in the Console view.</p><p><hr></div>
<h2 id="before_youre_done">Before you’re done</h2>
<div data-outline="before_youre_done"><ul>
<li><p>Make sure you have <strong>documented specifications</strong>, in the form of properly-formatted Javadoc comments, for all your types and operations.</p></li>
<li><p>Make sure you have <strong>documented abstraction functions and representation invariants</strong>, in the form of a comment near the field declarations, for all your implementations.</p>
<p>With the rep invariant, also say how the type prevents rep exposure.</p>
<p>Make sure all types use <code>checkRep()</code> to check the rep invariant and implement <code>toString()</code> with a useful representation of the abstract value.</p></li>
<li><p>Make sure you have satisfied the <strong><a href="//courses.edx.org/courses/course-v1:MITx+6.005.1x+3T2016/jump_to_id/vertical-equality-of-immutable-types#the_object_contract">Object contract</a></strong> for all types. In particular, you will need to specify, test, and implement <code>equals()</code> and <code>hashCode()</code> for all immutable types.</p></li>
<li><p>Use <a href="http://docs.oracle.com/javase/tutorial/java/annotations/predefined.html"><code>@Override</code></a> when you override <code>toString()</code>, <code>equals()</code>, and <code>hashCode()</code>, to gain static checking of the correct signature. </p>
<p>Also use <code>@Override</code> when a class implements an interface method, to remind readers where they can find the spec.</p></li>
<li><p>Make sure you have a thorough, principled <strong>test suite</strong> for every type.
Note that <code>Expression</code>’s variant classes are considered part of its rep, so a single good test suite for <code>Expression</code> covers the variants too.</p></li>
</ul><hr></div>
<h2 id="autograder">Run the Autograder</h2>
<div data-outline="autograder">
<p>Once your implementation is passing all your own tests, you need to run the automatic grader. The autograder is the file <code>grader.xml</code> in your project. It is written as an Ant script, where <a href="http://ant.apache.org/">Ant</a> is an example of a <em>build management tool</em>, a kind of tool commonly used in software development to compile code, run tests, and package up code for deployment. Our autograder script does all three of these things. Support for running Ant scripts is built into Eclipse.</p>
<p>To run the automatic grader, right click on <code>grader.xml</code> in the Package Explorer, and choose <em>Run As → Ant Build</em>. Choose the plain <em>Ant Build</em> rather than <em>Ant Build...</em>, because you don't need all the options that the Ant Build... dialog box will offer you.</p>
<p>The grading script will run and display output in the Console tab. At the end, it should tell you that it has created two new files: <code>my-grader-report.xml</code>, which is the result of running the grading tests, and <code>my-submission.zip</code>, which is your problem set code and grader output packaged up and ready for submission to edX.</p>
<blockquote><em style="font-size: 70%">Note: if automatic workspace refreshing is not working for some reason, then <code>my-grader-report.xml</code> and <code>my-submission.zip</code> may not immediately appear in the Eclipse Package Explorer. Try refreshing the project manually by right-clicking on <code>ps1-warmup</code> and choosing <em>Refresh</em>. Then you should see the files appear. If they still aren't there, check the Console tab for errors.</em></blockquote>
<p>To view your autograder results, double-click on <code>my-grader-report.xml</code>, and you will see the results in your JUnit pane. The <code>my-grader-report.xml</code> file is simply the output of running JUnit on the autograder's tests. For now (Problem Set Beta 1), the autograder tests are identical to the tests you've already been using in QuadraticTest.java, so you should see exactly the same tests passing or failing that you see when you ran JUnit yourself as in the previous section. On future problem sets, the autograder will run different tests.</p>
<p>You can change your code and rerun the autograder as often as you want. You have to double-click on <code>my-grader-report.xml</code> each time to see the newest results. You don't need to Refresh the project each time, however. Once <code>my-grader-report.xml</code> is visible in the Package Explorer, Eclipse will load the latest version whenever you click on it.</p>
</div>
<h2 id="submit">Submit the Beta version of your Problem Set</h2>
<div data-outline="submit">
<p>After the autograder runs, it produces <code>my-submission.zip</code> in your Eclipse project. This zip file contains your code and your grading report. To get credit for the problem set, you need to upload this zip file to edX before the deadline.</p>
<p>The Problem Set Beta 1 submission page is the last section of this handout. To find it, click the rightmost button on the section bar at the top of this page:</p>
<p style="text-align: center"><img style="width:50%" src="/assets/courseware/v1/9bc277bfebc84a58bf5ae1eef6779527/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/pset-submission-page.png" alt="problem set submission page"></p>
</div>
</div>
</div>
</div>
</div>