Saturday, February 7, 2015
Does jQuery expose a monadic interface?

Pam Selle raised an interesting question on her blog recently: does jQuery expose a monadic interface? I'll interpret this as specifically asking: are jQuery containers monads? This was such an interesting question that I decided to investigate it more thoroughly; one can never have too much practice figuring out how monads work, in my experience!

There are a couple of formulations of monads; both have in common that there is a container type M that "wraps" plain data values in some fashion. Here, M is the type of jQuery containers, and the plain data values are DOM elements. Some monads are polymorphic, in that they can wrap values of a wide variety of underlying data types (lists and Option/Maybe are good examples of these). jQuery containers are also polymorphic, although we usually just apply them to DOM elements. For the rest of this post, we'll refer to C as the type of a jQuery container, and when it contains items of type T then we'll write C[T].

Monadic operators


Now, in order to qualify as a monad, a type has to support certain operations with particular signatures, and then those operations have to obey certain "monadic laws" in order to be correctly composeable.

Both formulations share a requirement for a simple wrapping function called return or unit that take plain data values (DOM elements) and return values of the monadic type (jQuery containers, or C). In other words, we're looking for an operation / "constructor" of type:

unit : T → C[T]

If e is a DOM element, then $(e) returns a jQuery container with that one element in it; ditto for $(a) if a is an array of DOM elements. We can then understand all the other selectors as syntactic sugar for one or the other of these. For example, $("#foo") is equivalent to $(document.getElementById("foo")). In fact, we can see that even just $(elt) for a single element is equivalent to $([elt]) (i.e. wrapping the element in a single element array). This will be convenient for the rest of this post, since it means we just have to deal with this simplest constructor. At any rate, it seems like we have the unit operation covered.

Now, in one of the formal definitions of monad, the other operation required is one called bind that can take a value of the monadic type, a function from the underlying data type to another value of the monadic type, and returns a value of the monadic type again. That's a mouthful, so it might be helpful to look at the type of this operator:

bind : C[T] → (T  C[U]) → C[U]

Conceptually, this takes every contained item of type T, applies a transformation to it that maps to a new set of containers, and then "squashes" it down into one container again. As is common with object-oriented language implementations, the this variable can be thought of as an implicitly-passed parameter, so we can then look through the API for a jQuery container looking for a method that takes one of these transformation callbacks and returns a new jQuery container. One such candidate is the .map() method, which is defined as:
Pass each element in the current matched set through a function, producing a new jQuery object containing the return values.
Wow, this looks pretty good; it takes a transformation function and returns us a jQuery container at the end. The real question is whether it will "flatten" things down into a single jQuery container for us (since the documentation doesn't say) if our function returns jQuery containers. Suppose we have the following markup embedded in a page:
<div id="example">
  <div class="outer"><div id="one" class="inner"></div></div>
  <div class="outer"><div id="two" class="inner"></div></div>
</div>
Now, suppose we try this in the Javascript console:
> $(".outer").map(function (idx,elt) { return $(elt).children(); });
We can see that this does, in fact, squash down to just a container with the two div.inner elements in it, as opposed to a container containing two containers. Nice!

Monad Laws


We have our candidate operations for unit and bind, so we have to check whether they adhere to certain properties; these properties are similar in spirit to the commutative or associative properties of addition (or, perhaps better, the distributive law of multiplication over addition, since that expresses a relationship between two operations). For the below notation, the bind operator is written as >>=. The first law says:

(unit x) >>= f   ≅   f x

Or, to put things into jQuery syntax: $(x).map(f) should be the same as f(x). If f() can take a DOM element and return a jQuery container, then we can see from our test above that we're in good shape here. The second law says:

m >>= return   ≅   m

which is to say that if m is a jQuery container, then it should be the case that m.map(function (idx,item) { return $(item); }) gives us m back again, which also seems right. Finally, the third law says:

(m >>= f) >>= g   ≅   m >>= ( \x→ (f x >>= g))

Or, that if m is a jQuery container, and f and g are transformer functions, that the following are equivalent:

m.map(f).map(g)
m.map(function (idx,x) { return f(x).map(g); })

Ok, that's a mouthful--or at least a keyboardful. What we are doing in the first line is taking each element in m and applying f to it, squashing this into one container, then taking each element of that collection and then applying g to it, then flattening everything down into one colleection. In the second line, we are taking each element in m, and then applying the given function to it, but we can see that the body of the function does the same thing: namely, applying f to the element (which returns a container, remember), and then mapping g across all those elements. Because .map() does squashing for us, we end up with the equivalent containers at the end.

And that's it! It does look like jQuery containers are a monad after all. We can actually understand several methods of jQuery containers as convenient applications of .map(). For example, .children() is really equivalent to:

.map(function (idx,elt) {
       return $(elt.childNodes);
     });

[I suspect that the actual implementation of .children() ends up being more efficient, as it doesn't have to construct all the intervening jQuery containers and then squash their arrays back together again.]

Exercise for the reader: Can you find an expression of jQuery containers as a monad in their other formulation, with return, fmap, and join? (I ran out of time to try this before I had to make dinner for my kids!)

The Upshot


"So what?" you might ask. Well, it suggests that if you are writing a library meant to be used with jQuery, you might be well served to write many of your utility functions in the form of the monadic transform functions we saw above, taking DOM elements and returning jQuery containers--i.e. making sure your utility functions can be passed as arguments to .map(), because it means that they will be composeable in very flexible ways that let them be chained together easily.

Saturday, January 17, 2015
Installing Ubuntu on an old Macbook

[Update: This post is turning into a lab notebook more than anything, and I'm mainly just recording it here as someplace convenient, with the idea that someone *might* find it useful someday.]

I have a 2008-vintage Macbook for which OS X no longer seems to be a good option: I managed to get it upgraded to OS X 10.7 (which was not straightforward), but I think the hardware is a little underpowered at this point. In fact, upgrades to later versions of OS X are not even supported.

Since I don't otherwise have a personal laptop and occasionally need something for writing/email/lightweight development, I figured I'd give Linux a shot, having had previous experience of getting extended service lifetime out of old hardware. Plus it had been a while since I'd monkeyed around with installing Linux; I was curious how hard or easy this was (bearing in mind that I was highly confident it would be easier than installing Slackware off a stack of 3.5" floppies). I gave Ubuntu a shot.

Long story short: I managed to get it working (mostly), but it required a lot of trial-and-error (and multiple reinstall-from-scratch passes). Since this was hardware I was going to retire and I was working on it in my spare time [with 4 kids, this stretched out over weeks!], I didn't mind, but it wasn't entirely straightforward. The documentation was relatively good, although somewhat contradictory, likely because it was from several sources that did asynchronous evolution.

Some things I encountered:

  • Manually configuring my partitions with gparted didn't work the first go-round, I think due to insufficient guidance and my inability to remember (know?) limitations on needing to boot from primary partitions, and how many maximum primary partitions you're allowed, etc. When I freed up the space and left it unallocated, and let the Ubuntu install do whatever it wanted, it worked.
  • The latest supported Ubuntu release for my hardware according to the community docs was 13.04 (Raring Ringtail); at the time of this experiment, the latest supported was 14.10 (Utopic Unicorn), so I was already four releases behind the release train. Although I was able to install 13.04, even an upgrade to 13.10, the next release, no longer worked with my hardware (kernel panics on boot). Raring is already EOL, too: the latest updates to the mirrors were over a year ago at the time of this writing, even for security updates. Caught between retiring perfectly serviceable hardware and not having security updates is not a fun place to be. The reality  is that I could buy a replacement laptop if I really needed one, but I suspect there are lots of folks with hand-me-down hardware and/or insufficient means to buy newer that would just be stuck. At least I can nmap myself, shut down all my ports, and hunker down. If push comes to shove I used to know how to build kernel images from source, but again, that's definitely not for everyone. Tough problem: I know forward progress sometimes requires retiring support for old hardware, but there's a long tail out there.
  • Because my Ubuntu release was EOL, I had to manually configure my apt sources.list file, through a little bit of trial and error.
  • Got Chrome installed and hooked into updates, but could not get the Dropbox client to survive long enough to sign in. My guess is I'm so ancient the single .deb release they have isn't really being tested vis-a-vis the installed library ecosystem I have.
  • Once I had my sources.list updated, I was able to install missing software and even apply updates. I initially tried just applying the security-related updates, but this introduced some instability/random crashes of stuff, until I went ahead and applied *all* the available updates. So far so good after that <crosses fingers>.
  • Ended up buying a replacement battery off EBay, around $20, which I thought was a reasonable investment for a few more years' (hopefully) service lifetime. I'll probably buy an el cheapo USB mouse with multiple buttons, because the trackpad has gotten desensitized at this point and clicking is kinda hard--and pounding on the trackpad button, while satisfying when in a bad mood, gets old fast. I still haven't done the research to see what the maximum memory the motherboard supports is to see if a memory upgrade is possible; currently I have a paltry 2GB in it, which it seems to be ok with for the moment. But I think it's probably a good bang-for-the-buck investment to keep in mind.
Ultimately, a fun project, and the thrifty part of me likes getting some extended use out of the laptop. It appears to be able to run Minecraft reasonably well (and better than the OS X installation on the same hardware!), which will make it a big hit with the kids, and it's handy being able to have something serviceable for lightweight use when I'm on a trip where using a work laptop wouldn't be appropriate.

Notes for myself for later/lab notebook

(I won't rule out the possibility of needing to reinstall from scratch at some point, but I'll probably have forgotten all this stuff by then!)
18 January 2015: still having kernel panics on resume/wake up. This bug seems to blame the wireless driver, which means I am going to need a new kernel somehow. Since Raring Ringtail is EOL, this either means building my own kernel, possibly with a patched source (ugh) or something else. I'm somewhat tempted to attempt an install of the most recent LTS Ubuntu release just to see if it will work with this hardware or not; since I don't have anything important on the laptop anymore, blowing away the Linux install is still a viable option. Also suggests I should really be thinking of using this mostly as a netbook whose hard disk is mostly just temporary storage until I can push stuff out to the network sometime.

Went with 14.04.1 LTS (Trusty Tahr): so far this seems to be stable across sleep/restart. Default trackpad settings are off, though; they required pushing too hard on the trackpad. Found the settings to fix this:

$ xinput set-prop appletouch "Synaptics Finger" 10 50 0

Still need to work out how to make that trackpad setting persist across restarts. Apparently adding the above command as /etc/X11/Xsession.d/85custom_fix-trackpad may do that. Yup!

Success! Seems like everything works ok now: suspend/resume, trackpad, wireless, even Chrome and Dropbox. So, perhaps I misinterpreted the Ubuntu-on-Macbook support matrix? Possible, but the columns are labelled "most recent release" and "most recent LTS release", which led me to think those were the maximum versions that would work. Not so, apparently. But anyway, seem to have a working, semi-stable laptop now (although I discovered that Firefox could trigger a kernel crash on certain pages; not really a big deal since I plan to use Chrome mostly).


Friday, September 21, 2012
Hackday project: tarpio.us

I saw this tweet from @kellan that got me to thinking:

It would be useful if Tent.io could describe itself in the world of protocols I know, particularly PuSH, XMPP, and SMTP.

I think the notion of a distributed social network is an interesting one, and I've been pondering how it might work. I think I've got a scheme for one, which I'll outline in this post, and I think it might not take that long to throw it together with off-the-shelf open source and a dedicated hack day.

General Principles

Use existing, open standards. This increases the likelihood of finding good open source code to use when building software, ensures that a distributed marketplace of (interoperable!) clients and servers could arise, and increases the likelihood of avoiding platform specificity. Plus, giants have pretty high shoulders. I have limited hack time; I'm not into wheel reinvention.

Central service provider not required. This is pretty fundamental; means there's no central organization that owns/has access to everything ("creepy alert!"), but also that there's no central organization that can be subjected to lawsuits (e.g. Napster[1]).

Users have control over sharing. At least for the initial communication, users need to be able to say exactly who gets to see a piece of content. Of course, once you've shared something with someone else, there's no stopping that other person from sharing it further, but that's what social trust is all about.

Protocol Sketch

TL;DR. S/MIME, public key crypto, Atom.

To expand: everyone runs their own AtomPub server somewhere, or contracts with a service provider to do it on their behalf. Multiple PaaS and IaaS providers have a free tier of service, which is almost certainly more than enough for most users. I get whole tens of visits to my blog every day. And I am not a prolific sharer: looks like I've averaged 1.1 tweets per day since starting to use Twitter. "Roflscale" is probably enough, to be honest. Easy recoverability probably more important than high availability for a single-user server/hosted PaaS app, so I think this could be done for less than $10 a year (most of which is probably just buying a domain name). Given the relatively low traffic, actual friends could pretty easily share infrastructure.

Now, I'm the only one who posts to that Atom feed, and anyone can poll it at any time. The trick is that the content is encrypted, and you specify who gets access to the decryption key. Basically, you generate a random (symmetric) encryption key for the content, then public-key encrypt copies of the content key for all your recipients. Put it all together in one multipart package, upload to, say, S3, and then post a link to it on your Atom feed. Of interest is that neither S3 (the storage) nor the AtomPub server care one whit about the encryption/decryption stuff.

Interestingly, following gets somewhat inverted. You can post content intended for someone who never subscribes to your feed (gee, I hope he notices me!). You can also subscribe to someone's feed who never encrypts stuff for you. But you can see anyone's public broadcasts, of course. Actual "friending" is just GPG key exchange and an addition of the key to appropriate keyrings to represent friend groups/circles.

On the client side, then, it's mostly about subscribing to people's Atom feeds, polling them periodically (for which HTTP caching will really help a lot), cracking open the content encryption keys with your own private key, then interleaving and displaying the content.

That's about it. Definitely possible to layer PubSubHubbub on top to get more realtime exchange; no reason your free tier server couldn't host one of those for you too. Or perhaps just a feed aggregation proxy that would interleave all your subscriptions for you (without needing to understand who any of the recipients were, or even if you were one of the recipients!).

Hack Day Proposal

Roughly, get a simple AtomPub server stood up somewhere. Apache Abdera has a tutorial for doing exactly that, if you can implement the storage interface (MySql/Postgresql/SimpleDB/S3 I think would all work; looks to be just a Map). Front with Apache and some form of authentication module. Alternatively, grab Abdera and retrofit into Java Google AppEngine and use Google federated OpenID for login.

Client side, cobble together a UN*X command-line client out of bash/Python/Ruby/whatever, depending on what open source is out there. It'd be kind of neat to perhaps do commands interleaved on the command line, in MH style. Everybody's got an HTTP client library that can be made to convince the server you're you. AtomPub clients are available in Python (1,2), Java (3,4), Ruby (5,6). GnuPG for the public key implementation. Bouncycastle has a Java S/MIME implementation. Lots of S3 clients out there (7,8).

I think it's entirely possible to have a simple client and server up in a day with a smallish group of folks (5-6). If there are more folks we can also try multiple clients and servers.

Tentative Projectname

Since @kellan started this off by mentioning tent.io, and this is an attempt to slap something together with off-the-shelf stuff, it felt more like a lean-to made out of a tarp than a true tent, so I've snarfed the domain name tarpio.us (which is the closest I could come to something that meant "like a tarp" that lined up with a cheap TLD). Cool part, of course, is that there's no reason tent.io and tarpio.us couldn't interoperate with protocol bridges someday.

If you're interested, hit me up on Twitter at @jon_moore or follow along on GitHub. I'll see when I can free up for a hackday soon!

Footnotes

  1. I'm not advocating violating copyrights here, merely noting that Napster was a P2P system with a single point of failure (an organization that could be sued).