-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathchapter8.html
More file actions
31 lines (30 loc) · 45.7 KB
/
chapter8.html
File metadata and controls
31 lines (30 loc) · 45.7 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
<!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="chapter7.html">Previous Chapter</a><a href="chapter9.html">Next Chapter</a>
</td></tr>
<tr>
<td class="nav">
<h1>NAVIGATION</h1>
<h2><a href="#anchor291">Parametric Polymorphism</a></h2><h3><a href="#anchor73">The Need for Polymorphism</a></h3><h4><a href="#anchor292">The Limitations of the ? Type</a></h4><h3><a href="#anchor74">Explicit Type Arguments</a></h3><h3><a href="#anchor75">Captured Type Arguments</a></h3><h4><a href="#anchor293">Capture Locations</a></h4><h4><a href="#anchor294">Multiple Capture Locations</a></h4><h4><a href="#anchor295">Example: map-list</a></h4><h4><a href="#anchor296">Example: map-both</a></h4><h3><a href="#anchor76">Parametric Types</a></h3><h4><a href="#anchor297">Declaring a Parametric Type</a></h4><h4><a href="#anchor298">Declaring Multis</a></h4><h4><a href="#anchor299">Creating Either Objects</a></h4><h4><a href="#anchor300">Polymorphic Constructor Function</a></h4><h4><a href="#anchor301">Parametric Structs</a></h4><h4><a href="#anchor302">Constructor Function with Captured Arguments</a></h4><h4><a href="#anchor303">When <span style="font-style:italic;">not</span> to Use Captured Arguments</a></h4><h3><a href="#anchor77">Match Expressions and Type Erasure</a></h3><h3><a href="#anchor78">Revisiting Stack</a></h3><h4><a href="#anchor304">Parametric Type Declaration</a></h4><h4><a href="#anchor305">Polymorphic Fundamental Operations</a></h4><h4><a href="#anchor306">Polymorphic Constructor Function</a></h4><h4><a href="#anchor307">Trying It Out</a></h4>
</td>
<td class="main">
<h1 id="anchor291">Parametric Polymorphism</h1><p>This chapter will introduce you to the concept of <span style="font-style:italic;">parametric polymorphism</span> and show you how to parameterize your functions using <span style="font-style:italic;">type arguments</span>, and your types using <span style="font-style:italic;">type parameters</span>. </p><h2 id="anchor73">The Need for Polymorphism</h2><p>Thus far, none of the functions you have written so far have been parameterized by type. Here is an example implementation of a function that reverses a list of integers.</p><pre><code>defn reverse-list (xs:List<Int>) -> List<Int> :<br> if empty?(xs) :<br> xs<br> else :<br> append(<br> reverse-list(tail(xs))<br> List(head(xs)))</code></pre><p>But notice that it only works on integers. Thus the following does not compile.</p><pre><code>reverse-list(List("Timon", "and", "Pumbaa"))</code></pre><p>It gives this error.</p><pre><code>Cannot call function reverse-list of type List<Int> -> List<Int> <br>with arguments of type (FullList<String>).</code></pre><p>To handle this, we can write an overloaded version of <code>reverse-list</code> that accepts a list of strings.</p><pre><code>defn reverse-list (xs:List<String>) -> List<String> :<br> if empty?(xs) :<br> xs<br> else :<br> append(<br> reverse-list(tail(xs))<br> List(head(xs)))</code></pre><p>Now <code>reverse-list</code> will work on both integers and strings. So the following</p><pre><code>println(reverse-list(List(1, 2, 3)))<br>println(reverse-list(List("Timon", "and", "Pumbaa")))</code></pre><p>compiles and prints out</p><pre><code>(3 2 1)<br>("Pumbaa" "and" "Timon")</code></pre><p>However, the code for the string version of <code>reverse-list</code> is identical to the integer version, save for its type signature. This is an obvious duplication of effort. Also, this is clearly a subpar solution. What if we next want to reverse a list of characters? It is not practical to define an overloaded version of <code>reverse-list</code> for every type of list we wish to reverse.</p><h3 id="anchor292">The Limitations of the ? Type</h3><p>What we need is the ability to call <code>reverse-list</code> on lists of <span style="font-style:italic;">any</span> type. Well, we've already learned about one mechanism that will allow us to do this: the <code>?</code> type. So let's replace our two overloaded <code>reverse-list</code> functions with a single one that accepts a <code>List<?></code> as its argument.</p><pre><code>defn reverse-list (xs:List) -> List :<br> if empty?(xs) :<br> xs<br> else :<br> append(<br> reverse-list(tail(xs))<br> List(head(xs)))</code></pre><p>Recall that the default type parameter is <code>?</code> for a type without explicit type parameters. Thus <code>List</code> is equivalent to <code>List<?></code>. The above definition of <code>reverse-list</code> <span style="font-style:italic;">will</span> allow us to call both lists of integers and strings. Try out the following code again</p><pre><code>println(reverse-list(List(1, 2, 3)))<br>println(reverse-list(List("Timon", "and", "Pumbaa")))</code></pre><p>and verify that it still prints out</p><pre><code>(3 2 1)<br>("Pumbaa" "and" "Timon")</code></pre><p>It seems to work fine now on these cases. What is the problem? </p><p>The problem is in the type of the result of the <code>reverse-list</code> function. <code>reverse-list</code> is annotated to return a <code>List<?></code>. Thus the following obviously incorrect code will still compile.</p><pre><code>val xs = reverse-list(List("Timon", "and", "Pumbaa"))<br>println(head(xs) + 1)</code></pre> <p>When the compiled program is ran, it crashes with this error.</p><pre><code>FATAL ERROR: Cannot cast value to type.<br> at core/core.stanza:2619.12<br> at test.stanza:15.8</code></pre><p>This is disappointing. The reverse of a list of strings is obviously still a list of strings. So <code>head(xs)</code> should be a <code>String</code>, and Stanza should have stopped us from trying to add an integer to it. More precisely, what we need is the ability for <code>reverse-list</code> to accept lists of any type, but have it also return lists of the <span style="font-style:italic;">same</span> type.</p><p>In place of <code>reverse-list</code>, we'll instead call the <code>reverse</code> function included in Stanza's core library, and see that it does not suffer from these problems.</p><pre><code>val xs = reverse(List("Timon", "and", "Pumbaa"))<br>println(head(xs) + 1)</code></pre> <p>Attempting to compile the above gives this error.</p><pre><code>No appropriate function plus for arguments of type (String, Int). <br>Possibilities are:<br> plus: (Byte, Byte) -> Byte at core/core.stanza:2488.21<br> plus: (Int, Int) -> Int at core/core.stanza:2619.12<br> plus: (Long, Long) -> Long at core/core.stanza:2688.21<br> plus: (Float, Float) -> Float at core/core.stanza:2742.21<br> plus: (Double, Double) -> Double at core/core.stanza:2792.21</code></pre><p>which is much more reassuring. We'll now see how we can write such functions ourselves. </p><h2 id="anchor74">Explicit Type Arguments</h2><p>Here is how to write a <span style="font-style:italic;">polymorphic</span> <code>reverse-list</code> function that takes an explicit type argument.</p><pre><code>defn reverse-list<ElementType> (xs:List<ElementType>) -> List<ElementType> :<br> if empty?(xs) :<br> xs<br> else :<br> append(<br> reverse-list<ElementType>(tail(xs))<br> List(head(xs)))</code></pre><p><code>reverse-list</code> takes a single type argument called <code>ElementType</code> that represents the type of the elements inside the <code>xs</code> list. Now we need to provide a type argument to <code>reverse-list</code> when we call it.</p><pre><code>reverse-list<Int>(List(1, 2, 3))</code></pre><p>What that does is <span style="font-style:italic;">instantiate</span> a version of <code>reverse-list</code> by replacing <code>ElementType</code> with <code>Int</code> in its type signature. Thus the instantiated function has type</p><pre><code>List<Int> -> List<Int></code></pre><p>and we then call it with <code>List(1, 2, 3)</code>. </p><p>Let's use our polymorphic function to reverse lists of integers and strings.</p><pre><code>val xs = reverse-list<Int>(List(1, 2, 3))<br>val ys = reverse-list<String>(List("Timon", "and", "Pumbaa"))<br>println(xs)<br>println(ys)</code></pre><p>Compiling and running the above prints out the same message as before.</p><pre><code>(3 2 1)<br>("Pumbaa" "and" "Timon")</code></pre><p>Let's also verify that the return type of <code>reverse-list</code> is of the proper type.</p><pre><code>val xs = reverse-list<String>(List("Timon", "and", "Pumbaa"))<br>println(head(xs) + 1)</code></pre> <p>Attempting to compile the above gives this error.</p><pre><code>No appropriate function plus for arguments of type (String, Int). <br>Possibilities are:<br> plus: (Byte, Byte) -> Byte at core/core.stanza:2488.21<br> plus: (Int, Int) -> Int at core/core.stanza:2619.12<br> plus: (Long, Long) -> Long at core/core.stanza:2688.21<br> plus: (Float, Float) -> Float at core/core.stanza:2742.21<br> plus: (Double, Double) -> Double at core/core.stanza:2792.21</code></pre><p>So the return type is correct, and Stanza properly catches our mistakes.</p><p>Note that we are responsible for instantiating a correct version of <code>reverse-list</code> to call. If we pass in the wrong type arguments, </p><pre><code>reverse-list<String>(List(1, 2, 3))</code></pre><p>then the program will fail to compile. The above gives this error when we attempt to compile it.</p><pre><code>Cannot call function reverse-list of type List<String> -> List<String> <br>with arguments of type (FullList<Int>).</code></pre><p>As a comment on programming style, the purpose of each type argument in a polymorphic function is typically quite obvious. Thus programmers do not feel the need to give them descriptive names. Here is how <code>reverse-list</code> would commonly be written.</p><pre><code>defn reverse-list<T> (xs:List<T>) -> List<T> :<br> if empty?(xs) :<br> xs<br> else :<br> append(<br> reverse-list<T>(tail(xs))<br> List(head(xs)))</code></pre><p>The vast majority of type arguments are simply named <code>T</code> (short for <code>Type</code>), or <code>S</code> (because it's a letter close to <code>T</code>). </p><h2 id="anchor75">Captured Type Arguments</h2><p>Our polymorphic <code>reverse-list</code> function can now reverse lists of any type and also correctly returns a list of the same type. It's just a little cumbersome to use because we have to pass in the element type of the list we're reversing each time. This is because <code>T</code> is declared as an <span style="font-style:italic;">explicit</span> type argument. We'll see now how to have Stanza automatically infer the type argument by declaring it as a <span style="font-style:italic;">captured</span> type argument.</p><p>Here is a polymorphic <code>reverse-list</code> written using a <span style="font-style:italic;">captured</span> type argument.</p><pre><code>defn reverse-list<?T> (xs:List<?T>) -> List<T> :<br> if empty?(xs) :<br> xs<br> else :<br> append(<br> reverse-list(tail(xs))<br> List(head(xs)))</code></pre><p>A captured type argument is declared with a <code>?</code> prefix, which indicates that it is not passed in explicitly. Instead, it is <span style="font-style:italic;">captured</span> from the types of the arguments it is called with. The type signature above says that <code>reverse-list</code> requires a list to be passed in for <code>xs</code>. Capture <code>T</code> from the element type of <code>xs</code>. </p><p>Now we can call <code>reverse-list</code> without passing in an explicit type argument.</p><pre><code>reverse-list(List(1, 2, 3))</code></pre><p>The argument <code>List(1, 2, 3)</code> has type <code>List<Int></code>, and thus the type argument <code>T</code> captures the element type <code>Int</code>. </p><p>In the following call,</p><pre><code>reverse-list(List("Timon", "and", "Pumbaa"))</code></pre><p>the argument <code>List("Timon", "and", "Pumbaa")</code> has a type <code>List<String></code>, and thus the type argument <code>T</code> captures the element type <code>String</code>. </p><p>Let's try our example of reversing both integer lists and string lists again.</p><pre><code>val xs = reverse-list(List(1, 2, 3))<br>val ys = reverse-list(List("Timon", "and", "Pumbaa"))<br>println(xs)<br>println(ys)</code></pre><p>Notice that we no longer need to pass in type arguments. Compiling and running the above prints out</p><pre><code>(3 2 1)<br>("Pumbaa" "and" "Timon")</code></pre><p>We can also verify that the return type is correct.</p><pre><code>val xs = reverse-list(List("Timon", "and", "Pumbaa"))<br>println(head(xs) + 1)</code></pre><p>Attempting to compile the above gives this error.</p><pre><code>No appropriate function plus for arguments of type (String, Int). <br>Possibilities are:<br> plus: (Byte, Byte) -> Byte at core/core.stanza:2488.21<br> plus: (Int, Int) -> Int at core/core.stanza:2619.12<br> plus: (Long, Long) -> Long at core/core.stanza:2688.21<br> plus: (Float, Float) -> Float at core/core.stanza:2742.21<br> plus: (Double, Double) -> Double at core/core.stanza:2792.21</code></pre><p>Thus the <code>reverse-list</code> function is now polymorphic and it does not require any explicit type arguments. We've finished generalizing <code>reverse-list</code> at this point, and it actually now has the same type signature as the <code>reverse</code> function in the core library.</p><h3 id="anchor293">Capture Locations</h3><p>Here's another example polymorphic function.</p><pre><code>defn store-in-odd-slots<?T> (xs:Array<?T>, v:T) -> False :<br> for i in 1 to length(xs) by 2 do :<br> xs[i] = v</code></pre><p><code>store-in-odd-slots</code> is a polymorphic function that accepts an array, <code>xs</code>, and an item, <code>v</code>, and stores <code>v</code> at every odd index in <code>xs</code>. Let's try it out.</p><pre><code>val xs = to-array<String>(["Patrick", "Sunny", "Luca", "Whiskey", "Emmy", "Rummy"])<br>store-in-odd-slots(xs, "and")<br>println(xs)</code></pre><p>prints out</p><pre><code>["Patrick" "and" "Luca" "and" "Emmy" "and"]</code></pre><p>Let's now take a closer look at the type signature of <code>store-in-odd-slots</code>.</p><pre><code>defn store-in-odd-slots<?T> (xs:Array<?T>, v:T) -> False</code></pre><p>The <code>?T</code> following the function name</p><pre><code>store-in-odd-slots<?T></code></pre><p>means that the function is polymorphic and accepts a single captured type argument. The argument list</p><pre><code>(xs:Array<?T>, v:T)</code></pre><p>contains two references to <code>T</code>, but only one of them is prefixed with a <code>?</code>. This means that <code>T</code> is captured <span style="font-style:italic;">only</span> from the element type of <code>xs</code>. </p><p>The capture location for <code>T</code> was chosen carefully. Consider the following type definitions.</p><pre><code>deftype Shape<br>deftype Circle <: Shape</code></pre><p>where all circles are also shapes, but not all shapes are circles. </p><p>The following usage of <code>store-in-odd-slots</code></p><pre><code>val shapes = Array<Shape>(10)<br>store-in-odd-slots(shapes, new Circle)</code></pre><p>compiles correctly. <code>T</code> is captured from the element type of <code>Array<Shape></code>, and is thus <code>Shape</code>. The instantiated <code>store-in-odd-slots</code> therefore has type</p><pre><code>(Array<Shape>, Shape) -> False</code></pre><p>and can be suitably called with <code>shapes</code> and <code>new Circle</code>.</p><p>But this next usage</p><pre><code>val circles = Array<Circle>(10)<br>store-in-odd-slots(circles, new Shape)</code></pre><p>fails with this error</p><pre><code>Cannot call function store-in-odd-slots of type (Array<Circle>, Circle) -> False<br>with arguments of type (Array<Circle>, Shape).</code></pre><p>This is consistent with our intuition. You cannot store an arbitrary shape into an array that can only hold circles. As an exercise, think about what would happen if <code>store-in-odd-slots</code> was instead declared the following way.</p><pre><code>defn store-in-odd-slots<?T> (xs:Array<T>, v:?T) -> False</code></pre><p>As a general rule of thumb, the majority of polymorphic functions operate on a collection of some sort. The type argument is <span style="font-style:italic;">almost always</span> captured from the element type of the collection. </p><h3 id="anchor294">Multiple Capture Locations</h3><p>After reading the previous section, you might be naturally wondering what happens when there are <span style="font-style:italic;">multiple</span> capture locations. If there are multiple capture locations, then the final captured type is the <span style="font-style:italic;">union</span> of all the types captured from each location.</p><p>Here is an example of a function that makes use of two capture locations.</p><pre><code>defn append-lists<?T> (xs:List<?T>, ys:List<?T>) -> List<T> :<br> if empty?(xs) : ys<br> else : cons(head(xs), append-lists(tail(xs), ys))</code></pre><p>The type argument <code>T</code> is captured from both the element type of <code>xs</code> <span style="font-style:italic;">and</span> the element of type <code>ys</code>. Thus if we call <code>append-lists</code> on a list of integers and a list of strings,</p><pre><code>val xs = List(1, 2, 3)<br>val ys = List("Timon", "and", "Pumbaa")<br>val zs = append-lists(xs, ys)</code></pre><p>then the resulting type of <code>zs</code> is <code>List<Int|String></code>. </p><h3 id="anchor295">Example: map-list</h3><p>Let's try writing our own polymorphic <code>map</code> function on lists. We'll call ours <code>map-list</code>. <code>map-list</code> accepts a 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 in <code>xs</code>. To start off, here's the function definition without any type annotations.</p><pre><code>defn map-list (f, xs) :<br> if empty?(xs) :<br> List()<br> else :<br> val y = f(head(xs))<br> val ys = map-list(f, tail(xs))<br> cons(y, ys)</code></pre><p>Let's verify that it works as intended.</p><pre><code>val xs = to-list(["Timon", "and", "Pumbaa" "are", "good", "friends"])<br>val lengths = map-list(length, xs)<br>println(lengths)</code></pre><p>Compiling and running the above prints out</p><pre><code>(5 3 6 3 4 7)</code></pre><p>Let's start off with figuring out the type of <code>xs</code>, because it seems easier. It's a list for sure, and <code>map-list</code> should be able to work on lists of any type. So <code>xs</code> is therefore of type</p><pre><code>xs:List<?T></code></pre><p>and <code>T</code> is a captured type argument for <code>map-list</code>. </p><p>Next, let's figure out the type of <code>f</code>. It's a function for sure, and it's called with only a single argument. So it's at least</p><pre><code>f:? -> ?</code></pre><p>Next we know that <code>f</code> is called with items from <code>xs</code>, which is a list of <code>T</code>'s, so <code>f</code> has to accept <code>T</code>'s. Now we know it's at least</p><pre><code>f:T -> ?</code></pre><p>Finally, what is <code>f</code> allowed to return? Well, <code>f</code> is allowed to return anything actually. So let's introduce another captured type argument. The final type of <code>f</code> is</p><pre><code>f:T -> ?S</code></pre><p>Now that we know the types of its arguments, the last step is to figure out what <code>map-list</code> returns. We know that it returns a list, and we also know that the list contains the results of calling <code>f</code>. Since we now know that <code>f</code> returns <code>S</code>'s, therefore <code>map-list</code> returns a list of <code>S</code>'s. Here is the complete type signature for <code>map-list</code>.</p><pre><code>defn map-list<?T,?S> (f:T -> ?S, xs:List<?T>) -> List<S></code></pre><p>Let's try our test code again with our typed <code>map-list</code> function and ensure it works as expected.</p><pre><code>val xs = to-list(["Timon", "and", "Pumbaa" "are", "good", "friends"])<br>val lengths = map-list(length, xs)<br>println(lengths)</code></pre><p>Running the above prints out</p><pre><code>(5 3 6 3 4 7)</code></pre><p>as before. </p><p>To double check the inferred return type of <code>map-list</code>, let's cast <code>lengths</code> to an obviously incorrect type, and read what Stanza says about its type. </p><pre><code>lengths as False</code></pre><p>Compiling the above gives us the error</p><pre><code>Cannot cast expression of type List<Int> to type False.</code></pre><p>So Stanza says that <code>lengths</code> is a list of integers, which is correct. </p><h3 id="anchor296">Example: map-both</h3><p>Here's some more practice on using captured type arguments. Here is the un-annotated definition for the <code>map-both</code> function.</p><pre><code>defn map-both (f, g, xs) :<br> for x in xs map :<br> [f(x), g(x)]</code></pre><p><code>map-both</code> accepts two functions, <code>f</code> and <code>g</code>, and a list, <code>xs</code>, and returns a list containing two-element tuples. The first elements in all the tuples are the results of calling <code>f</code> on each item in <code>xs</code>, and the second elements in all the tuples are the results of calling <code>g</code> on each item in <code>xs</code>.</p><p>Similar to before, the list, <code>xs</code>, is the easiest argument to figure out the type signature for.</p><pre><code>xs:List<?T></code></pre><p><code>f</code> needs to be a function that can be called with items from <code>xs</code>, and can return anything.</p><pre><code>f:T -> ?S</code></pre><p><code>g</code> also needs to be a function that can called with items from <code>xs</code>, and can also return anything. </p><pre><code>g:T -> ?R</code></pre><p><code>map-both</code> returns a list of tuples. The first elements in the tuples are results of calling <code>f</code>, and the second elements are results of calling <code>g</code>.</p><pre><code>List<[S, R]></code></pre><p>Thus the complete definition for <code>map-both</code> is</p><pre><code>defn map-both<?T,?S,?R> (f:T -> ?S, g:T -> ?R, xs:List<?T>) -> List<[S, R]> :<br> for x in xs map :<br> [f(x), g(x)]</code></pre><p>Let's try it out on a list of strings.</p><pre><code>val xs = to-list(["Timon", "and", "Pumbaa", "are", "good", "friends"])<br>val zs = map-both(<br> xs,<br> fn (x) : x[2]<br> fn (y) : length(y) * 2)<br>println(zs)</code></pre><p>which prints out</p><pre><code>(['m' 10] ['d' 6] ['m' 12] ['e' 6] ['o' 8] ['i' 14])</code></pre><p>Let's cast <code>zs</code> to something silly to see what Stanza says about its type. Attempting to compile the following</p><pre><code>zs as False</code></pre><p>gives us this error.</p><pre><code>Cannot cast expression of type List<[Char, Int]> to type False.</code></pre><p>So <code>zs</code> has type <code>List<[Char, Int]></code>, which is what we expect.</p><h2 id="anchor76">Parametric Types</h2><p>You have been shown how to define your own types using <code>deftype</code> and also the shorthand <code>defstruct</code>. But none of the types you've defined thus far accept <span style="font-style:italic;">type parameters</span>. This stood out the most in our definition of the <code>Stack</code> type which was only able to store <span style="font-style:italic;">String</span> objects. We'll now learn how to declare our own <span style="font-style:italic;">parametric types</span>.</p><h3 id="anchor297">Declaring a Parametric Type</h3><p>Here is an example of a simple type that takes two type parameters. </p><pre><code>deftype Either<L,R></code></pre><p><code>Either</code> contains two wrapped objects, a left object of type <code>L</code>, and a right object of type <code>R</code>. </p><p>This is all there is to defining a parametric type! The rest of this section covers mechanisms that have already been introduced, but we'll go through them in the context of the <code>Either</code> type for practice.</p><h3 id="anchor298">Declaring Multis</h3><p>Let's define the fundamental operations for an <code>Either</code> object, which are simply getter functions for retrieving the two wrapped objects.</p><pre><code>defmulti left<?L> (e:Either<?L,?>) -> L<br>defmulti right<?R> (e:Either<?,?R>) -> R</code></pre><p>Notice that the <code>left</code> and <code>right</code> functions each take only a single type argument. The other type parameter for the <code>Either</code> object is left as <code>?</code> to indicate that it is free to be anything.</p><h3 id="anchor299">Creating Either Objects</h3><p>Now let's write a constructor function for creating <code>Either</code> objects. We'll start with a function that can only create <code>Either<Int,String></code> objects.</p><pre><code>defn Either (l:Int, r:String) :<br> new Either<Int,String> :<br> defmethod left (this) : l<br> defmethod right (this) : r</code></pre><p>Let's try it out.</p><pre><code>val e = Either(42, "Timon")<br>println("The left object is %_." % [left(e)])<br>println("The right object is %_." % [right(e)])</code></pre><p>prints out</p><pre><code>The left object is 42.<br>The right object is Timon.</code></pre><h3 id="anchor300">Polymorphic Constructor Function</h3><p>Now that we can successfully create specific <code>Either</code> objects, let's generalize our constructor function by making it polymorphic using type arguments. The following declares <code>Either</code> as taking two explicit type arguments, one for each wrapped object.</p><pre><code>defn Either<L,R> (l:L, r:R) :<br> new Either<L,R> :<br> defmethod left (this) : l<br> defmethod right (this) : r</code></pre><p>Now <code>Either</code> objects are created in the following way.</p><pre><code>val e = Either<Int,String>(42, "Timon")</code></pre><p>The way in which <code>Either</code> objects are created now resembles how we've been creating many of the other types included in the core library, such as arrays and vectors. This is not a coincidence. The construction function for arrays and vectors are also just regular functions that take explicit type arguments and return instances of parametric types.</p><h3 id="anchor301">Parametric Structs</h3><p>The <code>defstruct</code> expression also accepts type parameters for creating parametric structs. As mentioned previously, the <code>defstruct</code> expression is simply a syntactic shorthand for declaring a new type, getter functions for its fields, and a default construction function. Thus all the code we've written previously to define the <code>Either</code> type can be neatly expressed as</p><pre><code>defstruct Either<L,R> :<br> left: L<br> right: R</code></pre><h3 id="anchor302">Constructor Function with Captured Arguments</h3><p>Specifically for creating <code>Either</code> objects, it is also not necessary to have the user explicitly specify the types of the left and right objects. Let's make the constructor function more convenient to call by using captured type arguments.</p><pre><code>defn Either<?L,?R> (l:?L, r:?R) :<br> new Either<L,R> :<br> defmethod left (this) : l<br> defmethod right (this) : r</code></pre><p>Now we can create an <code>Either</code> object like this</p><pre><code>val e = Either(42, "Timon")</code></pre><p>and have Stanza automatically infer that <code>e</code> is an <code>Either<Int,String></code> based on the types of <code>42</code> and <code>"Timon"</code>.</p><h3 id="anchor303">When <span style="font-style:italic;">not</span> to Use Captured Arguments</h3><p>We showed above how to write a constructor function using captured arguments that did not require the left and right object types to be passed in explicitly to <code>Either</code>. This makes the constructor function for <code>Either</code> objects very similar to the constructor function for <code>List</code> objects, which also does not require any explicit type arguments. This is <span style="font-style:italic;">not</span> always an appropriate thing to do.</p><p>Let us suppose that <code>Either</code> is a <span style="font-style:italic;">mutable</span> datastructure; that we can change the left and right objects after the object has been created. The type definition for <code>Either</code> would stay the same, but it would gain two more fundamental operations.</p><pre><code>defmulti left<?L> (e:Either<?L,?>) -> L<br>defmulti right<?R> (e:Either<?,?R>) -> R<br>defmulti set-left<?L> (e:Either<?L,?>, v:L) -> False<br>defmulti set-right<?R> (e:Either<?,?R>, v:R) -> False</code></pre><p>Notice, especially, the capture locations of the type arguments in the setter functions. </p><p>The constructor function would be changed to now accept not the left and right objects, but the <span style="font-style:italic;">initial</span> left and right objects, since they may change later on.</p><pre><code>defn Either<?L,?R> (l0:?L, r0:?R) :<br> var l = l0<br> var r = r0<br> new Either<L,R> :<br> defmethod left (this) : l<br> defmethod right (this) : r<br> defmethod set-left (this, v:L) : l = v<br> defmethod set-right (this, v:R) : r = v</code></pre><p>For the next part, let us again assume that we have definitions for some basic shapes.</p><pre><code>deftype Shape<br>deftype Circle <: Shape<br>deftype Rectangle <: Shape<br><br>defmethod print (o:OutputStream, c:Circle) : print(o, "Circle")<br>defmethod print (o:OutputStream, r:Rectangle) : print(o, "Rectangle")</code></pre><p>Let's try creating a mutable <code>Either</code> object now.</p><pre><code>defn my-favorite-shape () -> Shape :<br> new Circle<br><br>val e = Either(42, my-favorite-shape())<br>println("After creation:")<br>println("The left object is %_" % [left(e)])<br>println("The right object is %_" % [right(e)])<br><br>set-left(e, 256)<br>set-right(e, new Rectangle)<br>println("\nAfter mutation:")<br>println("The left object is %_" % [left(e)])<br>println("The right object is %_" % [right(e)])</code></pre><p>Compiling and running the above prints out</p><pre><code>After creation:<br>The left object is 42<br>The right object is Circle<br><br>After mutation:<br>The left object is 256<br>The right object is Rectangle</code></pre><p>Everything seems to be working, but pay attention to what happens next. </p><p>The type signature for <code>my-favorite-shape</code> is not as precise as it could be. It's annotated to return <code>Shape</code>, but it's more precise to say that it returns <code>Circle</code>. So let's improve <code>my-favorite-shape</code>'s type signature.</p><pre><code>defn my-favorite-shape () -> Circle :<br> new Circle</code></pre><p>Now try compiling and running the program again. It will now give this error.</p><pre><code>Cannot call function set-right of type (Either<?, Circle>, Circle) -> False <br>with arguments of type (Either<Int, Circle>, Rectangle).</code></pre><p>What is going on? Why would changing (actually improving) the type signature for <code>my-favorite-shape</code> affect the later call to <code>set-right</code>? </p><p>The problem, as is evident in the error message, is that the inferred type for <code>e</code> is <code>Either<Int, Circle></code>. This is not right. Even though the <span style="font-style:italic;">initial</span> right object was a <code>Circle</code>, that doesn't mean we want <code>e</code> to <span style="font-style:italic;">only ever</span> hold <code>Circle</code> objects as its right object.</p><p>This is one of those cases where using a captured type argument is inappropriate. For a mutable <code>Either</code> object, the types of the left and right objects should be passed in explicitly.</p><p>Here is the constructor function rewritten to use explicit type arguments.</p><pre><code>defn Either<L,R> (l0:L, r0:R) :<br> var l = l0<br> var r = r0<br> new Either<L,R> :<br> defmethod left (this) : l<br> defmethod right (this) : r<br> defmethod set-left (this, v:L) : l = v<br> defmethod set-right (this, v:R) : r = v</code></pre><p>And here is our original test code rewritten to pass in explicit type arguments.</p><pre><code>defn my-favorite-shape () -> Shape :<br> new Circle<br><br>val e = Either<Int, Shape>(42, my-favorite-shape())<br>println("After creation:")<br>println("The left object is %_" % [left(e)])<br>println("The right object is %_" % [right(e)])<br><br>set-left(e, 256)<br>set-right(e, new Rectangle)<br>println("\nAfter mutation:")<br>println("The left object is %_" % [left(e)])<br>println("The right object is %_" % [right(e)])</code></pre><p>Verify that it still compiles and runs correctly. </p><p>At this point, we can try making the same change to <code>my-favorite-shape</code>'s type signature.</p><pre><code>defn my-favorite-shape () -> Circle :<br> new Circle</code></pre><p>This time, however, the program still compiles and continues to run as before. </p><p>Here are the basic rules of thumb for choosing between using explicit or captured type arguments. If you're creating an immutable object then feel free to use captured type arguments. If you're creating a mutable object, then use explicit type arguments. </p><p>These issues surrounding captured type arguments and mutable objects is also why <code>to-array</code> and <code>to-vector</code> require explicit type arguments and why <code>to-list</code> does not.</p><h2 id="anchor77">Match Expressions and Type Erasure</h2><p>One subtlety concerning Stanza's parametric type system is a concept called <span style="font-style:italic;">type erasure</span>. It roughly means that, given a program, if we replace every type argument with the <code>?</code> type, it should still run and compute the same result (providing that the original program doesn't fail). Said another way, the setting of a type argument can never change what is computed by a program.</p><p>Here is an example of incorrectly attempting to use a type argument to affect which branch is taken in a match expression.</p><pre><code>defn check-if<T> (x) :<br> match(x) :<br> (x:T) : true<br> (x) : false</code></pre><p>Let's try it out on a <code>String</code> object.</p><pre><code>println(check-if<Int>("Timon"))</code></pre><p>Compiling and running the above prints out</p><pre><code>FATAL ERROR: Cannot cast value to type.<br> at test.stanza:15.8<br> at test.stanza:18.8</code></pre><p>Here is what is happening underneath. The <span style="font-style:italic;">dispatch</span> type in a match branch has all of its type arguments and parametric types erased. Thus the code above is equivalent to the following</p><pre><code>defn check-if<T> (x) :<br> match(x) :<br> (y:?) :<br> val x = y as T<br> true<br> (y:?) :<br> false</code></pre><p>and the error message arises because <code>y</code> cannot be cast to a <code>T</code> object. We intentionally designed Stanza so that there is no possible way to write a function such as <code>check-if</code>.</p><h2 id="anchor78">Revisiting Stack</h2><p>At this point, we have all the requisite knowledge for writing a parametric version of our <code>Stack</code> class from chapter 6. Here are our old definitions for the <code>Stack</code> type and its fundamental operations.</p><pre><code>deftype Stack <: Collection<String><br>defmulti push (s:Stack, x:String) -> False<br>defmulti pop (s:Stack) -> String<br>defmulti empty? (s:Stack) -> True|False</code></pre><p>A <code>Stack</code> is declared to be a collection of strings, and its fundamental operations allow us to push and pop strings from it.</p><p>Here is the original constructor function.</p><pre><code>defn Stack (capacity:Int) -> Stack :<br> val items = Array<String>(capacity)<br> var size = 0<br> new Stack :<br> defmethod push (this, x:String) :<br> if size == capacity : fatal("Stack is full!")<br> items[size] = x<br> size = size + 1<br> defmethod pop (this) :<br> if size == 0 : fatal("Stack is empty!")<br> size = size - 1<br> items[size]<br> defmethod empty? (this) :<br> size == 0<br> defmethod print (o:OutputStream, this) :<br> print(o, "Stack containing [")<br> print-all(o, join(this, " "))<br> print(o, "]")<br> defmethod to-seq (this) :<br> take-n(size, items)</code></pre><h3 id="anchor304">Parametric Type Declaration</h3><p>The first step is to declare <code>Stack</code> as a parametric type. </p><pre><code>deftype Stack<T> <: Collection<T></code></pre><p>Thus, <code>Stack</code> now takes a type parameter, <code>T</code>, that indicates what types of objects the stack may hold, and is also no longer a collection of strings. It is now a collection of <code>T</code>'s. </p><h3 id="anchor305">Polymorphic Fundamental Operations</h3><p>The second step is to declare its fundamental operations as polymorphic functions.</p><pre><code>defmulti push<?T> (s:Stack<?T>, x:T) -> False<br>defmulti pop<?T> (s:Stack<?T>) -> T<br>defmulti empty? (s:Stack) -> True|False</code></pre><p>both <code>push</code> and <code>pop</code> now accept a captured type argument, <code>T</code>, that indicates the element type of the stack object. Here are some points to take note of. Notice that the <code>x</code> argument for <code>push</code> is not a capture location for <code>T</code>. This is consistent with our earlier discussion in the section on capture locations. Also notice that the <code>empty?</code> multi is unchanged, as the types of the objects in a stack are not needed to check whether the stack is empty.</p><h3 id="anchor306">Polymorphic Constructor Function</h3><p>The last step is to make its constructor function polymorphic.</p><pre><code>defn Stack<T> (capacity:Int) -> Stack<T> :<br> val items = Array<T>(capacity)<br> var size = 0<br> new Stack :<br> defmethod push (this, x:T) :<br> if size == capacity : fatal("Stack is full!")<br> items[size] = x<br> size = size + 1<br> defmethod pop (this) :<br> if size == 0 : fatal("Stack is empty!")<br> size = size - 1<br> items[size]<br> defmethod empty? (this) :<br> size == 0<br> defmethod print (o:OutputStream, this) :<br> print(o, "Stack containing [")<br> print-all(o, join(this, " "))<br> print(o, "]")<br> defmethod to-seq (this) :<br> take-n(size, items)</code></pre><p>The constructor function now takes an explicit type argument, <code>T</code>, indicating the element type of the stack object, and returns a <code>Stack<T></code>. Notice that the backing array, <code>items</code>, is no longer an <code>Array<String></code>. It is now declared as an <code>Array<T></code> in order to hold the items in the stack. <code>push</code> now also accepts a <code>T</code> value instead of a <code>String</code> value. The rest of the function is unchanged. </p><h3 id="anchor307">Trying It Out</h3><p>Let's try out our parametric <code>Stack</code> type using a variation of our original test code.</p><pre><code>defn main () :<br> val s = Stack<Int>(10)<br> for x in [1, 5, 2, 42, -11, 2, 5, 10, -42] do :<br> push(s, x)<br><br> println("1. Contents of s")<br> println(s)<br><br> println("\n2. Index of 42")<br> println(index-of(s, 42))<br><br> println("\n3. Does it contain any negative numbers?")<br> println(any?({_ < 0}, s))<br><br> println("\n4. Are all numbers negative?")<br> println(all?({_ < 0}, s))<br><br> println("\n5. What are the negative numbers?")<br> val cap-s = filter({_ < 0}, s)<br> println-all(join(cap-s, ", "))<br><br> println("\n6. What are its unique elements?")<br> println(unique(s))<br><br>main()</code></pre><p>Compiling and running the above prints out</p><pre><code>1. Contents of s<br>Stack containing [1 5 2 42 -11 2 5 10 -42]<br><br>2. Index of 42<br>3<br><br>3. Does it contain any negative numbers?<br>true<br><br>4. Are all numbers negative?<br>false<br><br>5. What are the negative numbers?<br>-11, -42<br><br>6. What are its unique elements?<br>(1 5 2 42 -11 10 -42)</code></pre><p>Our parametric stack type is now quite general. It can hold items of different types, and it supports all the operations in the core sequence library. Actually, the <code>Array</code> and <code>Vector</code> types in the core library are defined in much the same way as <code>Stack</code>.</p>
</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>