Functional Programming – How to Manage Without Assignment Statements

functional programmingprogramming-languagesscheme

When reading the famous SICP, I found the authors seem rather reluctant to introduce the assignment statement to Scheme in Chapter 3. I read the text and kind of understand why they feel so.

As Scheme is the first functional programming language I ever know something about, I am kind of surprised that there are some functional programming languages (not Scheme of course) can do without assignments.

Let use the example the book offers,the bank account example. If there is no assignment statement, how can this be done?How to change the balance variable? I ask so because I know there are some so-called pure functional languages out there and according to the Turing complete theory, this must can be done too.

I learned C, Java, Python and use assignments a lot in every program I wrote. So it's really an eye-opening experience. I really hope someone can briefly explain how assignments are avoided in those functional programming languages and what profound impact (if any) it has on these languages.

The example mentioned above is here:

(define (make-withdraw balance)
    (lambda (amount)
        (if (>= balance amount)
            (begin (set! balance (- balance amount))
                balance)
            "Insufficient funds")))

This changed the balance by set!. To me it looks a lot like a class method to change the class member balance.

As I said, I am not familiar with functional programming languages, so if I said something wrong about them, feel free to point out.

Best Answer

If there is no assignment statement,how can this be done?How to change the balance variable?

You can't change variables without some sort of assignment operator.

I ask so because I know there are some so-called pure functional languages out there and according to the Turing complete theory,this must can be done too.

Not quite. If a language is Turing complete that means that it can calculate anything that the any other Turing complete language can calculate. It doesn't mean that it has to have every feature other languages have.

It's not a contradiction that a Turing complete programming language has no way of changing the value of a variable, as long as for every program that has mutable variables, you can write an equivalent program that does not have mutable variables (where "equivalent" means that it calculates the same thing). And in fact every program can be written that way.

Regarding your example: In a purely functional language you simply wouldn't be able to write a function that returns a different account balance each time it's called. But you'd still be able to rewrite every program, that uses such a function, in a different way.

Since you asked for an example, let's consider an imperative program that uses your make-withdraw function (in pseudo-code). This program allows the user to withdraw from an account, deposit to it or query the amount of money in the account:

account = make-withdraw(0)
ask for input until the user enters "quit"
    if the user entered "withdraw $x"
        account(x)
    if the user entered "deposit $x"
        account(-x)
    if the user entered "query"
        print("The balance of the account is " + account(0))

Here's a way to write the same program without using mutable-variables (I won't bother with referentially transparent IO because the question wasn't about that):

function IO_loop(balance):
    ask for input
    if the user entered "withdraw $x"
        IO_loop(balance - x)
    if the user entered "deposit $x"
        IO_loop(balance + x)
    if the user entered "query"
        print("The balance of the account is " + balance)
        IO_loop(balance)
    if the user entered "quit"
        do nothing

 IO_loop(0)

The same function could also be written without using recursion by using a fold over the user input (which would be more idiomatic than explicit recursion), but I don't know whether you're familiar with folds yet, so I wrote it in a way that doesn't use anything you don't know yet.

Related Topic