Search
Talks
A Muggle's Guide to Tail Call Optimization in Ruby
Edit
#tail-call-optimization
#ruby-vm
#functional-programming
#recursion
#ruby-internals
#performance
Summarized using AI

A Muggle's Guide to Tail Call Optimization in Ruby

Danny Guinther • November 23, 2015 • San Antonio, TX • Talk

In the presentation titled A Muggle's Guide to Tail Call Optimization in Ruby, Danny Guinther explores the concept of tail call optimization (TCO) specifically within the Ruby programming language. The talk opens with light-hearted context tying in references from 'Harry Potter' and 'Star Wars', while introducing the challenges of system stack errors that developers may face.

Key points discussed in the video include:

  • Understanding Tail Calls: A tail call is defined as a subroutine call executed as the final action of a procedure. For example, if a method calls another at its end without additional operations, it's considered a tail call.
  • Recursion and Tail Recursion: Tail recursion is introduced as a useful concept when combined with TCO, allowing for reduced stack resource consumption. The concept is illustrated through examples that differentiate between regular recursion and tail recursion.
  • Benefits of Tail Call Optimization: TCO prevents system stack overflow by allowing the Ruby interpreter to reuse stack frames for tail-recursive calls, thus optimizing memory usage. This optimization conceptually transforms certain recursive methods into loops, which are generally more efficient.
  • Ruby's Status on TCO: Although TCO is part of Ruby's internal mechanisms since version 1.9.2, it is not enabled by default, which leads to practical considerations for developers interested in incorporating it into their applications.
  • Enabling TCO in Ruby: Methods to enable TCO in Ruby are discussed, including potential risks associated with deploying TCO features in production environments. Guinther shares insights about his creation of a gem called TCO Method, designed to facilitate experimentation with TCO.
  • Performance Implications: The presentation underscores the performance benefits of TCO through better memory management and garbage collection, while also acknowledging the complexity it adds to debugging due to the absence of detailed stack traces.

Overall, the session encourages Ruby developers to delve further into tail call optimization to leverage its capabilities while being mindful of its implications in debugging and performance.

In conclusion, while TCO is not inherently beneficial for all scenarios, it demonstrates great promise and efficiency when used thoughtfully in appropriate contexts. The audience is directed to explore further resources for deeper insights into Ruby's internal workings.

A Muggle's Guide to Tail Call Optimization in Ruby
Danny Guinther • November 23, 2015 • San Antonio, TX • Talk

A Muggle's Guide to Tail Call Optimization in Ruby by Danny Guinther

Submitted for your approval: a circle of torment unchronicled by the poets of old, a terror at the heart of many a horror story: SystemStackError: stack level too deep

Tremble no more! Conquer the well of eternity!

Behold the secrets of tail recursion and tail call optimization in Ruby! Witness the metamorphosis of a simple function as we explore the hidden power of tail call optimization buried deep within the Ruby VM! Follow the transformation to the revelation of tail call optimization's most ghastly secret: in many ways it's really just a special type of loop construct! The horror!

Help us caption & translate this video!

http://amara.org/v/H1T8/

RubyConf 2015

00:00:15.280 Good morning, everybody! I'm going to try to start just a few seconds early because chances are I will go over time. I'd also like to give you guys an opportunity to ask questions. In the event that you can't read any of the slides or anything like that, feel free to shout at me and say, 'Hey! Could you read that for me?' There’s a lot of good stuff.
00:00:34.559 All right, so the first thing I want to ask you is: how many of you went to Aaron's keynote yesterday? Nice! That's great because I was super excited about his keynote. It serves as a fantastic introduction to many of the topics we'll discuss today.
00:00:51.800 So, without further ado, today my presentation, as you all clearly know because you’re here, is 'A Muggle's Guide to Tail Call Optimization in Ruby'. I'll get into what I mean by that shortly, but first, let’s consider some alternate titles.
00:01:34.879 I was thinking of 'Harry Potter and The Well of Eternity' because SystemStackError can be a nightmare, especially those backtraces that seem to go on for days. I just wanted to get this out up front: Harry is a parselmouth, and his scripting language of choice is probably going to be Python, not Ruby. So if we can start to come to terms with that now, that would be great.
00:02:05.987 In that vein, I want to give you a warning—or maybe not so much a warning, but for whatever reason, this topic, like quite a few others in our industry, can get pretty religious at times. Whether it’s Vim or Emacs, we encounter divides between functional and object-oriented languages.
00:02:40.840 So if you'll indulge me for a moment, I'd like you to imagine, if you dare, a world without Minan. For those of you who don’t know what Minan is, it stands for 'Matz is nice' and well, I can’t find the picture I had about it on the internet anymore. But it's Mats with a puppet, and I don't know why that’s relevant.
00:02:59.919 From the blog of Guido van Rossum, who, for those of you who may not know, is the creator of Python, back in 2009, there was a lot of talk about tail call optimization. Here are just a few select quotes from his blog related to it: 'How very Pythonic of you to make up stupid reasons for not implementing a very simple optimization.' This demonstrates poor decision-making, poor performance, and immature ideology.
00:03:38.359 It's evident that this individual prefers functional paradigms and cannot believe that Python has not included tail call optimization. On the total opposite end of the spectrum, it's refreshing that Guido stuck with his intuitions rather than submitting to the TCO requesting functional enthusiasts.
00:04:30.679 That said, the good news is that no matter which side you are on in this matter, you’re going to be right, because it’s all about your point of view. As Obi-Wan tells us, everything depends on your point of view. I should also warn you that there are a few Star Wars references in this talk, despite the Harry Potter theme, because I’m really excited for next month!
00:05:16.080 So, moving on—what the hell is a muggle? For those of you who may not know, a muggle in the Harry Potter books is someone who lacks magical ability. Now, if you’re wondering why this matters in our context, I want to present this topic without magic. By 'magic', I mean those magical things that happen behind the scenes, like Rails magic.
00:05:39.200 On the other side of that magic emerges something wonderful, but you have to suspend disbelief in that middle process. If you’re one of those people who loves magic, that’s fine too—but it’s up to you to decide where the line between knowledge and magic should fall.
00:06:15.080 As much as I’d like to explain every minute detail, we only have so much time, and we can’t cover everything. So let's dive into our subject: what is a tail call? Now, if when you hear the term 'tail call' you think about certain types of phone calls that happen between midnight and 3:00 a.m., put down the Bud Light and focus.
00:06:35.960 The dictionary definition of a tail call is a subroutine call performed as the final action of a procedure. So, to illustrate this, let's look at a simple example. You have a method that takes a call in the tail position, followed by another method that very clearly marks the end of the outer method before it completes.
00:07:12.200 In contrast, you have another method that does not call in the tail position, which calls another method and then adds one to it. This does not adhere to our tail call definition because the last action of the method is not the call; it’s still adding one.
00:07:55.920 Even if you think of this as 'one plus other method', it’s still not a tail call because the last thing that happens in that method is adding one.
00:08:32.680 The interesting part about this is that certain circumstances can allow you to make a tail call. Some valid tail call sites include being at the end of an if statement or employing return on an expression. In cases like these, the call is the last operation—but if you add additional operations, it no longer qualifies.
00:09:12.639 So let’s take a moment to reflect on recursion. With the recursive count we previously discussed, you can see that the output will count down from five to zero. If we unwind this stack, the recursive function is called, checks if that’s zero, and continues down until the base case of zero is reached.
00:09:55.520 When you apply recursion with a tail call like this, you create something called tail recursion. This is particularly useful when combined with tail call optimization, as it allows you to perform some neat tricks. If you're familiar with Church's lambda calculus, you recognize that tail recursion enables fewer operators in modern languages.
00:10:36.640 As we will see, you can replace loops through tail call optimization. In the side-by-side example, you can see the recursive method implementing a loop, while the iterative version tracks its state within the method body.
00:11:14.999 However, tail recursion heavily depends on tail call optimization because without it, you will run out of stack space. In Ruby, this limit is usually around 10,000 frames by default depending on the arguments your method takes.
00:11:50.840 Now, for those of you getting excited about diving into our kind of flame war here, just chill out, let’s learn about tail call optimization. You might also have heard of tail call elimination. The trick is that they are essentially the same thing.
00:12:26.920 Tail call elimination refers to getting rid of the additional stack frames needed for a tail call, which is a type of optimization. However, before we dive deeper, I should confess something. While my recursive count function suggests tail call optimization, Ruby does not enable it by default.
00:13:06.640 What’s really happening is that each call allocates a new stack frame, consuming memory. This is fine for small counts, but what if you're counting down from 10,000? You will ultimately run into a stack level too deep error.
00:13:49.440 Now, onto tail call optimization! As we indicated, a tail call is the final action of a procedure, allowing for the assumption that nothing in the calling method is needed anymore. Consequently, we need to explore why we're holding on to this memory if we don't need it.
00:14:40.959 The first reason is debugging. Keeping the stack around allows you to trace your way through the VM. If you execute a method call from IRB or a debugging session, you will see the stack frame left behind.
00:15:26.880 The second reason is that it keeps track of where the result of each method should go. For these two reasons, you want to keep the execution trace for debugging purposes, but it isn't strictly necessary for the program itself.
00:15:54.760 So, what if we could just skip the entire stack frame? This is the magic of tail call elimination. It allows you to jump from the deepest call directly to the result without needing to preserve stack frames, saving memory and computational resources.
00:16:46.399 Now, if you've got questions, let's pause here for a moment while you think. All right, I appreciate your attention, and I hope I haven’t lost you just yet!
00:17:27.040 So regarding enabling tail call optimization, it's built into the RubyVM since version 1.9.2, yet it hasn't been enabled by default. There was talk of doing this around Ruby 2.0 but nothing ever came to fruition.
00:17:43.900 There are various ways to enable it, but exercise caution before implementing it in production. It's still an experimental feature, and while it holds potential, I would advise against deploying it without thorough testing.
00:18:09.920 For example, you could compile your Ruby with specific flags to enable it by default. You might also access the Ruby VM instruction sequence. However, manipulating the global instance could lead to problems.
00:18:54.800 I created a gem called TCO Method to allow you to experiment with tail call optimization and make it more user-friendly.
00:19:36.159 It's fascinating to think that a VM can have this feature enabled in one instance but not in another, demonstrating Ruby’s complex architecture. If you ever wished to patch Ruby for this feature, it’s a straightforward process of changing a couple of flags in the underlying code.
00:20:22.520 Let's explore how the RubyVM instruction sequence can be used to compile code with tail call optimization. In Aaron's talk, he highlighted the ease of accessing the Ruby VM's instruction sequence.
00:21:10.560 You can selectively compile code at runtime using this class. However, you must remember to turn off trace instructions, as that can negate tail call optimization. Even if you enable tail call optimization, you won’t see any effects without also disabling trace instructions.
00:21:53.760 Despite its complicated nature, exploring the VM reveals intriguing insights about how Ruby operates under the hood.
00:22:34.080 When working with recursive functions that implement tail call optimization, be cautious of the structure. Passing raw code strings can be clunky and less intuitive.
00:23:07.160 To address this issue, I attempted to provide a mixin that allows method decorators to automatically apply tail call optimization, making it easier for developers.
00:23:41.709 With Ruby being a multi-paradigm language, it pulls the best elements from various languages, merging them into a unique experience. Consequently, we still see the functional versus object-oriented design debate within Ruby.
00:24:18.000 In terms of functional programming, tail call optimization widens the range of recursive solutions, creating more flexibility in design patterns. Meanwhile, from an object-oriented perspective, it fosters better abstractions.
00:24:59.999 I also found that tail call optimization can enhance performance by allowing for memory management to be more efficient. Eliminating unnecessary stack frames means garbage collection can occur sooner, which is essential for memory-heavy applications.
00:25:44.639 The introduction of ECMAScript 6 means that JavaScript is also poised for tail call optimization, which may lead to intriguing developments in that language.
00:26:33.640 However, despite its benefits, one must consider the downsides of tail call optimization. Simplifying stack frames can make debugging challenging and may lead to issues with certain gems that rely on stack trace information.
00:27:19.759 Finding the right scenario to enable tail call optimization can drastically change the debugging experience as issues may arise unexpected at runtime.
00:28:04.480 Based on my research, tail call optimization is something the Ruby community should explore further to understand its benefits and potential risks better.
00:28:53.290 In conclusion, while tail call optimization isn’t inherently beneficial, it holds promise, especially when utilized wisely and in appropriate contexts.
00:29:41.639 As we wrap up, if you seek knowledge about Ruby's nuts and bolts, feel free to explore my GitHub for further information. If you enjoyed yesterday's presentation, my endeavors have led me to analyze tail call optimization in Ruby.
00:30:36.730 I appreciate you all coming today! If you have further questions, let’s engage!
Danny Guinther
@tdg5
Explore all talks recorded at RubyConf 2015
+80