Quote: Original post by Anonymous Poster
SamLowry:
My experience is that students with an imperative background have the most trouble with the concept of statelessness, because it's seldom mentioned explictly (or at least explicitly enough, it seems). They stumble on the initial examples in SICP and elsewhere because they try to write them imperatively.
As to how clear the explanation is... probably not very, I admit. Help me fix it; the text I posted is meant as discussion fodder.
I actually intend this as more of a cautionary note for imperative programmers than a real introduction: that's what SICP is for. So I think it should be as short as possible so people actually bother to read it (shorter than it is now).
Maybe another cautionary explanation should be given about binding vs. assignment.
Ah, and I love the Why FP paper, it's one of the things that keeps me warm during the functional winter. It should go in the links section. You're right that it's skewed more toward more pure languages than scheme; it'll still be very relevant when we get to SICP's lazy evaluator. And it's very motivational.
I've made an attempt to write my own introduction based on your and Rebooted's explanation, covering the topics you considered important. I made it a bit more theoretical than yours, but less than Rebooted's. The problem is that it ended up a lot longer. I prefered not to use Python as I'm not too familiar with it, and the introduction of new bindings looks so ambiguous to me. I also tried to give small hints towards the future, so as to provide not only a "what" but also a "why". Anyway, I have lost the ability to objectively judge it, so I'm relying on you to criticize it all you want. I've been looking up information where I thought it was necessary, so I hope there are no blatant mistakes in it.
The theoretical
Imperative programming sees the computer as a processor attached to memory. The memory consists of memory cells which can be read from and written to. An application is a series of sequentially executed instructions which manipulate the values in these cells. This model is very close to how our computers really work.
Functional programming is based on a more abstract model, the lambda calculus. This language provides you only with 3 basic concepts: symbols, functions, and function applications (maybe it's more interesting to point out what it does not support: no numbers, no data structures, no loops, no recursion, ... yet it is still turing complete, i.e. given code in any language, you can translate it into lambda-calculus code which will behave exactly the same, at least if you ignore performance). An application can be seen as one giant mathematical expression which has to be evaluated.
The most important difference between these two models is the dimension of time: using imperative style makes the effect of instructions dependent on time (i.e. dependent on when the instruction is executed, because the machine is in different states at different times), while functional style does not know such a dimension: it can be proven that whatever order you choose to evaluate the giant mathematical expression in, the result will stay the same. This makes using powerful concepts such as non-strict evaluation (evaluating expressions only when absolutely necessary), memoization (remembering previous computations), futures/dataflow variables (makes multithreading a lot simpler), ... a lot more easier to use.
The less theoretical
In an imperative setting, a function can
a) return a value and
b) manipulate the machine's state
Both these actions can depend on the arguments the function is called with and the machine's current state. If a function is fed the same arguments twice, it's possible the results will differ, meaning state can be seen as an implicit, hidden dependency. Imperative programming languages try their best to provide programmers with structure so that the reach of a function's dependencies can be limited, e.g. OO tries to limit influence by grouping things in objects and explicitly stating which object can reach what other objects.
In the functional model, there is no state, which means a function's only effect can be to return a value, and this result can only depend on the arguments provided, hence all dependencies are made explicit. Keep in mind that the arguments themselves are part of the state, so these cannot be modified either. Some consequences of this are that functions which take no arguments are constant (will always return the same value), and that having a function with void return type is rather useless.
An example with data structures
Let's consider the list data structure and the insert operation. In an imperative setting, the code would look something like
contains(list, x) => falseinsert(list, x)contains(list, x) => trueAs you can see, contains returns a different result depending on the time you call it. In a functional setting however, the function cannot change the list object, so you'd have to write
contains(lst1, x) => falselst2 = insert(lst1, x)contains(lst1, x) => falsecontains(lst2, x) => trueThe insert function needs to create a new object and return that as its result. This might look very inefficient, but it isn't necessarily: since you have the guarantee nothing will ever be modified, you can reuse parts of lst1 to build lst2. More on this in SICP.
State in functional languages
We have seen both the imperative style (stateful) and the functional style (stateless) of programming. An imperative programming language is one that pushes the programmer more towards the imperative style, but certainly does not make the functional style impossible. The same is true for functional languages: most functional languages offer state in one way or another, e.g. Scheme lets you modify your variables, SML and Oz provide cells, O'Caml offers mutable record fields, ... Haskell is one of the few languages that can be called purely functional because it has made no concessions whatsoever to the imperative world.
So, one could say that imperative languages make their variables mutable by default, which can often be overridden using a keyword ('const' in C++, 'readonly' in C#, 'final' in Java, ...), while functional languages often prefer to make their variables immutable, except for those where the programmer explicitly asks for mutability.
The cell
A functional programming language consists of having values which you apply to functions (functions themselves are also values, which leads to higher-order programming, but we'll leave that topic to SICP). A cell is a special kind of object (or value, here considered the same thing) which has a content that can be modified as though it was a normal mutable variable. The following O'Caml code
let total = ref 0and current = ref 1inwhile !current <= 10 do total := !total + !current; current := !current + 1done;!totalcomputes the sum of all numbers from 1 through 10 in an imperative way. The '!'-operator must be used to fetch to contents of the cell, and the ':=' operator serves to modify its contents. Cell creation is done with ref.
We could say that an imperative language automatically creates the cell for you when necessary, whereas functional languages do not.
Bindings
Programming languages generally offer you the possibility to use identifiers to name things, such as arguments, functions, ... A binding determines what an identifier actually refers to. Let's work in the functional model and pretend C++ automatically creates cells for you, then the following code
int x = 5;leads to the following configuration:
x ---> cell ---> 5The right arrow represents the contents of the cell, and can be changed using the '=' operator (in C++). The left arrow is called the binding: it determines to what the identifier 'x' refers. 'x' can be rebound to another value/object by introducing a new scope in which 'x' is redeclared:
int x;void f(int x){ for ( int x = 0; x != 10; ++x ) { ... }}class A{ public A(int x) : x(x) { } private int x;};A binding 'x->value' has a scope, i.e. the places in your code where 'x' will refer to 'value'. There are different kinds of scoping; most languages use lexical scoping, but dynamic scoping is another possibility which will be discussed in SICP.
Bindings can sometimes lead to confusion, consider this O'Caml code:
let x = 5;;let y () = print_int x;;let x = 8;;Calling 'y' will print 5, not 8, since the 'x' in the function body is bound by the first 'let'-statement. Here, the difference between binding and assignment is made clear: the second 'let' introduces a new binding for 'x', and does not assign a value to a cell attached to 'x' (since there is no cell). The following code uses assignment instead:
let x = ref 5;;let y () = print_int !x;;x := 8;;Calling 'y' will print 8 in this case.
It is important to make the difference between binding and assignment: what leads to the most confusion is the fact that same operator '=' is given different meanings in different languages. Imperative languages such as C++, C# and Java use it for expressing assignment, Scheme uses it for numerical comparison, O'Caml, SML and Haskell use it to express bindings, Prolog and Oz for unification, ...
