Functional Programming
2. Programming Styles



2.1 Introduction

The main object of this course is to change the way you think about computation and how to program. We are going to explore the key foundational notions that underly a programming style called functional programming. If you master these, your approach to programming will change dramatically.

These notes are just a rough summary of the various ideas we will explore. More detail can be found in the links and references we provide, and more significantly by the usual judicious search of the web.

We are going to begin with a very loose look at the relationship between the syntax of a program and how it evaluates. A proper treatment of this subject is the domain of a different type of course (pun intended). But if you are curious, look up semantics (operational semantics, axiomatic semantics, and denotational semantics) on Wikipedia.

2.2 Syntax and Semantics

Programs are written in programming languages. Every language has rules for constructing properly formed documents ("sentences" as the linguists would say). This is the syntax of the language. The process of parsing is used to determine if a document is syntactically correct.

Every language strives to convey meaning. Semantics deals with the how documents in a language are interpreted and understood by their readers.

Syntax is usually quite precise, at least in programming languages: a sentence is either grammatically correct or not. Meaning is much more subtle and debatable, especially in natural languages, but even in programming languages. The famous Artificial Intelligence (AI) sentence "Time flies like an arrow" is syntactically correct, but has a number of different parses, and has a variety of meanings.

What does this string of characters: (1 + 2) mean? Is it 3? Is it s(2)? Is it s(s(s(0)))?

What about this: ((3+4) * (5+6))? Do all of these mean the same thing?
((3+4) * (5+6)), (7 * (5+6)), (7 * 11), 77
Normally we say yes, because we can provide a series of steps for rewriting one expression into an equivalent one.

That is, we have meaning-preserving tranformations that let us convert a sentence from one syntatic form into another, while preserving the meaning inherent in the sentence. Eventually we transform it into something we understand (for some value of "understand").

Here is one way of rewriting where the idea is to reduce the leftmost deepest nested expression first:
((3+4) * (5+6)) =>
(7 * (5+6)) =>
(7 * 11) =>
77


What about program fragments like this code/Overview/if-while.txt

    if ( B > 0 ) {
        A = 2;
        }
    else {
        A= 1;
        }
     
     
     
     
    while ( A > 0 ) {
        ...
        }


Program fragments with equivalent meanings are fairly easy to come by for the conditional statement, but much more difficult for the loop (unless we know say that A <= 0).

What about 10-1? Is it 9 or 1? Obviously we need to have some additional information, such as whether we are using base 10 or 2 for our number representation.

2.3 Operational Semantics

How do we ultimately understand something? We run it within a model of computation and see what the effects are. Operational Semantics defines the meaning of a program in terms of the transitions it follows to change from one state to the next. To understand an imperative program, we need to know details about how the program statements cause the underlying machine model to change state.

Imperative programs make the state of the computation visible and allow us to directly change it. For example, the statement
A = B + 2
is read imperatively as "take the value stored in memory location B, add the value 2 to that, and store the computed result into memory location A".

Attached to the understanding of a statement is also a frame assumption which says that the statement also doesn't cause any other change of state that we care about. That is, any side-effects that occur do not affect the particular sense of meaning that we are using.

2.4 Transformational Semantics

Ultimately all meaning is operational, since we want to affect the state of our environment. But in the process of understanding what a program does we can transform parts of it into syntactically different form but with equivalent semantics (at least with respect to things that are important to us at the time.)

In transformational semantics, we don't think of A = B + 2 as a statement that stores the result of computing the contents of memory location B plus 2 into memory location named A. But instead we think of it as binding A to the right hand side in a way that permits any mention of A to be replaced by the expression (B+2) that it is bound to.

The manipulations we did above where we rewrote the arithmetic expressions above are examples of transformation semantics. We derived a sequence of equivalent programs without having to ultimately know what they did.

Note that a key factor in transformations is referential transparancy. An expression is referentially transparent if it can be replaced by its value without changing the program. This is what enables substitution of equals by equals. The opposite is called referential opaqueness.

The expression sin(x) + sin(x) can be replaced by 2 * sin(x) because the basic arithmetic and trignometric functions are referentially transparent.

On the other hand, the use of random is not referentially transparent because it returns a (possibly) different value on each invocation. Thus the expression random(2) + random(2) cannot be replaced by 2 * random(2).

2.5 Programming Styles

Much has been argued about what a program should look like, how you should program, and what programming language sins deserve eternal damnation. But the reality of programming is that different styles are suited to solving different kinds of problems. Few programming languages are purely of one style, but include a mix.

Loosely speaking, we have the following styles of program: If you have used Python or Perl, you have already seen aspects of functional programming embedded into an imperative language. For example, in Python there is an imperative way for constructing a list of squares, and a list comprehension way.

code/Python/listcomp.py

    # the imperative way to build a list of the squares of the integers 
    # 1 .. 10
    squares = []
    for x in range(10):
        squares.append(x**2)
    print(squares)
     
    # the functional way using list comprehension.  The expression x**2 is
    # mapped over the list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    squares = [x**2 for x in range(10)]
    print(squares)
     
     
The same approach in Perl is code/Perl/listcomp.pl

    # the imperative way to build a list of the squares of the integers 
    # 1 .. 10
    my @range = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
     
    my @squares = ();
    foreach my $x ( @range ) {
        push @squares, $x * $x;
        }
    print("@squares\n");
         
    # the functional way using list comprehension.  The expression x**2 is
    # mapped over the list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    @squares = map { $_ * $_ } @range;
    print("@squares\n");
2. Programming Styles
Notes on Functional Programming / Version 2.10 2014-02-24