next up previous
Contents Next: Summary of Rules Up: Programming Techniques Previous: Ensuring Proper Termination

Abstraction

As a program becomes larger, it becomes increasingly difficult to understand. When all of the details of the program are considered at once, they may easily exceed the intellectual grasp of one person. To increase the readability of the program, it is useful to abstract away or ``hide'' unnecessary details. There are two areas in which abstraction may be used: one may hide the details of the data one is working with by using abstract data structures and associated routines (chapter 5); or one may hide fragments of the program to improve clarity. The latter is explored in this section. Hiding fragments of the program increases clarity and often also results in shorter programs.

 

RULE OF THUMB 9:

Use ``let'' to reduce the number of function calls.

 

Example 10:

Write a function called ``cube-list,'' which takes a list of numbers and

returns the same list with each element replaced with its cube. Thus,

(cube-list '(5 3 -15)) should return (125 9 -3375).

By now, with the techniques presented above, the reader should be able to see that the following is a possible solution:
          (defun cube-list (lst)
             (cond ((null lst) nil)
                   (t (cons (* (first lst) 
                               (first lst) 
                               (first lst))
                            (cube-list (rest lst))))))
But note that to compute the cube of each element we must extract it three times from the list using ``first.'' Using Rule of Thumb 9, we can reduce this to only one use of ``first'' for each element. This may be done as follows:
          (defun cube-list (lst)
             (cond ((null lst) nil)
                   (t (let ((elt (first lst)))
                         (cons (* elt elt elt)
                               (cube-list (rest lst)))))))
 

RULE OF THUMB 10:

Encapsulate program fragments into new functions to

improve clarity.

 

Example 11:

Write a function called ``cube,'' which takes a number and returns its

cube. Use ``cube'' to rewrite ``cube-list.''

``cube'' is defined simply as follows:
          (defun cube (elt)
             (* elt elt elt))
Now we can use ``cube'' to rewrite ``cube-list'':
          (defun cube-list (lst)
             (cond ((null lst) nil)
                   (t (cons (cube (first lst))
                            (cube-list (rest lst))))))
These last two definitions are much easier to read and understand, and they do not waste any function calls. Furthermore, cube is a useful tool that may be used in other function definitions.
 

RULE OF THUMB 11:

Encapsulate repeated program fragments into new

functions to reduce program size.

 

Example 12:

Suppose a list of two numbers represents a point in euclidean space.

Write a function called ``get-side,'' which takes three points, a, b, and

c, and a key, k. The three points represent the vertices of a triangle.

The function returns a value as follows:

if k = 1, returns length of side a-b;

if k = 2, returns length of side b-c;

if k = 3, returns length of side c-a;

else, returns 0.

One possible solution is the following:
   (defun get-side (a b c k)
      (cond ((= k 1)
             (sqrt (+ (exp (- (first  a) (first  b)) 2)
                      (exp (- (second a) (second b)) 2))))
            ((= k 2)
             (sqrt (+ (exp (- (first  b) (first  c)) 2)
                      (exp (- (second b) (second c)) 2))))
            ((= k 3)
             (sqrt (+ (exp (- (first  c) (first  a)) 2)
                      (exp (- (second c) (second a)) 2))))
            (t 0)))
Note that we are performing almost the same computation in the first three cases of the ``cond'' clause; specifically, it is to calculate the distance between two points.
 

Example 13:

Write a function called ``distance,'' which takes two points (represented

as two-number lists), and returns the euclidean distance between them.

Use ``distance'' to rewrite ``get-side.''

The function ``distance'' can be implemented simply as follows:
    (defun distance (pt1 pt2)
       (sqrt (+ (exp (- (first  pt1) (first  pt2)) 2)
                (exp (- (second pt1) (second pt2)) 2))))
Now we can rewrite ``get-side'' as follows:
    (defun get-side (a b c k)
       (cond ((= k 1) (distance a b))
             ((= k 2) (distance b c))
             ((= k 3) (distance c a))
             (t 0)))
Thus, using Rule of Thumb 11, we have reduced the size of the program significantly, making it easier to understand.

The concept of abstraction is not unique to LISP. It is also used in other high-level programming languages such as C, Pascal, or FORTRAN.



next up previous
Contents Next: Summary of Rules Up: Programming Techniques Previous: Ensuring Proper Termination



© Colin Allen & Maneesh Dhagat
November 1999