A Humble Programmer

最近对Clojure比较感兴趣，写了一个quick sort做测试。

单线程版：

(defn qsort-seq [seq]
  (if (<= (.length seq) 25)
    (selection-sort seq)
    (let [[first-half second-half] (qsort-partition seq 0)
          sorted-first-half (qsort-seq first-half)
          sorted-second-half (qsort-seq second-half)]
          (concat sorted-first-half sorted-second-half))))

多线程版：

(defn qsort [seq]
  (if (<= (.length seq) 25)
    (selection-sort seq)
    (let [[first-half second-half] (qsort-partition seq 0)
      sorted-first-half (future (qsort first-half))
      sorted-second-half (qsort second-half)]
      (concat @sorted-first-half sorted-second-half))))

可以看到两个版本基本是一样的，所以在Clojure里通常可以很快把单线程的程序并行化。下面是一些调用到的函数：

(def random (new java.util.Random))

(defn gen_rand_ints [n]
  (loop [result [], i n]
    (if (zero? i)
      result
      (recur (conj result (.nextInt random)) (dec i)))))

(def values (vec (gen_rand_ints 10000)))

(defn swap [vec i j]
  (let [iv (vec i),
    jv (vec j)]
    (assoc vec i jv j iv)))

(defn selection-sort [seq]
  (defn index_of_smaller [seq i j]
    (if (< (seq i) (seq j)) i j))
  (loop [seq- seq start 0]
    (if (< start (.length seq))
      (let [index_of_smallest_v
            (reduce (partial index_of_smaller seq-)
                    (range start (.length seq-)))
            new_seq (swap seq- start index_of_smallest_v)]
        (recur new_seq (inc start)))
      seq-)))

(defn qsort-partition [seq pivot_index]
  (let [pivot (seq pivot_index)
    pair (loop [i 0, le [], gt []]
           (if (< i (.length seq))
         (if (<= (seq i) pivot)
           (let [le (cons (seq i) le)]
             (recur (inc i) le gt))
           (let [gt (cons (seq i) gt)]
             (recur (inc i) le gt)))
         [(vec le), (vec gt)]))]
    pair))

比较一下两个版本排列10000个数的时间：

(time (qsort-seq values))
(time (qsort values))
(shutdown-agents)

输出

"Elapsed time: 1532.536441 msecs"
"Elapsed time: 1121.529135 msecs"

The first time that I truly appreciated the benefit of automated software testing was when I served as the teaching assistant for CS323 at Yale University, taught by Professor Stanley Eisenstat. If you have read Joel on Software, either the book or the blog, you would have heard of Stan and CS323@Yale a few times.

The title of the course was Introduction to Systems Programming and Computer Organization. The student were taught computer systems, UNIX C programming, and some PERL. To quote Dan Andrei Iancu (from his homepage):

The turning point for many wannabe CS majors at Yale, Professor Eisenstat’s class can easily turn into a marathon of sleepless nights and endless frustration… However, the survivors can claim to have coded (among other things) a fully functional C shell, a Perl server, and an LZW compressor.

The students turned in their assignments by placing the source code under a specific path under their home directories on NFS. Stan gave me a sheet of very specific programming style criteria complete with how much weight to assign to each of the 25 or so items. I would read each solution and grade it for style — and for style only, because there is no way to reliably judge the correctness of a program just by reading it.

To check correctness, I wrote acceptance tests for the assignments. For each assignment, I had a PERL script to compile the students’ solutions and then ran them with STDIN and STDOUT redirected to my script with UNIX pipes. The script then went through each test case, feeding specified input and checking if the output was expected. Stan let me design the final project, which turned out to be a good exercise for writing requirements specification. I asked the students to design an old-school multi-user BBS system. The users would login with a Telnet client and can read, post, and reply with commands. I thought It would be a good practice for multi-threaded programming. Some of the programs turned in by students were quite impressive. I tested all solutions in a similar way, using a PERL script to simulate multiple users in the system and test various functionalities.

Interestingly, the students’ programs also served as tests for my scripts. I usually did the assignment myself and made sure my grading script could properly run my solutions and correctly parse the output, but it is hard to make sure that the script was robust enough to telerate minor differences. Sadly, I was not able to pass all the tests. One student wrote her solutions in Microsoft Word. Of course my script was never ready to parse .doc files. Talk about unexpected user behavior!

Enough history. I will start writing the technical content next time.

To be continued…

This is mostly just note to self, since most Ruby developers probably know this.

The following code snippet:

module TestModule
  def change_name
    @name = "TestModule"
  end

  private
  def private_fun
    puts "private_fun"
  end
end

class TestClass
  attr_accessor :name
  include TestModule

  def initialize
    @name = "TestClass"
  end

  def call_private
    private_fun
  end
end

tc = TestClass.new
puts tc.name
tc.change_name
puts tc.name
tc.call_private

Outputs

TestClass
TestModule
private_fun

It shows that when you include a module, everything is brought into the Class namespace, including private functions and instance variables. Coming from the C++ world, I found this somewhat surprising. This shows one of the practical difference between C++ multiple inheritance and Ruby mix-ins: included modules don’t have its own copy of instance variables, and private functions are visible.