As we have seen, the set! operation assignment enables us to model objects that have local state. However, this advantage comes at a price. Our programming language can no longer be interpreted in terms of the substitution model of procedure function application that we introduced in section 1.1.5. Moreover, no simple model with nice mathematical properties can be an adequate framework for dealing with objects and assignment in programming languages.

So long as we do not use assignments, two evaluations of the same procedure function with the same arguments will produce the same result, so that procedures functions can be viewed as computing mathematical functions. Programming without any use of assignments, as we did throughout the first two chapters of this book, is accordingly known as functional programming.

To understand how assignment complicates matters, consider a simplified version of the make_withdraw procedure function of section 3.1.1 that does not bother to check for an insufficient amount:

Original	JavaScript
(define (make-simplified-withdraw balance) (lambda (amount) (set! balance (- balance amount)) balance))	function make_simplified_withdraw(balance) { return amount => { balance = balance - amount; return balance; }; }

Original	JavaScript
(define W (make-simplified-withdraw 25))	const W = make_simplified_withdraw(25);

Original	JavaScript
(W 20) 5	W(20); 5

Original	JavaScript
(W 10) -5	W(10); -5

Compare this procedure function with the following make_decrementer procedure, function, which does not use set!: assignment:

Original	JavaScript
(define (make-decrementer balance) (lambda (amount) (- balance amount)))	function make_decrementer(balance) { return amount => balance - amount; }

make-decrementer The function make_decrementer returns a procedure function that subtracts its input from a designated amount balance, but there is no accumulated effect over successive calls, as with make_simplified_withdraw:

Original	JavaScript
(define D (make-decrementer 25))	const D = make_decrementer(25);

Original	JavaScript
(D 20) 5	D(20); 5

Original	JavaScript
(D 10) 15	D(10); 15

We can use the substitution model to explain how make_decrementer works. For instance, let us analyze the evaluation of the expression

Original	JavaScript
((make-decrementer 25) 20)	make_decrementer(25)(20)

We first simplify the operator of the combination function expression of the application by substituting $25$ for balance in the body of make-decrementer. make_decrementer. This reduces the expression to

Original	JavaScript
((lambda (amount) (- 25 amount)) 20)	(amount => 25 - amount)(20)

Now we apply the operator function by substituting 20 for amount in the body of the lambda lambda expression:

Original	JavaScript
(- 25 20)	25 - 20

The final answer is 5.

Observe, however, what happens if we attempt a similar substitution analysis with make_simplified_withdraw:

Original	JavaScript
((make-simplified-withdraw 25) 20)	make_simplified_withdraw(25)(20)

We first simplify the operator function expression by substituting 25 for balance in the body of the body of make_simplified_withdraw. This reduces the expression expression to[1]

Original	JavaScript
((lambda (amount) (set! balance (- 25 amount)) 25) 20)	(amount => { balance = 25 - amount; return 25; })(20)

Now we apply the operator function by substituting 20 for amount in the body of the lambda expression: lambda expression:

Original	JavaScript
(set! balance (- 25 20)) 25	balance = 25 - 20; return 25;

If we adhered to the substitution model, we would have to say that the meaning of the procedure function application is to first set balance to 5 and then return 25 as the value of the expression. This gets the wrong answer. In order to get the correct answer, we would have to somehow distinguish the first occurrence of balance (before the effect of the set!) assignment) from the second occurrence of balance (after the effect of the set!), assignment), and the substitution model cannot do this.

The trouble here is that substitution is based ultimately on the notion that the symbols in our language are essentially names for values. the name in our language are essentially symbols for values.

Original		JavaScript
But as soon as we introduce set! and the idea that the value of a variable can change, a variable can no longer be simply a name. Now a variable somehow refers to a place where a value can be stored, and the value stored at this place can change.		This worked well for constants. But a variable, whose value can change with assignment, cannot simply be a name for a value. A variable somehow refers to a place where a value can be stored, and the value stored at this place can change.

In section 3.2 we will see how environments play this role of place in our computational model.

Sameness and change

The issue surfacing here is more profound than the mere breakdown of a particular model of computation. As soon as we introduce change into our computational models, many notions that were previously straightforward become problematical. Consider the concept of two things being the same.

Suppose we call make-decrementer make_decrementer twice with the same argument to create two procedures: functions:

Original	JavaScript
(define D1 (make-decrementer 25)) (define D2 (make-decrementer 25))	const D1 = make_decrementer(25); const D2 = make_decrementer(25);

Are D1 and D2 the same? An acceptable answer is yes, because D1 and D2 have the same computational behavior—each is a procedure function that subtracts its input from 25. In fact, D1 could be substituted for D2 in any computation without changing the result.

Contrast this with making two calls to make-simplified-withdraw: make_simplified_withdraw:

Original	JavaScript
(define W1 (make-simplified-withdraw 25)) (define W2 (make-simplified-withdraw 25))	const W1 = make_simplified_withdraw(25); const W2 = make_simplified_withdraw(25);

Are W1 and W2 the same? Surely not, because calls to W1 and W2 have distinct effects, as shown by the following sequence of interactions:

Original	JavaScript
(W1 20) 5	W1(20); 5

Original	JavaScript
(W1 20) -15	W1(20); -15

Original	JavaScript
(W2 20) 5	W2(20); 5

Even though W1 and W2 are equal in the sense that they are both created by evaluating the same expression, (make-simplified-withdraw 25), make_simplified_withdraw(25), it is not true that W1 could be substituted for W2 in any expression without changing the result of evaluating the expression.

A language that supports the concept that equals can be substituted for equals in an expression without changing the value of the expression is said to be referentially transparent. Referential transparency is violated when we include set! assignment in our computer language. This makes it tricky to determine when we can simplify expressions by substituting equivalent expressions. Consequently, reasoning about programs that use assignment becomes drastically more difficult.

Once we forgo referential transparency, the notion of what it means for computational objects to be the same becomes difficult to capture in a formal way. Indeed, the meaning of same in the real world that our programs model is hardly clear in itself. In general, we can determine that two apparently identical objects are indeed the same one only by modifying one object and then observing whether the other object has changed in the same way. But how can we tell if an object has changed other than by observing the same object twice and seeing whether some property of the object differs from one observation to the next? Thus, we cannot determine change without some a priori notion of sameness, and we cannot determine sameness without observing the effects of change.

As an example of how this issue arises in programming, consider the situation where Peter and Paul have a bank account with $100 in it. There is a substantial difference between modeling this as

Original	JavaScript
(define peter-acc (make-account 100)) (define paul-acc (make-account 100))	const peter_acc = make_account(100); const paul_acc = make_account(100);

and modeling it as

Original	JavaScript
(define peter-acc (make-account 100)) (define paul-acc peter-acc)	const peter_acc = make_account(100); const paul_acc = peter_acc;

In the first situation, the two bank accounts are distinct. Transactions made by Peter will not affect Paul's account, and vice versa. In the second situation, however, we have defined paul-acc paul_acc to be the same thing as peter-acc. peter_acc. In effect, Peter and Paul now have a joint bank account, and if Peter makes a withdrawal from peter-acc peter_acc Paul will observe less money in paul-acc. paul_acc. These two similar but distinct situations can cause confusion in building computational models. With the shared account, in particular, it can be especially confusing that there is one object (the bank account) that has two different names (peter-acc and paul-acc); (peter_acc and paul_acc); if we are searching for all the places in our program where paul-acc paul_acc can be changed, we must remember to look also at things that change peter-accpeter_acc.[2]

With reference to the above remarks on sameness and change, observe that if Peter and Paul could only examine their bank balances, and could not perform operations that changed the balance, then the issue of whether the two accounts are distinct would be moot. In general, so long as we never modify data objects, we can regard a compound data object to be precisely the totality of its pieces. For example, a rational number is determined by giving its numerator and its denominator. But this view is no longer valid in the presence of change, where a compound data object has an identity that is something different from the pieces of which it is composed. A bank account is still the same bank account even if we change the balance by making a withdrawal; conversely, we could have two different bank accounts with the same state information. This complication is a consequence, not of our programming language, but of our perception of a bank account as an object. We do not, for example, ordinarily regard a rational number as a changeable object with identity, such that we could change the numerator and still have the same rational number.

Pitfalls of imperative programming

In contrast to functional programming, programming that makes extensive use of assignment is known as imperative programming. In addition to raising complications about computational models, programs written in imperative style are susceptible to bugs that cannot occur in functional programs. For example, recall the iterative factorial program from section 1.2.1: section 1.2.1 (here using a conditional statement instead of a conditional expression):

Original	JavaScript
(define (factorial n) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1))	function factorial(n) { function iter(product, counter) { if (counter > n) { return product; } else { return iter(counter * product, counter + 1); } } return iter(1, 1); }

Instead of passing arguments in the internal iterative loop, we could adopt a more imperative style by using explicit assignment to update the values of the variables product and counter:

Original	JavaScript
(define (factorial n) (let ((product 1) (counter 1)) (define (iter) (if (> counter n) product (begin (set! product (* counter product)) (set! counter (+ counter 1)) (iter)))) (iter)))	function factorial(n) { let product = 1; let counter = 1; function iter() { if (counter > n) { return product; } else { product = counter * product; counter = counter + 1; return iter(); } } return iter(); }

This does not change the results produced by the program, but it does introduce a subtle trap. How do we decide the order of the assignments? As it happens, the program is correct as written. But writing the assignments in the opposite order

Original	JavaScript
(set! counter (+ counter 1)) (set! product (* counter product))	counter = counter + 1; product = counter * product;

would have produced a different, incorrect result. In general, programming with assignment forces us to carefully consider the relative orders of the assignments to make sure that each statement is using the correct version of the variables that have been changed. This issue simply does not arise in functional programs.[3]

The complexity of imperative programs becomes even worse if we consider applications in which several processes execute concurrently. We will return to this in section 3.4. First, however, we will address the issue of providing a computational model for expressions that involve assignment, and explore the uses of objects with local state in designing simulations.

Exercise 3.7 Consider the bank account objects created by make-account, make_account, with the password modification described in exercise 3.3. Suppose that our banking system requires the ability to make joint accounts. Define a procedure function make-joint make_joint that accomplishes this. Make-joint The function make_joint should take three arguments. The first is a password-protected account. The second argument must match the password with which the account was defined in order for the make-joint make_joint operation to proceed. The third argument is a new password. Make-joint The function make_joint is to create an additional access to the original account using the new password. For example, if peter-acc peter_acc is a bank account with password open-sesame, "open sesame", then

Original	JavaScript
(define paul-acc (make-joint peter-acc 'open-sesame 'rosebud))	const paul_acc = make_joint(peter_acc, "open sesame", "rosebud");

will allow one to make transactions on peter-acc peter_acc using the name paul-acc paul_acc and the password rosebud. "rosebud". You may wish to modify your solution to exercise 3.3 to accommodate this new feature.

Solution

function make_joint(linked_acc, linked_pw, joint_pw) { return (message, input_pw) => { // Check authentication for joint account if (input_pw !== joint_pw) { return x => "Wrong joint account password"; } else { const access_linked = linked_acc(message, linked_pw); // Check authentication for linked account if (access_linked(0) === "Incorrect Password") { // access_linked(0) does deposit / withdrawal of 0 // to test for "Incorrect Password" message. return x => "Wrong linked account password"; } else { // All authentication passed, return accessed // account to user return access_linked; } } }; }

Exercise 3.8 When we defined the evaluation model in section 1.1.3, we said that the first step in evaluating an expression is to evaluate its subexpressions. But we never specified the order in which the subexpressions should be evaluated (e.g., left to right or right to left). When we introduce assignment, the order in which the arguments to a procedure are evaluated can make a difference to the result. When we introduce assignment, the order in which the operands of an operator combination are evaluated can make a difference to the result. Define a simple procedure function f such that evaluating (+ (f 0) (f 1)) f(0) + f(1) will return 0 if the arguments to + operands of + are evaluated from left to right but will return 1 if the arguments operands are evaluated from right to left.

Solution

function make_f(init) { return x => { init = x - init; return init; }; } const f = make_f(1/2);