Tuesday, June 24, 2008

Tokenization, Part 3: Functions

Tokenization, Part 3: Functions

Functions

In the last post, we saved the regular expression that we used to tokenize a string to a variable. But it would be more convenient to be able to save the entire tokenization procedure to a variable. Pretty much all programming languages let us save a series of statements or expressions—a function—to evaluate later. How does Clojure do this?

In fact, creating a function looks a lot like creating a variable. First, start Clojure and make sure that token-regex is still defined:

user=> (def token-regex #"\w+")
#'user/token-regex

Next, define the function, only instead of using def, use defn:

user=> (defn tokenize-str [input-string]
(re-seq token-regex input-string))
#'user/tokenize-str

Let’s break that apart:

  1. defn indicates that we’re defining a function, not a variable.
  2. tokenize-str is the name of the function. Functions and variables use the same set of names, so naming a variable tokenize-str will get rid of the function named tokenize-str, and vice versa.
  3. [input-string] is a square-bracket-delimited list of the parameters that this function accepts. In the case of tokenize-str, it takes one argument, named input-string. Expressions inside the function can refer to the value passed into the function using that name.
  4. After you type in that line and hit enter, nothing will happen. The first parenthesis before defn is still open, so the Clojure REPL knows you’re not finished yet. You’ll need to enter the second line to continue.
  5. The second line is just the re-seq function with both arguments as variables, like we used in the last posting. One variable is the regular expression from the previous def, and one is input-string from the function definition.
  6. Functions return the value of their last expression. In this case, that is the function call to re-seq.

Now let’s give it a try:

user=> (tokenize-str "This is a new input string with different tokens.")
("This" "is" "a" "new" "input" "string" "with" "different" "tokens")

Sure enough. Now calling (tokenize-str ...) is the same as calling (re-seq token-regex ...).

Saving Your Work

We’re starting to get enough code that typing it in every time we want to use it would be painful, inefficient, and worst of all, boring. Fortunately, like most other programming language, Clojure lets us save expressions to a file to execute all at once.

To do this, open your text editor and create a new file. Let’s call it word.clj and save it in whatever directory you’re currently working in. Next enter in all the code we’ve entered so far:

(def token-regex #"\\w+")
(defn tokenize-str [input-string]
  (re-seq token-regex input-string))

Now switch back to the Clojure REPL and load this file using the load-file function:

user=> (load-file "word.clj")
#'user/tokenize-str

After loading the file, Clojure prints the result of the last expression in the file. In this case, that is the expression defining the tokenize-str function.

We can use the variables and functions defined in that file, just as if we had typed them into the REPL:

user=> (tokenize-str "Another input string.")
("Another" "input" "string")

I’ve set up a Google Code Project for the code in this series at http://code.google.com/p/word-clj/. As we go along, I’ll update the code in step with the postings here.

Also, if you find any bugs, you can let me know using the issues tracker there.


Next time we’ll improve the tokenization and talk about how to organize our code better.

Monday, June 23, 2008

Tokenization: Part 2

Tokenization, Part 2: Literals and Variables

Literals

In the last posting, I showed how to tokenize a string into separate tokens/words. For reference, the code to do this (in the Clojure REPL), was:

user=> (re-seq #"\\w+" "This string contains some tokens. Yipee!")
("This" "string" "contains" "some" "tokens" "Yipee")

In the snippet above, both the regular expression and the input string are literals: a direct representation of a value. #"\\w+" is a literal regular expression, and "This string contains some tokens. Yipee!" is a string literal. Some other literal expressions in Clojure are:

String "This is a string."
Regular expression #"\\w+"
Character \a
Integer 42
Float 3.1415

Clojure also has literal expressions for a variety of other types of data. I’ll introduce them as we need them.

Remembering

Remembering the regular expression we were using above—#"\\w+"—isn’t a big deal. A more complicated expression may be difficult to read, much less to recall or to type correctly all the time. Fortunately, we don’t have to remember it. Instead, we can use variables. Clojure creates a variable and assigns it a value with a def expression:

user=> (def token-regex #"\\w+")
#'user/token-regex

Now, whenever we use the name token-regex, Clojure substitutes the value #"\\w+" instead:

user=> (re-seq token-regex "This string contains some tokens. Yipee!")
("This" "string" "contains" "some" "tokens" "Yipee")

For that matter, if we’re going to be using that input string frequently, we can assign it to a variable also:

user=> (def input-string "This string contains some tokens. Yipee!")  
#'user/input-string
user=> (re-seq token-regex input-string)                              
("This" "string" "contains" "some" "tokens" "Yipee")

Benefits

Using variables allows us a couple of advantages:

  1. We can name things according to what their function in the program is, not by their value.
  2. We can reduce errors by removing duplication. Since we aren't typing in the value by hand every time, we have fewer opportunities to type it in wrong.
  3. For data that may take up a lot of memory, we only need to use up that memory once, and then we can refer to that single instance of the data as many times as we need to.

Caveats

If you’re coming to Clojure from another, non-functional programming language (as I assume you are), variables in Clojure are immutable: you can’t change them. There is no assignment operator, like = in many languages. (You can call def again on the same variable name, but technically that’s not assigning a new value to the old variable, and in general, you don’t re-def a variable in Clojure.)

As we’ll see later, immutability is a good thing in Clojure. But does take some getting used to.


Next, we’ll look at how to wrap up the entire protocol for tokenization into its own variable.

Sunday, June 22, 2008

Tokenization: Part 1

Tokenization, Part 1: Regular Expressions

About Tokenization

Tokenization is the process of splitting a string of characters into tokens: useful sequences of characters that all belong together. When analyzing natural language, tokens are often conflated with words, and defining what is and what is not a word, from either a linguistic or a computer's point of view, is problematic. Should a contraction be split into a separate word? Should ice cream be two tokens or one?

But I’m going to keep this simple, so we're going to define a token/word in the simplest way possible, and we're going to use regular expressions to do it.

About Regular Expressions

Regular expressions (often shortened to regexes) are a mini-language used inside a full-fledged programming language or other tool to specify how to match text. For example, you can create a regex that says that you want to match one or more a characters (a+) and use that pattern to find or replace a group of a’s in a string.

Regexes also have short-cut ways to indicate classes of characters. For instance, the class \w matches any alphanumeric character or underscore.

Underscore? As it turns out, when regexes say “word characters,” you should usually add “as defined by the programming language C.” Words in C can contain non-accented ASCII letters, numbers, and—you guessed it—underscores.

Problems

\w is not ideal for tokenizing. It doesn't handle any letters that aren’t used in American English; it doesn’t include apostrophes; and it does include underscores. But as I said, I’m trying to keep this simple. Later, you can muck things up with theoretically pure tokens that actually make sense.

Enough Talk Already!

Let’s fire up Clojure with the scripts we created in the last posting and see what damage we can cause.

Clojure
user=>

Clojure has a simple syntax for creating regexes. To make a regular expression to find groups of “word” characters, just put a quote around the pattern and put a hash mark (#) in front of it. Also, the backslash has special meaning in Clojure strings, so you’ll need to double it, so that Clojure will pass the backslash to the regex pattern:

user=> #"\\w+"
\w+

That creates the regex, to use it, we’ll pass both it and a string to the re-seq function.

user=> (re-seq #"\\w+" "This string contains some tokens. Yipee!")
("This" "string" "contains" "some" "tokens" "Yipee")

(Don’t worry about how functions are called. Just type in what you see above. I’ll explain what’s happening in the next few postings.)

That’s it. We’ve got the basics of how to tokenize a string down. Next, we’ll learn how to package it up so we know we’ll always be tokenizing consistently.

More about Regular Expressions

This is as much as I’m going to cover about regular expressions. That doesn’t mean that regular expressions aren’t insanely useful: they’re just also insanely complicated. If you do much text processing, however, you'll want to get intimate with all their useful craziness.

Here are some resources for learning regular expressions:

Friday, June 20, 2008

Setting Up Clojure

(I added another reason why I like Clojure to my last post: community, reason #1 under "Why Clojure?". Check it out.)

Before we get started, we need to install Clojure and set up our environment to make the best use of it. This will involve installing Java, installing Clojure, creating some scripts to make calling Clojure easier, and setting up a text editor.

Below, I'll sketch out one quick way to get set up. There's more information on the Getting Started page and on the Clojure Wiki.

(These instructions are a little higher-level than I would like, for two reasons. First, how to do these things depends on your operating system. Second, if you have much computer experience, you probably already know how to do the tasks I gloss over below. But you may not. Grab a friend.)

Java

First, you may need to install a Java Runtime Environment. You may already have this installed, and if so, skip to the next section.

If you don't have Java installed or aren't sure whether you do, go to http://java.sun.com/javase/downloads/ and download the latest release of Java SE 6. Once you've downloaded it, double-click the installer to run it and install Java.

Depending on which installer you downloaded, at this point you'll either need to wait for Java to install or wait for it to download, then install. Either way, be patient.

Clojure

(If you're comfortable living on the edge and compiling Java with Maven, get the development code for Clojure from SVN and install that. I've been using the SVN version from the beginning, and it hasn't given me any trouble.)

Now you're ready to install Clojure. Go to its Sourceforge download page and select the latest release (20080612 at the time of this posting). Save it on your disk someplace you'll remember.

Now create a new directory named Clojure and unzip the file you downloaded into it. In that directory will be a file named clojure.jar. This contains the Clojure system.

Scripts

The Clojure JAR file isn't executable itself, so you'll want a script, which you can call from the command-line or double-click on, to run Clojure.

The easiest way to do this is to use the directory named Clojure, which contains clojure.jar as your working directory. Under UNIX/Mac OS-X, create a file in Clojure named clj and add these lines:

#!/bin/bash
java -cp clojure.jar clojure.lang.Repl

Of course, you'll need to set the permissions on this file to make it executable.

On Windows, create a file in Clojure named clj.bat and add these lines:

@ECHO OFF
java -cp clojure.jar clojure.lang.Repl

(Both of these assume that java is in your PATH. If it's not, you'll need to add it.)

Your start-up script can be a lot more complicated, of course. The Clojure Wiki has one that loads other libraries and can also be used to run scripts written in Clojure.

Double-click on or execute the file you created above and you should get a console window with this:

Clojure
user=>

Congratulations! Hit Ctrl-D to exit.

(Using the Clojure directory as your working directory is a good way to get started quickly, but its long-term merit is debatable. Set up the script so you can work from another directory. If that means nothing to you, find a friend who knows Java, and he can help.)

Editors

Because of the variety of editors out there, I'm punting on this one. The Clojure Wiki has information on setting up Emacs and Vim, and there is also enclojure, a plugin for the NetBeans IDE.

So far, I've been using Vim, and I haven't had any complaints.

Tuesday, June 17, 2008

Introduction to Clojure

What is Clojure? The rest of this series will answer that question in an easy-to-understand way. If that's good enough for you, skip down to Why Clojure?, where I talk about what I like about Clojure. If you want the shorter, more difficult explanation, though, wade through this: In one jargon-heavy sentence, Clojure is a general-purpose, dynamic, compiled lisp that targets the Java Virtual Machine and that provides strong facilities for functional and concurrent programming. Pretty dense. What does it mean?
  • General Purpose It's suitable to a wide variety of tasks. You might consider it for almost anything you'd use Java for.
  • Dynamic It shares many features, like dynamic typing, with Perl, Python, Ruby, and other agile languages. These traits make it easy to write programs quickly.
  • Lisp It's in the Lisp family of languages, and it shares much of the philosophy behind them. For example, Clojure programs are written in Clojure data structures, which enables a powerful macro facility.
  • Compiles Although Clojure is dynamic, it is not interpreted. Instead, each expression and function is immediately compiled to Java byte code. Often functions written in Clojure run just as fast as their Java equivalents, especially when you give the compiler hints about what kind of values your variables refer to.
  • Java Virtual Machine Clojure runs on the JVM, and it can use the standard Java library, as well as all of the third-party libraries available for Java.
  • Functional Although you can access mutable Java types, Clojure has an array of immutable, fast data structures suitable to functional programming. This is a style of programming that emphasizes functions that don't change their input and programs that are composed of many small functions, glued together.
  • Concurrent Clojure includes a robust implementation of software transactional memory (STM) and reactive Agents. When combined with functional programming, these systems make it easy to write clean, correct concurrent programs.
Why Clojure? For me, Clojure hits a sweet spot. I like the power and flexibility that dynamic languages—especially lisps—provide, but I also want the speed, the library, and the community of a behemoth like Java.
  • The interactive development model it shares with Python, Ruby, and especially lisp makes it an excellent platform to experiment on.
  • Unlike most current dynamic languages, it lets me take advantage of multiprocessor machines across a variety of OS platforms.
  • It gives me access to the zillion libraries available for Java, and to the JIT capabilities of the JVM.
  • It provides speed in both development and execution.
  • I can deploy it wherever the JVM is available.
In a nutshell, Clojure lets me do interesting things quickly, without having to fight with it. I think you'll like it too.

Clojure Series: Table of Contents

Here are the postings I have published so far for this series.

Monday, June 16, 2008

New Toys

So what new toys have been occupying my time? Clojure. It's a functional, compiled lisp for the Java Virtual Machine (JVM). Like any good lisp, it has macros and first-class functions; plus it also has many nice features for concurrent programming, like software transactional memory and agents. It has fast, read-only data structures designed to be used in a functional language. So far, I've had a lot of fun with it. I've mainly been using it to work through Programming Collective Intelligence by Toby Segaran (PCI, for the rest of this posting). Whenever I'm working through a programming book, I like to re-code the examples so I understand them better. And often it's better to use a language that's not at all like the one the author uses in the book. Since the code in PCI is in Python, most popular languages would be too similar to really help me understand the algorithms Segaran's describing. But since Clojure is a functional language, I have to step back, look at what he's trying to do, and think about how to accomplish the same thing with a different, functional approach. It's been good to help me understand the book better and to help me improve my functional chops. To further explore this fun little language, I'm going to start a long series here on this blog. Here's the plan:
  • Its target audience will be people like myself: self-taught programmers whose primary education has been in the humanities.
  • This won't be a tutorial on how to program: The audience should have a little programming experience, preferably in Perl, Python, or Ruby.
  • But you won't need to have any experience in lisp, functional programming, or concurrent programming. I'll touch on those as we go along.
  • The problems I'm going to tackle will be oriented to processing text documents and analyzing the language in them. The techniques I'll cover will be helpful to those interested in stylistics and other literary studies, or to those interested in corpus linguistics.
  • Many of the things I'll describe—such as tokenization–will be very basic and far back from the cutting-edge. Since this is also an introduction to Clojure, I'll cover the basics also.
  • But there will also be some odd gaps. For example, I'll explain regular expressions just enough to implement tokenization. Then I'll point you to one of the myriad-thousand excellent online tutorials if you want to learn more about them.
  • Since one of the main points of Clojure is concurrency and parallel processing, I'll cover that also.
  • The examples will build on each other, and in the end, we'll have a system for doing parallel processing of text documents. We'll build a variety of tasks to do some standard analyses, and we'll design it so creating more tasks and inserting them into the processing stream will be relatively easy.
Well, this is long enough for today. Tomorrow I'll start with a brief introduction to Clojure and a look at why you might want to learn it.