[mercury-users] term_expansion (was Re: Microsoft Common Lisp?)

[Fergus Henderson]

Peter Schachte, you wrote:
> 
> Joris Welkenhuysen wrote:
> 
> > Peter Schachte wrote:
> > > Add new directive to the language:
> > > 
> > >         :- transformation Module.
> > 
> > Before embarking on this project, I would like to see a clear and
> > somewhat formal definition of these proposed language feature.
> > It goes without saying that this definition shouldn't be based on
> > any compiler internals. Do you think this can be done ?
> 
> Not currently.  The reason is that I don't believe it's a very good
> idea to define too precisely the types that all Mercury compilers must
> use to represent programs being compiled.  This would tie the hands of
> implementors who might have some clever ideas of how to, for example,
> implement the compiler more efficiently, or give better error
> messages, or implement incremental recompilation.

I don't think it would ever be a good idea to tie down the
implementation details in a way that would tie the hands of
compiler implementors.  So, if you think your proposed extension
would require this, then I suggest you rethink it, and either
find a way of acheiving it without this drawback, or ditch
at least those parts of the proposal that would require it.

> As with so many questions, Type Classes Are The Answer (TM).

No, type classes are not "The Answer (TM)".  Type classes are not a
silver bullet, and I don't think they'd help in this case. 
Why not just use a simple abstract data type?

> For the time being, I would propose to use the term type
> for the initial transformations (which work like term_expansion), and
> hlds terms for the others.

There's another type, defined in compiler/prog_data.m, that would
also be suitable.

> Formally specifying this, or even just documenting it clearly, will be
> quite a lot of work.  I don't want to do it if such an extension
> wouldn't be incorporated into Mercury anyway.  So it seems to me at
> this stage the questions are:
> 
>     1.  Should the ability to transform Mercury programs be part of
> 	the language?

Mercury already has this ability -- for proof-by-example, see the Mercury
compiler.  What you mean is "Should the Mercury language or standard
library have special support for transforming Mercury programs?".  In
fact even this is already true: see the modules term, varset, and
term_io in the Mercury standard library.  So this question boils down
to "Should the Mercury language or standard library have any _more_
special support for transforming Mercury programs than it already
has?".

Well, first let me say that I don't see any need to extend the
language, as opposed to the libraries, to provide such support; for
writing efficient interpreters, we need to implement unique modes
properly and we need a uniq_store data type (a destructive version of
the current `store' data type), but program transformation is the sort
of task that is already ideal for Mercury as it stands.

In general I'd look quite favourably on proposals for improving the
current library support for writing programs that transforming Mercury
code, particularly if they were "self-funded" (i.e. the proposer was
volunteering to do the work).

I'm not sure whether they should be part of the _standard_ library
as such.  Depending on the complexity and difficulty of implementation,
it might be a bit much of a burden on implementors to _require_ them,
and this might discourage people from writing new Mercury implementations.
I think it would be best to make them a standardized but optional
component, documented in the Mercury Library Reference Manual,
but in an Appendix -- a bit like the "special needs" annexes in the Ada
programming language standard, which provide support for things like
distribution.  Of course if they are not difficult to implement then
every implementor will implement them pretty soon anyway. 
And since they're probably going to be written in Mercury, making
the source code freely available would be one simple way of
guaranteeing that every potential future Mercury implementation
would support them.

>     2.  Should it be possible for users to write code that involves
> 	source code transformation in Standard Mercury, or should this
> 	be outside the language?

Here I assume you're talking about writing code that gets transformed --
presumably into some core language that the compiler understands --
not the code that does the transformation.

I'm not so sure about this one.  I think for the time being I'd
rather take a conservative approach and leave it outside the language,
at least until we have had some experience with it.  If it proves
to be widely used then it would make sense to make it part of the
language.

>     3.  Should programs implemented using transformation be portable
> 	between different platforms and between different Mercury
> 	implementations?

Yes!  

>     4.  What's the simplest, cleanest way to extend Mercury to support
> 	this in a way that's convenient for transformation users and
> 	not too painful for transformation implementor, and not too
> 	painful for Mercury language implementors?

Well, I'll leave that one for you to ponder for a while ;-)

> > That's why I feel the methods proposed by Fergus, although a little
> > clumsy, are much better. 
> 
> I'm not really talking about implementation strategies, but about
> language design.  The Mercury compiler can implement it using Fergus's
> approach as far as I'm concerned (though of course this won't work for
> the transformations I'm going to need that have to be performed after
> type, mode, or determinism analysis).

It could work for those transformations, if you did the relatively minor
tweaks needed on the `--dump-hlds' option so that it's output was valid
Mercury.  However this would require more work in step "1." above to
provide Mercury libraries for dealing with type, mode, and determinism
information in Mercury programs.

> > Anybody understands a simple source to source
> > translation using filters. The whole Unix system is built on this concept.
> 
> Not everyone uses Unix.  I wonder how well this would work under
> Windows?  VM/CMS?  MacOS?

It works fine under Windows, in fact almost the entire Unix-style
Mercury development environment has been ported to Windows already.
You're right that some parts of the current Mercury development
environment would be difficult to port to some systems, but
"translation using filters", which is the only thing you need for the
purposes of the present discussion, could be implemented pretty
trivially on any operating system that supports temporary files and
provides a way for a program to invoke other programs.
Since the Mercury standard library already provides these
features, you could in fact implement it in portable Mercury code.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3         |     -- the last words of T. S. Garp.