SI413 Scheme Lab 0: Functional Programming & Scheme

Properties that define functional languages

The big difference between the functional programming paradigm and the the other pradigms we've seen - structured/procedural and object oriented - is that functional programming seeks to take references to time out of the program. That probably sounds wierd. Time permeates our programs, because any idea of execution order automatically brings time into the picture. When you write

int x = 0;
x = 3;
x = x + 1;

you are stating that "int x = 0" should be performed before "x = 3" which should come before "x = x + 1". Programs like this proceed by evaluating each statement in turn, and each evaluation may have side effects, meaning that the state of the program (roughly the values of its variables) changes. Functional programming tries to remove this dependency on side effects, and to remove these explicit references to time (i.e. ordering of statements). After we get a bit more comfortable with functional programming in a specific language - Scheme is the language we'll use - we'll try to talk about what benefits there are in the functional approach.

Here are the basic properties that define a language as being functional:

• referential transparency (Math has it!) Referential transparency means that a given expression has the same value whenever and whereever it is encountered. In math, we have this. We're allowed to make simplifications like (3 x - 2 sin(x)) - (3 x - 2 sin(x)) → 0 precisely because we know that the two syntactically identical expressions have the same value. This is not necessarily true in programs. How about (2 - i++) - (2 - i++)? I'm subtracting two syntactically identical expressions, so do I get zero? Nope. So C/C++/Java are not referentially transparent.

  Why is it desireable? The fact that f(x) - f(x) is not always zero in imperative programs is a source of error for humans, and it limits what can be done automatically with programs. Ex: Optimizing compilers, automatic parallelization

  Lack of referential tranparency does interesting things. For example, suppose S is a stack of numbers with 3 on the top and 5 second from the top, and suppose you evaluate the expression "S.pop() - S.pop()". What do you think you get? Hard to say! Depends which pop gets executed first. In C++, for example, this is not specified, so different compilers could give you different things. It's not just a question of the ambiguity - after all C++ could change the rules to fix that the leftmost operand, for example, gets evaluated first and there wouldn't be any ambiguity. The point is that determining the value of a very simple expression becomes a very subtle exercise.

• functions are first-class objects What does this mean? Well, functions in C/C++/Java are not "objects". (Recall that "objects" in a program have both type and a value.) In C and C++ they can be pointed to, and they even have type, but they do not have value. Most importantly: New functions cannot be created as a program runs. This is in direct contrast to objects (i.e. data); new objects are created all the time while the program runs. [Note: function objects in C++ ameliorate this somewhat.]

• types are first-class objects (in some languages, not Scheme) Scheme, the language we'll use is essentially a type-less language. The interpreter is not concerned with types, except for builtin types. It doesn't check user-defined types the way C/C++/Java do. However, strongly typed functional languages like ML do check types. Moreover, in these languages types are first class objects just like data and functions. In C/C++/Java running programs cannot create new types. In strongly typed functional languages they can. Types can also be passed in and out of functions, which is not the case in the imperative languages we know (although templates allow a limited form of this.)

Additionally, there are several properties that functional languages traditionally have, mostly because realizing the above properties would be difficult without them.

• Garbage collection
• Built-in lists
• Interpreted

We often call functional programs "declarative" instead of "imperative". In declarative programming we describe the object to be computed. In imperative we give a sequence of commands - the actions that accomplish the computation. In other words, declarative programming describes the result of the computation, while imperative describes the computation itself.