Programming with FirstClass FunctionsStanza fully supports and encourages functional programming, however "Functional Programming" is intentionally not the title of this chapter. In the community, the term functional programming has been used to refer to two different concepts. The first is the concept of programming with firstclass functions, where functions themselves are passed as arguments and stored in datastructures. This is the subject of this chapter. The second concept refers to a style of programming revolving around the mathematical definition of functions; so called pure functions. A pure function is guaranteed to return the same result if called with the same arguments, and also not affect the environment in any way (e.g. by printing to the terminal). This style of programming is largely an exercise in manipulating immutable datastructures. It is also a powerful paradigm and will be the subject of a later chapter. Nested FunctionsAs a gentle introduction to firstclass functions we will start with nested functions. We hope the concept will seem straightforward, and then later we'll reveal that they are actually quite sophisticated underneath. Here is a function that sorts an array of integers in increasing order. defn selectionsort (xs:Array<Int>) : val n = length(xs) for i in 0 to (n  1) do : var minidx = i var minval = xs[i] for j in (i + 1) to n do : if xs[j] < minval : minidx = j minval = xs[j] if i != minidx : xs[minidx] = xs[i] xs[i] = minval
Let's try it out on an array of random numbers. defn main () : val xs = Array<Int>(10) xs[0] = 510 xs[1] = 923 xs[2] = 671 xs[3] = 811 xs[4] = 129 xs[5] = 581 xs[6] = 233 xs[7] = 791 xs[8] = 899 xs[9] = 313
selectionsort(xs) println(xs)
main()
It should print out [791 581 129 233 313 510 671 811 899 923]
By reading through the algorithm, you can see that the larger problem of sorting the array is actually composed of a number of smaller subproblems. For example, the lines var minidx = i var minval = xs[i] for j in (i + 1) to n do : if xs[j] < minval : minidx = j minval = xs[j]
compute the index of the minimum element between index i + 1 and index n . The lines if i != minidx : xs[minidx] = xs[i] xs[i] = minval
swaps the element at index i with the element at index minidx . selectionsort is short enough that we can still understand the main algorithm even without explicitly dividing the problem into smaller ones. But as programs get larger, the ability to break up a larger problem into smaller ones is very important. Nested functions gives us a lot of power for doing this. Let's define a nested function, indexofmin , that takes two indices start and end , and returns the index of the minimum element between indices start (inclusive) and end (exclusive). defn indexofmin (start:Int, end:Int) : var minidx = start var minval = xs[start] for i in (start + 1) to end do : if xs[i] < minval : minidx = i minval = xs[i] minidx
Let's define another nested function, swap , that swaps the element in index i with the element in index j . defn swap (i:Int, j:Int) : if i != j : val xsi = xs[i] val xsj = xs[j] xs[i] = xsj xs[j] = xsi
And now let's clean up our selectionsort function using these nested functions. defn selectionsort (xs:Array<Int>) : defn indexofmin (start:Int, end:Int) : var minidx = start var minval = xs[start] for i in (start + 1) to end do : if xs[i] < minval : minidx = i minval = xs[i] minidx
defn swap (i:Int, j:Int) : if i != j : val xsi = xs[i] val xsj = xs[j] xs[i] = xsj xs[j] = xsi val n = length(xs) for i in 0 to (n  1) do : swap(i, indexofmin(i, n))
The code is slightly longer than before, but the overall algorithm is much clearer now. for i in 0 to (n  1) do : swap(i, indexofmin(i, n))
In English, it says: iterate with index i starting from 0 and proceeding to the end of the array, and swap the element at i with the minimum element in the rest of the array. Notice that the nested functions indexofmin and swap are not merely functions declared within the body of selectionsort . If you tried to declare them as toplevel functions, the program would give you this error when you try to compile it, Could not resolve xs.
indicating that xs is not in scope and is not visible to indexofmin or swap . Part of the power of nested functions rests in them being able to refer to values defined in the function they're nested in.
Example: Permutations
Here is another example of using nested functions to greatly simplify code. The permutations function accepts an array of strings and prints out all possible permutations of its contents. defn permutations (xs:Array<String>) : val n = length(xs) defn swap (i:Int, j:Int) : if i != j : val xi = xs[i] val xj = xs[j] xs[i] = xj xs[j] = xi defn permute (i:Int) : if i < n  1 : for j in i to n do : swap(i, j) permute(i + 1) swap(i, j) else : println(xs)
permute(0)
It internally relies upon the nested functions swap and permute . Let's try it out with these strings. defn main () : val xs = toarray<String>(["All" "Dogs" "Are" "Awesome"]) permutations(xs)
main()
When compiled and ran, it prints out ["All" "Dogs" "Are" "Awesome"] ["All" "Dogs" "Awesome" "Are"] ["All" "Are" "Dogs" "Awesome"] ["All" "Are" "Awesome" "Dogs"] ["All" "Awesome" "Are" "Dogs"] ["All" "Awesome" "Dogs" "Are"] ["Dogs" "All" "Are" "Awesome"] ["Dogs" "All" "Awesome" "Are"] ["Dogs" "Are" "All" "Awesome"] ["Dogs" "Are" "Awesome" "All"] ["Dogs" "Awesome" "Are" "All"] ["Dogs" "Awesome" "All" "Are"] ["Are" "Dogs" "All" "Awesome"] ["Are" "Dogs" "Awesome" "All"] ["Are" "All" "Dogs" "Awesome"] ["Are" "All" "Awesome" "Dogs"] ["Are" "Awesome" "All" "Dogs"] ["Are" "Awesome" "Dogs" "All"] ["Awesome" "Dogs" "Are" "All"] ["Awesome" "Dogs" "All" "Are"] ["Awesome" "Are" "Dogs" "All"] ["Awesome" "Are" "All" "Dogs"] ["Awesome" "All" "Are" "Dogs"] ["Awesome" "All" "Dogs" "Are"]
As an exercise, try writing a function called combinations that prints out all combinations of an array of strings instead of all permutations. Functions as ArgumentsThe selectionsort function in the previous example sorted the array in increasing order. But there are many ways to sort an array of integers. The following sortbyabs function sorts the array by their absolute values. defn sortbyabs (xs:Array<Int>) : defn indexofmin (start:Int, end:Int) : var minidx = start var minval = xs[start] for i in (start + 1) to end do : if abs(xs[i]) < abs(minval) : minidx = i minval = xs[i] minidx
defn swap (i:Int, j:Int) : if i != j : val xsi = xs[i] val xsj = xs[j] xs[i] = xsj xs[j] = xsi val n = length(xs) for i in 0 to (n  1) do : swap(i, indexofmin(i, n))
If you replace the call to selectionsort in the main function with sortbyabs then it now prints out [129 233 313 510 581 671 791 811 899 923]
Here is yet another way of sorting an array. The following sortbysumofdigits function sorts the array by the total sum of their individual digits. defn sumofdigits (n:Int) : if n == 0 : 0 else if n < 0 : sumofdigits(( n)) else : (n % 10) + sumofdigits(n / 10)
defn sortbysumofdigits (xs:Array<Int>) : defn indexofmin (start:Int, end:Int) : var minidx = start var minval = xs[start] for i in (start + 1) to end do : if sumofdigits(xs[i]) < sumofdigits(minval) : minidx = i minval = xs[i] minidx
defn swap (i:Int, j:Int) : if i != j : val xsi = xs[i] val xsj = xs[j] xs[i] = xsj xs[j] = xsi val n = length(xs) for i in 0 to (n  1) do : swap(i, indexofmin(i, n))
Replacing the call to selectionsort with sortbysumofdigits prints out [510 313 233 811 129 671 581 923 791 899]
You'll have noticed by now that the implementation of each sorting function is almost entirely identical except for one line. Here are the three different comparison functions. ;Compare value directly xs[i] < minval
;Compare absolute values abs(xs[i]) < abs(minval)
;Compare the sum of their digits sumofdigits(xs[i]) < sumofdigits(minval)
Couldn't we somehow write a general sort function and give it a specific way to compare things? We can! And the solution is to accept a key function that, for each item in the array, computes the value you wish to sort by. Here is the general sorting function, sortby , that accepts a key function key . defn sortby (key:Int > Int, xs:Array<Int>) : defn indexofmin (start:Int, end:Int) : var minidx = start var minval = xs[start] for i in (start + 1) to end do : if key(xs[i]) < key(minval) : minidx = i minval = xs[i] minidx
defn swap (i:Int, j:Int) : if i != j : val xsi = xs[i] val xsj = xs[j] xs[i] = xsj xs[j] = xsi val n = length(xs) for i in 0 to (n  1) do : swap(i, indexofmin(i, n))
Notice especially the type of the key argument. Int > Int
This says that key is a function that accepts a single argument, an Int , and returns an Int . We can update our main function to sort the array in three different ways by using three different key functions. defn identity (x:Int) : x defn main () : val xs = Array<Int>(10) xs[0] = 510 xs[1] = 923 xs[2] = 671 xs[3] = 811 xs[4] = 129 xs[5] = 581 xs[6] = 233 xs[7] = 791 xs[8] = 899 xs[9] = 313
println("Sort by value directly.") sortby(identity, xs) println(xs)
println("Sort by absolute value.") sortby(abs, xs) println(xs)
println("Sort by sum of digits.") sortby(sumofdigits, xs) println(xs) main()
Compiling and running the program prints out Sort by value directly. [791 581 129 233 313 510 671 811 899 923] Sort by absolute value. [129 233 313 510 581 671 791 811 899 923] Sort by sum of digits. [510 313 233 811 129 671 581 923 791 899] Up until now, we have always referred to a function in function call position. For example, abs( ... ) sumofdigits( ... )
But now you see that you can actually refer to functions directly as values to be passed to other functions! sortby(abs, xs) sortby(sumofdigits, xs)
Functions that take functions as arguments are called higherorder functions. They are an extremely powerful programming technique, and you'll soon see that you've already been using them everywhere without knowing it. Functions as Return ValuesWhen a language has firstclass functions, it means that functions can be treated as values. In the previous section we saw how to pass functions as arguments. Now we'll see how to use functions as return values. Here's a function called digit that accepts a single argument n , and returns a function. What the returned function does is extract and return the n 'th significant digit from its argument. defn digit (n:Int) > (Int > Int) : defn extractdigit (x:Int, n:Int) : if x < 0 : extractdigit(( x), n) else if n == 0 : x % 10 else : extractdigit(x / 10, n  1) defn extractdigitn (x:Int) : extractdigit(x, n) extractdigitn
Let's try it out on some numbers. defn main () : val firstdigit = digit(0) val thirddigit = digit(2)
defn testfirstdigit (x:Int) : println("The first digit of %_ is %_." % [x, firstdigit(x)]) testfirstdigit(413) testfirstdigit(313) testfirstdigit(41) testfirstdigit(137) testfirstdigit(991)
defn testthirddigit (x:Int) : println("The third digit of %_ is %_." % [x, thirddigit(x)]) testthirddigit(413) testthirddigit(313) testthirddigit(41) testthirddigit(137) testthirddigit(991)
main()
Compiling and running the program prints out The first digit of 413 is 3. The first digit of 313 is 3. The first digit of 41 is 1. The first digit of 137 is 7. The first digit of 991 is 1. The third digit of 413 is 4. The third digit of 313 is 3. The third digit of 41 is 0. The third digit of 137 is 1. The third digit of 991 is 9.
The type signature of digit is daunting at first. defn digit (n:Int) > (Int > Int)
Let's decipher it piece by piece. digit is a function that takes a single Int argument, and returns a (Int > Int) . And we learned previously that a (Int > Int) is a one argument function that takes an Int and returns an Int . The parentheses around Int > Int is not strictly necessary as > is a rightassociative operator. Thus, digit can also be declared the following way. defn digit (n:Int) > Int > Int
Write it in the way that is most clear to you. As an exercise, think about what the type of digit is.
Sorting By Digit
Now that we have a function for creating functions that are compatible with what is expected by sortby , let's use sortby to sort by different digits. Update the main function in our previous example. defn main () : val xs = Array<Int>(10) xs[0] = 510 xs[1] = 923 xs[2] = 671 xs[3] = 811 xs[4] = 129 xs[5] = 581 xs[6] = 233 xs[7] = 791 xs[8] = 899 xs[9] = 313
println("Sort by value directly.") sortby(identity, xs) println(xs)
println("Sort by absolute value.") sortby(abs, xs) println(xs)
println("Sort by sum of digits.") sortby(sumofdigits, xs) println(xs)
println("Sort by first digit.") sortby(digit(0), xs) println(xs)
println("Sort by second digit.") sortby(digit(1), xs) println(xs)
println("Sort by third digit.") sortby(digit(2), xs) println(xs)
Compile and run the program. It should print out Sort by value directly. [791 581 129 233 313 510 671 811 899 923] Sort by absolute value. [129 233 313 510 581 671 791 811 899 923] Sort by sum of digits. [510 313 233 811 129 671 581 923 791 899] Sort by first digit. [510 811 671 581 791 233 313 923 129 899] Sort by second digit. [510 811 313 923 129 233 671 581 791 899] Sort by third digit. [129 233 313 510 581 671 791 811 899 923]
Isn't that elegant! This is but a small demonstration of the power of firstclass functions. Core Library FunctionsThe sortby function is so general and useful that you might wonder whether it's already included in Stanza's core library. And it is, along with many other useful higher order functions. We'll show you a few of them here.
qsort!
The qsort! function is Stanza's included sorting function. It implements the quick sort algorithm, and you can use it sort collections in much the same way that you used the sortby function. One big difference, though, is that qsort! works on many different kinds of objects whereas your sortby function only worked on Int objects. val xs = Vector<String>() add(xs, "Patrick") add(xs, "Luca") add(xs, "Emmy") add(xs, "Sunny") add(xs, "Whiskey") add(xs, "Rummy") qsort!(xs) println(xs)
The above is an example of sorting a vector of strings, and it prints out ["Emmy" "Luca" "Patrick" "Rummy" "Sunny" "Whiskey"]
qsort! can optionally take a key function as its first argument for computing the item with which to sort. Here's how to sort the xs vector by the second letter.
defn secondletter (s:String) : s[1] qsort!(secondletter, xs) println(xs)
Running the program prints out ["Patrick" "Whiskey" "Emmy" "Rummy" "Luca" "Sunny"]
The third form of qsort! takes, as its second argument, a comparison function with which to sort by. The comparison function is given two items from the collection and must return true if the first argument is less than the second argument, or false otherwise. Here is an example of sorting a vector containing both integers and strings. Integers are less than other integers if their numeric value is smaller. Strings are compared against other strings according to their lexicographic order. And integers are less than strings if the integer is less than the length of the string. val xs = Vector<IntString>() add(xs, 1) add(xs, 3) add(xs, "A") add(xs, "B") add(xs, 4) add(xs, 10) add(xs, "Timon") add(xs, "Pumbaa") add(xs, 42)
defn compareitems (a:IntString, b:IntString) : match(a, b) : (a:Int, b:Int) : a < b (a:Int, b:String) : a < length(b) (a:String, b:Int) : length(a) < b (a:String, b:String) : a < b qsort!(xs, compareitems) println(xs)
Running the program prints out [10 1 "A" "B" 3 4 "Pumbaa" "Timon" 42]
find
The find function looks for the first item in a collection that satisfies a condition. The condition is given as a function, and takes a single argument representing an item from the collection. The condition function must return true if the item satisfies the condition, or false otherwise. find returns the item if it is found, or false otherwise. Here is an example of looking for the first capitalized word in a vector of strings. val xs = Vector<String>() add(xs, "they") add(xs, "call") add(xs, "me") add(xs, "Mr") add(xs, "Pig")
defn capitalized? (x:String) : uppercase?(x[0]) println(find(capitalized?, xs))
Running the program prints out Mr
indexwhen
The indexwhen function is similar to find , and looks for the first item in a collection that satisfies a condition. The difference is if the item is found, then indexwhen returns its index. Calling indexwhen instead of find on the previous example println(indexwhen(capitalized?, xs))
prints out 3
Maybe Objects and first
A Maybe is used to indicate the presence or absence of an object. A None object is a subtype of Maybe and indicates there is no object. A One object is a subtype of Maybe and contains a wrapped object. You can retrieve the wrapped object in a One object using the value function. The first function takes an argument function, f , and a collection xs , and calls f repeatedly on each item in the collection. f must return a Maybe object. first returns the first One object that is returned by f , or a None object if no call to f returns a One object. Here is an example of using first to find the first even sum of digits in a vector of integers. val xs = Vector<Int>() add(xs, 14) add(xs, 78) add(xs, 232) add(xs, 787) add(xs, 49)
defn evensum? (x:Int) : val s = sumofdigits(x) if s % 2 == 0 : One(s) else : None() match(first(evensum?, xs)) : (x:One<Int>) : println("The first even sum of digits is %_." % [value(x)]) (x:None) : println("No number in xs has an even sum of digits.")
map!
The map! function takes a function f and an array (or vector) xs . It then iterates through the array and replaces each item in the array with a call to f on the item. Here is how to capitalize each entry in a vector of strings using map! . val xs = Vector<String>() add(xs, "they") add(xs, "call") add(xs, "me") add(xs, "Mr") add(xs, "Pig")
defn capitalize (x:String) : append(uppercase(x[0 to 1]), x[1 to false]) map!(capitalize, xs) println(xs)
When ran, it prints out ["They" "Call" "Me" "Mr" "Pig"]
all?, any?, none?
all? is used to determine whether every item in a collection satisfies some condition. The all? function takes a function f and a collection xs . It returns true if calling f on every item in xs returns true . If f returns false on any item then all? immediately returns false .
Here is how we can use all? to test whether all numbers in xs are positive. val xs = Vector<Int>() add(xs, 4) add(xs, 2) add(xs, 3) add(xs, 8) add(xs, 5)
defn positive? (x:Int) : x > 0 all?(positive?, xs)
The any? and none? functions work similarly. any? determines whether any item satisfies the condition, and none? determines whether no item satisfies the condition.
do
Finally we get to the most commonly used higher order function of them all: the do function. The do function takes a function f and a collection xs and calls f on each item in the collection. Here is how to report the lengths of every string in a vector using do . val xs = Vector<String>() add(xs, "they") add(xs, "call") add(xs, "me") add(xs, "Mr") add(xs, "Pig")
defn reportlength (x:String) : println("%_ has length %_." % [x, length(x)]) do(reportlength, xs)
When ran, it prints out they has length 4. call has length 4. me has length 2. Mr has length 2. Pig has length 3.
At this point, particularly precocious readers might start to suspect that they have already used do in their programs without knowing it. Anonymous FunctionsBefore the introduction of higherorder functions it was natural for you to give every function in your program a name. After all, if a function has no name, then how would you call it? But after having been exposed to higherorder functions, you might now be wondering if it's possible to avoid giving functions a name. A lot of functions are now only ever used once, and only as an argument to another higherorder function. Anonymous functions are functions without names. Here is reportlength from the previous example written as an anonymous function. fn (x:String) : println("%_ has length %_." % [x, length(x)])
Here is an example of rewriting the do example using an anonymous function. val xs = Vector<String>() add(xs, "they") add(xs, "call") add(xs, "me") add(xs, "Mr") add(xs, "Pig") do(fn (x:String) : println("%_ has length %_." % [x, length(x)]) xs)
Notice how the reportlength function is now directly created using fn and passed immediately as an argument to do . The arguments to higherorder functions are often very short and anonymous functions provides a convenient syntax for using them.
Bidirectional Type Inference
The type inference rules for anonymous functions are different than those for named functions. For a named function, if a type annotation is left off of an argument, then the argument is assumed to have the ? type, and can accept anything. For an anonymous function, if a type annotation is left off of an argument, then the argument's type is inferred from the context in which the function is used. Thus the call to do in the above example could be more concisely written as do(fn (x) : println("%_ has length %_." % [x, length(x)]) xs)
From the context, the type of xs is Vector<String> , and since do calls the function on each item in xs , it is obvious that x must be of type String . Idiomatic Stanza code rarely contains type annotations for anonymous functions, and instead relies upon type inference. In certain circumstances, Stanza will be unable to infer the argument types, in which case you'll have to provide them explicitly.
Anonymous Function Shorthand
For extremely short anonymous functions, Stanza provides a syntactic shorthand. The following function fn (x) : x + 1
can be written equivalently as {_ + 1}
As another example, the following function fn (x, y) : x + 2 * y
can be written equivalently as {_ + 2 * _}
The shorthand consists of surrounding the function body with the {} brackets, and using underscores to denote arguments. To create anonymous functions with explicit type annotations use the following form. fn (x:Int, y:String) : x + length(y)
can be written equivalently as {_:Int + 2 * _:String}
Curried Function Shorthand
For extremely short anonymous functions consisting of a single function call, Stanza provides another syntactic shorthand. The following function fn (xs) : qsort!(abs, xs)
can be written equivalently as qsort!{abs, _}
Similarly, to create anonymous functions with explicit type annotations use the following form. fn (i:Int) : indexofmin(i, length(xs))
can be written equivalently as indexofmin{_:Int, length(xs)}
The Application Operator
With the introduction of anonymous functions, you'll find that you can implement lots of functionality using single lines of code. To help with this programming style, Stanza provides the $ operator to help reduce the number of nested expressions. The expression f $ x
is equivalent to f(x)
Thus the $ operator is just a shorthand for function application. Notice, however, that with the $ operator, the above expression did not require any parentheses. There is a very common usage pattern involving both curried functions and the $ operator. Here is what it looks like. f{x, _} $ y
Let's remove the syntactic shorthands incrementally to figure out what the above means. First, we will write out the $ operator in full. (f{x, _})(y)
Next, we will write out the curried function in full. (fn (a) : f(x, a))(y)
So the expression, when written in full, just creates an anonymous function and then immediately calls it with y . Calling the anonymous function is then equivalent to f(x, y)
Thus the expression f{x, _} $ y
is equivalent to f(x, y)
You can think of the $ operator as substituting the right hand side expression in for the underscores in the left hand side expression. This usage pattern is often used to chain a long sequence of operations together. f{1, _} $ head $ g{2, _} $ xs[2]
is a shorthand for writing val result1 = xs[2] val result2 = g(2, result1) val result3 = head(result2) f(1, result3)
Here is a concrete example of an idiomatic usage of the $ operator. In the demonstration of the qsort! operator, we explicitly created a compareitems function to pass into qsort! . defn compareitems (a:IntString, b:IntString) : match(a, b) : (a:Int, b:Int) : a < b (a:Int, b:String) : a < length(b) (a:String, b:Int) : length(a) < b (a:String, b:String) : a < b qsort!(xs, compareitems)
But here is another way it can be (and often is) written. qsort!{xs, _} $ fn (a, b) : match(a, b) : (a:Int, b:Int) : a < b (a:Int, b:String) : a < length(b) (a:String, b:Int) : length(a) < b (a:String, b:String) : a < b
Since the types of the arguments of anonymous functions are inferred, there is also no need to provide explicit type annotations. The For ConstructNow that you've been introduced to anonymous functions and higherorder functions, we are now ready to introduce the full for construct. The expression for x in xs do : println(x)
is equivalent to do(fn (x) : println(x) xs)
As mentioned before, the for construct is not a looping mechanism. It is a syntactic shorthand for calling higherorder functions of a certain form. As explained earlier, the do function is what's responsible for looping over each element in xs . The for construct can be called with multiple bindings as well. for (x in xs, y in ys) do : println(x + y)
is equivalent to do(fn (x, y) : println(x + y) xs, ys)
Thus, in general, the for construct expands to a call to a higher order function where the first argument is an anonymous function followed by n remaining arguments. The anonymous function must take n arguments, one for each of the remaining arguments. There are forms of the do function that accept multiple collections. The collections are iterated over in parallel, and iteration stops when it reaches the end of any one of them. The following example prints every item in a vector coupled with its index. val xs = Vector<String>() add(xs, "Patrick") add(xs, "Luca") add(xs, "Emmy")
for (x in xs, i in 0 to false) do : println("Element %_ is at index %_." % [x, i])
It prints out Element Patrick is at index 0. Element Luca is at index 1. Element Emmy is at index 2.
Operating Functions
find , all? , any? , none? , and indexwhen? also have multiple collection versions that can be used with a for construct with multiple bindings.
Functions like do , with type signatures compatible with the for construct, are called operating functions. Stanza's core library includes a large number of commonly used ones. For more details, read the reference documentation. Occasionally, it might also be appropriate to implement your own operating function. Here is an operating function that first iterates over each odd integer in a vector and then iterates over each even integer in the vector. defn dooddtheneven (f: Int > ?, xs:Vector<Int>) : for x in xs do : if x % 2 != 0 : f(x) for x in xs do : if x % 2 == 0 : f(x)
Here is an example of using it in conjunction with the for construct. val xs = Vector<Int>() add(xs, 1) add(xs, 3) add(xs, 2) add(xs, 6) add(xs, 5) add(xs, 2) add(xs, 4) add(xs, 3)
for x in xs dooddtheneven : println(x)
Compiling and running the above prints out 1 3 5 3 2 6 2 4 Stanza IdiomsWith our new knowledge of anonymous functions, curried functions, and the for construct, we can now revisit our examples of using the core library and write them using standard Stanza idioms and functions. ;A vector of strings val strs = Vector<String>() addall(strs, ["patrick", "luca", "emmy", "Sunny", "whiskey", "Rummy"])
;Sort by the second letter println("1.") qsort!({_[1]}, strs) println(strs)
;A vector of ints and strings val intstrs = Vector<IntString>() addall(intstrs, [1, 3, "A", "B", 4, 10, "Timon", "Pumbaa", 42])
;Sort using custom comparison function println("\n2.") qsort!{intstrs, _} $ fn (a, b) : match(a, b) : (a:Int, b:Int) : a < b (a:Int, b:String) : a < length(b) (a:String, b:Int) : length(a) < b (a:String, b:String) : a < b println(xs)
;Find first capitalized word println("\n3.") println $ for s in strs find : uppercase?(x[0])
;Find index of first capitalized word println("\n4.") println $ for s in strs indexwhen : uppercase?(x[0])
;Capitalize every word println("\n5.") for s in strs map! : append(uppercase(x[0 to 1]), x[1 to false]) println(strs)
;A vector of integers val ints = Vector<Int>() addall(ints, [4, 2, 3, 8, 5])
;Are they all positive? println("\n6.") println $ for x in ints all? : x > 0
;Report lengths of string along with their index println("\n7.") for (s in strs, i in 0 to false) do : println("strs[%_] = %_. Length = %_." % [i, strs[i], length(strs[i])])
Compiling and running all of the above print outs 1. ["patrick" "whiskey" "emmy" "Rummy" "luca" "Sunny"]
2. [10 1 "A" "B" 3 4 "Pumbaa" "Timon" 42]
3. Rummy
4. 3
5. ["Patrick" "Whiskey" "Emmy" "Rummy" "Luca" "Sunny"]
6. false
7. strs[0] = Patrick. Length = 7. strs[1] = Whiskey. Length = 7. strs[2] = Emmy. Length = 4. strs[3] = Rummy. Length = 5. strs[4] = Luca. Length = 4. strs[5] = Sunny. Length = 5. Tail CallsConsider the following function for computing the sum of all the positive integers less than or equal to n . defn sumof (n:Int) : if n > 0 : n + sumof(n  1) else : 0
Calling sumof(6) returns 21 . Here's a visualization of the execution context as that operation is being performed. sumof(6) = 6 + sumof(5) = 6 + 5 + sumof(4) = 6 + 5 + 4 + sumof(3) = 6 + 5 + 4 + 3 + sumof(2) = 6 + 5 + 4 + 3 + 2 + sumof(1) = 6 + 5 + 4 + 3 + 2 + 1 + sumof(0) = 6 + 5 + 4 + 3 + 2 + 1 + 0 = 6 + 5 + 4 + 3 + 2 + 1 = 6 + 5 + 4 + 3 + 3 = 6 + 5 + 4 + 6 = 6 + 5 + 10 = 6 + 15 = 21
Observe that the computation of sumof(6) requires knowing the result of sumof(5) . And so we then recursively compute the result of sumof(5) while remembering that we should add 6 to the result to get the final answer. Similarly, the computation of sumof(5) requires the result of sumof(4) . Et cetera. Each recursive invocation of sumof requires us to remember what to do with the result. This is our execution context, and in Stanza, is saved in a stack of activation records. How big does this stack get? Well, for sumof , it grows to contain exactly n activation records. This can be verified by forcing a program failure when n is equal to 0 and looking at the stack trace. defn sumof (n:Int) : if n > 0 : n + sumof(n  1) else : fatal("n reached zero.")
When compiled and ran, the above prints out FATAL ERROR: n reached zero. at test.stanza:7.10 at test.stanza:6.18 at test.stanza:6.18 at test.stanza:6.18 at test.stanza:6.18 at test.stanza:6.18 at test.stanza:6.18 at test.stanza:9.0
Each test.stanza:6.18 entry in the stack trace refers to a recursive call to sumof(n  1) . Thus you can see that there are 6 entries corresponding to calling sumof(6) . activation records take up space. If n is too large, then eventually the stack of activation records will consume all of your program memory.
An Iterative Algorithm
Now consider this alternative implementation of sumof . defn sumof (n:Int) : x+sumof(0, n) defn x+sumof (x:Int, n:Int) : if n > 0 : x+sumof(x + n, n  1) else : x
Here's a visualization of the execution context of computing sumof(6) . sumof(6) = x+sumof(0, 6) = x+sumof(6, 5) = x+sumof(11, 4) = x+sumof(15, 3) = x+sumof(18, 2) = x+sumof(20, 1) = x+sumof(21, 0) = 21
Similar to before, the computation of x+sumof(0, 6) requires knowing the result of x+sumof(6, 5) . And so we then recursively compute the result of x+sumof(6, 5) . But this time, we don't have to remember what to do with the result! The result of x+sumof(6, 5) is the result of x+sumof(0, 6) , so just return whatever x+sumof(6, 5) returns. In concrete terms, what this means is that Stanza can discard the activation record for x+sumof(0, 6) immediately before calling x+sumof(6, 5) since there's no context to remember. If that is done, then the number of activation records does not grow, no matter how large n is. And thus the program will not run out of memory. This optimization is called tail call optimization.
Tail Call Optimization
By default, Stanza does not optimize tail calls in functions. This is done for the purposes of debugging. It is useful to have a complete stack trace, even if not strictly necessary for correct operation of the algorithm. To tell Stanza to optimize tail calls in a function, we have to explicitly declare the function as being tail call optimized. defn sumof (n:Int) : x+sumof(0, n) defn* x+sumof (x:Int, n:Int) : if n > 0 : x+sumof(x + n, n  1) else : x
defn* is the tail call optimized version of defn . Similarly, defmethod* is the tail call optimized version of defmethod , and fn* is the tail call optimized version of fn .
To verify that the stack frames are properly being discarded, we'll again force the program to fail when n is equal to 0 and examine the stack trace. defn* x+sumof (x:Int, n:Int) : if n > 0 : x+sumof(x + n, n  1) else : fatal("n reached zero.")
Compiling and running the program prints FATAL ERROR: n reached zero. at tests/test.stanza:6.3 at tests/test.stanza:20.10
There are now no stack frames corresponding to x+sumof . They have all been discarded. Revisiting WhileWith the introduction of tail calls, it is time for us to unveil the internals of the while loop construct. The expression var i = 0 while i < 10 : println(i) i = i + 1
is equivalent to var i = 0 defn* loop () : if i < 10 : println(i) i = i + 1 loop() loop()
Thus the while construct simply defines a local tail call optimized function and then calls it. Directly expressing loops using recursive functions can often be much more natural than using a while loop. A while loop loops by default, and the programmer has to specify when it should stop looping. In constrast, a recursive function does not loop by default, and the programmer instead specifies when to perform another iteration. Here is an example of using a tail call optimized function for finding the index of an integer x in a sorted vector xs using binary search. defn bsearch (x:Int, xs:Vector<Int>) : label<IntFalse> return : defn* loop (start:Int, end:Int) : if start < end : val mid = start + (end  start) / 2 if x < xs[mid] : loop(start, mid) else if x > xs[mid] : loop(mid + 1, end) else : return(mid) loop(0, length(xs))
loop finds the index of x , assuming that it exists between the start index and end index (exclusive). It does this by computing a midpoint, mid , between the two indices. If x is less than the element at mid then it looks again in the first half of the range. If x is greater than the element at mid then it looks again in the second half of the range. Otherwise it has found x , and it is at index mid .
Let's try looking for the numbers 1 , 14 , and 13 . defn main () : val xs = Vector<Int>() addall(xs, [1,3,4,7,8,11,14,18,20,35]) println(bsearch(1, xs)) println(bsearch(14, xs)) println(bsearch(13, xs))
main()
When compiled and ran, the above prints out 0 6 false
