Announcements

 See web page for talk schedule

 Dire consequences if I don’t hear from
you by Monday
 Schedule next week:
• Monday – class as usual
• Wednesday – class as usual
• immediately after class – I go to Chicago for
data mining conference, return Sunday (will be
checking email)
• Friday – class as usual: Les LaCroix from
ITS will talk about scripting languages
Scheme Lists
 Lists are a special form of S-
Expressions
 () represents the empty list
 (A) represents list contains A
• (A) is really (A . ())
 (A B) is really (A . (B . () ) )
• (picture on blackboard)
Function Calls
 Function calls represented as lists
• (A B C) means
• evaluate A to a function, evaluate B and C as parameters
 Use the value returned by the call as the
"meaning" of (A B C)
 Why does (car (1 2)) fail?
• (1 2) looks like a function call, but 1 isn't a
function. quote function says "don't evaluate"
• (car (quote (1 2)))
• shorthand: (car '(1 2))
User-defined functions
 The list
(lambda (args) (body))
creates an anonymous function
 (lambda (x y) (+ x y))
 ((lambda (x y) (+ x y)) 5 6)
=> 11
User-defined functions
 The scheme command define binds
values and functions to symbols
• (define pi 3.14159265)
• (define add-two-nums
(lambda (x y) (+ x y)))
 Abbreviated as
(define add-two-nums (x y)
(+ x y))
 Functions in Scheme are first-class
objects – treated just like any other data
type
Recursion
 Breaks a problem down into simpler or
smaller problems
 Mentality:
If trivial case then
supply answer
else
supply part of answer
combined with solution of
smaller problem
Example: nth function
Example: nth function
 (define (nth input n)
(if (= n 0) (car input)
(nth (cdr input) (- n 1))))
Example: copy-list
Example: copy-list
 (define (copy-list input)
(cond ((= (length input) 0) ())
((= (length input) 1)
(list (car input)))
(else (cons (car input)
(copy-list (cdr input))))))
Let and side effects
 let is used to create local variables
• example in DrScheme
 let is good for preventing functions from
affecting the outside world
 A side effect is when a function changes
either one if its parameters or a global
variable
 Scheme uses the ! as a convention to
indicate that a function changes an
argument
Subsets
 How can we define a Scheme function
to create a subset?
 (subsets ‘(1 2 3)) =>
( () (1) (2) (3) (1 2)
(1 3) (2 3) (1 2 3))
 Number of subsets of n+1 values is
twice as many as subsets of n values
 If we have subsets of (1 2), get subsets
of (1 2 3) by duplicating all subsets of
(1 2) and adding 3
Subsets
 Define distrib function to add a new
element to a list of lists
(distrib ‘(() (1) (2) (1 2)) 3) =>
( (3) (3 1) (3 2) (3 1 2))
 (define (distrib L E)
(if (null? L) ()
(cons (cons E (car L))
(distrib (cdr L) E))))
 Then define an extend function to attach
these two together:
Subsets
 (define (extend L E)
(append L (distrib L E)))
 Then defining the subsets code is easy:
 (define (subsets L)
(if (null? L)
(list ())
(extend (subsets (cdr L))
(car L))))
Accessing elements of a list
 (list-tail L k)
• returns tail of a list after removing first k
elements
 (list-ref L k)
• pulls off the k-th element
 Both of these can be slow since lists are
linked lists
Still have not heard from a
handful of people
 No language or date, but paired
• Mark Peralta / Chris Middleton
 Language but no date:
• Robin Smogor / Jenny Cooper
 Paired? Language? Date?
• Scott O’Reilly / Thorin Tatge
 No contact at all
• Kevin DeRonne
• Shaun Reynolds
• Ryan Wakeham
• Chris Ghere
• Steve Fritzdixon
 Looking for partner
• Akira Matoba
 If you have not contacted me at all by the end of the day today (via
email), drop a letter grade on the talk
 If you do not have a language and date scheduled before class on
Wednesday, same penalty
Vectors
 Better to use vectors if accessing
multiple elements of a list:
• (define x #(1 2.0 “three”))
• (vector-ref x 2)
 vector->list and list->vector convert
back and forth
 “->” is Scheme convention for a
conversion function
Lookup tables
 Scheme function assoc does lookup in
a list
• (define my-list
‘( (a 10) (b 20) (c 30))
(assoc ‘b my-list)
 Can do it with non-atomic keys too
• (define price-list
‘( ( (subaru forester) 21000)
( (toyota rav4) 23000)
( (honda cr-v) 21200) ))
(assoc ‘(toyota rav4) price-list)
Nasty Scheme functions
 set-car!
 set-cdr!
 examples
Scoping
 Scheme has lexical scoping. Any
variables which are non-local are bound
to containing lambda parameters, let
values, or globally defined values.
 Example:
(define (f x)
(lambda (y) (+ x y)))
 f takes one parameter, x. It returns a
function of y.
 (f 10) => (lambda (y) (+ 10 y))
Scoping
 Unbound symbols are assumed to be
globals
 Let is a good way to encapsulate
internal variables
 (define cnt
(let ( (I 0) )
(lambda ()
(set! I (+ I 1))
I)))
 Try it by executing the function (cnt)
repeatedly
Let bindings can be subtle
 Notice the difference in behavior
between these two programs:
 (define cnt
(let ( (I 0) )
(lambda ()
(set! I (+ I 1))
I)))
 (define cnt
(lambda ()
(let ( (I 0) )
(set! I (+ I 1))
I)))
Sharing vs. Copying
 If there were no side effects, would
never need to copy an object – just
copy pointers
 If there are side effects, sometimes
need to copy entire objects
 (define A ‘(1 2))
(define B (cons A A))
B = ( (1 2) 1 2)
 show picture
 (set-car! (car B) 10)
Copying Scheme objects
 (define (copy obj)
(if (pair? obj)
(cons (copy (car obj))
(copy (cdr obj)))
obj))
Shallow & Deep Copying
 Shallow copy – just copies a reference
 Deep copy – copies the entire object
 In Java (similar to C++):
• Object O1 = new Object();
• Object O2;
• O2 = O1; // shallow copy
 Java has a clone operation:
• O2 = O1.clone();
 ... but anything referenced by the object is
shallow copied (unless you overload clone)
Equality Checking
 Pointer equivalence – do the two
operands point to the same address?
 Structural equivalence – do the two
operands point to identical structures,
even if in different locations?
 Pointer equivalence is faster but may
not be what you want
• eqv? and eq? are pointer equivalence
• equal? is structural equivalence
 equal? is usually what you want (but
slower)
Loops
 Look like recursion
 (let loop ((x 1) (sum 0))
if (<= x 10)
(loop (+ x 1) (+ sum x))
sum))
 Sums the values from 1 to 10 and
displays it
 Similar to
 for (x=1; x <= 10; sum += x, x++){};
cout << sum;
Control Flow in Scheme
 Scheme’s control flow is normally simple and
recursive:
• First argument is evaluated to get a function
• Remaining arguments are evaluated to get actual
parameters
• Actual parameters are bound to function’s formal
parameters
• Function body is evaluated to obtain function call
value
 Leads to deeply nested expression
evaluation.
Example: Multiply a list of
integers
 (define (mult-list L)
(if (null? L)
1
(* (car L) (mult-list (cdr L)))))
 The call
(mult-list ‘(1 2 3 4 5))
expands to
(* 1 (* 2 (* 3 (* 4 (* 5 1)))))
 Get clever: if a 0 appears anywhere in
the list, the product must be 0.
Improved multiply
 (define (mult-list L)
(cond
((null? L) 1)
((= 0 (car L)) 0)
(else
(* (car L) (mult-list (cdr L)))))))
 Better than above: but still do lots of
unnecessary multiplications (until you
hit zero)
 Can we escape from a sequence of
nested calls once we know they’re
unnecessary?
Exceptions
 C++ handles this problem with
exceptions
 struct Node {
int val;
Node *next;
}
C++ Exceptions
 int mult (Node *L) {
try {
return multNode(L);
} catch (int returnCode) {
return returnCode;
}
int multNode(Node *L) {
if (L == NULL)
return 1;
else if (L->val == 0)
throw 0;
else
return L->val * multNode(L->next);
}
Scheme Continuations
 A continuation is a Scheme mechanism
for storing what you should do with a
return value.
 Two different styles
• Implement your own
• Built in Scheme mechanisms
Scheme continuations
 http://www.cs.utexas.edu/users/wilson/schintro/
schintro_127.html#SEC171
 http://www.cs.utexas.edu/users/wilson/schintro/
schintro_141.html#SEC264
 In most languages, calling a function
creates a stack frame that holds return
address for call and variable bindings
 In Scheme, everything is stored in
garbage collected heap
 Whenever you call a function, you get a
pointer to the calling function: partial
continuation (draw picture)
Scheme continuations
 Scheme actually lets you manipulate
these continuations. This is weird!
 Scheme function:
• call-with-current-continuation
• can be abbreviated as call/cc
 Call/cc is used to call another function,
but it passes along the current
continuation as an argument.
Continuations example
 (define (resumable-fun)
(display 1)
(display (call/cc abortable-fun))
(display 2))

(define (abortable-fun escape-fun)

(display ‘a)
(if (bad-thing-happens)
(escape-fun 0))
(display ‘b))

(resumable-fun)
Continuations with multiply
 Problem: how to use call/cc with an
argument?
 (define (mult-list L)
(call/cc mult-list-main L))
;; this is bad code – can’t take
;; a list
 Trick: have call/cc call an anonymous
function
 (define (mult-list L)
(call/cc (lambda (escape)
(mult-list L escape)))
Multiply with continuations
 (define (mult-list-main L escape)
(cond
((null? L) 1)
((=0 (car L)) escape 0)
(else (* (car L)
(mult-list-main
(cdr L) escape))))

(define (mult-list L)
(call/cc
(lambda (escape)
(mult-list-main L escape)))
Implement your own
continuation
 ;; con has “to be done” multiplications
(define (mult-list L con)
(cond
((null? L) (con 1))
((= 0 (car L) 0)
(else (mult-list (cdr L)
(lambda (n)
(* n (con (car L)))))))
 To actually call the function:
 (define (id x) x)
(mult-list ‘(1 2 3) id)