Stemming, Part 5: Functions and Recursion

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:

1. Have the public function named count-item and create a private version named something like count-item-;
2. Use let to define the private function inside count-item; or
3. 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

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:

1. We can make changes to the vector without having to copy it every time; and
2. 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

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.

Stemming, Part 2: Functional Programming

In the last posting, we looked at what the Porter Stemmer will need to do, and we glanced at functional programming. Now, we’ll consider what information the stemmer will need to keep processing a word, and we’ll start examining what data structures Clojure provides to keep track of that information.

What We Need to Keep Track Of

The primary data that the stemmer needs to track is the word itself. It strips characters off the end of the word, and occasionally it adds a character back on or changes the last character.

Also, the stemmer needs an index into the word. Sometimes, one function will analyze the word and mark a location. A later function may then change the word based upon that index.

Of course, to keep the functions from getting too complicated, the stemmer should package those two data—the word and the index—together.

Clojure Data Structures

So what does Clojure give us to manage this data?

I’ll list a few of Clojure’s data structures here. Also, since in a functional language a data type is defined by the functions that operate on it, we’ll look at them too. And as we go along, we’ll try everything out.

Lists

The most basic data type is almost any lisp is the list. It is a sequence of elements that is optimized for adding items onto and remove items from the beginning of the list.

List literals have parentheses around the items. Of course, this also looks like a function call, so we have to quote the list to indicate that we want it treated as a list:

user=> '(1 2 3)
(1 2 3)

Lists can also be constructed using list:

user=> (list 1 2 3)
(1 2 3)

Finally, you can convert a list or vector to a list using the seq function. (The thing in square brackets below is a vector. See the next section for details.)

user=> (seq [1 2 3]) 
(1 2 3)

Vectors

Vectors are conceptually similar to lists, except that they make it easy to add items to or remove items from the end of the vector.

Vector literals also look like lists, except they use square brackets ([ and ]). Since these can’t be confused with function calls, you don’t need to quote them. You can also create a vector using the vector function. And finally, you can convert a list to a vector using vec:

user=> [1 2 3 4]
[1 2 3 4]
user=> (vector 1 2 3 4)
[1 2 3 4]
user=> (vec '(1 2 3 4))
[1 2 3 4]

You can also get part of a vector using subvec. It takes one or two indexes into the vector. If called with one index, it returns everything from that index to the end of the vector; if called with two, it returns everything from the starting index up to, but not including, the second. The index for the first item is always zero, because that’s the way computers do things. (I could explain, but trust me: you don’t want to know.)

user=> (subvec [1 2 3 4 5] 2)
[3 4 5]
user=> (subvec [1 2 3 4 5] 2 4)
[3 4]

Sequences

Both lists and vectors (as well as some other things) are sequences. Sequence functions take any type of sequence and operate on it. Some of these functions always return lists; some of them return the same type that was passed in to it; some of the functions return information about the sequence or about what it contains. Here are some of the more important sequence functions:

count returns the number of items in the sequence.

user=> (count [1 2 3])
3

nth returns an element from the sequence. Remember that the index of the first item is zero.

user=> (nth [1 2 3] 1)
2

pop returns a sequence without one item. In lists, this is the first item; in vectors, it is the last.

user=> (pop '(1 2 3))
(2 3)
user=> (pop [1 2 3])
[1 2]

peek returns one item from the sequence. In lists, this is the first item; in vectors, it is the last.

user=> (peek '(1 2 3))
1
user=> (peek [1 2 3])
3

take returns the first n items in the sequence as a list.

user=> (take 2 [1 2 3 4 5])
(1 2)

conj returns the sequence with one item added to it. In lists, the item is added to the beginning of the list; in vectors, it is added to the end.

user=> (conj '(1 2 3) 4)
(4 1 2 3)
user=> (conj [1 2 3] 4)
[1 2 3 4]

into takes two sequences. It returns the results of calling conj on the first sequence with each item in the second sequence.

user=> (into '(1 2 3) [4 5 6])
(6 5 4 1 2 3)
user=> (into [1 2 3] '(4 5 6))
[1 2 3 4 5 6]

You can see that different types of sequences share functions; that the functions do conceptually similar things; but that what exactly happens for each function- and sequence-type-combination may differ.

Also, note that vectors make it easy to add and remove items from the end of the list. Because of this, are ideal for storing the word while the stemmer processes it.

Mappings

A mapping is the same as a hash table in Perl or a dictionary in Python. Actually, just as Clojure has different types of sequences, it also has a couple of different types of mappings. Hash maps are the most common, and that is the one I’ll be referring to below.

Literals for hash maps use curly braces ({ and }), and they don’t require any punctuation between keys and values or between key/value pairs. You can include a comma, but that’s whitespace and is just ignored. Notice that when Clojure prints the mapping, it adds the commas, because they make it easier to read. We’ll use them too for that reason.

user=> {"a" 1 "the" 2 "but" 3}
{"a" 1, "but" 3, "the" 2}

hash-map also creates a mapping using a function.

user=> (hash-map "a" 1 "the" 2 "but" 3)
{"a" 1, "but" 3, "the" 2}

assoc associates a key with a value in the mapping.

user=> (assoc {"a" 1, "the" 2, "but" 3} "and" 4)
{"a" 1, "but" 3, "the" 2, "and" 4}

dissoc removes a key from the mapping.

user=> (dissoc {"a" 1, "the" 2, "but" 3} "but") 
{"a" 1, "the" 2}

count, like with sequences, returns how many key/value pairs are in the hash map.

user=> (count {"a" 1, "the" 2, "but" 3})       
3

For the next posting, I’ll introduce some more data types, and we’ll apply them to the stemmer.

Stemming, Part 1: Introduction

What Is Stemming?

One problem with the tokenizer we’ve developed is that it doesn’t recognize any relationship between the same word with different endings, between, say, cat and cats or between walk, walks, walked, and walking. One way to identify those relationships is by using stemming, a process that removes the suffixes from a word (-s, -ed, or -ing) and returns just the word’s base (cat or walk).

Porter Stemmer

There are various algorithms to do this automatically. One of the most common is the Porter Stemmer, developed by Martin Porter in 1980, and available online for a variety of programming languages. This web site also has some test data and its expected output, and we’ll test our implementation against that.

In this section of the series, we’ll build a stemmer using the original C version of the algorithm as a guide. Don’t worry, though: you don’t need to know C to follow along here.

Although stemming may seem a minor process, it’s actually more complex than the simple tokenization we implemented earlier. Essentially, it walks the word being stemmed through five steps:

1. Get rid of plurals, -ed, and -ing, and turn -y to -i, so it will be recognized as a suffix in later steps;
2. Collapse multiple suffixes, such as -ational, -ator, -iveness, and others, to a single suffix, such as -ate, -ate, and -ive, respectively;
3. Collapse a different set of multiple suffixes or remove a small set of single suffixes;
4. Remove a set of suffixes including -ance, -ic, and -ive; and
5. Remove final -e and change -ll to -l in some circumstances.

This process is going to require more programming constructs and data structures than we’ve used so far. But then, what we’ve used up to now is pretty basic, and the new constructs will be necessary for anything but the most simple programs.

Functional Programming

I said earlier that I’m using the C implementation of the Porter Stemmer as a reference implementation. But C is a very different programming language than Clojure. C is imperative: Programs in C are composed of a series of statements that operate primarily by changing data.

However, as I’ve mentioned before, Clojure is a [functional language][functional]: Programs in Clojure are composed of functions that are put together and that transform data without changing it.

A Contrived Example

For example, a word processor written in C would make changes directly to the document. Each change would obliterate what had been there before it. The final draft of a paper in this program might be perfect, but the program would have no record of how it got to be that way.

A word processor written in Clojure would be different, though. Instead of obliterating parts of a document as it made changes, it would keep the old version and make the changes on a new copy of the document. The final document, in this case, is the sum of the original document plus all the changes that had been made to it.

All of Clojure’s data structures actually keep a reference to the old document and just keep a track of the changes that have been made to it.

(For the rest of this posting, and probably for the rest of this series, I’m going to talk about Clojure making copies of things and changing the copies. That’s not correct. Clojure actually keeps as much of the original uncopied as it can and passes around the original, plus changes. Of course, copy-and-change sounds inefficient—and it is—but what Clojure does is far more efficient. Still, generally, if you think of what Clojure does as copy-and-change, you’ll get the gist of it, and I think it’s less complicated to reason about. It’s certainly less cumbersome to write. )

Now, from the perspective of a user of the word processor, there might not be any difference between the C word processor and the Clojure one. But the Clojure program would work better in certain contexts. For example, imagine that you were editing a document in a collaborative environment, and someone else were editing it simultaneously. With the C word processor, if someone makes a change right after you did, their change would erase any record of yours.

However, with the Clojure, the word processor would be able to see that your friend’s change was to a different version of the document. It could then reconcile these changes.

In fact, Clojure has features for building exactly this kind of collaborative environment. We’ll talk about that later. First, let’s glance at some of the characteristics of functional programming, which we’ll explore them in more detail in coming posts.

Side-Effect-Free Programming

One of the primary rules of functional programming is to avoid side effects. A side effect is a change to a data structure or any other part of the computer’s environment.

To continue the word processor example, say you have a function that adds “The End” to the bottom of a document. An imperative version of the function would simply take the input document, add “The End,” and return the changed document. That modification is a side effect.

The functional version would create a new document that was exactly the same as the original, except it had “The End” at the bottom. It would return the new document, but leave the old one unchanged. That is side-effect free.

Now imagine we have another function that prints a hard copy of a document. Printing—either to the screen or to a printer—is a side effect, but it’s a desirable one. Avoiding side effects is an ideal, but we should be reasonable about it.

Immutable Data Structures

I’ve been talking about creating new data instead of changing them. In the C word processor, the document can be changed. In the Clojure program, it can’t be changed. Not please don’t, not you shouldn’t, not we really recommend not, but you can’t. If you want to change a Clojure data structure, you have to copy-and-change.

Fortunately Clojure makes this easy. Instead, Clojure’s built-in functions never modify a data structure. Instead, they return a modified copy of the data structures they operate on.

Thus, if you limit yourself to use Clojure’s native, immutable data structures, you will be avoiding side effects. In the code for this series, we’re going to stick with Clojure’s data structures every chance we have.

Caveat: Dysfunctional Java

Of course, Java’s data structures are anything but immutable. Any time you use them, you’re risking losing the benefits of functional programming. This isn’t critical now, but once we start working in a concurrent (i.e., collaborative) environment, using Java data structures invites problems.

I’m sure I’ll harp on this more later.

First-Order Functions

At its heart, functional programming is about using functions as data.

In Clojure, the word processing function to add “The End” to a document is a function that can be passed to another function. It can be wrapped in a function that takes a directory of documents and adds “The End” to all of them.

We’ve already seen how functions are data in their own right. Remember how we used map and filter to implement stop words.

The benefits to using functions in this way is that each function is usually small enough to see what it does easily, and programs are easier to think about, to test, and to understand.

Getting Started

Enough talk. Let’s code.

To keep things neat, put the stemmer in its own file and its own namespace: Create a new file in the same directory as word.clj, and name this file porter.clj. Now add this to the top of the file:

(in-ns 'porter)
(clojure/refer 'clojure)

That’s enough programming for one day, don’t you think?

For the next posting, we’ll take tour of some of the primary Clojure data structures, and we’ll consider what would be the best way to represent the stemmer’s work-in-progress, its working state.

Hiatus

Hey. This is a short post to let you know I haven’t disappeared: life’s just gotten in the way.

My wife had a kidney stone (it’s passed now).

July 4th weekend.

And this blog. The next topic—stemming—is going to take longer than I’d planned. It’s going to touch on a lot of topics that I wanted to put off to later. So I’m taking some time to figure out the best way to approach things.

But I’m still here.

Tokenization: Part 8, Summary

Have we really been covering tokenizing for seven posts? I thought it has been much longer than that.

Looking back on it, however, we’ve really talked about many things besides tokenizing and stop words:

• regular expressions;
• string and number literals;
• variables;
• calling functions;
• creating functions;
• saving source code;
• namespaces;
• calling Java methods;
• higher-order functions;
• sequence literals;
• quoting;
• sets;
• sets as functions;
• function overloading; and
• recursive functions.

Many of these things we only touched on, and we’ll revisit them later in more depth. However, these are all basic concepts that we’ll use over and over during this series.

In the meantime, feel free to pat yourselves on the back!

For the next posting, we’ll start creating a filter to stem the tokens, which we’ll use as an excuse to explore functional programming in more detail.