From: Jurgen Vinju To: Date: Fri, 5 Nov 2004 13:10:02 +0100 Subject: PEM: Ralf Lämmel | Typed Generic Traversals in S'_gamma | 19.07.01 From: pem (PEM moderator) To: pem-noreply Subject: PEM meeting | 19.07.01 | M.279 Precedence: bulk X-url: http://www.cwi.nl/~pem Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Dear colleagues, This week Ralf Lämmel will tell us how to solve the hard and interesting problem of designing a type system for generic tree traversals. This announcement can be found at Typed Generic Traversals in S'_gamma Date: 19.07.01 Time: 10:00 Venue: M.279 Speaker: Ralf Lämmel Title: Typed Generic Traversals in S'_gamma A typed model of strategic rewriting is developed. An innovation is that generic traversals are covered. To this end, we define a rewriting calculus S'_gamma. The calculus offers a few strategy combinators for generic traversals. There is, for example, a combinator to apply a strategy to all children of a given term. This idiom is relevant for generic type-preserving traversals. We also go beyond type-preservation which corresponds to another innovation. There is, for example, a combinator to reduce all the children of a term. To provide a typeful model for generic strategies, one has to identify signature-independent, that is, generic strategy types. To inhabit generic types, we need to add a fundamental combinator to lift a sort-specific strategy s to a generic type gamma. The reduction semantics for this kind of lifting states that is only applied if the type of the term at hand fits, otherwise the strategy fails. This approach dictates that the semantics of strategy application must be type-dependent to a certain extent. Typed strategic rewriting with generic traversals is a simple but expressive model of generic programming. It has applications in program transformation and program analysis. _________________________________________________________________ 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 _________________________________________________________________