3.1.1 Local State Variables - SICP Comparison Edition

Permalink copied!

3.1.1

To illustrate what we mean by having a computational object with time-varying state, let us model the situation of withdrawing money from a bank account. We will do this using a function withdraw, which takes as argument an amount to be withdrawn. If there is enough money in the account to accommodate the withdrawal, then withdraw should return the balance remaining after the withdrawal. Otherwise, withdraw should return the message Insufficient funds. For example, if we begin with $100 in the account, we should obtain the following sequence of responses using withdraw:

withdraw(25);

withdraw(25);

withdraw(60);

"Insufficient funds"

withdraw(15);

Observe that the expression withdraw(25), evaluated twice, yields different values. This is a new kind of behavior for a function. Until now, all our JavaScript functions could be viewed as specifications for computing mathematical functions. A call to a function computed the value of the function applied to the given arguments, and two calls to the same function with the same arguments always produced the same result.

[1]

So far, all our names have been immutable. When a function was applied, the values that its parameters referred to never changed, and once a declaration was evaluated, the declared name never changed its value. To implement functions like withdraw, we introduce variable declarations, which use the keyword let, in addition to constant declarations, which use the keyword const. We can declare a variable balance to indicate the balance of money in the account and define withdraw as a function that accesses balance.

The withdraw function checks to see if balance is at least as large as the requested amount. If so, withdraw decrements balance by amount and returns the new value of balance. Otherwise, withdraw returns the Insufficient funds message. Here are the declarations of balance and withdraw:

let balance = 100;

function withdraw(amount) {
    if (balance >= amount) {
        balance = balance - amount;
        return balance;
    } else {
        return "Insufficient funds";
    }
}

Decrementing balance is accomplished by the expression statement

balance = balance - amount;

The syntax of assignment expressions is

$name$ = $new$-$value$

Here $name$ has been declared with let or as a function parameter and $new$-$value$ is any expression. The assignment changes $name$ so that its value is the result obtained by evaluating $new$-$value$. In the case at hand, we are changing balance so that its new value will be the result of subtracting amount from the previous value of balance.

[2]

The function withdraw also uses a sequence of statements to cause two statements to be evaluated in the case where the if test is true: first decrementing balance and then returning the value of balance. In general, executing a sequence

$stmt$$_{1}$ $stmt$$_{2} \ldots$$stmt$$_{n}$

causes the statements $stmt$$_{1}$ through $stmt$$_{n}$ to be evaluated in sequence.

[3]

Although withdraw works as desired, the variable balance presents a problem. As specified above, balance is a name defined in the program environment and is freely accessible to be examined or modified by any function. It would be much better if we could somehow make balance internal to withdraw, so that withdraw would be the only function that could access balance directly and any other function could access balance only indirectly (through calls to withdraw). This would more accurately model the notion that balance is a local state variable used by withdraw to keep track of the state of the account.

We can make balance internal to withdraw by rewriting the definition as follows:

function make_withdraw_balance_100() {
    let balance = 100;
    return amount => {
               if (balance >= amount) {
                   balance = balance - amount;
                   return balance;
               } else {
                   return "Insufficient funds";
               }
           };
}
const new_withdraw = make_withdraw_balance_100();

What we have done here is use let to establish an environment with a local variable balance, bound to the initial value 100. Within this local environment, we use a lambda expression

[4]

to create a function that takes amount as an argument and behaves like our previous withdraw function. This function—returned as the result of evaluating the body of the make_withdraw_balance_100 function—behaves in precisely the same way as withdraw, but its variable balance is not accessible by any other function.

[5]

Combining assignments with variable declarations is the general programming technique we will use for constructing computational objects with local state. Unfortunately, using this technique raises a serious problem: When we first introduced functions, we also introduced the substitution model of evaluation (section 1.1.5) to provide an interpretation of what function application means. We said that applying a function whose body is a return statement should be interpreted as evaluating the return expression of the function with the parameters replaced by their values. For functions with more complex bodies, we need to evaluate the whole body with the parameters replaced by their values. The trouble is that, as soon as we introduce assignment into our language, substitution is no longer an adequate model of function application. (We will see why this is so in section 3.1.3.) As a consequence, we technically have at this point no way to understand why the new_withdraw function behaves as claimed above. In order to really understand a function such as new_withdraw, we will need to develop a new model of function application. In section 3.2 we will introduce such a model, together with an explanation of assignments and variable declarations. First, however, we examine some variations on the theme established by new_withdraw.

Parameters of functions as well as names declared with let are variables. The following function, make_withdraw, creates withdrawal processors. The parameter balance in make_withdraw specifies the initial amount of money in the account.

[6]

function make_withdraw(balance) {
    return amount => {
               if (balance >= amount) {
                   balance = balance - amount;
                   return balance;
               } else {
                   return "Insufficient funds";
               }
           };
}

The function make_withdraw can be used as follows to create two objects W1 and W2:

const W1 = make_withdraw(100);
const W2 = make_withdraw(100);

W1(50);

W2(70);

W2(40);

"Insufficient funds"

W1(40);

Observe that W1 and W2 are completely independent objects, each with its own local state variable balance. Withdrawals from one do not affect the other.

We can also create objects that handle deposits as well as withdrawals, and thus we can represent simple bank accounts. Here is a function that returns a bank-account object with a specified initial balance:

function make_account(balance) {
    function withdraw(amount) {
        if (balance >= amount) {
            balance = balance - amount;
            return balance;
        } else {
            return "Insufficient funds";
        }
    }
    function deposit(amount) {
        balance = balance + amount;
        return balance;
    }
    function dispatch(m) {
        return m === "withdraw"
               ? withdraw
               : m === "deposit"
               ? deposit
               : error(m, "unknown request -- make_account");
    }
    return dispatch;
}

Each call to make_account sets up an environment with a local state variable balance. Within this environment, make_account defines functions deposit and withdraw that access balance and an additional function dispatch that takes a message as input and returns one of the two local functions. The dispatch function itself is returned as the value that represents the bank-account object. This is precisely the message-passing style of programming that we saw in section 2.4.3, although here we are using it in conjunction with the ability to modify local variables.

The function make_account can be used as follows:

const acc = make_account(100);

acc("withdraw")(50);

acc("withdraw")(60);

"Insufficient funds"

acc("deposit")(40);

acc("withdraw")(60);

Each call to acc returns the locally defined deposit or withdraw function, which is then applied to the specified amount. As was the case with make_withdraw, another call to make_account

const acc2 = make_account(100);

will produce a completely separate account object, which maintains its own local balance.

Exercise 3.1

An accumulator is a function that is called repeatedly with a single numeric argument and accumulates its arguments into a sum. Each time it is called, it returns the currently accumulated sum. Write a function make_accumulator that generates accumulators, each maintaining an independent sum. The input to make_accumulator should specify the initial value of the sum; for example

const a = make_accumulator(5);

a(10);

a(10);

function make_accumulator(current) {
    function add(arg) {
        current = current + arg;
        return current;
    }
    return add;
}

Exercise 3.2

In software-testing applications, it is useful to be able to count the number of times a given function is called during the course of a computation. Write a function make_monitored that takes as input a function, f, that itself takes one input. The result returned by make_monitored is a third function, say mf, that keeps track of the number of times it has been called by maintaining an internal counter. If the input to mf is the string "how many calls", then mf returns the value of the counter. If the input is the string "reset count", then mf resets the counter to zero. For any other input, mf returns the result of calling f on that input and increments the counter. For instance, we could make a monitored version of the sqrt function:

const s = make_monitored(math_sqrt);

s(100);

s("how many calls");

const s = make_monitored(math_sqrt);
s(100);
display(s("how many calls"));
s(5);
display(s("how many calls"));

function make_monitored(f) {
    let counter = 0; //initialized to 0
    function mf(cmd) {
        if (cmd === "how many calls") {
            return counter;
        } else if (cmd === "reset count") {
            counter = 0;
            return counter;
        } else {
            counter = counter + 1;
            return f(cmd);
        }
    }
    return mf;
}

Exercise 3.3

Modify the make_account function so that it creates password-protected accounts. That is, make_account should take a string as an additional argument, as in

const acc = make_account(100, "secret password");

The resulting account object should process a request only if it is accompanied by the password with which the account was created, and should otherwise return a complaint:

acc("secret password", "withdraw")(40);

acc("some other password", "deposit")(40);

"Incorrect password"

function make_account(balance, p) {
    function withdraw(amount) {
        if (balance >= amount) {
            balance = balance - amount;
            return balance;
        } else {
            return "Insufficient funds";
        }
    }
    function deposit(amount) {
        balance = balance + amount;
        return balance;
    }
    function dispatch(m, q) {
        if (p === q) {
            return m === "withdraw"
                   ? withdraw
                   : m === "deposit"
                   ? deposit
                   : "Unknown request: make_account";
        } else {
            return q => "Incorrect Password";
        }
    }
    return dispatch;
}

const a = make_account(100, "eva");
a("withdraw", "eva")(50); //withdraws 50
a("withdraw", "ben")(40); //incorrect password

Exercise 3.4

Modify the make_account function of exercise 3.3 by adding another local state variable so that, if an account is accessed more than seven consecutive times with an incorrect password, it invokes the function call_the_cops.

function call_the_cops(reason) {
    return "calling the cops because " + reason;
}
function make_account(balance, p) {

    let invalid_attempts = 0; //initializes to 0

    function withdraw(amount) {
        if (balance >= amount) {
            balance = balance - amount;
            return balance;
        } else {
            return "Insufficient funds";
        }
    }

    function deposit(amount) {
        balance = balance + amount;
        return balance;
    }

    function calling_the_cops(_) {
        return call_the_cops("you have exceeded " +
                             "the max no of failed attempts");
    }

    function dispatch(m, q) {
        if (invalid_attempts < 7) {
            if (p === q) {
                return m === "withdraw"
                       ? withdraw
                       : m === "deposit"
                       ? deposit
                       : "Unknown request: make_account";
            } else {
                invalid_attempts = invalid_attempts + 1;
                return x => "Incorrect Password";
            }
        } else {
            return calling_the_cops;
        }
    }

    return dispatch;

}

[1]

Actually, this is not quite true. One exception was the random-number generator in section 1.2.6. Another exception involved the operation/type tables we introduced in section 2.4.3, where the values of two calls to get with the same arguments depended on intervening calls to put. On the other hand, until we introduce assignment, we have no way to create such functions ourselves.

[2]

The value of an assignment is the value being assigned to the name. Assignment expression statements look similar to and should not be confused with constant and variable declarations of the form

const $name$ = $value$;

and

let $name$ = $value$;

in which a newly declared $name$ is associated with a $value$. Assignment expressions look similar to and should not be confused with expressions of the form

$expression_1$ === $expression_2$

which evaluate to true if $expression$$_1$ evaluates to the same value as $expression$$_2$ and to false otherwise.

[3]

We have already used sequences implicitly in our programs, because in JavaScript the body block of a function can contain a sequence of function declarations followed by a return statement, not just a single return statement, as discussed in section 1.1.8.

[4]

Blocks as bodies of lambda expressions were introduced in section 2.2.4.

[5]

In programming-language jargon, the variable balance is said to be encapsulated within the new_withdraw function. Encapsulation reflects the general system-design principle known as the hiding principle: One can make a system more modular and robust by protecting parts of the system from each other; that is, by providing information access only to those parts of the system that have a need to know.

[6]

In contrast with make_withdraw_balance_100 above, we do not have to use let to make balance a local variable, since parameters are already local. This will be clearer after the discussion of the environment model of evaluation in section 3.2. (See also exercise 3.10.)

< Previous

Next >

3.1.1

Local State Variables