In your labs/11 directory, create a clojure directory; then create a src directory inside clojure. Copy the files max.clj and listOps.clj from the course directory labs/11/clojure into your new src directory. (There is also a Makefile that you are welcome to copy into our clojure directory, if you want to use make to build and run your program.) Using a text editor, open the Clojure source files, and take a few minutes to study their contents. Then run the program to verify that it runs correctly at the outset.
LISP was the first language to provide the list as a built-in language primitive, and Clojure is a modern dialect of LISP. Since lists are hard-wired into the language and types are not needed to declare variables or parameters, we do not need to do anything to declare the name list or List as a type. As we shall see next, list objects can be defined and used quite easily in Clojure.
While there are a variety of ways to build a Clojure list, two especially convenient ways to define list objects are: (i) using a list literal; or (ii) using the list() function. Given a sequence of expressions, each approach builds a list containing those expressions:
Expression ::= ListLiteral ListLiteral ::= '( Expressions) Expression ::= (list Expressions) Expressions ::= Expression Expressions | ØThe program in max.clj uses both approaches within a let expression to build some list objects and bind them to the names list1, list2, list3, and emptyList.
Note that in a list literal like '(11 22 33), the single quote is strictly necessary. If we were to write (11 22 33), the Clojure compiler would process that as an attempt to call a function named 11, with 22 and 33 as arguments to that function-call. Since there is no function named 11, this will produce an error.
To print a list, we can use the normal Clojure print() or println() functions; the pprint() function can be used to print a list to a file:
Expression ::= (print ListExpr ) Expression ::= (println ListExpr ) Expression ::= (pprint ListExpr Writer)Here, ListExpr is any expression that produces a list object, and Writer is a Java Writer object. The program in max.clj uses calls to println to display each list defined in the program's let expression.
While many list operations are predefined in LISP-family languages, finding the maximum value in a list is not commonly provided, so we will implement it ourselves. Take a moment to review the specification of the operation, if necessary.
Finding the maximum value in a list requires traversing the list, comparing each value to the largest seen thus far. One very general way to perform such a traversal is using recursion, so we begin by deriving a recursive solution to the problem:
Basis: There is one value in the list.
-> Return that value.
I-Step: There are multiple values in the list.
-> Return the larger of the first value and
the maximum of the rest of the list.
To perform the induction step conveniently, a function that computes
the maximum of two values is useful.
We have provided a function for this operation named maxOf2()
in listOps.clj.
Since Lisp-family languages do not perform static type-checking, we should add a bit of validation logic to ensure that a list is being passed to our function. We might use these observations to design the following recursive algorithm:
listMax(aList):
If aList is a list:
Let firstVal be the first value in aList
If aList contains one value:
Return firstVal
Otherwise
Return maxOf2(firstVal, listMax(the rest of aList)).
End if
Otherwise
Return nil.
End if.
Note how this algorithm traverses the list:
in its winding phase, it recursively calls
listMax() to find the maximum in the list consisting of
aList minus its first value.
When it reaches the trivial case
(i.e., aList contains 1 value),
it returns that value, halting the recursion.
The recursion then begins to unwind.
During this phase, each call uses maxOf2() to compare
the maximum returned by listMax() and the first value in its
parameter aList, returning whichever is larger.
This algorithm thus effectively traverses the list
during its winding phase, as it seeks the last value,
and then "un-traverses" the list during its unwinding phase,
when it determines the maximum by comparing
the first value of the current list
with the maximum value seen (thus far) in the rest of the list.
To implement the steps of our algorithm, the following pieces of information may be useful:
Expression ::= (list? Expression)
Expression ::= (count List)
Expression ::= (first List)
Expression ::= (rest List)
This use of first and rest to recursively process a list is typical of a Clojure function. These two simple functions are sufficient to implement the vast majority of list-processing functions.
To illustrate, if the count() function were not already defined for us, it might be defined this way:
(defn count [aList]
(if (list? aList) ; if aList is a list:
(if (empty? aList) ; if it is empty:
0 ; -> 0
(+ 1 (count (rest aList))) ; else -> 1 + count(rest)
)
nil ; else -> nil
)
)
Combined with recursion, first() and rest()
provide amazingly powerful list-processing capabilities.
Once you have defined listMax() in listOps.clj, uncomment the calls to println() in max.clj that display the max values for list1, list2 and list3. (Leave the call to find the max value of emptyList commented out.)
If you have correctly implemented our recursive algorithm for listMax(), then these three calls should work. Continue when this is the case.
Note that we did not account for empty lists when we designed our recursive algorithm. What happens if the caller passes an empty list to our listMax() function? To find out, uncomment the lines at the end of max.clj; then rebuild and run the program. What happens? (Scroll up until you find the top error message.)
Revise your listMax() function to fix this problem. Then verify that max.clj works correctly.
It is worth mentioning that Clojure provides a built-in max() function, which returns the maximum of a sequence of expressions:
Expression ::= (max Expressions) Expressions ::= Expression Expressions | ØTo illustrate, the expressions:
(max 11 22 33) (max 33 22 11) (max 11 33 22will all return 33, the maximum value in each sequence. However, if we try to use max() on a list:
(max '(11 22 33))it will return the list (11 22 33), because '(11 22 33) is a single expression -- a list literal -- so max() just returns that expression. If we gave it two lists:
(max '(11 22 33) '(11 22 33 44))it will return the larger of those lists ((11 22 33 44)). Clojure's built-in max() thus will not find the maximum value in a list. (But we could have used it instead of our maxOf2() function.)
However, the built-in max() function can be leveraged to solve our problem. Here is an alternate, equally robust function listMax2() that uses it:
;; using Clojure's built-in max and apply functions
(defn listMax2 [aList]
(if (list? aList) ; if aList is a list:
(if (empty? aList) ; if aList is empty:
nil ; nil
(apply max aList) ; else apply max to
) ; the items in aList
)
)
This solution uses Clojure's apply() function, which
(i) takes a function and a collection of values as its arguments, and
(ii) returns the result of applying that function to the values in the collection.
To illustrate the following will all return 33:
(apply max '(11 22 33)) (apply max '(33 22 11)) (apply max '(11 33 22))This illustrates one of the most powerful features of functional programming: the ability to pass a function (in this case max()) as an argument to another function (in this case apply()). Many of the Clojure examples available on the Internet use this feature.
Copy-and-paste the preceding definition of listMax2() into listOps.clj. Then add code to max.clj that demonstrates that listMax2() behaves the same way as listMax() for each of the four lists.
Use script to create a script.clojure file that lists the contents of both max.clj and listOps.clj, and that demonstrates that your program builds and runs correctly. Quit script.
That concludes the Clojure part of this lab.
Calvin > CS > 214 > Labs > 11 > Clojure