next up previous
Next: About this document

CS341, Spring 1996
LISP Assignment #1
Assigned 4/5, due 4/15.



1. Some simple recursive functions.
(In some cases these functions, or ones like them, are defined as part of the CommonLisp language. Do not use the built-in function in writing your function.)

  1. Write a function (add-numbers list), which returns the sum of all the numbers in its list argument. Non-numbers should be ignored. Write two versions: one in which the list is simply a flat list of objects (no nesting), the other in which the list structure may be nested.

  2. Write the function (obj-position object list) which returns the index of the first occurrence of the object in the list. Assume that the list is not nested. (Extra credit: extend the function so it would return a reasonable answer if the list is nested. First discuss what the function should return, then write the function that does so.)

  3. Write the function (generate-indices num) that takes as input an integer 0 or greater, and generates the list (0 1 2 ... num). You should signal an error if the argument is less than 0. (Hint: two functions may be easier than one.)

  4. The next two functions will be a binary search and a sort. In each case it will be useful to have a function that splits a list into its first half and its second half. Write two functions, (first-half list) and (second-half list) that do exactly that. Be careful about lists with odd numbers of elements. You want to assure that the list always splits into two disjoint sublists.

  5. A binary search looks for an element in a sorted list as follows: split the list into the first and second half. If the element in question is less than the first element in the second half of the list, search for it in the first half. Otherwise search for it in the second half. The search terminates when the size of the list is 1 or less. Write the function
    (binary-search integer sorted-list-of-integers)
    The function should return NIL if the input integer is not in the list.

  6. A ``merge sort'' is a simple way of sorting a list. The idea is that you split the list into two lists of equal length, recursively sort each shorter list, then merge the result. (The base case for the recursion is that a list of length 0 or 1 is already sorted.) Write the recursive function merge-sort which takes a single list of integers as input and returns it sorted. In implementing the sort you should also write a recursive function my-merge that takes two sorted lists as input and merges them to produce a single sorted list. (MERGE is already a function in Common Lisp and the interpreter complains if you re-define that function. You are to write your own version of merge; don't use the built-in version.) Extra credit: make merge-sort work on arbitrarily nested lists of integers.

2. A Simple ``Bank''

For this problem you will write some functions that will simulate the operation of a simple bank. A bank is basically just a a set of accounts. Each account in turn has a unique account number, a balance, and a personal identification number (PIN). The PIN is required in order to withdraw money. The top-level functionality for the bank will be:

  1. Create an account. Ask for a PIN as input. You will have to create a unique new account number, which will be communicated back to the user. The account will initially have a balance of 0.
  2. Close an account. The account is removed from the bank's record. It is an error to try to close an account with a non-zero balance. A PIN is required to close an account.
  3. Change a PIN. Prompt for an account number, the old PIN, the new PIN, and the new PIN for verification. It is an error if the account number doesn't exist, if the old PIN is incorrect, or if the two versions of the new PIN do not match.
  4. Deposit money to an account. The input is the account number and an amount. It is an error to try to deposit money to a non-existent account; you do not need a PIN to deposit money.
  5. Withdraw money from an account. Prompt for an account number, a PIN, and an amount. It is an error if the account does not exist, if the PIN that does not match, or if the balance is insufficient.
  6. Balance inquiry. Prompt for an account number and a PIN. Return the account's balance. It is an error if the PIN does not match.
  7. Bank report. Print a list of account numbers and balance for all accounts, in ascending order of account number.

Start by defining data structures for the bank and for accounts. Then you should write some ``support'' functions for doing operations on the bank. Here are some functions you will probably want to write:

(defun bank-verify-account-number (bank account-number))     => boolean
(defun bank-verify-pin            (bank account-number pin)) => boolean
(defun bank-add-account           (bank pin)                 => account-number
(defun bank-delete-account        (bank account-number)      => void
(defun bank-change-pin            (bank account-number pin)) => void
(defun bank-deposit            (bank account-number amount)  => void
(defun bank-withdraw           (bank account-number amount)  => void
Note that these functions will do no error checking, nor will they verify a PIN number. They are low-level operations on the bank data structure.

Next you will implement a simple command loop. It will prompt you for an operation (create account, deposit, withdraw, etc.), prompt you for an account number and PIN as appropriate, and do all the error checking as appropriate: does this account exist? does the PIN match? is there enough money in the account? It then calls the appropriate bank- function to do the transaction, and prints an error or verification message.

The main function you will write is (process-commands bank)---note that you have to create a bank structure ahead of time.

Code available to you:

  1. There is a running version of the code in the file ~c341/code/psl1/bank.fasl. You can load this file, but the Lisp source code is not available. To run the demo you might do the following:
    1. (load "~c341/code/psl1/menus")
    2. (load "~c341/code/psl1/bank")
    3. (process-commands (make-bank :name "My bank"))

  2. To implement the menu and other IO, there are some useful functions in
       ~c341/code/psl1/menus.lisp
    
    The main helper function takes a list of prompt strings as input, puts up the menu, and returns a number that is the index of the string the user selects. There is also some code to input numbers and to input and verify account numbers and PINS. strings. You must use this code in implementing your solution.

  3. A word of either caution or encouragement, as the case may be. The code in menus.lisp is not easy code to get through for the Lisp novice! The idea here is to learn about Lisp constructs by seeing them ``in action'' instead of just seeing them presented out of context in class. In return for putting you through this misery, I will always answer any questions about the code that you care to ask in class, in Email, or any other way. For general questions about the code your best bet is probably to post the question to the class bulletin board. I will answer it if I see it first, but chances are somebody else in the class will answer it faster.




next up previous
Next: About this document



Steve Hanks
Thu Apr 4 18:58:25 PST 1996