[m-rev.] for review: delay partial instantiations pass

[Peter Ross]

On Thu, Jun 21, 2007 at 01:57:26PM +1000, Peter Wang wrote:
> Estimated hours taken: 30
> Branches: main
> 
> Add a post-processing pass directly after mode checking that tries to transform
> procedures to avoid intermediate partially instantiated data structures.  The
> Erlang backend in particular cannot handle partially instantiated data
> structures.
> 
> compiler/delay_partial_inst.m:
> 	New module.
> 
> compiler/check_hlds.m:
> 	Import delay_partial_inst.m
> 
> compiler/modes.m:
> 	Call the delay partial instantiations pass after mode checking succeeds
> 	if it is enabled.
> 
> compiler/options.m:
> 	Add a new internal option `--delay-partial-instantiations', disabled by
> 	default.
> 
> compiler/handle_options.m:
> 	Make Erlang target imply --delay-partial-instantiations.
> 
> compiler/notes/compiler_design.html:
> 	Mention delay_partial_inst.m
> 
> tests/hard_coded/Mercury.options:
> tests/hard_coded/Mmakefile:
> tests/hard_coded/delay_partial_test.exp:
> tests/hard_coded/delay_partial_test.m:
> tests/hard_coded/delay_partial_test2.exp:
> tests/hard_coded/delay_partial_test2.m:
> 	Add test cases for --delay-partial-instantiations.
> 
> compiler/goal_util.m:
> 	Fix a comment.
> 

I think even commented out options haves to be documented in the 
user_guide

> Index: compiler/delay_partial_inst.m
> ===================================================================
> RCS file: compiler/delay_partial_inst.m
> diff -N compiler/delay_partial_inst.m
> --- /dev/null	1 Jan 1970 00:00:00 -0000
> +++ compiler/delay_partial_inst.m	21 Jun 2007 03:55:12 -0000
> @@ -0,0 +1,491 @@
> +%-----------------------------------------------------------------------------%
> +% vim: ft=mercury ts=4 sw=4 et
> +%-----------------------------------------------------------------------------%
> +% Copyright (C) 2007 The University of Melbourne.
> +% This file may only be copied under the terms of the GNU General
> +% Public License - see the file COPYING in the Mercury distribution.
> +%-----------------------------------------------------------------------------%
> +%
> +% File: delay_partial_inst.m.
> +% Author: wangp.
> +%
> +% This module runs just after mode analysis on mode-correct procedures and
> +% tries to transform procedures to avoid intermediate partially instantiated
> +% data structures.  The Erlang backend in particular cannot handle partially
> +% instantiated data structures (we cannot use destructive update to further
> +% instantiate data structures since all values are immutable).
> +%
> +% There are two situations.  An implied mode call, e.g.
> +%
> +%       p(f(_, _))
> +%
> +% looks like this after mode checking:
> +%
> +%       X := f(V_1, V_2),       % partially instantiated
> +%       p(Y),
> +%       X ?= Y
> +%
> +% We transform it to this more obvious sequence which doesn't need the
> +% partially instantiated data structure:
> +%
> +%       p(Y),
> +%       Y ?= f(_, _)
> +%
> +% The other situation is if the user writes code that constructs data
> +% structures with free variables, e.g.
> +%
> +%       :- type t
> +%           --->    t(
> +%                       a :: int,
> +%                       b :: int
> +%                   ).
> +%
> +%       F ^ a = 1,
> +%       F ^ b = 2
> +%
> +% After mode checking we get:
> +%
> +%       V_1 = 1,
> +%       F := t(V_1, V_2),       % ground, free
> +%       V_3 = 2,
> +%       F => t(V_4, V_3)        % ground, ground
> +%
> +% Whereas we would like to see this:
> +%
> +%       V_1 = 1,
> +%       V_2 = 2,
> +%       F := t(V_1, V_2)
> +%
> +%-----------------------------------------------------------------------------%
> +%
> +% ALGORITHM
> +%
> +% The idea is to remove unifications that produce partially instantiated data
> +% structures (as the mode checker can't be counted on to move these), and keep
> +% track of variables which are bound to top-level functors with free arguments.
> +% In place of the unifications we remove, we insert the unifications for the
> +% sub-components which are ground.  Only once the variable is ground, because
> +% all its sub-components are ground, do we construct the top-level data
> +% structure.
> +%
s/do we construct/we construct/

> +% The algorithm makes a single forward pass over each procedure.  When we see

s/we see/we see a/

> +% unification that binds a variable V to a functor f/n with at least one free
> +% argument, we add an entry to the "construction map" and delete the
> +% unification.  The construction map records that V was bound to f/n.  We also
> +% create new "canonical" variables for each of the arguments.
> +%
> +% When we later see a deconstruction unification of V we first unify each
> +% argument in the deconstruction with its corresponding "canonical" variable.
> +% This way we can always use the canonical variables when it comes time to
> +% reconstruct V, so we don't need to keep track of aliases.  If the mode of the
> +% deconstruction unification indicates that V should be ground at end of the
> +% deconstruction, we insert a construction unification using the canonical
> +% variables, in place of the deconstruction, and delete V's entry from the
> +% construction map now.  Otherwise, if V is not ground, we just delete the
> +% deconstruction unification.
> +%
> +% To handle the problem with implied mode calls, we look for complicated
> +% `can_fail' unifications that have V on the left-hand side.  We transform them
> +% as in the example above, i.e. instead of unifying a ground variable G with a
> +% partially instantiated V, we unify G with the functor that V is bound to.
> +%
> +% After transforming all the procedures, we requantify and rerun mode analysis,
> +% which should do the rest.
> +%
> +%-----------------------------------------------------------------------------%
> +

Otherewise looks fine.
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------