Could we build a functional computer

There is nothing wrong with a functional language maintaining mutable state. Even "pure" functional languages such as Haskell need to maintain state in order to interact with the real world. "Impure" functional languages like Clojure allow side effects which can include mutating state.

The main point is that functional languages discourage mutable state unless you really need it. The general style is to program using pure functions and immutable data, and only interact with "impure" mutable state in the specific parts of your code that require it. That way, you can keep the rest of your code base "pure".

I think there are several reasons why STM is more common in functional languages:

• Research: STM is a hot research topic, and programming language researchers frequently prefer to work with functional langauges (a reasearch topic in themselves, plus it is easier to create "proofs" about program behaviour)
• Lock don't compose: STM can be seen as an alternative to lock-based approaches to concurrency, which starts to run into problems when you scale up to complex systems by composing different components. This is arguably the main "pragmatic" reason for STM
• STM fits well with immutability: If you have a large immutable structure, you want to make sure it stays immutable, so you don't want some other thread coming in and mutating some sub-element. Likewise, if you can guarantee immutability of said data structure, you can reliably treat is as a stable "value" in your STM system.

I personally like Clojure's approach of allowing mutability, but only in the context of strictly controlled "managed references" that may participate in STM transactions. Everything else in the language is "purely functional".

  ;; define two accounts as managed references
  (def account-a (ref 100))
  (def account-b (ref 100))

  ;; define a transactional "transfer" function
  (defn transfer [ref-1 ref-2 amount]
    (dosync
      (if (>= @ref-1 amount)
        (do 
          (alter ref-1 - amount)
          (alter ref-2 + amount))
        (throw (Error. "Insufficient balance!")))))

  ;; make a stranfer
  (transfer account-a account-b 75)

  ;; inspect the accounts
  @account-a
  => 25

  @account-b
  => 175

Note the above code is fully transactional and atomic - an external observer reading the two balances within another transaction will always see a consistent atomic state, i.e. the two balances will always sum to 200. With lock-based concurrency, this is a surprisingly hard problem to solve in a large complex system with many transactional entities.

For some extra enlightenment, Rich Hickey does an excellent job of explaining Clojure's STM in this video

For the purposes of this answer I define "purely functional language" to mean a functional language in which functions are referentially transparent, i.e. calling the same function multiple times with the same arguments will always produce the same results. This is, I believe, the usual definition of a purely functional language.

Pure functional programming languages do not allow side effects (and are therefore of little use in practice because any useful program does have side effects, e.g. when it interacts with the external world).

The easiest way to achieve referential transparency would indeed be to disallow side effects and there are indeed languages in which that is the case (mostly domain specific ones). However it is certainly not the only way and most general purpose purely functional languages (Haskell, Clean, ...) do allow side effect.

Also saying that a programming language without side effects is little use in practice isn't really fair I think - certainly not for domain specific languages, but even for general purpose languages, I'd imagine a language can be quite useful without providing side effects. Maybe not for console applications, but I think GUI applications can be nicely implemented without side-effects in, say, the functional reactive paradigm.

Regarding point 1, you can interact with the environment in purely functional languages but you have to explicitly mark the code (functions) that introduces them (e.g. in Haskell by means of monadic types).

That's a bit over simplifying it. Just having a system where side-effecting functions need to be marked as such (similar to const-correctness in C++, but with general side-effects) is not enough to ensure referential transparency. You need to ensure that a program can never call a function multiple times with the same arguments and get different results. You could either do that by making things like readLine be something that's not a function (that's what Haskell does with the IO monad) or you could make it impossible to call side-effecting functions multiple times with the same argument (that's what Clean does). In the latter case the compiler would ensure that every time you call a side-effecting function, you do so with a fresh argument, and it would reject any program where you pass the same argument to a side-effecting function twice.

Pure functional programming languages do not allow to write a program that maintains state (which makes programming very awkward because in many application you do need state).

Again, a purely functional language might very well disallow mutable state, but it's certainly possible to be pure and still have mutable state, if you implement it in the same way as I described with side-effects above. Really mutable state is just another form of side-effects.

That said, functional programming languages definitely do discourage mutable state - pure ones especially so. And I don't think that that makes programming awkward - quite the opposite. Sometimes (but not all that often) mutable state can't be avoided without losing performance or clarity (which is why languages like Haskell do have facilities for mutable state), but most often it can.

If they are misconceptions, how did they come about?

I think many people simply read "a function must produce the same result when called with the same arguments" and conclude from that that it's not possible to implement something like readLine or code that maintains mutable state. So they're simply not aware of the "cheats" that purely functional languages can use to introduce these things without breaking referential transparency.

Also mutable state is heavily discourages in functional languages, so it isn't all that much of a leap to assume it's not allowed at all in purely functional ones.

Could you write a (possibly small) code snippet illustrating the Haskell idiomatic way to (1) implement side effects and (2) implement a computation with state?

Here's an application in Pseudo-Haskell that asks the user for a name and greets him. Pseudo-Haskell is a language that I just invented, which has Haskell's IO system, but uses more conventional syntax, more descriptive function names and has no do-notation (as that would just distract from how exactly the IO monad works):

greet(name) = print("Hello, " ++ name ++ "!")
main = composeMonad(readLine, greet)

The clue here is that readLine is a value of type IO<String> and composeMonad is a function that takes an argument of type IO<T> (for some type T) and another argument that is a function which takes an argument of type T and returns a value of type IO<U> (for some type U). print is a function that takes a string and returns a value of type IO<void>.

A value of type IO<A> is a value that "encodes" a given action that produces a value of type A. composeMonad(m, f) produces a new IO value that encodes the action of m followed by the action of f(x), where x is the value produces by performing the action of m.

Mutable state would look like this:

counter = mutableVariable(0)
increaseCounter(cnt) =
    setIncreasedValue(oldValue) = setValue(cnt, oldValue + 1)
    composeMonad(getValue(cnt), setIncreasedValue)

printCounter(cnt) = composeMonad( getValue(cnt), print )

main = composeVoidMonad( increaseCounter(counter), printCounter(counter) )

Here mutableVariable is a function that takes value of any type T and produces a MutableVariable<T>. The function getValue takes MutableVariable and returns an IO<T> that produces its current value. setValue takes a MutableVariable<T> and a T and returns an IO<void> that sets the value. composeVoidMonad is the same as composeMonad except that the first argument is an IO that does not produce a sensible value and the second argument is another monad, not a function that returns a monad.

In Haskell there's some syntactic sugar, that makes this whole ordeal less painful, but it's still obvious that mutable state is something that language doesn't really want you to do.