[mercury-users] More on monads

[Fergus Henderson]

On 13-Sep-1998, Fergus Henderson <fjh at cs.mu.OZ.AU> wrote:
> On 12-Sep-1998, Ralph Becket <rwab1 at cam.sri.com> wrote:
> > BUT, the point of this note re: Mercury is that, while I believe the
> > compiler can unpack all the higher order stuff and simplify 90% of all
> > the unused machinery away from the computation, it seems to me that
> > there is a lot of unpacking of dead monad objects only to be followed
> > by direct repackaging with a new `value' - this isn't going to be
> > terribly efficient without compile-time garbage collection.  Am I
> > right about this?
> 
> If the monad type has only one functor with only one argument, e.g.
> 
> 	:- type monad(T) ---> mk_monad(whatever(T)).
> 
> then the mk_monad/1 constructor is like a `newtype' constructor in Haskell --
> it will get optimized away entirely.
> 
> But otherwise, e.g. for the maybe(T) monad, you are right that
> compile-time garbage collection is needed for maximal efficiency.

Actually I misspoke on that one.  The existing Mercury compiler
is capable of doing a reasonably good job on code like that,
because it optimizes away construction of variables which are
only used in an immediately following deconstruction.
This optimization won't remove all the constructions,
but it can remove most of them.

In particular, if you have a bunch of procedure calls
to say p1, p2, and p3

	:- type t ---> f(int, int).

	:- pred p(t::in, t::out) is det.
	p(X, W) :-
		p1(X, Y),
		p2(Y, Z),
		p3(Z, W).
	
where each of p1-p3 does a deconstruction and then a construction, e.g.

	p1(X, Y) :-
		X = f(A1, B1),		% deconstruct X
		q(B1, B2),		% do something
		Y = f(A1, B2).		% construct Y

then after inlining you have

	deconstruct X	% \
	do something	%  p1
	construct Y	% /
	deconstruct Y	% \
	do something	%  p2
	construct Z	% /
	deconstruct Z	% \
	do something	%  p3
	construct W	% /

Compile-time garbage collection could avoid all the constructions by
reusing existing storage.  The optimization that the existing compiler
does is to avoid constructions if their only use is in an immediately
following deconstruction.  This won't avoid the construction of `W' in
this example, but it will avoid the construction of `Y' and `Z'.

-- 
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.