[Haskell-cafe] "show" for functional types

[Claus Reinke]

>    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
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe