*hypf*

I recently came across the following image:

And I thought it greatly sums up the usual problem. Both users and developers think at vastly different levels of abstraction. To the developer the UI is “just another shell” around the core and most erratic behavior of the UI can easily be explained by the inner workings of another component in the program. To the user, however, the UI is the program. And she just doesn't bother with understanding anything else. For all intents and purposes it's really magic.

Now, above image is a bit small, unfortunately and I didn't find an original creator or a higher-resolution version, so I created a vector version of the image which is attached to this post. Actually, I made two vector versions, one white on black and one black on white, the latter of which should use up substantially less toner when printed:

The font used on the high-res PDFs versions is the free (and pretty) Fontin font.

I attached the Expression Design files as well, if someone wants the “source” files. The Design and PDF files are released into the public domain by me.

The 2009 Summer Scripting Games will open today. I am going to participate and try to golf the entries as well.

Announcements of the events are a bit hard to find, though. I only started today since I didn't know they were already at event 5. But officially they begin today.

My solutions to the individual events can be found in my SVN repository.

Update (2009–08–06): I won a signed copy of Windows Powershell: Step by Step.

NOTE: I do not encourage anyone to use these suggestions for real code that needs to be maintained. I won't take any responsibilities for exploded brains and the like. Although I have to admit, the amount of obfuscation you can do with Powershell with these tips is minimal and in most cases still understandable. Certainly not harder than trying to recognize design patterns in a gazillion lines of Java code.

I am currently playing some sort of code golf with a friend. We're both trying to solve the Project Euler problems (the easier ones, for now, as I am not yet that far) in as little code as possible. He's using Ruby, while I try my best in Windows Powershell.

So probably by not using (or even knowing) Perl or Ruby I am as far as I could get from the whole code golf thing but nevertheless, it's fun and for some solutions he beat me just by mere two or four bytes. But still, he consistently beats me. Now, if only Powershell could lose all those $ for variables or operators as unwieldy and lengthy as -eq or -lt … (although Ruby has similar problems with such horrendously long names like times or inject)

However, I've gained a few insights on how you can still squeeze some bytes out of Powershell scripts by knowing how the shell behaves in certain situations.

Whitespace

The first thing you should do when aiming for as little code as possible is remove all whitespace from the code. This can be done even around operators such as -lt, -eq, -contains, etc. A snippet like $_%7-eq0 is perfectly valid.

Aliases

Take advantage of predefined aliases, such as % for ForEach-Object and ? for Where-Object. Many commands also have very short aliases, should you need them; the command

will list all aliases with a name shorter than three characters.

Booleans

Booleans are cumbersome. Period. Using $true and $false just gobbles up too many characters. You can take advantage of the following implicit conversions to boolean:

So using $b=1 instead of $b=$true is much shorter. In many cases, however, you won't need explicit boolean variables. I'll illustrate this with the following example. Suppose you just want to check whether an array contains a multiple of 7 and take that result to do something else. Then you need a boolean value, somehow. A naïve implementation known from Java or so might look like the following:

This reflects how I have done things at first. I've already omitted all whitespace, but still, this is 32 characters long for returning a boolean. We can rewrite the check for the modulus as !($_%7) since everything zero gets casted to false. This saves one precious character:

Next we can get rid of the helper variable $b altogether, since we can just use the result of the pipeline as a boolean value:

which reduces the length to 16 characters. Half of what we needed at the beginning.

Another thing that tends to come up sometimes is a logical operation of two values, like for example !($a)-or!($b). With De Morgan's laws you can easily rewrite that to !($a-and$b), saving two characters (or even four, if you had -and to begin with).

Powers of ten

Maybe you won't need them often, but sometimes they come in handy. Why write out a number like 10000 or even 10000000 when you can shorten it to 1e4 or 1e7, respectively?

Semicolons

Semicolons separate commands in one line. However, when you are just doing imperative programming crammed into one line it might look like this:

The $s at the end simply drops the variable off the pipeline into the shell so it gets printed. However, you can omit the semicolon directly after a script block:

is perfectly valid and a whole character shorter.

for loops

The for loop in Powershell looks very much like its cousin from C-like languages:

Many times you're probably better of rewriting such a snippet (29 characters) to a pipeline (14 characters):

But sometimes you need a for loop since maybe the terminating condition isn't that simple. I'll take the above example nonetheless. What you can do first here is getting rid of the increment part and pack it into the terminating condition (27 characters):

we need to use the prefix increment since we are comparing $i after the increment (which happens usually at the end of the loop). Unfortunately this messes up the loop since now the start of the loop isn't right. In fact, now we start at $i = 2 because of the additional increment at the start of the loop.

This can be easily fixed, however, by changing the initialization:

What we notice now, however, is that we actually don't need to use the initialization anymore. Variables get initialized to   when they are first used (a fact that we already use with the summation variable $s). So the complete initalization can be removed (23 characters):

And then there is a last small thing with for loops and that is that any trailing semicolons in the loop header seem to be optional. So if we don't need the increment part of the header, we can throw away the semicolon as well:

Down to 22 characters now. Using a pipeline is more code-size-efficient in many cases (see above), but still, the good old for loop can be optimized a bit as well.

Pipeline

Powershell has a very powerful pipeline, based on objects instead of strings which is a great help in many cases. We have already seen that the for loop can be shortened tremendously in some cases by simply using the range operator and piping that array.

Some things lend themselves quite well for pipeline processing. Basically every time you need to do something with the members of an array or a range. For example the following while loop terminates only if $n contains nothing but ones:

Accomplished by a rather small but nice pipeline in an otherwise imperative environment. Some things can be quite cumbersome and long when done imperatively and reduce to very small amount of code when done in a pipeline.

ETA: I have to admit, that by now I have discovered an even shorter way of checking this:

Comparison operators

This is certainly shorter than

and can be helpful in some circumstances. Careful though, in using the result in a boolean context, since the boolean conversion rules are a bit confusing at times.

Select-Object

Select-Object or its predefined alias select is a rather long way of getting the first or last element of a pipeline. Compare

with

for getting the first element of a pipeline. Similarly for getting the last element.

Typecasts

Sometimes they are necessary, for example if you want to treat a string or substring as a number or convert a number to a string. The straightforward approach would be

Not very short. In fact, I try to avoid typecasts whenever possible, at least when trying to write concise code no-one else needs to read. You can, however, take advantage of the fact that Powershell converts operands. So you can just add the neutral element to something you want to convert:

And we just got down the cost of a string typecast to two bytes, instead of eight, and for integers we're also at two bytes instead of five, while a double typecast can be shortened to three bytes instead of eight.

Conclusion

I have presented some techniques for getting Powershell scripts smaller by taking advantage of some mathematical properties, quirks in the Powershell syntax as well as different methods of accomplishing the same goal, sometimes with large differences in code size. Mostly accumulated over the past few days but I'm still learning.

If I find anything new then this list will get updated.

Cellular automata

One-dimensional elementary cellular automata are very simple. You just got a single row of cells which have one of two states: On or Off (0 or 1, living or dead, whatever you want to call it), so they can be nicely represented by a simple two-color bitmap.

States in cellular automata change according to the neighbourhood of a cell in the previous (global) state. Let's say you're a living cell (On, 1) and your neighbours in both directions are dead (Off, 0). Suppose you also have a table that states that your state in exactly this case changes to dead (might happen, maybe you just were too lonely to exist, don't blame me). But in another configuration your left neighbour might still be living and in that case you get to live on. Or in yet another configuration you are a dead cell and regardless what your neighbours are you change state to living.

State transitions

Such a table essentially needs only a few things: State of a cell, state of all neighbour cells (two in this case) and the state of the cell in the following generation. We can visualize this as follows:

In the top row we have a cell with two neighbours, one left, one right, so three cells each. The bottom row gives the following state for each configuration. As you may have noticed, there are only eight possible configurations. And we can impose an order on them as I have done here. And the relevant part, once that order is established is simply a string of eight zeros and ones—so essentially eight bits. We can simply write this rule as a number. What wonderful way of shortening things. This numbering was conceived by Stephen Wolfram, a British mathematician and thus it's called Wolfram code or a Wolfram rule.

The rule pictured above is rule 30.

Display

So we now know that such a cellular automaton might be described by a single number and that it can change states. What good is that?

Well, we might display a certain state of the automaton as a series of either black or white boxes:

and then we might display each of these states below the previous one:

et voila, we got a nice picture. Slightly chaotic, but that's usual for rule 30 and we got some nice recurring triangle formations in there.

So the point of all that was to generate a weird-looking image. Now for the fun part of this. Programming such a beast.

The code

It isn't exactly complicated to do this, so lets start at the top:

We obviously need some control over how much is calculated and rendered. I put a single cell with state 1 in the center of the first row (initial state) so it's advisable to choose an uneven width because many patterns fan out to both sides (as seen above) and then they reach the left and right edge simultaneuosly. Height might be chose for a similar reason, since as the pattern fans out and reaches the sides it gets meaningless pretty quickly.

If the rule is given as the first parameter we only ask for it if it lies outside the permitted range (0–255), else we ask anyway until a correct rule is given.

Following that I wrote a simple subroutine which dissects the numerical rule into its eight parts:

We then initialize the area in which we store the states of each cell for each generation:

Basically we just initialize everything with zero and add a single one in the center of the first generation.

We have a problem with this approach, however, since when states are computed they need a neighbourhood. But how does the neighbourhood look for the first and last cells in each row? At first I simply put another cell to the left and right of the row, containing a zero. This works fine for most rules and we leave it as that for now. How one would implement this I leave as an exercise for the reader.

We might need a subroutine to display the whole area:

As you can see, that are actually two subroutines. They come in handy later.

What is still missing, however, is the calculation of successor states. So let's do that now.

Nothing fancy here, we just delegate the computation of a single cell to another subroutine. As you may note we display the calculated row immediately after we calculated it, this makes the watching experience while the batch file runs a bit less boring as we see a new line every few seconds (yes it is that slow).

Here we calculate the new state for a given cell, by using another helper subroutine which looks up the specific case from the table. We make use of the fact that the configuration of a cell and its neighbours are essentially three-bit numbers and the table is laid out in such a way here that we can access it simply by converting the configuration into a number between 0 and 7. The code for that looks a little ugly, since lots of escaping is needed (I escaped the parentheses just out of fear they might break something, as they often do when nesting structures).

But that was it, essentially. Running the batch without arguments produces the following prompt:

entering, say, 54 in there, yields the following picture:

The actual source code is a bit longer, since I offer an option how the sides of the area are handled (all zero, all one, wraparound and copy, the last of which is now the default which seems the most sensible to me—rules like 169 look very different when calculated with the edges being zero).

I am now working on SVG export from within the same batch file and I hope I found all major bugs by now. But the first working version was just 54 lines long. I think, had I been using Java instead (which was the other choice here), I would have needed significantly more.

UPDATE (2008–12–26 16:21): SVG export is now done and works as it should. At the moment I am mis-using the terminal server in the uni to compute all 256 rules simultaneously:

Recently I discovered that the suggestions that are built into the search bar of Internet Explorer and Firefox expose results from the Google calculator:

So I fired up Fiddler to look where those suggestion requests where going to and found the following URL (for the request 1+1):

http://suggestqueries.google.com/complete/search?output=firefox&client=IE8&hl=en&qu=1%2B1

The answer to that request was a little JSON which looked like the following:

I pretty-printed the output a bit, since it comes out as one long line. As you can see, there are two nested arrays, the first element of the outer one being the search query and the inner one containing the suggestions. If the query was processed by the Google calculator the first element of the suggestions is the result.

Knowing that I hacked together a little program that sends its arguments as a search query to Google and prints the first suggestion (which hopefully is a calculator result):

Mostly I like the ability for unit conversion. Although not everything works. And unfortunately requests for physical constants don't yield a result, which they do, however, when using Google search directly. So that may be an area of improvement.

The program was written in C# 2.0 and uses LitJSON for JSON parsing. It runs on Mono as well, though I haven't tried to build it there, but since it's all .NET 2.0 it should work without problems.

Executable as well as source code is attached.

UPDATE (2008–10–26 00:34): I have updated source and executable as follows:

1. The output encoding is now Unicode (I finally found out how)
2. If no calculator result is returned (i. e. no = as the first char in the first result), then all results are returned. This is mainly to leverage the suggestions as intended and sometimes that can be fun, too:

Aah, recursion, the favorite pet of every programmer. Surely it must be possible to recurse even in Windows batch files (I'm still trying to prove Turing-completeness, by the way :-)).

The first tentative test would be an infinite recursion:

And know what? It works. Well, kinda:

But that's ok, we didn't expect this to do anything useful except of causing a stack overflow. But as we can see, cmd has a stack of some sort and seemingly manages it well enough to allow for recursion.

Time for another test, this time something remotely practical: Factorials. Never mind that those are more easily done with iteration, we want to make sure that recursion works properly:

We need a temporary variable at the end, unfortunately, since cmd does not allow computations inline. But aside from that it looks pretty much how it should. The case for breaking the recursion is also provided in the form of an IF block (sorry, no functional programming niceties, like different function definitions).

But does it work? Oh, sure it does:

And my calculator tells me that those are actually correct. 12! is unfortunately the highest factorial we can compute with it, since we are limited to 32-bit signed integers. A minor bug is still present when using negative numbers, though (infinite recursion, again). This is corrected in the attached version (as well as giving a helpful hint when running the batch without arguments).

Just as a side note, a fun way to implement factorial calculation by leveraging cmd's own “calculator”:

We simply construct the complete term and evaluate that by using SET /A. Nothing fancy, but probably faster than the recursion.

What happened here?

Note, that if you have the parentheses in a variable (such as the 32-bit program files directory on x64 systems), then you need to either use delayed expansion or a subroutine (to avoid the parentheses).

Things to learn from this: The escape character is applicable anywhere in batch files. It causes every character to be recognized as not being part of the syntax.

The Sapir-Whorf hypothesis is an interesting concept in linguistics that basically states that the language(s) you speak affect the thoughts you are able to think and your understanding. Now I read an interesting connection to programming languages by Jeff Moser.

I never thought that this may apply to programming languages as well, but it seems reasonable. Paul Graham notes such a thing as The Blub Paradox where he explains that one's choice of programming language usually determines an opinion towards inferior ones (“How anyone can get anything done with it. It doesn't even have x (Blub feature of your choice)”) and towards more powerful ones (“He probably considers them about equivalent in power to Blub, but with all this other hairy stuff thrown in as well. Blub is good enough for him, because he thinks in Blub.”). Blub is the language the programmer thinks in and it inevitably determines his way of solving problems and judging other tools for solving them.

Probably that's the reason why we (CS students at Uni Rostock) were told that learning programming is not about mastery of one programming language, but rather solving problems in as many languages as possible. To prevent lock-in to one particular language and the thinking connected to it.

That said, I still won't learn Perl :-)

Well, I like UI assistance in the usual ways. Many of you probably know the run dialog of Windows:

or perhaps the address bar:

Both exhibit kind of a text box, merged with a drop down list. In initiated Visual Basic circles called a combo box. The point is to simultaneously allow more text input and selection of a predefined or previously entered value. Usually the list drops down while typing but won't get in the way or steal focus, thus being quite unobtrusive. You can, however, use the arrow down key to select an item from the list. And you can hit Esc any time to close the list again.

Yesterday I stumbled over an example of such assistance gone wrong, from a usability perspective. Eclipse offers something called Content Assist in many places, it is context-sensitive, offers usually only the options that make sense in the current context, etc. In general a good feature and nice to have. Until I tried a simple search and replace through my source code:

Short explanation: I typed the “r()” in the “Find” text box and hit tab to get to the “Replace with” text box. Never mind that the find/replace I attempted there didn't work (as I was doing a regular expression search and parentheses are special characters there) the dialog thought the pressing of Tab to be a good time to display content assistance that not only completely covered the text box I was about to type into, but also managed to provide no obvious way to get rid of it.

My natural reaction was to hit Esc. No good, it closed the dialog completely. I fell into this trap about three times until I actually thought about what I was doing there. Anyway, turns out that the content assistance didn't even have focus, for whichever reason. Thus any input I made went straight to the dialog (hence Esc closing it, ok). Clicking elsewhere in the dialog didn't work either, perhaps for the same reason. I gave up trying yesterday and instead just unchecked the “Regular expressions” check box.

It seems (note: I can only guess) as if Eclipse is trying to display the content assistance for the previous text box, the one where it noticed “Hey, parentheses are special characters, let's display the user some help with them or other common Reg Ex templates”. Hitting Shift-Tab to get to the “Find” text box and then hitting Tab will get you to the list of suggestions. Turns out that even waiting until it appears will get rid of that annoyance, it actually does, but needs a second or two.

The problem is probably that regular expression search and replace is a feature not used by beginners (who perhaps need the assistance most) but rather by people already familiar with it. And those are much more likely to just type away as they already know what they want to search and replace. So waiting until you display that will cause the list to pop up too late in most cases anyway.

Note: I mentioned above that I did the same mistake (hitting Esc) three times before actually realizing what I was doing. Many people that deal with Usability and Interaction Design note the same: The first thing a user attempts when facing something unexpected is to get rid of it as fast as possible. I seems even people who spend the majority of their time with computers aren't any better than those we usually just look upon scornfully.

Seriously, I get some strange referrers from Google. Who the hell gets the idea to clear that from a batch file? I mean, most programs store that kind of stuff either in the registry or in some ugly binary files. The first option is the easier one, at least on Windows 5.1 onwards, since you could use reg.exe. The other part is trickier except the application doesn't mind a missing file.

It works, but reminds me a bit of How do I inflate a bicycle tire with a potato?.