Vincent Gable’s Blog

May 31, 2009

The Best Quicksort Ever

Filed under: Design,Programming,Sample Code | , , , ,
― Vincent Gable on May 31, 2009

The first time I saw this quicksort in Haskell was an eye opening moment,

 
qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

The first line reads: “When you sort an empty list ([]), the result is another empty list”. The second line reads: “To sort a list whose first element is named x and the rest of which is named xs, sort the elements of xs that are less than x, sort the elements of xs that are greater than or equal to x, and concatenate (++) the results, with x sandwiched in the middle.”

The code is so concise, yet clear (even with cryptic variable names like xs). The day my professor wrote it on the whiteboard was the first time I internalized that there might be something good about the alien world of functional programming.

The biggest revelation to me was, filter (< x) xs . It’s amazing that (< x) builds a temporary, unnamed, function equivalent to C++,

bool lessThanX(AnyOrderedType y){
    return y < X;
}
//plus the definition of X somewhere...

Building a function! It’s still profound stuff to me. And clearly it really uses fewer lines of code. Amazingly, using list comprehension syntax is not more concise,

qsort (x:xs) = qsort [i | i <- xs, i < x] ++ [x] ++ qsort [i | i <- xs, i <= x]

compared to the original,

qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

I hope this is an ah-ah moment for someone else too. I’d love to know what made you interested in functional programming; or if you know of a more elegant quicksort implementation.

May 29, 2009

Don’t Waste Memory to Save Time

Filed under: iPhone,MacOSX,Programming,Usability | , , ,
― Vincent Gable on May 29, 2009

In the provocatively titled, Space is Time: How Your CS Theory Class Lied to You, Greg Parker explains why hogging memory to speed up your program is a bad idea on consumer-level devices.

Space is time. An optimization that makes your program faster may make the user’s system slower overall. Play well with others.

I think it’s excellent advice. There’s only one point I want to make (and it must be made now, before silent SSD hard disks become more popular).

Every time your whole computer is nonresponsive, it makes that grrnrrnrnrr sound, right? That’s because it ran out of RAM, and the virtual memory system is thrashing to the disk. In the real word, on computers like the one you are on now, low memory plays a part in every system-wide slowdown.

Hogging the CPU can make your application slow. (Although if you pay attention to threading, and the run loop, using 100% of every core shouldn’t kill responsiveness and usability.) But hogging memory makes the whole damn world slow, including your application. And the worst case scenario of bad memory management kills the system deader then a kernel panic.

This isn’t to say that caching never makes sense. But a healthy respect for memory usage generally trumps worrying about the CPU.

May 26, 2009

Secret Questions Are a Bad Idea

Filed under: Design,Quotes,Security,Usability | , , ,
― Vincent Gable on May 26, 2009

Secret questions are an easier way for someone to hack your account. I don’t see that they offer much over asking people to pick an insecurely convenient password.

Here’s some data on how insecure secret questions are,

Acquaintance with whom participants reported being unwilling to share their webmail passwords were able to guess 17% of their answers (to “secret” questions). Participants forgot 20% of their own answers within six months. What’s more, 13% of answers could be guessed within five attempts by guessing the most popular answers of other participants, though this weakness is partially attributable to the geographic homogeneity of our participant pool.

—
It’s no secret: Measuring the security and reliability of authentication via ‘secret’ questions, Stuart Schechter, A. J. Bernheim Brush, Serge Egelman, 17 May 2009

(Via Bruce Schneier)

It’s important to note that people often forget answers to their own secret questions. Anecdotally, I’ve had to call my bank twice because I forgot exactly how I typed in my answers.

Forgetting the answer to a secret question can be embarrassing, unlike forgetting a password. I once got my mother’s maiden name wrong repeatedly. It was pretty awkward. (A credit card was also in my mother’s name, so when they asked “for my mother’s maiden name” they really meant her mother’s maiden name.)

I don’t know of any statistics on how often accounts are compromised by secret questions. But there have been high-profile cases, like Sarah Palin’s email,

…the Palin hack didn’t require any real skill. Instead, the hacker simply reset Palin’s password using her birthdate, ZIP code and information about where she met her spouse — the security question on her Yahoo account, which was answered (Wasilla High) by a simple Google search.

Bruce Schneier says, “Passwords have reached the end of their useful life. Today, they only work for low-security applications. The secret question is just one manifestation of that fact.” If you must use password authentication, then don’t weaken it further with a questionable back door.

May 19, 2009

Improving Twitter.com: Space to Work

Filed under: Design,Sample Code,Tips,Usability | , , , , ,
― Vincent Gable on May 19, 2009

The Change

Enlarge the “What are you doing” box on Twitter.com, to make compressing substantial ideas easier.

Twitter.com with a larger text-field

Motivation

I’ve been disappointed with the posting interface of every Twitter-client I’ve tried so far. Just like any writing, tweets start with a first draft. My first drafts are often longer than 140 characters. That shouldn’t be a problem; trimming the fat is part of any editing process. But most Twitter-interfaces are so downright hostile to anything longer then 140 characters that trimming a 145 letter utterance is a frustrating study in fighting my tools.

(The worst client I tried was, Blogo, which would stop you from typing and yell at you with a dialog if you dared press another key after typing 140 characters. But Twitterrific was little better; I don’t understand how something so user-unfriendly became so popular.)

Even Twitter.com doesn’t give you enough room for writing a long, but under-the-limit tweet. To see for yourself, just start typing “mmmmm”; the box will run out of room before you run out of characters. It’s downright crazy to have to scroll to see all of a tweet you are writing.

Now there’s nothing wrong with trying to prescribe a pithy style of communication. Clearly Twitter wouldn’t have worked otherwise. But punishing users for doing the “wrong” thing isn’t as effective as giving them the tools to change their behavior, to wit: space to work on shortening their writing.

The Code

This CSS code makes the direct-messaging, and “what are you doing?” text-boxes tall enough to hold 5 lines of text without scrolling. By default Twitter’s web interface only holds 2 lines of text on screen.

#dm_update_box #direct_message_form fieldset div.info textarea#text,
#status_update_box #status_update_form fieldset div.info textarea#status {
	height: 6em !important;
}

The selectors I used are pretty specific to Twitter.com, so it’s unlikely this will interfere with another site’s layout, unless it’s HTML code is nearly identical to Twitter’s.

How-To: Safari

Copy the above code into a .css file, (“CustomSafari.css” is what I called mine) then select that file in Safari -> Preferences -> Advanced -> Style sheet:
safariStyleSheet.png

After restarting Safari, Twitter’s web interface should give you room to work.

May 15, 2009

Concise NSDictionary and NSArray Lookup

Filed under: Objective-C,Programming,Research,Sample Code,Usability | , ,
― Vincent Gable on May 15, 2009

I started writing a list of ways I thought Objective-C could be improved, and I realized that many of my wishes involved more compact syntax. For example [array objectAtIndex:1] is so verbose I think it diminishes readability, compared to array[1].

I can’t quite match that brevity (can you, by using Objective-C++?), but with a one-line category, you can say, x = [array:1];.

@interface NSArray (ConciseLookup)
- (id):(NSUInteger)index;
@end
@implementation NSArray (ConciseLookup)
- (id):(NSUInteger)index;
{
	return [self objectAtIndex:index];
}
@end

My question is: do you find this compact “syntax” useful at all, or is it added complexity with no substantial code compression? Personally I think the latter, but the number of wishes I had involving more concise Objective-C syntax makes me wonder…

May 14, 2009

Emergent Libraries

Filed under: Programming,Research | , , , , , ,
― Vincent Gable on May 14, 2009

I have latched onto an idea, but don’t have the resources to follow up on it: could a static-analysis tool identify repeated patterns of code, across many code bases, that should be extracted out as subroutines and higher-level functions? How universal would these “emergent libraries” be?

My inspiration here is Section 4.1 Identifying Common Functions, in the excellent paper Some Thoughts on Security After Ten Years of qmail 1.0 (PDF), by Daniel J. Bernstein,

Most programmers would never bother to create such a small function. But several words of code are saved whenever one occurrence of the dup2()/close() pattern is replaced with one call to fd_move(); replacing a dozen occurrences saves considerably more code than were spent writing the function itself. (The function is also a natural target for tests.) The same benefit scales to larger systems and to a huge variety of functions; fd_move() is just one example. In many cases an automated scan for common operation sequences can suggest helpful new functions, but even without automation I frequently find myself thinking “Haven’t I seen this before?” and extracting a new function out of existing code.

What’s particularly fascinating to me are the new operations we might find.

Before I was exposed to the Haskell prelude I hadn’t known about the fundamentally useful foldl and foldr operations. I had written dozens of programs that used accumulation, but it’s generalization hadn’t occurred to me — and probably never would have. Static analysis can help uncover generalizations that we might have missed, or didn’t think were important, but turn out in practice to be widely used operations.

May 9, 2009

Words Lie More Than Statistics

Filed under: Quotes | , , , ,
― Vincent Gable on May 9, 2009

Increasingly it seems, people throw up their hands, “graphs and statistics are all lies anyway!” and never deeply examine quantitative information. And that’s part of the reason why I can’t recommend The Visual Display of Quantitative Information enough.

For many people the first word that comes to mind when they think about statistical charts is “lie.” No doubt some graphics do distort the underlying data, making it hard for the viewer to learn the truth. But data graphics are no different from words in this regard, for any means of communication can be used to deceive. There is no reason to believe that graphics are especially vulnerable to exploitation by liars; in fact, most of us have pretty good graphical lie detectors that help us see right through frauds.

Much of twentieth-century thinking about statistical graphics has been preoccupied with the question of how some amateurish chart might fool a naive viewer. Other important issues, such as the use of graphics for serious data analysis, were largely ignored. At the core of the preoccupation with deceptive graphics was the assumption that data graphics were mainly devices for showing the obvious to the ignorant. It is hard to imagine any doctrine more likely to stifle intellectual progress in a field…

–Edward Tufte, The Visual Display of Quantitative Information, page 53.

You will be lied to more often, and more subtly, with words than with figures. But unlike empty words, the data behind a chart is verifiable, and can be objectively redrawn. As I see it, quantitative analysis is our best chance to reason truthfully and without ego. Sometimes infographics are a better tool than words, especially for summarizing large datasets objectively. If anything, we should be scared when there aren’t graphs and statistics.

May 6, 2009

No Common Name

Filed under: Quotes | , , , ,
― Vincent Gable on May 6, 2009

The problem with insects is their sheer number. There are millions of species. How many million we can’t say, and our guesses even as to the appropriate order of magnitude are tentative.* Certainly, there are too many for any language to absorb into common parlance. Most pass their lives entirely unnoticed by humans, and any specialists who happen to work on them are content with the scientific names. This is to say, most insects have no common name at all.

*for more on the diversity of life, see Rob Dunn’s book Every Living Thing.

—Alex Wild

May 3, 2009

Confounding Circles

Filed under: Quotes | , , , , ,
― Vincent Gable on May 3, 2009

Consider a technique used by the legendary pickpocket Apollo Robbins…. When the researchers asked him about his devious methods—how he could steal the wallet of a man who knew he was going to have his pocket picked—they learned something surprising: Robbins said the trick worked only when he moved his free hand in an arc instead of a straight line. According to the thief, these arcs distract the eyes of his victims for a matter of milliseconds, just enough time for his other hand to pilfer their belongings.

At first, the scientists couldn’t explain this phenomenon. Why would arcs keep us from looking at the right place? But then they began to think about saccades, movements of the eye that can precede conscious decisions about where to turn one’s gaze. Saccades are among the fastest movements produced by the human body, which is why a pickpocket has to trick them: The eyes are in fact quicker than the hands. “This is an idea scientists had never contemplated before,” Macknik says. “It turns out, though, that the pickpocket was onto something.” When we see a hand moving in a straight line, we automatically look toward the end point—this is called the pursuit system. A hand moving in a semicircle, however, seems to short-circuit our saccades. The arc doesn’t tell our eyes where the hand is going, so we fixate on the hand itself—and fail to notice the other hand reaching into our pocket. “The pickpocket has found a weakness in the way we perceive motion,” Macknik says. “Show the eyes an arc and they move differently.”

Jonah Lehrer,
WIRED MAGAZINE: 17.05 (1999-04-20), Magic and the Brain: Teller Reveals the Neuroscience of Illusion

May 1, 2009

NSXMLParser and HTML/XHTML

Filed under: Bug Bite,iPhone,Objective-C,Programming | , , , ,
― Vincent Gable on May 1, 2009

NSXMLParser converts HTML/XML-entities in the string it gives the delegate callback -(void)parser:(NSXMLParser *)parser foundCharacters:(NSString *)string. So if an XML file contains the string, "&lt; or &gt;", the converted string "< or >" would be reported to the delegate, not the string that you would see if you opened the file with TextEdit.

This is correct behavior for XML files, but it can cause problems if you are trying to use an NSXMLParser to monkey with XHTML/HTML.

I was using an NSXMLParser to modify an XHTML webpage from Simple Wikipedia, and it was turning: “#include &lt;stdio&gt;” into “#include <stdio>“, which then displayed as “#include “, because WebKit thought <stdio> was a tag.

Solution: Better Tools

For scraping/reading a webpage, XPath is the best choice. It is faster and less memory intensive then NSXMLParser, and very concise. My experience with it has been positive.

For modifying a webpage, JavaScript might be a better fit then Objective-C. You can use
- (NSString *)stringByEvaluatingJavaScriptFromString:(NSString *)script to execute JavaScript inside a UIWebView in any Cocoa program. Neat stuff!

My Unsatisfying Solution

Do not use this, see why below:

- (void)parser:(NSXMLParser *)parser foundCharacters:(NSString *)string;
{
	string = [string stringByReplacingOccurrencesOfString:@"<" withString:@"&lt;"];
	string = [string stringByReplacingOccurrencesOfString:@">" withString:@"&gt;"];

	/* ... rest of the method */
}

Frankly that code scares me. I worry I’m not escaping something I should be. Experience has taught me I don’t have the experience of the teams who wrote HTML libraries, so it’s dangerous to try and recreate their work.

(UPDATED 2009-05-26: And indeed, I screwed up. I was replacing & with &amp;, and that was causing trouble. While my “fix” of not converting & seems to work on one website, it will not in general.)

I would like to experiment with using JavaScript instead of an NSXMLParser, but at the moment I have a working (and surprisingly compact) NSXMLParser implementation, and much less familiarity with JavaScript then Objective-C. And compiled Obj-C code should be more performant then JavaScript. So I’m sticking with what I have, at least until I’ve gotten Prometheus 1.0 out the door.

Powered by WordPress