CS 214 Lab 4: Clojure

As usual, begin by creating clojure/ and clojure/src/ folders. Move logTable.clj to your clojure/src/ folder. Then use a text editor to edit the file logTable.clj. Take a moment to study it, to see how it implements our basic algorithm, and compare it to the other "programs" you've seen.

Since all computing is accomplished via functions in LISP-family languages, we will define a displayLogTable() function whose specification is

   Receive: start, stop, step, three numbers.
   Output: A table of logarithms,
            beginning with start, ending at stop,
            and with an interval of step.

As we have seen before, a Clojure function has the following structure:

   FunctionDef     ::=   (defn identifier [Parameters]
                            Documentation
                            ExpressionList)
   Parameters      ::=    identifier Parameters | Ø
   Documentation   ::=    "Characters" | Ø
   ExpressionList  ::=    Expression ExpressionList | Ø

Using these productions, define a "stub" function named displayLogTable, with the indicated parameters, above the -main() function.

Our function need not return anything; instead, it needs to implement the second step of our algorithm:

   2. For count = start to stop by increment:
         Display count and the logarithm of count.

To complete the stub, we need the syntax of the Clojure repetition construct. Clojure offers us several options:

Pure LISP-family languages have no repetition constructs, and instead rely upon recursion for repetition.
As a hybrid LISP dialect, Clojure provides a loop function that can be used to solve problems involving tail recursion.
To support compiler-optimization of tail-recursive functions, Clojure provides a recur function that can be used with a loop or a normal function.

In the rest of this exercise, we will explore each of these options.

1. A Pure Recursive Solution

We can derive a recursive solution to our problem as follows:

   Basis: There are no values to output (start > stop).
           -> Do nothing.

   Induction Step: There are values to output (start <= stop).
           -> Display start and its logarithm;
           -> Recursively display the log table
                 from start+step to stop using step.

Since the function may be calling itself many times, we can use an if function to distinquish which of these cases the function is processing. Since our base-case does nothing, we can ignore it, making our recursive algorithm the following;

   if (start <= stop)
      a. Display start and its logarithm.
      b. displayLogTable(start+step, stop, step).

Recall that the pattern for LISP's if function is given by

   IfExpr          ::=   (if CondExpr ThenExpr ElseExpr)
   CondExpr        ::=   Expression
   ThenExpr        ::=   Expression
   ElseExpr        ::=   Expression | Ø

where the first CondExpr is the condition of the if, the value of the ThenExpr is returned if the first one is not nil, and the value of the ElseExpr is returned otherwise. Since our algorithm has two steps instead of one, we need a Clojure function to "convert" multiple expressions into a single Expression (much like a C-family Block "converts" a sequence of statements into a single statement). This is provided in Clojure by the do function:

   DoExpr        ::=   (do ExpressionList)

The effect of this statement is to combine the sequence of epressions that make up our algorithm into a single Lisp Expression. The do() function returns the value of the last Expression in the ExpressionList.

Using this information, add an if function to your function, containing a do function for the Expression to be performed if its condition evaluates to true (i.e., non-nil).

To perform step (a) of our recursive algorithm, we will use the Clojure printf (print-formatted) function:

   Expression      ::=   (printf FormatString Expressions)
   Expressions     ::=   Expression Expressions | Ø

which behaves similarly to Java's printf() function.

To compute the base-10 logarithm of start, Clojure lets us use Java's Math/log10() function.

Using this information, add a printf() function to the do() function to perform step (a) of our recursive algorithm.

Performing step (b) simply requires a recursive call to our algorithm, so add an appropriate recursive call to displayLogTable() to your do() function that implements step (b).

That's it! Save your work and then compile and run your program. The provided -main() function will prompt you to enter the input values, and then invoke displayLogTable() with those values, letting you test that it works correctly for different inputs. Test your function using the values 1, 10 and 0.5. Then try other values; make certain this version works correctly before proceeding.

2. Using the `loop()` function

As mentioned previously, Clojure also provides a loop() function. This can only be used in situations in which tail-end recursion (i.e., the recursive call is the last thing in the function) can be used to solve the problem at hand. As we will see later in the course, clojure's loop() function can be significantly more efficient than a normal recursive function.

If you examine your definition of displayLogTable(), you'll see that it employs tail-end-recursion, so we can use the loop() function to solve our problem. The syntax for this function is as follows:

   LoopFunction   ::=   (loop [ Bindings ] CondExpr Expr (recur Expr))
   Bindings       ::=   identifier initialValue MoreBindings
   MoreBindings   ::=   identifier initialValue MoreBindings | Ø
   LoopExpr       ::=   when CondExpr | if CondExpr | ...

Getting these details correct can be challenging (and time-consuming), especially when you haven't seen or used this function before, so here is a definition of displayLogTable2() that uses the loop() function:

;; loop (indirect-recursion) version
(defn displayLogTable2 [start stop step]
  (loop [i start]                           ; set i to start
    (when (<= i stop)                       ; if i <= stop:
      (printf "The logarithm of %f is %f\n" ;  print one line
                  i (Math/log10 i)
      )
      (recur (+ i step))                    ; recurse, i += step
    )
  )
)

Let's go through this definition line by line, to understand how it works:

The first line:
```
    (loop [i start] 
```
invokes the loop() function, and declares i as a parameter with an initial value of start. The overall effect is similar to writing for (i = start; ....
The second line:
```
    (when (<= i stop) 
```
invokes the when() function, which acts like a single-branch if function for our loop() function. Combined with the first line, the effect is similar to writing for (i = start; i <= stop; ....
The next three lines just invoke printf() to display the logarithm of start, so there is nothing new there.
The next line:
```
     (recur (+ i step)
```
triggers an indirect-recursive invocation of the loop function, passing (+ i step) as the new value for parameter i in the recursive call. Combined with the first two lines, the effect is similar to writing: for (i = start; i <= stop; ++i) {....
Since the loop() function can only be used for tail-recursion, this call to the recurse() function must be the final expression of the when() function's LoopExprList.
The loop function returns the result of the final expression executed.

Add this definition of displayLogTable2() to your source file, immediately above the -main() function. Then uncomment the calls to displayLogTable2() and println at the end of the -main() function. Save your changes and verify that this version produces the same output as displayLogTable().

3. More on Function `recur`

It is worth mentioning that the recur function is not tied to the loop function; it can be used to trigger a recursive call of any function. To illustrate, here is yet another version of displayLogTable() that solves our problem without a loop:

;; indirect/tail-recursive version (just using recur)
(defn displayLogTable3 [start stop step]
  (if (<= start stop)                     ; if start <= stop:
    (do                                      ; do these two things:
      (printf "The logarithm of %f is %f\n"  ; - print one line
                  start (Math/log10 start)
      )
      (recur (+ start step) stop step)       ; - recurse, start+=step
    )
  )
)

As with displayLogTable2(), this version will allow the compiler to perform tail-recursion optimizations that it cannot otherwise perform.

Take a moment to copy-paste this into your source file; then uncomment the final two commented-out lines in -main(), and verify that this achieves the same effect as the previous versions.

When recur is invoked within a function that contains no loop, it triggers a recursive call to that function. When recur is invoked within a loop, it triggers a recursive call to that loop.

Note that the number of arguments passed with recur much match the number of parameters in the function being "recursed": Our loop has a single parameter (i) and so the call to recur in displayLogTable2() has a single argument; our displayLogTable3() function has three parameters (start, stop, and step), and so our call to recur in that function has three arguments.

Wrapping Up

To turn in, create a script.clojure file in which you use cat to concatenate your source file, and then test both of your functions using the values 1, 10 and 0.5. When you are finished, quit script and move your script.clojure file "up" from your clojure folder to its parent folder, with the other script-files.

That concludes the Clojure part of this lab.

Calvin > CS > 214 > Labs > 04 > Clojure

This page maintained by Joel Adams.