程序代写代做代考 scheme CSE1729: Introduction to Programming

CSE1729: Introduction to Programming
Mutable data:
Objects, Streams, and
Environment Semantics
Robert McCartney

Our story thus far…
We have focused, so far, on a programming paradigm called: Functional Programming.
When you build a program in a functional style, computation proceeds as the result of function application.
In particular: binding a variable only happens when a function is called. This means (the golden rule of a functional language):
Once a variable is bound, its value (in a particular environment) never changes



The virtues of functional programming



Functional programming is predictable and relatively easy to analyze. Why?
Variable values “never change.”
Function definitions never change: Once a function has been defined (in a particular environment), applying it multiple times to a particular value will always result in the same value–it behaves like a mathematical function.

Mutable data is powerful



However, the notion of changing the value of a variable can have some powerful implications.
In particular (and perhaps most importantly), it can naturally model some important and intuitive computational frameworks.
In SCHEME, we introduce a new destructive ingredient that allows us to change the value of a variable in an environment.

With great power… comes great responsibility
Once we forsake purely functional programming, program dynamics become more…

With great power… comes great responsibility
Once we forsake purely functional programming, program dynamics become more…

Expressive

With great power… comes great responsibility
Once we forsake purely functional programming, program dynamics become more…

Complex

Motivation



Recall the queue datatype. Problem: enqueue/dequeue in constant time.
Idea: If we “knew” where the end of the queue was, we could avoid traversing the entire structure during an enqueue.
Idea: represent a queue as a pair which maintains the front and back of the queue simultaneously.
Then…

A better queue? Inherently non-functional
We will maintain a queue as a list “remembering” both head and tail.
Notice that we can enqueue and dequeue in a fixed amount of time (independent of the number of elements in the queue) if we remember the tail.


Head Tail
3
4
5

A better queue? Inherently non-functional
We will maintain a queue as a list “remembering” both head and tail.
Notice that we can enqueue and dequeue in a fixed amount of time (independent of the number of elements in the queue) if we remember the tail.


Head Tail
3
Insertion
4
5

A better queue? Inherently non-functional
We will maintain a queue as a list “remembering” both head and tail.
Notice that we can enqueue and dequeue in a fixed amount of time (independent of the number of elements in the queue) if we remember the tail.


Head Tail
3
Insertion
4
5
6

A better queue? Inherently non-functional
We will maintain a queue as a list “remembering” both head and tail.
Notice that we can enqueue and dequeue in a fixed amount of time (independent of the number of elements in the queue) if we remember the tail.


Head Tail
3
Insertion
4
5
6

A better queue? Inherently non-functional
We will maintain a queue as a list “remembering” both head and tail.
Notice that we can enqueue and dequeue in a fixed amount of time (independent of the number of elements in the queue) if we remember the tail.


Head Tail
3
Insertion
4
5
6

A better queue? Inherently non-functional
We will maintain a queue as a list “remembering” both head and tail.
Notice that we can enqueue and dequeue in a fixed amount of time (independent of the number of elements in the queue) if we remember the tail.


Head Tail
3
Insertion
4
5
6

A better queue? Inherently non-functional
We will maintain a queue as a list “remembering” both head and tail.
Notice that we can enqueue and dequeue in a fixed amount of time (independent of the number of elements in the queue) if we remember the tail.


Head Tail
3
4
5
6

A better queue? Inherently non-functional
We will maintain a queue as a list “remembering” both head and tail.
Notice that we can enqueue and dequeue in a fixed amount of time (independent of the number of elements in the queue) if we remember the tail.


Head Tail
3
Deletion
4
5
6

A better queue? Inherently non-functional
We will maintain a queue as a list “remembering” both head and tail.
Notice that we can enqueue and dequeue in a fixed amount of time (independent of the number of elements in the queue) if we remember the tail.


Head Tail
3
Deletion
4
5
6

A better queue? Inherently non-functional
We will maintain a queue as a list “remembering” both head and tail.
Notice that we can enqueue and dequeue in a fixed amount of time (independent of the number of elements in the queue) if we remember the tail.


Head Tail
3
Deletion
4
5
6

A better queue? Inherently non-functional
We will maintain a queue as a list “remembering” both head and tail.
Notice that we can enqueue and dequeue in a fixed amount of time (independent of the number of elements in the queue) if we remember the tail.


Head Tail
Deletion
4
5
6

A better queue? Inherently non-functional
We will maintain a queue as a list “remembering” both head and tail.
Notice that we can enqueue and dequeue in a fixed amount of time (independent of the number of elements in the queue) if we remember the tail.


Head Tail
Deletion
5
6
This notion of insert changes a binding!
4

Basic mechanics of mutable data
Before discussing mutation of structured data…
We’ll return briefly to simple data types
We’ll introduce the notion of object, a principled way to control the complexity of mutable data.
Then….finally…we’ll return to structured data and give an efficient implementation of a heap.



The set! special form

The set! changes the value of a variable in the assignment in which it is called.
A simple example:
> (define a 3)
>a
3
> (set! a 4) a:4 >a
a:3

4
> (set! a 5) >a
5
a:5

The sequence/begin function
The sequence function
 



 

(begin )

carries out a sequence of function calls, returning the value of the last call.
In purely functional programming, there would be no point to such an operation (since the return value would always simply be the value of ), but now that we have side-effects, sequences can be a valuable tool.
Warning: Your textbook calls this command: sequence.

We can have sequences of expressions without begin
(define ( )



)
(let (( ))



)
(cond
( )

(else ))
Value of function application, let, or cond, is the value of the last evaluated

What’s the big deal?
Our programming enterprise will be most successful if we build computational models that reflect the “intuitive, real-world” structure of the objects we’re modeling.
When we want to model objects that change over time, we have a choice to make:
Model them functionally, as a sequence of “different” objects.
Model them via mutation, as single object that is changing.





Consider sorting: philosophically, are we creating a new list, that is sorted, or massaging the old list into sorted order? It has far reaching consequences for efficiency, intelligibility, modularity, …

A simple example

A simple example: maintaining balance information in a bank account:
> (define balance 100)
> (define (withdraw f)
(cond ((> f balance)
(“Insufficient funds!”))
(else
(set! balance(- balance f))
balance)))
> (withdraw 40)
60
> (withdraw 40)
20
> (withdraw 40)
“Insufficient funds!”

A simple example

A simple example: maintaining balance information in a bank account:
> (define balance 100)
> (define (withdraw f)
(cond ((> f balance)
(“Insufficient funds!”))
(else
(set! balance(- balance f))
balance)))
> (withdraw 40)
60
> (withdraw 40)
20
> (withdraw 40)
“Insufficient funds!”
Non-functional behavior

A problem with this implementation
> (define balance 100)
> (define (withdraw f)
(cond ((> f balance)
“Insufficient funds!”)
(else
(set! balance (- balance f))
balance)))

Anyone can now change the bank balance…
(setq! balance 1000000000)
We’d like an abstraction barrier, so that the only way to change the balance is via the official withdraw function

Abstraction barriers
The Ford model T engine
Expose only what must be exposed:
• Protect the internals from accidental (or malicious) tampering.
• Protect the user.

Abstraction barriers
Expose only what must be exposed:
• Protect the internals from accidental (or malicious) tampering.
• Protect the user.
The user interface

Abstraction barriers
Expose only what must be exposed:
• Protect the internals from accidental (or malicious) tampering.
• Protect the user.

Abstraction barriers
Expose only what must be exposed:
• Protect the internals from accidental (or malicious) tampering.
• Protect the user.
Hot water system

Abstraction barriers
The user interface
Expose only what must be exposed:
• Protect the internals from accidental (or malicious) tampering.
• Protect the user.

Hiding the balance: recall
environment definition semantics
Recall lexical scope rules: the value of a free variable in a function is determined by the environment in which it was defined.
To warm up:
> (define (incrementer x)
(lambda (z) (+ x z)))
> (define add-5 (incrementer 5))
> (add-5 10)
15
> (define x 50)
> (add-5 10)
15
>

Hiding the balance: recall
environment definition semantics
The value of x in the body of
Recall lexical scope rules: the value of a free variable in a function is add-5 is determined by the
determined by the environment in which it was defined.
environment in which add-5 was


> (define (incrementer x)
(lambda (z) (+ x z)))
> (define add-5 (incrementer 5))
> (add-5 10)
15
> (define x 50)
> (add-5 10)
15
>
defined.
To warm up:

Hiding the balance: recall
environment definition semantics
The value of x in the body of


Recall lexical scope rules: the value of a free variable in a function is add-5 is determined by the
determined by the environment in which it was defined.
environment in which add-5 was
defined.
(lambda (z) (+ x z))
add-5:
> (add-5 10) x:50 15
>
To warm up:
> (define (incrementer x)
(lambda (z) (+ x z))) x:5
> (define add-5 (incrementer 5))
> (add-5 10)
15
> (define x 50)

Hiding the balance
The basic definition
(define (new-account initial-balance)
(let ((balance initial-balance))
(lambda (withdrawal)
(cond ((> f balance)
“Insufficient funds!”)
(else
(set! balance (- balance f))
balance)))


Usage
> (define my-acct-w (new-account 100))
> (my-acct-w 30)
70 Note nonfunctional behavior! > (my-acct-w 30)
40
This function is returned; it has access to balance

Who sees what?
(define (new-account initial-balance)
(let ((balance initial-balance))
(lambda (withdrawal)
(cond ((> withdrawal balance)
“Insufficient funds”)
(else
(set! balance (- balance withdrawal))
balance)))))
balance
This function is passed out of the environment; note that it refers to balance.
(define my-acct-w (new-account 100))
balance does not exist in this environment, but my-acct-w can change it!

This is important…let’s do it again
Consider the code fragment:
(define (make-hidden-value initial-value)
(let ((value initial-value))
(define (mult-by x) (set! value (* value x))
value)
(define (add-to y) (set! value (+ value y))
value))
(cons mult-by add-to)))


What does it do? It creates an environment with a variable value. It passes back two functions (as a pair) which can operate on value.

In action…
(define (make-hidden-value initial-value)
(let ((value initial-value))
(define (mult-by x) (set! value (* value x))
value)
(define (add-to y) (set! value (+ value y))
value)
(cons mult-by add-to)))
Let’s follow it during an execution:
> (define function-pair (make-hidden-value 100))
> ((car function-pair) 2)
200
> ((car function-pair) 2)
400
> ((cdr function-pair) 2)
402
> ((cdr function-pair) 2)
404

In action…
(define (make-hidden-value initial-value)
(let ((value initial-value))
(define (mult-by x) (set! value (* value x))
value)
(define (add-to y) (set! value (+ value y))
value)
(cons mult-by add-to)))
Let’s follow it during an execution:
> (define function-pair (make-hidden-value 100))
> ((car function-pair) 2)
200
> ((car function-pair) 2)
400
> ((cdr function-pair) 2)
402
> ((cdr function-pair) 2)
404

In action…
(define (make-hidden-value initial-value)
(let ((value initial-value))
(define (mult-by x) (set! value (* value x))
value)
(define (add-to y) (set! value (+ value y))
value)
(cons mult-by add-to)))
Let’s follow it during an execution:
value: 100
> (define function-pair (make-hidden-value 100))
> ((car function-pair) 2)
200
> ((car function-pair) 2)
400
> ((cdr function-pair) 2)
402
> ((cdr function-pair) 2)
404

In action…
(define (make-hidden-value initial-value)
(let ((value initial-value))
(define (mult-by x) (set! value (* value x))
value)
(define (add-to y) (set! value (+ value y))
value)
(cons mult-by add-to)))
Let’s follow it during an execution:
value: 100
> (define function-pair (make-hidden-value 100))
> ((car function-pair) 2)
200
> ((car function-pair) 2)
400
> ((cdr function-pair) 2)
402
> ((cdr function-pair) 2)
404
function-pair: (m . a)
(define (mult-by x)
(set! value (* value x))
value)
(define (add-to y)
(set! value (+ value y))
value)

In action…
(define (make-hidden-value initial-value)
(let ((value initial-value))
(define (mult-by x) (set! value (* value x))
value)
(define (add-to y) (set! value (+ value y))
value)
(cons mult-by add-to)))
Let’s follow it during an execution:
value: 100
> (define function-pair (make-hidden-value 100))
> ((car function-pair) 2)
200
> ((car function-pair) 2)
400
> ((cdr function-pair) 2)
402
> ((cdr function-pair) 2)
404
function-pair: (m . a)
(define (mult-by x)
(set! value (* value x))
value)
(define (add-to y)
(set! value (+ value y))
value)

In action…
(define (make-hidden-value initial-value)
(let ((value initial-value))
(define (mult-by x) (set! value (* value x))
value)
(define (add-to y) (set! value (+ value y))
value)
(cons mult-by add-to)))
Let’s follow it during an execution:
value:
> (define function-pair (make-hidden-value 100))
> ((car function-pair) 2)
200
> ((car function-pair) 2)
400
> ((cdr function-pair) 2)
402
> ((cdr function-pair) 2)
404
function-pair: (m . a)
(define (mult-by x)
(set! value (* value x))
value)
(define (add-to y)
(set! value (+ value y))
value)

In action…
(define (make-hidden-value initial-value)
(let ((value initial-value))
(define (mult-by x) (set! value (* value x))
value)
(define (add-to y) (set! value (+ value y))
value)
(cons mult-by add-to)))
Let’s follow it during an execution:
value: 200
> (define function-pair (make-hidden-value 100))
> ((car function-pair) 2)
200
> ((car function-pair) 2)
400
> ((cdr function-pair) 2)
402
> ((cdr function-pair) 2)
404
function-pair: (m . a)
(define (mult-by x)
(set! value (* value x))
value)
(define (add-to y)
(set! value (+ value y))
value)

In action…
(define (make-hidden-value initial-value)
(let ((value initial-value))
(define (mult-by x) (set! value (* value x))
value)
(define (add-to y) (set! value (+ value y))
value)
(cons mult-by add-to)))
Let’s follow it during an execution:
value:
> (define function-pair (make-hidden-value 100))
> ((car function-pair) 2)
200
> ((car function-pair) 2)
400
> ((cdr function-pair) 2)
402
> ((cdr function-pair) 2)
404
function-pair: (m . a)
(define (mult-by x)
(set! value (* value x))
value)
(define (add-to y)
(set! value (+ value y))
value)

In action…
(define (make-hidden-value initial-value)
(let ((value initial-value))
(define (mult-by x) (set! value (* value x))
value)
(define (add-to y) (set! value (+ value y))
value)
(cons mult-by add-to)))
Let’s follow it during an execution:
value: 400
> (define function-pair (make-hidden-value 100))
> ((car function-pair) 2)
200
> ((car function-pair) 2)
400
> ((cdr function-pair) 2)
402
> ((cdr function-pair) 2)
404
function-pair: (m . a)
(define (mult-by x)
(set! value (* value x))
value)
(define (add-to y)
(set! value (+ value y))
value)

In action…
(define (make-hidden-value initial-value)
(let ((value initial-value))
(define (mult-by x) (set! value (* value x))
value)
(define (add-to y) (set! value (+ value y))
value)
(cons mult-by add-to)))
Let’s follow it during an execution:
value:
> (define function-pair (make-hidden-value 100))
> ((car function-pair) 2)
200
> ((car function-pair) 2)
400
> ((cdr function-pair) 2)
402
> ((cdr function-pair) 2)
404
function-pair: (m . a)
(define (mult-by x)
(set! value (* value x))
value)
(define (add-to y)
(set! value (+ value y))
value)

In action…
(define (make-hidden-value initial-value)
(let ((value initial-value))
(define (mult-by x) (set! value (* value x))
value)
(define (add-to y) (set! value (+ value y))
value)
(cons mult-by add-to)))
Let’s follow it during an execution:
value: 402
> (define function-pair (make-hidden-value 100))
> ((car function-pair) 2)
200
> ((car function-pair) 2)
400
> ((cdr function-pair) 2)
402
> ((cdr function-pair) 2)
404
function-pair: (m . a)
(define (mult-by x)
(set! value (* value x))
value)
(define (add-to y)
(set! value (+ value y))
value)

In action…
(define (make-hidden-value initial-value)
(let ((value initial-value))
(define (mult-by x) (set! value (* value x))
value)
(define (add-to y) (set! value (+ value y))
value)
(cons mult-by add-to)))
Let’s follow it during an execution:
value:
> (define function-pair (make-hidden-value 100))
> ((car function-pair) 2)
200
> ((car function-pair) 2)
400
> ((cdr function-pair) 2)
402
> ((cdr function-pair) 2)
404
function-pair: (m . a)
(define (mult-by x)
(set! value (* value x))
value)
(define (add-to y)
(set! value (+ value y))
value)

In action…
(define (make-hidden-value initial-value)
(let ((value initial-value))
(define (mult-by x) (set! value (* value x))
value)
(define (add-to y) (set! value (+ value y))
value)
(cons mult-by add-to)))
Let’s follow it during an execution:
value: 404
> (define function-pair (make-hidden-value 100))
> ((car function-pair) 2)
200
> ((car function-pair) 2)
400
> ((cdr function-pair) 2)
402
> ((cdr function-pair) 2)
404
function-pair: (m . a)
(define (mult-by x)
(set! value (* value x))
value)
(define (add-to y)
(set! value (+ value y))
value)

In action…
(define (make-hidden-value initial-value)
(let ((value initial-value))
(define (mult-by x) (set! value (* value x))
value)
(define (add-to y) (set! value (+ value y))
value)
(cons mult-by add-to)))
Let’s follow it during an execution:
value: 404
This environment is persistent!
> (define function-pair (make-hidden-value 100))
> ((car function-pair) 2)
200
> ((car function-pair) 2)
400
> ((cdr function-pair) 2)
402
> ((cdr function-pair) 2)
404
function-pair: (m . a)
(define (mult-by x)
(set! value (* value x))
value)
(define (add-to y)
(set! value (+ value y))
value)

Objects
In our bank account example, the only way to change the balance is through the withdrawal function. Thus, while there is destructive assignment, it is carried out behind an abstraction barrier.
This is called object-oriented programming.
Data objects are permitted private “state” information that can change over time, but
All interaction with these objects are carried out by specifically- crafted functions; no other functions have access to the state.



A more sophisticated bank account example

The idea: As before, we will establish an environment in which balance lives. Functions will be defined in this environment with access to the balance, and passed out of the environment.
(define (new-account initial-balance)
(let ((balance initial-balance))
(lambda (method x)
(cond ((eq? method ‘deposit)
(set! balance (+ balance x))
balance)
((eq? method ‘withdrawal)
(cond ((> x balance)
“Insufficient funds”)
(else
(set! balance
(- balance x))
balance)))
(else ‘undefined-method)))))

Putting this to work
Once the new-account object creator is defined…
> (define my-acct (new-account 200))
> (my-acct ‘deposit 250)
450
> (my-acct ‘withdrawal 300)
150
> balance
balance: undefined;
cannot reference undefined identifier
>
The function my-acct is a dispatcher; it can provide different functionality depending on the first parameter.
Note that balance is undefined in this environment.


Refining the solution: a first order dispatcher

We can slightly improve the solution by allowing the dispatcher to return the appropriate function (rather than applying it itself). Methods can now have varying number of arguments.
(define (new-account initial-balance)
(let ((balance initial-balance))
(define (deposit f)
(set! balance (+ balance f))
balance)
(define (withdraw f)
(cond ((> f balance)
“Insufficient funds”)
(else
(set! balance
(- balance f))
balance)))
(define (bal-inq) balance)
(lambda (method)
(cond ((eq? method ‘deposit) deposit)
((eq? method ‘withdraw) withdraw)
((eq? method ‘balance-inquire) bal-inq)
(else ‘undefined-operation)))))
The methods
The dispatcher

Refining the solution: a first order dispatcher

We can slightly improve the solution by allowing the dispatcher to return the appropriate function (rather than applying it itself). Methods can now have varying number of arguments.
(define (new-account initial-balance)
(let ((balance initial-balance))
(define (deposit f)
(set! balance (+ balance f))
balance)
(define (withdraw f)
(cond ((> f balance)
“Insufficient funds”)
(else
(set! balance
(- balance f))
balance)))
(define (bal-inq) balance)
(lambda (method)
(cond ((eq? method ‘deposit) deposit)
((eq? method ‘withdraw) withdraw)
((eq? method ‘balance-inquire) bal-inq)
(else ‘undefined-operation)))))
The methods
The dispatcher

Refining the solution: a first order dispatcher

We can slightly improve the solution by allowing the dispatcher to return the appropriate function (rather than applying it itself). Methods can now have varying number of arguments.
(define (new-account initial-balance)
(let ((balance initial-balance))
(define (deposit f)
(set! balance (+ balance f))
balance)
(define (withdraw f)
(cond ((> f balance)
“Insufficient funds”)
(else
(set! balance
(- balance f))
balance)))
(define (bal-inq) balance)
(lambda (method)
(cond ((eq? method ‘deposit) deposit)
The methods
((eq? method ‘withdraw) withdraw)
((eq? method ‘balance-inquire) bal-inq)
(else ‘undefined-operation)))))
The dispatcher

Using the first order dispatcher
Note that the dispatcher now returns the requested function.
> (define my-account (new-account 500))
> (my-account ‘deposit)
# > ((my-account ‘deposit) 200)
700
> ((my-account ‘withdraw) 250)
450
> ((my-account ‘balance-inquire))
450
Why the double parentheses?

Objects, in general




In general, these functions with access to the private state variables are called methods for this object.
Implemented in SCHEME by defining an object creator.
The creator builds an environment containing the private state variables of the object.
It returns a function (which references these local variables in its body). The function can be a dispatcher, as in the last example.