LECTURE 7: November 2, 2009 

----------------------------------------------------------------------
'hour 1' : design strategies 

four important design strategies: 

 -- domain knowledge* (physics, music, accounting)
    inputs are (usually) ATOMIC DATA; 
    to design the function's entire body, the programmer uses 
    knowledge about some 'worldly' domain; 

 -- function composition* (one function/one task)
    the function doesn't 'touch' its arguments
    typical shape: (define (f x y z) (g x (h y z)))
      where g and h are defined elsewhere 
      (on occasion you may see an if in such functions)
    if you introduce a data def for intermediate results, 
      point to this in the data definition 

 -- structural design 
    inputs are always STRUCTURED (compound) DATA; 
    the function's organization is based on the DATA DEF for one 
      (or more) of the function's parameters 
    one function per interconnected DATA DEFINITION
    recursions in the functions follows self- and cross-references 
      in the data defs 

 -- generative recursion 
    inputs encode problems from a class of problems
    recursion solves a different problem, without regard to data 
    ad hoc insight 
    termination argument 

* it is true that you need domain knowledge for many different designs
  it is equally true that many functions exploit function composition
  that does not mean that these functions are design via composition

two critical design attributes: 
 
 -- with "loops": USE EXISTING ABSTRACTIONS
      a "loop" is either a function or some built-in construct that
      traverses an arbitrarily large piece of data (self-ref needed)
      recursion) and that applies some action to each 'node'

 -- with accumulators 
      remembering and exploiting contexts 
      clarify your accumulator statement

and you CREATE YOUR OWN ABSTRACTIONS 

 -- build your own abstractions (especially loops) 
    when your program calls for it with repetition 

    you notice these when you are tempted to copy 
    and paste; do so. Then abstract! 
   
all design strategies come with some flavor of the design recipes
key is: you are never really stuck until it comes to the creative part 

CHOICES: 

 1. always try to complete the design with one of the four basic 
    design strategies and try in the above order 

    are the parameters atomic? --> exploit the domain 
    does the problem statement suggest separate tasks? --> compose 
    is there structure to the 'main' argument? --> structural
       binary? 
    does the problem statement describe a recursive problem	
       solving process? --> generative recursion, encode 

 2. if you notice that a problem demands an accumulator, 
    finish the basic organization (structural, generative)
    THEN add accumulator 
    
    AFTER completion, check whether loops can shorten the 
    function definitions. Use tests to re-confirm. (When 
    you get older, you won't need this.)

 3. When the program runs, edit and abstract on your own 
    if needed.