3 Declarative programming and input/output

In later sections, we will describe how one can use combinators for programming input/output. But before that, we will discuss how output can be done in a declarative programming language. Output from a program can also be seen as an effect that the program has on the outside world. When combining effects, their order is often highly important (the reader might want to try different combinations of the effects ``Open door'', and ``Walk through door'', for example). This is an important aspect which we must have in mind when considering subprograms for defining effects.

There are two widely used styles for dealing with effects in declarative programming languages. We either allow all subprograms to directly have effects on the outer world, or we only allow subprograms to return values that represent effects.

Consider a subprogram in a programming language using direct effects. If the subprogram is a function that returns some value, it is often said that the function can have a side effect while computing its value. The order in which these side effects happen is made precise by defining a computation order for expressions. This is most easily done by saying that all arguments to subprograms should be computed left to right, and then the subprogram is called. Also, an expression which uses a local definition should compute the definition before the expression. Such programming languages are called strict.

Side effects can interact with the programmer's activity of forming new subprograms, or naming subexpressions. For example, it is no longer clear that we could write

let average = (a + b) / 2 

in f(average,average)
instead of

f((a + b) / 2,(a + b) / 2)
because a potential side effect of the subprogram a would be carried out once in the first case, but twice in the second.

Another problem with combinator programming in strict programming languages is that we must be much more careful when defining combinators in terms of themselves. If we use the definition

many(p) = (p >>> many(p)) ||| epsilon
for many, we end up in an infinite loop, if arguments are computed strictly.

It is a very desirable feature of a programming language that subprograms do not have side effects. This feature is used in the non-strict, purely functional programming languages that we will use in the rest of this thesis. The term ``purely functional'' means that it is guaranteed that a function always return the same value if its arguments have the same value, and that it does not have any side effect. More generally, if the same expression occurs in many places (as a above, for example), it is guaranteed that all those occurrences compute to the same value. It is only in a purely functional programming language that we can introduce the variable average in the previous example, regardless of what a and b are.

In purely functional languages, we use the second way of dealing with effects, where subprograms may return values that represent effects, instead of performing them directly. A representation of an effect can then be combined with other representations of effects, yielding a new representation of an effect. Finally, the effect that our whole program represents is carried out. This means that issues of effects and computations are separated. When defining and combining effects, we do not have to bother about which parts of our program should be computed, how many times they might be computed, and in which order.

Having combinators that return representations of effects opens up the possibility to manipulate these effects before they are carried out. This can be used to adapt the effects of existing combinators to new situations.

In what follows, we will often speak about combinators having various effects, or doing various kind of input/output. At times, it will be convenient to think that the combinators actually perform these effects directly, but it is important to remember that they only define a representation of an effect.