Lecture 2 -- Abstraction action

Three important concepts

There are three important generic concepts that you'll need to be aware of 
yin order to manage computational complexity in software.  These concepts are:

  abstraction:  giving something a name; treating something 
                complex as if it were simpler; throwing away
                detail.  We can reduce any complex thing to a
                simpler thing in this way, and worry about the
                details later.

  reference:    mentioning something by name.  This allows us
                to use what was previously abstracted away.

  synthesis:    combining two simple things to make a more
                complex thing; the opposite of abstraction.

(And, of course, you need some primitive, previously-defined  operations at 
some lowest level so that you can eventually stop abstracting.)

These three concepts are essential to controlling the complexity of big 
programs, which is one of the things we'll stress in this course.  In fact, 
the person who wrote one of our LISP books thinks that abstraction is the 
most important concept in computer science:

    "The most important concept in all of computer science is 
    abstraction.  Computer science deals with information and
    complexity.  We make complexity manageable by judiciously
    reducing it when and where possible.

    "I regret that I cannot recall who remarked that computation
    is the art of carefully throwing away information:  given an
    overwhelming collection of data, you reduce it to a usable
    result by discarding most of its content"

                             Guy Steele

Using these concepts - an example

Consider the quadratic formula that you undoubtedly remember from high school 
math classes (sorry for the crude ASCII representation):

                     ________
                    / 2
            -b +- \/ b  - 4ac
        x = _________________

                  2a

This formula tells us what must be computed in finding the roots or 
x-intercepts of a quadratic expression, but it doesn't exactly tell us how, 
at least if we look at this from the point of view of a computer.  In order 
to get a computer to perform these computations, we're going to have to use 
this formula as a specification for the design and implementation of a program.

The design

How would we design a program to find the roots of a quadratic expression, 
following the constraints imposed by what we already know about the 
functional programming paradigm?  

First, that +- operator tells us that there are two roots, and accordingly we 
can decompose this problem of finding the roots into two smaller problems, 
each finding one root.  Right there we've done an abstraction---we've pushed 
some detail out of the way.  We give the big problem a meaningful name, and 
we do the same for the subproblems.  We'll call these problems "quadratic", 
"pos-root", and "neg-root".  Using a little bit of English and a little bit 
of mathematical notation as a design language, we can describe what we've 
done like this:

    quadratic (a,b,c)

    is defined as pos-root (a,b,c)
    combined with neg-root (a,b,c)

     ^             ^
     |             |
     |            here's an example of reference
     |
     |
    here's an example of synthesis

The pos-root problem can be further decomposed.  Essentially, it's a 
division---the result of the numerator divided by the denominator:

    pos-root (a,b,c)

    is defined as numerator (a,b,c)
    divided by    denominator (a,b,c)

(We don't really need the arguments b and c in that denominator function, but 
in the spirit of abstraction, we'll postpone worrying about that detail for 
now.)

To break down the numerator problem, we find that it's the sum of -b and that 
ugly square root, which has a mathematical name:  the discriminant.

    numerator (a,b,c)

    is defined as negate (b)
    plus          discriminant (a,b,c)

What about the denominator?  That's easy:

    denominator (a,b,c)

    is defined as a
    multiplied by 2

As for the discriminant itself, we've left that as part of your first
homework assignment.  What about neg-root?  It's pretty much the same as 
pos-root, except that I'm going to have to change numerator so that it 
subtracts instead of adds.  For consistency, I'll go back and change the 
name of numerator to pos-numerator, and I'll change pos-root accordingly:

    pos-root (a,b,c)

    is defined as pos-numerator (a,b,c)
    divided by    denominator (a,b,c)


    pos-numerator (a,b,c)

    is defined as negate (b)
    plus          discriminant (a,b,c)

and then I'll reuse pos-root and pos-numerator with a little bit of adaptation 
to give me neg-root and neg-numerator:

    neg-root (a,b,c)

    is defined as neg-numerator (a,b,c)
    divided by    denominator (a,b,c)


    neg-numerator (a,b,c)

    is defined as negate (b)
    minus         discriminant (a,b,c)

Unless we want to decompose things like minus and plus, we have pretty much 
abstracted this problem as much as we can.  Since in this course we're going 
to be using Common LISP, we can treat each one of these abstractions as a 
design for a LISP function.

The implementation

How do we turn the design into LISP code?  LISP in its early days was a 
purely functional language and, even though there are lots of things you can 
do in LISP now that do not adhere to functional programming constraints, it 
still retains much of that functional flavor, some of which shows through in 
the language's syntax.  Since we've used a functional notation in our design, 
converting the design to working LISP code will require nothing more than 
some simple cosmetic changes.  We start with this:

    quadratic (a,b,c)
      is defined as pos-root (a,b,c)
      combined with neg-root (a,b,c)

    pos-root (a,b,c)
      is defined as pos-numerator (a,b,c)
      divided by    denominator (a,b,c)

    pos-numerator (a,b,c)
      is defined as negate (b)
      plus          discriminant (a,b,c)

    denominator (a,b,c)
      is defined as a
      multiplied by 2

    neg-root (a,b,c)
      is defined as neg-numerator (a,b,c)
      divided by    denominator (a,b,c)

    neg-numerator (a,b,c)
      is defined as negate (b)
      minus         discriminant (a,b,c)


First, we'll get rid of the commas.  LISP doesn't want commas; it regards 
spaces as delimiters.  We only used commas in our design because that comes 
from standard math notation.

    quadratic (a b c)
      is defined as pos-root (a b c)
      combined with neg-root (a b c)

    pos-root (a b c)
      is defined as pos-numerator (a b c)
      divided by    denominator (a b c)

    pos-numerator (a b c)
      is defined as negate (b)
      plus          discriminant (a b c)

    denominator (a b c)
      is defined as a
      multiplied by 2

    neg-root (a b c)
      is defined as neg-numerator (a b c)
      divided by    denominator (a b c)

    neg-numerator (a b c)
      is defined as negate (b)
      minus         discriminant (a b c)

The syntax of LISP dictates that all functions begin with a left parenthesis 
and end with a right parenthesis, so let's add those details:

    (quadratic (a b c)
      is defined as pos-root (a b c)
      combined with neg-root (a b c))

    (pos-root (a b c)
      is defined as pos-numerator (a b c)
      divided by    denominator (a b c))

    (pos-numerator (a b c)
      is defined as negate (b)
      plus          discriminant (a b c))

    (denominator (a b c)
      is defined as a
      multiplied by 2)

    (neg-root (a b c)
      is defined as neg-numerator (a b c)
      divided by    denominator (a b c))

    (neg-numerator (a b c)
      is defined as negate (b)
      minus         discriminant (a b c))

Note that there are two sorts of things going on in this design.  Sometimes 
we're "defining" functions and other times we're "invoking" them or referring 
to them.  The syntax for these two sorts of things are slightly different, 
for reasons we'll explain in detail as the course progresses.  (The dialect 
of LISP called Scheme is more consistent in this regard.)

To define a new function in LISP, we use a pre-defined function called 
"defun", which stands for "define function".  The syntax for function 
definition is this:

    (defun <function-name> <list-of-arguments> <function-body>)

So now we add the function name "defun" in the appropriate places, and remove 
our English equivalent, "is defined as":

    (defun quadratic (a b c)
      pos-root (a b c)
      combined with neg-root (a b c))

    (defun pos-root (a b c)
      pos-numerator (a b c)
      divided by    denominator (a b c))

    (defun pos-numerator (a b c)
      negate (b)
      plus          discriminant (a b c))

    (defun denominator (a b c)
      a
      multiplied by 2)

    (defun neg-root (a b c)
      neg-numerator (a b c)
      divided by    denominator (a b c))

    (defun neg-numerator (a b c)
      negate (b)
      minus         discriminant (a b c))

The syntax for a plain old function invocation is this:

    (<function-name> <one-or-more-arguments>)

The difference in syntax between function definition and function invocation 
has to do with what things get evaluated when, and we'll talk about that in 
the next lecture.  (Actually, function definition using "defun" is just a 
special form of function invocation.)  For the time being, just remember that 
most of the time you'll be using the syntax shown just above.  If we apply 
that syntax to what we've done so far, we get this:

    (defun quadratic (a b c)
      (pos-root a b c)
      combined with (neg-root a b c))

    (defun pos-root (a b c)
      (pos-numerator a b c)
      divided by    (denominator a b c))

    (defun pos-numerator (a b c)
      (negate b)
      plus          (discriminant a b c))

    (defun denominator (a b c)
      a
      multiplied by 2)

    (defun neg-root (a b c)
      (neg-numerator a b c)
      divided by    (denominator a b c))

    (defun neg-numerator (a b c)
      (negate b)
      minus         (discriminant a b c))

Now what?  We can get rid of all those English names for arithmetic functions, 
and replace them with the LISP equivalents.  Either of your LISP books will
tell you what those equivalents are.  In case you don't have a book, I'll 
tell you the equivalents:

    plus is just +
    minus is just -
    multiplied by is just *
    divided by is just /

See, I told you it was easy.  But before we do those replacements, remember 
the syntax of a function invocation:  the name of the function comes first, 
followed by the arguments to the function.  It's called prefix notation.  
So we don't just replace those arithmetic operators, we have to move them 
into our prefix form and add the appropriate parentheses:

    (defun quadratic (a b c)
      (pos-root a b c)
      combined with (neg-root a b c))

    (defun pos-root (a b c)
      (/ (pos-numerator a b c)
         (denominator a b c)))

    (defun pos-numerator (a b c)
      (+ (negate b)
         (discriminant a b c)))

    (defun denominator (a b c)
      (* a
         2))

    (defun neg-root (a b c)
      (/ (neg-numerator a b c)
         (denominator a b c)))

    (defun neg-numerator (a b c)
      (- (negate b)
         (discriminant a b c)))

Almost done.  There's no "negate" function in LISP.  We just use "-" with one 
argument, which LISP interprets as "subtract the argument from zero":

    (defun pos-numerator (a b c)
      (+ (- b)
         (discriminant a b c)))

    (defun neg-numerator (a b c)
      (- (- b)
         (discriminant a b c)))

The last thing we have to deal with is that nebulous "combined with" 
operation.  Functions return a single value, but here we want to return 
two values.  So what we'll do is combine the two numeric values into a 
single data structure and return that.  We'll use LISP's favorite data 
structure, the list.  The way we get LISP to combine a bunch of separate 
entities into a single list is to pass those entities as arguments to a 
function called "list".  So, if we typed (list 2.0 -5.0) to our LISP 
interpreter, LISP would return (2.0 -5.0).  Packaging up our multiple 
numbers into a single structure satisfies LISP's need to return a single 
value as well as our need to see what looks like multiple values returned by 
a single function.  Here's what it all looks like after we've made this last 
alteration:

    (defun quadratic (a b c)
      (list (pos-root a b c)
            (neg-root a b c)))

    (defun pos-root (a b c)
      (/ (pos-numerator a b c)
         (denominator a b c)))

    (defun pos-numerator (a b c)
      (+ (- b)
         (discriminant a b c)))

    (defun denominator (a b c)
      (* a
         2))

    (defun neg-root (a b c)
      (/ (neg-numerator a b c)
         (denominator a b c)))

    (defun neg-numerator (a b c)
      (- (- b)
         (discriminant a b c)))

That, in gory detail, is a step-by-step illustration of how one goes from a 
design in some off-the-cuff high-level design language to an actual 
implementation in Common LISP.  Initially, we started with a formula, and we 
designed a working implementation of the formula from the top-down by 
breaking off a piece of the problem, designing a solution to that little 
piece, and abstracting away the rest of that problem.  Then we started over 
on the stuff we abstracted away:  we broke off a piece of the remainder, 
designed the solution, abstracted away the rest, and so on.  In fact, if you 
go back and analyze the code, you'll see very little in the way of real LISP, 
and a lot of procedure names we invented on the fly.  We just treated our 
problem and its subproblems as successively refined black boxes, until those 
black boxes map directly onto primitive operations that are already defined 
for us.  This is called "procedural abstraction" (which differentiates it 
from "data abstraction"---something we'll hear more about later on).

We were aided in this process by thinking "functionally".  Thinking 
"functionally" here means that your procedures access only those values 
that are passed to them as arguments, that they return single values, and 
that they leave no side-effects---that is, a procedure does nothing that 
persists after it returns its value.  That's why we're going to keep you 
away from assignment operations for awhile.

If you go back and look at the LISP code just created, some things should be 
obvious.  We generated a lot of procedures (and we didn't even implement the 
discriminant), but each one of those procedures is very small and amazingly 
easy to read.  In fact, I'd argue that someone who had no LISP exposure 
whatsoever could figure out pretty quickly exactly what was intended here, 
even without any supporting documentation.  And that's another thing---because 
we've taken the time to make our function names very descriptive, we've 
reduced the need for in-line documentation (although we haven't eliminated 
the need, so don't start thinking that you don't have to document your work!).
Also, because each of these functions are small and adhere to our functional 
programming constraints, they're a snap to debug if something goes wrong.  So 
while one might want to argue that this approach creates "many unnecessary 
procedure calls and is therefore inefficient code" (we wouldn't want to 
impose on the computer, would we?) or that it requires too many unnecessary 
keystrokes (your fingertips are probably bleeding just in anticipation of all 
this typing), one would also be certifiably insane if one argued that 
understanding and debugging this more "efficient" (yet still functional)
version:

    (defun quadratic (a b c)
      (list (/ (+ (- b)
                  (sqrt (- (* b b)
                           (* 4.0 a c))))
               (* 2.0 a))
            (/ (- (- b)
                  (sqrt (- (* b b)
                           (* 4.0 a c))))
               (* 2.0 a))))

was in any way easier than understanding and debugging what we created 
earlier, wouldn't one?

Clarification: "procedure" vs. "function"

Here's some stuff I didn't think was worth talking about in class, but
you should know it anyway, just so you're not confused.  In the discussion 
above, I've been using "procedure" and "function" pretty much interchangeably.
This is not uncommon in the LISP programming community.  For example, 
consider this definition by Deborah G. Tatar in "A Programmer's Guide to 
Common LISP":

    "A function is a procedure that obeys the usual rules for
    evaluation."  [You'll find out what those rules are next 
    time. - Kurt]

Then she goes on to say this:

    "The words 'procedure' and 'operator' are used in this book
    to refer to functions, macros, or special forms.  In LISP, a
    procedure is a thing that you write to express a process.  
    There is no particular opposition between the terms 
    'function' and 'procedure,' since everything in LISP returns 
    a value, and functions usually express a process."

So this implies to me that "procedure" and "function" are interchangeable in 
LISP world (although there are things called "special forms" and "macros" that 
technically aren't functions according to the LISP specification; more about
those in the weeks to come).  That sort of agrees with Winston and Horn in 
"LISP (3rd edition)", who offer these definitions:

    Procedure:  A step by step specification, expressed in a
                programming language, such as LISP, of how to
                do something.

    Function:   Narrowly, a procedure that has no side effects.
                Broadly, any procedure.

Like I said, these folks sort of agree, but not quite.  Tatar says a function 
follows the usual evaluation rules, while Winston and Horn, if we follow the 
"narrow" definition, say something much more restrictive (but desirable)---
namely, that a function has no side effects.  This definition is certainly in 
keeping with the constraints of the functional programming paradigm, but the 
evaluation rules of LISP do not prohibit side effects.  In any case, don't 
lose sleep over it.  The big whammy here comes when we look to people outside 
LISP world for definitions.  For example, Fischer and Grodzinsky in 
"The Anatomy of Programming Languages" say:

    "In semistandard terminology, a function is a program object
    that receives information through a list of arguments, 
    performs a prescribed computation on that information,
    calculates some 'answer,' and returns that value to the 
    calling program....A procedure is just like a function 
    except that it does not return a value."

ARGH!  But they go on to give themselves, and everyone else, a way out:

    "We will use the word 'function' as a generic word to refer
    to functions...and procedures when the distinctions among
    them are not important."

So, in short, it's sort of sloppy. It's ok to call just about anything in 
LISP world a function, as long as there's no need to worry about the technical 
distinctions between things that are functions and things that aren't (e.g., 
macros and special forms).  When you go outside of LISP world, like in CS 3411,
the people there may be a little bit more picky about how you use those words, 
so be careful.


Copyright 1995 by Kurt Eiselt.  All rights reserved.
-- 


Kurt Eiselt
Assistant Dean, Student Services
College of Computing
Georgia Institute of Technology
Atlanta, GA 30332-0280