Writing/Coding

Not Dead Yet!

2009-06-10T12:38:00.002-05:00

I'm back. For the moment, anyway. More about that below.

What have I been up to? A lot, really.

General life stuff, of course. It always gets in the way.
My wife and I have adopted a little girl, and that keeps us busy, both with adoption busyness and with new parent busyness.
I've started a new job.
As far as programming goes, I'm exploring function programming. Clojure got me started, and since then I've branched out to Haskell and F#. I primarily wanted to learn Haskell, but I've had more opportunity to use F#. At some point, I should compare the two.

Speaking of Clojure, I recently finished scanning my dead-tree edition of Programming Clojure. It has good, practical examples. (I've taught enough to know how hard it is to have practical examples.) For example, Lancet is an extended example that Stuart Halloway develops throughout the book. It creates a DSL for build files (think make). The system itself is built upon ant, but it creates a nice interface layer on top of that.

The book is also a good introduction to functional programming, including how it's different than object-oriented programming and how to use it best for the benefits it gives for concurrency and other problems.

I'll close this post by outlining the direction I'd like to take this blog. I think I've implied in the past that I haven't been happy that it's turned into a Clojure tutorial (nice though that is). I just haven't been sure what I wanted it to become. I think I've finally got some ideas.

Primarily, I'd like Writing/Coding to be more results oriented. I'll still talk about text- and natural-language-processing, but instead of a lot of code and nuts-and-bolts, I'll focus on the results of those analysis and visualizations and pretty pictures. There will still be some code, but much, much less. For a while now, I've been interested in data visualization, and this will give me an opportunity to explore that.

This will also be much less Clojure-centric. Clojure will still be here, certainly, but you can also expect some Python, Haskell, F#, and who-knows-what. (BF, anyone?)

First off, I need to brainstorm some post ideas, outline a dozen or so of those, and draft a few to have ready. Once that's taken care of, I'll start posting here again. That won't happen immediately, but I hope to get it done real soon now.

In the meantime, go get Programming Clojure.

Facebook Haiku/Doggerel #1

2008-11-11T20:50:00.001-05:00

The other night, bored, I half watched TV and half watched my wife on Facebook. It inspired me to take up pen and produce some dreadful haikus, and in the best tradition of the Internet and blogs, I'm inflicting them on you. To draw out your pain and my evil glee, I'll deliver them one at a time.

Here's number one.

Heh. Enjoy.

Friends write on my wall.
Messages of cheer and joy
Why do they hassle me?

Concordances, Part 3: Positioning Tokens

2008-10-24T14:52:00.001-05:00

Today, we're going to add to the processing information about where a token appears in the original document.

Tokens Today

Currently, a token is just the string containing the token data.

Easy enough.

Tokens Tomorrow

To hold more information about the token, we'll need a richer data type. To accommodate that, here's a struct for tokens:

(defstruct token :text :raw :line :start :end :filename)

This gives us slots to hold the token's text; its original text before case normalization, stemming, or whatever; the line it occurred on; the start and end indices where it can be found on that line; and the name of the file the token was read from.

Again, pretty simple.

Updating the Tokenization

The big changes happen in the tokenization procedure. Currently, it doesn't take lines into account.

Let's start with the highest-level functions and drill down to the lowest. First, these functions tokenize either a file or a string.

(defn split-lines [input-string]
  (.split #"\\r|\\n|\\r\\n" input-string))

(defn tokenize-str
  ([input-string]
   (tokenize-str-seq (split-lines input-string)))
  ([input-string stop-word?]
   (filter (comp :text (complement stop-word?))
                       (tokenize-str input-string))))

(defn tokenize
  ([filename]
   (with-open in (BufferedReader. (FileReader. filename))
     (doall
       (map (fn [tkn] (assoc tkn :filename filename))
            (tokenize-str-seq (line-seq in))))))
  ([filename stop-word?]
   (with-open in (BufferedReader. (FileReader. filename))
     (doall
       (map (fn [tkn] (assoc tkn :filename filename))
            (filter (comp :text (complement stop-word?))
                    (tokenize-str-seq (line-seq in))))))))

split-lines breaks a string into lines based on a regex of line endings.

tokenize-str uses split-lines to break its input into lines, and it calls tokenize-str-seq with them. The second overload for this function then filters the tokens with a stop list.

tokenize opens a file with a java.io.BufferedReader, and it calls tokenize-str-seq with them. It sets the :filename key on the token structures.

doall is thrown in there because map is lazy, but with-open isn't. doall forces map to evaluate everything. Without it, with-open would close the file before its contents could be read. This is a common mistake, and it will probably bit you regularly. It does me.

We haven't seen tokenize-str-seq yet. What does it do?

(def token-regex #"\\w+")

(defn- tokenize-str-seq
  "This tokenizes a sequence of strings."
  ([strings]
   (tokenize-str-seq strings 0))
  ([strings line-no]
   (when-first line strings
     (lazy-cat (tokenize-line line-no (re-matcher token-regex line) 0)
               (tokenize-str-seq (rest strings) (inc line-no))))))

This function tokenizes a sequence of strings. It walks through the sequence, numbering each line (line-no). For each input line, it constructs a lazy sequence by concatenating the tokens for that line (tokenize-line) with the tokens for the rest of the lines.

when-first is new. It is exactly equivalent to when plus let:

user=> (macroexpand-1 '(when-first line strings (println line)))
(clojure/when (clojure/seq strings)
  (clojure/let [line (clojure/first strings)]
    (println line)))

tokenize-line constructs a lazy sequence of the tokens in that line.

(defn- tokenize-line
  "This tokenizes a single line into a lazy sequence of tokens."
  ([line-no matcher]
   (tokenize-line line-no matcher 0))
  ([line-no matcher start]
   (when (.find matcher start)
     (lazy-cons (mk-token line-no matcher)
                (tokenize-line line-no matcher (.end matcher))))))

mk-token constructs a token struct from a regex and line number.

(defn- mk-token
  "This creates a token given a line number and regex matcher."
  [line-no matcher]
  (let [raw (.group matcher)]
    (struct token
            (.toLowerCase raw) raw
            line-no (.start matcher) (.end matcher))))

That's it. tokenize and tokenize-str create a sequence of strings of input data. Each item in the sequence is a line in the input.

tokenize-str-seq takes that input sequence and creates a lazy sequence of the tokens from the first line and the tokens from the rest of the input sequence.

tokenize-line takes a line and constructs a lazy sequence of the tokens in it, as defined by the regex held in token-regex.

Finally, mk-token constructs the token from the regex Matcher and the line number.

If you've made it this far, you've probably got Clojure up and running, but if not, Bill Clementson has a great post on how to set up Clojure+Emacs+SLIME. In the future, he'll be exploring Clojure in more detail. He's got a lot of good posts on Common Lisp and Scheme, and I'm looking forward to seeing what he does with Clojure.

I haven't really explained about Clojure's laziness. Next, I'll talk about that.

Work in Progress, Draft 2....

2008-10-17T10:35:00.001-05:00

Is done!

This is a SF/F novel I've been working on all year.

Is it any good? Who knows? It's certainly better than my last two efforts.

For draft three, I'm just going to decide what point of view to use. I wrote it in first person, but I rewrote the first half of draft two in third-person. I'm going to read the whole thing and decide which half has more potential, and then I'll beat the other half into submission.

Then I will take a break to get some perspective on it, just in time for NaNoWriMo.

Blog Action Day

2008-10-15T12:44:00.002-05:00

Lately, I've donated some time writing for a non-profit that promotes education in India to diminish poverty, hunger, child labor, illness, and other concerns. So when I saw that the topic for Blog Action Day 2008 was poverty, I thought I'd lend my voice.

When I sat down to write this entry, I looked on the Internet for some facts to throw at you.

Then I changed my mind.

In all those numbers and percent signs, it's easy to forget that poverty has a face.

It is the man who doesn't have the livestock and knowledge to get the most from his farm, and who thus cannot provide enough food for his family.

It is the single mother who doesn't have the education and resources to support her children.

It is the child who has to work in a factory to help her family survive.

The current world economic crisis makes poverty an even more pressing concern. Bill Gates and Warren Buffer will be fine. As worried as the stock brokers and bankers are, they won't bear the full impact of the crisis. They'll be fine. I'm no Bill Gates, but I'll be fine, too, thanks for your concern.

But the economic downturn will hit first and hardest on those who already have trouble getting enough to eat each day.

I would say, "Remember them," but I don't want you to remember them. I want you to find a reputable charity, such as one of these, and give.

Now. Go. Do it.

Concordances, Part 2: Making a Plan

2008-10-15T09:18:00.001-05:00

In the last entry, I showed what a concordance looks like. Today, I'm going to talk about the changes that I'll need to make to what we already have and about what I'll need to add to the system that's here now.

Position

The biggest underlying change is that tokens will need to know their position in the input document. The system that we're building can only handle plain text documents, so I get to pretend that position is a simple concept. But it's really not. For example, in an XML document, the position could be an XPath expression.

Even for a text document, position isn't entirely clear. Is the position of a token the byte it started on in the original raw file? Is it the after-Unicode-decoding character of the token in the text of the file?

For our case, I'm going to say that the position of a token is the line number and beginning and ending character in the Unicode data of the document. This is what my example yesterday had.

Input Text

To keep track of that, instead of slurping in a file's contents all at once, I'll now need to read in each line separately and keep track of the line numbers. That shouldn't be difficult, though.

Tokens

Tokens will also need to be more than just plain strings. They'll now need to be structures that keep track of their location: file names, line numbers, and starting and ending character indices.

As an added bonus, tokens will also be able to keep track of the original form of the word, as well as a normalized or a stemmed form.

Indexing

To display the documents in alphabetical order and to pull all the occurrences of each word together easily, I'll need to index the tokens by word. The index won't be industrial-strength, really. It will probably bog down with too large of a document. Other options would be to use Lucene or store the index in a database of some form. For now, though, I'll just keep things simple.

Display

I can imagine displaying a concordance a number of different ways: text files, HTML, a GUI form. To keep the system flexible, I'm going to defer that decision until later, and the core concordance generator will just return some basic Clojure data types. I'll also add a function that prints them to the screen.

That's it. This should be a lot simpler than the Stemmer we just worked on, but it should give us a good idea of how various words are being used in the documents.

Concordances, Part 1: What's that?

2008-10-09T11:19:00.001-05:00

OK, that's enough of a break, don't you think?

Now we've got some processing tools under our belts: tokenizing and stemming. We'll tweak those, and we'll add more later. But for now let's take a look at our data.

One of the earliest ways of analyzing texts is the concordance. Simply put, it's an alphabetical list of the words used in a document, followed by every occurrence of that word, a little context around it (typically just a few words), and the location of that occurrence.

The first concordance was done in the thirteenth century for the Vulgate translation of the Christian Bible. However, because complete concordances are labor-intensive, they really weren't practical as a wide-spread tool. Because of this, concordances were only made for works deemed sufficiently important, such as religious texts or the works of Shakespeare or Chaucer.

But computers changed that. Now, given a text file, a computer can spit out a concordance in little time.

For example, here are the first few entries of a concordance of the first few paragraphs of this blog entry (although this may reflect an earlier draft). The numbers at the beginning are the line in a text file I copied the entry into and the start and end indices of the word in that line. This should give you a picture of what a concordance is, although a better one would pull context from surrounding lines. This one doesn't. Yet.

a
=
  1: 23: 24 K, that's enough of *a* break.
  5:  7:  8                take *a* look at our data.
 10: 35: 36 eren't practical as *a* wide-spread tool. B

add
===
  4: 17: 20      We'll probably *add* more later, and we'

analyzing
=========
  7: 30: 39 he earliest ways of *analyzing* texts is the [conco

and
===
  3: 66: 69 r belts: tokenizing *and* stemming.
  4: 33: 36 bly add more later, *and* we'll definitely tw

are
===
  9: 58: 61 mplete concordances *are* labor-intensive,

Next we'll analyze what we'll need to build the concordance and plan the next steps.

Stemming, Part 19: Debugging

2008-09-12T19:10:00.001-05:00

Before I leave the Porter Stemmer behind, I want to show you some of the tools I used to debug the code as I went along.

There are some more modern options for debugging Clojure than what I'm presenting here. (Search the mailing list for details.) Personally, I generally use print statements for debugging. It's primitive, but effective. In some languages, it can also be painful. Fortunately, lisp languages take much of the pain out of print-debugging.

Tracing

One common way to debug programs is to follow when a function is called and returns. This is called tracing, and this function and macro handle that.

(defn trace-call
  [f tag]
  (fn [& input]
    (print tag ":" input "-> ") (flush)
    (let [result (apply f input)]
      (println result) (flush)
      result)))

trace-call returns a new function that prints the input arguments to a function, calls the function, prints the result, and returns it. It takes the function and a tag to identify what is being traced.

(defmacro trace
  [fn-name]
  `(def ~fn-name (trace-call ~fn-name '~fn-name)))

The trace macro is syntactic sugar on trace-call. It replaces the function with a traced version of it that uses its own name as a tag. For example, this creates and traces a function that upper-cases strings:

user=> (defn upper-case [string] (.toUpperCase string))
#'user/upper-case
user=> (upper-case "name")
"NAME"
user=> (trace upper-case)
#'user/upper-case
user=> (upper-case "name")
upper-case : (name) -> NAME
"NAME"

The `debug` Macro

Another common trick in print-debugging is to print the value of an expression. The macro below evaluates an expression, prints both the expression and the result, and returns the result.

(defmacro debug
  [expr]
  `(let [value# ~expr]
     (println '~expr "=>" value#)
     (flush)
     value#))

For example:

user=> (debug (+ 1 2))
(+ 1 2) => 3
3

Lisp macros are especially helpful here, because they allow you to treat the expression both as data to print and as code to evaluate.

The `debug-stem` Function

This function is a debugging version to stem. It uses binding to replace all the major functions of the stemmer with traced versions of them.

(We'll talk more about binding later, when we deal with concurrency. Right now, just understand that binding changes the value of a top-level variable, like a function name, with a new value. But the variable only has that value for the duration of the binding. Afterward, it is returned to its former value.)

(defn debug-stem
  [word]
  (binding [stem (trace stem),
            make-stemmer (trace make-stemmer),
            step-1ab (trace step-1ab),
            step-1c (trace step-1c),
            step-2 (trace step-2),
            step-3 (trace step-3),
            step-4 (trace step-4),
            step-5 (trace step-5)]
    (stem word)))

That's it. These were the main functions I used in debugging the stemmer as I ported it from C and made it more Clojure-native.

Next up, we'll create a concordance and look at other ways of presenting the texts that we're analyzing.

By the way, I've also finally updated the repository for sample code.

I'm Ba-a-ack

2008-09-11T16:14:00.001-05:00

Boy, but doesn't life just get in the way sometimes?

On the other hand, I have also let it keep me from posting. I was getting so bored with the Clojure tutorial series. I hate to think how tired you must have been with it.

But I'm back, and I'm going to make some changes.

I've put a link to the table of contents for the Clojure tutorial in the sidebar. No matter how tired I am of it, it's still the main content on here.
I'm going to continue the Clojure tutorial, but the pace won't be quite as relentless as it was. Hopefully, I'll be able to inject a little more energy into it, and it won't be quite as boring.
I'm going to intersperse the tutorial with some other postings. I'll catch you up on what I've been doing, as well as talk about some other things that have caught my interest.

That's it. The moral: When you're getting tired, take a break and retool.

Stemming, Part 18: Processing and Testing

2008-08-07T20:56:00.001-05:00

All the pieces are in place, now here is the final piece. Also, I’ll describe how I tested this to make sure it was working correctly.

The `stem` Function

Everything that we’ve written so far happens under the hood. This function is finally the one function that will be called in other code. Without further ado, here it is.

(defn stem
  [word]
  (if (<= (count word) 2)
    word
    (apply str (-> word make-stemmer
                   step-1ab step-1c step-2 step-3 step-4 step-5
                   :word))))

If the word has one or two letters, just return it. If it is longer, use the -> macro to thread the word through make-stemmer and the steps, and extract the stem vector.

The word vector gets passed to the apply function. This is a special higher-order function that takes a function and its arguments as a sequence. It applies the arguments to the function and returns the result. Let’s look at how it works.

user=> (+ 1 2 3)
6
user=> (apply + '(1 2 3))
6
user=> (apply + 1 '(2 3))
6

You can see that only the last argument to apply has to be a sequence of arguments to pass to the function. The other arguments can be listed individually before the final sequence, and they are put before the sequence. For example, you can’t do this:

user=> (apply + 1 2 3)   
java.lang.IllegalArgumentException: Don't know how to create ISeq from: Integer

Of course, if you’re doing that, you already know how many arguments you’re calling the function with, and in that case, you should just call it as is (that is, just call (+ 1 2 3)).

So in stem, we take a word vector and pass all of the characters in it to the str function. str converts all of this arguments to a string and concatenates them.

user=> (str \w \o \r \d)
"word"
user=> (apply str [\w \o \r \d])
"word"

Well, we have a new toy now, so let’s play with it:

porter=> (stem "porter")
"porter"
porter=> (stem "porting")
"port"
porter=> (stem "ports")
"port"
porter=> (stem "ported")
"port"
porter=> (stem "stemming")
"stem"

Testing

I’ve been presenting the code here as a finished product, perfect (I guess) as written. But it didn’t begin that way. In fact, I originally wrote something very close to the C version of the algorithm and made sure that worked right. Then I gradually changed it to make it more lispy. The is the result I have presented here.

To make sure it worked correctly, I downloaded the test input data and expected output from the Porter Stemmer web site. The first file contains 23,531 words for a test set. The second contains those same words after they’ve been run through the stemmer.

Next, I wrote a function that reads from both files, stems the input, and compares it to the output. I don’t always need to test every item in the test set. Sometimes I can get by with only testing the first so many words, so I’ve included a parameter to limit how many words to test. Also, sometimes I may want to see the output from every word in the test set, but most of the time, I really only want to see the errors. Finally, this returns the total number of words tested, the number the stemmer got right, and the number it got wrong.

(defn read-lines
  [filename]
  (with-open reader (new java.io.BufferedReader (new java.io.FileReader filename))
    (doall (line-seq reader))))

(defn test-porter
  ([]
   (test-porter (.MAX_VALUE Integer) false))
  ([n output-all?]
   (loop [input (take n (read-lines "porter-test/voc.txt")),
          expected (take n (read-lines "porter-test/output.txt")),
          total 0, correct 0, error 0]
     (if (and input expected)
       (let [i (first input), e (first expected), a (stem i)]
         (if (= a e)
           (do
             (when output-all?
               (println "OK:" (pr-str i)))
             (recur (rest input)
                    (rest expected)
                    (inc total)
                    (inc correct)
                    error))
           (do
             (println "ERROR:" (pr-str i)
                      "=> (" (pr-str a) "!=" (pr-str e) ")")
             (recur (rest input)
                    (rest expected)
                    (inc total)
                    correct
                    (inc error)))))
       [total correct error]))))

The highlights of this are:

read-lines is a utility that opens a file using a Java BufferedReader and assigns that to reader. with-open always calls (. reader close) when it exits. line-seq takes a reader and returns a lazy sequence on the lines in the reader, and doall forces Clojure to read all the items in a lazy sequence. Basically, read-lines reads all the lines in a file and returns them in a sequence.
As we’ve seen before, take pulls the first n items from a list, which limits the number of words to be tested.
The loop continues while there is input from input and expected.
The input is stemmed and stored as the variable a (short for actual).
If the actual is the same as the expected, optionally output that, and loop, incrementing the number of total words tested and the number of words stemmed correctly.
If the actual and expected are not the same, always write this out and loop, incrementing the number of total words tested and the number of errors.

Tomorrow, I’ll talk about how I tracked down bugs that cropped up during testing.

Stemming, Part 17: The Final Step

2008-08-06T19:58:00.002-05:00

Today, we pick apart step five. This will involve removing the final -e and -l from words. But each of these cases will be handled in a different function.

Final E

Silent -e is one of the more, um, endearing quirks of English spelling. Invariably, whenever someone suggests spelling reform, it is the first letter on the chopping block. Stemming isn’t spelling reform, but this step does get rid of silent and final -e in all words with more than one internal consonant cluster.

(defn rule-e
  "This removes the final -e from a word if
    - there is more than one internal consonant cluster; or
    - there is exactly one final consonant cluster and
      it is not preceded by a CVC sequence.
  "
  [stemmer]
  (if (= (last (:word stemmer)) \e)
    (let [a (m stemmer)]
      (if (or (> a 1)
              (and (= a 1)
                   (not (cvc? stemmer (dec (:index stemmer))))))
        (pop-word stemmer)
        stemmer))
    stemmer))

Final L

Handling final -l just changes -ll to -l if there is more than one consonant cluster in the word. This cleans up any double-l’s that may be left around.

(defn rule-l
  "This changes -ll to -l if (> (m) 1)."
  [stemmer]
  (if (and (= (last (:word stemmer)) \l)
           (double-c? stemmer (dec (count (:word stemmer))))
           (> (m stemmer) 1))
    (pop-word stemmer)
    stemmer))

Step 5

Once again, the function for step five is pretty simple:

It pulls the word from the input stemmer and creates a new one with an index pointing to the end of the word;
It runs that through both of the functions listed above.

Again, notice that we used -> to make it easier to read.

(defn step-5
  "Removes a final -e and changes -ll to -l if (> (m) 1)."
  [stemmer]
  (-> stemmer :word reset-index rule-e rule-l))

Surprise

One quirk with this algorithm is that it sometimes removes letters from standard English words. For example, locate becomes locat. The output it produces isn’t standard, but it is correct. That is, all forms of locate collapse down to one stem: locat. So if you see a word that isn’t a word, don’t worry, it’s still correct. Remember, we’re identifying stems, not words.

Next, we’ll look at the stem function and at how to test a system like this.

Stemming, Part 16: More Suffixes

2008-08-05T20:00:00.001-05:00

Today, we’ll look at step four of the Porter stemmer. This is a little different than previous and later steps, so we’ll just focus on it today.

Utilities

Before we outline the step itself, however, we need to define another utility function. This tests whether the stemmer’s word has more than one internal consonant cluster. If it does, it strips off the ending; otherwise, it returns the original stemmer.

(defn chop
  "If there is more than one internal
  consonant cluster in the stem, this chops
  the ending (as identified by the index)."
  [stemmer]
  (if (> (m stemmer) 1)
    (assoc stemmer :word (subword stemmer))
    stemmer))

Step Four

Once chop is defined, the rest of step four pretty much defines itself. Like steps two and three, it is a cond-ends? that tests for a variety of endings and strips them off.

There is one special case: If a word ends in -ion, preceded by a -s- or -t-, the -ion is removed, but the -s- or -t- is left. You can see how that is handled about half way through step-4.

(defn step-4
  "takes off -ant, -ence, etc., in context <c>vcvc<v>."
  [stemmer]
  (cond-ends? st stemmer
              "al" (chop st)
              "ance" (chop st)
              "ence" (chop st)
              "er" (chop st)
              "ic" (chop st)
              "able" (chop st)
              "ible" (chop st)
              "ant" (chop st)
              "ement" (chop st)
              "ment" (chop st)
              "ent" (chop st)
              "ion" (if (#{\s \t} (index-char st))
                      (chop st)
                      stemmer)
              "ou" (chop st)
              "ism" (chop st)
              "ate" (chop st)
              "iti" (chop st)
              "ous" (chop st)
              "ive" (chop st)
              "ize" (chop st)))

That’s it for step four. In the posting, I’ll outline step five, which is, if anything, more like step one than steps two to four.

Stemming, Part 15: Morphological Suffix

2008-08-01T18:52:00.001-05:00

Now on to steps two and three. Here we strip off a bunch of morphological suffixes.

What Is a Morphological Suffix?

A morphological suffix changes a word from one part of speech to another. These can be joined together almost infinitely:

sense (verb)
sense + -ate = sensate (adjective)
sensate + -tion = sensation (noun)
sensation + al = sensational (adjective)
sensational + -ly = sensationally (adverb)
sensational + -ize = sensationalize (verb)

You get the idea. We could play this all day.

(I should drop in a warning here. The derivations above are purely morphological. I’m not making any statement about how a word developed historically or how it came into the language. There, I feel better. Thanks for putting up with my moment of pedantry.)

There are a set of rules to how morphological suffixes can be combined. You can’t just stick sensation and -ize together to make a verb. Also, different morphological suffixes change the stem’s root in different ways. Sense + -ate (sensate) is very different than sense + -ible (sensible), even though both -ate and -ible turn sense into an adjective.

The Porter stemmer leverages these rules to test for two different sets of endings in two different steps. The two steps are structured almost identically as two large cond-ends? expressions. In each case, they test for an ending, and if it is found, they replace it with another ending using r. The r function only makes the change if the word has an internal consonant cluster inside the stem. If it doesn’t have an internal consonant cluster, the ending is assumed to be part of the word and left alone.

For example, step 1c changes sensationally to sensationalli. Step 2 changes sensationalli to sensational.

On the other hand, the name calli, which also ends in -alli, should not be truncated to cal. Because the stemmer only truncates the ending if the stem has an internal consonant cluster, which calli does not, calli is left the way it is.

Our Functions for Today

Today, we’ll look at the functions for steps 2 and 3. As I said before, they are almost structurally identical, so I’ll show them both and comment on them together.

(defn step-2
  [stemmer]
  (cond-ends? st stemmer
              "ational" (r st stemmer "ate")
              "tional" (r st stemmer "tion")
              "enci" (r st stemmer "ence")
              "anci" (r st stemmer "ance")
              "izer" (r st stemmer "ize")
              "bli" (r st stemmer "ble")
              "alli" (r st stemmer "al")
              "entli" (r st stemmer "ent")
              "eli" (r st stemmer "e")
              "ousli" (r st stemmer "ous")
              "ization" (r st stemmer "ize")
              "ation" (r st stemmer "ate")
              "ator" (r st stemmer "ate")
              "alism" (r st stemmer "al")
              "iveness" (r st stemmer "ive")
              "fulness" (r st stemmer "ful")
              "ousness" (r st stemmer "ous")
              "fulness" (r st stemmer "ful")
              "ousness" (r st stemmer "ous")
              "aliti" (r st stemmer "al")
              "iviti" (r st stemmer "ive")
              "biliti" (r st stemmer "ble")
              "logi" (r st stemmer "log")))

(defn step-3
  "deals with -ic-, -full, -ness, etc., using
  a similar strategy to step-2."
  [stemmer]
  (cond-ends? st stemmer
              "icate" (r st stemmer "ic")
              "ative" (r st stemmer "")
              "alize" (r st stemmer "al")
              "iciti" (r st stemmer "ic")
              "ical" (r st stemmer "ic")
              "ful" (r st stemmer "")
              "ness" (r st stemmer "")))

These are nothing but cond-ends?. Each tests the input stemmer for a series of endings, and on the first ending found, it tests for an internal consonant cluster and changes the ending. If either of those conditions are false, the original stemmer is returned.

Possible Improvements

One obvious improvement would be to make a macro that takes an input stemmer and a sequence of ending/replacement pairs. It would expand into the cond-ends? above. It might look something like:

(replace-ending stemmer
                "icate" "ic"
                "ative" ""
                "alize" "al"
                "iciti" "ic"
                "ful" ""
                "ness" "")

I’ll leave that as an exercise to the reader.

In the next posting, we’ll look at stem 4, which is slightly different than steps 2 and 3.

Stemming, Part 14: Verb Endings

2008-07-31T17:48:00.001-05:00

In today’s posting, we’ll take a look at the initial step in the Porter stemmer.

An Overview

The first step in stemming tokens involves removing plural -s and verb endings -ed and -ing. It also turns -y to -i, so it will be recognized as a suffix in later steps. The documentation in the C source code lists some examples:

caresses -> caress ponies -> poni ties -> ti caress -> caress cats -> cat feed -> feed agreed -> agree disabled -> disable matting -> mat mating -> mate meeting -> meet milling -> mill messing -> mess meetings -> meet

Plurals

The first step is to strip off plurals. If the word ends in a -sses or -ies, this removes the -es; otherwise, if it ends in -s, but not -ss, it takes off the -s. If none of those apply, it returns the original stemmer.

(defn stem-plural
  "This is part of step 1ab. It removes plurals (-s) from a stem."
  [stemmer]
  (if (= (last (:word stemmer)) \s)
    (cond-ends? st stemmer
      "sses" (reset-index (pop (pop (:word st))))
      "ies" (set-to st "i")
      :else (if (and (>= (count (:word st)) 2)
                     (not= (nth (:word st) (- (count (:word st)) 2))
                           \s))
              (assoc st :word (pop (:word st)))
              st))
    stemmer))

It’s been a while since we’ve seen some of these functions. Here are a few reminders about what they do:

reset-index returns a new stemmer from a word vector (here with the last two letters removed from the word).

set-to removes the -ies from the end of the word and replaces it with an -i.

cond-ends? is the macro we created in the last few postings. I just wanted to point that out.

Verb Endings

Another part of step 1 involves removing the verb suffixes -ed and -ing from the word. It first looks for -eed if it is long enough (that is, if it has more than one internal sequence of consonants), it removes the -d; if it ends in -ed, it removes that; and if it ends in -ing, it removes that. In either of the last two cases, it also expands truncated suffixes.

Expanding suffixes just tests for certain endings and, if they are found, appends an -e to the word. Specifically, it looks for -at, -bl, and -iz. It also checks for a double-consonant ending. Some are all right in English (-ll, -ss, and -zz), but most others should be removed. Finally, it removes the final consonant in words that end in CVC (with exceptions). This process is handled by the stem-expand-suffix function, which is listed first.

(defn stem-expand-suffix
  "This is part of step 1ab. It expands -at, -bl,
  and -iz by adding an -e in certain circumstances."
  [stemmer]
  (cond-ends? st stemmer
    "at" (set-to st "ate")
    "bl" (set-to st "ble")
    "iz" (set-to st "ize")
    :else (cond
            (double-c? st (dec (count (:word st))))
              (if (#{\l \s \z} (last (:word st)))
                st
                (assoc st :word (pop (:word st))))
            (and (= (m st) 1) (cvc? st (dec (count (:word st)))))
              (set-to st "e")
            :else
              st)))

(defn stem-verb-ending
  "This is part of step 1ab. It removes verb endings -ed
  and -ing."
  [stemmer]
  (cond-ends? st stemmer
    "eed" (if (pos? (m st))
            (assoc st :word (pop (:word st)))
            stemmer)
    "ed"  (if (vowel-in-stem? st)
            (stem-expand-suffix (assoc st :word (subword st)))
            stemmer)
    "ing" (if (vowel-in-stem? st)
            (stem-expand-suffix (assoc st :word (subword st)))
            stemmer)))

double-c? returns true if the word ends in a double consonant. For example, -ll or -ss or something.

cvc? returns true if the word ends in a consonant-vowel-consonant sequence and if the final consonant is not w, x, or y.

m returns the number of consonant sequences between the start of a word and the index position. But if the word starts with a consonant sequence, it isn’t counted.

Step 1AB

The actual function for step 1AB (A calls stem-plural and B calls stem-verb-ending) is simple. It just passes its input through the two functions:

(defn step-1ab
  [stemmer]
  (stem-verb-ending (stem-plural stemmer)))

One thing about functional languages is that they often have to be read from right to left. The stemmer gets passed to stem-plural first and stem-verb-ending second. The way it is written, however, is counter-intuitive, and it makes functional languages harder to read.

Clojure provides an improvement to this. It uses the -> macro to build expressions like above. Let’s spend some time understanding what this macro does, first by using it and then by looking at the expressions it outputs.

The first parameter to -> is an expression. The remaining parameters are functions. The expression parameter gets passed as the first parameter to the first function, and the output of this gets passed as the first parameter to the second function parameter. This continues until all the functions have been chained together.

To play with this, let’s define some functions that operate on strings.

porter=> (defn to-lower-case [string] (.toLowerCase string))
#'porter/to-lower-case
porter=> (defn trim [string] (.trim string))
#'porter/trim
porter=> (trim (to-lower-case "   ThIs NeEdS ClEaNiNg  "))
"this needs cleaning"

If we make that last call with ->, it looks like this:

porter=> (-> "   ThIs NeEdS ClEaNiNg   " to-lower-case trim)
"this needs cleaning"

This is really handy if there aren’t any other arguments. But what if you want to use a function that needs more than one argument. As long as the first argument is the expression parameter or the result of the previous function in the sequence, it’s no problem. Just enclose the function and the remaining parameters to that function in parentheses. For example, this defines a wrapper for String.substring that returns everything from the second parameter on.

porter=> (defn substring [string index] (.substring string index))
#'porter/substring
porter=> (-> "   ThIs NeEdS ClEaNiNg   " to-lower-case trim (substring 11))
"cleaning"

We can see what this does using macroexpand-1:

porter=> (macroexpand-1 '(-> "   ThIs NeEdS ClEaNiNg   " to-lower-case trim (substring 11)))
(clojure/-> (clojure/-> "   ThIs NeEdS ClEaNiNg   " to-lower-case) trim (substring 11))

Umm. It changed, but not by much. Let’s just take the inner, second -> and try expanding it:

porter=> (macroexpand-1 '(-> "   ThIs NeEdS ClEaNiNg   " to-lower-case))
(to-lower-case "   ThIs NeEdS ClEaNiNg   ")

That seems like a normal function call. If we keep breaking it down, we get this:

(substring (trim (to-lower-case "   ThIs NeEdS ClEaNiNg   ")) 11)

Which is what we want and expect.

Now, we can rewrite step-1ab to use this macro and be much more readable.

(defn step-1ab
  "step-1ab gets rid of plurals and -ed or -ing. E.g.,
    caresses -> caress
    ponies -> poni
    ties -> ti
    caress -> caress
    cats -> cat
    feed -> feed
    agreed -> agree
    disabled -> disable
    matting -> mat
    mating -> mate
    meeting -> meet
    milling -> mill
    messing -> mess
    meetings -> meet
  "
  [stemmer]
  (-> stemmer stem-plural stem-verb-ending))

Step 1C

The rest of step one just tests to see if the word ends in -y. If it does, and if there is a vowel in the stem, it removes the -y and adds a -i to the word.

(defn step-1c
  "Turns terminal y to i when there is another vowel in the stem."
  [stemmer]
  (if-ends? st stemmer "y"
            (if (vowel-in-stem? st)
              (reset-index (conj (pop (:word st)) \i))
              stemmer)))

That’s pretty straightforward. It uses if-ends? to test for the -y, and vowel-in-stem? looks for a vowel before the -y. If either of these is not the case, the original stemmer is returned.

Those two functions comprise step 1. In the next posting, we’ll look at the next several steps.

Stemming, Part 13: The Steps for Processing

2008-07-29T18:46:00.001-05:00

We finally have all the pieces in place to actually put the Porter stemmer together. But it’s been so long, I’ve certainly forgotten what goes next, so let’s take a moment to remember where we are going with this.

Earlier I outlined the process that the stemmer will perform in five steps:

Get rid of plurals, -ed, and -ing, and turn -y to -i, so it will be recognized as a suffix in later steps;

Collapse multiple suffixes, such as -ational, -ator, -iveness, and others, to a single suffix, such as -ate, -ate, and -ive, respectively;

Collapse a different set of multiple suffixes or remove a small set of single suffixes;

Remove a set of suffixes including -ance, -ic, and -ive; and

Remove final -e and change -ll to -l in some circumstances.

In the next posting, we’ll pick apart what needs to be done for step 1.

(Sorry this posting isn’t longer. I’m still taking a breath after the macro death march.)

Stemming, Part 12: Macros and Moving on

2008-07-28T18:10:00.001-05:00

All right, let’s review what we’ve been doing for the last few days.

What Have We Done?

In a real sense, we’ve been writing a program that writes programs. A macro is a function that accepts Clojure code—represented as lists, vectors, symbols, strings, numbers, and other Clojure data types—and returns another list, vector, etc., that represents Clojure code. A macro can change its input any way it wants to, but of course the output needs to be valid Clojure code.

Creating Abstractions

All computer languages allow us to make abstractions. We can abstract the data “given-name,” “surname,” “age,” and “address” into a class (or structure in Clojure) called “Person.” We can abstract the action of printing “Greeting” and a person’s name into the function “hello-world.” All languages in common use let us do that. Object-oriented languages also give us other abstractions for associating actions with data.

But lisps, including Clojure, go a step beyond that. They allow us to create abstractions of the syntax of the language. This allows us to control when and how expressions get executed.

Does this allow us to do things we cannot do in other languages? Strictly speaking, no.

But it allows us to do things more concisely and readably than we otherwise could. But because we can abstract more things away and worry less about them, we can build and understand programs that are more complex than we otherwise could be able to comprehend.

Domain Specific Languages

Another benefit of macros is that they allow us to create a mini-language with Clojure. If you look at Clojure’s source code, most of it is written in Clojure. And you have that same power. Once written, your code isn’t really that different than the code that makes up Clojure’s core.

You can use that ability to extend Clojure, to build up from its foundation, to create your own language ideally suited to the work you need to do.

You can do this in other languages, of course. It’s called creating domain specific languages. But in lisp, it is natural in a way it is in no other language.

The Spiderman Clause

Of course, as Peter Parker was told, “With great power comes great responsibility.” Like operator overloading or multiple inheritance, macros make it easy for you to shoot yourself in the foot. If you’re not careful, you can create something that is so far from Clojure that others have trouble understanding it, and you will have trouble getting your bearings when you come back to it in six months.

Remember: a little macros go a long way.

In the next posting, we’ll finally start on the steps involved in stemming.

Stemming, Part 11: the cond-ends? Macro

2008-07-25T16:09:00.001-05:00

In the last posting, we created the macro if-ends?, which was a combination of let, if and the function ends?. Today, we’ll look at another similar macro, one that combines let, cond, and ends?.

The Purpose of cond-ends?

The problem with if-ends? is that sometimes we’ll want to look for twenty or more different endings on a single stemmer and handle each case differently. We can do that with if-ends?, but it would be a lot cleaner if we had a construct like cond.

Input Patterns

For example, we might want to do something like this:

(cond-ends? st (make-stemmer "names")
  "ing" (do (println "ends with -ing") st)
  "ed" (do (println "ends with -ed") st)
  "s" (do (println "ends with -s") st)
  :else (do (println "no ending") st))

First, notice that this starts out like if-ends?. It has a variable (st) that the new stemmer will be assigned to, followed by a stemmer instance to test.

These are followed by a series of ending/expression pairs. The endings are tested one by one until a match is found. Once it is, the expression following that ending is executed with the variable st available to it and assigned to the new stemmer, with the index changed to reflect the ending. The return value of that expression is the value of the entire cond-ends? expression.

Finally, if no ending matches, the cond-ends? should return the original stemmer unchanged. Or, optionally, the last ending can be the keyword :else. If no ending before that point matched, the expression following :else is executed and its value returned.

Before we start on the expected output for this macro, let’s look at a short expression that uses the default value if no ending matches:

(cond-ends? st (make-stemmer "names")
  "ing" (do (println "ends with -ing") st))

Of course, that would be better expressed with if-ends?, but using it as an input pattern will help us build the default ending.

Output Patterns

Here’s what the macro should construct from the input above.

;(cond-ends? st (make-stemmer "names")
;  "ing" (do (println "ends with -ing") st)
;  "ed" (do (println "ends with -ed") st)
;  "s" (do (println "ends with -s") st)
;  :else (do (println "no ending") st))
;; Set up the environment
(let [stemmer# (make-stemmer "names"),
      word# (subword stemmer#)]
  ;; -ing
  (let [j# (- (count word#) 3)]
    (if (and (pos? j#) (= (subvec word# j#) [\i \n \g]))
      (let [st (assoc stemmer# :index (dec j#))]
        (do (println "ends with -ing") st))
      ;; -ed
      (let [j# (- (count word#) 2)]
        (if (and (pos? j#) (= (subvec word# j#) [\e \d]))
          (let [st (assoc stemmer# :index (dec j#))]
            (do (println "ends with -ed") st))
          ;; -s
          (let [j# (- (count word#) 1)]
            (if (and (pos? j#) (= (subvec word# j#) [\s]))
              (let [st (assoc stemmer# :index (dec j#))]
                (do (println "ends with -s") st))
              ;; :else
              (let [st stemmer#]
                (do (println "no ending") st)))))))))

That’s scary.

Actually, it’s not that bad. Notice that after the first let, it is a series of (let ... (if ...)) constructions. (I’ve added comments to separate each of these sections.) Each of those three let/if constructions are almost identical, until the :else expression. Also, notice that I’ve not only pre-compiled the vector itself, but also the length of the vector, and I’ve inserted them into the result example as their literal values. (Pre-computing the length of the vector was suggested by Holger Durer in the comments to the last posting.)

Before we start writing the macro, let’s look at the expected output for the second example above.

;(cond-ends? st (make-stemmer "names")
;  "ing" (do (println "ends with -ing") st))
;; Set up the environment
(let [stemmer# (make-stemmer "names"),
      word# (subword stemmer#)]
  ;; -ing
  (let [j# (- (count word#) 3)]
    (if (and (pos? j#) (= (subvec word# j#) [\i \n \g]))
      (let [st (assoc stemmer# :index (dec j#))]
        (do (println "ends with -ing") st))
      ;; default :else
      stemmer#)))

One of the things to notice about these output expressions is that a lot of the state for it can be computed once, and used throughout all the conditionals in the cond-ends? body. That observation will be useful later.

The Macro

Looking at the output above, we really have three tasks: set up the environment for the cond-ends? in the outer let; for each test generate a let/if construction; and finally generate an :else value, maybe using the default.

One way to tackle this problem would be to separate it into two macros:

One macro sets up the environment and calls another macro to build the test expressions;
The second macro builds one let/if pair, similar to what if-ends? did, for one test expression, then it calls itself on the rest of the test expressions. It does this until it reaches the last test expression and that test is :else or until it is out of test expressions.

Let’s start with the second macro. That will allow us to see what the first macro needs to provide to the test macro, and it has to be defined first anyway, because that’s the way Clojure likes things.

Generating the Tests

The test macro will be overloaded. Either it will take one ending/expression pair, or it will take many. If there is only one, the ending could be an :else, or it could be the last ending to test for, and the :else will be a default. So the first, shorter version of this will return one of these two constructions (taken from above):

  ;;; With :else
              ;; :else
              (let [st stemmer#]
                (do (println "no ending") st))

  ;;; With a test + the default :else
  ;; -ing
  (let [j# (- (count word#) 3)]
    (if (and (pos? j#) (= (subvec word# j#) [\i \n \g]))
      (let [st (assoc stemmer# :index (dec j#))]
        (do (println "ends with -ing") st))
      ;; default :else
      stemmer#))

Another point to make about the test expressions is that—as an astute commenter pointed out (thanks, Holger)—there is a lot of duplication between the two versions of the macro that builds the expressions. We can capture that duplication in a function and just call that function with the difference between the two structures. The function will then create the macro’s output structure.

All right. Let’s roll up our sleeves. The helper function will be called make-cond-ends-test. It take the variable symbol, the stemmer variable, an ending string, a true expression, and a false expression.

(defn make-cond-ends-test
  [var stemmer word end true-expr false-expr]
  (let [vend (vec end)]
    `(let [j# (- (count ~word) ~(count vend))]
       (if (and (pos? j#) (= (subvec ~word j#) ~vend))
         (let [~var (assoc ~stemmer :index (dec j#))]
           ~true-expr)
         ~false-expr))))

Notice that this function requires several parameters beyond the ending (end) and the result expressions (true-expr and false-expr)? It also has var, stemmer, and word. But the stemmer and the subword should have been stored in variables in the first, outer let by this point. That’s right. In this function, these are the variables that those values were stored in, represented here as symbols. Throughout this helper function, ~stemmer inserts the variable that the stemmer will have been assigned to in the outer let.

Now we can define the secondary macro. We’ll call it cond-ends-helper, because I’m not feeling creative. It’s main purpose is to examine the input and call make-cond-ends-test with the appropriate false expression. The first overload for it will handle the last expression by testing for :else and deciding whether to use the default :else:

(defmacro cond-ends-helper
  "This helps cond-ends? by processing the "
  test-exprs pairs in cond-ends?'s environment."
  ([var stemmer word end true-expr]
   (if (= end :else)
     `(let [~var ~stemmer]
        ~true-expr)
     (make-cond-ends-test var stemmer word end true-expr stemmer)))
  ;; The overload will go here ...
  )

What happens here? First, at compile time (before the quasi-quote or call to make-cond-ends-test), it tests whether the ending is :else. If it is, it just outputs the shorter version of the ending. If it isn’t :else, it calls the helper function, with all the same parameters plus the false expression as a data structure. In this case, the false expression is the stemmer variable.

If your head is starting to hurt, take a moment. Unless you have programmed in lisp before, this isn’t like any programming you’ve ever done. We’re writing a program to write programs. Like any meta-activity, it can make your brain explode. Unfortunately, this is a particularly convoluted macro, because it has these two levels of macro, plus a function. Don’t worry if you don’t quite get it at first. There’s nothing wrong with copying and pasting the macro’s code into your source file and moving on. Start building macros like debug and if-ends?, and when you’re comfortable there, come back and read this through again. It will make a lot more sense.

Now, if you’re still with me, here’s the overloaded version of the helper macro. This takes an ending/expression pair and a list of the rest of the pairs in the expression. It then calls make-cond-ends-test with a new version of

(defmacro cond-ends-helper
  "This helps cond-ends? by processing the
  test-exprs pairs in cond-ends?'s environment."
  ;; The earlier override goes here....
  ([var stemmer word end true-expr & more]
   (make-cond-ends-test
      var stemmer word end true-expr
      `(cond-ends-helper ~var ~stemmer ~word ~@more))))

In some ways, this part of cond-ends-helper is much simpler. There are just a few things to comment on.

In the parameter list, & more collects the values of the rest of the parameters and stores them in a variable I’ve named more. This works with functions too.
The false expression that this passes to make-cond-ends-test begins with a quasi-quote (back quote). This just generates an expression to pass as the false expression. This expression gets inserted into the expression that make-conds-ends-test creates.
This quasi-quoted expression, when finally evaluated, is a macro call to the macro that created it. It starts the process all over again, passing the new macro expansion the values of var, stemmer, and word unchanged, and splicing all of the rest of the parameters that haven’t been handled yet into the expression using ~@more.

Creating the Environment

So we know that the cond-ends? sets up the environment by creating an expression like this:

;; Set up the environment
(let [stemmer# (make-stemmer "names"),
      word# (subword stemmer#)]
  ; ...
  )

And it replaces the ellipses by calling the macro cond-ends-helper with the variable and the variables stemmer# and word#. Put like that, it almost writes itself.

(defmacro cond-ends?
  "This is the same as a stacked series of if-ends?.
  This just sets up the environment for cond-ends-helper."
  [var stemmer & test-exprs]
  `(let [stemmer# ~stemmer, word# (subword stemmer#)]
     (cond-ends-helper ~var stemmer# word# ~@test-exprs)))

Notice that we use & test-exprs to collect all of the test expressions, and we use ~@test-exprs to splice them into the cond-ends-helper call.

Summary

For posterity’s sake, here is all the code for the cond-ends? macro, in one place:

(defn make-cond-ends-test
  [var stemmer word end true-expr false-expr]
  (let [vend (vec end)]
    `(let [j# (- (count ~word) ~(count vend))]
       (if (and (pos? j#) (= (subvec ~word j#) ~vend))
         (let [~var (assoc ~stemmer :index (dec j#))]
           ~true-expr)
         ~false-expr))))

(defmacro cond-ends-helper
  "This helps cond-ends? by processing the
  test-exprs pairs in cond-ends?'s environment."
  ([var stemmer word end true-expr]
   (if (= end :else)
     `(let [~var ~stemmer]
        ~true-expr)
     (make-cond-ends-test var stemmer word end
                          true-expr stemmer)))
  ([var stemmer word end true-expr & more]
   (make-cond-ends-test
      var stemmer word end true-expr
      `(cond-ends-helper ~var ~stemmer ~word ~@more))))

(defmacro cond-ends?
  "This is the same as a stacked series of if-ends?.
  This just sets up the environment for cond-ends-helper."
  [var stemmer & test-exprs]
  `(let [stemmer# ~stemmer, word# (subword stemmer#)]
     (cond-ends-helper ~var stemmer# word# ~@test-exprs)))

In the next posting, I’ll to wrap up macros by pointing out how they’re used and why.

Stemming, Part 10: The if-ends? Macro

2008-07-22T20:07:00.001-05:00

For the last two postings, we’ve looked at macros. Today, we’ll finally put them to use for the Porter Stemmer. Remember that we’re looking to simplify the ends? function, so let’s start by reviewing it.

The ends? Function

The ends? function tests whether a stemmer ends with a given suffix. If it does, it moves the working :index to exclude that ending. If it does not, it leaves the :index where it was originally. Moveover, code that calls ends? needs to know whether that ending was found or not. If it was, it may want to take special action; if it wasn’t, it may want to test the stemmer against another ending. Currently, ends? returns a vector containing the resulting stemmer (which may be the original one) and a flag indicating whether the ending was found or not:

(defn ends?
  "true if the word ends with s."
  [stemmer s]
  (let [word (subword stemmer),
        sv (vec s),
        j (- (count word) (count sv))]
    (if (and (pos? j) (= (subvec word j) sv))
      [(assoc stemmer :index (dec j)) true]
      [stemmer false])))

A quick explanation:

(subword stemmer) is the part of word before the working index;
(vec s) turns the ending into a vector, if it isn’t already; and
(- (count word) (count sv)) is the index where the ending starts in the word. It will be the new value of the working index if the ending is found.

First, this tests whether the ending is shorter than the word and whether the word ends with the ending. If both are true, it returns a new stemmer with the working index (:index) set to the position just before the ending in the word.

Let’s see what how what calling it looks like.

porter=> (ends? (make-stemmer "walking") "ing")
[{:word [\w \a \l \k \i \n \g], :index 3} true]
porter=> (ends? (make-stemmer "walking") "s")
[{:word [\w \a \l \k \i \n \g], :index 6} false]

The Purpose of if-ends?

The reason why we want to use a macro in place of a function for ends? is because returning the extra value, the flag indicating whether the ending was actually found, is messy. Instead, we want something like an if statement. We want a conditional that tests whether a stemmer ends with a suffix, but instead of returning true or false, it executes a different expression, depending on the result of ends?.

Another wrinkle is that we’ll want to have access to the newly created stemmer in the true- or false-expressions. In this sense, if-ends? is like a let. We need to provide a variable that will be used in the bodies of the true- and false-expressions. The altered stemmer will be assigned to it.

Sample Inputs

What would calling this look like? Here are some examples:

(if-ends? x (make-stemmer "names") "s"
  (println x "YES: had a plural suffix")
  (println x "NO : never had a plural suffix"))

(if-ends? x (make-stemmer "walking") "ing"
  (println "with -ing:" x)
  (println "without -ing:" x))

(if-ends? x (make-stemmer "walked") "ed"
  x)

From these expressions, we can see that if-ends? will need to take five or six parameters:

The variable that the resulting stemmer will be assigned to and that can be used in the body expressions of the if-ends?. In all of these expressions, that variable is x.
The next parameter is the input stemmer. This could be an expression, as it is here, so we’ll need to evaluate this first and store it in a variable.
Next is the ending.
Next is the expression to evaluate if the stemmer does end with the ending. In it, the altered stemmer is assigned to the variable name given in the first parameter.
Finally, the last parameter is the expression to evaluate if the stemmer does not end with the ending. Just as with if, this branch is optional. If it is not given, whatever expression the if-ends? creates should the original, unchanged stemmer.

Sample Outputs

Given these constraints, what would the output for each of these if-ends? look like?

;(if-ends? x (make-stemmer "names") "s"
;  (println x "YES: had a plural suffix")
;  (println x "NO : never had a plural suffix"))
(let [stemmer-var (make-stemmer "names"),
      end-var (vec "s"),
      word-var (subword stemmer-var),
      j-var (- (count word-var) (count end-var))]
  (if (and (pos? j-var) (= (subvec word-var j-var) end-var))
    (let [x (assoc stemmer-var :index (dec j-var))]
      (println x "YES: had a plural suffix"))
    (let [x stemmer-var]
      (println x "NO : never had a plural suffix"))))

(Here I’ve used -var in place of the # ending.)

First, this assigns the input stemmer and ending to temporary variables. Second, it assigns word-var and j-var to values, just as ends? does. Finally, it performs the test. In either branch, it uses a let to assign stemmer—new or old—to the variable x. Finally, it inserts the body of the branch expression into each branch.

;(if-ends? x (make-stemmer "walking") "ing"
;  (println "with -ing:" x)
;  (println "without -ing:" x))
(let [stemmer-var (make-stemmer "walking"),
      end-var (vec "ing"),
      word-var (subword stemmer-var),
      j-var (- (count word-var) (count end-var))]
  (if (and (pos? j-var) (= (subvec word-var j-var) end-var))
    (let [x (assoc stemmer-var :index (dec j-var))]
      (println "with -ing:" x))
    (let [x stemmer-var]
      (println "without -ing:" x))))

:::clj
;(if-ends? x (make-stemmer "walked") "ed"
;  x)
(let [stemmer-var (make-stemmer "walked"),
      end-var (vec "ed"),
      word-var (subword stemmer-var),
      j-var (- (count word-var) (count end-var))]
  (if (and (pos? j-var) (= (subvec word-var j-var) end-var))
    (let [x (assoc stemmer-var :index (dec j-var))]
      x)
    stemmer-var))

The last output shows what it should return when the optional false-expression is omitted.

Writing the Macro

Actually, let’s start writing the macro with the shorter version. You can overload a macro’s parameter list just as you do with functions. Just enclose each set of parameters and body in its own set of parentheses.

(defmacro if-ends?
  "Instead of the function ends?, I'm using this:
  (if-ends? x (make-stemmer \"names\") [\\s]
            (println x \"no longer has a plural suffix\")
            (println x \"never had a plural suffix\"))
  "
  ([var stemmer end true-expr]
   `(let [stemmer# ~stemmer,
          end# ~(vec ~end),
          word# (subword stemmer#),
          j# (- (count word#) (count end#))]
      (if (and (pos? j#) (= (subvec word# j#) end#))
        (let [~var (assoc stemmer# :index (dec j#))]
          ~true-expr)
        stemmer#)))
  ;; ... the full version of if-ends? goes here
  )

This is a fairly straightforward transformation. The -var variables are replaced with their # counterparts. Otherwise, the parameters are inserted into the macro result with tilde expansion (~expression).

The full version of if-ends?.

(defmacro if-ends?
  ;; ... the short version of if-ends? goes here
  ([var stemmer end true-expr false-expr]
   `(let [stemmer# ~stemmer,
          end# ~(vec ~end),
          word# (subword stemmer#),
          j# (- (count word#) (count end#))]
      (if (and (pos? j#) (= (subvec word# j#) end#))
        (let [~var (assoc stemmer# :index (dec j#))]
          ~true-expr)
        (let [~var stemmer#]
          ~false-expr)))))

Compile-Time Optimization

We’ve got all the pieces in place, but we’re still not quite finished. Let’s make one assumption about our input, an assumption that will hold as we use this macro in the stemmer code. This will allow us to make an optimization that also leverages one of the advantages of macros: they are expanded at compile-time.

The assumption is this: the ending will always be a string literal. That is, we will always start if-ends? like this:

(if-ends? v stemmer "ing" ...)

"ing" will get passed to the macro as a string literal, and we can convert it to a vector when the macro is translated at compile time. In the macros that I’ve outlined above, the ending is converted to a vector in the outer let. But we could also move it to a new let outside the macro expansion expression. The value of that pre-converted ending is used in the macro result.

With this optimization, the entirety of if-ends? looks like this:

(defmacro if-ends?
  "Instead of the function ends?, I'm using this:
  (if-ends? x (make-stemmer \"names\") [\\s]
            (println x \"no longer has a plural suffix\")
            (println x \"never had a plural suffix\"))
  "
  ([var stemmer end true-expr]
   (let [vend (vec end)]
     `(let [stemmer# ~stemmer,
            end# ~vend,
            word# (subword stemmer#),
            j# (- (count word#) (count end#))]
        (if (and (pos? j#) (= (subvec word# j#) end#))
          (let [~var (assoc stemmer# :index (dec j#))]
            ~true-expr)
          stemmer#))))
  ([var stemmer end true-expr false-expr]
   (let [vend (vec end)]
     `(let [stemmer# ~stemmer,
            end# ~vend,
            word# (subword stemmer#),
            j# (- (count word#) (count end#))]
        (if (and (pos? j#) (= (subvec word# j#) end#))
          (let [~var (assoc stemmer# :index (dec j#))]
            ~true-expr)
          (let [~var stemmer#]
            ~false-expr))))))

Here, in both versions of if-ends?, we first convert the ending to a vector and assign it to vend. Inside the macro expansion expression, vend is what gets assigned to end#. Clojure calculates vend when the macro is expanded at compile time. The time saved by the optimization won’t be much, but it does illustrate another benefit of macros.

This simplifies things a lot, but it doesn’t cover all the use cases for ends?. We will also want to use it in a nested set of twenty or more comparisons. That is less like an if and more like a cond expression. In the next posting, we’ll create cond-ends?.

Stemming, Part 9: Writing Macros

2008-07-21T19:14:00.001-05:00

In the last posting, I introduced macros. Today, I’m going to point out some of the pitfalls in writing macros and suggest a method for writing them that help you avoid those potential problems.

To illustrate these issues, let’s take a look at a simplified, incorrect version of the debug macro from the last posting:

(defmacro debug
  [expr]
  `(do
     (println '~expr "=>" ~expr)
     ~expr))

Superficially, this version appears to work correctly. At least, if you try it out, it seemed to work:

user=> (debug (+ 1 2))
(+ 1 2) => 3
3

Recomputing Values

The first problem with debug as given above can best be illustrated by passing it an expression that has a side-effect, such as a println expression.

user=> (debug (println "Count Me!"))
Count Me!
(println Count Me!) => nil
Count Me!
nil

“Count Me!” gets printed twice. That’s because the expression’s getting executed twice: once when its value is printed and once when its value is being returned. In this case, that might be fine, but imagine if the value took a long time to compute or if it deleted a file or inserted a new value into the database. The macro would take twice as long to run; it would cause an error when it tried again to delete a file it had just deleted; or it would insert a value into the database twice. None of those are good options.

Instead of having the value computed twice, we need it to be computed only once. We can get that by added a let to the macro that computes the expression’s value once and stores it in a variable.

(defmacro debug
  [expr]
  `(let [value ~expr]
     (println '~expr "=>" value)
     value))

Now if we try it again:

user=> (debug (println "Count Me!"))
java.lang.Exception: Can't let qualified name: user/value

Hmm. That introduces the second type of error.

Variable Capture

Basically, Clojure was complaining because macros return symbols that are attached to a namespace (user, in this case). But variables have to exist outside of any namespace. To fix it, we change value to use the # variable notation I mentioned in the last posting.

(defmacro debug
  [expr]
  `(let [value# ~expr]
     (println '~expr "=>" value#)
     value#))

Let’s try it out.

user=> (debug (println "Count Me!"))
Count Me!
(println Count Me!) => nil
nil

There. That fixed both problems. Now it only evaluates the expression once, and it won’t clobber any variables from the surrounding context. Now it’s correct.

Writing Macros

So how do we go about writing macros that are correct?

Input Examples

First, create several examples of what you want the input to look like. For the debug macro, that might look like:

(debug name)
(debug (+ 1 2))
(debug (:name person))

Make sure to include many different types of input parameters. In the debug macro, the first problem—recomputing values—won’t appear if you always pass it a variable or another expression that doesn’t require computation. This is just good development and testing: test thoroughly.

Output Examples

Next, for each input expression, write what you want the corresponding output expression to be:

;(debug name)
(let [n# name]
  (println 'name "=>" n#)
  n#)

;(debug (+ 1 2))
(let [value# (+ 1 2)]
  (println '(+ 1 2) "=>" value#)
  value#)

;(debug (:name person))
(let [value# (:name person)]
  (println '(:name person) "=>" value#)
  value#)

Write the Macro

Now that we have the pairs of input and output, we can write a macro that converts the first expression into the second. The result is what we had in the last posting:

(defmacro debug
  [expr]
  `(let [value# ~expr]
     (println '~expr "=>" value#)
     (flush)
     value#))

(The flush function just makes sure that the expression is written out immediately. Otherwise, the computer might sit on it for a while.)

As you write the macro, think about the two common macro mistakes I outlined above.

Debugging

Of course, occasionally you might make a mistake. You can see what expression a macro produces using the macroexpand-1 function:

user=> (macroexpand-1 '(debug (+ 1 2)))
(clojure/let [value__3063 (+ 1 2)]
  (clojure/println (quote (+ 1 2)) "=>" value__3063)
  (clojure/flush)
  value__3063)

(I’ve broken the lines up to make them more readable.)

Examining the output of macroexpand-1 should make it clear where the problem is.

In the next posting, we’ll create a macro to use in place of the ends? function.

Stemming, Part 8: Macros

2008-07-18T16:42:00.001-05:00

At the end of the last posting, I mentioned that we could probably simplify the ends? function. Currently, it returns a vector with the result and a boolean indicating whether it had been changed.

Data as Code

Compared to most programming languages, Clojure (and lisp) programs are odd: Functions and expressions look like lists; parameter lists for functions or let expressions look like vectors; variables look like symbols.

In fact, those programming constructs start their lives as those data structures. Remember that our interactive environment is called a REPL—a read, evaluate, and print loop. In the read stage, a function or expression is read in as a list, vector, symbol, string, or number. It’s not actually compiled into computer code until the evaluate stage. Before then, it’s all data.

This characteristic of Clojure—that programs are data—is called homoiconicity. Part of what makes lisp so powerful and special is that it introduces a new step in the evaluation process. In most computer languages, the computer reads in an expression and immediately turns it into an action or byte code or whatever. In lisp, the computer reads in the expression as a native lisp data structure, and before it processes the data, it asks the programmer again how it should be handled.

This makes more sense with an example. Consider the Clojure built-in when. You’ll recall that when is just like if, except that the true expression can be a sequence of expressions and the false expression doesn’t exist. Consider this when expression:

user=> (when (= (nth "abc" 1) \b)
         (println "b")
         \b)
b
\b

(println prints its arguments, separated by spaces, and followed by a new line.)

The first “b” is what is printed. The “b” is the value returned by the when expression, from the third line of the expression.

Of course, that when expression is the same as this if expression:

user=> (if (= (nth "abc" 1) \b)
         (do
           (println "b")
           \b))
b
\b

(do just executes a list of expressions and returns the value of the last one. It’s a way of taking a sequence of expressions and using them in places that only want one expression.)

In fact, the when expression is exactly equal to the if expression. Clojure reads the when expression and transforms it into the if expression before evaluating it.

How is this done and how can we create our own code transformations?

Macros.

Code Transformations

A macro is a code transformation. If you know XSLT, a macro transforms a Clojure expression in almost the same way as XSLT transforms an XML document. (If you don’t know XSLT, forget I mentioned it.)

A macro definition looks a lot like a function definition. It has a macro name and a vector of parameters. But macros start with the symbol defmacro, and the body of the macro has a template that builds the output expression.

Here are the tools you use to create the template.

Quote

A quote tells Clojure to return the next expression as data, exactly the way it is written, not as an expression or as a macro template. For example, the first let evaluates x before returning, but the quote in the second let means that Clojure returns the symbol x, not the value that the variable x evaluates to.

user=> (let [x 1] x)
1
user=> (let [x 1] 'x)
x

Quasi-Quote

A quasi-quote is a back-quote character. It indicates that, when the macro is called, the expression it quotes should be scanned for the constructs below, and the list or expression generated should be returned. Except for the scanning bit, it’s a lot like a regular quote.

user=> `(let [x 1] x)
(clojure/let [user/x 1] user/x)

Tilde

Inside a macro template, a tilde forces Clojure to evaluate the expression that follows it and insert its value into that place in the result.

user=> (let [x 2]
         `(let [y ~x] y))
(clojure/let [user/y 2] user/y)

In this, the outer let sets x to 2. Inside that let, it defines a macro template, which returns a list that looks like another let expression. Inside the inner let it inserts the value of x from the outer let.

In many ways, macro templates are shortcuts for longer expressions that build lists and vectors. For example, the last expression is the same as this expression, using functions to build the output expression:

user=> (let [x 2]
         (list 'let (vector 'y x) 'y))
(let [y 2] y)

Tilde-At

The tilde-at sequence is a variation of tilde that evaluates its argument, which should return a sequence, and inserts the elements from that sequence into a list in the macro template.

user=> (let [x '(1 2 3)]
         `(println ~@(map (fn [y] (* 2 y)) x) 'done))
(clojure/println 2 4 6 (quote user/done))

In this expression, the elements from x are run through map, which doubles their values. The output of map is inserted into the list that starts with println and ends with 'done. Notice that 'done in the output is still quoted. It was read in as data—'done—and output as the same data.

gensym and #

Sometimes when you’re creating a macro template, you want to use create a variable. One danger is that it could shadow a variable in the surrounding code.

For example, in this code,

user=> (let [x 42]
         `(let [x 13]
           [x x]))
(clojure/let [user/x 13] [user/x user/x])

what do the two x variables refer to on the third line? The x from the outer let (42); or the x from the inner let (13)? In this case, they both refer to the inner x. Occasionally, you may do this on purpose, but usually it’s a mistake.

To avoid this mistake, in variables you declare in a macro template, you should append an # onto the end of the variable name. This makes sure that that variable name is never used elsewhere. It cannot clobber any other variable name.

user=> (let [x 42]
         `(let [x# 13]
           [x x#]))
(clojure/let [x__1888 13] [user/x x__1888])

In this case, the two x variables in the final line now refer to two different variables. The first refers to the variable in the outer let, and the second refers to the variable in the inner let, in the macro template. You can see that it’s different because Clojure has removed the # character and replaced it with __1888. (That number always changes. If you run this code, it will be different for you.) Moreover, Clojure guarantees that that variable name will never be used again during that run.

A Quick Macro

So let’s write a quick macro, just to see what one looks like.

I usually develop with just a REPL and the text editor Vim, and if I need to debug anything, often I just put in print statements. In languages like Python, many of these statements look like this:

print "x+4 =", x+4
print "counts[word] =", counts[word]

That’s a lot of duplication and typing, and aren’t computers supposed to get rid of that?

The problem is that we want to bypass the way the language normally evaluates expressions. We want the computer to print the first expression out, just like it would data; we want it to evaluate the second expression and print out the result.

Because we want to change Clojure’s normal evaluation rules, this is a perfect place for a macro. We will pass in an expression and have Clojure print both the expression and its value. As an added bonus, we can have it also return the value. Here’s what we want it to look like:

user=> (let [x (+ 42 13)]
         (println '(+ 42 13) "=>" x)
         (flush)
         x)
(+ 42 13) => 55
55

Let’s look at what this would look like as a macro named debug:

(defmacro debug
  [expr]
  `(let [value# ~expr]
     (println '~expr "=>" value#)
     (flush)
     value#))

Let’s pick this apart.

(defmacro debug: Create a macro named debug.

[expr]: The macro takes one parameter, which will be called expr in the body of this macro.

(let [value# ~expr]: Start the macro template with a let expression. The let will define one variable, named value#, which will be assigned the value of evaluating expr.

(println '~expr "=>" value#): Print the expression expr as data (because it is quoted, an arrow, and the value of the variable value#.

(flush): Flush the output buffer.

value#)): Return the value of the variable value#.

Before we actually try it, we can see what calling it would return using the function macroexpand-1. This takes a list expression and returns the list expression created by calling the first macro, if any, that needs to be executed on it.

user=> (macroexpand-1 '(debug (+ 42 13)))
(clojure/let [value__1892 (+ 42 13)]
  (clojure/println (quote (+ 42 13)) "=>" value__1892)
  (clojure/flush)
  value__1892)

(I reformatted this to make it readable.) With a little mangling, we can see that the debug macro will generate the expression

(let [value__1892 (+ 42 13)]
  (println '(+ 42 13) "=>" value__1892)
  (flush)
  value__1892)

Which is exactly what we want. If we then call that macro, we get this.

user=> (debug (+ 42 13))
(+ 42 13) => 55
55

(The first line is the printed output of the expression. The final 55 is the result of the expression.)

In the next posting, we’re going to look at the process of how to write macros and how to avoid the pitfalls and dangers of macro writing, and we’re going to write a number of macros for the Porter Stemmer.

Stemming, Part 7: More Functions

2008-07-17T18:58:00.001-05:00

Today, we’ll define some more utilities for the Stemmer.

Internal Functions

One facet of functions that these utilities will use is internal functions. Remember that we can declare a function literal using fn. Also, we can declare variables using let. Internal functions combine both of these to create functions that are only visible and usable within a function. For example, in the last posting we redefined count-item to use cond. We could also rewrite it to use an internal function instead of loop.

(defn count-item [sequence item]
  (let [ci (fn [sq accum]
             (cond (not (seq sq)) accum
                   (= (peek sq) item) (recur (pop sq) (inc accum))
                   :else (recur (pop sq) accum)))]
    (ci sequence 0)))
#'user/count-item

In this case, the loop is redefined as a recursive function. It is assigned to the variable ci, which is called in the body of the let.

In this case, using an internal function instead of a loop isn’t really a win, but if you have several internal loops that interact, defining them as internal functions can greatly clarify what the function does.

Stemmer Utilities

(m stemmer)

One of the utilities that will use internal functions is m. It counts how many consonant sequences are between the beginning of a word and the stemmer’s index. It uses a function called count-v, which skips letters while they are still vowels; count-c, which skips letters while they are still consonants; and count-cluster, which walks over the vowel and consonant clusters in the word, counting the consonants.

count-v and count-c both return vectors. The first item in the vector indicates what the caller should do after the function returns.
:return means that the function should just return immediately; :break means that it should continue processing. The second and the third items in the vectors are the current consonant cluster count and the current index of letter that is being considered.

(defn m
  "Measures the number of consonant sequences between
  the start of word and position j. If c is a consonant
  sequence and v a vowel sequence, and <...> indicates
  arbitrary presence,
    <c><v>       -> 0
    <c>vc<v>     -> 1
    <c>vcvc<v>   -> 2
    <c>vcvcvc<v> -> 3
    ...
  "
  [stemmer]
  (let [
        j (get-index stemmer)
        count-v (fn [n i]
                  (cond (> i j) [:return n i]
                        (vowel? stemmer i) [:break n i]
                        :else (recur n (inc i))))
        count-c (fn [n i]
                  (cond (> i j) [:return n i]
                        (consonant? stemmer i) [:break n i]
                        :else (recur n (inc i))))
        count-cluster (fn [n i]
                        (let [[stage1 n1 i1] (count-c n i)]
                          (if (= stage1 :return)
                            n1
                            (let [[stage2 n2 i2] (count-v (inc n1) (inc i1))]
                              (if (= stage2 :return)
                                n2
                                (recur n2 (inc i2)))))))
        [stage n i] (count-v 0 0)
        ]
    (if (= stage :return)
      n
      (count-cluster n (inc i)))))

(ends? stemmer suffix)

ends? tests whether the stemmer ends with a given suffix. If it does, it moves the stemmer’s current :index and returns the new stemmer. The processor also needs to know whether the ending was actually found. To accommodate this, ends? returns a vector containing the new (or old) stemmer and true or false.

(defn ends?
  "true if the word ends with s."
  [stemmer s]
  (let [word (subword stemmer), sv (vec s), j (- (count word) (count sv))]
    (if (and (pos? j) (= (subvec word j) sv))
      [(assoc stemmer :index (dec j)) true]
      [stemmer false])))

(set-to stemmer new-ending)

set-to sets the stemmer’s word to the prefix of the word (everything before the stemmer’s index) and the new ending.

(defn set-to
  "This sets the last j+1 characters to x and readjusts the length of b."
  [stemmer new-end]
  (reset-index (into (subword stemmer) new-end)))

(r stemmer orig-stemmer suffix)

r tests whether there are any consonant clusters in the stem. If so, the ending is set to suffix. Otherwise, the original stemmer is returned. This is used in some of the steps to add a suffix only if the stem is long enough. For example, you want to replace the ending of “restive” with nothing (to produce “rest”); but you don’t want to strip the “-ive” off “five.”

(defn r
  "This is used further down."
  [stemmer orig-stemmer s]
  (if (pos? (m stemmer))
    (set-to stemmer s)
    orig-stemmer))

Some of these are pretty messy. For instance, returning the vector of multiple values may be fine for a collection of internal functions, but it creates a complicated interface to the ends? predicate. In the next posting, we’ll look at how we can simplify ends?.

Stemming, Part 6: Stemmer Predicates

2008-07-15T20:39:00.001-05:00

In the last few postings we’ve been looking at functions and how they’re used in Clojure. One of the fundamental kinds of functions is the predicate: a function that tests something and returns true or false. By convention, these functions end in a ?. Clojure has a number of these, and for the Porter Stemmer, we’ll define a few.

Sets

Sets can act as predicates. As we saw when we were discussing stop words, sets are also functions that test for membership.

Built-Ins

Clojure defines a number of built-in predicates, and higher-order functions are often useful for creating other predicates.

(zero? num) Returns whether its argument is zero.

(pos? num) Returns whether its argument is a positive number.

(neg? num) Returns whether its argument is a negative number.

(complement fn) Returns a new function that returns the opposite of the predicate function passed into it. For example, (complement zero?) returns a predicate that tests whether its argument is not zero.

(cond test expression ...) A structure that acts as a series of nested if statements. Each test is followed by one expression. If the test evaluates as true, the expression is evaluated and its value is returned by the cond expression. An optional final test, by default :else, can be used if no previous tests evaluated as true. If no default test is provided, cond returns nil.

For example, in the last post, we had defined count-item, which had two nested if expressions:

(defn count-item [sequence item]
  (loop [sq sequence, accum 0]
    (if (not (seq sq))
      accum
      (if (= (peek sq) item)
        (recur (pop sq) (inc accum))
        (recur (pop sq) accum)))))
#'user/count-item

This could be defined more simply using cond:

(defn count-item [sequence item]
  (loop [sq sequence, accum 0]
    (cond (not (seq sq)) accum
          (= (peek sq) item) (recur (pop sq) (inc accum))
          :else (recur (pop sq) accum))))
#'user/count-item

In the last post, we also defined member?. How would you define it using cond?

Stemmer Predicates

With all that we’ve learned, we’re ready to define a number of predicates that we can use later in the Porter Stemmer.

vowel-letter? is a set of the standard vowel letters. This will only be used to define consonant?.

(def vowel-letter? #{\a \e \i \o \u})

consonant? returns true if the index in the stemmer points to a consonant letter. Alternatively, it tests whether a given index points to a consonant letter.

(defn consonant?
  "Returns true if the ith character in a stemmer
  is a consonant. i defaults to :index."
  ([stemmer]
   (consonant? stemmer (get-index stemmer)))
  ([stemmer i]
   (let [c (nth (:word stemmer) i)]
     (cond (vowel-letter? c) false
           (= c \y) (if (zero? i)
                      true
                      (not (consonant? stemmer (dec i))))
           :else true))))

vowel? is the logical opposite of consonant?.

(def vowel? (complement consonant?))

vowel-in-stem? returns true if any of the characters before the index is a vowel character.

(defn vowel-in-stem?
  "true iff 0 ... j contains a vowel"
  [stemmer]
  (let [j (get-index stemmer)]
    (loop [i 0]
      (cond (> i j) false
            (consonant? stemmer i) (recur (inc i))
            :else true))))

double-c? returns true if the index (or another character) is the last letter in a double consonant pair.

(defn double-c?
  "returns true if this is a double consonant."
  ([stemmer]
   (double-c? stemmer (get-index stemmer)))
  ([stemmer j]
   (and (>= j 1)
        (= (nth (:word stemmer) j)
           (nth (:word stemmer) (dec j)))
        (consonant? stemmer j))))

cvc? return true if the characters before the index (or another character) is a CVC sequence (consonant-vowel-consonant).

(defn cvc?
  "true if (i-2 i-1 i) has the form CVC and
  also if the second C is not w, x, or y.
  This is used when trying to restore an *e*
  at the end of a short word.
  E.g.,
    cav(e), lov(e), hop(e), crim(e)
    but snow, box, tray
  "
  ([stemmer]
   (cvc? stemmer (get-index stemmer)))
  ([stemmer i]
   (and (>= i 2)
        (consonant? stemmer (- i 2))
        (vowel? stemmer (dec i))
        (consonant? stemmer i)
        (not (#{\w \x \y} (nth (:word stemmer) i))))))

Notice that we’ve established a pattern here: these all take one or two arguments. With one argument, they test against the :index character in the stemmer. With two arguments, they test against any character:

porter=> (consonant? (make-stemmer "secrets"))
true
porter=> (consonant? (make-stemmer "secrets") 4)
false
porter=> (nth "secrets" 4)
\e

Read over these and make sure you understand them. There’s nothing in them that we haven’t covered already. And if you have any questions, feel free to ask in the comments.

In the next posting, we’ll define some more utilities for the stemmer.

Stemming, Part 5: Functions and Recursion

2008-07-14T17:16:00.001-05:00

So far in this Clojure tutorial/NLP tutorial, we’ve mainly been looking at Clojure’s functions, but the last posting actually included a good chunk of code for the Porter Stemmer. Today, we’ll review functions. Some of this we’ve seen before, but some of it will be new.

Functions

As with any functional language, functions are the building blocks of Clojure. I’m going to briefly summarize what we’ve learned about functions so far, and then we’ll explore one important topic—recursion—in more detail.

Defining Functions

Generally, functions are defined using defn, followed by the name of the function, a vector listing the parameters it takes, and the expressions in the body of the function. You can also include a documentation string between the function name and the parameter vector:

user=> (defn greetings 
         "Say hello."
         [name]
         (str "Hello, " name))
#'user/greetings
user=> (greetings 'Eric)
"Hello, Eric"

(The str function here just creates strings out of all its arguments and concatenates them together.)

Higher-Order Functions

Higher-order functions are functions that take other functions as values. These may use the other function in a calculation, or they may create a new function from the existing one. For example, map calls a function on each element in a sequence:

user=> (map greetings '(Eric Elsa))
("Hello, Eric" "Hello, Elsa")

complement, however, creates a new function that is equivalent to (not (original-function *args...*)):

user=> (def not-zero? (complement zero?))
#'user/not-zero?
user=> (not-zero? 0)
false
user=> (not-zero? 1)
true

Function Literals

Sometimes, particularly when you’re using a higher-order function, you may want to create a short function just for that one place, and giving it a name would clutter up your program. Or you may want to define a function inside another function, in a let expression, to using only within that function.

For either of these, use a function literal. A function literal looks like a regular function definition, except instead of defn, use fn; the name is optional; and generally it cannot have a documentation string. For example, suppose that greeting, which we defined above, doesn’t exist, and we want to greet a list of people. We could do this by creating a function literal and passing it to map.

user=> (map (fn [n] (str "Hello, " n)) '(Eric Elsa))                  
("Hello, Eric" "Hello, Elsa")

Or, we could temporarily define greet using let, and pass that to map.

user=> (let [greet (fn [n] (str "Hello, " n))]
         (map greet '(Eric Elsa)))
("Hello, Eric" "Hello, Elsa")

Overriding Functions

I’ve already mentioned that Clojure allows you to provide different versions of a function for different argument lists. Do this by grouping each set of parameter vector and expressions in its own list. The documentation string, if there is one, comes before all of the groups:

user=> (defn count-parameters
         "This returns the number of parameters
         passed to the function."
         ([] 0)
         ([a] 1)
         ([a b] 2)
         ([a b c] 3)
         ([a b c d] 4)
         ([a b c d e] 5))
#'user/count-parameters
user=> (count-parameters 'p0 'p1 'p2)
3
user=> (count-parameters)
0

This also works in function literals. This creates a shortened version of count-parameters called cp and calls it twice within a vector. The two calls are collected in a vector because let only returns one value, and we want to see the value of both calls to cp.

user=> (let [cp (fn ([] 0)
                    ([a] 1)
                    ([a b] 2)
                    ([a b c] 3))]
         [(cp 'p0 'p1) (cp)])
[2 0]

Recursion

Many problems can be broken into smaller versions of the same problem.

For example, you can test whether a list contains a particular item by looking at the first element of the list. At each place in the list, ask yourself: is the list empty? If it is, the item is not in the list. However, if the first element is what you’re looking for, good; if it’s not, strip the first element off the list and start over again.

This way of attacking problems—by calling the solution within itself—is called recursion. Recursive problems are fundamental to functional programming, so let’s look at it in more detail.

General Recursion

The main pitfall in creating a recursive problem is to make sure that it will end eventually. To do this, you need to make sure that you have an end condition. In the list-membership problem I described above, the end conditions are the empty list and the first element being the item you are looking for.

Let’s look at what this would look like in Clojure.

user=> (defn member? [sequence item]
         (if (not (seq sequence))    
           nil
           (if (= (peek sequence) item)
             sequence
             (member? (pop sequence) item))))
#'user/member?

In this, the first if tests whether the sequence is empty (that is, if seq cannot create a sequence out of it; if it is, it returns nil, which evaluates as false. The second if tests whether the first element in the sequence is what we’re looking for; if it is, this returns the sequence at that point. This is a common idiom in Clojure. Since the sequence has at least one item, it will evaluate as true, fulfilling its contract as a test, but it returns more information than that. This function is useful for more than just determining whether an item is in a sequence: it also finds the item and returns it. Finally, if the first element is not the item being sought, this *calls member? again with everything except the first item of the list*. This is the recursive part of the function. Let’s test it.

user=> (member? '(1 2 3 4) 2)
(2 3 4)
user=> (member? '(1 2 3 4) 5)
nil

Sometimes it’s helpful to map this out. In the diagram below, a call within another call is indented under it. A function call returning is indicated by a “=>” and a value at the same level of indentation as the original call. Here’s the sequence of calls in the first example above.

(member? '(1 2 3 4) 2)
    (member? '(2 3 4) 2)
    => '(2 3 4)
=> '(2 3 4)

The second example call to member? would graph out like this:

(member? '(1 2 3 4) 5)
    (member? '(2 3 4) 5)
        (member? '(3 4) 5)
            (member? '(4) 5)
                (member? '() 5)
                => nil
            => nil
        => nil
    => nil
=> nil

In this case, we’re just returning the results of the membership test back unchanged, but we could modify the results as they’re being returned. For example, if we wanted to count how many times as item occurs in a sequence, we could do this:

user=> (defn count-item [sequence item]
         (if (not (seq sequence))
           0
           (if (= (peek sequence) item)
             (inc (count-item (pop sequence) item))
             (count-item (pop sequence) item))))
#'user/count-item

In many ways, this is very similar to member?. It first tests whether the sequence is empty, and if it is, it returns zero. If the first element is the item, this calls itself (it recurses) and increments the result by one, to count the current item. Otherwise, it recurses, but it does not increment the result. Let’s see this in action.

user=> (count-item '(1 2 3 2 1 2 3 4 3 2 1) 2)
4
user=> (count-item '(1 2 3 2 1 2 3 4 3 2 1) 3)
3
user=> (count-item '(1 2 3 2 1 2 3 4 3 2 1) 5)
0

Here, the first example (in shortened form) graphs out like so:

(count-item '(1 2 3 2 1) 2)
    (count-item '(2 3 2 1) 2)
        (count-item '(3 2 1) 2)
            (count-item '(2 1) 2)
                (count-item '(1) 2)
                    (count-item '() 2)
                    => 0
                => 0
            => 1
        => 1
    => 2
=> 2

You see that the results gets incremented as the computer leaves each function call where 2 is the first element in the input list.

Tail-Recursive Functions

While these two examples of recursion are superficially similar, on a deeper level they are very different. In member?, once you’ve computed the result, you can return it immediately back to the function that originally called member?. If Clojure had some way to jump completely out of a function from any level, you could do this. On the other hand, when count-item recurses, it is not finished with its calculation yet. It has to wait for itself to return and possibly add one to the result. (Sentences like that remind me why recursion can be confusing. Don’t worry. Eventually your brain will get used to being twisted into a pretzel.)

There’s a term to describe functions like member? that are finished with their calculations when they recurse. It’s called tail-call recursion or tail-recursive. This is a very good quality. The computer can optimize these calls to make them very fast and very efficient.

But the Java Virtual Machine doesn’t recognize tail recursion on its own, so Clojure needs a little help to make these optimizations. You signal a tail-recursive function call by using the recur built-in instead of the function name when you recurse. Thus, we could re-write member? to be tail-recursive like this.

user=> (defn member? [sequence item]          
         (if (not (seq sequence))               
           nil                                    
           (if (= (peek sequence) item)           
             sequence                               
             (recur (pop sequence) item))))         
#'user/member?

See the recur in the last line? That’s all that has changed.

This should work exactly the same (and it does—try it), but for long lists, it should be much more efficient.

In fact, it’s often worth putting in a little extra work to make non-tail-recursive functions tail-recursive. There’s a straightforward transformation you can use to make almost any function tail recursive. Just add an extra parameter and use it to accumulate the results before you make the recursive function call. The first time you call the function, you need to pass the base value into the function for that parameter. For example, count-item with tail recursion would look like this:

user=> (defn count-item [sequence item accum]
         (if (not (seq sequence))              
           accum                                 
           (if (= (peek sequence) item)          
             (recur (pop sequence) item (inc accum))
             (recur (pop sequence) item accum))))   
#'user/count-item

The difference here is the accum parameter. When item equals the first element of the sequence, accum is incremented before the recursive functional call is made. When the function starts again on the shorter list, accum is incremented. Finally, when the end of the list is reached, accum is returned. It contains the counts accumulated as count-item walked down the sequence.

Of course, now we have to call count-item differently also:

user=> (count-item '(1 2 3 2 3 4 3 2 1) 2 0)
3
user=> (count-item '(1 2 3 2 3 4 3 2 1) 1 0)
2
user=> (count-item '(1 2 3 2 3 4 3 2 1) 5 0)
0

Whenever we call count-item, we have to include a superfluous zero that we really don’t care about. That seems messy and error-prone. How can we get rid of it?

Essentially, we want to hide this version of count-item and replace it with a new version that handles the extra zero for us. Then, we call the new version and forget about this one. There are several ways to actually do this:

Have the public function named count-item and create a private version named something like count-item-;
Use let to define the private function inside count-item; or
Use loop.

loop? Yes, this is new. loop is a cross between a function call and let. It looks a lot like let because it allows you to define variables. But it also acts as a target for recur. How would count-item look with loop?

(defn count-item [sequence item]
  (loop [sq sequence, accum 0]
    (if (not (seq sq))
      accum
      (if (= (peek sq) item)
        (recur (pop sq) (inc accum))
        (recur (pop sq) accum)))))
#'user/count-item

Notice that the first line of loop looks a lot like the first line of let. Both declare and initialize a series of variables. Just to keep things clear, I’ve renamed sequence to sq within the loop. Also, item isn’t included in the list of variables that loop declares, since it doesn’t change. Finally, at the end of the loop are two recur statements. When they are evaluated, they cause the program to jump back to the loop statement, but this time, instead of the original values used to initialize the loop variables, the values in the recur call are used.

Now we can again call count-item without the extra parameter:

user=> (count-item '(1 2 3 2 3 4 3 2 1) 2)
3
user=> (count-item '(1 2 3 2 3 4 3 2 1) 1)
2
user=> (count-item '(1 2 3 2 3 4 3 2 1) 5)
0

Stemmer Utility

With recursion, we can define another utility to use on the stemmer structures. This function will take a predicate and a stemmer. For each step, it will test the stemmer with the predicate, and if true, it will pop one character from the word and recurse. If there are no letters left in the word or if the predicate evaluates to false, it will return the stemmer the way it is:

(defn pop-stemmer-on
  "This is an amalgam of a number of
  different functions: pop (it walks
  through the :word sequence using pop);
  drop-while (it drops items off while
  testing the sequence against drop-while);
  and maplist from Common Lisp (the
  predicate is tested against the entire
  current stemmer, not just the first
  element)."
  [predicate stemmer]
  (if (and (seq (:word stemmer)) (predicate stemmer))
    (recur predicate (pop-word stemmer))
    stemmer))

I’m ready for a break. Next time, We’ll look at some more of the functions that Clojure provides, and we’ll define a few predicates of our own.

Stemming, Part 4: Tracking the Stemmer’s Data

2008-07-11T16:45:00.001-05:00

After the last several postings, we finally have seen enough of Clojure’s native data structures and the functions associated with them to define the data structure that the Porter Stemmer will use, as well as some of the functions that will operate on it.

The Stemmer Structure

Recall that the data that the stemmer will need to track is the word—and it will will need to manipulate the end of it—and an index into that word. A struct is an obvious way to keep those two data together.

For the word, a string is probably not the best option, because it is a Java string. We would have to copy-and-change every time we wanted to remove a letter. Instead, a vector gives us several advantages:

We can make changes to the vector without having to copy it every time; and
It is still an immutable data structure, so we’re staying within Clojure’s functional framework, where things are easiest.

So open up porter.clj and add these lines to the bottom. This defines the stemmer structure to have two fields, :word and :index.

;; :word = input string
;; :index = general offset into string
(defstruct stemmer :word :index)

Creating A Stemmer Structure

Like other data structures, a stemmer structure is defined by the functions that operate on it.

The first function we’ll need is one to create a stemmer structure from a word. It converts the word to a vector and sets the index to the index of the last character (one less than the number of characters in the word).

(defn make-stemmer
  "This returns a stemmer structure for the given word."
  [word]
  (struct stemmer (vec word) (dec (count word))))

Notice the string between the function name and the list of parameters ([word]). This is a documentation string. You can use the doc function to retrieve this later:

porter=> (doc make-stemmer)
-------------------------
porter/make-stemmer
([word])
  This returns a stemmer structure for the given word.
nil

Resetting the Index

Occasionally, we’ll need to reset the index to the last character. Generally, we’ll only need to do this after making a change to the word vector, so this function takes a word vector and creates a new stemmer structure with the correct index value from it.

(defn reset-index
  "This returns a new stemmer with the :word vector and
  :index set to the last index."
  [word-vec]
  (struct stemmer word-vec (dec (count word-vec))))

Retrieving the Index

We will also need to retrieve the index sometimes. Of course, there’s a chance that the index was not set and is nil or that it has gotten out of sync and points beyond the end of the word. get-index will check for both of these, and it will either return the index or the index of the last character.

(defn get-index
  "This returns a valid value of j."
  [stemmer]
  (if-let j (:index stemmer)
    (min j (dec (count (:word stemmer))))
    (dec (count (:word stemmer)))))

Retrieving the Word

A major role of the index is to mark a subsection of the word for later consideration. subword returns the part of the word before the index.

(defn subword
  "This returns the subword in the stemmer from 0..j."
  [stemmer]
  (let [b (:word stemmer), j (inc (get-index stemmer))]
    (if (< j (count b))
      (subvec b 0 j)
      b)))

If the index points to the last character in the word, it just returns the original word index. Otherwise, it returns the part of the word up to and including the index. By default, subvec only returns the part of the word up to its second index, so the index has to be incremented before getting passed to subvec.

Retrieving a Character

Sometimes we just want the single character that the index points to. index-char handles this.

(defn index-char
  "This returns the index-char character in the word."
  [stemmer]
  (nth (:word stemmer) (get-index stemmer)))

Removing a Character

So far, we’ve just been messing with the index. The most common operation we’ll perform on the word itself is removing the last character. pop-word handles this by popping a letter off the stemmer’s word and creating a new structure that associates :word with that new, shorter word.

(defn pop-word
  "This returns the stemmer with one character popped from the end of the
  list."
  [stemmer]
  (assoc stemmer :word (pop (:word stemmer))))

For the next posting, I’ll review functions again in more detail.

Stemming, Part 3: More Basics

2008-07-10T16:20:00.003-05:00

In the last posting, I introduced a number of Clojure data structures. Today, I’ll introduce a few more; then I’ll show you some common functions.

More Data Structures

Keywords

We’ve seen symbols before: every word in Clojure is represented as a symbol; every function name; anything that’s text, really, but isn’t a string. In programs, symbols act as variable names.

Clojure also has keyword symbols, which are like symbols, except they cannot be used as variables. Instead, a keyword also stands for itself. To write a keyword, put a colon (:) before its name:

user=> :word
:word

Keywords are used a lot in Clojure, particularly as keys for hash maps. There is good reason for this: a keyword is also a function that takes a hash map and returns the value associated with itself in the mapping.

user=> (:word {:frequency 4, :word "the"})
"the"

If you try to retrieve a keyword’s value from a mapping that doesn’t have the keyword, it returns nil.

user=> (:location {:frequency 4, :word "the"})
nil

Structures

Keywords’ acting as functions makes both keywords and mappings incredibly useful as flexible, generic data structures in Clojure. This is so common in Clojure that Rich Hickey has added structures, which are mappings with predefined sets of keys, and which are very efficient.

To define a structure, use defstruct, give it a name and a list of keyword fields. Here’s a structure that stores a word and its frequency:

user=> (defstruct word-data :word :frequency)
#'user/word-data

Now, you can define an instance of that data type (a word-data), using struct, which is called with the name of the structure and the values for the fields in the same order as they’re defined in the defstruct:

user=> (def the-word (struct word-data "the" 400))
#'user/the-word
user=> the-word
{:word "the", :frequency 400}

Use the keyword field names as functions to retrieve the value of the field from a structure:

user=> (:word the-word)
"the"
user=> (:frequency the-word)
400

Of course, the-word is just a hash map, and you can add other fields to it and treat it like a hash map in other ways too:

user=> (assoc the-word :location 'here)
{:word "the", :frequency 400, :location here}

Other Useful Functions

Of course, the functions we’ve just seen won’t do everything that we’ll need. Here are some useful functions, many of which we’ve already seen.

(dec n) Return one less than n. This is faster than (- n 1).

(inc n) Return one more than n. This is faster than (+ n 1).

user=> (dec 4)
3
user=> (inc 4)
5

(let [variables] expressions) Defines one or more variables. variables is a vector of variable/value pairs, arranged just like the key/value pairs in a hash mapping. expressions is one or more expressions. The entire let returns the value of the last expression.

user=> (let [x 4, y 5] (+ x y))
9

(if test true-expression false-expression) Executes test, and if it returns a true value (anything but false or nil), it executes and returns the value of true-expression; otherwise, it executes and returns the value of false-expression.

user=> (let [x :name] (if (= x :name) :yes :no))
:yes

(if-let var test true-expression false-expression) Combines let and if, capturing a common pattern:

(let [age (:age person)]
  (if age
    (str "My age is " age)
    "No age given"))

Here, you define a variable from an expression, and if it has a true value, execute one expression, and if it’s false, execute another expression. Here’s what this looks like in practice:

user=> (def person {:given "Eric" :surname "Rochester"})
#'user/person
user=> person
{:given "Eric", :surname "Rochester"}
user=> (:age person)
nil
user=> (if-let age (:age person)
  (str "My age is " age)
  "No age given")
"No age given"

(when test expressions) If the value of test expression is true, executes expressions and returns the value of the last.

user=> (when (= 41 42)
  (list 'expression 'one)
  (list 'expression 'two))
nil
user=> (when (= 42 42)
  (list 'expression 'one)
  (list 'expression 'two))
(expression two)

(min values...) Returns the least value in its arguments.

user=> (min 3 5)
3
user=> (min 5 7 3)
3

(and expressions) Evaluates its expressions until one returns a false value, at which point it returns nil; otherwise, it returns the value of the last expression.

(or expressions) Evaluates its expressions until one returns a true value, at which point it returns that; otherwise, it returns nil.

(not expression) Evaluates its one expression and returns the logical complement of it. An expression evaluating to nil or false will return true; a true expression will return false.

user=> (and (:given person) (:surname person))
"Rochester"
user=> (and (:given person) (:surname person) (:age person))
nil
user=> (or (:given person) (:surname person))
"Eric"
user=> (or (:given person) (:surname person) (:age person))
"Eric"
user=> (not (:given person))
false
user=> (not (:age person))
true

+, -, *, / Performs arithmetic operations on their arguments.

user=> (- 5 3 1)
1
user=> (+ 5 3 1)
9
user=> (* 8 2)
16
user=> (/ 8 2)
4

=, not=, <, >, <=, >= Compares its arguments, returning a boolean.

user=> (= 5 3)
false
user=> (not= 4 5)
true
user=> (not= 4 4)
false
user=> (< 5 3)
false
user=> (> 5 3)
true
user=> (<= 5 3)
false
user=> (>= 5 3)
true

For the next posting, we’ll apply what we’ve learned about Clojure and its data structures to the Porter Stemmer algorithm.