ECS 15 -- Fall 1997 -- © Nancy E. Reed, 1997

Laboratory 8 Notes
String Manipulation and Association Lists

Handouts:

• Scheme, part 3: Algorithms and Flowcharts, The Program Development Process (7 pages, html)

Readings:

• Labs 6-8 in the Laboratory Manual
• Scheme/Edwin Quick Reference (3 pages, postscript), included in the lab manual
• List of Scheme Error messages (15 pages), included in the lab manual.
• Revised^4 Report on the Algorithmic Language Scheme (55 pages, postscript) optional, available from Classical Notes.
• The Little Schemer textbook and The Scheme Programming Language textbook, available from the reserve desk in Shields library.

New Scheme functions

This laboratory exercise introduces new functions to work with text (strings) and association lists.

String Functions:

You will also be introduced to built-in Scheme functions that work on strings - to create, modify, and print text at specific locations on the page.

• pp - Pretty print. Takes one argument and prints it with the parentheses lined up.
• string? - Takes one argument. Returns True if the argument is a string, otherwise False.
• string-length - Takes one argument, a string S. Returns an integer (the number of characters in S).
• string-append - Takes any number of string arguments. Returns a string containing all the text in the arguments, in the proper order.
• make-string - Takes two arguments, a number N, and a character C. Returns a string of length N, with character C in each position in the string.
• substring - Takes three arguments, a string S, a starting index (number) I, and an ending index (number) J. It returns the portion of the string S starting with the Ith character and ending with the J-1st character. Note that the first character is at position 0.
• string=? - Takes two string arguments. It returns True if the two strings have the same characters in the same positions. Note: this function is case-sensitive.
• string-fill! - Takes two arguments, a string S and a character C. This function modifies S so that each character is now character C, and returns the modified S.

New data structure - Association list

Association lists - An association list is a list of lists. Each sublist (list inside the association list) contains one or more elements. The first element in each sublist is a "key" value that makes it easy to retrieve the sublist from the association list.

The structure of an association list looks like this ( < sublist > * )
where each of the sublists looks like this:
( < key > < item > * )

Examples: () ; empty association list
(("David" "Gilmour") ("Richard" "Wright") ("Roger" "Waters") ("Nick" "Mason")) ; Pink Floyd

(("voyager" "Katherine" "Janeway") ("enterprise" "James" "Kirk"))
; starship captains

List and Association list functions

There are built-in Scheme functions that work on association lists, in particular assoc.

• assoc - Takes two arguments, a key and an association list. If the key is found in the association list, it returns the sublist in the association list with the key as its first element. If no sublists in the association list have the key value then it returns the empty list ().
• set-car! - Takes two arguments, an item and a list, and permanently modifies the list so that the car of the list will be the new item. The rest of the list is unchanged.

The syntax for these functions is shown below.

(assoc < key > < A-list > )
(set-car! < list > < item > )
(pp < argument >  )

Examples: Assume *captains* contains the following association list:
(("voyager" "Katherine" "Janeway") ("enterprise" "James" "Kirk"))

(assoc "enterprise" *captains*)
will return
("enterprise" "James" "Kirk")

(pp *captains*)
will return

(("voyager" "Katherine" "Janeway") 
 ("enterprise" "James" "Kirk"))

(set-car! (assoc "enterprise" *captains*) "enterprise I")
will have the side effect of making *captains* look like:
(("voyager" "Katherine" "Janeway") ("enterprise I" "James" "Kirk"))

Edwin editor functions

The Scheme editor edwin has powerful built-in functions to assist you in writing Scheme functions. The most valuable functions specific to Lisp programming are:

• [Ctrl-x][Ctrl-e] - Evaluate only the previous Scheme expression in an Edwin buffer and show the results in the REPL buffer.
• [Meta][control-f] - Move forward to the next expression. This will move the cursor to the beginning of the next expression (list) from its current position. This means to go to the close parenthesis that matches the next open parenthesis (or the close double quote that matches the open double quote of a string).
• [Meta][control-b] - Move backward to the previous expression. This will move the cursor from the end of an expression to the beginning of the expression. This means to go to the open parenthesis that matches the nearest previous close parenthesis (or double quote).
• [Meta][Control-q] Auto indent function. Move your cursor to the beginning of a function definition and type the command. This will re-indent the code for the entire function and will allow you to tell where parentheses match without counting all of them.
• [Tab] - Auto indent line. - By typing the [Tab] key on any line, that line will be properly indented for the position of the code in the function. Particularly useful after you have edited part of a function to check if any parentheses were changed that you didn't intend to change.

• [Ctrl-space] - mark the start of a region (block).
• [Ctrl-w] - cut the region between the mark and the current cursor position to a buffer.
• [Meta-w] - copy the regin between the mark and current cursor position to a buffer.
• [Ctrl-y] - Yank/Paste the contents of the buffer to the current cursor position.

Check the editor quick reference pages in your laboratory manual for these and other useful Edwin commands to make your life easier.

Debugging Scheme code

Debugging your code is a part of the programming process. The TAs and staff are there to help you learn how to debug your programs in the labs. (They are not there to debug them for you.) The edwin editor and the Scheme interpreter are there to help you find any bugs in your code.

Common errors (or bugs) that occur in programs are mis-spellings and syntax errors, including missing or additional paretheses.

If you get a message "undefined variable", it is most likely a mis-spelling of your function, either in its definition (in the Edwin file) or in the function call in the interpreter. Look for typos first. Make sure you have the function defined in the Edwin buffer. Make sure you do not have spaces in your function names or argument names.

One of the first things to check is matching parentheses. Use the auto-indent capability of Edwin to visualize the structure of your functions. Items that like up vertically in the code are at the same level within the lists. If an expression is too far to the left, a structure before it has been closed off to quickly (extra ")"). If an expression is too far to the right, a structure has not been closed when you thought it was (not enough ")" before the expression).

Another thing to check is syntax. If the interpreter gives an error message when evaluating the functions in your Edwin buffer, there is most likely a syntax error (which may be a parenthesis error). Make sure that each time you call a function, you enclose its name and arguments in a list. Make sure that you include the extra sets of parentheses that some functions require, for example let, and cond.

The error message "Function called with too many arguments" and "Function called with too few arguments" mean that the number of items specified as arguments to the function in your function definition (Edwin buffer, usually), do not match the number of items in the function call (in the interpreter). Make sure you do not have spaces in your function names or argument names. Spaces are the separator for arguments, so the-list is one argument, while the list is two arguments.

EOF encountered during READ - EOF means "end of file". When the end of the file is encountered during reading the file (evaluating the buffer) it most likely means that you have forgotten to close off all the parentheses in the statements in the file. Edwin automatically matches parentheses for you. Each time you type in a closing parenthesis, the matching open parenthesis flashes and is displayed on bottom line of the editor window. Edwin also does auto-indentation, which is also quite useful.

Testing hints: Once your programs in the editor buffer are evaluated and you see the ";Value " message in the REPL buffer, the syntax of your function is legal. The procedures still might have some logic bugs - meaning that you can run a procedure and it will do something, but maybe not exactly what you wanted it to do.

To make the debugging process as easy as possible: Test each function as soon as you write it in the Edwin buffer. If you wait until you have many functions, it is much more time-consuming to determine which one has an error and find that one than it is to just examine one function where you know the problem is.

If you load or evaluate an entire file/buffer and have errors in the file/buffer, everything in the file after the errors may be messed up. So work from the beginning of the file. You will most often evaluate just a single procedure in Edwin ([Ctrl-x][Ctrl-e] will evaluate the previous expression). Debug one procedure at a time.

To find logic errors, start testing with the smallest argument you can have to the function (0 or an empty list are common). If there is a conditional statement in the function, test each "branch" with small arguments. Try to discover what kinds of arguments cause it to produce incorrect behavior. Then examine the code for that part of the function carefully.

A Family Relationships Database

For the last section of this lab, you will complete a file of procedures for a family relationships database. Many of the procedures are already written for you and available on the web in the file family.scm . A copy of this file is also in the C:\ECS15\SCHEME\BIN directory in the Meyer Hall labs.

This lab exercise gives you the opportunity to complete parts of a group of procedures that work together. In the next lab, you will be creating all the procedures to solve a similar problem.

Go to the index of lectures for ECS15 - Fall 1997 .

Go to the homepage for ECS15 - Fall 1997 .