CSCI 330 Lab 1: Lisp fundamentals

You'll have two weeks to do the lab (including the lab sessions on Jan. 13th and 20th) and it will be due at the end of the day on Jan. 26th.

The exercise involves forking/cloning a git repository, editing the lab1fun.cl and lab1test.cl files, and then submitting your updated repository.

Instructions are given below and will be discussed in the lab sessions, along with a basic intro to working with lisp/sbcl.

In this first lab we include a review of the basic git process for obtaining/submitting labs, for later labs we'll simply dive straight into the actual lab requirements.

Marking: the lab will be marked out of 21. Of that, 15 marks are for the function implementations in lab1fun.cl and the other 6 are for your testing of those functions in lab1test.cl.

Git submission system

For this lab (and all CSCI 330 labs this term) you will be using an adaptation of the git version control system to get the starting lab material, to track changes as you make them, and ultimately to submit your completed lab.

You must use this system to obtain and submit your work - no other submission mechanism will be accepted.

For students new to ssh/linux/git intro to linux accounts, ssh, very basic linux - youtube, slides basic programming tips for ssh/C++ on our systems - youtube, slides git submit basics and troubleshooting - youtube, slides short guide to csci git project/lab submission

NOTE: if you have taken csci330 previously then it would be advisable to archive your old csci330 directory at the start of the term, e.g. mv csci330 old330

The basic instructions to obtain your lab1 are shown below (issued from cubs/pups).

    mkdir -p csci330
    ssh csci fork csci330/lab1 csci330/$USER/lab1
    cd csci330
    git clone csci:csci330/$USER/lab1
    cd lab1

Working on and submitting your lab

After your git fork/clone steps, in your lab1 directory you should find files named lab1test.cl and lab1fun.cl, which will be the files you are ultimately graded on for the lab.

Edit the files with whatever text editor you prefer, and whenever you are ready to submit the lab use the following commands (from within your lab1 repository):

git add lab1fun.cl git add lab1test.cl git commit -m "whatever your message is" git push

(You can do the add/commit/push cycle as often as desired when submitting the lab.)

Lab 1 objectives

Lab 1 is meant to give you practice with the fundamentals of programming in lisp:

• working with executable lisp scripts that also load other lisp files
• writing and calling functions, including recursive functions
• performing type checking
• using cond effectively
• performing basic i/o
• performing basic computation and string manipulation
• working with lists and strings
• devising and applying suitable suites of test cases to your lisp functions

Lab 1 requirements

For lab 1, you are to finish implementing the functions in the provided lab1fun.cl file, and test/debug them using your lab1test.cl script. (When I mark your lab1fun.cl code I'll be using my own test script that loads lab1fun.cl and tests the functions work as specified independently, as well as running the lab1test.cl script you modified.)

The functions themselves are discussed in detail in the lab1fun.cl file (copied below), but in general they involve letting the user build up a list of words, one at a time. After each new word is entered by the user, the program checks to see if it is an exact or near match with any of the existing words:

• is it an exact match?
• is it one character off being an exact match? (i.e. could I make them match exactly by inserting, removing, or changing a single character in one of them?)
• is the new word a prefix for an existing word? (e.g. "foo" would be a prefix for "food", "foolish", "foopy", etc.)

• The lab1fun.cl file cannot have the #! line at the top, whereas the lab1test.cl file must have the #! line at the top.

• In the lab1fun.cl file no statements can appear outside function definitions: i.e. no stand-alone statements/function calls anywhere in the file outside a function definition.

  You can and should create as many additional helper functions in lab1fun.cl as needed. (I used a dozen or so helpers in the sample solution.)

• Your lab1fun.cl functions cannot create or use any functions: they can only access passed parameters.

• No global or local variables can be used in lab1fun.cl, including variables implicitly declared through the use of setf/setq.

• The implementation of the lab1fun.cl functions must follow their specifications provided in (the original) lab1fun.cl as closely as possible.

• All error messages must clearly identify the specific nature of the error.

• You must use recursion, not loops, for any/all iteration/repetition. (The functions are not required to be tail recursive.)

• While there are no specific code standards for the labs, you are still expected to follow sound practices in the use of identifiers, comments, layout etc. Penalties may be applied to code that is difficult to read/debug because of poor coding practices.

lab1fun.cl: the key functions you are to implement

Skeletal versions of the functions have been set up in the lab1fun.cl file, you'll be completing the bodies of each of the functions (at the moment they each simply return nil).

Do not alter the names of the functions or their parameter lists.

The specifications for the functions are provided in the comments in lab1fun.cl, and are repeated below (along with description strings for each).

; (charInsert word c pos) ; ----------------------- ; insert char c after the first pos characters in word ; e.g. (charInsert "arh" \#g 2) would return "argh" ; displays error message and returns nil if pos < 0 or > word length or if word isn't a string (defun charInsert (word c pos) "returns result of inserting character c after the first pos characters of word" nil) ; (charDelete word i) ; ------------------- ; delete the character in position i (0-based) ; e.g. (charDelete "argh" 2) would return "arh" ; displays error message and returns nil if pos < 0 or >= word length or if word isn't a string (defun charDelete (word i) "returns result after deleting the character in position i in word" nil) ; (isprefix pword tword) ; ---------------------- ; return tword if pword is a prefix string for tword, nil otherwise ; displays error message and returns nil if either word is not a string (defun isprefix (pword tword) "returns t iff pword is a prefix of tword" nil) ; (wordMatch word1 word2) ; ----------------------- ; return t iff word1 and word2 are both strings and are exact matches ; displays error message and returns nil if either word is not a string (defun wordMatch (word1 word2) " returns t iff the two words are exact matches" nil) ; (countDiffs word1 word2 i) ; -------------------------- ; assuming word1 and word2 are equal-length strings, counts and returns ; the number of positions in which their characters differ ; in positions i through the end of the word (defun countDiffs (word1 word2 i) "counts the number of characters that differ between two equal-length words" nil) ; (editDist1 word1 word2) ; ----------------------- ; return t if word1 is exactly edit distance 1 from word2, nil otherwise ; where edits are ; - insert a single char ; - alter a single char ; - remove a single char ; displays error message and returns nil if either word is not a string (defun editDist1 (word1 word2) "returns t iff the edit distance between the two words is exactly one" nil) ; (gather collection) ; ------------------- ; gathers a collection of words from the user, one at a time, ; on each recursive call it ; asks user if they want to quit or continue, ; returning collection if they choose to quit ; if they chose to continue it ; gets their new word choice ; checks if it is any of ; - an exact match for an existing word in the collection ; - a prefix match for an existing word in the collection ; - a typo match for an existing word in the collection ; if any of the above are true then it asks the user for confirmation ; before adding the word to the collection ; and recursively calls itself with the (possibly expanded) collection ; displays an error and returns nil if the originally-passed collection is not a list (defun gather (collection) "recursively gathers and adds words to collection after checking if they are matches, prefixes, or typos of existing words" nil)

Additional tips:

• I would very much recommend taking an incremental approach to development: for each function get a very basic version of it working then slowly tweak it to improve the error checking and to handle more complex cases.

  The error messages from the sbcl compiler are generally not very intuitive, so add and debug small chunks of code at a time!

  We'll spend two lab sessions on this lab (Jan. 13th and 20th), but I strongly recommend trying to make decent progress in the first week.

• Expand your test cases using lab1test.cl as you get more complete functionality for each of the functions in lab1fun.cl (especially error checking: create test cases that pass invalid values to the various functions)

• Since you can't declare/use variables in your functions, think about using intermediate/helper functions (and their parameters).

  Example: in my isprefix function I wanted to call the built-in search function to test if one word was a prefix for another, e.g. (search word1 word2) this attempts to find word1 in word2 and return where (what position) it was found, so returns 0 if word1 is a prefix but nil if word1 isn't anywhere in word2 thus I need to see if search returns an integer AND if that integer is 0, but it seems wasteful to use (and (integerp (search word1 word2)) (= 0 (search word1 word2))) and I can't store the result of search in a variable due to the lab restrictions solution: create an isZero function that takes a parameter and checks if it is both an integer and 0, and have the isprefix function pass the result of the search ...somewhere inside cond inside isprefix... ((isZero (search word1 word2)) ...whatever I want to do in this case...) while my isZero function could be simply (defun izZero (n) (and (integerp n) (= 0 n)))

• Remember your recursion and (again) use helper functions at will

  Example: In the (gather collection) function we need to - check if collection is actually a list (ending with an error message if not) - check if they want to quit (ending and returning the collection if so) - get/process the current word, possibly cons'ing it to the collection - call gather recursively to do it again solution: - write one function (e.g. wantsToQuit) to ask the user if they want to quit and return true/false, - write another function (e.g. getNewWord) to ask the user to enter their new word, read and return it - write another function (e.g. processWord) to check that word against the existing collection and return the collection with the new word added/not (as appropriate) - then use logic something like (defun gather (collection) (if (not (listp collectioon)) (format t "....some err message....") (if (wantsToQuit) collection (gather (processWord (getNewWord) collection)))))

• Misc. lisp tips that might be useful:
  • (typep c 'STANDARD-CHAR) will check if variable c currently holds a char
  • (format nil "~A~A~A" strpart1 c strpart2) might be a useful way to 'insert' a char into a string if you can divide it into two parts, which can be done with (subseq str 0 k) and (subseq str k)
  • (char str i) lets you access the i'th char in a string (0-indexed)
  • remember to use string= to compare strings
  • I recommend read-line, rather than read, since read converts everything to uppercase

• If you want to try out your lab1fun.cl functions in the interpretter, rather than through the lab1test.cl script, do the following:
  • cd into your lab1 directory
  • start the interpretter, sbcl
  • load your lab1fun.cl file using the command
    (load "lab1fun.cl")
    this might give some style warnings (functions with unused parameters etc), but if the load succeeds it will return true (T) at the end
  • now you can try calling the individual functions in the interpretter
  • use (quit) to end the interpretter

lab1test.cl: a test script for checking/debugging your functions

The lab1test.cl script is executable. It loads the lab1fun.cl file and interacts with the user to carry out any desired testing.

Its intended use is as a testing (and debugging) mechanism for you to check that your lab1fun.cl functions actually work correctly. All testing and debugging code, including test values, belongs in the lab1test.cl script, NOT in lab1fun.cl. Marks will be deducted if you including testing/debugging content in your lab1fun.cl file.

A few sample data values and test calls are included in the initial version of lab1test.cl, but these are nowhere near complete. A copy of the initial selftest file is shown below.

#! /usr/bin/sbcl --script (format t "~%--- Begin loading lab1fun.cl ---~%") (load "lab1fun.cl") (format t "~%--- completed loading of lab1fun.cl ---~%") ; ---------- unit testing of countDiffs function --------------------------------- (defun testDiffs (w1 w2) (format t "Count of diffs between ~A and ~A: ~A~%" w1 w2 (countDiffs w1 w2 0))) (format t "~%---BEGIN countDiffs tests ---~%") (testDiffs "blar" "abcd") (testDiffs "food" "fool") ; ---------- unit testing of charInsert function --------------------------------- (defun testInsert (text ch index) (format t "Result of insert ~A into ~A at pos 0: ~A~%" ch text (charInsert text ch index))) (format t "~%---BEGIN charInsert tests ---~%") (testInsert "whatever" #\k 0) (testInsert "whatever" #\k 4) (testInsert "whatever" #\k 8) ; ---------- unit testing of charDelete function --------------------------------- (defun testDelete (text index) (format t "Result of delete char at pos ~A from ~A: ~A~%" index text (charDelete text index))) (format t "~%---BEGIN charDelete tests ---~%") (testDelete "whatever" 0) (testDelete "whatever" 4) (testDelete "whatever" 7) ; ---------- unit testing of wordMatch function --------------------------------- (defun testMatch (w1 w2) (format t "Result of comparing words ~A,~A for exact match: ~A~%" w1 w2 (wordMatch w1 w2))) (format t "~%---BEGIN wordMatch tests ---~%") (testMatch "blah" "blah") (testMatch "x" "x") (testMatch "blahg" "blah") ; ---------- unit testing of isprefix function --------------------------------- (defun testPrefix (w1 w2) (format t "Result of checking if ~A is prefix of ~A: ~A~%" w1 w2 (isprefix w1 w2))) (format t "~%---BEGIN isprefix tests ---~%") (testPrefix "foo" "food") (testPrefix "k" "klahd") (testPrefix "blah" "blah") ; ---------- unit testing of editDist1 function --------------------------------- (defun testEdit (s1 s2) (if (editDist1 s1 s2) (format t "Edit dist between ~A and ~A is exactly 1~%" s1 s2) (format t "Edit dist between ~A and ~A is NOT 1~%" s1 s2))) (format t "~%---BEGIN editDist1 tests ---~%") ; single replace (testEdit "argh" "argk") ; single insert (testEdit "first" "firsty") ; single delete (testEdit "blah" "lah") ; ---------- unit testing of gather function --------------------------------- (format t "~%---BEGIN gather tests ---~%") (format t "~%Commencing run of gather with an empty starting collection~%") (format t "Resulting collection at end: ~A~%" (gather nil)) (format t "~%---END OF TESTING---~%~%")

Sample working self-test run

The example below shows a run of the initial lab1test.cl but where the functions in lab1fun.cl been completed:

--- Begin loading lab1fun.cl --- --- completed loading of lab1fun.cl --- ---BEGIN countDiffs tests --- Count of diffs between blar and abcd: 4 Count of diffs between food and fool: 1 ---BEGIN charInsert tests --- Result of insert k into whatever at pos 0: kwhatever Result of insert k into whatever at pos 0: whatkever Result of insert k into whatever at pos 0: whateverk ---BEGIN charDelete tests --- Result of delete char at pos 0 from whatever: hatever Result of delete char at pos 4 from whatever: whaever Result of delete char at pos 7 from whatever: whateve ---BEGIN wordMatch tests --- Result of comparing words blah,blah for exact match: T Result of comparing words x,x for exact match: T Result of comparing words blahg,blah for exact match: NIL ---BEGIN isprefix tests --- Result of checking if foo is prefix of food: food Result of checking if k is prefix of klahd: klahd Result of checking if blah is prefix of blah: blah ---BEGIN editDist1 tests --- Edit dist between argh and argk is exactly 1 Edit dist between first and firsty is exactly 1 Edit dist between blah and lah is exactly 1 ---BEGIN gather tests --- Commencing run of gather with an empty starting collection Do you wish to quit? (yes to quit, anything else to continue) no Please enter the next word for the collection foo Do you wish to quit? (yes to quit, anything else to continue) no Please enter the next word for the collection ick Do you wish to quit? (yes to quit, anything else to continue) no Please enter the next word for the collection food word food is a typo match against a word in the collection Enter yes to add it to the collection anyway, anything else to skip yes Do you wish to quit? (yes to quit, anything else to continue) no Please enter the next word for the collection icky word icky is a typo match against a word in the collection Enter yes to add it to the collection anyway, anything else to skip no Do you wish to quit? (yes to quit, anything else to continue) no Please enter the next word for the collection f word f is a prefix match against a word in the collection Enter yes to add it to the collection anyway, anything else to skip yes Do you wish to quit? (yes to quit, anything else to continue) yes Resulting collection at end: (f food ick foo) ---END OF TESTING---