[m-dev.] Partial evaluation

[Fergus Henderson]

On 23-Oct-2000, Ralph Becket <rbeck at microsoft.com> wrote:
> How does one set about finding out what sorts of constant expressions
> get evaluated at compile time or `just once' at run time?

Well, in general that will be implementation-dependent.

> One assumes
> that constant integer and float arithmetic expressions are pre-computed
> by the compiler.

Yes, the Mercury front-end does those optimizations.
(See const_prop.m in the compiler source code.)

> What about other things?

Function and predicate calls will be inlined when the compiler thinks
it is appropriate.  By default it will inline procedures whose bodies
are "small" and which are not recursive.  You can use `pragma inline'
to encourage the compiler to inline things if its default inlining
heuristics are too conservative.  Note that there is a limit on how
much the compiler will inline, even if you use `pragma inline', so you
may also need to set the `--inline-vars-threshold' option to a higher
value (the default is 100) to ensure things get fully inlined.

Deforestation optimization also does some computation at compile time.
For example, if you have a recursive procedure which does a case
analysis on the arguments, e.g.

	:- func sum(list(int)) = int.
	sum([]) = 0.
	sum([X|Xs]) = X + foo(Xs).

and there is a call to that procedure with known arguments, e.g.

	:- func bar = int.
	bar = sum([1,2,3,4,5,6]).

then it will get evaluated at compile time.  Again, there are some
limits on the deforestation optimization, so if you need this to apply
to complicated goals then you may need to set
`--deforestation-vars-threshold' and/or `--deforestation-depth-limit'
to higher values (the defaults are 100 and 4 respectively).

Constant ground terms -- terms formed using only constructors, not
function calls or predicate calls, unless they are inlined -- will be
allocated in read-only memory at compile/link-time, rather than using
dynamic heap allocation at run-time, at least if you're not making use
of unique modes.  However, this optimization is not supported for the
.NET back-end, due to lack of suitable constructs in the target
language.  (For the .NET back-end, we could allocate such terms once
at program start-up, but we haven't gotten around to implementing that
yet.)  Also, currently we don't do this optimization for certain
types such as arrays, since the code which allocates them is a
function which calls some C code, rather than a constructor.

> For example, at the moment I'm having trouble getting the fact table
> stuff to work (I think it's a bug - I've sent in a report).  I have
> a largish set of integer pairs (ooh, at least 450 of them) that I wish 
> to do fast lookups on:
> 
> :- pred edge(int::in, int::in) is semidet.
> edge(1, 2).
> edge(1, 7).
> edge(1, 28).
> ...
> 
> This approach takes *forever* to compile and the compiler runs out
> of memory in the debugging grades.
> 
> I've been considering recasting this as an array of arrays:
> 
> edge(X, Y) :- binary_search(lookup(edges, X - 1), Y) = yes(_).
> 
> :- func edges = array(array(int)).
> edges = array([
> /* row 1 */ array([...]),
> /* row 2 */ array([...]),
> ...
> ]).
> 
> but I have a sneaky suspicion that this would be the worst
> possible solution at the moment.

Right, the array would be allocated at each call to edges.
Currently we don't support static allocation of arrays.

> It just occurred to me that
> pragma memoing edges/0 might do the trick.

Yes, that sounds like a good idea.  This would ensure that the
array is allocated only once, the first time that edges/0 is called.
There would be a small overhead of a check for each call to edges/0
to see if the array had already been allocated, but this would be
small in comparison to the cost of the binary_search anyway.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------