Hi there, Christopher Svanefalk <christopher.svanef...@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/
signature.asc
Description: PGP signature
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
