attr_accessor_with_history

The Engineering SaaS textbook for the CS169.1x edX course I’ve been taking has a list of exercises and “suggested projects” for each chapter. I’ve been working through them, along with the Ruby Koans, and came upon the following question:

Project 3.6: Define a method attr_accessor_with_history that provides the same functionality as attr_accessor but also tracks every value the attribute ever had.

class Foo
  attr_accessor_with_history :bar
end
f = Foo.new # => #
f.bar = 3 # => 3
f.bar = :wowzo # => :wowzo
f.bar = 'boo!' # => 'boo!'
f.history(:bar) # => [3, :wowzo, 'boo!']

This is a great question to demonstrate Ruby’s metaprogramming. As I sat down, I got a creeping sensation that I’d done this before. Of course: the corresponding edX online course used this as a homework question, except…

Except the requirements were slightly different.

The online version of the question asked for f.bar_history whereas the book version asks for f.history(:bar).

This was enough of a difference to throw me.

Here’s the general framework for my solution:

First, we’re opening up the “Class” class, which will allow any class definition to declare an attr_acceessor_with_history.

class Class
  def attr_accessor_with_history(attr_name)
  ...
  end
end

This is truly mind-bending. What the hell is going on?

Well, in Ruby, there are no static class declarations like you’d see in Java or C#. A class declaration in Ruby is really just a call to a method named “class”, which creates an instance of the Class class with whatever behavior you choose to bestow to that class’s type. Your class is just an object, but it’s an object that helps define what the behavior of that class type’s instances will be.

Let’s look at an example:

class Foo
  attr_accessor :foo
end

Inside of your Foo object — which is a Class instance — you’ve invoked a call to the attr_accessor method with :foo as a parameter. This creates a getter and setter method named after :foo.

What we want to do is make it so that Foo can call the attr_accessor_with_history method.

Our first attempt might do something like this:

class Class
  def attr_accessor_with_history(attr_name)
  ...

but if you look at the Ruby docs for attr_accessor, attr_accessor is defined in the Module class, so let’s modify it there:

class Module
  def attr_accessor_with_history(attr_name)
  ...

We want the instance of our class to respond to the getter method so that we can do this:

f = Foo.new # => #
f.foo = 3 # => 3

We can do this by leveraging a method that already exists, which is attr_reader.

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
  ...

At this point, you can actually do this:

f = Foo.new # => #
f.foo # => nil

But doing this will fail:

f.foo = 3
NoMethodError: undefined method `foo=' for #

Of course, we haven’t created a setter. Let’s do that.

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
    attr_writer attr_name # or attr_accessor attr_name
  ...

No! Don’t do this! I mean, well, yeah, you will then be able to assign values to foo, but we need to do more than just that: we need to keep track of its history too.

To do that, we need to provide a custom definition for the assignment method. To do this, we will leverage another method called class_eval, which allows a class to add an instance method to itself:

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
    class_eval %Q{
    ...
    }
  ...

In this example, we’ve passed it a string (read up on %Q if you’re confused how that’s a string). That string needs to contain the method definition:

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
    class_eval %Q{
      def #{attr_name}=(value)
      ...
    }
  ...

Remember that “def #{attr_name}=(value)” once interpolated will become “def foo=(value)”.

We need to save the value into the instance variable (which is already created by attr_reader):

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
    class_eval %Q{
      def #{attr_name}=(value)
        @#{attr_name} = value
      end
    }
  ...

But now we need to add the history functionality. Let’s review the possible cases:

  • foo has not been set: foo_history should return nil
  • foo has been set to 1: foo_history should return [nil]
  • foo has been set to :bar: foo_history should return [1]
  • etc.

Let’s save the history of values in an array, which we stash into an instance variable named @#{attr_name}_history:

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
    class_eval %Q{
      def #{attr_name}=(value)
        @#{attr_name}_history = [] if @#{attr_name}_history.nil?
        @#{attr_name}_history << @#{attr_name}
        @#{attr_name} = value
      end
    }
  ...

We need to user to be able to call f.foo_history to get this instance variable:

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
    attr_reader "#{attr_name}_history"
    class_eval %Q{
      def #{attr_name}=(value)
        @#{attr_name}_history = [] if @#{attr_name}_history.nil?
        @#{attr_name}_history << @#{attr_name}
        @#{attr_name} = value
      end
    }
  ...

Note that wrapping up attr_name into an interpolated string makes sure that the name of the attr_reader gets properly converted.

When we run this code, it totally works!

foo.foo_history works, but we need to get foo.history(:foo) to work.

This is where things got really difficult for me. Okay, let’s take a swing at it!

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
    attr_reader "#{attr_name}_history"
    class_eval %Q{
      def #{attr_name}=(value)
        @#{attr_name}_history = [] if @#{attr_name}_history.nil?
        @#{attr_name}_history << @#{attr_name}
        @#{attr_name} = value
      end
      def history(name)
        @#{name}_history
      end
    }
  ...

This won’t work, sadly. Why not? Because when we call @#{name}_history, it won’t work since the scope of attr_accessor_with_history doesn’t have a variable “name”.

What we need is to somehow create an interpolated string with the history argument’s value.

The solution is to use the version of class_eval that accepts a block, and use a method called instance_variable_get to return the instance variable:

class Module
  def attr_accessor_with_history(attr_name)
    attr_reader attr_name
    attr_reader "#{attr_name}_history"
    class_eval %Q{
      def #{attr_name}=(value)
        @#{attr_name}_history = [] if @#{attr_name}_history.nil?
        @#{attr_name}_history << @#{attr_name}
        @#{attr_name} = value
      end
    }

    class_eval do
      def history(name)
        instance_variable_get("@#{name}_history")
      end
    end
  end
end

Note how instance_variable_get makes it possible to get a variable from its name string only.

Initial impression of CS169.1x

I’ve been taking an edX course CS169.1x Software as a Service, which is a UC Berkeley course on building SaaS apps with Ruby on Rails.

One of the lecturers, Armando Fox, might be the most talented lecturer I’ve seen.

The authors openly embrace the concept of the 5 Whys and do a really wonderful job of not just explaining what to do, but why we do it. This fits in line with what I’ve read about effective learning: you need the big picture to tie together disparate concepts into a cohesive framework. Setting up the big picture allows you to snap the little bits into place with ease. And finally, when it comes time to apply that knowledge, the framework itself serves as a mnemonic.

The accompanying textbook, Engineering SaaS, which is written by the instructors of the class, is also rather good at providing a framework of “why”:

  • Why do we build SaaS apps?
  • Why is Rails a good choice to build SaaS apps?
  • Why is Agile a good process for building SaaS apps?
  • Why does Rails embrace MVC?
  • Why do my instance variables disappear after each Rails controller action?

The course spends a decent chunk of its time explaining not only the Agile process, but the *opposite* of the Agile process, which is Plan-and-Document. It’s a smart choice to offer the alternate perspective because it ultimately strengthens understanding of Agile; again, it answers the question, “Why do we use Agile?”

On a personal note, as an old dinosaur who graduated from a CS program in 2004, it’s hilarious to see how much has changed. I remember taking a class dedicated to building software requirement specifications. We drew UML diagrams in Rational, came up with formal use cases, learned about Waterfall and Spiral, and oh yeah, there’s this new methodology called Agile that iterates super-fast but it’s sort of unclear if it’s really a formal methodology. I remember giggling to myself when we touched on Extreme Programming (XP): TOTALLY EXTREMEEE.

iOS 7 support for ColorMyWorld

iOS 7 support for ColorMyWorld was a little trickier than I thought it would be. I added support for Pantone colors, fixed a bug with some jumpiness during zoom, added a double-tap to zoom feature. That was all easy.

The trickiest part was fully adopting a pure Auto Layout implementation of the UI, as is recommended in iOS 7. It took the better part of two days to fully grasp the basics. In the future, I’ll have to learn a little bit more about how to manipulate constraints programmatically, as I only know the basics of the visual format language, but for now, I’m happy to be where I’m at.

Floyd’s Cycle Detection Algorithm

I just spent half a day trying to wrap my brain around how to detect cycles within linked lists, as well as how to find the first node of the cycle. After perusing all the Stack Overflow and Wikipedia entries, I had a pretty good mechanical understanding of the most elegant solution, which is known as Floyd’s Cycle-Finding Algorithm, or more informally, the tortoise and the hare algorithm.

The problem with my mechanical understanding was that it’s a classic case of surface-level learning, the kind of sloppy, rote-memorization cramming that somehow powered me through UCI to a 3.2 GPA but left me utterly uninterested and disengaged from my craft. I’d perform well if an interviewer asked me that question tomorrow, but I’d feel like a charlatan if I only parroted an answer back at him. Just because I flipped through some old tome and found an incantation that allowed me to cast a black magic wizard spell doesn’t make me Harry Potter.

I wanted an intuitive understanding of the solution. If I have that, I will carry it for the rest of my life.

In the name of that pursuit, I sat down and turned that problem over and over through my head until I found an elegant way to visualize and understand the reason behind the math. Since it’s an approach I wish I’d thought of six hours ago, I want to share it.

First off, let’s assume everyone knows what a linked list is. I’m talking about your standard, garden-variety singly linked list: it has a head pointer but no tail pointer, made up of nodes that contain a pointer to the next node in the list (except for the last node, which points to null).

Drawing1

A linked list with a cycle in it has one or more nodes that point to a previous node in the list. If you traverse the node starting from the head, you’ll get caught in the cycle loop.

Drawing2

Did you ever play Super Mario Bros. 1? On the Level 8 and 9 dungeons, if you didn’t go the right path, you would cycle backwards until you did. It’s sort of like that.

The Floyd Cycle Detection Algorithm works by using two pointers, one slow and one fast. We’ll call them the tortoise and the hare, respectively. They start at the first node.

Drawing3

The hare travels 2 nodes per move, and the tortoise travels 1 node per move.

Drawing4

Drawing5

Drawing5a

And so on. If the hare pointer meets the tortoise pointer, you’ve got yourself a cycle:

Drawing5c

To visualize why this works, let’s go back to our Mario analogy. Imagine you could play a co-op two-player mode of those cycle-containing dungeons. If Luigi always moved slower than Mario, and Mario keeps hitting the cycle part of the dungeon, Mario will at some point pass Luigi.

But why do we choose to go 2 nodes per move? Couldn’t you go 3 nodes per move? Well, yes, you could, but it’s not important how fast the hare goes. The hare could go light speed for all we care, but it can only pass the tortoise once the tortoise reaches the cycle.

There are some interesting properties about this algorithm:

  • The hare is always twice as many steps ahead of the tortoise (if an interviewer asks you how to find the middle of a linked list, have the hare run off the end of your list and the tortoise will be at exactly the middle)
  • The hare can never “skip” over the tortoise without them first sharing the same node. It seems like it might because it moves in chunks of two, but remember that for each step, the hare only gains one node on the tortoise.

Now that we can detect cycles, the next step is figuring out where the cycle starts and how to fix the cycle. This is where it gets tricky.

All of the Stack Overflow answers talk about the tortoise being Xi, the hare being X2i, and lambda (the length of the cycle) and mu (the number of steps to get to the cycle).

Let’s toss that all aside and agree upon this: the hare has always taken twice as many steps as the tortoise, right? Right.

So the tortoise and the hare meet at a particular node for the first time. The tortoise has entered the cycle but hasn’t done a full loop. The hare, depending on the size of the list and the cycle, may have done the loop only once, or it could have done the loop a million times. However, no matter how many times the poor hare has been spun through the cycle, we can guarantee that it has traveled twice as many steps as the tortoise has.

Drawing6

Again, that’s very important. It means that at that meeting point node, if the tortoise has taken i steps, and if the tortoise takes another i steps (i + i = 2i), it will end up at that same node. If it’s a big loop, it’ll only have to loop once, but if it’s a tight loop, it might go through it a lot of times, just like the hare had to do. But no matter what, we can guarantee that it’ll end up on the meeting node after i steps.

So here’s the heart and soul of Floyd’s Cycle Detection Algorithm: if we cloned the tortoise and placed one at the head of the list and one at the meeting point node, if we had them take i steps, we would guarantee that they would reach the meeting point node at the same time. Why? Because the cloned tortoise starts at position i and takes i steps, which makes a total distance of 2i.

But think about it: they wouldn’t just meet at the meeting point node, they would meet for all of the nodes at the beginning of the cycle until they reached the meeting point node. In fact, it means that the very first node that they meet is the very first node of the cycle.

Once we know the first node of the cycle, fixing the cycle is trivial: plop down a pointer to this first node, and use another pointer to traverse the rest of the cycle until you reach the node who points at the first node.

Circling back on iOS

Having completed the fairly comprehensive iOS online course offered by Stanford on iTunes U, and having completed ColorMyWorld as my “final project”, it’s time to circle back on some important topics that I haven’t covered yet or only skimmed the first time around:

  • Unit testing
  • Memory management that’s not ARC (i.e. pre-iOS 5)
  • Reading the Apple Human Interface Guidelines
  • Fully understanding the app submission process: certificates, provisioning profiles, etc.

There’s so much more I want to learn, though:

  • Core Graphics (Quartz)
  • Core Animation

But then even apart from iOS, there’s a desire to explore other topics: web, deeper CS theory and mathematics, etc. Too many paths, not enough time and energy to explore them all.

ColorMyWorld app submission

I managed to submit and upload ColorMyWorld to the App Store on Friday. It took longer than expected to put the finishing touches on it.

iAd Integration

The last-minute iAd integration was trickier than it should have been because the best practice for iAd integration changed in iOS 6, and most of the googleable resources on it are iOS 5 and below. Thankfully, the iAdSuite sample project that Apple created shows the most important parts:

  • Use a single central delegate object to manage the ADBannerView. The sample code uses a BannerViewController class that’s instantiated in application:DidFinishLaunchingWithOptions: and sets that as the root controller.
  • The BannerViewController class is a container VC. It wraps a content view controller — in ColorMyWorld’s case, a navigation controller on iPhone and a split view controller on iPad — by adding it as a child VC, along with the ADBannerView. This is done in its loadView method.
  • In BannerViewController’s viewDidLayoutSubviews method, it creates the appropriate frame for ADBannerView by calling
    [bannerView sizeThatFits:self.view.bounds.size];
  • Once the ad banner view is sized properly, we can adjust the content view’s frame so that both fit together comfortably

The problems I ran into were:

  • At first I tried using the ad banner view that you drag out from XCode. Getting it to resize on device orientation changes was a bit of a hot mess. In retrospect, I wonder if I could’ve just called sizeThatFits: on it, but I think to do so it needs the iOS 6 method of initialization (initWithAdType:ADAdTypeBanner), which I’m not certain that it does if you drag it out from XCode.
  • I was trying to not modify the app delegate to get this working. I tried to create the BannerViewController in the storyboard and set it as the root VC, but then I wasn’t certain how to get it to load my custom content VC. In retrospect, I could probably do this by modifying BannerViewController to expose its content VC as a public outlet, then create a subclass that would load my custom content VC on initialization (would probably have to be in an init method rather than viewDidLoad).

One suggestion from Apple that I did not implement is to remove the ad banner view from the view hierarchy when the ad banner won’t be on screen for a while. The idea is that you don’t keep it around when the ad isn’t viewable so that ads aren’t wasted. In ColorMyWorld, this occurs when the UIImagePickerController is presented modally on the iPhone.

The reason why I chose not to implement this is because I’m still considering whether users will spend enough time taking, selecting, and editing pictures to justify doing this. If I was to implement this, I would need to extend BannerViewController to be able to remove and re-add its banner view via some public method call. The child content controller would call this by accessing its parent controller.

iPad

And for some silly reason, I decided last-minute to implement iPad support. I had to dig up some of the slightly-decaying knowledge of split-view controllers. Setting the master and detail VCs, the weird detail about having to implement the delegate method that says, “DO NOT HIDE MY MASTER VC.” I had to test some unforeseen user workflows, since many of the screens that are presented full-screen modally on the iPhone are not on the iPad. Oh, and I had to think about implementing a popover for the first time.

Most challenging, however, was some weird behavior I noticed in one particular use case where a user taps the Photo Library button before tapping the Camera button. The camera would end up displaying just short of full-screen, with a gap where the status bar would be, and the camera controls at the bottom shifted and clipped by the same gap. Weirdly enough, closing and opening the camera again would get rid of this behavior.

I tried everything. At first I thought it was some weird interaction between the UIImagePickerController and the UIPopoverController — maybe displaying the photo library in the popover caused it to get confused when I then asked it to display the camera mode, and it didn’t update its frame properly? Maybe I had to dismiss the image picker when the user dismissed the popover. Maybe I had to set the modal presentation style to full screen before displaying the camera?

Nope. Nothing.

In the end, the only solution was to set the UIImagePickerController to nil when the user dismisses the popover, which then causes a fresh instance to be created when the user picks the camera again.

Very, very weird behavior.

App Store Assets

Another pain in the neck was creating all of the art assets required for App Store submission. Icons of every different size, and screenshots to use as launch images. I had to fire up GIMP for the first time in a while. It was a bit tedious creating screenshots for each device.

App Store Hoops

And finally, the actual submission process on iTunes Connect is extremely jargon-y, complex, and confusing for a noob like myself. You create an app record, which requires that you enter your app’s Bundle ID, and there’s a SKU you create, and that creates an App ID, and you have to provision a distribution profile, and once you associate the App ID with the distribution profile, then you create an archive, and then you test the archive, and oh my god what is going on.

I managed to limp through it. I’m not 100% certain I did it right, nor do I fully understand what’s going on, but I most certainly will circle back to it next time and try to figure out what’s going on. At least this time I’ll know a little more what I’m getting myself into.