I spent the summer at Mozilla working on source maps. Source maps allow one to map the line and column information between an original source and a generated source for debugging purposes. Watch the webcast to learn more!
When I wrote Pycco, it was meant to be a single-serving coding session. It was fun and simple. But then the project started receiving more attention than I ever expected it to. In fact, one year later, I am still getting a pull request every month or so. But the problem is that I no longer have the time to spend nor interest in maintaining the project. I feel bad because a few people are out there dedicating their own precious time while writing code to make Pycco better, and I'm not holding up my end of the bargain by reviewing that code and merging it back to the project.
If anyone would like to adopt this project and give it a loving home, please leave a comment here and we can work it out. I'd hate to see the project rot away while there are definitely still a few people interested in it.
This is the second post in a series I am doing on the real-time collaboration algorithm Operational Transformation (OT). The first post was an introduction to OT and this series. There are two repositiories on GitHub to follow along with:
operational-transformation - This is an Operational Transformation library for plain text which assumes nothing about how the storage backend for your documents works, what kind of frontend you will be using, etc. This is where most of the ideas discussed in this series will be implemented.
operational-transformation-example - This repository contains an example application which takes advantage of the OT library.
However, before we can start transforming operations and providing a real-time experience for our users, we have to decide how to represent and generate operations. That is the topic for this post.
We will be representing operations as a stream of simple edits. As Daniel Spiewak notes in Understanding and Applying Operational Transformation, this is perfect for the type of automated processing we will be doing inside the xform function. Our operations will be made up of the following three types of edits:
retain(n) - Copy n characters from the old version to the new one.
insert(subsequence) - Insert subsequence in to the new document, without changing where we are indexed in the old document.
delete(subsequence) - Advance the position we are indexed in the old document by the length of subsequence, without copying subsequence in to the new document. The reason we pass a subsequence instead of a number is soley so that we can assert we are deleting the proper subsequence and throw an error if we are not.
To create the document "Hello, World!" from the document "hello world", you would apply the following operation:
[ delete('h'),
insert('H'),
retain(4),
insert(','),
retain(1),
delete('w'),
insert('W'),
retain(4),
insert('!') ]
Note that the edits start at the beginning of the old document and finish at the end of it. If an operation doesn't affect the whole document, the last edit in the operation should be retain(length of remaining document).
First off: you don't want to add listeners to keyboard and mouse events! Imagine all of the edge cases and browser incompatibilities: would you successfully handle Ctrl-a or Shift-up-arrow followed by backspace? Yikes, I don't even want to think about all of the common key combinations (not to mention the differences between key combinations across OSs).
No, instead you want to take two versions of the document and programmatically generate a list of operations which transform one version to the other. Fortunately, comparing sequences and determining their similarity or difference is pretty much a solved problem in computer science.
Levenshtein distance (sometimes also referred to as edit distance) is defined as the number of edits required to transform one sequence in to another sequence. Classicly, these edits are either an insertion, deletion, or substitution of a single item in the sequence. Comparing sequences of characters (or, as we know them, plain text documents) is a classic use case for Levenshtein distance. Variations of Levenshtein distance are also often used in bioinformatics to compare sequences of DNA.
The Levenshtein distance between "WUTANG" and "MUTATION" is five, because it would take three substitutions and two insertions to transform "WUTANG" in to "MUTATION":
"WUTANG" -> "MUTANG" (substitution)
"MUTANG" -> "MUTATG" (substitution)
"MUTATG" -> "MUTATI" (substitution)
"MUTATI" -> "MUTATIO" (insertion)
"MUTATIO" -> "MUTATION" (insertion)
The algorithm for calculating Levenshtein distance runs in O(m * n). Here it is presented in psuedo code:
LevenshteinDistance( s[1..m], t[1..n] ):
d = matrix[0..m, 0..n]
# The distance between the empty string and another
# string is equal to the length of the other string.
for i = 0 to m:
d[i, 0] = i
for j = 0 to n:
d[0, j] = j
for j = 1 to n:
for i = 1 to m:
if s[i] is equal to t[j]:
d[i, j] = d[i-1, j-1] # No edit
else:
d[i. j] = minimum( d[i-1, j] + 1, # Deletion
d[i, j-1] + 1, # Insertion
d[i-1, j-1] + 1 # Substitution
)
return d[m, n]
However, the number of edits is immaterial in our application; we care about what the edits are. Modifying the algorithm to return a list of edits instead of the number of edits is trivial: just store lists of edits in the d matrix rather than numbers.
Here is my JavaScript implementation of calculating an operation on GitHub.
Currently, every insert, delete, and retain only handles one character at a
time. We could save some bandwidth if [retain(1), retain(1), retain(1)] was
simplified to [retain(3)] and [insert('c'), insert('a'), insert('t')] to
[insert('cat')], etc. I chose not to do this simply because it has been
easier this way, and I haven't ran in to any problems so far.
In practice, usually only a small part of the document has changed since the last comparison. Humans don't randomly change documents in random places; we add new sentences and delete old paragraphs. Knowing this, we can cut down on the size of our problem domain by reducing the area of the strings we are looking for edits in.
PrefixPostfixOptimizedOperations(s[1..m], t[1..n]):
prefix = []
i = 1
while s[i] == t[i] and i <= m and i <= n:
push(prefix, retain(1))
i = i + 1
postfix = []
j = 0
while s[m-j] == t[n-j] and j < m and j < n:
push(postfix, retain(1))
j = j + 1
return concatenate(prefix,
Operations(s[i..m-j], t[i..n-j]),
postfix)
I haven't implemented this optimization yet, but I probably will have to eventually. In my preliminary testing, O(m * n) is just too slow for large values of m and n, and causes the browser's UI to be unresponsive while the computation is performing.
My representation of the individual edits in the stream of edits which make
up an operation could be optimized. Currently, each edit is represented in an
array of two elements where the first is the type of edit and the second is
the associated data. For example, insert('toto') is represented as
['insert', 'toto'] and retain(4) is ['retain', 4]. This isn't the most
memory efficient, bandwidth efficient, or "JavaScripty" solution; it's just
the first I thought up and implemented. Eventually, I will probably update it
so that each edit is a string and the first character is the operation type,
while the rest of the string is the associated data. So, insert('toto')
would become 'itoto' and retain(4) would become 'r4'.
Update: I have now implemented the string representation.
Applying operations to a document is straight forward. See the apply.js
file in the operational-transformation GitHub repo.
In the next part of this series, I will describe the xform function, and how it transforms a pair of operations so that two documents can be kept in sync.
Levenshtein Distance on Wikipedia.
Understanding and Applying Operational Transformation by Daniel Spiewak.
Introduction To Algorithms section 15.4 on the Longest Common Subsequence algorithm by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. (Levenshtein distance and Longest Common Subsequence are very similar to the point of being two faces of the same problem).
Update: If you don't have the book (or just want more), MIT has provided the video recorded lecture and notes by Charles E. Leiserson.
I have been researching the optimistic concurrency algorithm for real time collaboration known as Operational Transformation (OT). OT is the algorithm used by many real time collaborative editors that you see today, such as Google Wave, Google Docs, Etherpad, Mockingbird, and Novell's Vibe Cloud (formerly known as Pulse). This is the first in a series of posts I will be writing on OT.
As I am writing this series, I am I also implementing the ideas being discussed in JavaScript. I have made two public repositories on github:
operational-transformation - This is an Operational Transformation library for plain text which assumes nothing about how the storage backend for your documents works, what kind of frontend you will be using, etc. This is where most of the ideas discussed in this series will be implemented.
operational-transformation-example - This repository contains an example application which takes advantage of the OT library.
Operational Transformation is a good fit for web applications because it is optimistic. Consider the scenario where multiple clients are concurrently editing the same document hosted on a central server. The goal is to provide a real time editing experience so that the clients can collaborate as they change the document, and each client's changes are preserved.
OT optimisticly assumes that whatever operations are currently being applied to the document on any given client will not conflict with any operations that might be applied at this same moment by one of the other clients. Conflicts can't be discovered, let alone dealt with, until some point in the future. This frees operations to be applied to the document as they are generated by the client and the user interface is updated in a responsive manner. There is no need to request a lock on the document from the server.
Locking, and other pessimistic concurrency algorithms, are unrealistic within the constrains of the web application environment because of the high latency associated with communicating round trip with the server and other clients. The majority of clients would be powerless to change the document for many seconds at a time while another client has acquired the lock. This is a recipe for bad user experience.
Furthermore, it is natural to stop thinking of changes at the document level, and instead focus on individual operations being applied. Operations are much more malleable than whole documents. If two clients change their documents such that they become out of sync, how do you bring them back to the same state while preserving both changes in a meaningful way? In comparison, it is easy to adjust the index of a single insertion operation on client A because of a deletion from client B, and then share this adjusted operation with client B so that both clients' documents are in the same state.
Finally, Operational Transformation allows us to only consider two operations at any given time. Rather than fret about how client A's changes will affect client B's document after client B just applied client C's recent changes, we only compare one client's document and the central master document at any given time. Not only is this much more simple, with many less edge cases, but it also directly maps on to the client/server architecture of the web.
At the heart of the aptly-named Operational Transformation is the transformation of operations such that they can be applied to documents whose states have diverged, bringing them both back to the same state. In other words,
xform(a, b) = {a', b'}
such that if applying the operation a followed by the operation b' to document Y yields document Z, applying the operation b followed by the operation a' to document Y must also yield document Z.
The one caveat to this rule is summarized in the paper High Latency, Low-Bandwidth Windowing in the Jupiter Collaboration System:
Of course, there are many possible functions that have this property. For example, the function xform(c, s) = {delete everything, delete everything} would satisfy our ordering property, but would probably not satisfy many users! In general, the transforms should try to find some "reasonable" way to combine the two operations into a final effect.
However, xform only handles the case where each side has diverged by one operation. In practice, it is hardly ever the case that we only consider divergences of one. To rectify the situation, xform will be called repeatedly, as you traverse across document state space until both the client and server's documents reach the same state. I will expand on these transformations in a later post in this series. In the meantime, see Understanding and Applying Operational Transformation for more.
Read the following papers and articles to learn more about Operational Transformation and to prepare for the rest of this series.
Authored by David A. Nichols, Pavel Curtis, Michael Dixon, and John Lamping.
This is the paper that I have seen referenced most often by other papers and articles discussing Operational Transformation. It is very well written and approachable, and was the first paper published describing OT as we know it today.
Authored by Daniel Spiewak.
This is a great article written by one of the developers working on Novell Vibe Cloud (previously named Pulse). Vibe Cloud implements the Wave Protocol, and the article reflects this by focusing on Wave's implementation of OT and Google's contribution to OT theory with the idea of composing operations. Nevertheless, this piece is incredibly informative and provides a very detailed walkthrough of the one of the more difficult transformations you will have to do.
Wikipedia's article on OT is very good, but not as approachable as either of the two resources above. I suggest reading them first and then only reading the Wikipedia entry once you feel you feel comfortable with the others.
This was a very simple implementation of OT that I wrote in Erlang. It is written in somewhat of a Literate Programming style, so it should be fairly easy to follow along with. I will be going in to much more depth in this series, and with the JavaScript implementation, than I previously did in this project.
The goals of the Erlang project was to prove to myself that I understood OT, could implement a simple version of it, and pass all of my tests. The goals of this series of blog posts, and accompanying JavaScript OT implementation, is a production-worthy real time collaboration app.
The next installment in this series will focus on how to generate the operations that Operational Transformation works with.
Update: Part 2 is posted.
There are two functions that browsers expose to the JavaScript environment for
asynchronously executing functions after a a specified amount of time in
milliseconds: window.setTimeout and window.setInterval. Timeouts occur once,
intervals repeat. However, JavaScript is single-threaded (with the exception of
Web Workers) and so if a timer is set, but then the process blocks, the callback
can be delayed or even fail to ever be fired. For example, the "hello" message
will never be logged below.
window.setTimeout(function () {
console.log("hello");
}, 1000);
while (true) ;
The thread within which the JavaScript interpreter runs is also shared by the browser's UI and rendering systems. This means that not only will the above message never be logged, but that the browser will be unresponsive and appear to be frozen to the user.
For more in depth discussions about the details of how JavaScript timers work, see the references.
It also follows from the single threaded nature of JavaScript that only one timeout can fire its callback at any given moment in time. If another piece of JavaScript is already executing when a timer is scheduled to run, the timer's callback is queued to run when the interpreter is done with the code it is currently executing.
It is possible to set so many timers expiring at about the same time that they just keep queuing up one after another; never giving the browser's UI a moment to update. I am going to refer to this as "timer congestion". I first read about this phenomena in Nicholas C. Zakas' book High Performance JavaScript (HPJS from now on). It was mentioned only in passing, however I found the idea fascinating. HPJS refers to research conducted by Neil Thomas while he was working on the mobile version of GMail.
Neil shared his research and the process that led him to do that research in his article Using Timers Effectively.
When I first started working on the new version of Gmail for mobile, the application used only a couple of timers. As we continued adding more and more features, the number of timers grew. We were curious about the performance implications: would 10 concurrent timers make the app feel slow? How about 100? How would the performance of many low-frequency timers compare to a single high-frequency timer?
He summarized his results as follows.
With low-frequency timers - timers with a delay of one second or more - we could create many timers without significantly degrading performance on either [an Android G1 or iPhone 3G]. Even with 100 timers scheduled, our app was not noticeably less responsive. With high-frequency timers, however, the story was exactly the opposite. A few timers firing every 100-200 ms was sufficient to make our UI feel sluggish.
Thomas goes on to explain why they decided to hardcode their callback functions inline, rather than create a registration-based system:
Keep in mind that this code is going to execute many times every second. Looping over an array of registered callbacks might be slightly "cleaner" code, but it's critical that this function execute as quickly as possible. Hardcoding the function calls also makes it really easy to keep track of all the work that is being done within the timer.
However, by sacrificing the accuracy of when timers fire, it is possible to attain the clean architecture Thomas refers to and also guarantee that many timers will not cause the page to feel sluggish.
First, restrict yourself to a single recursive timeout loop which you can
register tasks with. Use window.setTimeout instead of window.setInterval to
ensure that the browser has enough time to update between every single
iteration. This is necessary because window.setInterval(callback, ms) tries to
fire its callback every n milliseconds rather than providing n milliseconds
between each time it fires. Thus, if your callback takes longer than n
milliseconds to execute, it will be repeatedly executed back to back, never
allowing the browser a few milliseconds to update the UI.
Second, while looping through the tasks registered with the timeout loop, keep
track of how long the loop has been running. Before the loop has been running
long enough to negatively affect the user's experience, yield to the browser
with window.setTimeout and then pick up the loop where you left off after the
browser has had a chance to update the UI.
By doing these two things, when you have a large number of tasks firing their callbacks concurrently they will not make the browser feel sluggish like many timers expiring at the same time would. Instead, the tasks will only be pushed back and executed at a later time than they had been scheduled for to ensure that the browser can respond to user interaction. In extreme cases of congestion, it would be possible for a task pushed back for so long that it will effectively never be called. Even in this worst case scenario, it is better than the alternative: an unresponsive browser.
Chronos is an implementation of the techniques described above which also mirrors the HTML 5 WindowTimers interface.
interface WindowTimers {
long setTimeout(in any handler, in optional any timeout, in any... args);
void clearTimeout(in long handle);
long setInterval(in any handler, in optional any timeout, in any... args);
void clearInterval(in long handle);
};
This means that to switch existing code from using window.setTimout and
friends, all you need to do is include Chronos on the page and replace
window.setTimeout with chronos.setTimeout, etc to take advantage of what
Chronos has to offer.
I have put together a test page for Chronos where you can define how many concurrent timers to execute on the page, how long each one should block for, and whether to use Chronos, or the native timer functions. I have tested the page on my MacBook Pro (Firefox 3.6 and 4 beta, Safari 5, and Chrome 9), as well as on my Motorolla Droid 2 running Android 2.2. In all cases, the browser's UI updated more smoothly when using Chronos than without whenever there was enough of a workload for any type of sluggishness to occur.
Using Timers Effectively by Neil Thomas
High Performance JavaScript by Nicholas C. Zakas
How JavaScript Timers Work by John Resig
Understanding JavaScript Timers by Angus Croll
setTimeout Patterns in JavaScript by Yours Truly
A couple months ago, a Lisper who goes by Josh Marchán detailed the process he had been using to write programs in an Object Oriented style.
You first think of what kind of object you want to describe, and create a new class that has data fields that sort of describe that "object", then you write methods for that class. The hope here is that you can just inherit from whatever class, and everything will be okay.
I think this is a familiar process for many developers, including myself. However, Sykosomatic continued by pointing out the weaknesses that this style of programming presents, mainly that
There are many attributes, attribute initializations, and parameters for the initialization method. This grows to be verbose.
Some of these attributes might be completely unnecessary. A subclass might derive some of this information from other sources, or programmatically generate it rather than store it statically in a field.
Subclassing this class is the sole way for other developers or library end-users to reuse any code. Code that had the potential to be reused in other places is unnecessarily tied to a class.
In a similar vein, Raganwald pokes fun at inheritance and describes how OOP used backwards is POO.
The abstract ontology is derived from the behaviour of the individual specimens, the ontology does not define the behaviour of the individual specimens.
OOP gets this backwards. In OOP you define the ontology up front in the form of classes or prototypes. You then derive individual instances or objects from the ontology. The OOP ontology isn't a way of sketching what we observe, it's blueprint for building what we observe, nearly the exact opposite of the naturalist's ontology.
...
Changes and re-arrangements break existing code, because all of the specimens, the instances and objects, depend on the various classes, interfaces, and other constructs that define their behaviour. Is this a problem? Yes again, because computer programs change constantly. Discovery of new requirements, and new information is the norm, not the exception. OOP programs built as towering hierarchies of classes are like perfect crystals, to be admired by architects everywhere but loathed by the programmers responsible for maintaining them.
He goes on to champion an alternative way forward.
What if objects exist as encapsulations, and the communicate via messages? What if code re-use has nothing to do with inheritance, but uses composition, delegation, even old-fashioned helper objects or any technique the programmer deems fit? The ontology does not go away, but it is decoupled from the implementation.
Sykosomatic has a similar revelation after he discovers that the code base for his Chillax project becomes much cleaner when he codes in terms of generic functions and protocols rather than classes.
The beauty here is that you can reuse code without dealing with inheritance, or any sort of class-based hierarchy.
However, these ideas are nothing new. In fact, they are as old as the term "Object Oriented", which was coined by Alan Kay.
Just a gentle reminder that I took some pains at the last OOPSLA to try to remind everyone that Smalltalk is not only NOT its syntax or the class library, it is not even about classes. I'm sorry that I long ago coined the term "objects" for this topic because it gets many people to focus on the lesser idea.
The big idea is "messaging".
Does an object respond to a set of messages? Does it have X, Y, and Z methods? If so, we can use it; who cares if it inherits from a certain parent class or not?
function bad (foo) {
if ( ! (foo instanceof Bar) ) {
throw new TypeError("This is an annoying restriction!");
}
return foo.baz(foo.quux(10));
}
function good (foo) {
if ( !foo.baz || !foo.quux ) {
throw new TypeError("We need foo to have baz and quux methods.");
}
return foo.baz(foo.quux(10));
}
This paradigm is sometimes referred to as duck typing. Wikipedia describes duck typing as "a style of dynamic typing in which an object's current set of methods and properties determines the valid semantics, rather than its inheritance from a particular class."
The classic example is if it walks like a duck, swims like a duck, and quacks like a duck, it must be a duck. I prefer Cheech and Chong's explanation:
Looks like dog shit, smells like dog shit, feels like dog shit, tastes like dog shit. Must be dog shit. Good thing we didn't step in it!
So what am I getting at? I present to you a very simple method to support duck typing as a first class concept in JavaScript.
quacksLikeJust ask if a given object quacksLike you want it to. You can describe the
messages you want an object to respond to with the key, and the type that you
expect in the slot by using a constructor as the value.
var arrayish = {
length: Number
};
var iterable = {
filter: Function,
forEach: Function,
map: Function
};
(function () {
console.log(quacksLike(arguments, arrayish));
// true, because the arguments object has the value
// 3 in its length slot.
console.log(quacksLike(arguments, iterable));
// false, because the arguments object is not blessed
// with the `map`, `filter`, and `forEach` methods.
}(1, "a", {}));
The definition of the function quacksLike is given below.
var quacksLike = function (obj, definition) {
var k, ctor;
for ( k in definition ) {
ctor = definition[k];
if ( ctor === Number ) {
if ( Object.prototype.toString.call(obj[k]) !== "[object Number]"
|| isNaN(obj[k]) ) {
return false;
}
} else if ( ctor === String ) {
if ( Object.prototype.toString.call(obj[k])
!== "[object String]" ) {
return false;
}
} else if ( ! (obj[k] instanceof ctor) ) {
return false;
}
}
return true;
};
Do we really need to formalize duck typing with quacksLike? Strictly, no. You
could call the methods that you expect to exist and let the the errors be raised
if the object was missing that method, or you could check by hand that they
exist like I did in the above function good. I think the latter is better than
the former because it makes your expectations and
dependencies explicit. quacksLike is an easier-to-use formalization of this
pattern.
Composing objects to create new ones is a powerful technique that allows us to easily re-use code for multiple objects. Surprisingly enough, even the Gang Of Four reccomended using composition in favor of inheritance in Design Patterns.
var foo = { 0: "a", 1: "b", 2: "c", length: 3 };
var fooPlusPlus = Object.combine(Array.prototype, foo);
console.log(quacksLike(foo, iterable));
// false
console.log(quacksLike(fooPlusPlus, iterable));
// true
fooPlusPlus.forEach(console.log.bind(console));
// a
// b
// c
I have defined Object.combine using ES5's Object.getOwnPropertyNames for
convenience. Besides making the implementation clearer, it also allows us to
compose objects which include the non-enumerable methods of an object, such as
those on Array.prototype. If we were to use a for-in loop instead of
Object.getOwnPropertyNames, we wouldn't iterate over and copy concat,
forEach, etc. This is an ongoing trend in my code examples for this blog
post. I would rather communicate ideas than deal with browser quirks, or
incomplete ES5 implementations.
Object.combine = function () {
var newObj = {},
i = 0,
args = Array.prototype.slice.call(arguments),
len = args.length;
function copyProperty(k) {
newObj[k] = args[i][k];
}
for ( ; i < len; i++ ) {
Object.getOwnPropertyNames(args[i]).forEach(copyProperty);
}
return newObj;
};
Here is a less trivial example: a mini DOM manipulation library. To be trendy,
the global entry point will be $. This library uses quacksLike to determine
the DOM model and the correct way to attach event listeners, the module pattern
in multiple places to encapsulate private data, and Object.combine to re-use
code that has already been written for us by others in Array.prototype.
window.$ = (function () {
var undef, listen, customAPI;
// Private function to turn `thing` in to an array,
// optionally slicing the first `n` elems off.
function toArray(thing, n) {
return Array.prototype.slice.call(thing, n || 0);
}
// Private function to partially apply the first n arguments
// to `fn`.
function curry (fn) {
var args = toArray(arguments, 1);
return function () {
return fn.apply(this, args.concat(toArray(arguments)));
};
}
// Private function to set the attribute `attr` of a single
// DOM node `node` to `val`.
function nodeAttributeSetter (attr, val, node) {
node.setAttribute(attr, val);
}
// Private function to get the value of the attribute `attr`
// on the DOM node `node`.
function nodeAttributeGetter (attr, node) {
return node.getAttribute(attr);
}
// Do the work to determine the correct method for attaching
// event listeners only once by using `quacksLike` and an
// immediately invoked function.
listen = (function () {
var w3c = {
addEventListener: Function
},
ie = {
attachEvent: Function
};
if ( quacksLike(document.body, w3c) ) {
return function (event, fn, node) {
node.addEventListener(event, fn, false);
};
} else if ( quacksLike(document.body, ie) ) {
return function (event, fn, node) {
node.attachEvent("on" + event, fn);
};
} else {
throw new TypeError("Do not know how to attach event listeners.");
}
}());
// This object is a mixin to be composed with the NodeList
// results of querying the DOM by CSS selector. It provides
// handy methods for getting and setting attributes,
// attaching event listeners, and performing sub-queries by
// CSS on these elements.
customAPI = {
attr: function (attr, val) {
if ( val !== undef ) {
this.forEach(curry(nodeAttributeSetter, attr, val));
return this;
} else {
return this.length > 0
? nodeAttributeGetter(attr, this[0])
: "";
}
},
on: function (event, fn) {
this.forEach(curry(listen, event, fn));
return this;
},
find: function (selector) {
var res = [];
this.forEach(function (node) {
res.push.apply(res, toArray(node.querySelectorAll(selector)));
});
return Object.combine(res, customAPI);
}
};
return function (selector, context) {
context = context || document;
return Object.combine(Array.prototype,
context.querySelectorAll(selector),
customAPI);
};
}());
The mini DOM library might be used like this:
// The following two forms are equivalent.
// They select the same elements.
$("div").find("p");
$("div p");
// Disable all links.
$("a").on("click", function (event) {
event.preventDefault();
alert("Don't leave me all alone!");
});
// Get the id of the first paragraph.
$("p").attr("id");
// Disable all input elementss.
$(input").attr("disabled", "disabled");
// Do stuff with each matched element.
$("div.foo").forEach(function (el) {
doStuffWith(el);
});
To conclude, we should recognize that OOP does not need to be an all or nothing proposition. You can take the parts that are beneficial to you (such as message passing, encapsulation, and composition) and leave the parts which you may not require (such as inheritance).
Finally, take everything I say with a grain of salt (as you should with everything you read on the internet).
Josh Marchán's article Chillax and Protocols.
Raganwald's article OOP Practiced Backwards is POO.
Wikipedia's entry on Duck Typing.
Alan Kay's message to the Squeak mailing list about OOP, inheritance, and message passing.
The Gang of Four, on composition versus inheritance.
Angus Croll's article Delegation vs. Inheritance in JavaScript.
For anyone who hasn't used Python before, every instance method in Python takes the object it is bound to as its first argument, which is named self by convention.
class Foo(object):
def bar(self):
print "This is me:", self
When I refer to "Pythonic" methods, I simply mean methods on an object which have their first argument bound to that object.
This is a very good question, and if I did not have an answer this whole blog post would be questionable. Some people like the way methods work in Python, others do not. I do not want to discuss whether it is good for Python; I want to explain why it is good for JavaScript. Funny enough, the arguments behind whether it is good for Python and whether it is good for JavaScript don't really intersect. This is due to the nature of this in JavaScript, and how it differs from self in Python.
Unlike Python's self, JavaScript's this is not just a normal variable or parameter. It has dynamic binding (as opposed to lexical) meaning it is a reflection of the context of the surrounding function when it is invoked rather than when it is defined. It is common that the value of this will change in the middle of your method definitions:
var myObject = {
foo: function () {
console.log(1, this);
(function () {
console.log(2, this);
}());
setTimeout(function () {
console.log(3, this);
}, 100);
}
};
myObject.foo();
// Logs:
// 1 myObject
// 2 window
// 3 window
If you wanted the second and third calls to console.log to have access to the same this that the first one does, the common solution is to create a normal variable that references the desired context:
var myObject = {
foo: function () {
var that = this;
console.log(1, that);
(function () {
console.log(2, that);
}());
setTimeout(function () {
console.log(3, that);
}, 100);
}
};
myObject.foo();
// Logs:
// 1 myObject
// 2 myObject
// 3 myObject
But I get tired of doing that all the time. Tired of remembering when I need to define that until after I have a bug. Tired of the ugly blemish it puts in my code. I would rather write this:
var myObject = bindSelf({
foo: function (self) {
console.log(1, self);
(function () {
console.log(2, self);
}());
setTimeout(function () {
console.log(3, self);
}, 100);
}
});
myObject.foo();
// Logs:
// 1 myObject
// 2 myObject
// 3 myObject
I find this syntactic helper especially nice when defining prototypes or extending existing objects. These situations tend to rely on state that is stored in this more often than other examples, so I find the utility added by binding this to self also tends to be greater.
var MyView = Backbone.View.extend(bindSelf({
events: {
"click :input": "clickHandler"
},
initialize: function (self, opts) {
...
},
render: function (self) {
...
},
clickHandler: function (self, event) {
...
}
}));
function bindSelf (obj) {
// 1
for (var k in obj) {
if (obj.hasOwnProperty(k) && typeof obj[k] === "function") {
// 2
(function (oldMethod) {
obj[k] = function () {
// 3
return oldMethod.apply(
this,
[this].concat(toArray(arguments))
);
};
}(obj[k]));
}
}
// 4
function toArray (thing) {
return Array.prototype.slice.call(thing);
}
return obj;
}
What is it doing? We are iterating through each of the methods on obj and rebinding the name of each method to a new function which calls the old method with its this concatenated with its arguments. That was a mouthful.
Here is the step-by-step:
First, we iterate over all of the keys in obj which are not from the prototype chain and whose values are functions. This is important. We obviously don't want to try and redefine non-method attributes of obj as functions, which is why we check that typeof obj[k] === "function". However, we also do not want to break any of the object's methods which are inherited from its prototype, which is why we check that obj.hasOwnProperty(k).
Before rebinding obj[k] to the new function, we need to make an immediately invoked function expression so that we create a new variable oldMethod on every iteration of the loop. If we didn't do this, and incorrectly wrote the code something like this:
...
// At the top level of `bindSelf`.
var oldMethod;
...
// Inside the loop.
oldMethod = obj[k];
obj[k] = function () {
return oldMethod.apply(
this,
[this].concat(toArray(arguments))
);
}
...
...
then we would capture the same oldMethod variable in the closure of every new function. Unlike languages such as C, JavaScript does not create a new scope every time you open the curly braces. Every new method would call the same oldMethod; definitely not what we want.
Okay we are finally creating these new functions and rebinding them to where the oldMethod used to live. When we call oldMethod, lets make sure that this inside oldMethod is still bound to this; and lets also add this to the front of the arguments we were called with before passing them to oldMethod. This is what we set out to do all along. Its really quite simple from this point on, you just need to understand what Function.prototype.apply does.
The last piece is our good old friend toArray. Any JavaScripter worth their salt has probably written this exact function many times before, possibly with a different name. All it does is take an array-like object and turn it in to a real array. What is an array-like object? It is one which has a length property and possibly 0, 1, 2, etc. properties defined. The cannonical example is the arguments object, which is what we are using it for. See the problem with arguments is that it doesn't have any of the Array.prototype's methods attached, and that when you concatenate it with a list, you get unexpected results:
// Does *not* return [1,2,3,4,5,6] as you might expect!
(function () {
return [1,2,3].concat(arguments);
}(4, 5, 6));
// Instead it returns something like this:
[1, 2, 3, { 0: 4, 1: 5, 2: 6, length: 3 }]
By calling toArray on arguments before concatenation, we get the expected result.
Today I was prompted to throw Pycco up on PyPi. I had never pushed a package to PyPi before; I assumed it would be hard, require too much sign up and registration. Turns out that it was a breeze to register and push a project, so I did it for Zoolander as well.
If anyone out there is afraid to put one of their Github projects on PyPi because of perceived hassle, I am here to tell you otherwise. Just do it, its easy.
python setup.py register python setup.py sdist upload
Before discussing possible implementations of multiple value returns, I want to illustrate some of the use cases for them.
Let's start with something simple. The function get treats obj as a hash table or dictionary and returns the value of indexing it by key.
function get (key, obj) {
return obj[key];
}
At first, everything seems ok...
get("foo", { foo: 5}); // 5
...however, ambiguities begin to arise. Ignoring the issues with prototypes, .hasOwnProperty(), and modifications to the global object's prototype, how can we tell the difference between when a key is explicitly set to undefined, and when there is no value associated with that key and it returns undefined by default?
get("foo", {}); // undefined
get("foo", { foo: undefined }); // undefined
Here is another example. Taking the User API for granted, the following getOrCreateUser function also has some serious issues. Is it a new user or not? The caller of this function probably needs to know that information.
function getOrCreateUser (username, email) {
var user = User.query.byUsername(username)
.byEmail(email)
.first();
return user !== null
? user
: new User({
username : username,
email : email
});
}
Both of these types of issues can be solved with multiple return values where the secondary return values contain meta information about the primary return value. Unlike languages such as Common Lisp and Lua, JavaScript does not natively support multiple return values, however we have a variety of ways we can implement them ourselves.
It is fairly common to see multiple values returned as an array; sometimes I have returned objects to accomplish the same thing. There are advantages and drawbacks to this technique, and it is incredibly more useful with destructuring assignment (a watered down flavor of pattern matching) than without.
function getOrCreateUser (username, email) {
var user = User.query.byUsername(username)
.byEmail(email)
.first(),
isNew = user === null;
if ( isNew )
user = new User({
username : username,
email : email
});
return [user, isNew];
}
This technique works fairly well if you are only supporting Mozilla's JS 1.7 and up, and therefore can rely on destructuring assignment.
var user, isNew;
[user, isNew] = getOrCreateUser("franky", "frankster@gmail.com");
console.log(user); // [object Object]
console.log(isNew); // true
[user, isNew] = getOrCreateUser("franky", "frankster@gmail.com");
console.log(user); // [object Object]
console.log(isNew); // false
If you need to support the various browsers and their various JavaScript/ECMAScript implementations, arrays become clumsy. The caller is forced to destructure the return values by hand.
var temp = getOrCreateUser("dolemite", "rudy@thetotalexperience.com"),
user = temp[0],
isNew = temp[1];
The abstraction is leaky because it forces the caller of the function to know that it returns multiple values via an array; you can't just get the primary value via a normal invocation. Suppose that in one case, we don't care whether it is a new user or not.
Someone who is a consumer of our getOrCreateUser API might just assume it returns one value; this will lead to bugs.
var user = getOrCreateUser("mocha", "kitty@cat.com"); // Wrong; leads to bugs!
Once they have tracked down their nasty bug created above, they will find that the multiple values returned as an array is a leaky abstraction.
var user = getOrCreateUser("mocha", "kitty@cat.com")[0]; // Leaky abstraction!
Returning an object also suffers from the same ailments, but without taking advantage of any destructuring syntactic sugar in JS 1.7.
// Gross
var temp = getOrCreateUser("dolemite", "rudy@thetotalexperience.com"),
user = temp.user,
isNew = temp.isNew;
// Leads to bugs: return value is a container object not a user.
var user = getOrCreateUser("odb", "dirtdawg@gmail.com");
// Leaky abstraction
var user = getOrCreateUser("vinnie", "vincent.chase@entourage.com").user;
We can fix some of these issues with Continuation Passing Style. (For those who are not familiar with CPS, it basically involves passing around callback functions that represent the computation waiting to happen when the current function returns). If we want to return more than one value, it is as simple as calling the continuation with more than one argument.
function get (key, obj, cont) {
return cont(obj[key], key in obj);
}
get("foo", {}, function (val, hasProp) {
console.log(val); // undefined
console.log(hasProp); // false
});
get("foo", { foo: undefined }, function (val, hasProp) {
console.log(val); // undefined
console.log(hasProp); // true
});
But now we are forced to use functions for every invocation, even when we only want the primary return value. (Granted, it is nice that JS has such dynamic function parameters which let us choose to bind only some of the returned values).
console.log(100 === get("foo", { foo: 10 }, function (val) {
return val * val;
}));
// true
This does not seem to be that much better than the previous solution involving arrays; it certainly is not more concise. The best we can do is to make the continuation optional and if it is missing just return the primary value.
function get (key, obj, cont) {
return typeof cont === "function"
? cont(obj[key], key in obj)
: obj[key];
}
get("foo", { foo: "Normal" }); // "Normal"
get("foo", {}, function (val, hasProp) {
console.log(val); // undefined
console.log(hasProp); // false
});
The API for the caller of this function is excellent — the best that JavaScript can offer in this situation — but the bit of logic that checks for the continuation leaves something to be desired. Do we need to repeat this snippet for every function that will return multiple values? Of course not.
Formalizing the pattern of optional continuations, we can create a function values which takes a continuation followed by the values to return. If the continuation is not a function (for example it is undefined because it was not passed to the caller function) then the primary return value is returned.
function values (k /*, and values */) {
return typeof k === "function"
? k.apply(this, Array.prototype.slice.call(arguments, 1))
: arguments[1];
}
Here is the final revision of the getOrCreateUser function, which uses values.
function getOrCreateUser (username, email, cont) {
var user = User.query.byUsername(username)
.byEmail(email)
.first(),
isNew = user === null;
if ( isNew )
user = new User({
username : username,
email : email
});
return values(cont, user, isNew);
}
Maybe we don't care whether or not the user is new.
var me = getOrCreateUser("fitzgen", "fitzgen@gmail.com");
Or maybe we have special things to do with new users before continuing.
var me = getOrCreateUser("fitzgen", "fitzgen@gmail.com", function (user, isNew) {
if ( isNew )
createPasswordFor(user);
return user;
});
The values function is the best of all available options. You can call the function normally as if it only returned one value without passing in a continuation function, or you can capture all (or as many as you want) of the return values via the continuation. It is also compatible with all JavaScript/ECMAScript environments.
Thanks to Kartik Agaram, Angus Croll, and Brian Goldman for reading drafts of this article.
Last updated:
May 16, 2012 04:22 PM
All times are UTC.
Powered by:
