TEACH FUNCTIONAL.STYLE                             Aaron Sloman Jan 1997


             WHAT IS THE "FUNCTIONAL" STYLE OF PROGRAMMING?

This file can be read as an extension to TEACH * RECURSION

CONTENTS

 -- Introduction
 -- Restrictions in functional languages
 -- Positive features of functional languages
 -- Why use functional languages?
 -- Which languages are best?

-- Introduction -------------------------------------------------------

There are some programming languages which have the following
features, some negative, and some positive, and they are often referred
to as "functional" languages. It is also possible to program in a
functional style in a language which includes the components allowed
in functional languages.

-- Restrictions in functional languages -------------------------------

They DISALLOW the following:

o Statement sequences:
    Only function calls are allowed, i.e. expressions to be evaluated,
    including complete conditional expressions, like
        if x == 0 then 1 else factorial(x - 1) * x endif

    Thus you can't have a statement sequence like:

        x + 5 -> x;
        foo(x);
        baz(x);

    Instead you'd have to define a procedure called foobaz and run it
    with
            foobaz(x + 5)

    Defining foobaz to do first foo then baz can be tricky!

o Loops: do all repetition by using recursion

o Assignments of values to variables
    The only assignments allowed are the implicit assignment involved
    in giving values to function arguments, and the initialisation of
    constant identifiers.

o Side effects
    Changing the contents of an existing list or string or vector, etc.
    is not allowed.

    Instead a COPY always has to be made, if you want part of a list
    changed. The original version remains unchanged, so programs that
    refer to the old version will not be affected. This rules out the
    use of a single large database whose components can be updated.
    Since making copies of large structures can be very expensive,
    special techniques may be used to represent a changed data structure
    by a complex structure containing the original plus an indication of
    the changes.

-- Positive features of functional languages --------------------------

However functional languages don't simply exclude features. They
generally also INCLUDE the following types of "high order functional
programming":

o Treating functions as "first class objects"
    This includes the ability to use functions as arguments and results
    of functions (procedures), and to include functions as elements of
    lists, vectors, arrays, etc.

    Functions here include closures
        (e.g. partial application in Pop-11: see HELP * CLOSURES,
        and lexical closures, see HELP * LVARS/'lexical closures')

-- Why use functional languages? --------------------------------------

Languages with these "functional" restrictions, can be analysed
mathematically far more easily than languages like Pop-11, Lisp, C, C++,
Pascal, etc. which allow arbitrary sequences of statements, loops,
multiple assignments to the same variable, and updating of
data-structures.

This is especially the case if all identifiers have syntactic "types"
which restrict their values, as is the case in ML, Miranda, C++, Java,
Ada and many of the non-AI languages.

Logic programming languages, like Prolog have many of the features of
functional languages, which follow naturally from the restriction to a
logical syntax. However, most implementations of Prolog also have extra
features allowing programmers to get round these restrictions, e.g.
the "cut" operator. Moreover, Prolog does not include typed identifiers.

-- Which languages are best? ------------------------------------------

There are endless debates about which sorts of languages are "best" and
they are really rather silly and often take on the characteristics of
debates about which religion is the true one.

Different languages are useful for different purposes. Understanding
what sorts of different purposes there are includes understanding the
nature of different programming tasks, and also the nature of different
stages during the development of a program. E.g. a language that is good
for final production of a "finished" product to be used on millions of
computers is not necessarily so good for the initial exploration of an
ill-understood problem (e.g. designing a "friendly" interface).

A language that is good for building a system that is in a fixed final
form is not necesarily good for building a system that nees to be
extendable and tailorable by users, especially if it is to be extendable
while it is actually running.

One of the things that make very general languages like Pop-11 and
Common Lisp attractive to some programmers is the fact that there is a
subset that can be used like a functional language, whereas other parts
of the language provide powerful facilities that can be very useful when
the functional subset is hard to use.

The functional style can also be found aesthetically attractive,
especially to mathematicians. (I like it very much, when it fits a
problem.)

Sometimes using the functional style with recursion makes tracing and
debugging easier than using loops, since it is easier to switch tracing
on and off for procedure entry and exit than to turn on tracing of
looping constructs: that normally requires adding and removing print
statements (admittedly quick and easy in an incrementlly compiled
language like Pop-11 or Lisp).
    (See also TEACH * TRACE, HELP * DEBUGGER, HELP * TRACE)

Much of the TEACH * RECURSION file illustrates the functional subset of
Pop-11. Common Lisp also has a functional subset, but it is a bit clumsy
to use because in common lisp variables have two distinct sorts of
values, function values and ordinary values. For more on Lisp see
    TEACH * READLISP, * LISPNOTES, HELP * CLISP

Scheme is a widely used Lisp-like functional language that is very
similar to the functional subset of Pop-11, but using the Lisp syntax. T
is a Lisp variant developed at Yale University that is more like Pop-11
in that it includes the functional subset of Lisp and lots of other
things, but treats functions as ordinary values of variables.

Other more or less pure functional languages are

    ML (SML), Miranda, Haskell, Dylan, .... and no doubt many more.


--- $usepop/pop/teach/functional.style
--- Copyright University of Birmingham 1997. All rights reserved. ------