Lab: Functional Abstraction and Recursion

Let's do a simple example so that you can do the more complex examples on your own.

1. First, type the following into the Definitions window:

   (+ 3 (/ (- 13 2) 4))
   

2. Press the button. The Stepper window will appear which contains the following:
   
   This shows you that Scheme evaluated as .

3. Pressing the button in the Stepper window will progress the evaluation one more step:

   
   

4. One final yields the final evaluation:

   
   

(define fact
  (lambda (n)
    (if (= n 0) 
        1
        (* n (fact (- n 1))))))

(fact 3) ; => 3 * 2 * 1 = 6
(fact 5) ; => 5 * 4 * 3 * 2 * 1 = 120

As the first line in your Definitions window, add the following to allow function tracing:

(require (lib "trace.ss"))

(trace fact)

(fact 4)

|(fact 4)	;trace showing that fact is invoked with arg 4
| (fact 3)	;trace showing that fact is invoked with arg 3 from (fact 4)
| |(fact 2)     ;trace showing that fact is invoked with arg 2 from (fact 3)
| | (fact 1)    ;trace showing that fact is invoked with arg 1 from (fact 2)
| | |(fact 0)	;trace showing that fact is invoked with arg 0 from (fact 1)
| | |1		;trace showing value returned from (fact 0) is 1
| | 1           ;trace showing value returned from (fact 1) is 1
| |2            ;trace showing value returned from (fact 2) is 2
| 6		;trace showing value returned from (fact 3) is 6
|24		;trace showing value returned from (fact 4) is 24

The output can get pretty messy with all of those functions traced!

Though you don't need it here, it may be useful to remember that you can tell Scheme to stop tracing functions using untrace, e.g. (untrace * -)

Note: You cannot use the function in the full version of Scheme (Graphical (MrEd, includes MzScheme)), and you cannot trace functions in the trimmed-down version of Scheme (Intermediate Student with lambda).

1. Open a new DrScheme window from the File menu.
2. Choose Help Desk from the Help and search for open-graphics.
3. Click on the entry 'open-graphics'.
4. Scroll to the top of the section (Viewport Graphics) and quickly skim over the contents of the available graphics commands. You should stop at Section 2.4.5 on Ellipses. The idea is not to memorize all the functions since you can always look them up in the Help Desk if you need to. Instead, just get an idea of what functions are available to you.

Here are some things to note as we get started:

1. If you want to use graphics, you need the following line at the top of your Definitions window:

   (require (lib "graphics.ss" "graphics"))
   

2. Before you use any graphics functions, you must initialize the graphics routines:

   (open-graphics)
   

3. Graphics that you would like to appear on-screen must be done in a viewport which you must create. The following defines a variable win1 which is assigned to be a viewport whose title is "cs37" and has dimensions 500 by 500:

   (define win1 (open-viewport "cs37" 500 500))
   

((draw-line win1) (make-posn 100 100) (make-posn 300 400))

((draw-line win1) (make-posn 10 100) (make-posn 30 40))

((draw-line win1) (make-posn 10 100) (make-posn 100 100))

((draw-solid-rectangle win1) (make-posn 20 300) 30 30 (make-rgb 1 0 0))

A couple of more useful commands are (don't type these in - just read them through):

(close-graphics)        ; closes all graphics viewports that may be open
(close-viewport win1)   ; closes the viewport named win1
((clear-viewport win1)) ; erases the viewport named win1

((draw-line win1) (make-posn 10 100) (make-posn 100 100) (make-rgb 0 0 1))

(define draw-blue-line
  (lambda (x1 y1 x2 y2)
    ((draw-line win1)
     (make-posn x1 y1)
     (make-posn x2 y2)
     (make-rgb 0 0 1))))

Note: You should always be sure to save your file often. This might be a good time to do so.

Suppose you want to draw two lines of equal length that meet at a right angle and such that the unattached end point of one line is (x1, y1) and the unattached endpoint of the other line is (x2, y2). That is, we want to draw the two legs of an isosceles right triangle whose hypotenuse is the straight line from (x1, y1) to (x2, y2). We can do this by finding the coordinates of the right angle vertex, (xm, ym), and then drawing a line from (x1, y1) to (xm, ym) and another line from (xm, ym) to (x2, y2). There are actually 2 possible vertices (xm, ym) that will work, one on each side of the hypotenuse. Using a little math, one possible set of coordinates are xm=(x1+x2+y1-y2)/2 and ym=(x2+y1+y2-x1)/2. We can write a function to draw these two legs in viewport win1. Notice that in the solution below, we first define the function draw-lines inside the definition of two-legs:

(define two-legs
  (lambda (x1 y1 x2 y2)
    (define draw-lines                 ;;;draw-lines from the provided
      (lambda (xm ym)                  ;;;(xm, ym) to (x1, y1) and (x2, y2),
        (draw-blue-line x1 y1 xm ym)   ;;;forming the right angle
        (draw-blue-line xm ym x2 y2))) 
    (draw-lines                        ;;;call the draw-lines function with 
     (/ (- (+ x1 x2 y1) y2) 2)         ;;;the computed argument for xm and
     (/ (- (+ x2 y1 y2) x1) 2))))      ;;;the computed argument for ym

(draw-blue-line 50 50 100 150) ;;;draw the hypotenuse
(two-legs 50 50 100 150)       ;;;draw the two legs

Reminder note: Don't forget to save your file often!

• A "level 0" C-curve is a straight line.
• A "level n" C-curve consists of two "level n-1" C-curves meeting at a right angle such that the unattached endpoints of the level n-1 C-curves are the endpoints specified for the level n C-curve.

We could try and write a new procedure to draw level 2 C-curves, then another for procedure level 3 C-curves... but this lab is all about using recursion. So instead, we will write a function called c-curve which draws a C-curve of level n by following the definition we wrote above:

• If n equals 0, we will just draw a straight line from (x1, y1) to (x2, y2).
• Otherwise (if n is greater than 0), we will find the midpoint (xm, ym) as we did in two-legs and draw two level n-1 C-curves, one from (x1, y1) to (xm, ym), and the other from (xm, ym) to (x2, y2).

(define c-curve
  (lambda (x1 y1 x2 y2 level)
    (define draw-curves
      (lambda (xm ym)                       ;;;draws the lower level curves
        (c-curve x1 y1 xm ym (- level 1))   ;;;to the midpoint (xm, ym) from
        (c-curve xm ym x2 y2 (- level 1)))) ;;;(x1, y1) and (x2, y2)
    (if (= level 0)
        (draw-blue-line x1 y1 x2 y2)        ;;;level 0 so draw a straight line
        (draw-curves                        ;;;level is greater than 0 so 
         (/ (- (+ x1 x2 y1) y2) 2)          ;;;call draw-curves with the 
         (/ (- (+ x2 y1 y2) x1) 2)))))      ;;;computed midpoint

Add the c-curve function to your Definitions window and press Run (and save it).

Try each of the following in the Interactions window:

(c-curve 250 100 350 300 0)
(c-curve 250 100 350 300 1)
(c-curve 250 100 350 300 2)

Now add (require (lib "trace.ss")) to the top of the Definitions window and hit Run. (This line can go before or after the require line which included the graphics library.)

Then in interaction window, type:

(trace c-curve draw-blue-line)

(c-curve 250 100 350 300 0)

Clear the graphics window and draw a level 1 C-curve, examining the traced output:

((clear-viewport win1))     ;notice there are two parenthesis on each end
(c-curve 250 100 350 300 1)

Clear the graphics window and draw a level 2 C-curve, again examining the traced output:

((clear-viewport win1)) 
(c-curve 250 100 350 300 2)

Make sure you understand the curve drawn and how it relates to the output of the trace. Call me over if you have questions.

Untrace the functions you had traced, clear the viewport, and draw a level 13 C-curve:

(untrace draw-blue-line c-curve)
((clear-viewport win1))
(c-curve 250 100 350 300 13)

That's it for today. If you finished, great.
If you didn't, finish it up by next class and ask me questions next time if you have them.