From: Jurgen Vinju
To:
Date: Fri, 5 Nov 2004 13:09:50 +0100
Subject: PEM: Arie van Deursen | Implementing Origin Tracking by Specification Transformations | 22.05.97

 
From: pem (PEM moderator)
To: pem-noreply
Subject: PEM meeting | 22.05.97 | F013, UvA WINS 
Precedence: bulk
X-url: http://www.cwi.nl/~pem
Mime-Version: 1.0
Content-Type: text/plain;
        charset="iso-8859-1"

   This announcement can be found at <http://www.cwi.nl/~pem>

       Implementing Origin Tracking by Specification Transformations

   Date:    22.05.97
   Time:    10:00
   Venue:   F013, UvA WINS
   Speaker: Arie van Deursen
   Title:   Implementing Origin Tracking by Specification Transformations

   Origin  tracking is a technique for explaining term rewriting results:
   subterms  in  the  normal  form  are automatically related to relevant
   subterms  in  the  initial term. We discuss a recent implementation of
   origin  tracking  based on transforming a specification in a series of
   steps:
    1. Map   mix-fix   term   rewriting  system  (ASF+SDF)  to  a  prefix
       applicative representation (AsFix);
    2. Map the many-sorted specification to a single sorted equivalent;
    3. Eliminate non-linear rules by adding join conditions;
    4. Extend   all   function   symbols   with  an  extra  argument  for
       representing annotations, covering
         1. the signature,
         2. the  terms used in the equations, which should obtain a fresh
            variable at the annotation position, and
         3. join  conditions,  which  should wrap the terms to be equated
            with a strip function eliminating the annotation argument.
    5. Fill  the  annotation positions in the right-hand sides with terms
       building up the origin information --- see below;
    6. Map the resulting specification to a format executable by existing
       rewriting tools (the ASF+SDF Meta-Environment).

   For origin tracking purposes, the contents of the annotations are sets
   of  labels.  A  term  is given an initial labeling, where each symbols
   gets  a  unique  label.  The  propagation  of  these  origin labels is
   determined  by the way in which the specification transformation fills
   the  annotation  attributes  in  the  right-hand  sides of the rewrite
   rules. For this a series of heuristics is used, based on, e.g., common
   subterms between right and left-hand sides, the syntax-directed nature
   of  the  specification,  common  symbols,  and  several others. If all
   annotation  positions  occurring  in right hand sides obtain the empty
   set  of  labels,  the  origin  relation  is equivalent to the standard
   descendants relation.

   In our talk we cover
    1. a  more  detailed  description of the steps and origin propagation
       rules involved;
    2. correctness criteria;
    3. a discussion of the actual implementation; and
    4. applications in the area of software renovation.
     _________________________________________________________________

   The  programming environment meetings are a forum for the presentation
   and  discussion  of  new  ideas,  ongoing and finished work. A typical
   meeting  addresses  a subject in the area of programming environments,
   program  generation, algebraic specification, term rewriting, parsing,
   etc.  A presentation ideally takes between 45 and 90 minutes. Meetings
   taking  longer  than 45 minutes are interrupted by a coffeebreak. Most
   Thursdays,  a  meeting is held which starts at 10:00 am. in one of the
   rooms at CWI/WINS. Exceptionally, dates or times may change.

   The    program    of    the    meetings    is    available   on   WWW:
   http://www.cwi.nl/~pem
     _________________________________________________________________