Got slow download but fast upload speeds over wireless? Here's a fix.

If you find that your wireless download speeds are abysmal while your uploads speeds are pretty solid, especially with Apple devices, I've got a possible solution for you. I actually struggled with this issue for a while and decided to write down my findings in a blog post in case I, or anyone else, runs into this in the future.

tldr: disable WMM QoS in your router settings.

Symptoms

At home, I have the following setup:
Whenever I used my laptop or phone, the Wi-Fi connection felt incredibly slow. Youtube videos took forever to load, Google Maps tiles filled in slowly, and even gmail felt unresponsive. On the other hand, my desktop, which was connected to the router via an ethernet cable, worked just fine. 

Numbers

To confirm my observations, I decided to take some bandwidth measurements using bandwidthplace.com, speakeasy.net, and speedtest.net for the laptop and the Speed Test app for the iPhone. The results were pretty consistent across all app and device pairs and looked something like this:

Desktop
  • Download: 24 Mbps
  • Upload: 4.5 Mbps
Laptop
  • Download: 0.65 Mbps
  • Upload: 4.5 Mbps
iPhone
  • Download: 0.58 Mbps
  • Upload: 4.4 Mbps

Yikes! My laptop and iPhone download speed were more than 30 times slower than my desktop's download speed! On the other hand, the upload speed was roughly the same on all devices. What the hell was going on?

Failed attempts

After googling for solutions, I tried a number of tweaks commonly suggested around the web:
  • Change DNS hosts
  • Change wireless channel
  • Change the wireless channel width
  • Use a different security mode (WPA2 personal)
  • Shut off firewalls
  • Enable or disable IPv6 settings
  • Reboot the router
None of these worked. 

The solution

Out of desperation, I started tweaking random settings on my router and stumbled across one that finally worked. The directions for other routers may be a little different, but here's what I did:
  1. Go to http://192.168.1.1 and login to your router. If you've never done this, look for instructions that came with your router or do a google search to find the default username and password.
  2. Find a page that has QoS settings. For the E1200, you need to click on "Applications & Gaming" and select the "QoS" sub-menu.
  3. Disable WMM Support
  4. Click save.
That's it. The second I disabled WMM support, the download speeds for my laptop and iPhone both jumped to 24 Mbps, perfectly matching my desktop. 

What the hell is WMM?

WMM is apparently an 802.11e feature that provides higher priority for "time-dependent" traffic, such as video or voice. In theory, this should make things like VoIP calls and video chat (e.g. Skype) perform better. In practice, having it enabled destroyed my Wi-Fi download speeds. Since I disabled it, my Wi-Fi is blazing fast and I've seen no negative side-effects.

If anyone has more information as to why this would be the case, please share it here.

Update (09/13): some nitty-gritty details

In the last year, this post has had over 100k views and helped many people fix their download speeds. I'm happy I was able to help people. Other folks have been eager to share advice too: I got an email from a Russ Washington in Atlanta who did some impressive investigative work to uncover a potential underlying cause. In case it helps others, here is his email:
Yevgeniy: I ran into your blog post "Got slow download but fast upload speeds over wireless? Here's a fix." I have some info you may find useful. 
This happened to me too when I moved to Comcast - but I had DSL running in parallel. The Comcast traffic had this problem but the DSL did not. Also, it affected my Linksys router when it had stock firmware *and* after switching to DD-WRT. Clearly the traffic itself was at issue, so I broke out the packet sniffer. 
*All* inbound Comcast traffic (Internet --> client) was tagged with a DSCP value of 8 (Class Selector 1). The DSL traffic had a DSCP value of 0. So Comcast is tagging all traffic to be treated a certain way by QoS: "Priority," which sounds good but is actually the second-*lowest* possible. 
WMM, itself a QoS technique, apparently de-prioritizes (drops?) based on the Comcast-supplied value. Turning off WMM worked around it - but since WMM is part of the 802.11n spec, I wanted root cause. Judiciously replacing that set-by-Comcast DSCP value does the trick. 
So between my Linksys router and both ISPs, I had a Netscreen firewall. It lets me set DSCP values by policy - so I told it to match the DSL (DSCP 0). This yielded great improvement. However, I was still not getting full speed so even a zero value was not the best for > DSL rates. I set the DSCP value to 46 (Expedited Forwarding) and bingo, up to 20Mbps, almost full provisioned speed (25Mbps). 
Why only download issues? Because the only Comcast-tagged packets are the inbound ones: Internet --> you, including those big data packets. When uploading, yes, you get sent ACK packets and such - but they are tiny connection-control packets. I imagine WWM weirds out on them too, but you (usually) wouldn't notice when doing multi-Mbps speed tests. 
I am still trying to udnerstand WMM, but this was a big find, and I was lucky to have a firewall that let me packet-tweak. Hope you find the info useful. 
Russ Washington
Atlanta, GA

Seven Languages in Seven Weeks: Prolog, Day 3

After a rocky day 2 of Prolog, I'm back for a 3rd day in my Seven Languages in Seven Weeks series of blog posts.

Prolog, Day 3: Thoughts

Today, I got to see Prolog flex its muscles. After just 2 days of using the language, we were already able to use it to solve two relatively complicated puzzles: Sudoku and eight queens. Even more impressively, the Prolog solutions were remarkably elegant and concise.

I had complained on the previous day that, for simple problems, the Prolog approach did not communicate its intent particularly well. Day 3 turns that completely around. For example, let's check out the 4x4 Sudoku solver in the book. Here's how you run it:

| ?- sudoku([_, _, 2, 3,
_, _, _, _,
_, _, _, _,
3, 4, _, _],
Solution).
S = [4,1,2,3,2,3,4,1,1,2,3,4,3,4,1,2]

And here is the code:

sudoku(Puzzle, Solution) :-
Solution = Puzzle,
Puzzle = [S11, S12, S13, S14,
S21, S22, S23, S24,
S31, S32, S33, S34,
S41, S42, S43, S44],
fd_domain(Solution, 1, 4),
Row1 = [S11, S12, S13, S14],
Row2 = [S21, S22, S23, S24],
Row3 = [S31, S32, S33, S34],
Row4 = [S41, S42, S43, S44],
Col1 = [S11, S21, S31, S41],
Col2 = [S12, S22, S32, S42],
Col3 = [S13, S23, S33, S43],
Col4 = [S14, S24, S34, S44],
Square1 = [S11, S12, S21, S22],
Square2 = [S13, S14, S23, S24],
Square3 = [S31, S32, S41, S42],
Square4 = [S33, S34, S43, S44],
valid([Row1, Row2, Row3, Row4,
Col1, Col2, Col3, Col4,
Square1, Square2, Square3, Square4]).
valid([]).
valid([Head | Tail]) :- fd_all_different(Head), valid(Tail).
view raw sudoku4.prolog hosted with ❤ by GitHub

Even if you don't know Prolog, the code is so eminently declarative and visual, that you can still get an idea of what's going on. We break the 4x4 puzzle down into individual elements, rows, columns, and squares. After that, we just apply some constraints to them: all elements must have a value between 1 and 4 (fd_domain) and the values in each row, column, and square must be different (fd_all_different).

And that's it.

A few lines of code and the Prolog compiler figures out values that satisfy these criteria to get you a solution. Although not an entirely even comparison, take a look at Sudoku solvers I found online in Ruby, Java, and C++. I'm sure each of these imperative solutions could be made prettier; perhaps they are faster; but none of them comes close to the declarative solution in terms of communicating the code's intent.

6x6 Sudoku

Modify the Sudoku solver to work on six-by-six puzzles, where squares are 3x2. Also, make the solver print prettier solutions.

The code:

sudoku6(Puzzle, Solution) :-
Solution = Puzzle,
Puzzle = [S11, S12, S13, S14, S15, S16,
S21, S22, S23, S24, S25, S26,
S31, S32, S33, S34, S35, S36,
S41, S42, S43, S44, S45, S46,
S51, S52, S53, S54, S55, S56,
S61, S62, S63, S64, S65, S66],
fd_domain(Solution, 1, 6),
Row1 = [S11, S12, S13, S14, S15, S16],
Row2 = [S21, S22, S23, S24, S25, S26],
Row3 = [S31, S32, S33, S34, S35, S36],
Row4 = [S41, S42, S43, S44, S45, S46],
Row5 = [S51, S52, S53, S54, S55, S56],
Row6 = [S61, S62, S63, S64, S65, S66],
Col1 = [S11, S21, S31, S41, S51, S61],
Col2 = [S12, S22, S32, S42, S52, S62],
Col3 = [S13, S23, S33, S43, S53, S63],
Col4 = [S14, S24, S34, S44, S54, S64],
Col5 = [S15, S25, S35, S45, S55, S65],
Col6 = [S16, S26, S36, S46, S56, S66],
Square1 = [S11, S12, S13, S21, S22, S23],
Square2 = [S14, S15, S16, S24, S25, S26],
Square3 = [S31, S32, S33, S41, S42, S43],
Square4 = [S34, S35, S36, S44, S45, S46],
Square5 = [S51, S52, S53, S61, S62, S63],
Square6 = [S54, S55, S56, S64, S65, S66],
valid([Row1, Row2, Row3, Row4, Row5, Row6,
Col1, Col2, Col3, Col4, Col5, Col6,
Square1, Square2, Square3, Square4, Square5, Square6]),
pretty_print([Row1, Row2, Row3, Row4, Row5, Row6]).
valid([]).
valid([Head | Tail]) :- fd_all_different(Head), valid(Tail).
pretty_print([Head | Tail]) :-
print(Head),
print('\n'),
pretty_print(Tail).
view raw sudoku6.prolog hosted with ❤ by GitHub

The output:

| ?- sudoku6([1, _, _, _, _, _,
_, 5, _, 2, _, _,
_, 1, 6, _, 5, _,
_, 3, _, 6, 2, _,
_, _, 1, _, 3, _,
_, _, _, _, _, 5],
Solution).
[1,2,3,5,4,6]
[6,5,4,2,1,3]
[2,1,6,3,5,4]
[4,3,5,6,2,1]
[5,6,1,4,3,2]
[3,4,2,1,6,5]

I took the easy way out on this problem, just extending the 4x4 solver to handle 6x6 puzzles with some copy and paste.

9x9 Sudoku

Modify the Sudoku solver to work on nine-by-nine puzzles.

The code:

sudoku(Puzzle, Solution) :-
length(Puzzle, L),
Size is floor(sqrt(L)),
Solution = Puzzle,
fd_domain(Solution, 1, Size),
slice(Puzzle, Rows, Size, 'row'),
slice(Puzzle, Cols, Size, 'col'),
slice(Puzzle, Squares, Size, 'square'),
valid(Rows),
valid(Cols),
valid(Squares),
pretty_print(Rows).
valid([]).
valid([Head | Tail]) :- fd_all_different(Head), valid(Tail).
sublist_length([], _).
sublist_length([Head | Tail], Length) :- length(Head, Length), sublist_length(Tail, Length).
nth0(I, List, Out) :- I1 is I + 1, nth(I1, List, Out).
insert_into_slice(Item, Values, X, Y) :-
nth0(X, Values, Bucket),
nth0(Y, Bucket, Item).
slice_position('row', Size, I, X, Y) :-
X is I // Size,
Y is I mod Size.
slice_position('col', Size, I, X, Y) :-
X is I mod Size,
Y is I // Size.
slice_position('square', Size, I, X, Y) :-
Size_Sqrt is floor(sqrt(Size)),
X is (I mod Size // Size_Sqrt) + (Size_Sqrt * (I // (Size * Size_Sqrt))),
Y is (I mod Size_Sqrt) + (Size_Sqrt * ((I mod (Size * Size_Sqrt)) // Size)).
slice(Puzzle, Slice, Size, Type) :- slice(Puzzle, Slice, Size, Type, 0).
slice(_, Slice, Size, _, I) :- I is Size * Size, length(Slice, Size), sublist_length(Slice, Size).
slice([Head | Tail], Slice, Size, Type, I) :-
slice_position(Type, Size, I, X, Y),
insert_into_slice(Head, Slice, X, Y),
I1 is I + 1,
slice(Tail, Slice, Size, Type, I1).
pretty_print([Head | Tail]) :-
print(Head),
print('\n'),
pretty_print(Tail).
view raw sudoku.prolog hosted with ❤ by GitHub

The output:

| ?- sudoku([_, _, 2, 3,
_, _, _, _,
_, _, _, _,
3, 4, _, _],
Solution).
[4,1,2,3]
[2,3,4,1]
[1,2,3,4]
[3,4,1,2]
| ?- sudoku([5, 3, _, _, 7, _, _, _, _,
6, _, _, 1, 9, 5, _, _, _,
_, 9, 8, _, _, _, _, 6, _,
8, _, _, _, 6, _, _, _, 3,
4, _, _, 8, _, 3, _, _, 1,
7, _, _, _, 2, _, _, _, 6,
_, 6, _, _, _, _, 2, 8, _,
_, _, _, 4, 1, 9, _, _, 5,
_, _, _, _, 8, _, _, 7, 9],
Solution).
[5,3,4,6,7,8,9,1,2]
[6,7,2,1,9,5,3,4,8]
[1,9,8,3,4,2,5,6,7]
[8,5,9,7,6,1,4,2,3]
[4,2,6,8,5,3,7,9,1]
[7,1,3,9,2,4,8,5,6]
[9,6,1,5,3,7,2,8,4]
[2,8,7,4,1,9,6,3,5]
[3,4,5,2,8,6,1,7,9]

With an even bigger puzzle, I finally decided to avoid copy and paste and build something more generic. The code above should be able to solve any NxN puzzle, where N is a perfect square (4x4, 9x9, 16x16, etc).

The approach is the same as before: ensure the values are all in the range 1..N, carve them into rows, columns, and squares, and check that no value in each row, column, or square repeats.

The bulk of the work is done by a rule called slice:

slice([Head | Tail], Slice, Size, Type, I) :-
slice_position(Type, Size, I, X, Y),
insert_into_slice(Head, Slice, X, Y),
I1 is I + 1,
slice(Tail, Slice, Size, Type, I1).
view raw slice.prolog hosted with ❤ by GitHub

The goal of slice is to chop the Puzzle into a list of N sublists. Each sublist represents a row, column, or square (depending on the variable Type) in Puzzle. The slice rule takes one element at a time from Puzzle and uses one of the slice_position methods to put this element into the proper spot in its sublist. For example, here is slice_position for rows:

slice_position('row', Size, I, X, Y) :-
X is I // Size,
Y is I mod Size.

For each element I of Puzzle, we first figure out which row (sublist) it lives in: X = I // Size. The // in prolog is a shortcut for integer division. We then figure out where in that sublist the element belongs: Y = I mod Size. Pretty simple. Squares, however, are a lot more complicated:

slice_position('square', Size, I, X, Y) :-
Size_Sqrt is floor(sqrt(Size)),
X is (I mod Size // Size_Sqrt) + (Size_Sqrt * (I // (Size * Size_Sqrt))),
Y is (I mod Size_Sqrt) + (Size_Sqrt * ((I mod (Size * Size_Sqrt)) // Size)).

To get the math right on this one, I got some help from Hristo. He even posted his reasoning on the Math StackExchange to see if anyone could come up with a formal proof for his formula. Once that piece was in place, the Sudoku solver was pumping out solutions to 9x9 puzzles in no time.

Wrapping up Prolog

Prolog is a fascinating language. If you've done imperative programming your whole life, you really owe it to yourself to try it out. It's a refreshingly different approach to problem solving that will definitely impact the way you think.

I found it particularly bizarre to be manipulating the solution or output to some programming puzzle, even though the solution wasn't yet known! Of course, in Prolog, you're not actually manipulating the solution, you're merely describing and defining it. Sometimes it was easy to invert my thinking this way; at other times, it was brutally difficult, like trying to mentally reverse the direction of the spinning girl illusion.

Unfortunately, much like Io before it, Prolog suffers from the lack of an active online community. You can find some information via Google and StackOverflow, but it's often sparse and incomplete. The documentation is a bit scattered, seems to be written in a very academic language, and is often more confusing than helpful. Worst of all, there are several flavors/dialects of Prolog and the code from one often doesn't work in another.

Having said all that, I have a suspicion that declarative programming is going to grow in popularity in the future (10+ years). Being able to just tell the computer what you want instead of how to get it could provide enormous leverage for programmer productivity and creativity. Of course, I think we'll need a language more intuitive and expressive than Prolog, as well as a smart enough compiler to understand it, but the declarative approach to coding seems like a much bigger leap forward than, say, the whole object oriented vs. functional programming debate.

Onto the next chapter!

Changing gears one more time, head over to Scala, Day 1 to learn about a language that mixes OO and functional programming.

Seven Languages in Seven Weeks: Prolog, Day 2

Today is the second day of Prolog in the Seven Languages in Seven Weeks series of blog posts. You can find the first day of Prolog here.

Prolog, Day 2: Thoughts

Today, Prolog broke my brain. The chapter started with recursion, lists, tuples, and pattern matching, all of which were tolerable if you've had prior exposure to functional programming. However, after that, we moved onto using unification as the primary construct for problem solving, and the gears in my head began to grind.

It took me a while to wrap my head around using unification, but once it clicked, I was both elated and disappointed. I was elated because (a) I often get that way when I learn something new and (b) the book was clearly getting me to think about programming in a totally new manner. However, I was disappointed because even accomplishing something as trivial as adding all the values in a list required a recursive solution that seemed unnecessarily complicated:

sum(0, []).
sum(Total, [Head | Tail]) :- sum(Sum, Tail), Total is Head + Sum.
view raw sum_list.prolog hosted with ❤ by GitHub

The algorithm starts with a base case: the sum of an empty list is 0. We then add a recursive case: the sum of a non-empty list is the head of the list plus the sum of the tail. This isn't too bad once you get used to it, but I find that this sort of code does not communicate its intent well at all. That is, I'm a believer that "programs must be written for people to read, and only incidentally for machines to execute" (Structure and Interpretation of Computer Programs) and this prolog code seems to be the exact opposite. Even for something as trivial as adding the values in a list, I find myself distracted by the need to do pattern matching on the list, recursive calls, and base cases.

In fact, while I have no doubt that the declarative approach is very powerful for certain types of problems, it's not exactly what I expected when I first heard of declarative programming. Conceptually, I thought declarative programming would be all about describing what the solution looks like. From the Prolog I've seen so far, which is admittedly very little, I feel like what we're actually doing is setting up elaborate "traps" to force the unification engine to fill in the proper values for our variables.

As a counter-example, here's how an "ideal" declarative programming might let me define the sum of a list:

sum([a1, a2, a3, ..., an]) = a1 + a2 + a3 + ... + an

To me, the "code" above screams it's intent far more clearly than the recursive prolog solution. An even clearer example comes later in this blog post, where I sort a list using Prolog. While writing this sorting code, I felt like I was playing a game of "how do I setup my rules and atoms to arm twist unification into sorting?" If I had designed Prolog using a coding backwards approach, I would've strived to let the user define a sorted list in a much more natural manner:

sort(list) =
for i in [0..list.length]
list[i] <= list[i + 1]

(Update: turns out it is possible to do something close to this. See the end of the post.)

However, I admit freely that I'm no expert on compilers or language design, so perhaps I'm being naive. Maybe there's no way to define a syntax or compiler that can handle such simple looking definitions in the general case. Perhaps the unification approach in Prolog is as close as we can get and I just need time until my brain gets used to it more.

Prolog, Day 2: Problems

Reverse the elements of a list

reverse_list([], []).
reverse_list([Head | Tail], Out) :- reverse_list(Tail, TailReversed), append(TailReversed, [Head], Out).

Find the smallest element of a list

min([Head | []], Head).
min([Head | Tail], TailMin) :- min(Tail, TailMin), TailMin =< Head.
min([Head | Tail], Head) :- min(Tail, TailMin), TailMin > Head.
view raw min.prolog hosted with ❤ by GitHub

A pretty simple problem, except that there doesn't seem to be a way to do an if/else statement in Prolog. Instead, to handle the possible outcomes of TailMin =< Head and TailMin > Head, I had to use pattern matching and a bit of copy & paste. If anyone knows a more DRY way to do this, please let me know.

Sort the elements of a list

sort_list([], []).
sort_list([Head], [Head]).
sort_list([First, Second | Tail], Sorted) :-
divide([First, Second | Tail], Left, Right),
sort_list(Left, LeftSorted),
sort_list(Right, RightSorted),
merge(LeftSorted, RightSorted, Sorted).
merge(LeftList, [], LeftList).
merge([], RightList, RightList).
merge([LeftHead | LeftTail], [RightHead | RightTail], [LeftHead | Merged]) :-
LeftHead =< RightHead,
merge(LeftTail, [RightHead | RightTail], Merged).
merge([LeftHead | LeftTail], [RightHead | RightTail], [RightHead | Merged]) :-
LeftHead > RightHead,
merge([LeftHead | LeftTail], RightTail, Merged).
divide([], [], []).
divide([Head], [Head], []).
divide([First, Second | Tail], [First | Left], [Second | Right]) :-
divide(Tail, Left, Right).

I implemented merge sort. In retrospect, this seems to somewhat defeat the purpose of declarative programming. That is, instead of describing the solution - that is, what a sorted list looks like - I'm effectively describing the individual steps it takes to sort a list. In other words, this is awfully close to imperative programming.

Unfortunately, I couldn't think of a more "declarative" way of solving this. I initially wrote something similar to a selection sort: it recursively called sort_list on the tail until we got down to one item. At that point, it would use the merge method to arrange the head and tail in the proper order. As we went back up the recursion stack, the merge method would insert the head in the proper spot in the partial sublist. This was obviously less efficient, but at least the sort_list method looked declarative. If only there was a way to define it without a merge step, I'd be in business.

Fibonacci series

fib(1, 1).
fib(2, 1).
fib(N, Out) :- N > 2, N1 is N - 1, N2 is N - 2, fib(N1, Prev), fib(N2, PrevPrev), Out is Prev + PrevPrev.

I ran into two gotchas writing a fibonacci function: first, I had to remember that the recursive calls to "fib" are not really function calls and you can't just directly pass "N - 1" or "N - 2" as parameters. However, when defining N1 and N2, I ran into a second gotcha: you need to use the "is" keyword instead of the equals ("=") sign.

Factorial

fact(0, 1).
fact(N, Out) :- N > 0, N1 is N - 1, fact(N1, Prev), Out is N * Prev.


UPDATE: eating humble pie

Ok, I was wrong. It turns out you can write Prolog code that looks much more declarative and much less imperative. After reading through Day 3 of Prolog, I was a bit wiser, and was able to write the following code for sorting:

sort_list(Input, Output) :-
permutation(Input, Output),
check_order(Output).
check_order([]).
check_order([Head]).
check_order([First, Second | Tail]) :-
First =< Second,
check_order([Second | Tail]).

I'm sure it's not as fast as the merge sort I wrote on my first attempt, but the intent is much clearer: I'm quite obviously describing what a sorted list should look like instead of walking through the steps of how to build one. The recursion and various language quirks of Prolog still take some getting used to, but from a readability perspective, I'm much happier with what I've been seeing since reading Day 3.

Moving right along

Check out Prolog: Day 3 for some more declarative goodness, including an elegant Sudoku solver.

Seven Languages in Seven Weeks: Prolog, Day 1

After finishing up Io, it's time to shift gears yet again in my Seven Languages in Seven Weeks series of blog posts. This time, it's time for something radically different: Prolog.

Prolog, Day 1: Thoughts

The main goals of Seven Languages in Seven Weeks is not actually to teach you seven new languages, but to teach you seven new ways of thinking. In fact, the languages in the book are deliberately chosen so as to represent a wide spectrum of approaches to programming problems.

While the first two languages, Ruby and Io, felt pretty familiar, the third one is a totally different kind of beast. Prolog is my first exposure to declarative programming and definitely a new way of thinking. All the previous languages followed an imperative model: you write code to tell the compiler what to do one step at a time to arrive at some result. In declarative programming, you actually start by describing the result you want and the compiler figures out the steps to get you there.

As an example, consider sorting a collection of integers. In an imperative language, you would describe all the steps of a sorting algorithm:
  1. Divide the collection into sublists of size 1.
  2. Merge pairs of sublists together into a new sublist, keeping the values in sorted order.
  3. Continue merging the larger sublists together until there is only 1 list remaining.
With declarative programming, you would instead describe what the output list should look like:
  1. It has every element in the original list.
  2. Each value at position i in the output list is less than or equal to the value at position i + 1.
And that's it. The prolog compiler would take this description and figure out how to assemble a list that matches your description.

Well, that's the theory any way. After the first chapter, I've only gotten a small taste of this model of programming, so I'm still finding it hard to understand (a) how hard it would be to describe something more complicated than sorting and (b) if the compiler could come up with efficient solutions.

Nevertheless, many of us have been using a (limited, non-turing complete) form of declarative programming for years: HTML. Instead of writing procedural code that instructs the browser how to render the page pixel by pixel, HTML lets you describe what the result should look like and the browser figures out how to render it for you.

Prolog, Day 1: Problems

Books and authors

Make a simple knowledge base representing some of your favorite books and authors. Find all books in your knowledge base written by one author.

Knowledge base:

book(a_game_of_thrones).
book(a_clash_of_kings).
book(the_road).
book(flatland).
book(the_adventures_of_sherlock_holmes).
book(one_flew_over_the_cuckoos_nest).
book(the_hitchhikers_guide_to_the_galaxy).
book(the_restaurant_at_the_end_of_the_universe).
book(life_the_universe_and_everything).
author(george_rr_martin).
author(cormac_mccarthy).
author(edwin_abbott).
author(aurthur_conan_doyle).
author(ken_kesey).
author(douglas_adams).
wrote(george_rr_martin, a_game_of_thrones).
wrote(george_rr_martin, a_clash_of_kings).
wrote(cormac_mccarthy, the_road).
wrote(edwin_abbott, flatland).
wrote(aurthur_conan_doyle, the_adventures_of_sherlock_holmes).
wrote(ken_kesey, one_flew_over_the_cuckoos_nest).
wrote(douglas_adams, the_hitchhikers_guide_to_the_galaxy).
wrote(douglas_adams, the_restaurant_at_the_end_of_the_universe).
wrote(douglas_adams, life_the_universe_and_everything).
view raw books.prolog hosted with ❤ by GitHub

Queries:

| ?- wrote(george_rr_martin, What).
What = a_game_of_thrones ? a
What = a_clash_of_kings
?- wrote(douglas_adams, What).
What = the_hitchhikers_guide_to_the_galaxy ? a
What = the_restaurant_at_the_end_of_the_universe
What = life_the_universe_and_everything

Music and instruments

Make a knowledge base representing musicians and instruments. Also represent musicians and their genre of music. Find all musicians who play the guitar.

Knowledge base:

musician_plays(eric_clapton, guitar).
musician_plays(yo_yo_ma, cello).
musician_plays(jim_brickman, piano).
musician_plays(paul_mccartney, piano).
musician_plays(paul_mccartney, guitar).
musician_plays(jimi_hendrix, guitar).
musician_plays(slash, guitar).
musician_plays(ringo_starr, drums).
musician_genre(eric_clapton, rock).
musician_genre(eric_clapton, blues).
musician_genre(yo_yo_ma, classical).
musician_genre(jim_brickman, contemporary).
musician_genre(paul_mccartney, rock).
musician_genre(paul_mccartney, pop).
musician_genre(jimi_hendrix, rock).
musician_genre(jimi_hendrix, hard_rock).
musician_genre(slash, hard_rock).
musician_genre(ringo_starr, rock).
musician_genre(ringo_starr, pop).
view raw music.prolog hosted with ❤ by GitHub

Queries:

| ?- musician_plays(Who, guitar).
Who = eric_clapton ? a
Who = paul_mccartney
Who = jimi_hendrix
Who = slash

Normalization?

For the books knowledge base, I defined the rules in a "normalized" style as I might use for a SQL database. Looking back at it now, I'm not sure this is the best way to do it. It doesn't seem like I can do anything meaningful with the "normalized" rules other than, perhaps, checking if a given atom is valid.

For the music knowledge base, I only defined the relationships and not any individual atoms. This seems closer to the style in the book and can field the same queries, but with less code. I would hazard a guess that this is the proper way to do it, but I'd love to hear back from anyone who has had more than 1 day of exposure to Prolog.

Day 2

For more Prolog goodness, continue on to Prolog, Day 2.

Seven Languages in Seven Weeks: Io, Day 3

Today is the final chapter of Io in the Seven Languages in Seven Weeks series of posts. You can find the previous day of Io here.

Io, Day 3: Thoughts

Although I'm only on the second language out of seven in the book, a pattern is emerging: day 1 is very basic syntax, day 2 is more advanced syntax, and day 3 shows you some of the advanced applications that set the current language apart from all the others. 

It's a great strategy: each jump is small enough that you can follow along, but big enough that you're able to get a thorough look at the language in just a few days. In fact, my biggest complaint so far is that the examples in the final day of Io are very intriguing, but also very short, so I'm dying to see more.

In a single chapter, we tore through using metaprogramming and concurrency in the span of just a few pages. It was tough to appreciate it all in such a short time. I was able to get a little more practice with Io metaprogramming by implementing a super simple "doInTransaction" method similar to the one I created in Ruby


doInTransaction := Object clone do(
curlyBrackets := method(
"Starting transaction" println
call evalArgs
"Ending transaction" println
)
)
doInTransaction {
"do some first thing" println
"do some second thing" println
"do a third thing" println
}
/*
Starting transaction
do some first thing
do some second thing
do a third thing
Ending transaction
*/
view raw Transactions.io hosted with ❤ by GitHub

The idea was to be able to run some code, such as starting and ending a transaction, before and after a "block" of statements. For added fun, I wanted to be able to support curly braces for defining blocks. Accomplishing both was trivial by taking advantage of the fact that Io treats "{" as the message "curlyBrackets". Handle that message properly in your object, add some basic introspection, and you're done.

Unfortunately, I wasn't able to think of a suitable "toy" example to learn more about coroutines. I'm still fuzzy on a lot of the nuances, such as how memory is shared between the "threads", how many threads there are, and how yield and resume really interact. I'd love to see some more examples, especially those that show a practical use case for Io actors.

Io, Day 3: Problems

Enhance Builder XML

Enhance the XML program (see the original source, the original test file, and the original output) to add spaces to show the indentation structure. Also, enhance the XML program to handle attributes: if the first argument is a map (use the curly brackets syntax), add attributes to the XML program. For example, book({"author": "Tate"}..) would print <book author="Tate">.

This is an awesome example of Io's flexibility and power when it comes to creating DSLs. In some 30 lines of code, Io can process this Builder format:

Builder html(
head(
title("Test webpage")
),
body(
h1("Welcome to my test webpage!"),
div({"class": "content", "id": "main"},
p("Lots of fun to be had!"),
p("Don't forget to sign the guest book")
)
)
)

To produce the equivalent HTML output:

<html>
<head>
<title>
Test webpage
</title>
</head>
<body>
<h1>
Welcome to my test webpage!
</h1>
<div class="content" id="main">
<p>
Lots of fun to be had!
</p>
<p>
Don't forget to sign the guest book
</p>
</div>
</body>
</html>

Most of the (surprisingly concise and elegant) builder source code came from the book. Here's my updated version that handles indentation and attributes:

OperatorTable addAssignOperator(":", "atParseHash")
Builder := Object clone do (
indent := ""
atParseHash := method(
key := call evalArgAt(0) asMutable removePrefix("\"") removeSuffix("\"")
value := call evalArgAt(1)
" #{key}=\"#{value}\"" interpolate
)
curlyBrackets := method(
call message arguments map(arg, self doMessage(arg)) join("")
)
forward := method(
arguments := call message arguments
name := call message name
attrs := ""
if(arguments size > 0 and arguments at(0) name == "curlyBrackets",
attrs = doMessage(arguments removeFirst)
)
writeln(indent, "<", name, attrs, ">")
arguments foreach(index, arg,
indent = indent .. " "
content := self doMessage(arg)
if (content type == "Sequence", writeln(indent, content))
indent = indent exclusiveSlice(2)
)
writeln(indent, "</", name, ">")
)
)
doFile("BuilderNewTest.io")
view raw BuilderNew.io hosted with ❤ by GitHub

The biggest stumbling point was trying to use addAssignOperator in the same file as the test script. This doesn't work: the OperatorTable has already been loaded and can't be changed. By splitting the code into two files, one for source and one for testing, I was able to properly handle the colon and avoid the very frustrating "Sequence does not respond to ':'" error.

Create a list syntax that uses brackets

squareBrackets := method(
call message arguments
)
test := [1, 2, 3, 4]
test println // list(1, 2, 3, 4)

A much easier problem, but another great example of the flexibility of Io: Ruby-like syntax for lists in just a couple lines of code.

Wrapping up Io

This was the last day of Io and I must admit, I'm a bit sad to see it go. It's a beautiful example of just how simple and flexible a language can be. Of course, being able - and tempted - to change just about anything is a bit of double-edged sword: more than once I saw unexpected consequences from overriding the "forward" method. However, it's undeniably powerful. If nothing else, Io has made me more excited to learn about the Lisp family, with Clojure being the 6th language in the book.

I wish I got to see some more examples of concurrency in Io, but the book was pretty sparse in that area. Even worse, I can't find much online. Unfortunately, Io's community is tiny. It's hard to justify spending too much time on a language that, in all honesty, I'll probably never use in any capacity besides learning.

Time for something new

Continue on to Prolog, Day 1, to learn about a radically different style of programming.

Seven Languages in Seven Weeks: Io, Day 2

Today is Day 2 of Io in my Seven Languages in Seven Weeks series of blog posts. You can check out Day 1 of IO here.

Io, Day 2: Thoughts

Day 2 made some huge leaps and bounds over the basic syntax introduced in Day 1. The key learning from this day is that in Io, just about everything is a message sent to an object. There aren't separate semantics for calling functions, using control structures, or defining objects: those are all just objects reacting to some sort of message.

One of the most startling examples of this is the realization that even the basic operators in Io, such as +, -, and *, are actually messages. That is, the code "2 + 5" is actually understood as the message "+" being sent to the object 2 with 5 as a parameter. In other words, it could be re-written as "2 +(5)". The "+", then, is just a method defined on the number object that takes another number as a parameter.

This makes supporting operators on custom objects simple: all I have to do is define a "slot" with the operator's name. For example, here's an object for complex numbers that can be used with the "+" operator:


Complex := Object clone do (
setValues := method(real, imaginary,
self real := real;
self imaginary := imaginary;
self
)
+ := method(other,
result := Complex clone setValues(self real + other real, self imaginary + other imaginary)
)
)
c1 := Complex clone setValues(1, 2)
c2 := Complex clone setValues(3, 4)
c3 := c1 + c2
c3 println
/*
Complex_0x22ee90:
imaginary = 6
real = 4
*/

I found this fairly eye opening. As I think of the syntaxes of other languages I'm used to, such as Java, there are "special cases" all over the place. For example, the "+" operator has special code to handle addition for numbers and String concatenation and nothing else; for loops, while loops, if statements, defining classes, and so on are all special syntax features. In Io, they are all just objects responding to messages.

Io, Day 2: Problems

Fibonacci

Write a program to find the nth Fibonacci number. Both the recursive and iterative solutions are included:


fib_recursive := method(n,
if(n < 3, 1, fib_recursive(n - 1) + fib_recursive(n - 2))
)
fib_iterative := method(n,
prev_prev := 0
prev := 0
sum := 1
for(i, 2, n,
prev_prev = prev
prev = sum
sum = prev + prev_prev
)
sum
)
"-- Recursive Fibonacci --" println
for(i, 1, 10, fib_recursive(i) println)
"" println
"-- Iterative Fibonacci --" println
for(i, 1, 10, fib_iterative(i) println)
/*
-- Recursive Fibonacci --
1
1
2
3
5
8
13
21
34
55
-- Iterative Fibonacci --
1
1
2
3
5
8
13
21
34
55
*/
view raw Fibonacci.io hosted with ❤ by GitHub

Safe division

How would you change the "/" operator to return 0 if the denominator is zero?

(1 / 0) println // inf
(1 / 2) println // 0.5
Number originalDivision := Number getSlot("/")
Number / := method(other,
if (other == 0, 0, self originalDivision(other))
)
(1 / 0) println // 0
(1 / 2) println // 0.5
view raw SafeDivision.io hosted with ❤ by GitHub

2d add

Write a program to add up all the values in a 2-dimensional array.

sum2dArray := method(arr,
arr flatten sum
)
arr := list(list(1, 2), list(3, 4), 5, list(6, 7, 8), 9, 10)
sum2dArray(arr) println // 55
view raw Sum2dArray.io hosted with ❤ by GitHub

myAverage

Add a slot called "myAverage" to a list that computes the average of all the numbers in a list. Bonus: raise an exception if any item in the list is not a number.

List myAverage := method(
sum := 0
self foreach(i, v, if(v type == "Number", sum = sum + v, Exception raise("#{v} is not a Number" interpolate)))
sum / (self size)
)
list(1) myAverage println // 1
list(3, 3, 3) myAverage println // 3
list(1, 2, 3, 4, 5, 6, 7, 8, 9) myAverage println // 5
list(1, "A", 3) myAverage println // Exception: A is not a Number
view raw myAverage.io hosted with ❤ by GitHub

Two Dimensional List

Write a prototype for a two-dimensional list. The dim(x, y) method should allocate a list of y lists that are x elements long. set(x, y, value) should set a value and get(x, y) should return that value. Write a transpose method so that new_matrix get(y, x) == original_matrix get(x, y). Write the matrix to a file and read the matrix from a file.

TwoDList := Object clone do (
init := method(
self lists := list()
)
dim := method(x, y,
self lists preallocateToSize(y)
for(i, 0, y - 1, self lists append(list() preallocateToSize(x)))
self
)
set := method(x, y, value,
self lists at(y) atInsert(x, value)
)
get := method(x, y,
self lists at(y) at(x)
)
transpose := method(
transposedList := TwoDList clone dim(self lists size, self lists at(0) size)
self lists foreach(y, subList,
subList foreach(x, value,
transposedList set(y, x, value)
)
)
transposedList
)
println := method(
self lists foreach(y, subList,
subList foreach(x, value,
if(x == 0 or x == subList size, "|" print)
" #{get(x, y)} |" interpolate print
)
"" println
)
)
toFile := method(name,
File with(name) open write(self serialized) close
)
fromFile := method(name,
doRelativeFile(name)
)
)
list = TwoDList clone dim(2, 3)
list set(0, 0, "A")
list set(1, 0, "B")
list set(0, 1, "C")
list set(1, 1, "D")
list set(0, 2, "E")
list set(1, 2, "F")
transposedList := list transpose
transposedList toFile("transposed.txt")
transposedListFromFile := TwoDList fromFile("transposed.txt")
"2x3 list:" println
list println
"Transposed 3x2 list:" println
transposedList println
"Transposed 3x2 list from file:" println
transposedListFromFile println
/*
2x3 list:
| A | B |
| C | D |
| E | F |
Transposed 3x2 list:
| A | C | E |
| B | D | F |
Transposed 3x2 list from file:
| A | C | E |
| B | D | F |
*/

Guess Number

Write a program that gives you ten tries to guess a random number from 1-100. Give a hint of "hotter" or "colder" for each guess after the first one.

// Can't use Random due to http://stackoverflow.com/questions/3481651/how-do-i-import-an-addon-in-the-io-language
// toGuess := Random value(100) ceil
// A random number as per http://xkcd.com/221/
toGuess := 4
guessCounter := 0
previousDiff := nil
currentDiff := nil
while(guessCounter < 10,
guessCounter = guessCounter + 1
currentGuess := File standardInput readLine("Enter your guess: ") asNumber()
currentDiff := (toGuess - currentGuess) abs
if(currentDiff == 0) then (
guessCounter = 10
) else (
if (previousDiff == nil) then("Try again" println) elseif(currentDiff == previousDiff) then ("You just guessed that!" println) elseif(currentDiff < previousDiff) then ("Hotter" println) else("Colder" println)
previousDiff = currentDiff
)
)
if(currentDiff == 0, "Correct!", "Sorry, you ran out of guesses.") println
view raw GuessNumber.io hosted with ❤ by GitHub

On to day 3!

Continue on to day 3 of Io here.

Seven Languages in Seven Weeks: Io, Day 1

Welcome to the first day of Io in my Seven Languages in Seven Weeks series of blog posts. After spending a few days playing around with Ruby, Io is definitely a change of pace.

Io, Day 1: Thoughts

From what I've seen so far, Io is a prototype-based language (similar to JavaScript), with extremely minimal syntax (none of Ruby's syntax sugar), objects are just a collection of "slots" that contain either data or methods, and you interact with objects by passing them messages. To give you a taste, here are some snippets:

We'll start with the classic Hello World:

"Hello, world!" println
view raw HelloWorld.io hosted with ❤ by GitHub

The way to think about this in Io terms is that you are passing the "println" message to the "Hello, World!" String object. I must note that having a space between object and message makes the code noticeably harder for my mind to parse. If the code had used a dot instead - "Hello, World!".println - I would've found it much easier! As it is, perhaps because I'm not used to it, my comprehension is slowed and my aesthetic sense is tingling.

Here's a simple example of defining variables and methods:

speak := method(text, text println)
phrase := "Hello, world!"
speak phrase // Hello, world!

Method calls look similar to most languages I'm used to: "method param1, param2, ..." However, I wonder if the Io way of looking at it is that the speak method is an object and the phrase parameter is the message?

Finally, here's an example that shows objects and prototypal inheritance:

Animal := Object clone do(
speak := method(phrase println)
description := "A living creature"
)
Dog := Animal clone do (
phrase := "Woof!"
)
Cat := Animal clone do (
phrase := "Meow"
description := "I can haz Io?"
)
myDog := Dog clone
myCat := Cat clone
myDog speak // Woof!
myDog description println // A living creature
myCat speak // Meow
myCat description println // I can haz Io?

In prototype-based languages, the distinction is blurred between a "class" - that is, some sort of template defining an object and its behavior - and an "instance" of that class. In Io, they are pretty much one and the same: you just clone an existing object to create a new one, whether you intend them as instances or templates.

The one place where "instances" do differ from "classes", however, is by convention: the class-like objects are usually named with an upper case first letter (Dog, Cat) while the instance-like objects are named with a lower case first letter (myDog, myCat). I suppose this sort of design greatly simplifies the language, as there's no need for special syntax, constructs, or rules for "classes".

Io, Day 1: Problems

The day 1 problems in this book are always very basic. I skipped a few of the really simple ones as they are not too interesting.

Io typing

Evaluate 1 + 1 and then 1 + "1". Is Io weakly or strongly typed?

1 + 1 // 2
1 + "1" // Exception: argument 0 to method '+' must be a Number, not a 'Sequence'

As you can see above, Io is a strongly typed language.

Dynamic code slot

Execute the code in a slot given its name.

TestObject := Object clone do(
foo := method("you called foo" println)
bar := method("you called bar" println)
baz := method("you called baz" println)
)
TestObject getSlot(System args at(1)) call
/*
> io DynamicCodeSlot.io foo
you called foo
> io DynamicCodeSlot.io bar
you called bar
> io DynamicCodeSlot.io baz
you called baz
*/

Explanation: the "System" object contains various system properties and methods. I pass the "args" parameter to it to get the command line parameters. I then use the "at" method to access the parameter at a given index: in Io, index 0 has the name of the app (DynamicCodeSlot.io) and index 1 is the first argument (foo or bar).

By calling the "getSlot" method, I get back the object stored at the slot named as a command line argument. Finally, the "call" method does what you'd expect: it calls that slot.

Io, Continued

Continue on to Io, Day 2.