[Haskell-cafe] On the purity of Haskell

Chris Smith cdsmith at gmail.com
Fri Dec 30 21:04:21 CET 2011


On Fri, 2011-12-30 at 12:24 -0600, Gregg Reynolds wrote:
> No redefinition involved, just a narrowing of scope.  I assume that,
> since we are talking about computation, it is reasonable to limit  the
> discussion to the class of computable functions - which, by the way,
> are about as deeply embedded in orthodox mathematics as you can get,
> by way of recursion theory.  What would be the point of talking about
> non-computable functions for the semantics of a programming language?

Computability is just a distraction here.  The problem isn't whether
"getAnIntFromUser" is computable... it is whether it's a function at
all!  Even uncomputable functions are first and foremost functions, and
not being computable is just a property that they have.  Clearly this is
not a function at all.  It doesn't even have the general form of a
function: it has no input, so clearly it can't map each input value to a
specific output value.  Now, since it's not a function, it makes little
sense to even try to talk about whether it is computable or not (unless
you first define a notion of computability for something other than
functions).

If you want to talk about things that read values from the keyboard or
such, calling them "uncomputable" is confusing, since the issue isn't
really computability at all, but rather needing information from a
constantly changing external environment.  I suspect that at least some
people talking about "functions" are using the word to mean a
computational procedure, the sort of thing meant by the C programming
language by that word.  Uncomputable is a very poor word for that idea.


-- 
Chris Smith




More information about the Haskell-Cafe mailing list