John says we can't go from a function to its concrete representation
ie E -> [E] - OK. He hints that implementations are from concrete
representations to real functions ie [E] -> E. I disagree profoundly.
Implementations are from concrete representations to concrete
representations. Suppose E1 is the original language, say Haskell, and E2 is
the language of the internal form, say "lambda calculus" in strings. Then the
compiler is: [E1] -> [E2] and a string based beta reduction implementation
is [E2] -> [E2] NOT [E2] -> E where E is "real" functions. There are no
"real" functions in computers, only physical representations made of
quarks or quantum states or whatever, and our abstractions from them.
Now language implementations are certainly full of data structures eg machine
code which a CPU traverses eg graphs which an STG machine traverses. These
abstractions are none the less concrete representations - they still have
those essential brackets [...] round them. We choose them to preserve the
meaning of our original programs relative to the implementation. Yes, this is
horrendously operational! So are computers! John suggests that printing
things in [...] is within the canon. If implementations are [...] -> [...]
then printing final values should be acceptable.
Mark says:
>If you really want to manipulate some concrete representation of function
>values, the best thing to do is to create an explicit concrete
>representation.
So to manipulate concrete representations of functions in a functional
language we have to implement functions all over again? But don't we already
have concrete representations of functions in the original functional language
implementation? All (all?) I'm proposing is to print them out.
It seems really eccentric to me that we can input functions and build
functions by function updating and time how a long an
implementation takes to build such functions but we can't then display
their final values. I teach a course on denotational semantics
and ask the students to use my beyond-the-pale strict, untyped functional
language with integral 1st class grammar rules to implement simple languages
from their definitions. My language will attempt to print a closure as a local
definition binding free variable values in a function. This is invaluable for
seeing how state and store and environment functions grow through pure
function updating during program execution. I would like to use
a mainstream language like Haskell or SML but do not want to get
bogged down with inventing ad-hoc representations when the lambda calculus
allows function updating for free.
Incidentally, my point about not bothering to evaluate functional
programs whose final values are functions was serious. Presumably,
people don't generally write programs that return functions as
final values? Maybe functions are the only types in functional languages
which are not 1st class objects - full orthogonality doesn't
stretch to printing functions. And we call this functional programming?
Greg Michaelson
