Lisp is full of teh WIN

I know that the title is lame, verging on cringe-inducing, but I had to say it; I'm not sorry. There has been a few threads of discussion over on Hacker News about what's wrong with Lisp. The argument seems to hinge on the lack of a literal syntax for "hashes" in lisp the way that there is in python or, in a more appropriate comparison, clojure. Clojure is great, by the way, and it is certainly deserving of its own post sometime soon. Suffice it to say that the next time I have to write something in Java I think I'm going to write it in clojure instead. Clojure has great interoperability with Java. Amazingly, there are fewer parenthesis in the Lisp version of that little GUI program than in the Java version! But on to the topic of the day. In many languages you can do something like this:

>>> d = {"a":1, "b":2, "c":3}
>>> d
{'a': 1, 'c': 3, 'b': 2}
>>> d['b']
2

You can see that we can explicitly give a representation of that hash that python knows how to parse into the corresponding data structure. Clojure has a very similar literal syntax:

user=> (get {:a 1 :b 2 :c 3} :b)
2

So the complaint is that Common Lisp doesn't have anything like that. Using hashes in CL consists of a bunch of function calls that manage the hash:

CL-USER> (let ((hash (make-hash-table)))                                       
          (setf (gethash :a hash) 1)                                          
          (setf (gethash :b hash) 2)                                          
          (setf (gethash :c hash) 3)                                          
          (gethash :b hash))
2
T

There is never any literal representation of the hash, in fact, if we evaluate the name of the hash we'll just get something like this "#<HASH-TABLE :TEST EQL :COUNT 3 {AD11A99}>" Which basically tells the lisp reader to signal an error if the form is read. But this doesn't have to be so verbose. We can write a really simple reader macro (with a little helper function) that gives us something like what we have in python or clojure above:

(defun ins-hash (h vals)
  (if (oddp (length vals))
      nil
      (if (not (null vals))
          (progn
            (setf (gethash (first vals) h) (second vals))
            (ins-hash h (cddr vals)))
          h)))

(set-macro-character #\} (get-macro-character #\)))

(set-dispatch-macro-character #\# #\{
  #'(lambda (stream char1 char2)
      (let ((items (read-delimited-list #\} stream t)))
        (ins-hash (make-hash-table) items))))

With this reader macro I can now write this:

CL-USER> (gethash :b #{:a 1 :b 2 :c 3})
2
T

Lisp now interprets everything between '#{' and '}' as key, value pairs and using the helper function inserts them into a new hash. Cool!

dehexer

I was looking through Hal's blog when I came across his hexer program. I thought that I should write the complimentary program, that is, given an ascii file of hex characters (e.g. "01CAFEBABE") it will write actual bytes to stdout.

chris@papaya:c$ cc helloworld.c
chris@papaya:c$ ./a.out 
Hello World!
chris@papaya:c$ cat a.out | ./hexer | ./dehexer > helloworld
chris@papaya:c$ chmod a+x helloworld
chris@papaya:c$ ./helloworld 
Hello World!

It seems to work (I changed the name to 'helloworld' because doing

cat a.out | ./hexer | ./dehexer > a.out

seems to clobber the file in a bad way.

Without further ado:

/* dehexer - Convert an ascii file of hex characters into the
   corresponding binary file. Any non-hex characters are silently
   skipped (newlines, tabs, etc.)
   Copyright 2008 Christopher Wilson, based in part on hexer by Hal
   Canary (also DTPD)
   Dedicated to the Public Domain */
/* cc -o dehexer dehexer.c */
#include 
#include 
int main (int argc, char *argv[])
{
  char x;
  int char_out = 0;
  int low = 0; // LSBs, 1 for true
  while (fread(&x, sizeof(x), 1, stdin) == 1) {
    if (x > 47 && x < 58) { 
      // digit is 0-9
      x = x - 48;
      handle_byte(x, &char_out, low);
    } else if (x > 64 && x < 71) {
      // digit is A-F
      x = x - 55;
      handle_byte(x, &char_out, low);
    } else if (x > 96 && x < 103) {
      // digit a-f
      x = x - 87;
      handle_byte(x, &char_out, low);
    } else {
      // skip anything that isn't 0-9A-Z, or a-z
      continue;
    }
    low = (low + 1) % 2; // flip the high/low bit marker
  }
  return(0);
}

/* handle_byte - if low is true then it prints the full byte. If low
     is false, set char_out to 16 times x.
*/
int handle_byte(int x, char *char_out, int low)
{
  if(low) {
    *char_out += x;
    putc(*char_out, stdout);
  } else {
    *char_out = x * 16;
  }
  return 0;
}
/* EOF */

Comments

So I've had this idea bouncing around in my head and I'm not sure why. Well that's not true, if I were so unsure I don't think that I'd post this. Maybe it is the idea of what's going on with a project called StupidFilter. It is pretty much what its name would suggest. Its aim is to create a software filter that would remove stupid blog comments (or any other content that you'd like to filter). Note that by my use of 'stupid' above, I'm not really talking about stupidity per se, (because that's very likely a hard problem). No, what I'm talking about may be more akin to a symptom of stupidity? Or maybe just gross violations of proper English, which doesn't really speak to a person's intelligence... I had been thinking about what would be the simplest, most brain-dead method for identifying stupidity in text. The first thing that sprang to mind was entropy. Entropy is the measure of how much uncertainty there is in something (at least as it applies to information theory). A coin toss has 1 bit of entropy, it is calculated like so: So we get -1/2 * log(1/2) + -1/2 * log(1/2) = 1 I wrote the following code: here (which you can actually run, thanks codepad!). You'll notice that the text from a YouTube comment has a higher entropy than some text that I typed in. I'm actually just going by the letters, no punctuation is included. My hypothesis here is that badly mangled text will have a higher entropy than normal English. Perfectly random text (i.e. text with all 26 letters equally likely) has an entropy of 4.7 bits. This makes sense, since if you'd want to encode all the letters of the alphabet in binary, you'd need at least 5 bits (2^5 = 32, first power of two greater than 26). I think if I include punctuation and all that I may get a better "reading" because an exclamation point, being rare in normal text at least, would have a longer Huffman coding (I haven't really thought about this, could be wrong) and thus lend more to the entropy. My next idea was taken from my cryptography class. English has a certain frequency distribution for the letters (and numbers, punctuation etc.) that we can exploit. A string of 25 'z's in a row doesn't "look" like any standard sentence. We expect, roughly, that as the length of an English text increases the frequencies of the letters should approach 13% 'e', 9% 't', 8% 'a', and so on (List here). I wrote a very simple program here. I took the sum of the squared differences from the "normal" distribution as a "distance" measurement. We would expect a very long text to get very close to zero (i.e. the frequency distributions will tend to match). Both of these are really simple and would need a lot of work (multiplying together, weighting?) to be in in any way practical. But both constitute a very simple test of English-ness, basically, does the target text resemble English (at least statistically).