Functional Programming


One of a series of tutorials about Scheme in general
and the Wraith Scheme interpreter in particular.

Copyright © 2011 Jay Reynolds Freeman, all rights reserved.
Personal Web Site: http://JayReynoldsFreeman.com
EMail: Jay_Reynolds_Freeman@mac.com.


Functional programming is a style of programming that avoids saving state and also avoids changing the values of variables. It envisions computation as a series of applications of mathematical functions to data. It is very nearly synonymous with applicative programming, but both phrases have been around for quite a while, and may have somewhat different meanings in different contexts.

In case the connection with mathematical functions isn't clear, let's talk about it a little more: You can consider a mathematical function to be a black box, into which you put input values of some sort, and from which you obtain a result. What you get out of the box depends only on what you put into it -- a mathematical function is not considered to have any ability to remember anything, and with no memory, it has nothing but the input values to use in determining what result to return. Saved state would be an example of something that a function's "memory" could access, and mutable data would be an example of the function's memories changing from time to time. Mutating data would also be an example of what programmers call side effects -- a procedure doing something that leaves evidence of its action, so that you can tell it has been there, so to speak.

The business of a function's return value depending only on its input values is sometimes called referential transparency: The idea is that what the function returns does not depend on how many times it has been called, or on what previous values it has been called with. When you are using a function, there is no way to tell whether it has ever been used before -- whether there have been any prior references to it.

Functional programming has been a matter of considerable interest in computer science for quite a while. Some of that interest clearly has to do with the likes and dislikes of individual programmers, and with their mathematical interests, and I am not going to try to tell you what you should like or what you should be interested in. Rather, I am going to make two points and then elaborate on them.

Now let's go through those more slowly, one at a time.


When I say that Scheme is almost a functional language, what I really mean is that Scheme is in essence a perfectly good functional language with a few extra, non-functional features added in, like ants at a picnic. You can write perfectly good functional programs in Scheme simply by not using the non-functional features.

R5 Scheme only has a small handful of built-in procedures, special forms and macros that change state, and nearly all of them end with an exclamation point (which is sometimes called a bang by programmers). They include "set!", "set-car!", "set-cdr!", "vector-set!", "vector-fill!", "string-set!", "string-fill!", "define" and "define-syntax". Wraith Scheme adds some others as enhancements, but most such additions are more or less administrative procedures that control the internal state of the Wraith Scheme interpreter itself -- things like whether the compiler is turned on or the maximum number of items in a list that will be printed. Thus -- always remembering about "define" and "define-syntax" -- it is pretty much the case that you can write functional programs in Scheme by not using any feature whose name ends with a "bang" (an exclamation point).

Much of the potential power of Scheme as a functional language comes from the fact that Scheme has first-class procedures. What that means is that in Scheme, procedures, special forms and macros are data items that can be used like any other, simpler data items, such as numbers, characters and strings. In particular, they can be used as the arguments to other procedures, or as the values returned by procedures. Many computer languages do not allow that at all, and many others make it difficult. The computer-science idea of first-class procedures is related to the mathematical notion of higher-order functions, which are indeed mathematical functions that can take other functions as arguments and return them as results.

So for example, in Scheme it is very easy to pass a function to some other function, with the idea that the other function can use it when and if necessary. It turns out that that is a very functional-programming kind of thing to do.


Practical advantages of functional programming include:


Practical disadvantages of functional programming include:


Wraith Scheme has one enhancement designed to help keep would-be functional programmers honest. There is a way to arrange that a chunk of code run by Wraith Scheme will report an error if it ever tries to change state; for example, if it ever uses "set!" or "set-car!" and so on. It is not perfect -- there are ways to cheat -- but if you are trying to write functional programs in Wraith Scheme, it may help. It involves just one new procedure:

(In which <thunk> is a procedure of no arguments or a lambda expression of no arguments.)

This procedure performs <thunk> with Wraith Scheme's ability to change state turned off, and returns whatever <thunk> did. Specifically, within the code represented by <thunk>, any attempt to use any of the standard procedures that change state, or to use any of Wraith Scheme's enhancements that do so, will cause Wraith Scheme to report an error.

By way of illustration:

but

produces the error message:


The Wraith Scheme Help File has a long section about "e::perform-applicative", and what it does, and how it works, and how to use it. That section is called "Applicative Programming", and not "Functional Programming".


-- Jay Reynolds Freeman (Jay_Reynolds_Freeman@mac.com)


Wraith Face