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
instead oflet average = (a + b) / 2 in f(average,average)
because a potential side effect of the subprogram a would be carried out once in the first case, but twice in the second.f((a + b) / 2,(a + b) / 2)
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
formany(p) = (p >>> many(p)) ||| epsilon
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.