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.)

Attempting functional purity:

• Your lab1fun.cl functions cannot create or use any variables including variables implicitly declared through the use of setf/setq. (The only data values your functions can use/access are the passed parameters.)

• Your lab1fun.cl functions are not permitted to have side effects other than i/o with the user. (Note this effectively means you cannot use setf or its variants.)

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

• Your lab1fun.cl functions cannot use sequences of statements: each function's body must be a single statement which cannot be block, let, prog or their variants.

  General/structural requirements:

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

• 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.)

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

• 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, possibly a version that isn't functionally pure, then slowly tweak it to improve the error checking, handle more complex cases, and achieve functional purity.

  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)))

• If you have a function that seems to need to do two separate things in sequence, e.g. prompt a user then read/return their response, consider passing one of those actions as a parameter to a function that does the other.

  Example: Suppose I need to prompt the user to enter yes/no in response to a question, then return true if they answered yes, false otherwise. My yesOrNot function can take the result of the prompt as a dummy parameter and return the result of the read/compare The caller actually passes the result of the format prompt, e.g. (defun yesOrNot (promptResult) ; return the result of comparing the user response to "yes" (string= "yes" (read-line))) (defun someCaller () ; ask the user a yes/no question as part of the call to yesOrNot (if (yesOrNot (format t "Does this example make sense (yes or no)?")) ; deal with yes's (format t "yay~%") ; deal with no's (well, not yes's) (format t "boo~%")))

• 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 collection)) (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

• If it's any consolation, in labs 2 and 3 we'll be discarding functional purity while we focus on lisp's handling of higher order functions, its macro system, and its treatment of lisp code as lisp data.

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---

Hints/tips for the seven functions

You're definitely not required to use these approaches, but if you're struggling with any of the functions here are the approaches I used to try and meet our functionally pure(ish) goals.

If you'd like to use this as your approach I suggest sketching a quick graph of which functions call which (and which ones recurse), as that will definitely help clarify the structure of what's going on. (It's easy to get a bit muddled just reading through the functions individually.)

; (charInsert word c pos) ; ----------------------- ; check for incorrect types on any of the params, ; then a pos that's too small/too big, ; then use (format nil "~A~A~A" chunk1 c chunk2) to build the string, ; where chunk1 and chunk2 are the first/last half of word ; (obtained by using (subseq word startpos numchars)) ; (charDelete word i) ; ------------------- ; very similar to charInsert: ; error check the parameter types and value of i ; then use (format nil "~A~A" chunk1 chunk2) to get the desired start/end of word, ; though you may need special cases for deleting the first/last char ; (isprefix pword tword) ; ---------------------- ; check both are strings first, then check (search pword tword) returns 0: ; I found it helpful to add an (iszero n) helper function ; that returns t iff n is the integer 0 ; (wordMatch word1 word2) ; ----------------------- ; pretty basic: make sure both are strings then check if they're string= ; (countDiffs word1 word2 i) ; -------------------------- ; recursive: ; base case i >= word1 length, return 0 ; else if the two words are the same in position i (checked with char= and using (char w i) to get the chars) ; then return the result of a recursive call with i+1 ; else return 1 + the result of a recursive call with i+1 ; (editDist1 word1 word2) ; ----------------------- ; if wordmatch returns true then t ; else if countdiffs w1 w2 returns 1 then t ; else if isprefix returns true then t ; else if foundInsert w1 w2 0 returns true then t ; else if foundInsert w2 w1 0 returns true then t ; else false ; (gather collection) ; ------------------- ; recursive: ; error check that collection is actually a list (err otherwise) ; else call helper function yesOrNo, passing a prompt asking if they wish to quit ; returning collection if it returns true ; else recursively call gather, but call/pass processword as it's parameter, ; where processword's parameters are ; (1) a call to readentry, to which you pass the format call prompting the user to enter another word ; (2) collection ; ----------------- HELPER FUNCTIONS --------------------------------------- (yesOrNo promptResult) ; -------------------- ; it assumes format was called to print the prompt, ; and the (nil) returned by format is in the promptResult parameter (which we'll ignore) ; yesOrNo simply returns the result of applying string= "yes" to the result of a call to read-line (readEntry promptResult) ; -------------------- ; it assumes format was called to print the prompt, ; and the (nil) returned by format is in the promptResult parameter (which we'll ignore) ; readEntry simply returns the result of a call to read-line ; (foundInsert w1 w2 i) ; --------------------- ; it returns true if we can insert a character into w1 at position i or later to make w1/w2 match ; recursive: ; base cases: if i is w1's length or w1 and w2 differ in position i ; then insert w2's i'th char into w1 and return true if the strings then match, false otherwise ; (they have to match after a single insert in order to be edit distance 1) ; general case: return the result of recursing on the next position ; (processWord word collection) ; ----------------------------- ; uses checkAgainstCollection to see if the word is a match/near match for anything in collection, ; passing the result (along with word and collection) to processMatchType, ; which will return an appropriately updated collection which processWord can then return ; (processMatchType match word collection) ; ---------------------------------------- ; assumes match is the word "none" if word is not a match/near-match for anything in the collection, ; and something else otherwise ; thus if match is "none" then returns the cons of word and collection, ; otherwise calls yesOrNo, passing the format call asking the user if they wish to add the word anyway, ; returning the cons of word and collection if they said yes, or just collection if they said no ; (checkAgainstCollection word collection) ; ---------------------------------------- ; returns "exact", "prefix", or "typo" if the word matches something in the collection, "none" otherwise ; recursive: ; returns "none" if collection is empty list ; otherwise calls the various match types on word and car of collection: ; if wordMatch returns true then return "exact" ; if isprefix returns true then return "prefix" ; if editDist1 returns true then return "typo" ; otherwise return result of recursive call with word and cdr of collection