Problem 5-5: Mispellings[1] (Part 1)

Recall that make automates compilation of your code so that you don’t have to execute clang manually along with a whole bunch of switches. However, as your programs grow in size, make won’t be able to infer from context anymore how to compile your code; you’ll need to start telling make how to compile your program, particularly when they involve multiple source (i.e., .c) files, as in the case of this problem set. And so we’ll utilize a Makefile, a configuration file that tells make exactly what to do. Open up Makefile, and let’s take a tour of its lines; notice that this Makefile in particular seems quite a bit more complex than others we have seen.

The line below defines a variable called CC that specifies that make should use clang for compiling.

The line below defines a variable called CFLAGS that specifies, in turn, that clang should use some flags, most of which should look familiar.

The line below defines a variable called EXE, the value of which will be our program’s name.

The line below defines a variable called HDRS, the value of which is a space-separated list of header files used by speller.

The line below defines a variable called LIBS, the value of which is should be a space-separated list of libraries, each of which should be prefixed with -l. (Recall our use of -lcs50 earlier this term.) Odds are you won’t need to enumerate any libraries for this problem set, but we’ve included the variable just in case.

The line below defines a variable called SRCS, the value of which is a space-separated list of C files (and in this case, also an object file for which you do not have the source code) that will collectively implement speller.

The line below defines a variable called OBJS, the value of which is identical to that of SRCS, except that each file’s extension is not .c but .o.

The lines below define a "target" using these variables that tells make how to compile speller.

The line below specifies that our .o files all "depend on" dictionary.h and Makefile so that changes to either induce recompilation of the former when you run make.

Finally, the lines below define another target for cleaning up this problem set’s directory.

Know that you’re welcome to modify this Makefile as you see fit. In fact, you should if you create any .c or .h files of your own. But be sure not to change any tabs (i.e., \t) to spaces, since make expects the former to be present below each target.

The net effect of all these lines is that you can compile speller with a single command, even though it comprises quite a few files:

Even better, you can also just execute:

And if you ever want to delete speller plus any core or .o files, you can do so with a single command:

In general, though, anytime you want to compile your code for this problem set, it should suffice to run:

Okay, next open up speller.c and spend some time looking over the code and comments therein. You won’t need to (and indeed, shouldn’t!) change anything in this file, but you should understand it nonetheless. Notice how, by way of getrusage, we’ll be "benchmarking" (i.e., timing the execution of) your implementations of check, load, size, and unload. Also notice how we go about passing check, word by word, the contents of some file to be spell-checked. Ultimately, we report each misspelling in that file along with a bunch of statistics.

Notice, incidentally, that we have defined the usage of speller to be

where dictionary is assumed to be a file containing a list of lowercase words, one per line, and text is a file to be spell-checked. As the brackets suggest, provision of dictionary is optional; if this argument is omitted, speller will use dictionaries/large by default. In other words, running

will be equivalent to running

where text is the file you wish to spell-check. Suffice it to say, the former is easier to type! (Of course, speller will not be able to load any dictionaries until you implement load in dictionary.c! Until then, you’ll see Could not load.)

Within the default dictionary, mind you, are 143,091 words, all of which must be loaded into memory! In fact, take a peek at that file to get a sense of its structure and size. Notice that every word in that file appears in lowercase (even, for simplicity, proper nouns and acronyms). From top to bottom, the file is sorted lexicographically, with only one word per line (each of which ends with \n). No word is longer than 45 characters, and no word appears more than once. During development, you may find it helpful to provide speller with a dictionary of your own that contains far fewer words, lest you struggle to debug an otherwise enormous structure in memory. In dictionaries/small is one such dictionary. To use it, execute

where text is the file you wish to spell-check. Don’t move on until you’re sure you understand how speller itself works!

Odds are, you didn’t spend enough time looking over speller.c. Go back one square and walk yourself through it again!

So that you can test your implementation of speller, we’ve also provided you with a whole bunch of texts, among them the script from Austin Powers: International Man of Mystery, a sound bite from Ralph Wiggum, three million bytes from Tolstoy, some excerpts from Machiavelli and Shakespeare, the entirety of the King James V Bible, and more. So that you know what to expect, open and skim each of those files, all of which are in a directory called texts within your mispellings directory.

Now, as you should know from having read over speller.c carefully, the output of speller, if executed with, say,

will eventually resemble the below. For now, try executing the staff’s solution (using the default dictionary) with the below.

Below’s some of the output you’ll see. For amusement’s sake, we’ve excerpted some of our favorite "misspellings." And lest we spoil the fun, we’ve omitted our own statistics for now.

TIME IN load represents the number of seconds that speller spends executing your implementation of load. TIME IN check represents the number of seconds that speller spends, in total, executing your implementation of check. TIME IN size represents the number of seconds that speller spends executing your implementation of size. TIME IN unload represents the number of seconds that speller spends executing your implementation of unload. TIME IN TOTAL is the sum of those four measurements.

Note that these times may vary somewhat across executions of speller, depending on what else CS50 IDE is doing, even if you don’t change your code.

Incidentally, to be clear, by "misspelled" we simply mean that some word is not in the dictionary provided.

And now this:

Implement check!

Allow us to suggest that you whip up some small files to spell-check before trying out, oh, War and Peace. Here’s Zamyla:

Implement unload!

Be sure to free any memory that we allocated in load! (Per dictionary.h, the hash table itself is declared on the stack, but all of the nodes that are inserted into the hash table are dynamically allocated.) Remember that we used a hash table, and that you know how all the data in that hash table is organized and stored by virtue of its declaration and the definition of each node, even if you can’t see the exact mechanics we used to store it there. Here’s Zamyla with some final suggestions!

In fact, be sure that your spell-checker doesn’t leak any memory at all. Recall that valgrind is your newest best friend. Know that valgrind watches for leaks while your program is actually running, so be sure to provide command-line arguments if you want valgrind to analyze speller while you use a particular dictionary and/or text, as in the below.

And don’t forget about your other good buddy, gdb.