In section 5 of _Fun with Phantom Types_, Hinze states...
"Let us move on to one of the miracles of theoretical computer
science. In Haskell, one cannot show values of functional types. For
reasons of computability, there is no systematic way of showing
functions and any ad-hoc approach would destroy referential transparency
(except if show were a constant function). For instance, if show yielded
the text of a function definition, we could distinguish, say, quick sort
from merge sort. Substituting one for the other could then possibly
change the meaning of a program."
that doesn't look up to Ralf's usual standards, but it also looks more
like an informal introduction to a section that may explore the issues
in more detail.
there is no problem in showing functions in general, and the 'show'
problem is not specific to functions. there is a problem with converting
expressions into representations to be made available to the functional
programs from which those expressions came in the first place.
functional languages provide many ways of writing expressions with
the same meaning, as well as a normalization procedure that attempts
to compute a unique normal form for each class of expressions.
within such an equivalence class, you have many different
representations, all with the same meaning, which is convenient for
programming, because you may not know the specific result you
are looking for, but perhaps you know that it is equivalent to
'sort [1,5,3,8]'. so you can use any member of the equivalence
class to stand for the meaning of expressions in that class, and if
we ignore performance, all that matters about an expression is
its meaning.
if you want to show an expression, you need to evaluate it, then
find a representation for its meaning (for functions, perhaps as an
enumeration of parameter/result pairs, or a lambda-calculus
representation, or a number in an enumeration of all functions
of a type, ..). what you cannot do, however, is showing an
expression by returning a representation of its current form,
because that would allow you to distinguish different members
of the same equivalence class, meaning that they wouldn't be
equivalent anymore!
that holds even for simple arithmetic expressions: "3+2" and
"2+3" and "5" are just three ways of writing down the same
meaning. if you had a primitive "reify" such that
'reify (3+2) == "3+2"', but 'reify (2+3) == "2+3"', then that
primitive wouldn't even be a function - it yields different
results for different representations of the same argument!
hth,
claus
...I guess I'm not understanding what that means. Would there be some
sort of contradiction that arises when trying to evaluate "show (show)"
or somesuch? Can anyone point me in the direction of information that
tries to explain why this is? I'm at a loss as to what search terms to
use.
Thanks,
Greg Buchholz
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
