Previous Up Next

Construction of one-pass relations module
(onepassrel)

Introduction

In the generation process a number of relations are calculated. These relations are used to determine whether in a certain context an attribute occurrence is implemented as stored in the representation of the abstract program tree, or as a parameter of a tree walking and attribute evaluating procedure. This is not very simple, because the set of (attribute,element) pairs used to represent the dependency graph, differs from the (attribute,element) pairs that are represented in the abstract program tree. And also because we have to take in account the interface attributes.

1 Formal description

We first define the formal relation "one pass attr of" using the set of (attribute,element) pairs "one pass attr elem pairs", as defined in [3.3].

This formal relation is represented by the global variable onepass attr, which is initialized by the procedure gen program [genera 1].

An attribute could only be implemented as a one pass attribute, if all the (attribute,element) pairs where this attribute is projected on, have the one pass property. We introduce the formal relation "all one pass attr of", that tells us, which attributes have the one pass property with all elements under a certain class, according to the relation "one pass attr of". We can define this formal relation by:

This formal relation is represented by the global variable allone pass.

With this relation we can define the relation which gives us those attributes that do not need to be stored in the representation of the abstract program tree. This relation is defined in the following way:

This formal relation is stored in the global variable impattr at.

Because the attributes defined by the above formal relation have to be represented by parameters, we have to know which attributes under a given class have to be implemented as parameters. The following formal relation is used for this:

This formal relation is stored in the global variable under impl one pass.

The formal relation "imported attr at" is defined by:

This formal relation is stored in the global variable impattr at.

2 Implementation

The procedure makeone pass relations calculates the relations that are derived from the formal relation "one pass attr of". The algorithm to calculates has three steps. Each step is implemented by a separate local procedures.

In the first step the formal relation "all one pass attr of" is calculated. This is done by the procedure make all one pass relation. This procedure makes use of a local procedure make from, and a local variable not done to traverse the whole class hierarchy in an efficient way.

In the second step the formal relations "implemented one pass attr at" and "imported attr at" are calculated, by the procedure make imp attr at and impl one {pass relation}.

In the third step the formal relation "under impl one pass" is calculated, which is done by the procedure make under impl one pass{ relation}. This procedure makes use of a local procedure make from, and a local variable not done to traverse the whole class hierarchy in an efficient way.

3 Interface

This module uses declarations from the following modules:

3.1 Exported variables

This module exports the following variables

3.2 Exported procedure

This module exports the following procedure

4 Listing


(*      MODULE : MAKE ONE PASS RELATIONS                                      *)

[ENVIRONMENT ('onepassrel.pen'),
 INHERIT     ('[-.screen]screen.pen',
              'definitions.pen',
              'bintree.pen')]MODULE onepassrel(output);

(*      VARIABLE DECLARATION                                                  *)

VAR
(* defined in GENERA, shared with this program and GASS, are :                *)
  one_pass_attr ,                (* the one pass attributes                   *)
                                 (* for one_pass_attr(elem_nr)                *)
  allone_pass   ,                (* for all_one_pass(elem_nr)                 *)
  impattr_at    ,                (* for imp_attr_at(elem_nr)                  *)
  implone_pass  ,                (* for impl_one_pass(elem_nr)                *)
  under_impl_one_pass : tattr_at_elem; (* for under_impl_one_pass(elem_nr)    *)

4.1 Procedure

  PROCEDURE makeone_pass_relations;
  (* This procedure generates 4 important relations, that are used to decide  *)
  (* whether an certain attribute, in a certain context is a one pass         *)
  (* attribute. This process is done in 3 steps as described in the following *)
  (* procedures :                                                             *)
  (* STEP 1 :                                                                 *)

    PROCEDURE make_all_one_pass_relation;
    (* This procedure makes the relation all_one_pass, formal described by :  *)
    (*                                                                        *)
    (*  DF all_one_pass(E)                                                    *)
    (*     = one_pass_attr(E)                                                 *)
    (*       UNION IF   E IN classes                                          *)
    (*             THEN FORALL E' IN classes                                  *)
    (*                  INTERSECTION all_one_pass(E')                         *)
    (*             ELSE EMPTY                                                 *)
    (*             FI                                                         *)
    VAR
      dummy    : attributes;
      not_done : elements;
      with_elem_nr  : integer;

      FUNCTION make_from(this_elem_nr : integer) : attributes;
      (* This procedure makes the relation for element this_elem_nr, and if   *)
      (* needed can call the procedure recursively for all elements in the    *)
      (* clos_class of this element.                                          *)
      VAR
        result : attributes;
        new_nr : integer;
        class  : elements;
      BEGIN
        add_level_info( ' elem : ' + element[this_elem_nr]^.name );
        IF   this_elem_nr IN not_done
        THEN BEGIN
               class  := element[this_elem_nr]^.class_rule;
               IF   class = []
               THEN result := []
               ELSE BEGIN
                      result := [0..nr_of_elem];
                      new_nr := start_nr;
                      REPEAT
                        next_elem(new_nr, class);
                        result := result * make_from(new_nr)
                      UNTIL class = []
                    END;
             allone_pass[this_elem_nr] := one_pass_attr[this_elem_nr] + result;
             not_done := not_done - [this_elem_nr]
           END;
        make_from := allone_pass[this_elem_nr]
      END;

    BEGIN (* of make_all_one_pass_relation *)
      enter_level('make_all_one_pass');
      not_done := [0..nr_of_elem];
      FOR with_elem_nr := 0 TO nr_of_elem
      DO dummy := make_from(with_elem_nr);
      exit_level
    END;

  (* STEP 2 :                                                                 *)

    PROCEDURE make_imp_attr_at_and_impl_one_{pass_relation};
    (* This procedure makes two relations. The relation imp_attr_at is        *)
    (* described by :                                                         *)
    (*                                                                        *)
    (*  DF imp_attr_at(elem_nr)                                               *)
    (*     =         (all_attr_of(elem_nr) WITHOUT attr_of(elem_nr))          *)
    (*       WITHOUT (        all_one_pass(elem_nr)                           *)
    (*                WITHOUT (      all_input_attr_of(elem_nr)               *)
    (*                         UNION all_output_attr_of(elem_nr)              *)
    (*                        )                                               *)
    (*               )                                                        *)
    (*                                                                        *)
    (* This relation represents the so called imported attributes that are    *)
    (* needed if we find an element of a class in the right hand side of a    *)
    (* tree rule.                                                             *)
    (* This relation impl_one_pass is described by :                          *)
    (*                                                                        *)
    (*  DF impl_one_pass(E)                                                   *)
    (*     = (all_one_pass(E) INTERSECTION attr_of(E))                        *)
    (*       WITHOUT interface_attr_of(E)                                     *)
    (*                                                                        *)
    (* This relation, represented in the variable impl_one_pass indicates all *)
    (* attributes that are chosen not to be stored in the internal static     *)
    (* representation structure, but in the form of dynamic procedure       *)
    (* variables. We recall that interface_attr_of(E) is a subset of          *)
    (* attr_of(E), so that all attributes that are interface attributes shall *)
    (* never be chosen not to be stored in the internal static representation.*)
    VAR
      with_elem_nr : integer;
    BEGIN
      enter_level('make_imp_attr_at_');
      FOR with_elem_nr := 0 TO nr_of_elem
      DO WITH element[with_elem_nr]^
         DO BEGIN
              impattr_at[with_elem_nr]
              :=   (attr[all_gen] - attr[nor_gen])
                 - (allone_pass[with_elem_nr]
                    - (attr[all_in] + attr[all_out]));
              implone_pass[with_elem_nr]
              :=   (allone_pass[with_elem_nr] * attr[nor_gen])
                 - (attr[nor_in] + attr[nor_out])
            END;
      exit_level
    END;

  (* STEP 3 :                                                                 *)

    PROCEDURE make_under_impl_one_pass{_relation};
    (* This procedure makes the relation under_impl_one_pass, described by :  *)
    (*                                                                        *)
    (*  DF under_impl_one_pass(E)                                             *)
    (*     = iml_one_pass(E)                                                  *)
    (*       UNION IF   E IN classes                                          *)
    (*             THEN FORALL E' IN class(E)                                 *)
    (*                  UNION under_impl_one_pass(E)                          *)
    (*             ELSE EMPTY                                                 *)
    (*             FI                                                         *)
    VAR
      dummy    : attributes;
      not_done : elements;
      with_elem_nr  : integer;

      FUNCTION make_from(this_elem_nr : integer) : attributes;
      (* This function returns the value of the relation for this element,    *)
      (* and might call itself recursively for all the elements in the        *)
      (* clos_class of this element.                                          *)
      VAR
        result : attributes;
        new_nr : integer;
        class  : elements;
      BEGIN
        add_level_info(' elem : ' + element[this_elem_nr]^.name);
        IF   this_elem_nr IN not_done
        THEN BEGIN
               class  := element[this_elem_nr]^.class_rule;
               result := implone_pass[this_elem_nr];
               new_nr := start_nr;
               WHILE class <> []
               DO BEGIN
                    next_elem(new_nr, class);
                    result := result + make_from(new_nr)
                  END;
               under_impl_one_pass[this_elem_nr] := result;
               not_done := not_done - [this_elem_nr]
             END;
        make_from := under_impl_one_pass[this_elem_nr]
      END;

    BEGIN (* of make_under_impl_one_pass *)
      enter_level('make_under_impl_one_pass');
      not_done := [0..nr_of_elem];
      FOR with_elem_nr := 0 TO nr_of_elem
      DO dummy := make_from(with_elem_nr);
      exit_level
    END;

  BEGIN (* of makeone_pass_relations *)
    enter_level('makeone_pass_relation');
    make_all_one_pass_relation;
    make_imp_attr_at_and_impl_one_{pass_relation};
    make_under_impl_one_pass{_relation};
    exit_level
  END;


END.


My life as a hacker | My home page