Advanced

Interactive data representation migration: exploiting program dependence to aid program transformation

Narasimhan, Krishna ; Reichenbach, Christoph LU and Lawall, Julia (2017) p.47-58
Abstract
Data representation migration is a program transformation that involves changing the type of a particular data structure, and then updating all of the operations that somehow depend on that data structure according to the new type. Changing the data representation can provide benefits such as improving efficiency and improving the quality of the computed results. Performing such a transformation is challenging, because it requires applying data-type specific changes to code fragments that may be widely scattered throughout the source code, connected by dataflow dependencies.
Refactoring systems are typically sensitive to dataflow dependencies, but are not programmable with respect to the features of particular data... (More)
Data representation migration is a program transformation that involves changing the type of a particular data structure, and then updating all of the operations that somehow depend on that data structure according to the new type. Changing the data representation can provide benefits such as improving efficiency and improving the quality of the computed results. Performing such a transformation is challenging, because it requires applying data-type specific changes to code fragments that may be widely scattered throughout the source code, connected by dataflow dependencies.
Refactoring systems are typically sensitive to dataflow dependencies, but are not programmable with respect to the features of particular data types. Existing program transformation languages provide the needed flexibility, but do not concisely support reasoning about dataflow dependencies.
To address the needs of data representation migration, we propose a new approach to program transformation that relies on a notion of semantic dependency: every transformation step propagates the transformation process onward to code that somehow depends on the transformed code. Our approach provides a declarative transformation-specification language, for expressing type-specific transformation rules. We further provide scoped rules, a mechanism for guiding rule application, and tags, a device for simple program analysis within our framework, to enable more powerful program transformations.
We have implemented a prototype transformation system based on these ideas for C and C++ code and evaluate it against three example specifications, including vectorization, transformation of integers to big integers, and transformation of array-of-structures data types to structure-of-arrays format. Our evaluation shows that our approach can improve program performance and the precision of the computed results, and that it scales to programs of up to 3700 lines. (Less)
Please use this url to cite or link to this publication:
author
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
PEPM 2017 Proceedings of the 2017 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation
pages
47 - 58
publisher
ACM
external identifiers
  • scopus:85010445019
ISBN
978-1-4503-4721-1
DOI
10.1145/3018882.3018890
language
English
LU publication?
no
id
6dbdcc38-7fe4-4ad8-81f1-f23ad5efb9b4
date added to LUP
2017-11-07 17:08:58
date last changed
2019-02-20 11:07:34
@inproceedings{6dbdcc38-7fe4-4ad8-81f1-f23ad5efb9b4,
  abstract     = {Data representation migration is a program transformation that involves  changing  the  type  of  a  particular  data  structure,  and  then updating all of the operations that somehow depend on that data structure according to the new type. Changing the data representation can provide benefits such as improving efficiency and improving the quality of the computed results. Performing such a transformation  is  challenging,  because  it  requires  applying  data-type specific changes to code fragments that may be widely scattered throughout the source code, connected by dataflow dependencies.<br/>Refactoring systems are typically sensitive to dataflow dependencies, but are not programmable with respect to the features of particular data types. Existing program transformation languages provide the needed flexibility, but do not concisely support reasoning about dataflow dependencies.<br/>To address the needs of data representation migration, we propose  a  new  approach  to  program  transformation  that  relies  on  a notion of semantic dependency: every transformation step propagates the transformation process onward to code that somehow depends on the transformed code. Our approach provides a declarative  transformation-specification  language,  for  expressing  type-specific  transformation  rules.  We  further  provide  scoped  rules,  a mechanism for guiding rule application, and tags, a device for simple program analysis within our framework, to enable more powerful program transformations.<br/>We have implemented a prototype transformation system based on these ideas for C and C++ code and evaluate it against three example specifications, including vectorization, transformation of integers to big integers, and transformation of array-of-structures data types to structure-of-arrays format. Our evaluation shows that our approach can improve program performance and the precision of the computed results, and that it scales to programs of up to 3700 lines.},
  author       = {Narasimhan, Krishna and Reichenbach, Christoph and Lawall, Julia},
  booktitle    = {PEPM 2017 Proceedings of the 2017 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation },
  isbn         = {978-1-4503-4721-1},
  language     = {eng},
  pages        = {47--58},
  publisher    = {ACM},
  title        = {Interactive data representation migration: exploiting program dependence to aid program transformation},
  url          = {http://dx.doi.org/10.1145/3018882.3018890},
  doi          = {10.1145/3018882.3018890},
  year         = {2017},
}