00:00:20.880
This should be obvious by now: I've lost my voice. So, if you want to see this talk with proper audio, please leave the room lobby and stream it from Confreaks. Otherwise, please be nice and quiet; keep the rustling, typing, and everything else to a minimum so that I don't have to use any more voice than necessary.
00:00:30.240
Like I said, this is going to be an adventure for both of us. So, Goru 2010 was my first conference. Jim W. gave the keynote, covering a wide variety of topics including physical chemistry and emission spectrometry. He had this book recommended to him by many nerds, and he talked about a study group he set up to go through it.
00:00:49.719
He demonstrated the content from the first two chapters, and then pointed out that everything in the 90-minute talk he had given hadn’t used assignment. That talk by Jim W. is the inspiration for this talk. The book is called "Structure and Interpretation of Computer Programs." It was the programming 101 book at MIT for a very long time. It is wonderful.
00:01:15.000
So a little bit about me: I'm Aja Hammerly. You can tweet me during my talks, as my phone is down there, so you can't interrupt me. I’m also a Fiver on GitHub and hope to Vlog more frequently in the future at my blog. I’m not an expert on this stuff in any means, but I have been part of three functional study groups. I'm part of Seattle Ruby and am interested in the esoteric and academic parts of programming.
00:01:39.960
Truthfully, I’m seeing functional programming everywhere. Right before this talk, I was reading Twitter, and someone pointed out that all of the non-Ruby talks at RubyConf this year are about functional programming, which might be a hint.
00:02:00.280
So, what is functional programming? Here’s the Wikipedia definition: In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids changing state.
00:02:22.239
This is a comment from one of my coworkers who I respect a lot: the idea of mutable state is suspicious and easy to mess up. So, in this talk, I’m going to focus on one aspect of functional programming, which is not using mutable data structures. There will be no assignment in any code presented in this talk.
00:02:50.240
There won’t be a single assignment in Ruby. There’s a lot of Scheme in this talk. In Scheme, we use 'set!' so there can be no 'set!'. If modifying an object seems important, we'll clone it to create a new one instead. To set expectations: there are 112 slides, a lot of good content, lots of parentheses, and no ponies.
00:03:15.000
Why should you care about functional programming? First of all, it's easier to test—there's less setup, less debugging, and you always start from a known state. Previous tests can’t alter the state for the next test. Functional programming supports concurrency very well: if nothing is modifying state, it doesn’t matter how many threads you have because you don’t have to deal with locks on shared resources.
00:03:34.680
Reduce systems frequently use functional programming techniques. If your code doesn’t modify state, it’s always safe to reuse it in other programs and parts of the same program. Functional programs tend to be very brief and concise. Some people think this is awesome; I am one of them. Others think it isn’t; I apologize if you’re among those who don’t.
00:03:50.400
If you already use Ruby, it easily allows for functional techniques, though you might be using them poorly without realizing it. If you do any JavaScript, you’re probably writing some functional stuff and doing it poorly, so you might as well do it right. Learning it in Ruby is easy, and I find that when I’m learning a new paradigm, it’s best to do it with a language I’m already comfortable with.
00:04:11.560
I’m going to do this talk half in Scheme and half in Ruby. I believe everyone should be a polyglot programmer to make it easier. My slides are laid out side by side: Ruby is on the right in red, while Scheme is on the left in blue. The first thing you need to know about Scheme is that, unlike Ruby, it uses prefix notation. That means the operator comes first, so instead of 5 + 3, you write (+ 5 3).
00:04:39.280
You might think that's kind of lame, except when you see that you can do (* 1 2 3) with only a single asterisk. Using this kind of technique, your powerful grouping becomes more obvious; you can see how to group things with parentheses. You can also call named functions, not just mathematical operators, in the same way that ('add 1') can be a success function for numbers.
00:04:58.360
You can define functions in Scheme by naming the function and its arguments. For instance, we’re defining a function called 'square' that takes 'n' as an argument, and within its body, you would calculate (* n n). Just like we have 'def' and 'end' in Ruby, we use parentheses in Scheme to denote code blocks or groups. The closing parentheses serve as the equivalent of 'end' in Ruby.
00:05:13.600
Now we call that function with its name and argument in parentheses. Scheme also has several conditional expressions, which I will use 'cond' throughout this talk; it's like 'case' in Ruby. Here is a definition of absolute value in Scheme: if our argument is greater than zero, we return that argument; if it's equal to zero, we return zero; if it's less than zero, we return the opposite of it.
00:05:30.920
This is another place where prefix notation is awesome because I can use a unary operation in exactly the same way I would do a subtraction. Since the last time we gave this talk, this concept blew people's minds, it’s worth noting that yes, you can do this in Ruby too. You don’t have to put anything after the case: if you do this, it evaluates each of the clauses in order until it finds the first truthy one.
00:05:49.920
Since everything in Ruby is truthy or falsy, this works great. I use it all the time. I learned this technique from senior members of Seattle RB, so add this to your arsenal if you take nothing else from this talk. Returning to our conditionals: this is a slightly modified version of the Scheme side. This is how real Scheme would write it; it’s much more condensed, and it's pretty; however, you might think it has too many parentheses.
00:06:00.640
That’s okay; you'll get over it. People have also asked if you can use 'if' in Scheme. Here’s an example of defining a predicate function. This 'predicate' function is one that returns true or false. If the temperature is greater than 65, we can return true in Ruby, which is 'true'; otherwise, it is false, represented by 'false' in Scheme.
00:06:25.920
You can see the equivalent Ruby code laid out the same way as earlier provided in two different languages. So, most functional languages heavily use lists. In Scheme, we represent lists with an open parenthesis and the elements of the list without commas, followed by a closing parenthesis. This sometimes confuses me when switching back and forth between languages.
00:06:51.520
For our purposes in this talk, I’ll represent lists in Scheme as arrays in Ruby. They are not the same, but this makes the parallels easier to understand. Most functional languages make heavy use of 'car' and 'cdr'. 'Car' refers to the first element, and if you want to know why, ask Wikipedia. I don't have the space or voice to explain that right now.
00:07:05.040
In Ruby, to get rest, you call 'array[1..-1]'—that’s gross. So I’ll assume that 'cdr' exists as well, and when I built these slides, I redefined arrays to add a 'rest' method. When you're dealing with lists, it’s often helpful to know if your list is empty. Ruby has a method for that, while Scheme uses 'null?'. I'm applying the Canadian pronunciation of 'null?' there.
00:07:24.440
Knowing if your list is empty is essential for recursion. Let’s go through the canonical recursion example: factorial. The standard recursive definition of factorial goes as follows: if our input argument is one, the factorial of one is one, so we return that. Otherwise, we return the number multiplied by the factorial of the number minus one.
00:07:50.080
Here’s the same in Scheme and Ruby side by side. Now, let’s explore something slightly more complicated, known as tail call optimization. This is about exponentiation, specifically raising the base 'b' to the nth power. Remember your math: anything raised to the zeroth power is one, so that’s our base case.
00:08:17.840
If 'n' is equal to zero, we return one; otherwise, we multiply our base by the result of raising 'b' to the power of 'n-1'. This raises a small problem, as the stack gets deeper each time we call it recursively. Imagine you’re calculating 2 raised to the 4th power; you’re saving all those calls on the stack—2 * 2 * 2 * 2.
00:08:43.520
This can cause a stack overflow. But there’s a way to reduce the stack depth using tail call optimization. You can add a helper function that takes an accumulator. We now have 'B' for the base and 'C' for how many times we raise it, and 'P' for the partial product of all the multiplications we’ve done so far.
00:09:04.080
The goal is to create a recursive call to the helper function with the current base while decrementing the counter. So, if our counter is zero, we've done all the multiplications we intend to do and should return 'P'. If not, we continue the recursion, multiplying the base by what has been calculated so far.
00:09:25.440
If your language supports tail call optimization, it helps reduce the stack size, allowing you not to accumulate those extra calls. You’ll note our original function remains; we hide the helper and call it with the initial base and raise it to the power of zero as the initial product.
00:09:45.520
When we run this code in a language that supports tail call optimization, the stack looks much flatter, using less space. This might feel like a contrived example, but let’s dive into a problem that I love to test a new functional language with. Recently, I was part of a study group in Seattle, where we finished discussing a book called "Build Your Own Lisp in C."
00:10:08.880
This was a language-building exercise that, if you squint really hard, resembles Lisp. One of the exercises from the last chapter was to write a functional program using this Lisp-like language. The problem posed is: how many ways can you make change for a dollar using half dollars, quarters, dimes, nickels, and pennies?
00:10:32.480
To tackle this complexity, let’s simplify. We can ask: how many ways can you make some amount with some coins? This simpler phrasing gives us a basic function outline to define, stating that it takes two arguments: amount and coins. Here, amount refers to the number of cents, while coins represents the coin denominations.
00:10:47.600
I assume I have an infinite number of each denomination, all organized in descending value order. Thus, my main question evolves: how many ways can you make different amounts with coins? The first case we’ll handle is when we have no coins available. If that’s the case, we simply can’t make any change.
00:11:08.000
Now let's run this function with the amount of 1 cent and an empty list of coins. The correct output is zero because I have no coins. Awesome! Now let’s add a case for using pennies. The logic here is straightforward: if we want to make one cent using pennies, there’s only one way—by using one penny.
00:11:29.000
However, the next challenge is how to make five cents using only pennies. Similarly, we need to write a case for that. Now we attempt to make five cents using only pennies, and the result is the same: one way. And as we get more complicated, note that when trying amounts greater than the specified denominations, our logic will also require a method for handling this.
00:11:50.000
Next, let’s look at using nickels. The case when we have five cents—one nickel and four pennies—should yield two such ways. Yet let’s see how our code handles that. Unfortunately, it might not be correctly capturing all cases, pointing out that we could better recalculate how we consider using both nickels and pennies together.
00:12:10.000
When we substitute the arguments again, we need to recognize our upfront and recursive cases without missing elements. If we have five cents and we make a nickel, at least we ought not to overlook coins that may not factor in for the resultant amount.
00:12:32.480
Now, if we neglect checking for conditions where we have available coins to check against, we see inaccuracies returning false because we fail to account for all ways to achieve the target amount. It's crucial to incorporate branching paths in both logic flows that include and omit the first coin.
00:12:55.080
When we complete our calculations, we can formulate proper return responses tracking those edge cases at each step with careful evaluation. Therefore we can iteratively expand how many pennies can work with our available values or branching paths of coins leading to 'n' or zero.
00:13:15.840
Finally, let's say we want to check how many ways to make seven cents using only nickels. The result should return zero because it isn’t possible. Each time we revisit the setup, we find ourselves reflecting recursively while perfectly designed to ensure no overlapping cases generate anger.
00:13:40.000
As we closed in on our original complexity of one dollar, the answer remains 292 ways—using a combination of cents. If we were to break this down to scheme, we introduce similar recursive functions that would demonstrate how closely both Ruby and Scheme yield the same computational outcomes for overlapping operations.
00:14:02.320
In conclusion, as I sum up, many functional paradigms coexist throughout programming languages enabling clearer definitions while maintaining principles of closure and immutability where beneficial. As you explore further through these angled perspectives, consider diving deeper into the works of references like "Structure and Interpretation of Computer Programs" and others whilst grounding competence with exercises.
00:14:26.560
Final resources: 'The Little Schemer.' I highly recommend starting a study group for this book wherever you can. Also, look into the work of so-called 'Wizard Books,' which might feel heavy for newcomers but offer immensely rewarding content. I can potentially add to this list the likes of 'The Little Lisper' or 'The Little Reasoner' for those searching out additional perspectives and punchy practices to grow as a programmer.
00:14:49.430
Thank you for being here! I have some dinosaur figures which I’m giving away to those who share interesting insights or questions during the talk! Feel free to come find me. I saw some folks taking pictures, so let people know my slides are already up on my website.
00:15:08.000
I will also post this version of the slides shortly on my blog. If you want to rate my presentation, you can also visit my speaker rate page. Now let’s see if my voice still holds as I wrap it up! But once again, thank you for your attention!
