how a pure functional programming language manage without assignment statements?

Question

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.

Answer 1

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.

Answer 2

You're right that it looks a lot like a method on an object. That's because that's essentially what it is. The lambda function is a closure that pulls the external variable balance into its scope. Having multiple closures that close over the same external variable(s) and having multiple methods on the same object are two different abstractions for doing the exact same thing, and either one can be implemented in terms of the other if you understand both paradigms.

The way pure functional languages handle state is by cheating. For example, in Haskell if you want to read input from an external source, (which is nondeterministic, of course, and will not necessarily give the same result twice if you repeat it,) it uses a monad trick to say "we've got this other pretend variable that represents the state of the entire rest of the world, and we can't examine it directly, but reading input is a pure function that takes the state of the outside world and returns the deterministic input that that exact state will always render, plus the new state of the outside world." (That's a simplified explanation, of course. Reading up on the way it actually works will seriously break your brain.)

Or in the case of your bank account problem, instead of assigning a new value to the variable, it can return the new value as the function result, and then the caller has to deal with it in a functional style, generally by recreating any data that references that value with a new version containing the updated value. (This is not as bulky an operation as it might sound if your data is set up with the right sort of tree structure.)

Answer 3

"Multiple-assignment operators" is one example of a language feature which, generally speaking, has side effects, and is incompatible with some useful properties of functional languages (such as lazy-evaluation).

That, however, doesn't mean that assignment in general is incompatible with a pure functional programming style (see this discussion for example), nor does it mean that you can't construct syntax which allows actions that look like assignments in general, but are implemented without side effects. Creating that kind of syntax, and writing efficient programs in it, is time consuming and hard, though.

In your specific example, you're right - the set! operator is an assignment. It's not a side-effect free operator, and it's a place where Scheme breaks with a purely functional approach to programming.

Ultimately, any purely functional language is going to have to break with the purely functional approach sometime - the vast majority of useful programs do have side effects. The decision of where to do it is usually a matter of convenience, and language designers will try to give the programmer the highest flexibility in deciding where to break with a purely functional approach, as appropriate for their program and problem domain.

Answer 4

In a purely functional language, one would program a bank account object as a stream transformer function. The object is regarded as a function from an infinite stream of requests from the account owners (or whoever) to a potentially infinite stream of responses. The function starts off with an initial balance, and processes each request in the input stream to calculate a new balance, which is then fed back to the recursive call to process the remainder of the stream. (I recall that SICP discusses stream-transformer paradigm in another part of the book.)

A more elaborate version of this paradigm is called "functional reactive programming" discussed here on StackOverflow.

The naive way of doing stream transformers has some problems. It is possible (in fact, pretty easy) to write buggy programs that keep all the old requests around, wasting space. More seriously, it is possible to make the response to the current request depend on future requests. Solutions to these problems are currently being worked on. Neel Krishnaswami is the force behind them.

Disclaimer: I do not belong to the church of pure functional programming. In fact, I do not belong to any church :-)

Answer 5

It's not possible making a program 100% functional if it is supposed to do anything useful. (If side effects are not needed then the whole think could have been reduced to a constant compile time) Like the withdraw-example you can make most of the procedures functional but eventually you'll need procedures that has side effects (input from user, output to console). That said you can make most of your code functional and that part will be easy to test, even automatically. Then you make some imperative code to do the input/output/database/... which would need debugging, but keeping most of the code clean it won't be too much work. I'll use your withdraw-example:

(define +no-founds+ "Insufficient funds")

;; functional withdraw
(define (make-withdraw balance amount)
    (if (>= balance amount)
        (- balance amount)
        +no-founds+))

;; functional atm loop
(define (atm balance thunk)
  (let* ((amount (thunk balance)) 
         (new-balance (make-withdraw balance amount)))
    (if (eqv? new-balance +no-founds+)
        (cons +no-founds+ '())
        (cons (list 'withdraw amount 'balance new-balance) (atm new-balance thunk)))))

;; functional balance-line -> string 
(define (balance->string x)
  (if (eqv? x +no-founds+)
      (string-append +no-founds+ "\n")
      (if (null? x)
          "\n"
          (let ((first-token (car x)))
            (string-append
             (cond ((symbol? first-token) (symbol->string first-token))
                   (else (number->string first-token)))
             " "
             (balance->string (cdr x)))))))

;; functional thunk to test  
(define (input-10 x) 10) ;; define a purly functional input-method

;; since all procedures involved are functional 
;; we expect the same result every time.
;; we use this to test atm and make-withdraw
(apply string-append (map balance->string (atm 100 input-10)))

;; no program can be purly functional in any language.
;; From here on there are imperative dirty procedures!

;; A procedure to get input from user is needed. 
;; Side effects makes it imperative
(define (user-input balance)
  (display "You have $")
  (display balance)
  (display " founds. How much to withdraw? ")
  (read))

;; We need a procedure to print stuff to the console 
;; as well. Side effects makes it imperative
(define (pretty-print-result x)
  (for-each (lambda (x) (display (balance->string x))) x))

;; use imperative procedure with atm.
(pretty-print-result (atm 100 user-input))

It is possible to do the same in almost any language and produce the same results (less bugs), though you might have to set temporary variables within a procedure and even mutate stuff, but that doesn't matter to much as long as the procedure actually acts functional (the parameters alone determines the result). I belive you become a better programmer at any language after you have programmed a little LISP :)

Answer 6

Assignment is bad operation because it divides the state-space to two parts, before-assignment, and after-assignment. This causes difficulties tracking how the variables are being changed during program execution. The following things in functional languages are replacing assignments:

1. Function parameters linked directly to return values
2. choosing different objects to be returned instead of modifying existing objects.
3. creating new lazy-evaluated values
4. listing all possible objects, not just the ones that need to be in memory
5. no side effects