Exam Check-List: Discussion on Part 08 - Continuations

FeG
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 182
Registriert: 6. Dez 2007 07:01

Exam Check-List: Discussion on Part 08 - Continuations

Beitrag von FeG »

Hi,

here is my solution to the eighth topic of the exam check-list (-> spoiler alert...).

Best,
Felix


  1. Given a program, tell which function calls are tail calls. How do you recognize them?

    Code: Alles auswählen

    (define (filter f lst)
       (if (empty? lst)
           empty
           (if (f (first lst))
               (cons (first lst) (filter f (rest lst)))
               (filter f (rest lst)))))
    
    Last line is a tail call to filter, second to last line isn't a tail call. You recognize them by being direct function calls that aren't used as parameter to some other function.
  2. Why can tail calls be implemented more efficiently?

    Because you don't have to keep an evaluation stack, since their result value need not to be handeled in the caller function.
  3. Given two algorithms implementing the same problem, tell which of them is more efficient and why.

    Code: Alles auswählen

    (define (reverse1 lst)
      (if (empty? lst)
          empty
          (append (reverse1 (rest lst)) (list (first lst)))))
    
    (define (reverse2 lst)
      (local ((define (reverse2-acc l acc)
          (if (empty? l)
              acc
              (reverse2-acc (rest l) (cons (first l) acc)))))
      (reverse2-acc lst empty)))
    
    If we take "function calls" as metric for efficience, reverse2 is more efficient as it does less calls. Moreover, reverse2 does only tail call.
  4. Why are tail call optimizations especially important for CPS?

    With CPS, functions never return but do the rest-of-computation themselves. Thus, CPS programs only have tail calls, thus compilers with tail call optimization avoid unnecessary stack frame creation.
  5. Is it worth to transform a program to CPS just in order to benefit from TCO? Why?

    This depends on the size, run-time, etc. of the program. But generally, CPS transformation is "for free" as it can be done automatically, producing only a one-time overhead. Thus it is in most cases worth it, in order to benefit from TCO.
  6. Transform a given program into CPS.

    Code: Alles auswählen

    (define (filter f lst)
       (if (empty? lst)
           empty
           (if (f (first lst))
               (cons (first lst) (filter f (rest lst)))
               (filter f (rest lst)))))
    
    CPS version:

    Code: Alles auswählen

    (define (filter f lst k)
       (if (empty? lst)
           (k empty)
           (if (f (first lst))
               (filter f (rest lst) (lambda (x) (k (cons (first lst) x))))
               (filter f (rest lst) k))))
    
  7. Describe two application scenarios of continuations. Explain the benefits of using continuations.

    See 8.
  8. Explain how continuations could be used for [concurrency/error handing/Web programming].
    • Concurrency: Continuations can be used to implement "discretionary" round-robin scheduling, where processes call each other on their own. Here, the remaining computation of the processes giving control away can be passed to the next process (or stored globally), and thus can be used to resume the first process. Without continuations, a separate process-resumption logic would have to be implemented.
    • Error handling: Continuations can be called in case of an error with a fall-back value, in order to continue the computation with the fall-back value (e.g., return 42 when division by 0 shall be performed). Without continuations, a separate error-handling logic would have to be implemented.
    • Web programming: As HTTP is stateless, continuations can be stored by the server to resume a computation after, e.g., a form value is sent by a user. Without continuations, the whole computation resumption logic has to be manually coded by the developer.
  9. Given a program using the let/cc construct, compute its evaluation result.

    Code: Alles auswählen

    (define (f x)
      (+ 1 (let/cc k (if (= x 0)
                     (k 42)
                     (/ 100 x)))))
    
    (f 5) --> 21
    (f 0) --> 43
  10. Eliminate the use of let/cc in a program by means of transformation to CPS.

    Code: Alles auswählen

    (define (f x)
      (+ 1 (let/cc k (if (= x 0)
                     (k 42)
                     (/ 100 x)))))
    
    CPS version:

    Code: Alles auswählen

    (define (f x)
      (local ((define (division divisor dividend k)
        (if (= dividend 0)
          (k 42)
          (k (/ 100 x)))))
      (division 100 x (lambda (z) (+ 1 z)))))
    
  11. Given a (possibility erroneous) implementation of [exception handling/Web programming], improve it by using real continuations.

    Code: Alles auswählen

    (define (add-to-hash val hash key)
      (+ val (hash-ref hash key)))
    
    Might lead to an error when called with a non-existent key:

    Code: Alles auswählen

    > (add-to-hash 1 (make-hash) 0)
    --> hash-ref: no value found for key: 0
    
    Solve by continuation with fall-back value:

    Code: Alles auswählen

    (define (add-to-hash/c val hash key)
      (+ val
        (let/cc k (if (hash-has-key? hash key)
                      (hash-ref hash key)
                      (k 0)))))
    
    Now we get

    Code: Alles auswählen

    > (add-to-hash/c 1 (make-hash) 0)
    1
    
    (Of course this a contrived example solvable with an if-statement only, but I hope it illustrates the point.)
  12. Explain the general strategy of supporting continuations in an interpreter.

    Use an interpreter in CPS style. If a continuation binding (bindcc) is wanted, bind the identifier to the current receiver function of the interpreter (i.e., the interpreter's current continuation). If a continuation is called, ommit the current receiver function of the interpreter and just call the receiver function bound to the continuation identifier with the argument value of the continuation call.
  13. Find an error in a given interpreter fragment implementing continuations. Fix it.

    Code: Alles auswählen

    (define (interp expr en k)
      (type-case KCFWAE expr
                 [num (n) (k (numb n))]
                 [add (l r) (k (num+ (interp l en) (interp r en)))]
                 ...
                 [id (v) (lookup v en)]
                 [fun (arg body) 
                      (k (closure (lambda (value) (interp body (anEnv arg value en) k))))]
                 ...
                 [app (fun-expr arg-expr)
                      (interp fun-expr en
                              (lambda (fv)
                                (interp arg-expr en
                                        (lambda (av)
                                          (type-case KCFWAE-Value fv
                                                     [closure (f) (f av k)]
                                                     [cont (c) (k av)]
                                                     [else (error "not an applicable value")])))))]
                 [bindcc (id body) (interp body (anEnv id (cont k) en) k)]))
    
    Correct version:

    Code: Alles auswählen

    (define (interp expr en k)
      (type-case KCFWAE expr
                 [num (n) (k (numb n))]
                 [add (l r)
                      (interp l en
                              (lambda (lv) 
                                (interp r en
                                        (lambda (rv)
                                          (k (num+ lv rv))))))]
                 ...
                 [id (v) (k (lookup v en))]
                 [fun (arg body) 
                      (k (closure (lambda (value dyn-k) (interp body (anEnv arg value en) dyn-k))))]
                 ...
                 [app (fun-expr arg-expr)
                      (interp fun-expr en
                              (lambda (fv)
                                (interp arg-expr en
                                        (lambda (av)
                                          (type-case KCFWAE-Value fv
                                                     [closure (f) (f av k)]
                                                     [cont (c) (c av)]
                                                     [else (error "not an applicable value")])))))]
                 [bindcc (id body) (interp body (anEnv id (cont k) en) k)]))
    
    a) [add ...] clause: interp isn't tail-called, this has to be changed to nested calls with appropriate receiver functions.
    b) [id ...] clause: result of lookup has to be passed to receiver function k.
    c) [fun ...] clause: function will be called with the receiver function at application time, thus the closure doesn't store the receiver function at definition, but get's a dynamic receiver "dyn-k" when called.
    d) [app ...] clause, in [cont (c) ...] clause: here the continuation c has to be called, not the current receiver k.

Zurück zu „Archiv“