Computer Science – Programming Languages
Scientific paper
2002-05-14
Computer Science
Programming Languages
85 pages, submitted for publication to the Journal of Logic and Algebraic Programming
Scientific paper
A typed model of strategic term rewriting is developed. The key innovation is that generic traversal is covered. To this end, we define a typed rewriting calculus S'_{gamma}. The calculus employs a many-sorted type system extended by designated generic strategy types gamma. We consider two generic strategy types, namely the types of type-preserving and type-unifying strategies. S'_{gamma} offers traversal combinators to construct traversals or schemes thereof from many-sorted and generic strategies. The traversal combinators model different forms of one-step traversal, that is, they process the immediate subterms of a given term without anticipating any scheme of recursion into terms. To inhabit generic types, we need to add a fundamental combinator to lift a many-sorted strategy $s$ to a generic type gamma. This step is called strategy extension. The semantics of the corresponding combinator states that s is only applied if the type of the term at hand fits, otherwise the extended strategy fails. This approach dictates that the semantics of strategy application must be type-dependent to a certain extent. Typed strategic term rewriting with coverage of generic term traversal is a simple but expressive model of generic programming. It has applications in program transformation and program analysis.
No associations
LandOfFree
Typed Generic Traversal With Term Rewriting Strategies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Typed Generic Traversal With Term Rewriting Strategies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Typed Generic Traversal With Term Rewriting Strategies will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-652792