CSCI 330 Lab 1: Lisp fundamentals

Edit: we'll discuss the lab in the lecture on Jan. 14, discussed further in the lab session of Jan. 19th, and it will be due at the end of the day on Jan. 25th.

The exercise involves forking/cloning a git repository, editing the lab1.cl and test1.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 18. Of that, 14 marks are for the function implementations in lab1.cl and the other 4 are for your testing of those functions in test1.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 lab1.cl and test1.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 lab1.cl git add test1.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 and file i/o
• performing basic computation
• 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 lab1.cl file, and test/debug them using your test1.cl script. (When I mark your lab1.cl code I'll be using my own test1.cl script as well as yours.)

Overview

The functions themselves are discussed in detail in the lab1.cl file (details further below), but in general they involve reading a list of rankings (movie rankings, food rankings, destination rankings, ... any kind of rankings) and evaluating how the rankings would change after a hypothetical head-to-head match between two of the items.

It uses a ranking system similar to ELO in chess: each item has an integer score, with higher scores representing better ranks. The overall rankings are stored as an unsorted list of pairs, each pair being the item's (text) name and its rank, e.g.

( ( "Poke" 1500 )
  ( "Beets" 200 )
  ( "Sashimi" 1600 )
  ( "Green onions" 1300 )
  ( "Burger" 1449 )
  ( "Pizza" 1400 )
)

Possible scores in a match between X and Y would be 1 (X wins), 0.5 (draw), 0 (Y wins), with the results increasing the rank for the winner and decreasing the rank of the loser. A draw increases the score of the lower-ranked item and decreases that of the higher-ranked item. The formulae for calculating the changes is provided as part of the function specifications below.

In this lab we're creating and testing the various functions used to accomplish this, with a precise breakdown provided in the specifications below. In later labs we'll be using these as part of a more comprehensive overall program to maintain rankings over time.

General/structural requirements:

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

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

• The lab1.cl file cannot load other files.

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

  You can and should create as many additional helper functions in lab1.cl as needed.

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

• BONUS: up to 20% for coding lab1.cl in functionally pure form: With the exception of the provided init-random (which sets a global seed for the random number generator) the lab1.cl functions cannot create or use any variables, including variables implicitly declared through the use of setf/setq. (Declaring and using constants is permitted.) Your lab1.cl functions are not permitted to have side effects other than the specified file i/o and specified i/o for interaction with the user. (I.e. you cannot use setf or its variants on any passed lists.) Your lab1.cl functions must use recursion, not loops, for any/all iteration/repetition. (The functions are not required to be tail recursive.) Your lab1.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.

lab1.cl: the key functions you are to implement

Skeletal versions of the functions have been set up in the lab1.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 lab1.cl, and are repeated below (along with description strings for each).

; (readItemFromFile fname) ; ------------------------ ; read and return a single item from the start of the named file ; (init-random fixedSeed) ; ----------------------- ; initialize the random number generator, ; with a pseudo-random value if fixedSeed is nil, ; otherwise treat fixedSeed as the designated seed to be used ; (newRankings item1 item2 score) ; ------------------------------- ; compute and return the new rankings for two items, where the score ; reflects the user's choice between the two of them ; expected parameter values ; score should be 1 if Item1 won, 0.5 for a tie, 0 if Item2 won ; Item content is (name rank), e.g. ("pizza" 1200) ; returns the new rankings in the form ; ((item1name newitem1rank) (item2name newitem2rank)) ; returns (Item1 Item2) unchanged if either of them has invalid format ; (change X Y score) ; ------------------ ; calculate and return the change in ELO ranking for X based on X and Y ranks and the score ; (1 means X won, 0.5 means a draw, 0 means Y won) ; returns 0 if any of the parameters are invalid ; X and Y should be non-negative integers ; if X, Y, and score are valid, then the calculation is ; (round (* 16.0 (- score (expected X Y)))) ; (expected X Y) ; -------------- ; calculate and return the expected score for X vs Y based on their ranks ; returns 0.5 if any of the parameters are invalid ; X and Y should be non-negative integers ; if X and Y are valid, then the calculation is ; (/ 1.0 (+ 1.0 (expt 10.0 (/ (- Y X) 400.0)))) ; (validItem item) ; ---------------- ; return t iff i has the form (name rank) where name is a string and rank is a non-negative integer ; (validRankings itemList) ; ------------------------ ; given a list, L, of item rankings, return t if it has valid form, nil otherwise ; to be valid, L must have length at least 2 and each item must pass validItem ; (pickPair L) ; ------------ ; given a list of items, return a list of two (different) randomly selected items from the list ; returns nil if unsuccessful ; OOPS: diffPair was a helper function I used, it isn't meant to be required. ; (diffPair L m n) ; ---------------- ; if m and n are different positions within list L ; return the pair of elements they represent ; otherwise call pickPair on L to try to find a different pairing ; returns nil if L, m, or n are invalid

Additional tips:

• I would very much recommend taking an incremental approach to development: for each function get a very basic version of it working, without worrying about making it functionally pure, then slowly tweak it to improve the error checking, handle more complex cases, and (if going for the bonus marks) 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!

  I strongly recommend trying to make decent progress before the lab on the 19th, so you've got a good idea of what questions to ask/what to get help with during that lab session.

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

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

• If attempting a functionally pure form and 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.

• If you want to try out your lab1.cl functions in the interpretter, rather than through the test1.cl script, do the following:
  • cd into your lab1 directory
  • start the interpretter, sbcl
  • load your lab1.cl file using the command
    (load "lab1.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

• Misc. lisp tips:
  • Use string= if you need to compare strings.
  • Note that read is probably adequate for this lab, but in general read tends to convert text to all uppercase, so readline is often handier when working with text input from the user.

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

The test1.cl script is executable. It loads the lab1.cl file and interacts with the user to carry out any desired unit testing of individual functions.

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

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

#! /usr/bin/sbcl --script (format t "---loading lab1.cl---~%") (load "lab1.cl") (format t "---load complete, init RNG---~%") (init-random nil) (format t "---RNG initialized---~%") ; name of a test file to read a list of items from (defconstant SourceFile "testfile1") (format t "~%Reading from file ~A~%" SourceFile) (defvar ranksFromFile (readItemFromFile SourceFile)) (format t "Read ~A~%" ranksFromFile) ; test the list has valid form (format t "~%Testing validity~%") (defvar listok (validRankings ranksFromFile)) (format t "Result of tests: ~A~%" listok) ; pick random pair (format t "~%Picking random pair~%") (defvar chosen (pickPair ranksFromFile)) (format t "~%Randomly chosen (X Y) pair: ~A~%" chosen) (format t "~%Breaking down current rank of each~%") (defvar X (car chosen)) (defvar rankX (cadr X)) (format t "Rank of ~A is ~A~%" X rankX) (defvar Y (cadr chosen)) (defvar rankY (cadr Y)) (format t "Rank of ~A is ~A~%" Y rankY) ; see expected score for X vs Y (format t "~%Expected score for ~A vs ~A is ~A~%" X Y (expected rankX rankY)) (format t "Expected score for ~A vs ~A is ~A~%" Y X (expected rankY rankX)) ; show results from possible win,loss,draw between the pair (format t "~%Calculating expected rank change for ~A on win~%" X) (defvar results (change rankX rankY 1)) (format t "Ranking change would be ~A~%" results) (format t "~%Calculating expected rank change for ~A on draw~%" X) (setf results (change rankX rankY 0.5)) (format t "Ranking change would be ~A~%" results) (format t "~%Calculating expected rank change for ~A on loss~%" X) (setf results (change rankX rankY 0)) (format t "Ranking change would be ~A~%" results) ; show new rankings calculation for the pair (format t "~%Given pair ~A, ~A, calculating new rankings for pair on ~A win~%" X Y (car X)) (defvar Xwin (newRankings X Y 1)) (format t "New rankings: ~A~%" Xwin) (format t "~%Given pair ~A, ~A, calculating new rankings for pair on ~A win~%" X Y (car Y)) (defvar Ywin (newRankings X Y 0)) (format t "New rankings: ~A~%" Ywin) (format t "~%Given pair ~A, ~A, calculating new rankings for pair on draw~%" X Y) (defvar Draw (newRankings X Y 0.5)) (format t "New rankings: ~A~%" Draw) (format t "~%----End of testing----~%~%")

Sample working self-test run

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

---loading lab1.cl--- ---load complete, init RNG--- ---RNG initialized--- Reading from file testfile1 Read ((Poke 1500) (Beets 200) (Sashimi 1600) (Green onions 1300) (Burger 1449) (Pizza 1400)) Testing validity Result of tests: T Picking random pair Randomly chosen (X Y) pair: ((Beets 200) (Sashimi 1600)) Breaking down current rank of each Rank of (Beets 200) is 200 Rank of (Sashimi 1600) is 1600 Expected score for (Beets 200) vs (Sashimi 1600) is 3.1612781e-4 Expected score for (Sashimi 1600) vs (Beets 200) is 0.99968386 Calculating expected rank change for (Beets 200) on win Ranking change would be 16 Calculating expected rank change for (Beets 200) on draw Ranking change would be 8 Calculating expected rank change for (Beets 200) on loss Ranking change would be 0 Given pair (Beets 200), (Sashimi 1600), calculating new rankings for pair on Beets win New rankings: ((Beets 216) (Sashimi 1584)) Given pair (Beets 200), (Sashimi 1600), calculating new rankings for pair on Sashimi win New rankings: ((Beets 200) (Sashimi 1600)) Given pair (Beets 200), (Sashimi 1600), calculating new rankings for pair on draw New rankings: ((Beets 208) (Sashimi 1592)) ----End of testing----