Functional Problem Solving (CSC 151 2014F) : EBoards
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
Similar Expressions
> (define a 2)
> (+ 3 (* 5 (+ a 2)))
> ((o implicit-print (l-s + 3) (l-s * 5))(+ a 2))
> (+ 3 (* 5 (call/cc (lambda (cont) (cont (+ a 2))))))
That last one doesn't seem very useful. But we're Schemers. We know how to save things and reuse them.
> (define saved-continuation (vector (lambda (x) x)))
> (+ 3 (* 5 (call/cc (lambda (cont)
(vector-set! saved-continuation 0 cont)
(cont (+ a 2))))))
> (define cont1 (vector-ref saved-continuation 0))
We always have an implicit continuation
> (/ (- x 100) 5)
What's the continuation for x? "Subtract 100, divide by 5, and print."
What do you expect to have happen if I write
> (/ (- (cont1 0) 100) 5)
You evaluate cont1 at 0. That gives you 3 (and prints it?). Then you subtract 100, divide by 5, and print. Expectation of -97/5.
> (/ (- (cont1 0) 100) 5)
3
> (/ (- (cont1 1) 100) 5)
8
When you use a continuation as a function, it REPLACES the current continuation. It gives us a different "what's left to do"
Why would we use this? Consider the following procedure:
;;; Procedure:
;;; sum
;;; Parameters:
;;; lst, a list of numbers
;;; Purpose:
;;; Sum the values in list
;;; Produces:
;;; s, a number
;;; Preconditions:
;;; lst has the form (l1 l2 ... ln)
;;; Postcondiitions:
;;; s = (+ l1 l2 l3 l4 l5 ... ln)
(define sum
(lambda (lst)
(if (null? lst)
0
(+ (car lst) (sum (cdr lst))))))
If we try to sum a list with a non-number, this crashes. Sometimes we want to return a special value if the input is bad.
;;; Procedure:
;;; sum
;;; Parameters:
;;; lst
;;; Purpose:
;;; Sum the values in list
;;; Produces:
;;; result
;;; Preconditions:
;;; lst has the form (l1 l2 ... ln)
;;; Postcondiitions:
;;; If all of l1 ... ln are numbers, then
;;; result = (+ l1 l2 l3 l4 l5 ... ln)
;;; Otherwise
;;; result is #f
One option: First check that everything in the list is a number. (Offends Sam's sensibilities; it means we have to traverse the list twice.)
(define all-number?
(lambda (lst)
(or (null? lst)
(and (number? (car lst))
(all-number? (cdr lst))))))
(define sum
(lambda (lst)
(cond
[(null? lst)
0]
[(not (all-number? lst))
#f]
[else
(+ (car lst) (sum (cdr lst))))))
Whoops! This is atrocious. We keep checking whether it's all numbers again and again and again and again. Which is wasteful
(define sum
(lambda (lst)
(if (not (all-number? lst))
#f
(letrec ([kernel (lambda (lst)
(if (null? lst)
0
(+ (car lst) (kernel (cdr lst)))))])
(kernel lst)))))
Not as bad. Only looks through twice. Once to make sure it's all numbers and once to add. But can we do it once?
Another option: Check the car of the list each time
(define sum
(lambda (lst)
(if (null? lst)
0
(let ([auto (car lst)])
(if (number? auto)
(+ auto (sum (cdr lst)))
#f)))))
Using continuations (define sum (lambda (lst) (call/cc (lambda (escape) (letrec ([kernel (lambda (lst) (if (null? lst) 0 (if (not (number? (car lst))) (escape #f) (+ (car lst) (kernel (cdr lst))))))]) (kernel lst))))))