The Sweet Spot
On software, engineering leadership, and anything shiny.

Explorations in logic programming

Out of Storybook, a side project I’ve been doing for a friend, I had the opportunity to model the problem domain as a constraint satisfaction problem (CSP). It goes:

A set of students are assigned a book a week. Write plan generator to create a set of student-book assignments for that week, given the following constraints:

  • All students must receive a book.
  • Each book may only be assigned to one student at a time.
  • A student may not be assigned a book s/he has received before.

Being that this was a Rails app, I put Amb, a Ruby-based CSP solver, to use. Amb is derived off Jim Weirich’s original source code, implementing a simple backtracking algorithm. (More interesting reading on the original idea behind the amb operator, proposed in a paper by LISP founder John McCarthy in 1963.)

Not having written any CSP logic since my university days, I tried to come up with a naive solution. It goes something like this:

assignment_problem_1.rblink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class AssignmentProblem
  def solve
    # Generates the cross product of sids and bids.
    spaces = student_ids.product(bag_ids)

    # Now generate combinations of those uniques
    full_solution_space = spaces.permutation(student_ids.count).to_a

    # Assign those to the CSP
    plan = solver.choose(*full_solution_space)

    solver.assert all_students_have_bags(plan)
    solver.assert assigned_bags_are_unique(plan)
    solver.assert assigned_bags_without_student_repeats(plan)

    plan
  end
end

Well this would work for 2 students and 2 bags, 3 and 3, 4 and 4, but would blow up and overflow the stack when we got to 5 students and 5 bags. Why? I was forcing Ruby to generate the full solution space before starting the CSP search problem:

1
2
3
4
5
student_ids = [:s1, :s2]
bag_ids = [:b1, :b2]
# Modeled as: the complete solution space of assignments
spaces = student_ids.product(bag_ids)
# => [[:s1, :b1], [:s1, :b2], [:s2, :b1], [:s2, :b2]]

Then I was taking that cross product and brute-force generating all possible permutations internal to that:

1
2
3
4
5
6
7
spaces.permutation(student_ids.count).to_a
# => [[[:s1, :b1], [:s1, :b2]], [[:s1, :b1], [:s2, :b1]],
#     [[:s1, :b1], [:s2, :b2]], [[:s1, :b2], [:s1, :b1]],
#     [[:s1, :b2], [:s2, :b1]], [[:s1, :b2], [:s2, :b2]],
#     [[:s2, :b1], [:s1, :b1]], [[:s2, :b1], [:s1, :b2]],
#     [[:s2, :b1], [:s2, :b2]], [[:s2, :b2], [:s1, :b1]],
#     [[:s2, :b2], [:s1, :b2]], [[:s2, :b2], [:s2, :b1]]]

The most obvious thing that stood out to me like a sore thumb was how I wasn’t simply trusting the constraint-based nature of the problem and expressing the problem in terms of the constraints, instead of attempting to imperatively generate the solution. Usage of Enumerable#permutation resulted in an O(n!) algorithm, which is unacceptable. Back to the drawing board:

assignment_problem_2.rblink
1
2
3
4
5
6
7
8
9
10
11
12
class AssignmentProblem
  # Generates tuples of student => bag assignments
  def solve
    student_ids.each do |sid|
      bid = solver.choose(*bag_ids)
      partial_plan[sid] =  bid
      solver.assert assigned_bags_are_unique(partial_plan)
      solver.assert assigned_bags_without_student_repeats(partial_plan)
    end

    partial_plan.to_a
  end

Note the main difference here is how I’ve re-tooled the solver to assign variables one at a time (in L5) and check constraints after each assignment. This simplifies the domain of the problem as a graph search and helps us more easily reason about this program.

Further explorations

Follow my csp-solvers project, where I attempt to rewrite this in Prolog and Clojure in an attempt to see how language affects how we reason about problems like these. It’s gonna be fun.

Further reading

My own robot training buddy.

As an ultra runner, I am really into the mountains. As a software engineer, I’m really into data. So naturally, I’m interested in the intersection of both.

I’ve particularly been interested in how systems like Strava work, especially when they quantify what is known as a “Suffer Score”, a single number denoting the amount of training stress (a.k.a. suffering) you put yourself through in a workout.

How does a track workout compare to a long day on the trails? Which is tougher: a 5m tempo road run in and around my neighborhood, or a tough 2m climb into a local regional park?

Data in…

I first attacked the problem of getting data off of my phone. I record my GPX tracks in Runmeter, a fantastic iPhone application with all sorts of metrics and data export capabilities. What I wanted was a seamless way to get the data off my phone without fuss after a hard workout.

The application has a nifty feature in which it can automatically send an email to an email address after a workout is completed.

I wrote an email ingester, Velocitas, with the help of Cloudmailin, which fires off a POST request to the Node application. Velocitas does the following:

  • curls and downloads the GPX link embedded in the email.
  • Saves the GPX file to a linked Dropbox account.
  • Republishes the GPX file to a linked Strava account.

Deriving the Training Stress Score

Next up: I wanted to do a quick and dirty implementation of the (run-based) Training Stress Score. Stressfactor, a Ruby gem, is what came out of it.

It implements the rTSS as detailed in this article.

1
2
(duration_seconds * normalized_graded_pace * intensity_factor) /
(functional_threshold_pace * 3600) * 100

Stressfactor is a higher-order tookit for deriving meaning from GPX tracks, so it, at the moment, attempts to calculate the stress score and grade adjusted pace.

The data still needs validation, so I’m eager to run it on my data set of GPX tracks from the past years.

Generating reports

I’m working on this part right now – I need to nicely display a report from my workout history in Dropbox and display per-GPX. I’ve started the project – Stressreport.

Some things I’ve learned and am learning

  • The human body is complex, and cannot be easily modeled without sufficient data. That said, what I’m doing now may be sufficient for basic training data.
  • The nature of parsing and generating higher-order stats from raw data may lend itself well to experimentation with functional languages. I’m interested in trying to reimplement Stressfactor in Scala, or a functional equivalent.
  • Deploying all my apps on Heroku’s free tier may actually be an interesting start to building a microservice architecture – with the space limitations on Heroku, I’m forced to build new features on new services. Call it cheapskate architecture.

Recap: QCon SF 2014

Blurb sent me off to QCon SF 2014 for three days.

Notes

I took a series of notes each day in attendance:

Summary

  • Big trends in continuous delivery and deployment – deploy more often, smaller feedback loops
  • A lot of emphasis on event driven architectures + microservices. Lots of emphasis on DDD as a design tool.
  • Reactive systems with functional implementations were widely discussed as a scaling tool (backpressure-sensitive) and as a coordination tool between multiple async services.
  • Big data/realtime streaming talks were interesting – my personal experience with them is limited, but it seems there is a debate over the merits of existing Lambda architecture practice.
  • A lot of talk about microservice orchestration tools – acknowledging the pain of configuration and management of many services.
  • Scala got a lotttt of attention. Probably because of its presence in bigger companies like Netflix, Twitter, LinkedIn. Wonder what smaller startups are using.
  • Web Components were a big upcoming trend in frontend technologies. Strong modularization of views + behaviors in HTML documents.

Questions

  • If I could do a startup over again, would I begin an app in Rails? Where is the sweet spot for that sort of application architecture?
  • How can I design systems such that they can be extractible into focused components/services as early as possible?
  • How can we plan for failures (fault injection)?
  • How does one implement change in software engineering organizations? Bottom-up (organic initiatives bubbling up through management) vs top-down (management/software leaders direct org to implement).
  • How are we doing with encouraging women and minorities who traditionally are underrepresented in our industry?
  • What are places in our hiring funnels that, unbeknownst to us, may be turning away or detracting women and minorities?

Conway's Law for humans

If you’re familiar with Conway’s Law, it states:

Any organization that designs a system (defined broadly) will produce a design whose structure is a copy of the organization’s communication structure.

Or in layman’s terms, your software systems reflect the structure of the teams that create them.

Think about it – do your teams prefer to do everything themselves? Or do they ask for help from other teams? In general, as a team, we prefer to have as little dependencies as possible. The work that the engineer has to do to send an email, or wait for work from another team (like an API change or design change) is usually time-consuming and burdensome. Therefore, it is not (usually) in the team’s best interests to cross silos and ask for help from others. Your teams, if they look like this, tend to work in codebases that are generally monolithic and wholly owned by the team.

It’s not wrong, or it’s not bad, it’s just a sociological observation. This is why companies like Spotify, Netflix or Amazon have embraced Conway’s Law and changed their organizations to match the microservice-driven architecture they want. Small teams work on small codebases and are empowered to make the changes they need.

A corollary and some observations about your company culture.

Here’s a corollary, which I’ve heard in various shapes and forms. Paraphrased:

An organization’s structure tends to pattern after its leaders’ communication patterns.

I’ve been pushing an effort to unify our company’s frontend styles and UX into a unified framework in an attempt to standardize the look and feel of the site.

However, in working with our designers, I realized that they weren’t talking to each other. Designers in one department had opposing design aesthetics from designers in another. This was causing problems in the code, because the frontend framework itself was becoming fragmented. You could see it in the code. Version A of the styleguide went into Department A’s products. Version B of the styleguide went to Department B’s products.

In this case, as we kept rolling out this framework, I realized our organization had no single owner for the design language of the site. Why? I had to wonder if it had to do with some deeper communication issues between the heads of the two departments.

Code can be a good canary to organizational issues, and call out larger human issues at hand. In this case, Conway’s Law helps us root out and bring into the light structural concerns. Leaders can pay attention to these concerns and check themselves to become more open communicators.

Mocks aren't stubs: mockist & classic testing

With the famed “TDD is dead” debate around the Rails community largely
coming to an end, I found myself referencing Martin Fowler’s article,
Mocks Aren’t Stubs a good deal, trying to make sense of it in terms of how I write tests and code.

In this post I’m going to talk about mocking and stubbing and their
roots, paraphrase Fowler in an attempt to explain their differences, and
walk through a couple of code examples. In each case, I’m going to
attempt to build this example out in Ruby and RSpec 3.

Let’s assume this implementation in our code for a BookUpdater object in Ruby. Its job is to call through its collaborating ApiClient, which wraps some aspect of an API that we want to call.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Update a book's metadata in our systems.
class BookUpdater
  attr_accessor :book, :api_client, :response

  def initialize(book, api_client)
    @book = book
    @api_client = api_client
  end

  def updated?
    !!response.success?
  end

  def update!
    response = api_client.call_update_api(book)
  end
end

What they are

Mocks

Mocks are fake objects that verify that they have received messages. In
RSpec, we traditionally use the mock object utility to create these objects.

1
2
3
4
5
6
7
api_client = mock('api client')
book = Book.new

expect(api_client).to receive(:call_update_api).with(book).and_return(true)

subject = BookUpdater.new(api_client, book)
subject.list!

What’s happening here? RSpec creates a mock api_client object that will verify that, after the test case executes, it has received the :call_update_api message with the correct arguments.

The main point of this style of testing is behavior verification – that is, that your object is behaving correctly in relation with its collaborators.

Double

Let’s take a look at a double – also known as a stub. A double is a fake object that is set up to respond to a certain message with a pre-canned response, each time. Let’s take a look at how I would set up a test using doubles:

1
2
3
4
5
6
api_client = double('api client')
response = double('response', :success? => true)
book = Book.new

allow(api_client).to receive(:call_update_api).with(book).and_return(response)
expect(subject.update!).to change(subject, :updated?).from(false).to(true)

Okay, so what’s the big deal here? My test case still passes. Note that
I had to change my code to focus its expectation on the subject’s
state instead of the api_client.

The focus of using doubles is for state verification – that is, that so long as everybody around me is behaving according to their contracts, the test merely has to verify that internal object state changes correctly.

A third way – real objects

I won’t cover this very much in depth, but with sufficiently simple objects, one could actually instantiate real objects instead of doubles, and test an object against all its collaborators. This is, in my experience, the most common experience of working in Rails + ActiveRecord applications.

Classic vs Mockist testing: different strokes for different folks

As we saw above, the key difference between the mock and the stub (the double). The focus of the test in the mock case is on the messages being sent to the collaborators. The focus of the test when using the double is on the the subject under test (SUT).

Mocks and stubs/doubles are tools that we can use under the larger umbrellas of two TDD philosophical styles: classic vs mockist styles.

Classic TDD

  • Classic TDDists like using doubles or real objects to test collaborators.
  • From personal experience, testing classicly is oftentimes the path of least resistance. There isn’t expectation setup and verification that mockist testing requires of you.
  • Classic TDD sometimes results in creating objects that reveal state – note how the BookUpdater needed to expose an updated? method.
  • Setting up the state of the world prior to your test may be complex, requiring setting up all the objects in your universe. This can be a huge pain (has anybody ever had this problem with overcomplicated Rails models with spidery associations? Raise your hands…). Classicists may argue that the root cause here is not paying attention to your model architecture, and having too many associations is an antipattern. Alternatively, classicists oftentimes generate test factories (e.g. Rails’ FactoryGirl gem) to manage test setup.
  • Tests tend to be treatable more like black boxes, testable under isolation (due to verifications on object state) and are more resistant to refactoring.

Mockist TDD

  • Mockist TDD utilizes mocks to verify behavior between objects and collaborators.
  • It can be argued to develop “purer” objects, that are mainly concerned with objects passing messages to each other. Fowler refers to these objects as preferring role-interfaces.
  • These tests are easier to set up, as they don’t require setting up the state of the world prior to test invocation.
  • Tests tend to be more coupled to implementation, and may be more difficult to refactor due to very specific requirements for message passing between collaborators.
  • Fowler brings up a point where being a mockist means that your objects prefer to Tell Don’t Ask. A nice side effect of TDA is you generally can avoid Demeter violations.

In conclusion

In coming from a classic TDD background, I’ve oftentimes viewed mockist testing with some suspicion, particularly around how much work is involved to bring them about. Over the years, I’ve warmed up to the usage of mockist testing, but have not been diligent enough at doing pure driving TDD with mocks. In reviewing Fowler’s comments, I’m intruiged at the possibilities of mockist TDD in affecting system design, particularly in their natural inclinations toward role interfaces. I look forward to trying pure mockist TDD in a future project.

Further reading: