Dart Koans

The next week or so, I'm going to be limited in the amount of time I will have for some programming. I will hopefully still get some programming in but I will be limited in how much time and frequency I will have for it. Because of that, and the fact that I'm a little impatient, I've decided to share some information on my current project.

The project is Dart Koans. It is inspired, though not based on, a ruby project of a similar name: Ruby Koans. I completed the Ruby Koans when I was first learning Ruby, having come from other similar languages like Python as well as from JavaScript. The Koans helped a lot because I learn really well from hands-on coding. Additionally, while covering the basics, it does dive right in.

I felt that a similar approach to learning Dart would be a great contribution to the community. There are many programmers coming in from other languages who are comfortable with the basic concepts and don't need some of the background or theory involved with traditional tutorials. They're familiar with what a variable is, and just want to know how they're used in Dart. They're itching to write some code in Dart to see how it feels.

The Dart Koans are for people new to Dart, and comfortable on the CLI (currently it's not recommended to run from the Dart editor, as it's blocked by a couple of bugs.
1) Issue 4654 (Dart Editor should handle ANSI color output).
or
2) Issue 2789 (Provide a way to find out if stdout is connected to a terminal).

The idea behind Dart Koans is that you achieve enlightenment through failure. You start with many failing tests. And individually correct each test and re-run the program. With each run of the application you should get closer and closer to resolving all tests. Each test introduces a new concept of the Dart language or libraries. At the moment it is still very very early and only a small portion of the total tests are completed. Currently there are 55 tests. By the time this is completed I expect well over 300 or more. As each test fails it will provide the error, line and file to look at to correct the issue. Each test (using the unittest library) is accompanied by several comments which will provide information about the concept being introduced.

Due to the early development stage, the tutorial is currently very much in the preview stage and far from its completed form. However I intend to add more tests and areas as much as I can. I'm interested in any feedback or comments or concerns but please keep in mind things are very much subject to change. Current output is primarily for demonstration purposes and is most likely not the final result.

Because I will be updating very frequently I will not be making many blog posts about the projecct unless its regarding a significant milestone or involves any major changes to the project.

Resort to sort

So the past few days I've been playing around with some simple algorithms. I'm not 'professionally' trained, and most of my experience has been with what I've seen in code or have implemented myself. Does that make me less of a developer for not being classically trained? Maybe, maybe not.

In particular I've been playing around with some of the sorting algorithms. Stuff like Bubble sort, Selection sort, Insertion sort, and of course Quicksort.

My first task as been to study the algorithm and look at whatever pseudo-code or explanation is presented for the algorithm. Study and understand it. Then is to walk away from any computer or anything, take a little break. After a short time I then pull out a pen and paper and write down a Dart version of the code. I write it out in front of me without referring to APIs, or without referencing the material.

I later then enter that code (or re-write it) into the Dart editor in a simple test file I have. I run it, fix my bugs, and run it again. My test file contains all of the various sorts as I learn them, it then prints out the sorted list and the time it took to complete (using a Stopwatch). I also have a function to create a list of X size filed with values from Random.nextInt.

Being able to easily create a random list of a determined size is nice, as it allows me to easily increment the list size as I choose and see the differences in performance. For instance it took a list of almost 5000 items for Quicksort with the two isolates to be faster than the main-thread version of Quicksort. (See Edit note below)

Many of the algorithms I've implemented are without performance improvements and are far from the most efficient versions available. One thing I've noticed though is List.sort((a, b) => a - b); has generally been one of the best performing algorithms, in lists of up to 10,000 items.

However as I mentioned none of the algorithms has been tuned for best performance or memory usage and are just the 'simple' versions of the algorithms just for my own learning purposes and less for actual performance comparisons. The performance comparisons are more of a visual reference to the Big O Notation for myself.

[Edit:]So I was wrong. I had poorly implemented my Quicksort with Isolates. Very poorly. It was a hodgepodge of Futures and a custom callback. I went through and cleaned it up and changed it so it returned a Future instead of calling a callback. Once I did that I saw an over 10x speed increase in the Quicksort with Isolates version and it and was about the same speed as the Main-threaded Quicksort for lists below 500 items. And faster for lists greater than 500 items. This has more to do with my unfamiliarity with Isolates than with the algorithms themselves.[/Edit]

For those who may be interested, you can the current version of the file here: https://github.com/butlermatt/sorting_dart. As time goes by, I will be adding more algorithms (with comments) as I learn them myself. Again please recall these are not optimized in any way and are only presented as-is, as proof of concept.
In time I may add some optimized versions of algorithms myself as I progress. Keep in mind however this is primarily a learning project and not designed for use. They may be (and are) buggy.

Contributed Contributions

So it has been quite some time since my last post. Today will be a relatively short one, but I think I'm going to try and get into the habit of writing a blog post now and then.

Today I wanted to mention a little about contributing back to Dart. This is something very easy for anyone to do, on a variety of different levels. First and foremost, I've been contributing in small ways in the past just by using Dart. And in particular by using Dart and filing bug reports when you run into something. Currently I have 15 bug reports that I have reported and are still open. And many more which have been fixed for a long time.

You can submit bug reports for not only code that isn't working correctly, but also for documentation which may need to be updated or corrected; for updates to the website; or even just style recommendations (particularly those which may apply to the Style Guide).

Bug reports are a great way to contribute as the more bugs that are found and squashed the more stable and attractive Dart becomes.

Eventually you may start feeling comfortable enough to provide solutions to the bugs you provide. Either pasting in a suggestion into the bug report, or by submitting a patch.

Note: I will mention this here ahead of time. Before Google can integrate any code you provide them, you must sign the Contributor License Agreement (CLA).

I have personally submitted patches to a number of areas of the Dart project. My first was to the dartlang.org website. I found a typo in the language tour. So I went to GitHub site. Found the Dartlang/dartlang.org repository and forked it. I made the edits that I saw needed to be corrected and issued a pull request.

One handy tip I received, was to use a rebase workflow when dealing with edits to the github repositories. After doing a bit of searching around, a very good article I found was A Git Workflow for Agile Teams. This shows a very straight forward method of using rebase to create nice clean commits when pushing upstream. I still refer to it when working on patch for the sites.

After submitting a couple of corrections to the dartlang.org site(s) I began to feel comfortable enough with submitting code to the dart source code. This process is significantly different than just forking a github repository. First instead of using github, its best to follow the steps here for getting the source. Make sure you can build before trying to edit any code.

Once you've verified you can build after getting the source code for the first time. You can go ahead and make your changes. After making your changes, make sure you once again build. Then also make sure you can pass the tests. If possible run as many tests as you can, not just specific to one area as you never know what else might rely on behaviour you didn't expect (I found this out the hard way myself).

If everything looks good with the test. Submit your patch. I'll give you a hint now as well. Once the patch is uploaded, it will display a chromium code review site. Similar to: https://chromiumcodereview.appspot.com/10918056/ Be sure to go to that site. Edit the issue and add a reviewer (if you're not sure who should review ask in either the bug report that you're working on or from the mailing list). Update the issue once you've added a reviewer. Then click on 'Publish+Mail Comments'. If you don't do this, no one will know that your patch is waiting for review!!! (Mine waited over a week because I didn't do this haha).

Once your patch is looked at, you will usually get a 'lgtm' (Looks good to me) and possibly some suggestions on small typos to fix. If you get line comments on things to fix, then fix them in your code, then re-upload a patch (using the same method as before). It will automatically associate it with your previous patch (as long as you're using the same git branch!). Then go to the comments in the source that were left for you, click on each. Then click on the 'Done' link. That will signal to the reviewer that you looked at each comment and addressed the issue. Once you've marked each comment as 'Done', then 'Publish+Mail Comments' again.

Usually by this point the reviewer will commit your patch for you into the source. They will usually link another patch ID, and on that patch ID will be a revision id such as https://code.google.com/p/dart/source/detail?r=12278. Once you have that you can also watch the buildbot progress for your patch to see if you end up breaking anything ;)

So that's a summary of how I have, and you can, contribute to Dart. Now get out there and enjoy it!