This is the first of several articles I’m going to write about the REBOL programming language. To learn more about it, you can visit rebol.com. But my hope is to demystify some of its strengths and weaknesses in a way that their website currently does not, so if you read what I write first then it might help.

(Clear Warning: REBOL is not “free as in freedom” software, and no commitment has been laid out for how the commercial scaffolding which supports its development would be phased out. I know of no published statement that RT would not sue ORCA or other open-source efforts to implement the language. Until these issues are resolved, I consider it only an interesting thing to study and do *not* suggest its use in important projects. While REBOL may rebel against complexity, I think the rebellion for freedom is more fundamental—and the infrastructure we build on is too crucial to be left in the hands of one company that decides who may use a tool and how.)

REBOL is built on the foundational concept of a flexible series, and that’s what I’m going to focus on here. It’s one of the many things that give the language a kind of elegant uniformity. In my article about Computer Languages as Artistic Medium, someone likened it to modeling clay (mold is even a keyword in the language). I thought that might even make a good marketing visual and made a prototype, so keep the words “flexible”, “artistic”, “uniform”, “workable” and “fun” in mind.

Read the rest of this entry »

Not many people have the ability to look at the few fundamental elements of a system (such as constructs of a new computer language) and extrapolate the long-term implications of their use. But rather than jump in and tackle the difficult question of understanding the expressive power and limits of computation, I’ll start by talking about a simpler problem. Don’t panic: it involves crayons and coloring!

This example is going to seem pretty easy on the surface, and you may be familiar with it already. It involves trying to find a way to color in maps so that no areas which share a border are going to be the same color. Here’s an example of a simple coloring with 5 crayons, and then finding a method for doing it with only 4 (taken from Wikipedia’s article on the subject):

Without prior knowledge, the average Joe can only guess at how many crayons he’d need to reliably fill in any map he is given. Just by trying a few cases, he might get an intuition that a small box of different colors will do the trick. But if Joe knew the Devil was going to be presenting him with an arbitrary map and getting his soul if he couldn’t color it properly, he’d probably buy Crayola’s biggest box…120 colors! (Plus, because he doesn’t know for sure that even THAT would be enough, he’d also probably try to round up the discontinued colors off of eBay!)

Yet there is salvation from this kind of paranoia. Early formalisms of the map-coloring-problem from mathematicians comforted us with proof that it *never* took more than 5 different colors…and that 3 will certainly not always be enough. After considerable debate and experimentation over the years, we ultimately found that we only need four unique colors for any map the Devil—or anyone else—makes.

(Note: Depending on your purposes, discovering it was 4 vs. 5 might be somewhat academic. I myself feel that the more crucial step was bringing in math to save us from needing to pack a potentially infinite number of crayons.)

Now…what if the “Devil’s Map” you must solve is instead an arbitrary selection from mankind’s constant creation of new ideas for software? That raises a lot of questions about what a programmer needs in their backpack to be confident they could correctly “color in” any program specification with a working implementation.

Read the rest of this entry »

I somehow tripped across this problem on something called “Monday Math Madness #4″. They mentioned a Rubik’s Cube as a prize, and since some of the stickers are coming off of mine I decided to go ahead and work out the solution. My answer was right, but there were many correct answers so I was not chosen to win the cube… or the Amazon gift certificate. Alas.

Daniel: Hey Quan, we just received a shipment of 25 Macbook Pros from Apple Inc.

Daniel: Don’t worry Quan. The optimal strategy will only take ______ iterations.

First test all laptop groups w/no overlap (5 iterations). Label each computer with its performance rank order in the test.

Remembering which group it came from, test the fastest laptops from each group (marked 1) against each other. This will be the sixth iteration. Label each computer in the group whose laptop won this test “A”, the group whose laptop came in second place “B”, etc.

So each computer should now have a letter and a number. These equations show us what we know so far about their relative speeds:

A1 < A2 < A3 < A4 < A5
B1 < B2 < B3 < B4 < B5
C1 < C2 < C3 < C4 < C5
D1 < D2 < D3 < D4 < D5
E1 < E2 < E3 < E4 < E5
…and…
A1 < B1 < C1 < D1 < E1

We are only looking for 3 laptops. Thus we can exclude all computers labeled D and E as well as those labeled 4 and 5, because there are always three computers guaranteed to be faster than them. So this reduces our consideration to:

A1 < A2 < A3
B1 < B2 < B3
C1 < C2 < C3
…and…
A1 < B1 < C1

By similar logic, we know that B3, C2, and C3 are not in the running…e.g. we cannot choose B3 because the transitive property tells us that B2, B1, and A1 are faster. Narrowing the field to potential winners for the top 3 places we now have:

A1 < A2 < A3
B1 < B2
C1
…and…
A1 < B1 < C1

It is certain that A1 will be chosen, because it is the fastest of the fast. That leaves only 5 candidates for second and third place. So test them all together for the seventh and final iteration [A2, A3, B1, B2, C1]. Take the two top winners from this test along with A1 and you are done.

That is 7 iterations.

Somehow I made it up to 2007 without ever writing code that opened a raw network connection or pulled apart a TCP/IP packet. Naturally, I had some hand-wavy notions of more-or-less what was going on under the hood—in college I took a 400 level CS course based on an old edition of Tanenbaum’s excellent Introduction to Computer Networks. But our homework was all theoretical, and I didn’t delve very deeply into the practicality of what powers our modern Internet.

But this year I was tasked to port some Windows networking code to Linux and OS/X. Looking at what was there, I guessed it was no big deal and said I’d do it. After all…there is a layer of abstraction known as “Berkeley sockets” which is practically identical to the UNIX API for reading and writing files. How hard could it be to recompile that on a new platform?

Though sometimes it might not be that hard, this case turned out to include the functionality of a DHCP server. The Windows version was able to work at the socket level by broadcasting UDP packets to 255.255.255.255, but the OS/X and Linux versions fundamentally couldn’t do it this way. Their semantics are different for how the socket calls are translated into packets.

I want to talk about some of the high-level gotchas to watch out for if you’ve just never run up against these particular dark alleys. Because I’m talking about “weirdness” only, I’m not going to explain basic mundane socket programming—because there are many guides explaining that. (One of the best I found was Beej’s Guide to Network Programming—so check that out if you’re interested.)

Read the rest of this entry »

If you’ve ever looked at a hi-fi component stereo system you’ve probably seen a graphic equalizer. Traditional analog ones look like this one sold by Crutchfield:

Each slider lets you raise or lower the volume of certain sounds in your music. If you know that a flute is in a frequency range of 250 Hz - 2500 Hz, you could make the flute part louder by raising the sliders that corresponded to that range. (As you see from this acoustics chart, frequency ranges for instruments do overlap—so raising a flute can possibly also affect other things like Oboes or vocals.)

Cheaper stereo systems usually only offer “bass” and “treble” knobs. Yet nearly every MP3 player has a digital EQ. Even iTunes has one, if you click Show Equalizer on the View menu:

But here’s a problem: because graphic equalizers break your signals into pieces and then put them together again, they introduce some distortion. There’s a simple way to get a sense that this distortion exists: you can set all the sliders to “flat”… run the equalizer algorithm… and see that you don’t get the same data out that you put in.

As a student back in 1996, I came up with a way you can design a digital graphic equalizer so the algorithm will (nearly) exactly output the original signal when sliders are flat, even after running your audio through a barrage of filtering mathematics. Practically speaking, you would want to bypass the equalizer in that case for performance reasons. Yet there is an alluring elegance to an approach which would converge upon the original signal if you applied it with flat levels… and it strongly suggests you’d have overall less distortion when the sliders weren’t at zero. (This turns out to be true!)

I employ only two digital filters: a specially matched highpass and lowpass. Recursively applying these filters on downsampled versions of the data creates the exact logarithmic bands that are found in graphic equalizers. The process additionally leads to a phenomenon known as “perfect reconstruction”. I explain the details below.

Read the rest of this entry »