• rum in rust


    Whenever possible, it’s nice to know the theoretical limits of what you’re doing. As I’ve spent the last couple years helping write a search engine from scratch, access methods on data have been top of mind for me, and so I intuited the RUM Conjecture, as probably many programmers have, before I found out it had a name.



  • a (very) scenic tour of hnsw


    HNSW, which stands for “Hierarchical Navigable Small World” (graphs), is one of the first data structures for which I read not just its paper but (a lot of) the trail of papers backward in time until I arrived at one with a name I already knew. [WIP Post - 01/17/23]



  • tech debt isnt real and cant hurt you


    On every team I’ve worked on, including at Amazon, engineers bring up “tech debt” as a concern. When I ask “what is tech debt” other engineers give me different responses, but all agree that product managers and line managers seemingly don’t understand or value “working on tech debt.” A term that’s this ubiquitous and means this much to engineers, yet seemingly so vague and ineffective as a term when prioritizing work, begs for some clarification. Here’s mine.



  • substrings and subsequences


    In day to day work I don’t get to make much use of dynamic programming. But for fun, let’s consider LCS: longest common (substring/subsequence).



  • haskell for rubyists: functors


    People have been paying me to write Ruby for about 5 years now. It wasn’t my original programming language. But Ruby is a great language for the web, and I’ve used it very broadly: I’ve put JRuby in production, CRuby in production, written C extensions and Java extensions, and shipped I guess now thousands of features at large scale and small in it. I love Ruby’s readability and simple central metaphor: everything is a message or a receiver. It’s still the language I reach to when I want to quickly open a REPL and have the computer do simple tasks for me. (JSON.parse(File.read('filepath')) is etched on my brain.)



  • composing http endpoints


    While I’ve been working on choclety, I’ve also been experimenting a bit. Choclety is just based on the observation that many times a return type of one endpoint (some representation of a resource) is an input to another. Relatedly I thought, wouldn’t it be fun to try composing endpoints, ie.



  • kth cheapest wine in linear time


    Imagine you need to purchase some wine for a party. You’d like to follow the sage advice of this skit:



  • when is an API better or worse?


    If an API is not simply a data persistence surface or a list of functions, what is it? For me, the underutilized model is the API as a state machine or graph1.

    1. By graph, I do not mean object graphs. Objects in GraphQL or other graph APIs aren’t even objects in the object oriented sense: they don’t have methods or hide implementation. They’re just instances of values in a schema. 



  • table driven methods


    I read parts of Code Complete a year or so ago and one of the sections I found kind of intriguing was Table-Driven Methods.



  • OAR is not REST


    I hate scare quotes. But I’ve used them a few times describing ‘REST’. I’m not really driving for the “world’s most boring pedant” lifestyle. So let me try coining some other acronym for this pattern: OAR. Object as resource.



  • apis and program state


    I’m still at APIStrat. I attended the hypermedia breakout, and was happy to hear multiple people talk about APIs as graphs. “Hypermedia vs Graphs” was probably my favorite talk of today, and was the final one of that session. I rambled myself in my previous blog about how strange it was to contrast GraphQL and REST as being at odds, and this talk helped crystalize just how unnecessary that is as an attitude.



  • over the horizon of API development


    At APIStrat today I attended the “workshop”1 on Open API Specification. A somewhat off-hand remark by the final presenter struck me as especially important. Someone had asked whether the new Links Object could be used to implement hypermedia, and the presenter first said no but in subsequent comments admitted it was not impossible, just not a priority. (This seemed quite fair to me.) But in his disclaimers he said something I found remarkable, which was that hypermedia is fundamentally at odds with an API specification. This was probably the most interesting statement of the entire day for me.

    1. This was not a workshop. It was some vendors speaking fairly tediously, and then a tour of OAS 3.0. There was so little enthusiasm at first the audience wasn’t even inclined to clap. I felt bad. 



  • types, tests, and paper


    Owing to either my curiosity or my masochism, I’m taking a couple MOOCs this fall. As an opportunity to learn some new tools, I’m trying to do all (or as much of the work as will make sense) in Haskell and Spacemacs1. In doing today’s homework, I felt like I had a good case study in my own thinking process to examine, especially with regard to what “tools” I typically use.

    1. I LOVE Spacemacs. If you’re a vim person, give it a chance



  • refactoring away from statements in Ruby


    Since I’ve encountered exactly the same problem several times, and just encountered it afresh today in a codebase at work, I want to dissect a bit how I solved it once. Take this advice with a grain of salt. I’m positive there’s other, perhaps superior, ways to resolve this. But I thought this was a useful set of observations regardless.



  • Proc#compose


    After my combinators post I was curious why chaining map performs so much better than the composition operator I wrote in Ruby. I thought to myself, maybe I just need to write it in C? So, I wrote another C extension: Proc#compose.



  • Graph::Function, a gem for graphing functions


    When I do katas I often do several iterations with a focus on performance. I think this is probably pretty common. You start off with some quadratic solution, ponder a bit, and then try to get down to linear or n log n performance1.

    1. I’m realizing as I think about it very few of the exercises are ever worse performing than that. It’s rare to get an actual permutations problem that requires exponential time. Why is that? Perhaps just because NP problems are trickier to solve, and often only approximated. I think subset sum is the only problem in that class I’ve done yet. 



  • Prim's algorithm


    A bit ago I covered Dijkstra’s Algorithm which I pointed out shares much in common with BFS because BFS is a special case of Dijkstra’s.



  • combinators in Ruby


    Strange Loop conference is outputting videos at a steady clip. This one especially, by Amar Shah, caught my interest:



  • Array#flatten -> Array#collapse (my first C extension)


    If you work in Ruby, and probably in other dynamically typed languages, you’ve likely had to make use of flatten. Say you have an array like this: [[3, [3, 3, 3]], [3, [3, 3, 3]], [3, [3, 3, 3]]] and what you want is an array like this: [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3].



  • more on recursion


    I don’t think you can teach people the intuition around recursion. I think the old joke is basically true, and you need to practice. For myself though, I wanted to capture how I think about it now in case it is instructive for others or more likely curious to myself in the future.



  • always use Capybara matchers first


    There’s a deep well of blog posts out there about using Capybara. I wanted to add one recent observation I had that I hadn’t seen.



  • Dijkstra's algorithm


    I was just as guilty as many programmers when you ask them what Dijkstra’s algorithm is: “oh it’s BFS with a priority queue…” This made me think one could just drop in a PQueue where one had been using a Queue and you’d be all set. Well, sorta.



  • goals (and graph algorithms)


    Back in March I interviewed with Facebook. They gave me a really nice rejection I learned a lot from. It was not an ideal interview for me. As it turned out, I’d just had to have surgery and was still in a bit of pain. I had not whiteboarded in an interview before, and knew I was going in without enough preparation. I regret that in the sense that I don’t want to waste an interviewer’s time.



  • Rails SSE is for discrete push events, not streaming


    Recently I had occasion to experiment with streaming content from a Rails controller. I decided to try out Server Side Events just to see where the support was for them in Rails 4 and if they’d work well for my use case.