Isaac Cambron

@icambron

Feed

Transducer Composition

Dec 13, 2014

My startup has been building our product in Clojure. It’s been awesome, and overall, it’s been pretty easy to learn and be productive with, since our team was already in a functional programming mindset. But we’re still learning some of the edges. Specifically, today I was trying out a newish feature called transducers, which allow you to compose transformations on data without having to care much about its “container” type, so long as that container provides a way to reduce itself.

Just playing around with it, I got confused for a bit that my transducers kept composing in the opposite order I expected. Specifically, this (which I’ll explain in a second):

(defn doubler [x] (* 2 x))

(into [] (comp (map doubler) (map inc)) [1 2 3]) ;=> (3 5 7)

;;vs the ol' fashioned, non-tranducery:

((comp #(map doubler %) #(map inc %)) [1 2 3]) ;=> (4 6 8)

It turns out I’d missed that the docs mention that explicitly:

The composed xf transducer will be invoked left-to-right…

It took me a bit to figure out what was happening at all, and when it dawned on me (“oh, it goes the other way!”), I wondered why the hell does it do that? I asked about it on the ClojureScript IRC channel, where David Nolen told me to go look at the source. That’s a totally fine answer (it’s not his job to sit around and write out detailed answers to my questions), but it’s of course more useful if there’s an explanation written up, hence this post.

I actually didn’t look at the source; instead, I took a nap and when I woke up I was pretty confident I knew the answer.

A quick review of composition

The order of composition obviously matters; f(g(x)) is not the same of g(f(x)).

(defn doubler [x] (* 2 x))

((comp doubler inc) 2) ;=> 6, the result of (doubler (inc 2))

((comp inc doubler) 2) ;=> 5, the result (inc (doubler 2))

If you want to apply that composition to each element of a sequence, you’d do something like:

(map (comp doubler inc) [1 2 3]) ;=> (4 6 8)

But perhaps you have a bunch of functions that operate on sequences, and you want to compose those. You end up with the uglier, less efficient, and no less correct composition of maps:

((comp #(map doubler %) #(map inc %)) [1 2 3]) ;=> (4 6 8)

Transducers, briefly

Transducers manage to compose the same sort of transformations, but do it in a way that doesn’t create intermediate sequences (even lazy ones) and for which the transformations themselves are agnostic about what kind of container they’re transforming elements from (or into). It does this by defining various transformations (e.g. map, take, filter, etc) in terms of reduce and then parameterizing them with the reduce function itself. So map in the transducer world doesn’t mean “take each element from a sequence and call this function on them and put the results in another sequence”. It means “given some way (let’s call it foo) of reducing something, give me a way of reducing things that increments each thing and then reduces it with foo”.

You create a transducer by calling one of the standard listy functions without a collection arg, like (map inc). That transducer can be handed to pieces of machinery that know what transducers mean, like the transduce function:

(transduce (map inc) conj [1 2 3]) ;=> [2 3 4]
(transduce (map inc) + [1 2 3]) ;=> 9

What’s really neat is that different containery things can implement reduce differently without having to define its own specific transformations (or even make you do it differently for your different use cases). For example, you could use some transducers you built to transform a vector, while your async.core channels can use the same transducers to transform values pushed through them. That works because those async channels can provide their own definition of reduce, and the transducers only depend on that having the right shape.

OK, so that’s a terse introduction, but for more, go watch the StrangeLoop talk.

Reversals

So why does composing transducers mean they get evaluated “backwards” or “inside out”? Well, on reflection, it makes a lot of sense. What transducers really do is transform reducing functions, not actual values; they take one reducing function and return another one that works by transforming its values and passing the results to that passed-in reducing function. When you compose them, you’re using the function returned by the “inner” transducer as the reduction function for the “outer” transducer. So if I have (comp (map double) (map inc)), I’m saying that (map inc) provides a reducing function that takes a value, increments it, and feeds into the reducing function it gets passed. I’m then passing that reducing function into the doubling tansducer, which returns another reducing function that doubles the values and then feeds the answer into the map-incrementing reducer the doubler took as an argument. So double then inc.

Instead of bubbling values out like in a simple compose, you’re building a set of concentric spheres, each capable of taking a value from the outside and pushing it in.

I’ll make that more concrete in a moment, but first, note that this inside-outness is a common feature of composed higher order functions that use their arguments as their “outermost” invocation. Compare our original composed maps to these, which also don’t use transducers at all:

(defn pre-inc [f] #(f (inc %)))
(defn pre-doubler [f] #(f (doubler %)))

(((comp pre-doubler pre-inc) identity) 2) ;=> 5

(map ((comp pre-doubler pre-inc) identity) [1 2 3]) ;=> (3 5 7), all backwardslike

If that makes sense to you, the next part will be easy. One interesting way to better understand all this is to implement a simplified version of transducers. We’ll skip a bunch of complications, like stateful transducers, and we won’t bother to make the actual reduction polymorphic or add some of the conveniences. But here goes:

(defn my-transduce [xform f init coll]
  (let [reducer reduce ;todo: this should depend on the type of coll
        doit (xform f)]
    (reducer doit init coll)))

(defn my-into [to xform from]
  (my-transduce xform conj to from))

(defn my-map [f]
  (fn [rf] ;rf is like conj or +
    (fn [result input] ;can be passed to a reducing function
      (rf result (f input))))) ;this is the inversion that answers the question

(my-into [] (comp (my-map doubler) (my-map inc)) [1 2 3]) ;=> [3,5,7]

That’s the whole thing. my-map returns a transducer, i.e. a function that takes a reducing function and returns a different one. Since it does its transformation and then delegates the actual core reduction work to its argument, the order of composition from the standpoint of the individual values is…well, I still say it’s backwards. But it makes good sense.

Source

Kickstarter is for suckers

Mar 26, 2014

There was a recent article in the Wall Street Journal about how all of the people who gave Occulus money feel a bit screwed by the acquisition. I think the article has some flaws, but it reminded me of a point I’ve been making recently. I posted a short writeup of that point on Hacker News, and I like how it turned out enough to post it here (with some minor edits):

I’ll just say it: Kickstarter is for suckers. When you give money to a project, you’re doing one of two things:

  1. Making a donation to a company.

  2. Preordering something that hasn’t been built yet.

Doing 1 is silly, since you don’t really get anything in return. “But it makes it more likely that this thing I want will happen!” In some tiny marginal way, sure, but mostly it’s going to happen because other people donate (or fails to happen because they don’t). Don’t be the fool who tries to personally take on the collective action problem. And stop trying to make other people rich out of the goodness of your heart.

Of course, as the WSJ fails to make clear, most of Oculus’s Kickstarter money wasn’t straight-up donations; it was preorders of the Rift. That’s obviously not a donation, but it’s not a good idea either. As the buyer, you bear the risk that it never ships at all. “But I’m compensated with a discount!” Essentially, you’re making an investment in which your returns come in the form of future discounts on a product. Forget that you like the Oculus Rift for a second; is this a wise investment structure? If someone set up a VC company that did that instead of buying parts of companies, would you think that was smart? Did you do any kind of analysis that suggests this is actually works out to be a good investment? Do the potential returns even justify that analysis? Do you think of other consumer products this way, or only shiny electronic things?

Will you even get a discount? Why would you?

Or to think about it a different way: imagine if someone set up a store that worked like this: you take your item to the counter, where they don’t actually let you buy the item. Instead what you can do is pay the price minus n% and then they roll this big roulette wheel to decide whether you get the product (m% success rate). If you win you get to keep the product and if you lose it goes back on the shelf and they keep your money. To spice things up, they don’t tell you what n and m are either, just the price to play and whether you get the item. Now, it’s possible—though unknown—that m and n work out that you’re EV positive here. But would you really shop at that store? Especially when there’s another store next door that just sells you the same stuff at a known price (i.e. just buy the Rift when it comes out).

The fact of the matter is that you’re aren’t pre-buying the Rift on a rational basis. You’ve been convinced by clever marketing to shoulder risk for a company because it seems cool and feels good. Total sucker move. That probably explains why it tastes bitter when the company whose capital requirements you fronted rolls that into a $2 billion dollar acquisition.

The original is here if you want to see the responses.

Source

Introducing FbFriends

Dec 25, 2012

FbFriends is a new jQuery plugin for picking Facebook friends from a dialog using the Facebook JS SDK. It’s written in CoffeeScript and Less; you can find the docs and demos here and the code here.

For the lazy, here’s a screenshot (and apologies to my friends who showed up here):

FbFriends

Go check it out; I think it’s pretty cool.

Not a ton to say, but here are a few interesting notes about it:

  1. I went with the idea that the caller has to provide the dialog component. It just seemed dumb to bake in my own and likely you’ll want to make it look consistent with the dialogs/modals/whatever in the rest of your app. So you provide callbacks to open and close whatever dialog you want. FbFriends just provides the content.

  2. I really didn’t want to build this. In fact, the Facebook SDK used to have this ability, and they dropped support for it. I wish they hadn’t.

  3. A lot of Quarrels Harris Port was consumed during the making of this library.

Oh, and Merry Christmas!

Source

Introducing Timestack

Aug 27, 2012

This probably won’t render correctly in your RSS reader. If not, click through.

TL;DR

This is Timestack:

It’s a jQuery plugin I wrote that turns unordered lists into nifty timelines. Docs here. Code here. Check it out.

Why did I build it?

Timestack is a small library and didn’t take long to write, but I had a few thoughts about the process that I wanted to share.

When you build software for a living, you make a lot of compromises. You start with a vision of what you want to build, you get to work, and you run into obstacles. Maybe the technology you wanted to use doesn’t exist. Maybe it does exist but doesn’t work the way you wanted it to. Sometimes the right thing to do is to fix that technology or just build your own before moving on to the actual work. But usually that’s not the right move. Usually, you compromise your vision, make do with the pieces you have, make some quirky work-arounds, and move on. If you don’t, you’ll end up rewriting your entire stack from scratch to make every little part just right and you’ll never actually get anything done. You’ll have a bunch of (maybe) cool infrastructure for something that hasn’t been built yet. Knowing when and how to make this kind of tradeoff is part of being a good engineer.

One of the nice things about a personal side project is that it allows you to absolutely, totally ignore that whole last paragraph. You can compromise as much or as little as you want. And if you’re like me, personal projects are an awesome opportunity to solve problems totally tangential to your goal, getting distracted by problems you encounter solving those tangential problems, and so on into fractal oblivion. That’s just fun. That’s what a personal project is. If I had to actually deliver it, even to myself, it would be a job. Jobs are fine, but they’re not the best context for depth-first exploration.

Anyway, here I was trying to make a nice interactive resume for a simple “Hi, I’m Isaac. I build things.” website. I wanted a timeline that showed when I worked where, because I think that’s more interesting than a boring bulleted list. I looked around and there are a few components out there that do this:

After trying out Timeline (it is pretty), I decided it was too big and heavyweight— it’s a timeline, not an application framework. It doesn’t need themes or its own script loader. Importantly, it also didn’t really do what I wanted, partially because it imposes some constraints I don’t like, and partially because it just isn’t meant for my use case. Simile is similar, but unmaintained and worse looking. I wanted something really simple:

  1. It should turn some list items into timeline bars. No-JS fallback FTW.
  2. It should create an interval key (the times at the bottom).
  3. It should be able to do stuff when the user clicks on the timeline items. Note that I don’t want it to show me stuff; I just want a callback. Component does less = more flexibility for the user.
  4. It should be small, simple, and hackable. Libraries for handling simple things should be simple, and tweaking them should be trivial.
  5. It’s not important that it work in old browsers.

So I put aside the website and jumped down the rabbit hole.

Notes on building it

Since I’m terrible at UI design, I looked around and quickly found Matt Bango’s Pure CSS Timeline. It looks pretty good and the CSS is simple. It’s hand-cranked, though; the widths of the bars are just hardcoded for the particular times he needed. So all I had to do was write some code to generate those widths. I also added colors, because why not?

Some things I think I know now:

  1. The look and feel of web UI widgets should be customized by the user through CSS. CSS already gives you inheritance, overrides, and all that jazz. Just keep it simple and tell your users to override the CSS you ship. Easy.
  2. Give widgets a width of 100%. The user can decide how big to make the container box.
  3. Go for cheap extensibility over configuration. Instead of adding a whole bunch of flags into the options list, I just put the functions I wanted to make customizable into the options defaults and let the users override them.
  4. When dealing with tricky spacing problems in HTML, use box-sizing: border-box. It’s takes away that problem where you need to set the div width to realWidth - border - padding, which would have been really painful here. In fact, I’m increasingly convinced that border-box should just be the default browser behavior.
  5. If you need to work with dates and times in JS, you should use Moment. It’s just more pleasant than dealing with native dates and times.

If you want to know more about Timestack itself, definitely go here.

Source

What I want from Sublime

Jul 21, 2012

I’ve been using Sublime Text 2 for 7 months now, and it well past time for me to take a step back and evaluate things. In general, it’s a great editor, but there are now one too many things about that bug me. I wanted to write them up. Maybe someone will tell me how to fix them. Maybe they’ll actually get fixed by the author. Maybe I’ll just feel better having gotten it off my chest.

If any of this sounds nitpicky, I should point out that I spent like 10 hours per day in this program, so what might seem like minor nuisances add up very quickly. Programming is really just a particular kind of text editing, and we ought to have really well-oiled text editor programs. That’s partially for efficiency, and that’s partly for our happiness. If you were to respond to that by pointing out that if I feel that way, I should really invest more time customizing my editor, I wouldn’t disagree. I should probably dig in, learn my way around the API super well, and make it do what I want it to do. But since it’s easier to complain about it on the internet, I’m going to do that. Then I’ll look into fixing it.

It may also be that there are configuration options I don’t about that could fix this stuff. If so, I’d love to hear them.

Here’s my laundry list.

I want set_mark, yank, and so on to work a bit differently

One thing I think is profoundly annoying are the disjunctions between cut and delete-to-mark and between paste and yank.

For the uninitiated, in Emacs-speak, you set a mark (usually with ctrl+space), which is a sort of bookmark in the document. Then you move your caret around to wherever you want and then you “kill the region” (which really just means “cut”) between your caret and the mark you set before. Later you can “yank” (basically paste) that text back in. So the big difference here is that the region you keep is modal instead of being an explicit selection (the other big difference is that Emacs keeps a full history of your kills so you can do fancier stuff, but that’s not important here).

Sublime has support for this: you can set a mark, you can kill the region, you can yank the region, and you convert the region into a selection. So far so good, but here’s the issue: kill/yank and the more standard copy/paste use completely separate buckets to hold stuff. That might sound useful, but in practice it means I have to keep track of (and map) four commands instead of two. Want to paste in something from another program? Use paste. Want to paste in something I killed? Yank. Want to cut something I have selected with the mouse? Use cut then paste, not kill then yank. And we haven’t event talked about copy. So that’s annoying.

I could get around this by by setting a mark, going where I want to go, using the select_region command, and then cutting. Then I could always use paste. That would work, but it’s an extra command (and keybinding) just to kill some text. It’s also a deeper problem than just kill/cut: more complicated manifestation is that I can’t use to create a region and then hit Tab to add a tab to each line, because that command works on the selection, not this weird other region thing. The issue is that regions and selections are different things.

Slight aside: I’ve been using EmacsKillRing plugin that partially fixes at least the cut/paste part of this and adds some other Emacsy goodness, but it doesn’t really solve the issue that the region isn’t a first-class selection, and it has plenty of other issues too.

Anyway, what I want—I think, anyway—is just a select lock command. Instead of set_mark, I just want to say:

Look, I want my selection to start here. Wherever I go with caret, have the selection follow me, like how it does if I hit shift+up. Then treat my actions like you normally would. Cut cuts, Copy copies, etc.

That would add a total of one command and (for my purposes), get rid of all the kill/yank/region stuff. I’m a total noob when it comes to customizing ST2, but it seems kinda hard to implement as a plugin: would each command that moves the caret need to be aware of it? Do the actions that get rid of the selection have to be aware of it? It seems like I’d have to create my own versions of a lot of editing features to make it work. Or is there something simple I could be doing here?

The spellcheck face needs to be customizable

This is really only a problem for me when I’m writing blog posts, but since that’s what I’m doing right now, I’m going to complain about it. Spell-as-you-type uses a red squiggly underline, which is very painful to look at with a dark background:

My eyes!

I was unable to find a way to change that, and I did find some posts to the effect of “yeah, you can’t change that”. Bummer.

Opening an already-open file should move it to the right group

Sublime has groups, which allow you to split the screen. Files can be moved from group to group so that you can manage your workspace. And you can switch between them easily with the keyboard:

Splities

Another nice feature of ST is the “find a file dialog”, which allows you to open any file in your project via an autocompleting search. The cool thing is that if you already have the file open, it just pulls open that tab. The trouble is that these two features don’t play well together. If I want to edit an already-open file to the front of my selected group but the file is in some other group, Sublime will open another view on that file.

While it can occasionally be useful to see different parts of a file side by side, that’s the exception. One consequence is that you end up with a lot of clutter. If you have three groups and you’re working with five files, after enough switching you’ll have fifteen tabs open instead of just five. Another is that Sublime is a little quirky with more than one instance of a file open. For example, closing a tab triggers the “Don’t you want to save this?” dialog even if there are other instances open. There are other quirks like that. And that EmacsKillRing plugin we talked about earlier is totally broken in this scenario.

What Sublime should really do is move the file to the current group if it’s open already.

Deleting a file should close the file

This is the issue that probably causes me the most anguish on a day-to-day basis. You can delete files by right-clicking them off the side bar and clicking delete. Except that it’s not. If you have the file open, it’ll stay open. “Fine”, you say, and close it. But ST will think “Hmm, that file is different on disk, in that it doesn’t exist there. I’d better confirm Isaac really doesn’t want to save this!” and gives me a dialog about whether I want to save the file I JUST DELETED. Like, my intention is literally the opposite of what you’re asking about. In fact, it’ll do this even if I don’t have the file open, because when I right-click on the side bar item, ST opens it in a sort of preview mode, which is normally superuseful, but annoying here because when I close the preview I have to deal with this goddamn dialog.

If I delete a file, ST should close it.

Fewer dialogs

Sublime mostly gets out of your way, in that most of the dialogy things are expand out of the top or bottom of your screen and steal focus, as opposed to being a big rude modal dialog. That’s a great thing. But Sublime does have big rude dialogs, like “There’s a new version of Sublime. Would you like to upgrade?” or “This file has been edited. Would you like to save it?”, etc (neither of those are verbatim.) Not only are they jarring, but they’re also not very keyboard friendly, and reaching for my mouse to answer a question that could be Y/N makes me sad. Some sort of notification toaster would be better.

Some keyboard holes

I really hate using my mouse. Looking up, that’s actually what most of this is about. In general, Sublime does a good job here, but there are some holes. One in particular is search results. You can search your hole project, and results are displayed in a buffer. It’s really nice and Emacsy and well done:

Next, find things

But it doesn’t have good keyboard support. You have to actually click on those yellow boxes with your mouse; there’s no shortcut for that. You can actually iterate through all the results by hitting F4 as many times as you like, which is also nice, but not the same as being able to simply go to the right occurrence in the results and jump to it is frustrating.

I also haven’t figured out how to pull up the right-click menu with the keyboard, which would be really nice for selecting spelling alternatives.

Conclusion

Some of this I can probably fix with some Python hacking and some patience. Some of it will actually have to be changes in the product. In the meantime, it puts me in this annoying state of almost having a really great editor, but not quite.

Source

Next page