[Haskell-cafe] Theoretical question: are side effects necessary?

[Ertugrul Söylemez]

Hi there,

Christopher Svanefalk <christopher.svanefalk at gmail.com> wrote:

> there is a question I have been thinking about a bit. In short, we
> could simply formulate it like this:
>
> Are there any problems which *cannot *be solved a side effect-free
> language (such as Haskell)? In other words, are there problems that
> would explicitly demand semantics that can only be provided by a
> language allowing direct modification of external state variables,
> such as Java and C++?
>
> If not, are there problems which are simply *infeasible *to solve with
> a side effect-free language?
>
> I realize this question is very broad, and I am not expecting an exact
> answer by any means. I am asking since I am curious about the relation
> between functional and imperative/procedural languages in general. I
> primarily come from a Java background, but I can program Haskell and
> Erlang, and have recently started exploring Scala, so this would be
> interesting to know.

Every problem is solvable in a pure language like Haskell, but I guess
you are more interested in the fundamentals.  There is a proof that
lambda calculus (which is the smallest common denominator of all purely
functional languages) is equivalent to the model of Turing machines.
That basically means that any computer program can be written in both.

Adding types changes the whole picture.  In the typed lambda calculus
not every program can be expressed.  Particularly every program in this
model must terminate.  To get back the full expressivity you need to add
an (opaque) general recursion operator, and most languages do that by
allowing a definition to refer to any other, including itself.  Many of
them (F#, OCaml) have an explicit "let rec"-style construct, others
(Haskell, Clean) allow recursion everywhere.

Functional languages with a more powerful type system (like Agda) even
refrain from adding general recursion.  These are in fact not
Turing-complete.  Without general recursion you can use a language for
proofs, whether you prove theorems or program behavior.  Still you can
express infinite recursion using coinduction.

About feasibility:  For both models there is a set of problems which are
hard to express, and they are fairly disjoint.  Usually a hard to
express problem in one is easy to express in the other.  To add more
expressivity imperative languages add language constructs (loops, OO,
exceptions, etc.), while functional languages add combinators and
composition patterns (monads, higher order functions, etc.).  I think if
a problem is infeasible to express in one model, it will be infeasible
in the other as well.


Greets,
Ertugrul

-- 
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120316/ee802a4a/attachment.pgp>