-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathchapter7.html
More file actions
66 lines (55 loc) · 46.5 KB
/
chapter7.html
File metadata and controls
66 lines (55 loc) · 46.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
<!DOCTYPE html>
<html>
<head>
<title>L.B.Stanza</title>
<link type="text/css" rel="stylesheet" href="resources/mainstyle.css">
<link type="text/css" rel="stylesheet" href="resources/documentation.css">
</head>
<body>
<table class="wrap">
<tr><td colspan="3" class="banner">
<a href="index.html">Home</a><a href="stanzabyexample.html">Table of Contents</a><a href="chapter6.html">Previous Chapter</a><a href="chapter8.html">Next Chapter</a>
</td></tr>
<tr>
<td class="nav">
<h1>NAVIGATION</h1>
<h2><a href="#anchor270">Programming with Immutable Datastructures</a></h2><h3><a href="#anchor68">Lists</a></h3><h4><a href="#anchor271">Fundamental Operations</a></h4><h3><a href="#anchor69">Example: Coin Counting</a></h3><h4><a href="#anchor272">Strange Lands</a></h4><h4><a href="#anchor273">SICP</a></h4><h3><a href="#anchor70">List Library</a></h3><h4><a href="#anchor274">get</a></h4><h4><a href="#anchor275">headn</a></h4><h4><a href="#anchor276">tailn</a></h4><h4><a href="#anchor277">reverse</a></h4><h4><a href="#anchor278">last</a></h4><h4><a href="#anchor279">but-last</a></h4><h4><a href="#anchor280">map</a></h4><h3><a href="#anchor71">Example: More Coin Counting</a></h3><h4><a href="#anchor281">Readable Combos</a></h4><h3><a href="#anchor72">Extended Example: Automatic Differentiation</a></h3><h4><a href="#anchor282">Symbols</a></h4><h4><a href="#anchor283">The Expression Datastructure</a></h4><h4><a href="#anchor284">Printing an Expression</a></h4><h4><a href="#anchor285">Handling Precedence</a></h4><h4><a href="#anchor286">Operator Overloading</a></h4><h4><a href="#anchor287">The Differentiation Algorithm</a></h4><h4><a href="#anchor288">Simplification</a></h4><h4><a href="#anchor289">Program Listing</a></h4><h4><a href="#anchor290">Exercises</a></h4>
</td>
<td class="main">
<h1 id="anchor270">Programming with Immutable Datastructures</h1><p>An immutable datastructure is one that cannot be <span style="font-style:italic;">changed</span> after it has been created. Some examples you've already seen are strings, tuples, numbers, and true and false. In constrast, a <span style="font-style:italic;">mutable</span> datastructure is one that can be changed after it has been created. Some examples are arrays, vectors, and sequences. </p><p>If something is guaranteed not to change, then there are two details that you no longer have to worry about.</p><ol><li>You don't have to care about <span style="font-style:italic;">which</span> object it is. There is no difference between the value <code>42</code> and the value <code>20 + 22</code>. They are the same value. You can replace every occurrence of <code>42</code> in your program with <code>20 + 22</code> and it will still behave the same way. Similarly, you can replace every occurrence of
<pre><code>"Timon and Pumbaa"</code></pre>
in your program with
<pre><code>append("Timon", " and Pumbaa")</code></pre>
without changing its behaviour.
In contrast, consider the following call for adding a number to a vector.
<pre><code>add(xs, 42)</code></pre>
Now you <span style="font-style:italic;">do</span> need to pay very close attention to which vector <code>xs</code> is referring to. It would be an error to add 42 to the wrong vector.
</li><li>You don't have to think about <span style="font-style:italic;">when</span> to do something to an object. Consider the following code for popping an item from the vector <code>xs</code> and then adding two new items to it.
<pre><code>pop(xs)<br>add(xs, 42)<br>add(xs, 43)</code></pre>
The ordering of those expressions are critically important. Every possible ordering of those three expressions results in a different behaviour. Notice that this sort of thinking is never done with strings, tuples, or numbers; simply because there's nothing than <span style="font-style:italic;">can</span> be done to them except to create new objects out of them.
</li></ol> <h2 id="anchor68">Lists</h2><p>A <code>List</code> object represents a singly linked list of objects. A list is Stanza's most basic immutable datastructure and cannot be changed once created. Here is how to create an empty list.</p><pre><code>List()</code></pre><p>Here is how to create a list containing a single item.</p><pre><code>List(42)</code></pre><p>Here is how to create a list containing two items.</p><pre><code>List(42, "Timon")</code></pre><p>This works for lists containing up to four items. For creating lists containing more than four items, you may use the <code>to-list</code> function to convert sequences into lists.</p><pre><code>to-list([1, 2, 3, 4, 5, "Timon", "and", "Pumbaa"])</code></pre><p>You may also use <code>cons</code> (short for construct) to create a new list by tacking a new item to the beginning of an existing list.</p><pre><code>val xs = List(1, 2, 3)<br>val ys = cons(42, xs)</code></pre><p><code>cons</code> allows you to tack on up to three items.</p><pre><code>val xs = List(1, 2, 3)<br>val ys0 = cons(42, xs)<br>val ys1 = cons(42, 43, xs)<br>val ys2 = cons(42, 43, 44, xs)</code></pre><p>To append more than three items to the beginning of another list, use the <code>append</code> function.</p><pre><code>val xs = List(1, 2, 3)<br>val ys = append([42, 43, 44, 45, 46, 47], xs)<br>println(ys)</code></pre><p>Compiling and running the above prints out</p><pre><code>(42 43 44 45 46 47 1 2 3)</code></pre><h3 id="anchor271">Fundamental Operations</h3><p>A list is defined by three fundamental operations.</p><ol><li>You can check whether the list is empty.
</li><li>You can retrieve the first element in the list.
</li><li>You can retrieve a list containing all the elements after the first one.
</li></ol><p>Assuming that <code>xs</code> is a list, here is how to check whether <code>xs</code> is empty.</p><pre><code>empty?(xs)</code></pre><p>Here is how to retrieve the first element in <code>xs</code>.</p><pre><code>head(xs)</code></pre><p>And here is how to retrieve all the elements after the first one, as another list.</p><pre><code>tail(xs)</code></pre><h2 id="anchor69">Example: Coin Counting</h2><p>Suppose you have access to pennies, nickels, dimes, quarters, and <span style="font-style:italic;">loonies</span>, and the poutine you bought costs $1.17. (Loonies are Canadian coins worth 100 cents each.) How may different combinations of coins are there that total up to $1.17? </p><p>Here is our algorithm for calculating it. <code>num-coin-combos</code> takes two arguments: <code>cents</code>, which represents the amount of money you wish to make represented in cents, and <code>coins</code>, a list of the cent values of the coins you can use. </p><pre><code>defn num-coin-combos (cents:Int, coins:List<Int>) -> Int :<br> if cents == 0 :<br> 1<br> else if cents < 0 :<br> 0<br> else if empty?(coins) :<br> 0<br> else :<br> val with-first-coin = num-coin-combos(cents - head(coins), coins)<br> val without-first-coin = num-coin-combos(cents, tail(coins))<br> with-first-coin + without-first-coin</code></pre><p>Let's read through each case of the algorithm one by one. The first case is</p><pre><code>if cents == 0 :<br> 1</code></pre><p>There is only one way to make 0 cents, and that is to not use any coins at all. Makes sense.</p><p>The second case is</p><pre><code>else if cents < 0 :<br> 0</code></pre><p>There is no way to make a negative cent value. Makes sense.</p><p>The third case is</p><pre><code>else if empty?(coins) :<br> 0</code></pre><p>If we're not allowed to use <span style="font-style:italic;">any</span> kind of coin, then there's also no way to make our total. Makes sense as well.</p><p>The real work of the algorithm is done by the fourth case.</p><pre><code>val with-first-coin = num-coin-combos(cents - head(coins), coins)<br>val without-first-coin = num-coin-combos(cents, tail(coins))<br>with-first-coin + without-first-coin</code></pre><p>Consider the next type of coin in our list. Suppose it's a loonie. There are two choices we can now make. </p><ol><li>We can account for 100 cents by using the loonie, and count the number of ways to make <code>cents - 100</code>. This is calculated as <code>with-first-coin</code>.
</li><li>We can choose not to use the loonie, and count the number of ways to make <code>cents</code> without using loonies. This is calculated as <code>without-first-coin</code>.
</li></ol><p>The total number of combinations is the sum of the results of the two possible choices we can make.</p><p>Let's now use our <code>num-coin-combos</code> function to answer the original question.</p><pre><code>defn main () :<br> val coins = [100, 25, 10, 5, 1]<br> val num-combos = num-coin-combos(117, to-list(coins))<br> println("There are %_ coin combinations that total to 117 cents." %<br> [num-combos])<br><br>main()</code></pre><p>which prints out</p><pre><code>There are 349 coin combinations that total to 117 cents.</code></pre><h3 id="anchor272">Strange Lands</h3><p>Suppose we find ourselves in strange lands with a strange currency. The currency is made up of <span style="font-style:italic;">buzzles</span>, with a value of 57 cents, <span style="font-style:italic;">moozles</span> (26 cents), <span style="font-style:italic;">foogs</span> (10 cents), <span style="font-style:italic;">goofs</span> (5 cents), and <span style="font-style:italic;">tents</span> (3 cents). Now how many ways are there to make the $1.17 needed to buy poutine? (Though the currency may be strange, poutine is fairly universal). </p><p>Let's adapt our <code>main</code> function to calculate with the new currency.</p><pre><code>defn main () :<br> val coins = [57, 26, 10, 5, 3]<br> val num-combos = num-coin-combos(117, to-list(coins))<br> println("There are %_ coin combinations that total to 117 cents." %<br> [num-combos])<br><br>main()</code></pre><p>which prints out</p><pre><code>There are 137 coin combinations that total to 117 cents.</code></pre><p>indicating that buzzles and foogs are a little less flexible than Canadian currency.</p><h3 id="anchor273">SICP</h3><p>This exercise is adapted from the best book on computer science ever written, <span style="font-style:italic;">The Structure and Interpretation of Computer Programs</span> by Abelson and Sussman. I highly recommend it to anyone interested in the deep connections between languages and computation. And since Stanza is a (highly modified) Scheme dialect at heart, all the exercises can easily be done in Stanza as well.</p><h2 id="anchor70">List Library</h2><p><code>List</code> is a subtype of <code>Collection</code> and so all of Stanza's sequence library also works on lists. The core library also includes a few functions specifically for managing lists. You've been introduced to a few of them already: <code>head</code>, <code>tail</code>, <code>append</code>, <code>cons</code>. Here's a few more.</p><h3 id="anchor274">get</h3><p>The <code>get</code> function allows you to retrieve the element at a specific index in a list. </p><pre><code>val xs = to-list(0 to 1000 by 3)<br>get(xs, 11)</code></pre><p>Using Stanza's built-in operator, the above could also be written as</p><pre><code>val xs = to-list(0 to 1000 by 3)<br>xs[11]</code></pre><h3 id="anchor275">headn</h3><p><code>headn</code> returns a list containing the first n items in a list.</p><pre><code>val xs = to-list(0 to 1000 by 3)<br>headn(xs, 10)</code></pre><h3 id="anchor276">tailn</h3><p><code>tailn</code> returns a new list containing the items following the first n items in a list.</p><pre><code>val xs = to-list(0 to 1000 by 3)<br>tailn(xs, 10)</code></pre><h3 id="anchor277">reverse</h3><p><code>reverse</code> takes an argument list and returns a new list containing the same items in reversed order.</p><pre><code>val xs = to-list(0 to 1000 by 3)<br>reverse(xs)</code></pre><h3 id="anchor278">last</h3><p><code>last</code> takes an argument list and returns the last item in it. The list must not be empty.</p><pre><code>val xs = to-list(0 to 1000 by 3)<br>last(xs)</code></pre><h3 id="anchor279">but-last</h3><p><code>but-last</code> takes an argument list and returns a new list containing all the items from the argument list except the last one.</p><pre><code>val xs = to-list(0 to 1000 by 3)<br>but-last(xs)</code></pre><h3 id="anchor280">map</h3><p><code>map</code> is the most commonly used function on lists. It takes an argument function, <code>f</code>, and a list, <code>xs</code>, and returns a new list containing the results of calling <code>f</code> on each item.</p><p>Here is an example that calculates the lengths of all the strings in the list <code>xs</code>.</p><pre><code>val xs = to-list(["Timon" "and" "Pumbaa"])<br>val lengths = map(length, xs)</code></pre><p><code>map</code> is also an operating function, and it can be used together with the for construct. Here is an example of doubling every integer in the list <code>xs</code>.</p><pre><code>val xs = to-list(0 to 1000 by 3)<br>val doubled = for x in xs map :<br> x * 2</code></pre><h2 id="anchor71">Example: More Coin Counting</h2><p>One limitation of our previous algorithm for coin counting is that it calculated the number of ways we can make a certain total, but it never told us what these combinations actually were. You may be (as I was) actually quite curious about how to make $1.17 using buzzles and foogs.</p><p>Let's write a function called <code>coin-combos</code> that does that. Like <code>num-coin-combos</code>, <code>coin-combos</code> takes two arguments: <code>cents</code>, which represents the number of cents you wish to make, and <code>coins</code>, a list of the cent values of the coins. The difference is that <code>coin-combos</code> returns a list of <span style="font-style:italic;">combinations</span>. Each combination is a list containing the number of times each coin is used.</p><pre><code>defn coin-combos (cents:Int, coins:List<Int>) -> List<List<Int>> :<br> if cents == 0 :<br> List(map({0}, coins))<br> else if cents < 0 :<br> List()<br> else if empty?(coins) :<br> List()<br> else :<br> defn head+1 (xs:List<Int>) : cons(head(xs) + 1, tail(xs))<br> defn cons-0 (xs:List<Int>) : cons(0, xs)<br> val with-first-coin = map(head+1, coin-combos(cents - head(coins), coins))<br> val without-first-coin = map(cons-0, coin-combos(cents, tail(coins)))<br> append(with-first-coin, without-first-coin)</code></pre><p>Let's examine each case separately.</p><pre><code>if cents == 0 :<br> List(map({0}, coins))</code></pre><p>There is only one way to make up 0 cents, and that is by using no coins at all. So return a list with a single combination indicating that each coin is used 0 times. </p><pre><code>else if cents < 0 :<br> List()</code></pre><p>There is no way to make a negative total so return an empty list.</p><pre><code>else if empty?(coins) :<br> List()</code></pre><p>If we're not allowed to use <span style="font-style:italic;">any</span> kind of coin, then there's also no way to make our total. Return an empty list.</p><p>And finally, we're at the last case again.</p><pre><code>val with-first-coin = map(head+1, coin-combos(cents - head(coins), coins))<br>val without-first-coin = map(cons-0, coin-combos(cents, tail(coins)))<br>append(with-first-coin, without-first-coin)</code></pre><p>All the combinations resulting from choosing to use the first coin are computed in <code>with-first-coin</code>. And all the combinations resulting from choosing not to use the first coin are computed in <code>without-first-coin</code>. We then append both lists to get the complete list of combinations.</p><p>The fourth case relies upon two helper functions, <code>head+1</code>, which adds 1 to the head of a list, and <code>cons-0</code>, which tacks 0 on to the beginning of a list. </p><pre><code>defn head+1 (xs:List<Int>) : cons(head(xs) + 1, tail(xs))<br>defn cons-0 (xs:List<Int>) : cons(0, xs)</code></pre><p>Let's now update our <code>main</code> function to report all the different ways we can use buzzles and foogs to make $1.17. Recall that buzzles are worth 57 cents, moozles are 26 cents, foogs are 10 cents, goofs are 5 cents, and tents are 3 cents.</p><pre><code>defn main () :<br> val coins = [57, 26, 10, 5, 3]<br> val combos = coin-combos(117, to-list(coins))<br> println("There are %_ coin combinations that total to 117 cents." % [<br> length(combos)])<br> do(println, combos)<br><br>main()</code></pre><p>Compiling and running the above prints out</p><pre><code>There are 137 coin combinations that total to 117 cents.<br>(2 0 0 0 1)<br>(1 2 0 1 1)<br>(1 1 2 1 3)<br>(1 1 1 3 3)<br>...<br>(0 0 0 6 29)<br>(0 0 0 3 34)<br>(0 0 0 0 39)</code></pre><p>Thus we can pay for our $1.17 poutine using two buzzles and a foog. Or if we don't mind holding up the line, we can hunt around for thirty nine tents. </p><h3 id="anchor281">Readable Combos</h3><p>For the sake of readability, let's write a printing function for formatting the combinations in a readable way. <code>print-combo</code> takes as arguments a combination, <code>combo</code>, and a collection representing the names of the coins, <code>names</code>. </p><pre><code>defn print-combo (combo:List<Int>, names:Collection<String>) :<br> val parts = for (c in combo, n in names) seq? :<br> if c == 0 : None()<br> else if c == 1 : One("%_ %_" % [c, n])<br> else : One("%_ %_s" % [c, n])<br> println-all(join(parts, ", ")) </code></pre><p>You are encouraged to read the reference documentation for a description of what <code>seq?</code> does. You should be able to understand it now.</p><p>Now update the final call to <code>print</code> in the <code>main</code> function.</p><pre><code>val coin-names = ["buzzle", "moozle", "foog", "goof", "tent"]<br>do(print-combo{_, coin-names}, combos)</code></pre><p>Compiling and running the program now prints out</p><pre><code>There are 137 coin combinations that total to 117 cents.<br>2 buzzles, 1 tent<br>1 buzzle, 2 moozles, 1 goof, 1 tent<br>1 buzzle, 1 moozle, 2 foogs, 1 goof, 3 tents<br>1 buzzle, 1 moozle, 1 foog, 3 goofs, 3 tents<br>...<br>15 goofs, 14 tents<br>12 goofs, 19 tents<br>9 goofs, 24 tents<br>6 goofs, 29 tents<br>3 goofs, 34 tents<br>39 tents</code></pre><h2 id="anchor72">Extended Example: Automatic Differentiation</h2><p>In your own programming, you are encouraged to define and use immutable datastructures when possible. Uses of mutation and stateful objects should serve a clear purpose. In this example, we define an immutable datastructure for manipulating algebra expressions and write a function for automatically differentiating expressions.</p><h3 id="anchor282">Symbols</h3><p><code>Symbol</code> objects are used to represent a unique constant object in Stanza. For example, the following creates and assigns symbols to <code>x</code> and to <code>y</code>.</p><pre><code>val x = `Timon<br>val y = `Pumbaa</code></pre><p>Symbols are created by prefixing an identifier with the backtick (`) operator. Very little can be done with symbols except check whether it is equal to another symbol. The following</p><pre><code>println(x == `Timon)<br>println(y == `Timon)</code></pre><p>prints out</p><pre><code>true<br>false</code></pre><p>and represents the most common use case for symbols. In this respect they are used in much the same way as enumerated constants in other languages. We will use symbols to represent the name of variables in our algebraic expressions.</p><h3 id="anchor283">The Expression Datastructure</h3><p>We will first declare a type, <code>Exp</code>, to refer to an algebraic expression. </p><pre><code>deftype Exp<br>defstruct Const <: Exp : (value:Int)<br>defstruct Variable <: Exp : (name:Symbol)<br>defstruct Add <: Exp : (a:Exp, b:Exp)<br>defstruct Subtract <: Exp : (a:Exp, b:Exp)<br>defstruct Multiply <: Exp : (a:Exp, b:Exp)<br>defstruct Divide <: Exp : (a:Exp, b:Exp)<br>defstruct Power <: Exp : (a:Exp, b:Exp)<br>defstruct Log <: Exp : (a:Exp)</code></pre><p>A handful of different types of expressions are supported. <code>Const</code> represents constant integer literals, <code>Variable</code> represents a named variable, and the standard arithmetic operators are represented by <code>Add</code>, <code>Subtract</code>, <code>Multiply</code>, and <code>Divide</code>. <code>Power</code> represents one expression raised to the power of another, and <code>Log</code> represents the natural logarithm of an expression. Notice that many of the expressions contain fields that are themselves types of <code>Exp</code>. So the type <code>Exp</code> contains fields of type <code>Exp</code>. We call such a type a <span style="font-style:italic;">recursive</span> type.</p><h3 id="anchor284">Printing an Expression</h3><p>As usual, we will provide a custom <code>print</code> method for the <code>Exp</code> type to allow us to print it out.</p><pre><code>defmethod print (o:OutputStream, e:Exp) :<br> defn print-operator (a:Exp, op:String, b:Exp) :<br> print(o, a)<br> print(o, op)<br> print(o, b)<br> match(e) :<br> (e:Const) : print(o, value(e))<br> (e:Variable) : print(o, name(e))<br> (e:Log) : print(o, "ln(%_)" % [a(e)])<br> (e:Add) : print-operator(a(e), " + ", b(e))<br> (e:Subtract) : print-operator(a(e), " - ", b(e))<br> (e:Multiply) : print-operator(a(e), " * ", b(e))<br> (e:Divide) : print-operator(a(e), " / ", b(e))<br> (e:Power) : print-operator(a(e), " ^ ", b(e))</code></pre><p>Let's now create an expression and print it out. The expression we will create is </p><pre><code>2 * x ^ 2 + (1 + 3) * x + ln(x + 4)</code></pre> <p>Here is our <code>main</code> function.</p><pre><code>defn main () :<br> val term1 = Multiply(Const(2), Power(Variable(`x), Const(2)))<br> val term2 = Multiply(Add(Const(1), Const(3)), Variable(`x))<br> val term3 = Log(Add(Variable(`x), Const(4)))<br> val exp = Add(Add(term1, term2), term3)<br> println(exp) <br><br>main()</code></pre><p>Compiling and running the above prints out</p><pre><code>2 * x ^ 2 + 1 + 3 * x + ln(x + 4)</code></pre><p>We're off to a great start! </p><h3 id="anchor285">Handling Precedence</h3><p>Our printing method for expressions is close, but it doesn't handle precedences correctly. The <code>1 + 3</code> in the printed expression should be surrounded by parentheses. Otherwise the meaning is different than intended.</p><p>Let's add a mechanism to handle precedences properly. Here's the basic algorithm. Every type of expression is associated with a number that represents its precedence. <code>Const</code>, <code>Log</code>, and <code>Variable</code> expressions have the highest precedence 3. <code>Power</code> has precedence 2. <code>Multiply</code> and <code>Divide</code> have precedence 1. And <code>Add</code> and <code>Subtract</code> have the lowest precedence 0. </p><pre><code>defn precedence (e:Exp) :<br> match(e) :<br> (e:Add|Subtract) : 0<br> (e:Multiply|Divide|Power) : 1<br> (e:Power) : 2<br> (e:Const|Variable|Log) : 3</code></pre><p>The basic rule is that if a lower precedence expression appears as a child of a higher precedence expression, then the lower precedence expression needs to be surrounded by parentheses when printed out. So we'll define a new nested function within <code>print</code> to help us print nested expressions in the context of expression <code>e</code>. </p><pre><code>defn print-nested (ne:Exp) :<br> if precedence(ne) < precedence(e) :<br> print(o, "(%_)" % [ne])<br> else :<br> print(o, ne)</code></pre><p>If the nested expression <code>ne</code> has lower precedence than <code>e</code>, then <code>ne</code> is printed with surrounding parentheses. Otherwise <code>ne</code> is just printed directly.</p><p>The <code>print-operator</code> function also needs to be updated to call <code>print-nested</code>.</p><pre><code>defn print-operator (a:Exp, op:String, b:Exp) :<br> print-nested(a)<br> print(o, op)<br> print-nested(b)</code></pre><p>Those are all the changes needed to handle precedence. Here is the full <code>print</code> method. </p><pre><code>defmethod print (o:OutputStream, e:Exp) :<br> defn print-nested (ne:Exp) :<br> if precedence(ne) < precedence(e) :<br> print(o, "(%_)" % [ne])<br> else :<br> print(o, ne)<br> defn print-operator (a:Exp, op:String, b:Exp) :<br> print-nested(a)<br> print(o, op)<br> print-nested(b)<br> match(e) :<br> (e:Const) : print(o, value(e))<br> (e:Variable) : print(o, name(e))<br> (e:Log) : print(o, "ln(%_)" % [a(e)])<br> (e:Add) : print-operator(a(e), " + ", b(e))<br> (e:Subtract) : print-operator(a(e), " - ", b(e))<br> (e:Multiply) : print-operator(a(e), " * ", b(e))<br> (e:Divide) : print-operator(a(e), " / ", b(e))<br> (e:Power) : print-operator(a(e), " ^ ", b(e))</code></pre><p>If you compile and run the program again, it should now correctly print out</p><pre><code>2 * x ^ 2 + (1 + 3) * x + ln(x + 4)</code></pre><h3 id="anchor286">Operator Overloading</h3><p>The code we used to construct the expression</p><pre><code>val term1 = Multiply(Const(2), Power(Variable(`x), Const(2)))<br>val term2 = Multiply(Add(Const(1), Const(3)), Variable(`x))<br>val term3 = Log(Add(Variable(`x), Const(4)))<br>val exp = Add(Add(term1, term2), term3)</code></pre><p>is quite verbose. Let's overload some operators to help us with that. </p><p>Recall that the operators <code>+</code>, <code>-</code>, <code>*</code>, <code>/</code>, and <code>^</code> are just syntactic shorthands for calling the functions <code>plus</code>, <code>minus</code>, <code>times</code>, <code>divide</code>, and <code>bit-xor</code>. Thus all we need to do is define those functions on <code>Exp</code> objects.</p><pre><code>defn plus (a:Exp, b:Exp) : Add(a, b)<br>defn minus (a:Exp, b:Exp) : Subtract(a, b)<br>defn times (a:Exp, b:Exp) : Multiply(a, b)<br>defn divide (a:Exp, b:Exp) : Divide(a, b)<br>defn bit-xor (a:Exp, b:Exp) : Power(a, b)<br>defn ln (a:Exp) : Log(a)</code></pre><p>Now let's rewrite our <code>main</code> function using the new operators.</p><pre><code>defn main () :<br> val x = Variable(`x)<br> val [c1, c2, c3, c4] = [Const(1), Const(2), Const(3), Const(4)]<br> val exp = c2 * x ^ c2 + (c1 + c3) * x + ln(x + c4)<br> println(exp)</code></pre><p>Much better! If we overlook the little c's in front of each constant it's essentially identical to our printed expression.</p><h3 id="anchor287">The Differentiation Algorithm</h3><p>Now we can implement the differentiation algorithm! The function <code>differentiate</code> takes two arguments: the expression to differentiate, <code>e</code>, and the variable with respect to which it will differentiate, <code>x</code>. </p><p>The actual formulas used to do the differentiation are standard, and we won't explain how to derive them. If you have taken a course on calculus, you can break open your old textbook and copy the formulas here. If you haven't taken a course on calculus, then armed with this program, you'll never have to manually differentiate again. </p><pre><code>defn differentiate (e:Exp, x:Symbol) -> Exp :<br> defn ddx (e:Exp) : differentiate(e, x)<br> <br> match(e) :<br> (e:Const) :<br> Const(0)<br> (e:Variable) :<br> if name(e) == x : Const(1)<br> else : Const(0)<br> (e:Add) :<br> ddx(a(e)) + ddx(b(e))<br> (e:Subtract) :<br> ddx(a(e)) - ddx(b(e))<br> (e:Multiply) :<br> a(e) * ddx(b(e)) + b(e) * ddx(a(e))<br> (e:Divide) :<br> val num = b(e) * ddx(a(e)) - a(e) * ddx(b(e))<br> val den = b(e) ^ Const(2)<br> num / den<br> (e:Power) :<br> e * (b(e) * ddx(a(e)) / a(e) + ln(a(e)) * ddx(b(e)))<br> (e:Log) :<br> ddx(a(e)) / a(e)</code></pre><p>Let's try differentiating our example expression now. </p><pre><code>defn main () :<br> val x = Variable(`x)<br> val [c1, c2, c3, c4] = [Const(1), Const(2), Const(3), Const(4)]<br> val exp = c2 * x ^ c2 + (c1 + c3) * x + ln(x + c4)<br> val dexp = differentiate(exp, `x)<br> <br> println("Original Expression: %_" % [exp])<br> println("Differentiated Expression: %_" % [dexp])</code></pre><p>Compiling and running the program prints out</p><pre><code>Original Expression: 2 * x ^ 2 + (1 + 3) * x + ln(x + 4)<br>Differentiated Expression: 2 * x ^ 2 * (2 * 1 / x + ln(x) * 0) +<br> x ^ 2 * 0 + (1 + 3) * 1 +<br> x * (0 + 0) + (1 + 0) / (x + 4)</code></pre><p>If you check the result, it <span style="font-style:italic;">does</span> work! The only problem is that the result contains a lot of expressions that can be trivially simplified. We'll fix that later. But this isn't bad at all for a 22-line algorithm. </p><h3 id="anchor288">Simplification</h3><p>The only thing left to do now is simplify the resulting expression. We will write a <span style="font-style:italic;">very</span> simple simplifier that simply looks for patterns like adding an expression to zero, or dividing by one, et cetera. But before we introduce the simplification algorithm, we need to first write a very useful helper function. </p><pre><code>defn map (f: Exp -> Exp, e:Exp) -> Exp :<br> match(e) :<br> (e:Add) : Add(f(a(e)), f(b(e)))<br> (e:Subtract) : Subtract(f(a(e)), f(b(e)))<br> (e:Multiply) : Multiply(f(a(e)), f(b(e)))<br> (e:Divide) : Divide(f(a(e)), f(b(e)))<br> (e:Power) : Power(f(a(e)), f(b(e)))<br> (e:Log) : Log(f(a(e)))<br> (e) : e</code></pre><p><code>map</code> takes an argument function, <code>f</code>, and an expression, <code>e</code>, and returns a new expression resulting from calling <code>f</code> on every subexpression in <code>e</code>. Its behaviour is analogous to the <code>map</code> function for lists. Calling <code>map</code> on a list <span style="font-style:italic;">maps</span> <code>f</code> onto every element in the list. Similarly, calling <code>map</code> on an expression <span style="font-style:italic;">maps</span> <code>f</code> onto every subexpression in the expression.</p><p>We're now ready to write the <code>simplify</code> function. It takes an expression as its argument, and returns a simplified version of the expression by replacing specific patterns with simpler expressions. </p><pre><code>defn simplify (e:Exp) :<br> defn const? (e:Exp, v:Int) :<br> match(e) :<br> (e:Const) : value(e) == v<br> (e) : false<br> defn one? (e:Exp) : const?(e, 1)<br> defn zero? (e:Exp) : const?(e, 0) <br><br> match(map(simplify, e)) :<br> (e:Add) :<br> if zero?(a(e)) : b(e)<br> else if zero?(b(e)) : a(e)<br> else : e<br> (e:Subtract) :<br> if zero?(a(e)) : Const(-1) * b(e)<br> else if zero?(b(e)) : a(e)<br> else : e <br> (e:Multiply) :<br> if one?(a(e)) : b(e)<br> else if one?(b(e)) : a(e)<br> else if zero?(a(e)) or zero?(b(e)) : Const(0)<br> else : e<br> (e:Divide) :<br> if zero?(a(e)) : Const(0)<br> else if one?(b(e)) : a(e)<br> else : e<br> (e:Power) :<br> if one?(a(e)) : Const(1)<br> else if zero?(b(e)) : Const(1)<br> else : e<br> (e:Log) :<br> if one?(a(e)) : Const(0)<br> else : e<br> (e) : e</code></pre><p>Most of the work of the simplifier is done in the branches of the match expression; you can read through them to understand which patterns are being simplified and what they're being simplified to. However, the most magical part of the function is the call to <code>map</code>. </p><pre><code>match(map(simplify, e)) :<br> (e:Add) :<br> ...</code></pre><p>In English, that pattern says: first simplify all the nested subexpressions in <code>e</code> <span style="font-style:italic;">and then</span> look for these patterns and replace them with simpler ones. </p><p>Let's update our <code>main</code> function now to simplify the differentiated expression.</p><pre><code>defn main () :<br> val x = Variable(`x)<br> val [c1, c2, c3, c4] = [Const(1), Const(2), Const(3), Const(4)]<br> val exp = c2 * x ^ c2 + (c1 + c3) * x + ln(x + c4)<br> val dexp = differentiate(exp, `x)<br> val sexp = simplify(dexp)<br><br> println("Original Expression: %_" % [exp])<br> println("Differentiated Expression: %_" % [dexp])<br> println("Simplified Expression: %_" % [sexp]) </code></pre><p>When compiled and ran it prints out</p><pre><code>Original Expression: 2 * x ^ 2 + (1 + 3) * x + ln(x + 4)<br>Differentiated Expression: 2 * x ^ 2 * (2 * 1 / x + ln(x) * 0) +<br> x ^ 2 * 0 + (1 + 3) * 1 +<br> x * (0 + 0) + (1 + 0) / (x + 4)<br>Simplified Expression: 2 * x ^ 2 * 2 / x + 1 + 3 + 1 / (x + 4)</code></pre><p>The simplified expression is <span style="font-style:italic;">much</span> cleaner now! This concludes our automatic differentiation example. The simplicity of both the differentiation and the simplification algorithm stems from the fact that <code>Exp</code> is an immutable datastructure. In fact, the programming language Lisp, which strongly emphasized computation with immutable list structures and also heavily influenced the design of Stanza, was invented in part for writing computer algebra systems. John McCarthy started writing differentiation algorithms in Lisp even before the language was running!</p><h3 id="anchor289">Program Listing</h3><p>Here's a full program listing of the example. </p><pre><code>defpackage calculus :<br> import core<br><br>;Expression definition<br>deftype Exp<br>defstruct Const <: Exp : (value:Int)<br>defstruct Variable <: Exp : (name:Symbol)<br>defstruct Add <: Exp : (a:Exp, b:Exp)<br>defstruct Subtract <: Exp : (a:Exp, b:Exp)<br>defstruct Multiply <: Exp : (a:Exp, b:Exp)<br>defstruct Divide <: Exp : (a:Exp, b:Exp)<br>defstruct Power <: Exp : (a:Exp, b:Exp)<br>defstruct Log <: Exp : (a:Exp)<br><br>;Precedences<br>defn precedence (e:Exp) :<br> match(e) :<br> (e:Add|Subtract) : 0<br> (e:Multiply|Divide|Power) : 1<br> (e:Power) : 2<br> (e:Const|Variable|Log) : 3<br><br>;Print behaviour for expressions<br>defmethod print (o:OutputStream, e:Exp) :<br> defn print-nested (ne:Exp) :<br> if precedence(ne) < precedence(e) :<br> print(o, "(%_)" % [ne])<br> else :<br> print(o, ne)<br> defn print-operator (a:Exp, op:String, b:Exp) :<br> print-nested(a)<br> print(o, op)<br> print-nested(b)<br> match(e) :<br> (e:Const) : print(o, value(e))<br> (e:Variable) : print(o, name(e))<br> (e:Log) : print(o, "ln(%_)" % [a(e)])<br> (e:Add) : print-operator(a(e), " + ", b(e))<br> (e:Subtract) : print-operator(a(e), " - ", b(e))<br> (e:Multiply) : print-operator(a(e), " * ", b(e))<br> (e:Divide) : print-operator(a(e), " / ", b(e))<br> (e:Power) : print-operator(a(e), " ^ ", b(e))<br><br>;Overloaded operators<br>defn plus (a:Exp, b:Exp) : Add(a, b)<br>defn minus (a:Exp, b:Exp) : Subtract(a, b)<br>defn times (a:Exp, b:Exp) : Multiply(a, b)<br>defn divide (a:Exp, b:Exp) : Divide(a, b)<br>defn bit-xor (a:Exp, b:Exp) : Power(a, b)<br>defn ln (a:Exp) : Log(a)<br><br>;Differentiation algorithm<br>defn differentiate (e:Exp, x:Symbol) -> Exp :<br> defn ddx (e:Exp) : differentiate(e, x)<br> <br> match(e) :<br> (e:Const) :<br> Const(0)<br> (e:Variable) :<br> if name(e) == x : Const(1)<br> else : Const(0)<br> (e:Add) :<br> ddx(a(e)) + ddx(b(e))<br> (e:Subtract) :<br> ddx(a(e)) - ddx(b(e))<br> (e:Multiply) :<br> a(e) * ddx(b(e)) + b(e) * ddx(a(e))<br> (e:Divide) :<br> val num = b(e) * ddx(a(e)) - a(e) * ddx(b(e))<br> val den = b(e) ^ Const(2)<br> num / den<br> (e:Power) :<br> e * (b(e) * ddx(a(e)) / a(e) + ln(a(e)) * ddx(b(e)))<br> (e:Log) :<br> ddx(a(e)) / a(e)<br><br>;Map helper<br>defn map (f: Exp -> Exp, e:Exp) -> Exp :<br> match(e) :<br> (e:Add) : Add(f(a(e)), f(b(e)))<br> (e:Subtract) : Subtract(f(a(e)), f(b(e)))<br> (e:Multiply) : Multiply(f(a(e)), f(b(e)))<br> (e:Divide) : Divide(f(a(e)), f(b(e)))<br> (e:Power) : Power(f(a(e)), f(b(e)))<br> (e:Log) : Log(f(a(e)))<br> (e) : e<br><br>;Simplification algorithm<br>defn simplify (e:Exp) :<br> defn const? (e:Exp, v:Int) :<br> match(e) :<br> (e:Const) : value(e) == v<br> (e) : false<br> defn one? (e:Exp) : const?(e, 1)<br> defn zero? (e:Exp) : const?(e, 0) <br><br> match(map(simplify, e)) :<br> (e:Add) :<br> if zero?(a(e)) : b(e)<br> else if zero?(b(e)) : a(e)<br> else : e<br> (e:Subtract) :<br> if zero?(a(e)) : Const(-1) * b(e)<br> else if zero?(b(e)) : a(e)<br> else : e <br> (e:Multiply) :<br> if one?(a(e)) : b(e)<br> else if one?(b(e)) : a(e)<br> else if zero?(a(e)) or zero?(b(e)) : Const(0)<br> else : e<br> (e:Divide) :<br> if zero?(a(e)) : Const(0)<br> else if one?(b(e)) : a(e)<br> else : e<br> (e:Power) :<br> if one?(a(e)) : Const(1)<br> else if zero?(b(e)) : Const(1)<br> else : e<br> (e:Log) :<br> if one?(a(e)) : Const(0)<br> else : e<br> (e) : e<br><br>;Main program<br>defn main () :<br> val x = Variable(`x)<br> val [c1, c2, c3, c4] = [Const(1), Const(2), Const(3), Const(4)]<br> val exp = c2 * x ^ c2 + (c1 + c3) * x + ln(x + c4)<br> val dexp = differentiate(exp, `x)<br> val sexp = simplify(dexp)<br><br> println("Original Expression: %_" % [exp])<br> println("Differentiated Expression: %_" % [dexp])<br> println("Simplified Expression: %_" % [sexp]) <br><br>;Start!<br>main()</code></pre><h3 id="anchor290">Exercises</h3><ol><li>Our differentiation algorithm is general enough to always give the right answer (for the types of expressions it supports), but it's often <span style="font-style:italic;">too</span> general. This is most obvious in the differentiation rule for <code>Power</code> expressions. The current rule handles the case where both the base and exponent are functions of x, but typically only one of the two is a function of x and the other is a constant expression. Look for these special cases and handle them more intelligently.
</li><li>Extend the simplifier to be able to simplify <code>1 + 3</code> to <code>4</code>.
</li><li>Extend the simplifier to be able to simplify <code>1 + x + 3</code> to <code>4 + x</code>.
</li><li>Extend the simplifier to be able to simplify <code>x - x</code> to <code>0</code>.
</li><li>Extend the simplifier to be able to simplify <code>x + 1 - x</code> to <code>1</code>.
</li><li>Extend the simplifier to be able to simplify <code>x * x</code> to <code>x ^ 2</code>.
</li><li>Extend the simplifier to be able to simplify <code>x / x</code> to <code>1</code>.
</li><li>Extend the simplifier to be able to simplify <code>x ^ 2 / x</code> to <code>x</code>.
</li><li>Extend the simplifier to be able to simplify <code>(x + 1) ^ 2 / (x + 1)</code> to <code>x + 1</code>.
</li></ol>
</td>
<td class="rest">
<img url="resources/spacer.gif"></img>
</td>
</tr>
<tr><td colspan="3" class="footer">
Site design by Luca Li. Copyright 2015.
</td></tr>
</table>
</body>
</html>