Transcript Computing Power (in Apollo Control Computer Units)

Class 16: Mutation
CS200: Computer Science
University of Virginia
Computer Science
M. C. Escher, Day and Night
David Evans
http://www.cs.virginia.edu/evans
Menu
• Mutation Primitives
• PS 5
24 February 2003
CS 200 Spring 2003
2
From Lecture 3:
Evaluation Rule 2: Names
If the expression is a name, it evaluates
to the value associated with that name.
> (define two 2)
> two
2
24 February 2003
CS 200 Spring 2003
3
Names and Places
• A name is not just a value, it is a
place for storing a value.
• define creates a new place,
associates a name with that place,
and stores a value in that place
(define x 3)
24 February 2003
CS 200 Spring 2003
x: 3
4
Bang!
set! (“set bang”) changes the value
associated with a place
>
>
3
>
>
7
(define x 3)
x
x: 7
3
(set! x 7)
x
24 February 2003
CS 200 Spring 2003
5
set! should make you nervous
> (define x
> (nextx)
3
> (nextx)
4
>x
4
24 February 2003
2)
Before set! all procedures
were functions (except for
some with side-effects).
The value of (f) was the
same every time you
evaluate it. Now it might
be different!
CS 200 Spring 2003
6
Defining nextx
(define (nextx)
(set! x (+ x 1))
x)
syntactic sugar for
24 February 2003
(define nextx
(lambda ()
(begin
(set! x (+ x 1))
x))))
CS 200 Spring 2003
7
Evaluation Rules
> (define x 3)
> (+ (nextx) x)
7
DrScheme evaluates
or 8
application sub> (+ x (nextx))
9
or 10
24 February 2003
CS 200 Spring 2003
expression left to right,
but Scheme evaluation
rules allow any order.
8
set-car! and set-cdr!
(set-car! p v)
Replaces the car of the cons p with v.
(set-cdr! p v)
Replaces the cdr of the cons p with v.
These should scare you even more then set!!
24 February 2003
CS 200 Spring 2003
9
> (define pair (cons 1 2))
> pair
(1 . 2)
pair:
1
24 February 2003
CS 200 Spring 2003
2
10
> (define pair (cons 1 2))
> pair
(1 . 2)
pair:
> (set-car! pair 0)
> (car pair)
0
1 21
0
> (cdr pair)
2
> (set-cdr! pair 1)
> pair
(0 . 1)
Any reason to be afraid yet?
24 February 2003
CS 200 Spring 2003
11
> pair
(0 . 1)
> (set-cdr! pair pair)
> (car pair)
pair:
0
> (car (cdr pair))
0
> (car (cdr (cdr pair)))
0
> pair
#0=(0 . #0#)
24 February 2003
CS 200 Spring 2003
2
1
1 pair
0
12
Functional Programming
• Programming without mutation
– Side-effects like printing and drawing on the
screen are really mutations (of the display,
printer, bell, etc.)
• If an expression has a value, it is always
the same – order of evaluation doesn’t
matter
• Substitution mode of evaluation works fine
24 February 2003
CS 200 Spring 2003
13
Imperative Programming
• Programming with mutation (assignment)
• Value of an expression might be different
depending on when it is evaluated
• Substitution model of evaluation doesn’t
work anymore!
24 February 2003
CS 200 Spring 2003
14
Why Substitution Fails?
(define (nextx) (set! x (+ x 1)) x)
> (define x 0)
> ((lambda (x) (+ x x)) (nextx))
2
Substitution model:
(+
(+
(+
(+
0
(nextx) (nextx))
(begin (set! x (+ x 1)) x) (begin (set! x (+ x 1)) x))
(begin (set! 0 (+ 0 1)) 0) (begin (set! 0 (+ 0 1)) 0))
0 0)
24 February 2003
CS 200 Spring 2003
15
Why would a programming
language allow mutation?
• Does it allow us to express computations
we couldn’t express without it?
No! We can express all computations without
mutation. (We’ll see why before the end of
the course…)
• Mutation allows us to express some
computations more naturally and efficiently
– But it also makes everything else more
complicated
24 February 2003
CS 200 Spring 2003
16
Adelphiaize
• Define a procedure that takes a list of
numbers and replaces each positive
number with 0.
> (adelphiaize (list 23 -3 5 6 0 -12))
(0 -3 0 0 0 -12)
24 February 2003
CS 200 Spring 2003
17
Functional Solution
• Build a completely new list
(define (adelphiaize lst)
(if (null? lst)
lst
(cons (min 0 (car lst))
(adelphiaize (cdr lst)))))
24 February 2003
CS 200 Spring 2003
18
Imperative Solution
• Mutate the input list
(define (adelphiaize! lst)
(if (null? lst)
(void) ; nothing to return
(begin
(if (< (car lst) 0) (set-car! lst 0))
(adelphiaize! (cdr lst)))))
24 February 2003
CS 200 Spring 2003
19
Programming with Mutation
> (adelphiaize! (list 23 -5 12 -2 0))
> (define profits (list 23 -5 12 -2 0))
> (adelphiaize! profits)
> profits
(0 -5 0 -2 0)
Imperative
> (define profits (list 23 -5 12 -2 0))
> (adelphize profits)
(0 -5 0 -2 0)
> profits
(23 -5 12 -2 0)
Functional
24 February 2003
CS 200 Spring 2003
20
PS5:
24 February 2003
CS 200 Spring 2003
21
Databases
• Database is tables of fields containing
values
• Commands for inserting, selecting and
mutating entries in the tables
number lastname
firstname college
1
Washington
George
none
2
Adams
John
Harvard
3
Jefferson
Thomas
William and Mary
24 February 2003
CS 200 Spring 2003
22
Representing Tables
• A table is just a cons pair:
– fields (list of fields)
– list of entries
• Each entry is a list of values
number
lastname
firstname
college
1
Washington
George
none
2
Adams
John
Harvard
3
Jefferson
Thomas
William and Mary
(define presidents
(make-table (list ‘number ‘lastname ‘firstname ‘college)))
(table-insert! presidents (list 1 “Washington” “George” “none”))
24 February 2003
CS 200 Spring 2003
23
Selecting Entries
number
lastname
firstname
college
1
Washington
George
none
2
Adams
John
Harvard
3
Jefferson
Thomas
William and Mary
> (table-select presidents ‘college
(lambda (college)
(not (string=? pitem “Harvard”))))
((‘number ‘lastname ‘firstname ‘college)
. ((“Washington” “George” “none”)
(“Jefferson” “Thomas” “William and Mary”))
24 February 2003
CS 200 Spring 2003
24
PS5
• You will implement database commands
for selecting and deleting entries from a
table, and use your database to implement
an auction service
• The database commands similar to SQL
used by commercial database
– In PS8, you will use SQL to interact with a
provided database
24 February 2003
CS 200 Spring 2003
25
Charge
• PS5
– You know everything you need to do it after
today, so start early!
– More open ended than previous problem sets
• Wednesday
– How does mutation effect our evaluation rules?
• Friday: no class
24 February 2003
CS 200 Spring 2003
26