[mercury-users] Native garbage collector for Mercury

[Jonathan Martin]

> Dude, all I can say is your standards are pretty high.  To put this in
> perspective, just think how hard it would be to write a program in C++ which
> could prove the termination of 50% of the routings in a C++ compiler!

Much harder I would have thought.  Termination analysis _is_ more
tractable in a logic programming language than an imperative one
because, at least with a pure language, you "only" have to worry about
recursion.  And Mercury is pure (no side effects at all?).

Now, admittedly some programs are more amenable to termination
analysis than others (usually those where termination depends on data
structure rather than data content).  I guess I'm throwing figures
like 90% around because perhaps I'm underestimating the complexity of
the compiler.  I just don't know how much of it consists of analyses,
say, relying on iterating to fixpoints, for example, (difficult to
analyse) and other more straightforward parsing and code generation
style code (easier to analyse).  Now with the latter, proving
termination of all such code is more than likely achievable.  With the
former, proving termination of any of it would be quite impressive in
itself.  Can anyone give me an idea of how the compiler breaks down
into these two categorys? i.e. a rough "termination depends on data
content":"termination depends on data structure" ratio.

> Let me try again to build a case for why termination analysis is important
> for distributed/agent computing.  Suppose I've got a deductive database on
> my machine which I wish to let the world query.  The queries to this
> database will be simple logic programs.  But I don't want crackers to run
> malicious programs on my computer.  If I simply stipulate that I will only
> accept a database query which I can prove will terminate, I know that 
> crackers can't suck too much CPU power.  Yes, this does restrict the sorts
> of queries which I will accept, but this is a feature, not a bug.

OK.  I agree in principle.  It's just a question of pragmatics, but
with the simple sort of application suggested, I'm sure Mercury would
work just fine as it is.  It's just human nature to want more though...


Jonathan Martin		jcm93r at ecs.soton.ac.uk
----------------------------------------------
Department of Electronics and Computer Science
The Mountbatten Building  Room 3053
University of Southampton   S017 1BJ
----------------------------------------------