Ruby Koans

If anyone is learning Ruby, and wants to become more familiar with various nuances, go download the Ruby Koans.

There are about two dozen files, each discussing a specific topic. You go through each file, looking for __ segments and replace them with statements which would result in true assertions.

After completing a few, you can run ruby path_to_enlightenment.rb and you get the following prompt:

user:~/koans$ ruby path_to_enlightenment.rb 
AboutNil#test_nil_is_an_object has expanded your awareness.
AboutNil#test_you_dont_get_null_pointer_errors_when_calling_methods_on_nil has 
expanded your awareness.
AboutNil#test_nil_has_a_few_methods_defined_on_it has expanded your awareness.
AboutObjects#test_everything_is_an_object has damaged your karma.

The Master says:
  You have not yet reached enlightenment.
  You are progressing. Excellent. 8 completed.

The answers you seek...
  <"FILL ME IN"> expected but was  <true>.

Please meditate on the following code:
  /home/alex/local/ruby/koans/about_objects.rb:5:in `test_everything_is_an_object'

when you lose, don't lose the lesson
your path thus far [.X________________________________________________] 8/280
user:~/koans$

This really helps understand some of the nuances underpinning Ruby.

Code Academy: What's Missing?

Recently, Code Academy launched with the intention to teach computer programming to "the masses".

I'd like to discuss a short-coming in their material (I won't discuss the method used currently).

Someone in their forums has asked^[deadlink] "What topics need new courses the most?"

[NB: apparently code academy has taken down their forums...I guess they couldn't stand the complaints about their EULA.]

I gave a short answer, but it gave me something to think about: what should a programmer know?

Compounding the problem, the material a working coder should know differs from the material constituting an programmer's education.

I'm just going to rattle off items belonging to both categories...

Programmer's Education

The education includes stuff that may or may not be useful when working.

0. Difference between Expressions and Statements. This important distinction is never taught, so students never figure why foo = function() { ... } differs from function bar() { .... }.

1. Algorithms. This topic is not discussed thus far in any course on Code Academy. Being more specific, I mean CLRS-level stuff, not rudimentary "make a loop, do stuff, blah".

Specifically, algorithms that should be covered:

1. Sorting Algorithms
• Bubblesort, as an example of a bad idea;
• Insertion sort
• Mergesort
• Quicksort
• Heap sort
2. Searching Algorithms
• Linear search
• Binary search
• A* search algorithm (and other graph search algorithms)
• etc.

2. Data Structures. Although discussed a little, the Academy does not discuss linked lists, stacks, queues, binary trees, etc.

Advanced data structures might include, but not limited to, Fibonacci heaps, B-trees, van Emde Boas Trees, etc.

3. Dynamic Programming. Both the "Bottom-Up" and "Top-Down" approaches should be discussed; memoization ought to be covered, etc.

4. Greedy Algorithms. This, I feel, is important for pedagogical purposes...greedy algorithms can fail in practice, but it is important to expand your mind.

5. Algorithm Analysis. I learned this in numerical analysis, where we say "Stop: Why does this algorithm work? How can we make it better?"

This cannot be taught on Code Academy, since it would require a nonlinear framework...i.e., actually taking the user's response and generating questions/problems/exercises based off of it.

Think of it as the Socratic method applied to programming. Code Academy cannot handle the Socratic method (perhaps it would not be too far to suggest they are...sophists?).

But seriously: nurturing curiosity in a way specific to the pupil, that's the mark of a good teacher. Code Academy currently cannot facilitate this.

6. Various Rites of Passage. It seems computer science majors have certain "rites of passage": writing an operating system from scratch (or implementing their own file system, process manager, etc., for *nix); writing their own compiler or interpreter; understanding the networking stack; etc.

These should be included in any coder's education...but they require low level languages to do it (assembly or C). Code Academy cannot handle this, at the present moment...

Working Coder's Knowledge

Perhaps one should consult What every CS majors should know...

1. AJAX. Certainly, the most glaring feature missing is AJAX, which I think any browser can handle (the XMLHttpRequest...does it depend on a library?).

2. Runtime, Parse Time, etc. Code Academy does not mention these distinguished times. Nor is there any discussion of "server-side" vs. "client-side", what the difference is, etc.

3. Debugging Techniques. Really, this is most useful, when you run code and cannot figure out what the problem is. What to do?

Well, insert console.log(...) calls indicating what is happening. "I am doing this", "function blah() has been called", etc.

4. How to Optimize Code. I have just written a JavaScript program. Wonderful. It's slow as death. What do I do to make it faster?

Final Thoughts

Certainly many things are missing, but these are my thoughts on the matter of Code Academy and a programmer's pedagogy.

Pseudocode in HTML

So I've been typing up my own notes in html, by hand (like in the bad old days of the internet), and I've discovered some rather interesting behaviour of CSS2.

My pseudocode conventions have composite data structures resemble C's struct, so for example:

struct myDataStructure {
    // code not shown
}

Comments are done in traditional C method too. How to accomplish this using <span> classes? Well, we first specify a class pseudo for pre denoting our pseudocode:

pre.pseudo { } /* pre's pseudocode class */

Now we will investigate each part of pseudocode we want to implement!

Data Structures

I use Plain Old Data Structures in my pseudocode, often writing <span class="struct">myStructName</span> and formatting it as struct myStructName...

/* write a structure as <span class="struct">myStructName</span> */
pre.pseudo span.struct:before {
    content:"struct ";
    font-weight:bold;
}

Functions

My shorthand for the word "function" is always "fn", so this is the class I created. The pseudocode conventions used is simply function doSomething(...), and to implement this:

pre.pseudo span.fn:before {
    content:"function ";
    font-weight:bold;
}

This is my personal convention, but there is also the C-style convention which I'll discuss.

Alternative Function Pseudocode

Some people like writing their function pseudocode to resemble C's ret-type function-name (arg-list), and it is possible to do this:

/* <span class="function" ret="void">foobar</span>() produces "void foobar()" */
pre.pseudocode span.function:before {
    content:attr(ret) " ";
/*
    font-weight:bold;
*/
}

If you prefer the function's ret-type to be bold, you can uncomment the second line.

For Loops

Our trusty for(...) construct is readily implemented:

/* for-loop formatting to write 
   <span="for">i=1; i<j; i++</span>
   be formatted as
   for(i=1; i<j; i++) */
pre.pseudo span.for:before {
    content:"for (";
    font-style:normal;
}
pre.pseudo span.for:after {
    content:") ";
    font-style:normal;
}

It would be nice if I could write <span class="for>...</span> to produce for(...), but I cannot think of a way to do so.

Comments

I end up using the comment convention // my comment which works well on paper, but due to html resizing...it can be problematical. So here's the CSS implementation of the paper-way, and commented out is the traditional C way /* writing a comment like this */.

/* comments are italicized texts beginning with a double slash // */
pre.pseudo span.comment {
    font-style:italic;
}
pre.pseudo span.comment:before {
    content:"// ";
    font-style:normal;
}
/* alternatively uncomment the following to have C++ like comments */
/*
pre.pseudo span.comment:before {
    content:"/* ";
    font-style:normal;
}
pre.pseudo span.comment:after {
    content:" */";
    font-style:normal;
}
*/

Constants

What about constants? For example, I like referring to the null object as NULL, can we do it?

pre.pseudo span#NULL:before {
    content:"NULL";
}

This would require us to write <span id="NULL"/>. This may seem like a waste of time and energy, but when you decide lowercase "null" looks prettier...you have to change only one line of css to get it!

Flaws

None!

No, I'm just kidding, the only problems I can think of is that these <span> classes work only within the <pre class="pseudo"> environment.

So if you were working in the <code> environment...you'd have trouble!

Of course, my pseudocode listings provided are incomplete (conditionals and while-loops are omitted, among other things), but you get the idea how to take advantage of CSS when "typesetting" pseudocode in html.

Lectures on Algorithms

Although I'm devoted to Knuth, CLRS' Introduction to Algorithms is a good read.

Leiserson (the "L" in CLRS) has his lectures [youtube.com] free online. Caution: skip the first 16 or 17 minutes of the first lecture, it's administrative stuff.

The course website is available [mit.edu] thanks to MIT's OpenCourseWare.

The pseudocode appears a little foreign for neophytes (e.g. writing foo←bar instead of foo=bar for assignment). The assignment pseudocode operator actually remains the same across the board...at least, among theoretical computer scientists.

CLRS fixes their pseudocode conventions in their third edition, however; which was published after these lectures were Youtubed.

A personal quibble: array indices for CLRS begin at 1. This annoys me. But it is a misdemeanor, not a felony.

Also, if you are wondering about the difference between big-O notation and big-Theta notation: suppose some algorithm for a computer were Θ(n), then it is O(n). But not all O(n) algorithms are Θ(n) --- there are some rare instances when this is true.

So Θ(n) gives a more strict criteria than O(n), but in practice it's "ok" to mix up notations (since we usually examine worst-case scenarios anyways!).

Addendum: when is it not ok to make this mistake that [f(n)=Θ(g(n))]==[f(n)=O(g(n))] for some f(n), g(n)?

When f(n)<g(n).

However, if g(n)<f(n)<c*g(n) for every n and for some fixed positive integer c, then [f(n)=Θ(g(n))]==[f(n)=O(g(n))]

So if we study the worst case situations, it's okay to mix up big-O and big-Θ notation. The difference occurs when we study the best-case behaviour (which Leiserson calls "bogus"), and possibly when we study the average-case behaviour.

Punch-line: the big-Θ convention is "stronger" than (i.e., implies) the big-O notation, but big-O notation does not imply big-Θ in general.

For studying worst-case behaviour, they are equivalent.

When studying average-case behaviour, we do not know if they are equivalent (it needs to be proven for each algorithm).

When studying best-case behaviour, you are committing fraud: best-case scenarios are bogus.

Ruby on Rails Resources for Beginners

I'll give my overview of "Ruby on Rails" then list off resources for beginners.

Caution: I'm a student, like anyone else, so do not take my notes as the Gospel.

Overview of Ruby on Rails

So the three languages of the internet are: Ruby, Python, and JavaScript. But if you know Ruby on Rails, you will always have a job.

Ruby on Rails is peculiar to get started with (well, for me anyways). What's the basic idea?

Most people end up introducing Rails with some jargon about "MVC" (Model-View-Controller), Don't Repeat Yourself, Convention over Configuration...and from those three slogans alone, you should be able to program Rails applications.

Unfortunately, I am not that smart. So these are some notes to myself as far as what some of these slogans mean!

Imagine a car. People are concerned about how it looks, what color it is, etc. (the "View"). Others are concerned with what's going on under the hood (the "model"), and others worry about how the driver interfaces with the car and the car responds (the "controller").

For us, the Model usually is the data structures used. This is some flavor of ActiveRecord (the API is available online [rubyonrails.org] for the "Base" class).

Great, now what's an "Active Record" and why should anyone give a damn? It's a way of describing the Object-relation mapping (ORM), i.e., encode a SQL database inside a Ruby object. For more about this, see Active Record [rubyonrails.org] for more details.

Lets be clear about this: the model is specified by active records. That's why we care. Got it? Good.

The view is much easier to understand: it's just a chunk of html. That's what the user views.

The controller is more-or-less taken care of, all thanks to the rails library. This is my understanding, at least. I may be completely wrong...

Resources

Several Screencasts [rubonrails.org] are available, and they are quite decent introductions!

You should first Try Ruby before doing rails; since rails is a ruby library...

The best walkthrough describing rails appears in a mere ten step program [tutsplus.com], and I must agree this is the best approach.

I found this YouTube Video (showing how to make a blog under ten minutes) quite enlightening, perhaps you might like it as well?

JavaScript Object Oriented Technique #0 Common Object Methods

Whenever we define a JavaScript class, there are three methods we should immediately define.

toString()

We should be able to return a string representation useful enough for debugging purposes.

We might want to consider adding a static parse() method to our class, parsing a string output from toString() back to object form.

The usual conventions, for objects, is to surround the string by brackets [...] and describe the object's properties within it.

Polygon.prototype.toString = function() {
    return "[Polygon with perimeter "+this.perimeter+", with area "
        + this.area+", centered at ("+this.x+", "+this.y+").]";
}

valueOf()

Typically, we write an valueOf() method to give us a number form of our object.

The textbook example is, since JavaScript number objects are supposedly "real" numbers, then for a complex number object the valueOf() should return the real part. Why? Because it lets us do the following:

var foo = new Complex(1,2);
var bar = new Complex(3,4);
var spam = Complex.sum(foo,bar); // spam is the complex number (4,6)
var eggs = foo + bar; // eggs is the number 4

Also note that the valueOf() method is called when concatenating a string with your object. So continuing from the previous example:

console.log("foo = " + foo); // uses valueOf(), displays "foo = 1"
console.log("foo = " + foo.toString()); // displays "foo = {1,2}"

You have been warned!

Comparison Methods

It's useful to sort objects, and creating comparison methods allows us to do this.

The first one we should consider is equals(), which tests if two objects are equal in some sense. Usually it's if the properties are the same.

Next we need to test for inequalities. We implement a compareTo() method, which should behave as follows:

foo.compareTo(bar)>0; // foo > bar
foo.compareTo(bar)==0; // foo == bar
foo.compareTo(bar)<0; // foo < bar

I suppose the best implementation might have the following skeleton:

MyClass.prototype.compareTo = function(that) {
    if(this.equals(that))
    {
        return 0;
    }
    // else return something like "this.valueOf() - that.valueOf()"
}

Again, it depends on the circumstances...

JavaScript Object Class

JavaScript Object Oriented Framework

JavaScript is fairly quirky (you can learn it at the code academy). It is object oriented, but its a sort of duck typed version.

Every object is really an associative array, so writing foo.bar is the same as foo["bar"]. They are synonymous.

Curiously enough, JavaScript's object oriented framework has a base class called Object. Lets discuss its properties.

Object Properties

What properties does a generic object have?

1. It keeps track of its own constructor, for example:

var foo = new Array();
console.log(foo.constructor === Array); // prints "true"

The instanceof operator checks the value of the constructor property.

2. We can also convert an object to a string by a toString() method.

This does the obvious thing: returns a string representation of the object.

(Actually, if you're a mathematician, you might want to make a toTeX() method...)

3. What about converting an object to a primitive type (well, a primitive type except a string)? We have the valueOf() method.

4. Since we're duck typing objects, we might want to check the properties an object has. We can do this with the hasOwnProperty() method.

It's a function that takes a string, for example "toString", then checks to see if our object has it or not. If our beloved object has it, then foo.hasOwnProperty("toString") returns true.

5. The object base class has a method testing a given property if it's enumerable or not. In other words: it tests if we can use it in a loop construction. This method is called propertyIsEnumerable(). For example:

var foo = { bar:0 };
foo.propertyIsEnumerable("x"); // returns true
foo.propertyIsEnumerable("spam"); // returns false, since foo.spam is undefined
foo.propertyIsEnumerable("valueOf"); //returns false for inherited properties

6. The last method I'll discuss is kind of tricky. The isPrototypeOf() method is similar to the instanceof operator discussed above (see this discussion [StackExchange.com] for more details).

Object.prototype.instanceOf = function( iface )
{
    return iface.prototype.isPrototypeOf( this );
};

Addendum: to find all the properties of the Object class on YOUR system, run the following in your browser's javascript console (however you find that...on Mozilla, it's in the "Tools" part of the browser):

function getAllProperties(object){
    return Object.getOwnPropertyNames(object);
}
console.log(getAllProperties(Object));

/* prints out
[ 'prototype',
  'getPrototypeOf',
  'getOwnPropertyDescriptor',
  'keys',
  'defineProperty',
  'defineProperties',
  'create',
  'getOwnPropertyNames',
  'isExtensible',
  'preventExtensions',
  'freeze',
  'isFrozen',
  'seal',
  'isSealed',
  'length',
  'name',
  'arguments',
  'caller' ] */