Deductions has a problem: it punishes users who enter the wrong rule names. It doesn’t make nice. In the current release, if you enter a valid rule name, such as “Conj”, everything is happy. But if you enter an invalid rule name, such as “Conj” or “Conh”, the rule simply disappears, and you have to type it all over again if you want to fix it.

This goes against what might be called the principle of pleasant surprises. In a nutshell, this principle means that a program should try to adapt to the user. In this case, Deductions should try to figure out what rule the user was trying to enter when she types “conh”. What we need is fuzzy string matching.

There are a plethora of fuzzy string matching algorithms. The basic idea is that you take an input string, a list of possible target strings, and rank the possible target strings according to the “distance” to the input string. The target with the least distance is (hopefully) the intended string.

One of the simplest fuzzy string matching algorithms is one in which you simply calculate the number of letters that are different between the input string and a given target string. For example, suppose the input string is “hello” and the target string is “hullo”. Since the “e” in the input string is a “u” in the target string, the distance between these strings is 1. Given target string “wullo”, the distance between the strings is 2.

This algorithm just illustrates the idea; it is way too simple for most real-world applications. For example, an extraneous letter at the beginning, for example, could throw it off completely, making the distance between “hello” and “whello” 6. A more realistic algorithm is one that I settled on for Deductions, called the Damerau-Levenshtein algorithm.

The Damerau-Levenshtein algorithm calculates the distance between two strings as a function of: (i) insertion of a single character, (ii) deletion of a single character, (iii) substitution of a single character, or (iv) transposition of a pair of characters. With the example of “hello” and “whello” above, the distance would be 1, because all that is required is a deletion of the “w” in the second string. Given “hello” and “hlel”, the distance is 2, because you need to transpose “le” and then add “o”.

I have been very pleased with my initial tests of the Damerau-Levenshtein algorithm in Deductions. Now, instead of punishing users for entering an invalid rule name, Deductions guesses what rule they meant. Deductions 1.2 will make nice with users who enter the wrong rule names.

The following is some code you can use to implement the Damerau-Levenshtein algorithm in your own application. It is based on Rick Bourner’s implementation of the Levenshtein algorithm (Levenshtein is largely similar to Damerau-Levenshtein, except that it lacks support for transposition), and some pseudo-code for the Damerau extension:

-(float)compareString:(NSString *)originalString withString:(NSString *)comparisonString
{
	// Normalize strings
	[originalString stringByTrimmingCharactersInSet:[NSCharacterSet whitespaceAndNewlineCharacterSet]];
	[comparisonString stringByTrimmingCharactersInSet:[NSCharacterSet whitespaceAndNewlineCharacterSet]];

	originalString = [originalString lowercaseString];
	comparisonString = [comparisonString lowercaseString];

	// Step 1 (Steps follow description at http://www.merriampark.com/ld.htm)
	NSInteger k, i, j, cost, * d, distance;

	NSInteger n = [originalString length];
	NSInteger m = [comparisonString length];	

	if( n++ != 0 && m++ != 0 ) {

		d = malloc( sizeof(NSInteger) * m * n );

		// Step 2
		for( k = 0; k < n; k++)
			d[k] = k;

		for( k = 0; k < m; k++)
			d[ k * n ] = k;

		// Step 3 and 4
		for( i = 1; i < n; i++ )
			for( j = 1; j < m; j++ ) {

				// Step 5
				if( [originalString characterAtIndex: i-1] == 
				   [comparisonString characterAtIndex: j-1] )
					cost = 0;
				else
					cost = 1;

				// Step 6
				d[ j * n + i ] = [self smallestOf: d [ (j - 1) * n + i ] + 1
				andOf: d[ j * n + i - 1 ] +  1
				andOf: d[ (j - 1) * n + i - 1 ] + cost ];

				// This conditional adds Damerau transposition to Levenshtein distance
				if( i>1 && j>1 && [originalString characterAtIndex: i-1] ==
					[comparisonString characterAtIndex: j-2] &&
					[originalString characterAtIndex: i-2] ==
					[comparisonString characterAtIndex: j-1] )
				{
					d[ j * n + i] = [self smallestOf: d[ j * n + i ]
					andOf: d[ (j - 2) * n + i - 2 ] + cost ];
				}
			}

		distance = d[ n * m - 1 ];

		free( d );

		return distance;
	}
	return 0.0;
}

// Return the minimum of a, b and c - used by compareString:withString:
-(NSInteger)smallestOf:(NSInteger)a andOf:(NSInteger)b andOf:(NSInteger)c
{
	NSInteger min = a;
	if ( b < min )
		min = b;

	if( c < min )
		min = c;

	return min;
}

-(NSInteger)smallestOf:(NSInteger)a andOf:(NSInteger)b
{
	NSInteger min=a;
	if (b < min)
		min=b;

	return min;
}

With this code, you’ll be able to calculate the distance between any two strings. Given an input string and an array of target strings, you can run through the array and decide which target the input is most like.

In preparation for the release of Deductions 1.1, I completed an interview that might be of some interest:

Question: What’s the most unique, useful feature of Deductions?

Wandering Mango: I’d have to say the most useful feature is different from the most unique feature. The most useful feature is that Deductions gives you immediate feedback on proofs; it lets you know whether you made a mistake right away. The most unique feature is the hint engine. Often, when you’re working on proofs in logic, you can get stuck. The hint engine gives you an idea how you might solve the problem.

Q: Why did you create Deductions?

WM: I created Deductions because I have always been fascinated by computational logic, and because the vast majority of natural deduction apps lack a modern look and feel. When you look at the other natural deduction programs that are on the market, most of them are antiquated. They are written for DOS, or Windows 95. Some are rudimentary Java applets. As you might expect, these programs tend to be awkward and primitive. I wrote Deduction to have an intuitive user interface, and to be a modern alternative.

Q: What is most interesting to you about developing software for the Mac platform?

WM: What is most interesting to me is the attention to design. From the Cocoa framework, to separation of the view and model, to the polished user interface that users expect, the Mac development environment is something really special. I’ve worked on other platforms, and so I really feel like I’ve come to a place where people are very interested in what your program does and how your program does it. It is the interest in “how” that sets the platform apart.

Q: What features should a prospective buyer look into during a trial of your product?

WM: A prospective buyer should have a look at the video tutorials, and then if you know anything about natural deduction, run through some deductions to see how the program helps you learn. Deductions is a great tool, and this will give you a good idea how and why.

Q: What are some interesting experiences you’ve had creating new versions of your software when OS is upgraded?

WM: An OS update always makes developers a little jittery, but so far everything has gone smoothly. I was able to plug directly into a number of Objective-C 2.0 features that came about it Leopard, and that made the development of Deductions a lot easier. I have no doubt that we’ll be incorporating some Snow Leopard technologies into Deductions too. I’m thinking about putting the hint engine into a separate thread using Grand Central Dispatch.

Q: What features would you like to add to your product that at this time seem improbable/impossible?

WM: I’d really like to improve the hint engine to the point that it gives advice several steps ahead: not just “derive a contradiction,” but “derive this particular contradiction in order to achieve this particular goal.” Now for really fascinating reasons (to me, anyway) that have to do with the computability of predicate logic, there are fixed limits on just how far advice can go. But I’d love to do the research necessary to design a hint engine that presses right up against those fixed limits. That just seems out of reach right now.

Q: What should a beginning logic student know before purchasing Deductions?

WM: If you are taking a class, you should know that formal logic is unlike mathematics in that the symbols and rules differ from textbook to textbook. Deductions works with several popular textbooks, and is very configurable, but it does not work with every textbook. If your textbook is The Logic Book by Bergmann, Moor and Nelson, A Modern Formal Logic Primer by Teller, or An Accessible Introduction to Serious Mathematical Logic by Roy, then Deductions will be of great help. If you are using some other textbook, Deductions may or may not be compatible; feel free to contact us if you’re not sure, or ask your instructor.

Q: Can someone use Deductions even if not taking a logic course?

WM: Of course! Deductions has several video tutorials that you can follow, but if you really want to learn how to do proofs in formal logic, you’ll want to follow a textbook or set of lectures. Fortunately, Teller’s Modern Formal Logic Primer and Roy’s Accessible Introduction to Serious Mathematical Logic are freely available on the web.

Q: What’s your favorite Mac app out there from another developer? Why?

WM: VoodooPad, without a doubt. I use it to keep track of notes, press releases, marketing, feature requests and business expenses. I use it to write the Deductions help files. I find it indispensable.

Q: Can you us more about your company?

WM: I started Wandering Mango just this year, and Deductions is my first product. I’m hoping to make a go of it as a Mac indie developer. I think I’m lucky in that the market for Deductions is pretty well-defined (instructors and students who study formal logic in philosophy, mathematics, and computer science, and other people interested in formal logic).

Q: What’s with the name “Wandering Mango”?

WM: Well, Mac indie developers tend to have incongruous names that stick in your head: Rogue Amoeba, Flying Meat, Delicious Monster, and so on. Our name follows that tradition. A friend of mine decided that “Wandering Mango” sounded like a drink, and she created a recipe to celebrate our first app. It’s on our About page, and it’s really very tasty.

The last time I talked about version control, I discussed why you should use version control for your solo developer project, some of version control systems you have as options, and some reasons I chose Mercurial. Now, I want to talk about using Mercurial to solve a typical development problem: concurrent development.

The Problem and a Solution

Suppose that you have come to a 1.0 release (just as I have, about two weeks ago). At this point, it is not unreasonable for your development to branch. In the first branch, you want to start work on 1.0.1. Here, you’ll have small bugfixes to your 1.0 release. (For example, I’ve added a “reset to defaults” option in preferences, and I found a typo in the help files.) In the second branch, you want to start work on 1.1. Here, you’ll revise or add a feature to your 1.0 release. (For example, I am adding some inference rules in 1.1, and simplifying preferences.)

Why not just copy your original 1.0 release code into two additional directories, label those directories 1.0.1 and 1.1 respectively, and be done with it? Well, here’s the thing: the small bugfixes I’m planning to roll out as part of 1.0.1 will also apply to 1.1. And while 1.0.1 will be released much sooner than 1.1, I want to begin work on 1.1 immediately. So, how do I make sure the small bugfixes in 1.0.1 are transferred to the code I’m working on in 1.1? Well, I could just do a lot of copying and pasting. That’s what developers did before version control, after all. But this wastes time, and it is possible that I will make some copying mistakes. The elegant solution is to use branchy development under version control.

Growing Branches

Imagine that your project directory is called “1.0” that is a Mercurial repository, and you have a file, Myfile.txt that is part of that repository:

1
2
3
4
5

You release your program, and Myfile.txt goes out the door with it. Now, you want to start work on 1.0.1 and 1.1. First, clone your 1.0 repository twice, as follows:

hg clone 1.0 1.0.1
hg clone 1.0 1.1

Now you have two copies of the 1.0 directory, conveniently named 1.0.1 and 1.1. Now, cd into 1.0.1, and change Myfile.txt to look like this:

1 – Minor change
2
3
4
5

And cd into 1.1, and change Myfile.txt to look like this:

1
2
{ Big change here }
3
4
5

So, let’s imagine that you’re happy with the change you made to 1.0.1, and everything is working without a hitch. You commit the change to 1.0.1 the repository. You’re still hacking away at 1.1, but you’d like to incorporate the change you made in 1.0.1 (a change that is unrelated to the changes you are making in 1.1). How do you do this? Well, first, cd into 1.1. Now issue the following commands:

hg pull ../1.0.1
hg merge
hg commit -m ‘Merged 1.1 with 1.0.1’

This will integrate the changes you made in 1.0.1 into your 1.1 repository. When you issue pull, you bring in the changes from 1.0.1, but do not update the files in your working directory. It is merge that updates the files in your working directory. Finally, you commit the results of the merge to the 1.1 repository. You will get the following result:

1 – Minor change
2
{ Big change here }
3
4
5

It goes without saying that you should have a backup of your repository and files before you start doing this sort of thing for the first time, just in case things do not go as planned. For more information on branchy development, I suggest you have a look at The Basics and Merging Work, both chapters of Mercurial: The Definitive Guide.

This article shows, quite graphically, the way search engine sites have changed, and it got me thinking about design again. In particular, how important simplicity is to good design. The front page of most search engines have changed dramatically since the late 1990s. Perhaps the single greatest driver of these changes is Google, which really gained traction at the turn of the century. Google was different, even in its earlier iterations, in that it presented users with a streamlined user interface: a white screen, in the centre of which is a search box. Nice and minimal. After all, that’s why you go to a search engine site: to search.

Compare the 2009 Hotbot, Webcrawler, Ask, Altavista, Bing, AOL Search and Netscape Search, to their respective pre-Google incarnations, and you can see that Google’s influence on their design has been profound. If imitation is the highest form of flattery, then Google gets flattered a lot.

Simplicity Done Right

So, Google has a simple user interface. But that doesn’t mean that it lacks power. And its power is accessible in two ways: first, there are Google-specific tricks a knowledgeable user can employ to make search more powerful. And second, there are ways in which Google intervenes to help you find what you are looking for, faster. Generally speaking, power in the first case comes from specific knowledge about how Google works: for example, knowing that you can append “site:http://domain-name” to a search query to search just that site. If you don’t know you can use “site:”, you’ll never get the benefit of this sort of search. In a sense, you are meeting Google’s expectations. Power in the second case comes from Google anticipating what you want. Google is meeting your expectations.

The simplicity of Google’s user interface is preserved only in the latter case. Only in this case do you get a pleasant surprise: type “16 miles in km”, and you get the result. Nice and simple. In the former case, there are no surprises: you used Google-specific parameters to narrow the search. Clearly, it is better to be surprised pleasantly, than expend time and effort to learn the contingent intricacies of a particular search engine (yes, even when using the search engine). So, simplicity done right is for power to be revealed as pleasant surprises.

Incidentally, Wil Shipley gets close to this idea of the “pleasant surprise” in his discussion On Heuristics and Human Factors. His cardinal rule is basically that the program should adapt to the user, not the other way around. In some sense this means: maximise pleasant surprises.

Choice

I appreciate applications that have deep preferences. This appreciation is reflected in Deductions’ preferences. Here is the front panel (the General tab):

Here are some screenshots of the other tabs: Editing, Rules, and Negation. Lots of choices. But I am sympathetic to Joel Spolksy’s advice that suggests the developer should look at each proposed option and ask: does the user care? The short version of his answer to this question: the user does not care unless the choice has something directly to do with the tasks they are trying to accomplish with your program. To illustrate: the user cares about where they save their data – give the user that choice; but the user does not care about how you index their data – make this choice for them and move on.

Take another look at the preference tabs for Deductions. They are packed with options for configuring Deductions to work with particular systems of logic. I need to make these options because, unlike mathematics, where symbols and rules are standardised (for the most part), the symbols and rules in logic vary widely. And I want Deductions to work with a large number of logic systems. But there is some real sense in which choice is the enemy of good, simple design.

Simplifying Choice

How would I improve the Preferences panel? Well, ideally Deductions would adhere to the “pleasant surprise” model – infer what system of logic the user is using from what is entered. But this is not possible for a number of reasons, not the least of which is the program must know which rules are “on” in order to evaluate what the user enters: even if an inference is correct, it can only be marked as correct if the rule is “on.”

Nevertheless, I think the Preferences panel could be improved by not showing so many options on the opening page. Perhaps the General tab could have two or three editing options, along with the “Presets” drop-down menu that pre-configured Deductions for certain logical systems. Then, if the user wants to make further changes, they can use the tabs to further refine the configuration. But the general tab would be relatively simple. This would be something of an analogue to Google’s search box: simplicity up front, power if you drill down.

But there is also one way, it occurs to me, that I could implement the “pleasant surprise” model. In formal logic, there are two common patterns for the negation rules; in the program, I label these Pattern A and Pattern B. Now, the negation tab makes the user choose between these patterns. My thinking at the time was: I have to know which pattern, A or B, the logical system adheres to in order to know how to evaluate the negation rules. Building this flexibility into the program was quite complex, and at the time I was implementing it, I was focussed on getting it working and providing the option to the user. But I now think this was not the best approach.

Having multiple patterns for the negation rules is a good move – it makes the program compatible with that many more logical systems. But how the patterns are presented to the user is not particularly intuitive. By presenting the user with a choice, Pattern A or Pattern B, I require the user to understand the difference between these patterns at the time they are making this choice. Yet, Deductions is geared towards helping people learn: really, you have to already know how natural deduction works in order to make this sort of choice. What Deductions should do default to allowing both Pattern A and Pattern B, and in the Negation tab, give the user the option to turn off one or the other if desired. But by default, the user doesn’t have to know anything about patterns in different logical systems to use the program. At the very least, this is simpler; and it is a lot closer to the “pleasant surprise” model.

A Truly Pleasant Surprise

Regarding the selection of Pattern A or Pattern B for negation rules, the best of all possible worlds would be to have Deductions divine what the user intends. This could be done by making both patterns available at first, but the first time the user uses one of the patterns correctly, assume that that pattern is the one the user intends, and turn off the other possibility. The two patterns are different enough that the number of people who were using a logical system with one pattern would likely never use the other pattern correctly; so it would be more-or-less foolproof. This would get as close to the “pleasant surprise” model as possible. The only thing that stops me from implementing something like this is that I don’t like the idea of clandestinely changing preferences; and popping up a sheet to engage the user about this sort of option, a user who is most likely struggling to deal with a proof at the time, seems like a bad idea.

So, my design goals going forward, at least insofar as preferences are concerned, will be to build a simpler panel: one that has a simple General tab, and has more complexity as you go through the tabs. This will make preferences simple on the surface, without sacrificing power. As for “pleasant surprises,” that is a goal to be aimed at in every aspect of a program.

When I first came to the Mac from the Windows platform, I was amazed at how simple it was to install and remove programs: drag to install, drag to remove. No install routines. No uninstall routines. No dumping huge numbers of files all around the hard drive. It was like a breath of fresh air. But it turns out that this air is not without its drawbacks.

Alexander Limi has posted an interesting discussion concerning problems and possible solutions installing applications on the Mac. This is in response to articles on Daring Fireball, TAUW, OS News, and it all began with Limi’s original post on Improving the Mac Installer for Firefox.

In his latest, Limi proposes the following solution:

1. When download completes, Safari will unpack the disk image, throw away the dmg file, and show a Firefox icon in its download window — as well as selecting it in the Finder in the background.
2. When you double-click the Firefox file, it gives you the options to: (i) move Firefox to the Applications folder; (ii) add Firefox to the Dock; or (iii) set Firefox as your default browser.

Limi’s solution in (1) is to streamline the installation process as much as possible, mainly by giving the user an obvious target and implicitly prompting a click. This doesn’t seem like a bad thing, but I wonder if it goes a bit too far. I think something that is closer to the standard paradigm of a disk image would be better.

I propose the following: Have the dmg pop up the usual window that asks the user to drag the application to the application folder. If the user runs the application from the dmg (the work of detecting this may be done by using M3InstallController), ask if the application should be moved from the disk image. If so, move the application, and then eject and trash the disk image. This gives us the same result as (1). But I think it is better, in that it preserves the “drag from the disk image” behaviour that might be expected from a disk image.

And incidentally, I really do not like (2-ii). I’m not saying it’s not useful or interesting to present such an option to a user. But to me, it seems very Windows, and very not-Mac. There is only one way an application should appear in my Dock: if I drag it there. My Dock is dynamic and constantly changing; not a parking spot for applications that want to market their presence on my machine.

I understand why, in the highly competitive world of browsers, this is a tempting move. I even suspect Safari does this every time there is a browser update. But this doesn’t mean it should be that way. We can easily imagine the slippery slope: today, the Dock; tomorrow, the Desktop; the day after tomorrow, everywhere. And the latter is pretty much where many Windows applications install their shortcuts, today.