Exercises
Simulation of other Paradigms and Continuations

The purpose of this exercise is to strengthen your understanding of functions used as classes in Scheme.

First, play with the existing Point class defined on this page available from the on-line version of this material.

As an example, construct two points and add them together. Also, construct two lists of each four points, and add them together pair by pair.

Define a new method in the Point class called (move dx dy), which displaces a point with dx units in the x direction and dy units in the y direction. We encourage you to make a functional solution in which move creates a new displaced point. (After that you may consider an imperative solution, in which the state of the receiving point can be changed with an assignment, set!).

Finally, define a new class, Rectangle, which aggregates two points to a representation of a rectangle. Define move and area methods in the new class.

As a practical remark to the 'class Point ' and the send primitive, be sure to define send before you define Point . (This is done to redefine an existing send procedure in Racket).

On this page we have seen the class ColorPoint, which inherits from Point. The classes make use of virtual methods.

In this exercise you should start with the code in this file.

1. First take a look at the existing stuff, and make sure you understand it. Be aware that both of the classes Point and ColorPoint use virtual methods.

2. Add a method class-of to both Point and ColorPoint that returns the class of an instance.

3. Now repair the method add in Point, such that it always instantiate a class corresponding to the class of the receiver. In other words, if the receiver of add is a Point, instantiate a Point. If the receiver of add is a ColorPoint, instantiate a ColorPoint. You can probably use the method class-of from above. You may encounter a problem, because the constructor of point and color-point take a different number of parameters. You are welcome to default the color of a color point to your favorite color!

This is an open exercise - maybe the start of a minor project - The exercises relates to LAML. I do not recommend this exercise in this variant of PP.

In the original mirror of HTML in Scheme, the HTML mirror functions, return strings. In the current version, the mirror functions return an internal syntax tree representation of the web documents. With this, it is realistic to validate a document against a grammar while it is constructed. In this exercise we will experiment with an object representation of a web document. We will use the class and object representation which we have introduced in this lecture.

Construct a general class html-element which implement the general properties of a HTML element object. These include:

1. A method that generates a rendering of the element
2. A method that returns the list of constituents
3. An abstract method that performs context free validation of the element

In addition, construct one or more examples of specific subclasses of html-element , such as html , head , or body. These subclasses should have methods to access particular, required constituents of an element instance, such as the head and the body of a HTML element, and title of a head element. Also, the concrete validation predicate must be redefined for each specific element.

Program the following discriminant function (lambda (a b c) (- (* b b) (* 4 a c))) in continuation passing style (CPS).

 
(define (discriminant a b c)
  (sub (square b) (mult (mult 4 a) c)))

; AUX functions:
(define (square a)
  (mult a a))

(define (mult a b)
  (* a b))

(define (sub a b)
  (- a b))

In the program above we have provided auxilliary functions for squaring, multiplication and subtraction. These functions must be provided with an extra continuation parameter when you program the CPS variants of the functions. Consider different evaluation orders, and how it affects the CPS variant of the functions.

On the accompanying slide we have studied so-called trampolining of tail calls. In this exercise we will understand if/why it is necessary to apply trampolining on tail calls.

Use return and bounce in a 'normal, (non-tail)recursive factorial function' fact-rec or a similar function that does not make use of tail calls. What happens if we call the function, and if we attempt to drive or schedule the computation of (fact-rec 5) with pogo-stick?

Explain your findings, and draw your conclusions.

The function seesaw, as discussed on the slide, only completes one of the threads. This may be convenient in some situations (if one of the threads runs infinitly), but in general we are interested in the results of both threads. Here is the version of seesaw that we discuss:

  (define (seesaw thread-1 thread-2)                           
    (cond ((eqv? 'done (tag-of thread-1))                      
            (tag-value thread-1))
          ((eqv? 'doing (tag-of thread-1))
            (seesaw thread-2 (call (tag-value thread-1))))))

Program a version of seesaw that - at the very end - return a list of length 2: First element must be the value finally returned by thread-1, and the second element must be the value finally returned by thread-2. Here is an example of the call of the new version of seesaw:

  > (seesaw (fact-iter 5 1) (fib 8))
  (120 21)

Your variant of seesaw may be seen as an example of a loop which maintains some state (the two threads, their status (doing/done), and their values - if they exist). As such, this exercise is a good example of programming an iterative, tail-recursive, state-transitioning function in Scheme.

Here is all you need to get started:

(define (return x) (tag 'done x))                 
(define (bounce thunk) (tag 'doing thunk))   
(define (call thunk) (thunk))    
(define (tag label thing) (cons label thing))
(define tag-of car)
(define tag-value cdr)

(define (fact-iter n acc)
  (if (zero? n)
      (return acc)
      (bounce 
        (lambda ()
          (fact-iter
            (- n 1)
            (* acc n))))))

(define (mem? n lst)
  (cond ((null? lst) (return #f))
        ((= (car lst ) n) (return #t))
        (else (bounce
                (lambda ()
                  (mem? n (cdr lst)))))))

(define (fib n)
  (fib-iter n 0 0 1))

(define (fib-iter n i small large)
  (if (< i n)
      (bounce
        (lambda () 
          (fib-iter n (+ i 1) large (+ large small))))
      (return small)))

(define (pogo-stick thread)                                  
  (cond ((eqv? 'done (tag-of thread))                      
          (tag-value thread))                                
        ((eqv? 'doing (tag-of thread))                     
          (pogo-stick (call (tag-value thread))))))          

; A version of seesaw that delivers 'the value of the fastest thread'.
; The one from the video.
(define (seesaw thread-1 thread-2)                           
  (cond ((eqv? 'done (tag-of thread-1))                      
          (tag-value thread-1))
        ((eqv? 'doing (tag-of thread-1))
          (seesaw thread-2 (call (tag-value thread-1)))))) 

Take a look at this expression:

(let ((x 1)
      (y 2)
      (z 3)
      (v 5))
  (cons x 
        (call/cc (lambda (e) 
                   (cons y  
                         (cons z 
                              (if (even? v) v (e (+ v 1)))))))))

What is the value of the expression? [Needless to say: Figure it out without just putting it into your Scheme REPL.]

Play with it - and try out possible variations.

The same for:

(let ((x 1)
      (y 2)
      (z 3)
      (v 5))
  (+ x 
     (call/cc
       (lambda (e) 
         (+ y 
            (+ z
               (if (even? v) v (e (+ v 1)))))))))

This exercises is strange! Therefore, I discourage you from making it. Most likely, you will be more confused about continuations after having made this exercise than before...

Write a simple recursive function square-list that traverse a list of numbers, with the purpose of squaring each element in the list.

Modify your function such that it captures a continuation of the handling of the third element in the list (if such an element exists). Replace the squared number with this continuation.

Are you able to access the captured contination from the list, and demonstrate how to use it?

Try this:

  > (define xxx (square-list (list 1 2 3 4 5 6)))
  > ((caddr xxx) '()) 

Explain your results (or lack of results). caddr is a convenient composition of car, cdr and cdr.

Now try to assign the captured continuation (with set!) to a global variable remember-continuation. After you have called square-list, play with your captured and stored continuation:

  > (square-list (list 1 2 3 4 5 6))
  > remember-continuation
  > (remember-continuation '())
  > (remember-continuation '(10 11 12))

Discuss and explain the results you obtain.