Homework #3 Solution

Overview




The purpose of this assignment is for you to gain some experience designing and implementing LISP programs. In this assignment, however, you will explore only a few of the many interesting LISP features. The assignment is broken into three parts. The rst part is a fairly straightforward LISP warm-up. The second part requires you to build a pattern-matching program. The third part is related to operations on matrices - addition, multiplication, and transpose. This assignment should be worked on individually. Please turn in your solutions electronically via Kodethon or Canvas by the due date.







Part 1: Simple Function De nitions (35 points)




The goal of this part of the homework is to familiarize you with the notions of lists, function de nitions, and function applications in Lisp. This part requires you to de ne a number of simple functions:




The test program for part one may be executed by calling ./test.sh 1




De ne a function element-count that takes an atom and a list and returns the number of occurrences of that atom in the list. Searching in the rst level in the list will su ce.



(element-count ’h ’(2 d t h 3 h 6))



2




(element-count ’hi ’(good morning hello))



0




De ne a function min-mean-max that takes a list of numbers (with at least one element) and returns a list of length 3 that consists of the smallest number, the mean (reduced to the simplest fraction) of all numbers and the largest number.



(min-mean-max ’(2 5 11 15 7 1 8)) (1 7 15)






(min-mean-max ’(6 6 5 -4 3 2 1 1)) (-4 5/2 6)












1



De ne a function shift that takes a list and an integer n as input and returns the same list, but with the rst element shift to the end of the list n times.



(shift 1 ’(1 2 3 4)) (2341)






(shift 2 ’(1 2 3 4 5))) (34512)









De ne a function pivot that takes a list l and a number n and splits it into two lists, one containing all the numbers in l less than n and the other containing all numbers in l greater than or equal to n. Note: preserve the relative order of elements inside the list.



(pivot 3 ’(3 2 5 1 4)))



((2 1) (3 5 4))




(pivot 3 nil)) (NIL NIL)



Write a function break-list that takes a list and an atom and splits the list using the atom as the delimiter. If the array does not contain the delimiter, then it returns the entire list as it is.



(break-list ’1 ’(a b 1 c d 1 e f))



((a b) (c d) (e f))




(break-list ’a ’(b c d e)) ((b c d e))









Write a quicksort function that sorts a list. (Review of the quicksort algorithm: First pick an element and call it the pivot. The head of the list is an easy option for pivot. Partition the rest of the list into two sublists, one with all the elements less than the pivot and the other with all the elements not less than the pivot. Recursively sort the sublists. Combine the two sublists and the pivot into a nal sorted list). You can reuse the idea of a pivot from the question 4.



(quicksort ’(2 9 5 3 8))



(23589)

























2



Part 2: Assertions and Simple Pattern-Matching (35 points)










Before we start building the pattern-matching function, let us rst build a set of routines that will allow us to represent facts, called assertions. For instance, we can de ne the following assertions:




(this is an assertion)




(color apple red)




(supports table block1)




Here each assertion is represented as a list. The set of assertions can be maintained in a database by representing them in a list. For instance, the following list represents an assertion database containing the above assertions:




((this is an assertion) (color apple red) (supports table block1))




Patterns are like assertions, except that they may contain certain special atoms not allowed in assertions, the single characters ? and !, for instance.




(this ! assertion)




(color ? red)




Write a function match that compares a pattern and an assertion. When a pattern con-taining no special atoms is compared to an assertion, the two match only if they are exactly the same, with each corresponding position occupied by the same atom.




The test program for part two may be executed by calling ./test.sh 2




(match ’(color apple red) ’(color apple red))



T




(match ’(color apple red) ’(color apple green))



NIL




The special atom ? matches any single atom.




(match ’(color apple ?) ’(color apple red))



T




(match ’(color ? red) ’(color apple red))



T




(match ’(color ? red) ’(color apple green))



NIL




In the last example, (color ? red) and (color apple green) do not match because red and green do not match.




The special symbol ! expands the capability of match by matching any one or more atoms.




3



(match ’(! table !) ’(this table supports a block))



T




Here, the rst ! symbol matches this, table matches table, and the second ! symbol matches supports a block.




(match ’(this table !) ’(this table supports a block))



T




(match ’(! brown) ’(green red brown yellow))



NIL




In the last example, the special symbol ! matches green red. However, the match fails because yellow occurs in the assertion after brown, whereas it does not occur in the assertion. However, the following example succeeds:




(match ’(! brown) ’(green red brown brown))



T




In this example, ! matches the list (green red brown), whereas brown matches the last element.







Part 3: Matrix Operations (30 points)




Suppose we represent a matrix in LISP as a list of lists. For example, ((a b) (c d)) would represent a 2*2 matrix whose rst row contains the elements a and b, and whose second row contains the elements a and c. You may assume that the matrices are well-formed and compatible.




The test program for part three may be executed by calling ./test.sh 3




Write a function matrix-add that takes two matrices as input and outputs the sum of the two matrices.



(matrix-add ’((1 2) (2 1)) ’((1 2) (3 4))) ((2 4) (5 5))






Write a function matrix-multiply that takes two matrices as input and multiplies them and outputs the resultant.



(matrix-multiply ((1 2) (2 1)) ’((3 1) (1 3)))



((5 7) (7 5))




Write a function matrix-transpose that takes a matrix as input, and outputs its transpose.



(matrix-transpose ’((1 2 3) (4 5 6))) ((1 4) (2 5) (3 6))



4
Notes




The only le that needs to be modi ed is hw3.l. The command to use Common LISP is clisp.




Appendix A of LISPcraft summarizes LISP’s built-in functions. Each function is ex-plained brie y. You will nd this a very useful reference as you write and debug your programs. Also, you can get help about clisp by typing:




man clisp




The test le test.l can be loaded ithin LISP by typing:




(load "test.l")



The test program may be executed by calling ./test.sh. This is going to test all of the parts.




You may de ne additional helper functions that your main functions use. Be sure, though, to name the main functions as speci ed since the test program uses those names.




When developing your program, you might nd it easier to test your functions rst interactively before using the test program. You might nd trace, step, print, etc. functions useful in debugging your functions.




A few points to help the novice LISP programmer:




{ Watch your use of (, ), and . Be sure to quote things that need to be quoted.




{ To see how lisp reads your function, use pretty printing. For example, (pprint (symbol-function foo)) It will print out the de nition of the function foo, using indentation to show nesting. This is useful to locate logically incorrect nesting due to, e.g., wrong parenthesizing.




{ If you cause an error, Common Lisp places you into a mode in which debugging can be performed (LISPcraft section 11.2). To exit any level, except the top level, type quit or :q. To exit the top level, type (exit) or (bye).




Start early!































5