#19 - But All My Friends Have Trampolines

Lets step away from Kotlin for a minute and revisit Groovy. Let's also revisit an alternate solution to the looping problem, recursion. To really demonstrate this feature, I am going to need to show you two solutions. First the recursive Groovy solution.

def fb
fb = {i, s = "" ->
    s = ((i%3)
        ? ((i%5)?i:"Buzz")
        : (i%5?"Fizz":"FizzBuzz")) + "\n" + s
    i <= 1 ? s : fb(i - 1, s)
}

fb(100)

This is a very simple recursive solution.  Base case happens on line 6 if i is one or less. Lines 3-6 determines the fizzy and buzziness, and line 9 sets the limit with the first call in. It works, trust me. In fact, try it out! You can download Groovy if you don't already have it, or you can Etry it out online.

Really. Go try it. Right now. I'll wait. It's important. No, seriously. Do it.

Tried it already? Great, now go change line 7 so that it will calculate FizzBuzz from one to one thousand. Did it work? Great let's move on. Wait, what? It didn't work? Something about a StackOverflowError? Awesome, you did it right. Let's continue the discussion.

The principal problem with deeply recursive solutions is the sheer amount of bookkeeping needed to keep the recursion straight.  Since this is a deep rather than a broad recursion each and every step in the iteration takes up space on the stack.  Each iterative step costs memory, and memory is limited unlike clock cycles.

So how do we fix this? Install a trampoline, invite the neighbor kids over, and see who you can chain-bounce onto the roof.

def fb
fb = {i, s = "" ->
    s = ((i%3)
        ? ((i%5)?i:"Buzz")
        : (i%5?"Fizz":"FizzBuzz")) + "\n" + s
    i <= 1 ? s : fb.trampoline(i - 1, s)
}.trampoline()

fb(100)

This is the actual solution for this week.  With the simple addition of two calls to the trampoline method in lines 6 and 7 this recursive solution now uses a form of a technique called tail recursion, where instead of layering on another level of memory for the stack we take the existing layer wipe it clean, and just jump back to the beginning of the method without a subroutine. What was once a gosub is now a goto. And we are no no longer beholden to the size of the stack but instead to the size of a String.  This isn't always appropriate in all situations, you need to be sure you are not preserving information from one recursive call to the next.

The thing about trampolines is that trying to chain-jump onto the roof is how bones tend to get broken.  Which is why we don't have a trampoline, even though all of my children's friends do.

[code samples edited for line width]

Buzz 10 - How Many Times?

I'm going to be changing up my plan for Buzz entries.  I had intended on writing 500-1500 essays tangentially related to the FizzBuzz at hand (much like my tiny e-book on Amazon) but I see several problems with it. First, it can ruin the natural progression of solutions if I hold out one solution for a particular post I have planned.  Second, it will ruin the the general feel of this blog, going from technical to random life experiences and then back.  Third, writing that much text on a deadline is kinda hard with my current life balance.  Really, should 1st graders have homework?  Even if it is reading with a parent 20 minutes a night?

So here is the new Buzz plan... for each Buzz I will revisit a language introduced in a previous Fizz entry, and re-work a number entry not in that language using some of the unique features of the language.  For this first entry the selection is limited, but actually relevant to the current numeric theme, especially since Groovy has so many ways to do repitition.

100 times {
  int i = it+1
  if ((i % 3 == 0) && (i % 5 == 0)) {
    println "FizzBuzz"
  } else if (i % 3 == 0) {
    println "Fizz"
  } else if (i % 5 == 0) {
    println "Buzz"
  } else {
    println i
  }
}

Lines one and two are the focus for this post, because the rest of it is a simple transliteration to standard Groovy.

On first reading, it does what it says. Repeat the enclosed block 100 times. But in the syntax sugar and details of the API are some common assumptions. First, what the current count is matters, but there is no explicit variable for that. Each closure without an argument block gets a single variable it that you don't need to declare and just exists. Kind of like this in methods. (And when is some programming language going to introduce that?)

The next assumption is what number to count from. You would think that counting from 1 would be sensible. But Groovy uses zero based arrays, like nearly all popular languages, so instead it starts all couting from zero. Line 2 is an optimization so we don't have to extend our math into the rest of the method.

The rest is pure syntactic sugar. When a symbol that could be a method trails an object with no punctuation it is presumed to be a method call in Groovy. And when a single closure follows a method call, whether or not it is in the argument list, it is added to the argument list of the method. The integer 100 is boxed up to a java.lang.Integer class. And via the Meta-Object-Protocol we can graft in a random times method onto the Ingeger class even though it doesn't exist in the plain JDK.

The end result is something that looks a little bit more like a spoken sentence, but not too close.

Fizz 3 - Elvis Has Left the Building (Groovy)

Whenever I count "Fizz" in this series I will examine a language that has yet to be examined before. There is no shortage of candidates but the trick will be to keep the languages choices relevant and readily verifyable (this could be tricky).  Ideally I will be able to consider a feature that is relatively unique to that language or family of languages.

For this post I will examine the Groovy programming language.  Picking a relatively unique feature for Groovy is a fairly hard prospect since it tries to pull all the best parts from all other languages.  It is based on Java, so it's a C like curly brace language.  It compiles to JVM byte code.  It is object oriented, but strives to delay it's method dispatch as late as possible, enabling multiple dispatch method invocations as seen in Common Lisp.  It uses closure like blocks much like you would see in Ruby.

There are a lot of neat tricks in Groovy so I see myself coming back to this language later in this series.  But perhaps the most unique feature of Groovy, or the one feature that it has gone the furthest to popularize, then it would be the "Elvis Operator:" ?: a C style ternary operator with the middle operand removed.

for (int i = 1; i <= 100; i++) {
  String answer = ""

  if (i%3 == 0) {
    answer += "Fizz"
  }

  if (i%5 == 0) {
    answer += "Buzz"
  }
  
  println answer ?: i
}

This isn't the most idiomatic Groovy code for this solution. It is intended to demonstrate just the Elvis operator with all other awesomeness removed.  I have a three statement solution that shows other Groovy features such as blocks and ranges. But for the purpose of this post we should focus just on the unique feature. There, on line 12 of the verbosely expressed code, is the Elvis operator. Why is it called Elvis? If you rotate it clockwise the question mark kind of forms Elvis Presley's hair just above his eyes.

But what does it do?  It clearly has no hips to shake suggestively since he is being expressed from the nose up.  Elvis picks the first "true" item it sees and returns only that item.  Mode technically, the left hand side of the operator is evaluated for "groovy truth," and if it returns negative (null, false, zero, or empty string in most cases) then the right hand side of the operator is returned. If the left had side matches any other value, then the left hand side of the operator is returned.

This roughly equates to the C style statement x ? x : y. If the middle operator leaves the building, along with the white space, you are left with the Elvis operator: x ?: y. Even though Elvis has left the building, his legacy remains.