Maniagnosis

An apology

2013-05-16T20:00:00.000-05:00

If you have been viewing this blog recently and have been redirected to some advertisement site like search.goodcarquotes, or had a pop-up, or seen the Clicksor ads in the left bar, I would like to apologize. I had noticed them myself before, and finally took the time to track them down. It seems the Sociable gadget (that showed submit-this-page-to-various-social-networking-sites buttons) is bad. I have removed it, and I hope I've cleaned up the situation.

Thanks to Nitecruzr on the Google product forums for the answer. (Note that the specific advice is only applicable to my layout.) For reference, see Blogger Blogs Being Hijacked By The Sociable Gadget.

Quote o' the day: Do what the moody guy on the Ducati does

2013-05-16T12:04:00.000-05:00

In a sub-thread on Reddit about the advantages of IntelliJ vs. Eclipse, Moerderhai wrote,

...So I tried this Intellij thing that the moody guy who rode a Ducati really liked....

Moerderhai was then enlightened, he found a chickadee that laid golden eggs, rainbows and unicorns began wandering through his cubicle, and so on.

(I don't know why I found this amusing.)

Link o' the day: A flashback

2013-05-02T11:05:00.001-05:00

I ran across this recently. Apparently, Larry Loucks passed away back in 2006.

Computer Business Review, June 23, 1995: IBM SHIFTS EMPHASIS OF WORK ON MICROKERNEL.

I've got no idea what "Instead, it has been prototyped further down in the kernel, where performance gains of up to 1,000 times have apparently been achieved" is supposed to mean, and the IBM microkernel was hardly a clean-room effort; it was based on the Mach kernel from CMU. But still, I was there! That's where I spent a formative year or so of my life.

And the performance of the IBM microkernel was really, really horrible.

Link o' the day: Brian Kernighan on the Elements of Programming Style

2013-04-28T21:32:00.000-05:00

Brian Kernighan, co-creator of AMPL, gave a talk on the Elements of Programming Style in 2009 at the Institute for Advanced Study. The hour-long video is well worth a watch, although you should beware of the fire alarm at about 58 minutes.

Kernighan, who now teaches at Princeton, continues the format of the original Elements of Programming Style by examining unsavory code found in the wild, either in programming textbooks or real-life software, but with up-to-date examples. Among the other, less interesting, points, at about 11:48 bwk indicates that he does not know how strpbrk should be pronounced.

Does anyone reading this know what C (at 28:00) and C++ (43:45) books he is talking about? Those examples are horrible.

Operator overloading in Rust

2013-04-26T18:32:00.000-05:00

Rust offers several features that may make frustrated C++ programmers feel more at home. One of those features is operator overloading, for at least some common operators. The technique of overloading operators in Rust is handled through traits: the Rust manual describes overloading by saying, "[arithmetic operator] expressions are syntactic sugar for calls to built-in traits, defined in the core::ops module of the core library. This means that arithmetic operators can be overridden for user-defined types." So, how does one use these built-in traits?

Let's say you want to use complex numbers in your code, because you are the kind of person who knows what complex numbers are good for and can use them in a safe and appropriately sanitary fashion. Complex numbers, for those of us who do not know what they are good for and probably cannot use a spatula in a safe and sanitary manner, are an extension of more commonly seen sets of numbers such as integers and real numbers, and pair a real number and an imaginary number. An imaginary number, to back up a bit, is a multiple of a number $i$ whose square is -1, so a complex number is expressible as $a + bi$, where $a$ is the real component and $b$ is the imaginary component, multiplied by $i$, the imaginary unit. The complex number system provides at least one root for every polynomial expression in much the same way that real numbers provide a value for every division, unlike the integers. Or at least that is the impression that Wikipedia gives me. Thank you, great Wiki!

In any case, this is what a complex number looks like in Rust, at least according to me.

struct Complex {
    r : float,
    j : float
}

(In the code, $i$, the traditional notation for the imaginary unit, is replaced by j by suggestion of englabenny and dfjkfskjhfshdfjhsdjl on reddit, because "1i" is the Rust notation for 1 as an int and because "i" is associated with current in various disciplines that commonly use complex numbers.)

This is a structure containing two fields, the real component and the imaginary component. float is the Rust machine-dependent floating point type, and represents the largest floating point type preferred on the target hardware. (Alternatively, f32 and f64 are the 32- and 64-bit machine independent floating point types.)

To overload the operator + for complex numbers, just provide an implementation of the Add trait:

impl Add<Complex,Complex> for Complex {
    fn add(&self, rhs: &Complex) -> Complex {
        Complex {
            r : self.r + rhs.r,
            j : self.j + rhs.j
        }
    }
}

The Add trait contains one method, add, that performs the operation. To unpack the impl line, implementing Add<X,Y> for Z for types X, Y, and Z would provide an implementation of the operation where the left-hand side was a Z (the receiver of the method and the type for which the trait is being implemented), the right-hand side would be an X (the argument to the method), and the result would be a Y. This implementation allows two complex numbers to be added, producing a new complex number.

One thing I would like to be able to do is to provide multiple implementations of the Add trait, such as:

// impl Add<float,Complex> for Complex {
//     fn add(&self, rhs : &float) -> Complex {
//         Complex { r : self.r + *rhs, j : self.j }
//     }
// }

This implementation would allow floating point numbers as the right-hand side, producing a complex result. Unfortunately, the current Rust trait implementation does not allow that, complaining about conflicting operations.

complex.rs:52:0: 56:1 error: conflicting implementations for a trait
...
complex.rs:24:0: 28:1 error: conflicting implementations for a trait
...
complex.rs:81:12: 81:17 error: multiple applicable methods in scope
...

Something to look forward to in future releases.

With that said, the following code now works and produces the expected results:

    let x = Complex { r : 1.0, j : 0.0 };
    let y = Complex { r : 3.0, j : 0.0 };
    let z = x + y;

Two further examples implement subtraction and multiplication for Complex values.

impl Sub<Complex,Complex> for Complex {
    fn sub(&self, rhs : &Complex) -> Complex {
        Complex { r : self.r - rhs.r, j : self.j - rhs.j }
    }
}

impl Mul<Complex,Complex> for Complex {
    fn mul(&self, rhs : &Complex) -> Complex {
        Complex {
            r : (self.r * rhs.r) - (self.j * rhs.j),
            j : (self.r * rhs.j) + (self.j * rhs.r)
        }
    }
}

Isn't that just lovely, hmm?

The operators which can be overloaded, as of Rust 0.6, are:

Operator	Trait
Arithmetic
+	core::ops::Add<RHS,Result>
-	core::ops::Sub<RHS,Result>
*	core::ops::Mul<RHS,Result>
/	core::ops::Div<RHS,Result>
%	core::ops::Modulo<RHS,Result>
- (unary negation)	core::ops::Neg<Result>
Bitwise
&	core::ops::BitAnd<RHS,Result>
\|	core::ops::BitOr<RHS,Result>
^ (exclusive or)	core::ops::BitXor<RHS,Result>
<< (shift left)	core::ops::Shl<RHS,Result>
>> (shift right)	core::ops::Shr<RHS,Result>
Comparison
==	core::cmp::Eq
!=	core::cmp::Eq
<	core::cmp::Ord
>	core::cmp::Ord
<=	core::cmp::Ord
>=	core::cmp::Ord
Miscellaneous
! (Boolean negation)	core::ops::Not<Result>
a[i] (indexing)	core::ops::Index<RHS,Result>

In order to preserve sanity, Rust limits operator overloading. As kibwen pointed out in the reddit discussion, there are restrictions on where traits, types, and the implementations of traits for types can legitimately appear. Specifically, the implementation must be in the same crate as either the type or the trait. kibwen writes,

Now note that the overloading traits are defined in libcore, which is shipped with the Rust compiler.

The implication then is that it is only possible to overload operators on types that you've defined yourself. You never have to worry about library A attempting distant overloads on types from library B; this also means that you never have to worry about libraries changing what 2+2 means.

At this point, I must note that operator overloading, even with Rust's limits on it, is not something to be used without considerable thought. If you misuse overloading, doing something like C++'s 'cout << "hello world"', a Rust developer will find you. And Fix. Your. Little. Red. Wagon.

Going further with complex numbers

Complex numbers have two specialized operations that are useful to me here: conjugation, which negates the imaginary component, and magnitude, which computes the distance of a complex number from the origin of the complex number plane. (The magnitude is the closest I can come to a meaningful way of down-converting from a complex number to a floating value.)

impl Complex {
    fn conjugate(&self) -> Complex { Complex { r : self.r, j : -self.j } }
    fn magnitude(&self) -> float { float::sqrt( self.r * self.r + self.j * self.j ) }
}

This implementation provides conjugate and magnitude methods for the Complex structure; think of it as the implementation of an anonymous trait. One thing we need the conjugate method for is implementing division for complex numbers:

impl Div<Complex,Complex> for Complex {
    fn div(&self, rhs : &Complex) -> Complex {
        let rhs_conj = rhs.conjugate();
        let num      = self * rhs_conj;
        let denom    = rhs * rhs_conj;
        Complex {
            r : (num.r / denom.r),
            j : (num.i / denom.r)
        }
    }
}

Speaking of traits, ToStr is a trait supported by most Rust types, converting a value to a string.

impl ToStr for Complex {
    fn to_str(&self) -> ~str { fmt!("(%f + %fi)", self.r, self. i) }
}

For Complex, to_str will produce a string of the form "(a + bi)". One further thing that I would like to be able to do is to convert other values, such as float's into Complex numbers.

trait ToComplex { fn to_complex(&self) -> Complex; }

impl ToComplex for float {
    fn to_complex(&self) -> Complex { Complex { r : *self, j : 0.0f } }
}

That trait and implementation adds a to_complex method to any float value, such as 3.0f.to_complex().

There is a standard trait for converting among numeric types in Rust, NumCast. This is the implementation of it for Complex numbers:

impl NumCast for Complex {
    fn from<N:NumCast>(n: N) -> Complex { n.to_float().to_complex() }

    fn to_u8(&self)    -> u8    { self.magnitude() as u8    }
    fn to_u16(&self)   -> u16   { self.magnitude() as u16   }
    fn to_u32(&self)   -> u32   { self.magnitude() as u32   }
    fn to_u64(&self)   -> u64   { self.magnitude() as u64   }
    fn to_uint(&self)  -> uint  { self.magnitude() as uint  }

    fn to_i8(&self)    -> i8    { self.magnitude() as i8    }
    fn to_i16(&self)   -> i16   { self.magnitude() as i16   }
    fn to_i32(&self)   -> i32   { self.magnitude() as i32   }
    fn to_i64(&self)   -> i64   { self.magnitude() as i64   }
    fn to_int(&self)   -> int   { self.magnitude() as int   }

    fn to_f32(&self)   -> f32   { self.magnitude() as f32   }
    fn to_f64(&self)   -> f64   { self.magnitude() as f64   }
    fn to_float(&self) -> float { self.magnitude()          }
}

With that addition, I can write the following main:

fn main() {
    let x = Complex { r : 1.0, j : 0.0 };
    let y = Complex { r : 3.0, j : 0.0 };
    let z = x + y;
    let w = NumCast::from(2);
    println(( y + 3.0f.to_complex()   ).to_str());
    println(( x * NumCast::from(3.0f) ).to_str());
    println(( x * NumCast::from(4)    ).to_str());
    println(( z / w                   ).to_str());

    let n = Complex { r : 0.0, j : 1.0 };
    println(( n * n                   ).to_str());
}

Which produces the following output:

(6 + 0i)
(3 + 0i)
(4 + 0i)
(2 + 0i)
(-1 + 0i)

The source code for these examples in on github.

I would like to thank the commenters from Reddit, particularly englabenny, dfjkfskjhfshdfjhsdjl, and kibwen, for their help.

Letterpress cheating in Rust: Parallelism part 2

2013-04-16T20:30:00.000-05:00

Last time I wrote, "Or, how to turn an 8 second runtime to a 27 second runtime by throwing a stack of CPU's at it", but I did not actually describe that case. It turns out that the second option for parallelizing the anagram program is the way to do that. As a reminder, the second option is:

Have each of the $N$ tasks get its own copy of the complete dictionary. The main task then sends each request computed from the input letters (30,000,000 queries, remember) to one of the tasks, which accumulates a subset of the anagram words and then communicates those back to the main task.

The code for this version is somewhat similar to that for option 1, so rather than presenting the whole main function I am just showing the key bits.

The first block creates the worker tasks and sets up streams to allow the master task to send requests.

    let mut request_chans : ~[Chan<~[~[int]]>] = ~[];
    for uint::range(0, width) |_| {
        let (request_port,request_chan) = stream();
        request_chans.push(request_chan);
        // Set up and start worker task
        let response_chan = response_chan.clone();
        do spawn {
            let (keys,values) = load_dictionary();
            response_chan.send( search(keys, values, &request_port) );
        }
    }

As a reminder, Rust tasks communicate only by sending and receiving messages; a Port is the sending side and a Chan is the receiving side. In this code, the main task creates an empty vector of Chan's and enters a loop where it

creates a stream,
stores the Chan for the main task's use,
duplicates the Chan used to report results from the worker task to the master, and
finally spawns a worker task.

The worker task loads a copy of the keys and values vectors (remember that the "vectors" version of the program uses binary search rather than a hash table to store and look-up matching letter sequences), and calls a search function to perform the useful work. When done, the results are returned to the master task via the response_chan.

The search function looks like this:

fn search(keys         : &[~[int]],
          values       : &[~[~str]],
          request_port : &Port<~[~[int]]>) -> ~LinearSet<~str> {
    let klen    = keys.len();
    let mut set = ~LinearSet::new();
    loop {
        let key_set = request_port.recv();
        if key_set.len() == 0 { break; }
        for key_set.each |key| {
            let j = bisect::bisect_left_ref(keys, key, 0, klen);
            if j < klen && keys[j] == *key {
                for values[j].each |&word| { set.insert(copy word); }
            }
        }
    }
    return set;
}

Notice that the type of request_port is a borrowed pointer to Port<~[~[int]]>: a Port on which the code can receive vectors of vectors of ints. The reason for the levels of vectors is simple: the key used for each look-up is a vector of ints, created from a string of letters. Unfortunately, sending each key individually (all 33,000,000 of them) would result in an enormous amount of communications overhead; this code receives a collection of keys (the badly named key_set) to look up at once. The master task signals that the worker should complete by sending an empty key_set.

The master task hands out requests to the workers with the following code:

    let mut t = 0;
    let mut key_set = ~[];
    for uint::range(2,letters.len() + 1) |i| {
        for combinations::each_combination(letters,i) |combo| {
            key_set.push( vec::from_slice(combo) );
            if key_set.len() >= depth {
                let mut ks = ~[];
                ks <-> key_set;
                request_chans[t].send(ks);
                t = (t + 1) % width;
            }
        }
    }
    if !key_set.is_empty() { request_chans[t].send(key_set); }
    for request_chans.each |chan| { chan.send(~[]) };

The variable t is used to identify which worker should receive a request; this code allocates the work round-robin style. It also accumulates depth keys into each request.

The dance in the innermost block is needed to avoid having key_set losing its value on each iteration. The send call transfers ownership of the message to the receiving task, so chan.send(key_set) would leave key_set without any meaningful value. This code instead creates a new variable, ks, containing an empty vector. ks and key_set then swap values, resetting key_set to the empty vector, and ks is used to send the request to the worker—ks is not used again, so there is no problem with it losing ownership while key_set is used again, on the next iteration.

The second-to-last line sends any remaining keys to the next worker thread, and the final line sends the empty request to inform the workers that no further requests will be made.

How well does this work?

Language	Program	Time (sec)	Speedup
Python	alternatives/presser_one.py	49.12	1
Rust	anagrams-vectors-tasks	27.13	2
Python	alternatives/presser_two.py	12.84	4
Rust	anagrams-vectors-wide	11.75	4
Rust	anagrams-hashmap-wide	9.38	5
C	alternatives/anagrams-vectors	8.05	6
Rust	anagrams-vectors	7.97	6
Rust	anagrams-hashmap	5.98	8
Python	alternatives/presser_three.py	5.94	8
C	alternatives/anagrams-hash	0.94	52

The program here, anagrams-vectors-tasks, takes about 27 seconds, making it the second-slowest of the current crop and much worse than the 8 seconds used by the sequential version of the same algorithm. Unlike the other parallel versions, anagrams-vectors-wide and anagrams-hashmap-wide, it also does not keep the CPU's busy; rather than seeing 100% utilization of five or six CPUs, I see 40 or 50%.

I believe Rust's send and receive implement a rendezvous: if a sender is not waiting with a message, the receiver blocks until a sender comes along; if a receiver is not waiting, the sender blocks. This is good in some cases, where it makes some optimizations possible. For example, it is possible to avoid invoking the thread scheduler if the sending thread can change its execution context and continue as the receiving thread. On the other hand, a rendezvous is bad here, because after the master task assigns a group of keys to the last worker task, it wraps around to send the next request to the first worker and must wait until the first worker task is finished with the previous group of keys, at which time that worker will call recv.

Letterpress cheating in Rust: Parallelism

2013-04-07T16:23:00.000-05:00

Or, how to turn an 8 second runtime to a 27 second runtime by throwing a stack of CPU's at it.

The anagram programs I have been using to explore Rust are CPU bound. They take command line arguments, read a file, do some number of seconds (or minutes) of computation, and print out a number. In other words, in modern terms, it is begging for parallelization¹.

After a little thought (very little, as will probably become obvious), there are two ways of doing it:

Split the anagram dictionary into $N$ non-overlapping segments and feed those to $N$ tasks along with the input letters. (Rust supports lightweight threads running under multiple CPU's, so-called "M:N threading".) Each task then runs all of the 30,000,000 queries implied by my standard input letters against its fragment of the dictionary, computing its subset of the anagram words as a LinearMap. Then each task communicates its result map back to the main thread, which accumulates the results and prints the final answer.
Have each of the $N$ tasks get its own copy of the complete dictionary. The main task then sends each request computed from the input letters (30,000,000 queries, remember) to one of the tasks, which accumulates a subset of the anagram words and then communicates those back to the main task.

I'll take a look at the first option here using, inexplicably, the vector, binary search, version of the programs. Here's the main function of the first:

fn main() {
    let width = 6;

    let args = os::args();
    if args.len() < 2 { fail!(~"Usage: anagrams letters"); }
    let letters = get_letters(args[1]);

    let (response_port,response_chan)
        : (Port<~LinearSet<~str>>,Chan<~LinearSet<~str>>) = stream();
    let response_chan = SharedChan(response_chan);

    for load_dictionary(width).each |&kv_pair{keys   : keys,
                                              values : values}| {
        let response_chan = response_chan.clone();
        let letters = copy letters;
        do spawn {
            let set = search(letters, keys, values);
            response_chan.send(set);
        }
    }

    let mut set = ~LinearSet::new();
    for uint::range(0,width) |_| {
        let res = response_port.recv();
        for res.each |&word| { set.insert(word); }
    }
    println(fmt!("%u", set.len()));
}

width is the number of sub-tasks to spawn and the next three lines set up the input query letters. The next three lines build up response_port and response_chan, used to communicate the sub-task's results to the main task.

The next block does the work of the program. The load_dictionary function, in this program, reads the dictionary file and splits it into width individual keys and values pairs of vectors. (I don't want to talk about the "kv_pair" structure. Let's just pretend it didn't happen.) The next step is to set up each sub-task's copy of the response_chan (via the call to clone) and a copy of the input letters. Then it calls spawn with an anonymous function; spawn executes the function in a separate task; that function here performs the 30,000,000 lookups and returns the resulting map.

The reason that letters has to be copied before calling spawn is that it is an owned value and the new anonymous function will take ownership of it in the new task; subsequent tasks wouldn't be able to get a copy of letters. Or, more correctly, the compiler will make whiney noises, since the type system is watching for things like that.

How do the sub-tasks report their results back to the main task? That is the purpose of response_port and response_chan. Rust tasks communicate by sending messages, with Chan's being the sending end and Port's being the receiving end of the message stream.

Creating that stream is handled by the second block of three lines, fundamentally by the call to core::comms::stream. The basic stream contains messages from exactly one task, destined for exactly one other task. In order to send results from multiple sub-tasks, the Chan end is wrapped in a SharedChan, which adds the clone method used further down. clone duplicates the SharedChan, allowing it to be used by multiple tasks to send messages to a single Port.

Sending the result is handled by response_chan.send(set), where set is a ~LinearSet<~str>; the important part is that set is an owned structure. Before the send, the sub-task owns it, and after the send, the main, receiving, task owns it. Receiving is handled by response_port.recv(). The main task uses the received result to accumulate its own, complete, set of results for all tasks and prints out the size of the set.

So, how well does this work?

Program	Duration (secs)	Speedup
anagrams-vectors-wide	11.75	4
anagrams-hashmap-wide	9.38	5
anagrams-vectors	7.97	6
anagrams-hashmap	5.98	8

The program we've been discussing is anagrams-vectors-wide; anagrams-hashmap-wide is a LinearMap-based version with identical structure. (Yeah, I don't get to name things.) anagrams-vectors and anagrams-hashmap are the serial versions. They're indeed faster; the speedup is a factor of the slowest version of the program, the first Python version. Interestingly, if you multiply the time taken by the serial version by 6, the number of parallel tasks, you get roughly the amount of user plus system CPU time taken by the parallel version. Anyway, the performance difference is almost certainly tasking overhead, although I have no idea what exactly is causing it at the moment. But more on that in the next post.

1. My $10 word of the day. I hope I spelled it right; it's not in my dictionary. It's also hard to pronounce.

Creating a Letterpress cheating program in Rust: Traits

2013-03-26T20:08:00.000-05:00

Ok, I'm not saying you would want to do this. But you could. That's all I want to get across. Just that you could do this, if you really wanted to.

What could you do? Let's say you are writing a Letterpress cheating thingy and need a program to generate the anagram dictionary: a file that contains a list of sorted letters, followed by the word or words that are made from those letters:

...
aabcdiinot abdication
aabcdkrsw backwards drawbacks
aabcdkrsy backyards
...

One way would be to just do it, which I've mentioned before. But that would hardly be any fun, right? How about we use (or overuse) traits?

Rust's traits are akin to Java interfaces or Haskell's type classes. Traits provide two things in Rust: a set of related functions (or "methods" in this case) which can be implemented for any suitable data structure, and as the Rust tutorial describes, a way to bound the type parameters of generic operations, limiting the types that can be arguments to the generic functions to those which implement the given trait as well as making the trait's methods available on the values of the generic type.

The first thing the mk_anadict program does is to read the /usr/dict/words file and create a dictionary mapping sorted sequences of letters to a list of words that can be made from those letters. Here is a trait that describes that operation:

trait DictReader {
    fn read_dict(&self) -> ~LinearMap<~str,~[~str]>;
}

That declaration says that an implementation of DictReader provides a method, read_dict, that takes no arguments (other than the object the method is invoked on) and returns a map from strings to vectors of strings. Now, I could provide a sui generis implementation of that trait, by creating a new type and defining an implementation on it, but that doesn't really show the power of traits. Instead, I wrote an implementation of the trait for an existing type, in effect adding the read_dict method to the existing type:

impl DictReader for Reader {

    fn read_dict(&self) -> ~LinearMap<~str,~[~str]> {
        let mut map = ~LinearMap::new();
        for self.each_line |line| {
            let line = line.trim();
            let length = line.len();
            // Original is using pre-strip() line for comparisons
            if length >= 2 && length < 19
                && line.all(|ch| (char::is_ascii(ch)
                                  && char::is_lowercase(ch))) {
                let mut chars = str::chars(line);
                std::sort::quick_sort(chars, |a,b| *a <= *b);
                let key = str::from_chars(chars);

                // What I'd like to do:
                // map.find_or_insert(key, ~[]).push(line);
                // But find_or_insert's result isn't mutable.

                let mut value = match map.pop(&key) {
                    None => { ~[] }
                    Some(old) => { old }
                };
                value.push(line);
                map.insert(key,value);
            }
        }
        return map;
    }

}

Reader is an existing Rust core library trait for reading input, in this case from a file. It has a method, each_line, which is an iterator over the lines from the input stream. What this implementation is saying is that anything that is a Reader is also a DictReader; any type that implements Reader also implements DictReader, including whatever file_reader returns.

How's that for spiffy?

I did a similar thing for writing the output, anagram dictionary file:

trait DictWriter {
    fn write_dict(&self, dict : &LinearMap<~str,~[~str]>);
}

impl DictWriter for Writer {

    fn write_dict(&self, dict : &LinearMap<~str,~[~str]>) {
        for dict.each_key_sorted() |key| {
            let line = str::connect(dict.get(key).map(|v| copy *v), " ");
            self.write_str(fmt!("%s %s\n", *key, line));
        }
    }

}

...with a small difficulty: LinearMap doesn't provide a way to iterate across the keys of the dictionary in sorted order. So, I added a third trait and implementation (see how addictive these things are?):

trait SortedKeys<K : Ord> {
    fn each_key_sorted(&self, blk : &fn(key : &K) -> bool);
}

impl<K : Hash + IterBytes + Eq + Ord, V> SortedKeys<K> for LinearMap<K,V> {

    fn each_key_sorted(&self, blk : &fn(key : &self/K) -> bool) {
        let mut keys : ~[&self/K] = vec::with_capacity(self.len());
        for self.each |&(k,_)| { keys.push(k); }
        std::sort::quick_sort(keys, |a,b| *a <= *b);
        for keys.each |&k| { if !blk(k) { break; } }
    }

}

...which is where the each_key_sorted method in the DictWriter implementation came from.

The type constraints on the implementation of SortedKeys<K> for LinearMap<K,V> deserve some explanation. The Hash and Eq traits are required of anything that can be a key in a LinearMap, and the IterBytes trait is required by Hash if I understand things correctly. The Ord trait requirement is added by the SortedKeys<K> trait, because the keys have to be ordered in order to be sortable. That implementation declaration is saying, if a type K is Hash-able, IterBytes-able, Eq-able, and Ord-able, then any LinearMap with keys of type K also implements Sortedkeys and has an each_key_sorted method.

The bottom line is the new implementation of mk_anadict's main function:

fn main() {
    match (file_reader(&Path("/usr/share/dict/words")),
           file_writer(&Path("anadict-rust.txt"), [Create,Truncate])) {
        (Ok(r),    Ok(w))     => {
            // It's like magic, but not as exciting.
            w.write_dict(r.read_dict());
        }
        (Err(msg), _)         => { fail!(msg); }
        (_,        Err(msg))  => { fail!(msg); }
    }
}

Like magic, indeed. The neat part is that I have done nothing to file_reader and file_writer; those functions from Rust's core io module still return whatever they return; I have just added some capabilities to the values they do return.

Like I wrote above, I am not advocating this style as a good way of writing idiotic programs like mk_anadict. I'm just saying that it's possible. And that you should get some exposure to traits (and type classes in Haskell) because they're powerful juju. Anyway, the trait version of the program, mk_anadict_traits.rs, is on github.

Link o' the day: I've been broken by Java.

2013-03-11T11:57:00.000-05:00

From java.lang.Character#getNumericValue(char):

public static int getNumericValue(char ch)
Returns the int value that the specified Unicode character represents. For example, the character '\u216C' (the roman numeral fifty) will return an int with a value of 50.

The letters A-Z in their uppercase ('\u0041' through '\u005A'), lowercase ('\u0061' through '\u007A'), and full width variant ('\uFF21' through '\uFF3A' and '\uFF41' through '\uFF5A') forms have numeric values from 10 through 35. This is independent of the Unicode specification, which does not assign numeric values to these char values.

If the character does not have a numeric value, then -1 is returned. If the character has a numeric value that cannot be represented as a nonnegative integer (for example, a fractional value), then -2 is returned.

Note: This method cannot handle supplementary characters. To support all Unicode characters, including supplementary characters, use the getNumericValue(int) method.

Parameters:

ch - the character to be converted.

Returns:

the numeric value of the character, as a nonnegative int value; -2 if the character has a numeric value that is not a nonnegative integer; -1 if the character has no numeric value.

Since:

1.1

See Also:

forDigit(int, int), isDigit(char)

Ok, I'm with them on the first paragraph: int value of the Unicode character. But, A-Z, a-z, and their "full width" versions are 10-35? Then, -1 and -2? And it's not complete.

See forDigit and isDigit? I don't think so.

I would like to thank Del for inflicting this ghastly abomination on me. I would, really. But I can't.

Creating a Letterpress cheating program in Rust, v2

2013-03-09T11:10:00.002-06:00

I have updated my horrible, horrible Rust anagram-esque code for a (relatively) up-to-date build of the Rust *master* branch, rustc 0.6 (edcebac 2013-03-03 20:02:06 -0800). There were a number of simple syntax changes, along with a much nicer hashmap.

I also fixed a grotesque performance problem that improved the Rust programs' times considerably, so these times are not *directly* comparable to the previous post.

To start, here are the current timings:

Program	Duration (sec)	Speedup
pesser_one.py	49.7	1
presser_two.py	12.5	4
anagrams-vectors.rs	7.9	6
presser_three.py	6.0	8
anagrams-hashmap.rs	5.8	9
anagrams-vectors.c	5.6	9
anagrams-hash.c	0.9	55

Once again, the argument for all of these runs was "asdwtribnowplfglewhqagnbe", which produces 7440 results from my dictionary; I get 33,554,406 combinations to look at. I used Python 2.7.3; gcc 4.6.3, with -O3; and rustc, with -O.

So, what did I change?

Overall, I'm now using core::hashmap::linear::LinearMap and LinearSet instead of the HashMap that used to be in the std crate. LinearMap has a much nicer, if still imperfect, interface.

The fail "keyword" is now a macro: fail!.

anagrams-vectors.rs

The previous version use a (owned) vector of (owned) vectors of chars to store the "keys" from the dictionary file: ~[~[char]]. To look up a key, made from a combination of the input letters (a (borrowed) vector of chars), I use a binary search into this vector. To make the binary search work, two vectors of chars need to be comparable, to implement the Ord trait. Unfortunately (and I need to check on this), char's don't have an implementation of Ord. So, I added one:

impl char : Ord {
    #[inline(always)] pure fn lt(&self, other: &char) -> bool { *self <  *other }
    #[inline(always)] pure fn le(&self, other: &char) -> bool { *self <= *other }
    #[inline(always)] pure fn gt(&self, other: &char) -> bool { *self >  *other }
    #[inline(always)] pure fn ge(&self, other: &char) -> bool { *self >= *other }
}

One of the recent changes to rustc, however, makes that illegal because it is problematic to implement a trait for a type originating from a different crate. As a result, I removed that implementation and made the keys vectors of int's (converting the char's to int's). The int's are comparable.

By the way, one of the syntax changes was to replace "impl char : Ord ..." with "impl Ord for char...". That declaration is now much more readable.

anagrams-hashmap.rs

Once again, I converted the vector of char's to a vector of int's. In this case, that did not result in any major changes.

The major performance change (which I did make to both programs) was to move the allocation of the actual key used by the lookup out of the each_combination inner loop. That is the major performance change.

The combination provided by each_combination is a &[int], while the call to dictionary.find(...) wants a &~[int] because the key type, K, for the dictionary is ~[int]. As a result, I need to copy the combination's values out of one vector and into an appropriately allocated vector. The previous version was allocating the copy in the inner loop; this version allocates it in the outer loop, where the size is known, and inserts the values in the inner loop. In other words, the previous version had:

let key = @vec::from_fn(combo.len(), |i| combo[i]);

(You can ignore the "@", which was needed by the previous hashmap to make the key's Copy-able.)

The current version uses:

let mut key = vec::from_elem(size, 0);              // outer loop
...
    for uint::range(0,i) |j| { key[j] = combo[j]; } // inner loop

Avoiding the allocation was a big win. Avoiding the copy would also be a win, but I don't know how to do that. Yet.

Link o' the day: The Deep Insights of Alan Kay

2013-03-08T18:41:00.000-06:00

At a meeting I recently attended, a coworker asked, "Is anyone going past low earth orbit in the next 50 years?"

"Well, lots of states are making marijuana legal," I replied

Alan Kay is my nomination for the computer science equivalent of astronautical marijuana.

Link(s) o' the day: Unix CLI tricks

2013-03-07T21:28:00.000-06:00

Unix tricks.
Commandlinefu: all commands sorted by votes.
The Magic SysRq key.

Quote o' the day: A bell you can't un-ring

2013-03-07T14:50:00.002-06:00

From Crafting a basic Ethernet MAC and 10BASE-T PHY,

So without further ado it’s time to cut the end off a CAT5 cable and start jamming wires into I/O ports.

In my experience, that doesn't usually end well.

Creating a Letterpress cheating program in Rust

2013-02-25T22:31:00.000-06:00

Update: Creating a Letterpress cheating program in Rust, v2.

As I believe I have mentioned, I have been casually learning Rust (currently, Rust 0.5) by working on a port of Jeff Knupp's Creating and Optimizing a Letterpress Cheating Program in Python. It's now time to describe my current progress.

For those of you with short attention spans, this is the punchline:

Program	Duration (sec)	Speedup
pesser_one.py	49.7	1
anagrams-hashmap.rs	24.0	2
anagrams-vectors.rs	17.6	3
presser_two.py	12.5	4
presser_three.py	6.0	8
anagrams-vectors.c	5.6	9
anagrams-hash.c	0.9	55

The argument for all of these runs was "asdwtribnowplfglewhqagnbe", which produces 7440 results from my dictionary; I get 33,554,406 combinations. I used Python 2.7.3; gcc 4.6.3, with -O3; and rustc 0.5, with -O. (I missed "--opt-level 3" the first time around and did get some improvement when I used it. But that's not shown here.)

I started by getting all three of the Python versions from Knupp working, to have something to compare against. (I would like to point out that presser_one.py is not something I would consider idiomatic Python, but I do need something to make the rest look better.) Then, I wrote the anagrams-hashmap Rust version, the meat of which looks like:

fn main() {
    let args = os::args();
    if args.len() < 2 { fail ~"Usage: anagrams letters"; }
    let mut letters = str::chars(args[1]);
    std::sort::quick_sort(letters, |a,b| *a <= *b);
    let dictionary = load_dictionary();
    let mut set : Set<@~str> = HashMap();
    for uint::range(2,letters.len()) |i| {
        for combinations::each_combination_ref(letters,i) |combo| {
            let ana = @vec::from_fn(combo.len(), |i| *combo[i]);
            match dictionary.find(ana) {
                Some(ref val) => {
                    for val.each() |word| { set_add(set, *word); }
                }
                None => { }
            }
        }
    }
    let result = vec_from_set(set);
    println(fmt!("%u", result.len()));
}

This code uses the each_combination function I described last time. Unfortunately, the hashmap interface (and implementation) are a bit of a mess in 0.5, leading to some unpleasant code and probably poor performance. Specifically, I'm looking at the line "@vec::from_fn(combo.len(), |i| *combo[i])", which copies the contents of the combination vector into a separate vector, since the call to "find(ana)" is going to take ownership.

Unhappy with the performance of that, I wrote the anagrams-vectors Rust version, which avoids the use of the hashmap for the dictionary, replacing it with a binary search similar to presser_one.py. In fact, it uses a conversion of the same bisect_left function. The fact that anagrams-vectors shows improvement should tell you there's something fishy in the state of Denmark (er, hashmap). (Unfortunately, the Set used to contain the resulting words is a thin wrapper on the hashmap, so I did not completely remove that module.)

Following several attempts to improve the Rust results without much success, I decided to dust off my C and go old-school, medieval in fact, on this sucker. I first came up with the vector-based C version, which mmaps the anagram dictionary file and builds its dictionary structure based on that file's sorted lines. Given that attempt's not-completely-satisfactory success, I added the hash version, which builds a pseudo-hashtable over the mmap'ed dictionary. That version is about as far as I'm willing to go at the moment.

There are probably a few worthwhile notes on the C versions:

There is no reusability in the C code. I'm not sure if there would be a point, given the focus on getting the fastest code quickly. On the other hand, it is fairly difficult to build reusable data structures such as hashmaps in C.
I am using some less-well-known parts of C. mmap is one example; another is using alloca for memory allocation; it puts the allocated space in the current stack frame, making deletion easier. (On the other hand, you can blow your stack pretty easily with it.)
The hash is djb2 from Hash Functions; it is dead simple and works fairly well. To keep the maximum chain length down (for linear chaining), the hashtable load factor is a pitiful 0.2; I tried several other values, but increasing it did cost time, while decreasing it further did not offer much improvement. For a load factor of 0.5, the maximum chain length was 41 if I remember correctly, for 0.2, it was 9 with 58505 entries.
I used a bitset to hold the results, noting that each word in the output could come from exactly one line, all of the words on the line would appear if any did, and each line could appear exactly once. Yes, that's 58,000 bits. Using integers did not seem to make any special difference over the bit-manipulations, and I was worried about stack space.

I expect the performance to improve as Rust work continues. In fact, the hashmap interface is much better in the version in the core library in incoming. When 0.6 lands (or sooner), I'll update this code and provide up-to-date results.

Rust Iterators

2013-02-21T20:42:00.000-06:00

In my last post, I described my first Rust program, a simple utility to build an anagram dictionary based on part of Jeff Knupp's Python Letterpress cheating program. This time, I would like to take a closer look at a slightly unusual part of Rust by presenting an implementation of part of Python's itertools module that is needed by the remainder of the anagram-esqe program.

In order to find all the words that can be built from a set of characters, Jeff uses combinations, a function which "[returns] r length subsequences of elements from the input iterable. Combinations are emitted in lexicographic sort order. So, if the input iterable is sorted, the combination tuples will be produced in sorted order." According to the documentation, combinations('ABCD', 2) produces "AB", "AC", "AD", "BC", "BD", "CD". The Rust standard library doesn't include anything like this function.

What Rust does have is a style of iterators based on higher-order functions. For example, to iterate across all the elements of a vector, the function vec::each takes a vector and a function to be applied to each element: each(v, |elt| { frob(elt) }) (or alternatively, the "method" version is an element of a typeclass with an implementation for vectors, allowing it to be called as v.each(|elt| { frob(elt) })). Now, the way this function works is that the function argument should return true or false after processing each element; if it returns false, the iteration terminates. In other words, the frob function should return a boolean in those examples.

Rust provides a couple of special syntactic forms that make these higher-order functions easier to use: do and for expressions. The syntax for the for expression is:

"for" expr [ '|' ident_list '|' ] ? '{' block '}' ;

The do expression differs only in the keyword. do is the simpler of the two; to illustrate, the Rust manual describes the following two expressions as identical:

f(|j| g(j));

do f |j| {
    g(j);
}

The higher-order function is f, j is the parameter to the anonymous function, which in turn calls g with j. One feature of this syntactic form is that a return expression in the body of the anonymous function returns from the function enclosing the do expression, not the inner anonymous function. Likewise, break and loop are handled specially, allowing the expression to behave more like a control structure. (The latter is similar to continue in many other languages, in this use.)

The for expression is similar, but more specialized. In addition to the specialized handling of return, the anonymous function forming the body of the for expression implicitly returns true, continuing the iteration. The Rust tutorial provides this example:

for each([2, 4, 8, 5, 16]) |n| {
    if *n % 2 != 0 {
        println("found odd number!");
        break;
    }
}

The signature of each is fn each<'r,T>(v: &'r [T], f: &fn(&'r T) -> bool); v is the vector argument and f is the function. (For the moment, ignore the "&'r" bit.)

How does this interact with combinations? How about an each-like function that takes arguments describing what and how many to combine, and a function to apply to each combination as it is generated? Without too much introduction, this is what I came up with:

pub pure fn each_combination<T:Copy>(values : &[T],
                                     r : uint,
                                     fun : &fn(combo : &[T]) -> bool) {
    let length = values.len();
    if r == 0 || r > length { return; }
    let max_indices0 = length - r;
    let mut indices = vec::from_fn(r, |i| i);
    let mut combination = vec::from_fn(r, |i| values[i]);
    loop {
        if !fun(combination) { return; }
        let mut i = r - 1;
        indices[i] += 1;
        while i > 0 && indices[i] > max_indices0 + i {
            i -= 1;
            indices[i] += 1;
        }
        if indices[0] > max_indices0 { break; }
        combination[i] = values[indices[i]];
        for uint::range(i + 1, r) |i| {
            indices[i] = indices[i-1] + 1;
            combination[i] = values[indices[i]];
        }
    }
}

This function first tests whether any iterations are needed, then creates a pair of vectors to handle those needed. indices is a vector of integers, the size of the combinations that are needed, containing the indices into the values argument for the current combination. The combination vector contains the r elements from values (specifically, copies of them) for the current combination. Specifially, the loop tries to maintain combination[i] = values[indices[i], for i in 0 to r-1. The contents of the indices vector are incremented lexicographically, with the first, while, inner loop locating the right-most index to be incremented and the second, for loop, fixing up the subsequent indices as well as the combination vector. The overall loop terminates when the left-most index, indices[0] is too large to allow the remainder of indices to fit into values. Or when fun returns false after being invoked with a combination.

There are a couple of minor points to notice about this function. First, it is marked pure, indicating that it only modifies data owned by its own stack frame; meaning that aside from internal manipulations, it is (ideally) referentially transparent. Second, notice that indices, combination, and the helper i are declared mut, meaning that these variables are mutable; otherwise variables in Rust are immutable.

Third, the type parameter of each_combination, T. Because elements from values are copied into combination, T must be copyable, indicated by the Copy typeclass. Requiring that, in general, seems sub-optimal, so I created a second, much shorter, function that uses each_combination but does not require T to be copyable.

pub pure fn each_combination_ref<'v,T>(values : &'v [T],
                                    r : uint,
                                    fun : &fn(combo : &[&'v T]) -> bool) {
    each_combination(vec::from_fn(values.len(), |i| &values[i]), r, fun);
}

This function creates a vector containing borrowed pointers to the elements of the original values, then calls each_combination on it. Since the borrowed pointers are being copied, not the contents of the vector, T no longer needs to be copyable and as a side effect (if T is large enough, say) this function may be more efficient. The function parameter must be different, of course, in that it acts on a borrowed pointer to a vector containing borrowed pointers to the value elements. That is where Rust's type system gets interesting.

Check out the type of values and the type of combo, the parameter to the function fun. The type of values is &'v [T], indicating that it is a borrowed pointer to a vector containing T's, with a lifetime variable of v. The type of combo is &[&'v T], which is a borrowed pointer to a vector containing borrowed pointers to T's, here the inner borrowed pointers have the same lifetime variable, v. [Note: the syntax for lifetime variables will be changing in Rust 0.6.]

Those types are telling the Rust compiler that the contents of combo can be used anywhere that doesn't live any longer than values. Equivalent C code could easily leak the pointers into values, leaving them dangling if that vector were freed.

Niko Matsakis described the for loop protocol in detail, along with a significant problem and proposed solution: Revised for loop protocol.

Update 4/5/2013: Updated to use rust 0.6 lifetime syntax. "&v/T" became "&'v T". Also, the library modules have the lifetime, "'v", as the first of the type parameters as shown above, although that is not mentioned in the manual or RELEASES.txt.

Exploring Rust

2013-02-17T00:24:00.000-06:00

Of the current crop of new programming languages, the one that I've been most interested in is Rust, a "safe, concurrent, practical language" that is intended for "frustrated C++ developers", with features intended to improve "systems" programming currently done in C and C++. Those features are mostly things that have been floating around the programming language community for decades, but have not been applied to a low-level language that also addresses issues like memory layout and garbage-collection avoidance.

The only way to learn a programming language is to write programs using it. Unfortunately, I have only limited natural creativity, so I need a little help in finding programs to write. In this case, the inspiration was Creating and Optimizing a Letterpress Cheating Program in Python, in which Jeff Knupp presents some Python to find all of the words which can be made from a set of letters. (No, it's not really anagrams, but it's close. Yes, I know my naming sucks.)

The first step in the program, and my first step in Rust, is a program to convert the Unix words file into an anagram dictionary. This is my version in Rust; I would greatly appreciate any comments or suggestions. I am currently using Rust 0.5, which is an important point; Rust is changing rapidly. Also, I am not making any claim that this is a particularly good Rust program.

fn main() {
    match (file_reader(&Path("/usr/share/dict/words")),
           file_writer(&Path("anadict-rust.txt"), [Create,Truncate])) {
        (Ok(r),    Ok(w))    => { print_dict(w, read_dict(r)); }
        (Err(msg), _)        => { fail msg; }
        (_,        Err(msg)) => { fail msg; }
    }
}

Beginning at the end, the main function opens a reader on the words file and a writer on a dictionary file. Both of those operations can fail, so the return type for file_reader, for example, is Result<Reader, ~str>; a Reader object implements the interface to read the file while the str represents the error message. In fact, the error message is a ~str, an owned pointer to a dynamically allocated string; a string allocated on the "owned" heap which will be deleted when the (single) owning reference to it goes away. The two variants of the Result are the constructors Ok and Err. (If you are familiar with Haskell or any of the ML languages, Result is a specialization of an Either algebraic data type.)

This function first creates a pair of Results, then uses pattern matching to deconstruct the two results. If both are Ok, the program reads the words file, building a dictionary, and then writes the dictionary out. Otherwise, it fails with an error message. The patterns are tried in order, so if both fail then only the reader message will be produced.

The read_dict function produces a HashMap (on the owned heap) mapping strings to vectors of strings. The value is a list of words made from the same set of letters while the key is the sorted letters. There are some peculiarities here; let me go over the relatively normal processing before getting into them.

fn read_dict(reader : Reader) -> ~HashMap<@~str,@[@~str]> {
    let map = ~HashMap();                             // [1]
    for reader.each_line |line| {                     // [2]
        let line   = line.trim();
        let length = line.len();
        // Original is using pre-strip() line for comparisons
        if length >= 2 && length < 19 && line.all(|ch| (char::is_ascii(ch) && char::is_lowercase(ch))) {
            let mut chars = str::chars(line);         // [3]
            std::sort::quick_sort(chars, |a,b| *a <= *b);
            let key = str::from_chars(chars);
            map.update(@key, @[@line], |old,nw| at_vec::append(old,nw));
        }
    }
    return map;
}

The line marked [1] allocates the Hashmap on the owned heap. The type is inferred, based on the keys and values and the function return type.

The line [2] is a use of Rust's iterator pattern. The function each_line, used as a method on the reader, takes one argument, a function to which is passed the line just read. This function is supposed to return true or false, indicating whether or not the iteration is to continue. However, special syntax and semantics are provided by the for keyword; since each_line has no other arguments, the parentheses are optional, and the function is provided by an anonymous function immediately following each_line. "|line|" is the parameter list for the anonymous function, while the body follows in braces. Another feature of the for keyword is that the anonymous function automatically returns true.

The major processing of the anonymous function filters out words of less than one character or more than 18, or which are made up of non-lowercase ASCII. The key for the HashMap is made by breaking the words into a vector of characters, then sorting and re-forming a string. The value is a vector containing the word, if the map does not already have a matching key, or the combination of the existing list and the new word if it does.

The second argument to the quick_sort function, "|a,b| *a <= *b", is another anonymous function, used to compare characters while sorting. The "mut" keyword on line [3], by the way, marks the chars vector as mutable, allowing it to be sorted.

A tilde indicates a pointer to the owned heap, but an at-sign, @, indicates a pointer into the managed heap. Rust's managed heap is a garbage-collected area local to the one thread. With the current library, most functions such as str::chars and str::from_chars produce owned pointers, a vector of characters and a string, respectively. Also, the HashMap requires its keys and values to be copyable, which owned strings in particular are not. To avoid warnings and excess copying, I am using @~str, a managed pointer to an owned string.

Fortunately, writing the dictionary is simpler. Since it is important that the resulting file is in sorted order, print_dict first gets the sorted keys to the dictionary. For each one, it gets the values, joins them into a string separated by spaces, and writes the formatted line out.

fn print_dict(writer : Writer, dict : &HashMap<@~str,@[@~str]>) {
    for sorted_keys(dict).each |key| {
        let line = str::connect( dict.get(*key).map(|v| **v), " " );
        writer.write_str( fmt!("%s %s\n", **key, line) );
    }
}

The * operator in this code dereferences a pointer; the key in the anonymous function is a borrowed (the third type) pointer, pointing to the @~str HashMap key. As a result, "*key" (the argument to the map function, is a @~str, while the value of the anonymous method "|v| **v" is a ~str, a vector of which is the correct argument to str::connect.

Naturally, sorted_keys is not a function from the library.

fn sorted_keys<V:Copy>(dict : &HashMap<@~str,V>) -> ~[@~str] {
    let mut keys = vec::with_capacity( dict.size() );
    for dict.each_key |key| { keys.push(key); }
    std::sort::quick_sort(keys, |a,b| *a <= *b);
    return keys;
}

"<V:Copy>" is a type parameter to sorted_keys; V is the type variable, which must satisfy the Copy typeclass, which is in turn needed by the HashMap. This type signature simply indicates that this function does not care about the type of values of the map.

Pattern matching, algebraic data types, anonymous and higher-order functions, type inference, parametric polymorphism, type classes, a confusing variety of memory allocation strategies, a somewhat chaotic library.... Rust is entertaining, at least.

The code is available on Github.

Brian Harvey on Scheme vs. Python

2013-01-30T20:22:00.000-06:00

Scheme vs. Python is an excellent read, but I would be more impressed if he took points 3 and 4 out back and shot them in the head. "[Y]ou should be able to learn a programming language (after the first time) over a weekend" is perfectly true (for some reasonable value of "weekend"), for a Computer Science program. "The best language for a course is not necessarily the best language for writing real-world code" is an excellent point as well. "You can learn to program in any language [but] the big ideas in [SICP]...express themselves best in Scheme" is (arguably, I admit) also valid.

But points 3 and 4 are, first of all, the same "Everyone should use Lisp" argument that hasn't actually convinced anyone in the 50-year history of Lisp. They weaken the actual point I think he's trying to make, or at least that I wish he was trying to make.

What, exactly does "the lifespan of a programming language is closer to the lifespan of a dog than to that of a person" mean? What is the lifespan of a programming language? I don't know of any programming languages that have achieved some kind of critical mass that can be meaningfully said to have "died".

Furthermore, fundamentally, what is "Lisp"? LISP 1.5, a la McCarthy? Is anyone still using that? Common Lisp? Good luck with recursion there; recursion without tail call elimination is not an especially good idea. Scheme != Lisp, any more than C, C++, Java, et al., are the same as ALGOL. There are ideas that unite all of these languages, but the fundamental one, that programs are data and that data is a program, is not one of "Lisp’s ideas [demanded by 'real users'] in the programming languages they do use."

Finally, what the heck is up with "[u]sers of strongly typed languages demanded, and got, Lisp's heterogeneous lists." I'm not seeing it.

RESTful web services

2013-01-25T12:59:00.002-06:00

This is a copy of an email I just sent to a co-worker that I thought might be worth preserving.

"I’m looking for a really good RESTful webservices book...."

The three I have looked at are:

RESTful Web Services Cookbook by Subbu Allamaraju, is probably the one I would recommend. It follows the O'Reilly "cookbook" format, which I hate, but it has more specific details that aren't found in blog posts and product documentation.

RESTful Web Services by Leonard Richardson and Sam Ruby, is another one I would recommend. In fact, it is the more generic introduction to RESTy stuff, but since the devil is in the details, I kind of prefer the cookbook. On the other hand, if you're looking for two books, I would get both.

RESTful Java with JAX-RS by Bill Burke, which is focused primarily on the Java JSR-311/JAX-RS framework.

The one important blog post I would like to mention is Roy Fielding's "REST APIs must be hypertext-driven". Fielding produces exceptional gibberish, but that post has the three (really, two and a half) points that most RESTful stuff misses:

"A REST API should spend almost all of its descriptive effort in defining the media type(s) used for representing resources...or in defining ... hypertext-enabled mark-up for existing standard media types." The important part of REST, as a networking strategy in general, is the focus on the "document", the messages exchanged on the wire describing the "resources". Almost everything else is actually an implementation detail that should be pinned down later.

"A REST API must not define fixed resource names or hierarchies (an obvious coupling of client and server). Instead, allow servers to instruct clients on how to construct appropriate URIs, such as is done in HTML forms and URI templates, by defining those instructions within media types and link relations." Most of the REST documentation spends a lot of time on "URL paths", which is a complete waste of time since the client shouldn't care where the resources are.

"A REST API should be entered with no prior knowledge beyond the initial URI (bookmark) and set of standardized media types that are appropriate for the intended audience.... From that point on, all application state transitions must be driven by client selection of server-provided choices that are present in the received representations...." This is a corollary of #2; every operation the client invokes should be driven from a URL received in a previous operation. The key point is that all the client needs to know is a single "touchpoint" URL and the format of the documents sent back and forth.

Here endeth the lesson.

Quote o' the day: The award for best function name goes to...

2012-12-14T12:46:00.000-06:00

While reading a message from Daniel Fischer on the Haskell-beginners mailing list, what do I see but:

it'sSafeIPromise :: Reader a -> Text -> a
it'sSafeIPromise = (value .)
  where
    value (Right (v,_)) = v

readInt :: Text -> Int
readInt = it'sSafeIPromise decimal

Yes, the apostrophe is a valid character in identifiers in Haskell, but I had always seen it as a prime, not in a contraction.

Link o' the day: Taken to School

2012-10-18T19:45:00.002-05:00

From The Quantum Pontiff, a link to a journalistic investigation of the most important issue facing the academic community, not to mention the greatest scam ever perpetrated on the young people of today.

Taken to School

Tip: RedHat httpd RPM replacement

2012-10-17T12:00:00.001-05:00

Hmph. I can't think of a word beginning with r- for Apache httpd.

When a couple of our servers were patched, it looks like the RedHat httpd took over for our /usr/local/ httpd. I didn't think the RPM was installed previously but I'm not sure, so I don't know whether the infamous They upgraded it during the patching or if they just installed it.

In any case, here's how to fix it:

To tell what httpd is running:
```
  $ ps -ef | grep httpd
```
If the list of processes has /usr/sbin/httpd, it's the RPM version. Our local version will be something starting with /usr/local.
If the RPM version is running, become root and kill it:
```
  # /etc/init.d/httpd stop
```
(Optional) Blow away the httpd RPMs:
```
  # rpm -qa | grep httpd
```
This command lists the RPMs installed; looks like there's three on this server now: httpd-2.2.15, httpd-tools-2.2.15, and httpd-manual-2.2.15. (Yay, doccies.)
```
  # yum remove package
```
The comes from the rpm -qa list above, and removing httpd removes httpd-manual (and some other packages as well) so I just had to remove httpd and httpd-tools.

That'll teach 'em.

You will want to do this after you stop httpd and before you remove and re-create the /etc/init.d link because removing the RPM blows away the /etc/init.d link as well as stopping the server. Trying to use the rpm command rather than yum is possible (The command is rpm -e package.), but it doesn't remove recursive dependencies, meaning it will require iteration.
Remove the /etc/init.d/httpd script from the RPM and replace it with a link to the our version:
```
  # rm /etc/init.d/httpd
  # ln -s /usr/local/ours/httpd/bin/apachectl /etc/init.d/httpd
```
Yes, the startup script that comes with apache is called apachectl. If you removed the RPM in the previous step, you don't have to remove the init.d script here. If you didn't, you will probably have to go through this dance the next time They patch the servers.
Start our httpd:
```
  # /etc/init.d/httpd start
```
The ps command above should now show our httpd.

Here's to not having to look up rpm commands again.

Quote o' the day: apt-wat?

2012-09-18T11:50:00.000-05:00

From the apt-get(8) man page:

remove

remove is identical to install except that packages are removed instead of installed. Note the removing a package leaves its configuration files in system. If a plus sign is appended to the package name (with no intervening space), the identified package will be installed instead of removed.

In a burst of consistency, apt-get install can remove packages: "If a hyphen is appended to the package name (with no intervening space), the identified package will be removed if it is installed." It also gives some explanation: "These latter features may be used to override decisions made by apt-get's conflict resolution system."

Still, people think I'm weird.

Quote o' the day: Slightly over the top

2012-09-12T11:51:00.000-05:00

cunningjames, in the thread on Go at Conformal on proggit, writes

Where are the cons? This reads to me like “Go is perfect! If my daughter brought home Go and told me she was having his baby, I’d be ecstatic! Yes, I know my daughter’s 11! Okay, the documentation is slightly less than perfect. But otherwise it’s the bee’s knees, the bee’s elbows, and — heck — all the bee’s hinge joints! Writing Go is like being on Vicodin and Cocaine and a mixture of adderall and benzos all the time!”

Wow. Just, wow.

Link o' the day: Why ebooks cost as much as paperbacks

2012-08-18T22:26:00.000-05:00

From Doug Bolden, Ten reasons why ebooks cost as much as paperbacks:

10. High medical premiums associated with XML lung.

Cough, cough.

Quote o' the day: IE vs. cookies

2012-07-27T17:07:00.000-05:00

From EricLaw's IEInternals:

It’s worth mentioning that increased cookie limit actually broke the website of a major financial institution. The site depended on cookies beyond the 20 cookie limit getting dropped, and stopped working properly when the limit was increased. This is just one example of how tightly-coupled today’s web is to IE’s cookie implementation. That, in turn, is one reason why the IE team must exercise great care when making any change to IE’s cookie implementation.

Great care, indeed. Eric also writes, "Over the five years I’ve worked on Internet Explorer, I’ve probably seen more questions from the community about HTTP cookies than on any other topic."

Which might mean something.