News Archives

Higher-Order Transformation and the Distributed Data Problem

February 24, 2004

Date: Tuesday, February 24th, 2004
Time: 11am-12:15pm
Location: Woodward 149

Victor Winter, <vwinter@mail.unomaha.edu>
Computer Science Department,University of Nebraska at Omaha

Abstract: The control mechanisms offered by strategic programming have been successfully used to address a variety of problems relating to confluence and termination. However, the application of strategic programming to problems of increasing complexity has raised another issue, namely how auxiliary data fits within a strategic framework. The distributed data problem characterizes the problem posed by auxiliary data. This problem arises from a discord between the semantic association of terms within a specification and the structural association of terms resulting from the term language definition. My research is based on the premise that higher-order rewriting provides a mechanism for dealing with auxiliary data conforming to the tenets of rewriting. In a higher-order framework, the use of auxiliary data is expressed as a rule. Instantiation of such rules can be done using standard (albeit higher-order) mechanisms controlling rule application (e.g., traversal). Typically, a traversal-driven application of a higher-order rule will result in a number of instantiations. If left unstructured, these instantiations can be collectively seen as constituting a rule base whose creation takes place dynamically. However, such rule bases again encounter difficulties with respect to confluence and termination. In order to address this concern the notion of strategy construction is lifted to the higher-order as well. That is, instantiations result in rule bases that are structured to form strategies. Nevertheless, in many cases, simply lifting first-order control mechanisms to the higher-order does not permit the construction of strategies that are sufficiently refined. This difficulty is alleviated though the introduction of the transient combinator. The interplay between transients and more traditional control mechanisms enables a variety of instances of the distributed data problem to be elegantly solved in a higher-order setting. These ideas are formalized in a higher-order strategic programming language called TL. Bio Victor Winter is an assistant professor in the Computer Science department at the University of Nebraska at Omaha. He received his Ph.D. in Computer Science from the University of New Mexico in 1994. From 1995--2001 Dr. Winter worked at Sandia National Laboratories where his research efforts focused on high-assurance software development.