Gradually typing strategies

J. Smits, Eelco Visser

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Citation (Scopus)
39 Downloads (Pure)


The Stratego language supports program transformation by means of term rewriting with programmable rewriting strategies. Stratego's traversal primitives support concise definition of generic tree traversals. Stratego is a dynamically typed language because its features cannot be captured fully by a static type system. While dynamic typing makes for a flexible programming model, it also leads to unintended type errors, code that is harder to maintain, and missed opportunities for optimization. In this paper, we introduce a gradual type system for Stratego that combines the flexibility of dynamically typed generic programming, where needed, with the safety of statically declared and enforced types, where possible. To make sure that statically typed code cannot go wrong, all access to statically typed code from dynamically typed code is protected by dynamic type checks (casts). The type system is backwards compatible such that types can be introduced incrementally to existing Stratego programs. We formally define a type system for Core Gradual Stratego, discuss its implementation in a new type checker for Stratego, and present an evaluation of its impact on Stratego programs.
Original languageEnglish
Title of host publicationSLE 2020: Proceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering
Place of PublicationNew York, NY, United States
PublisherAssociation for Computing Machinery (ACM)
Number of pages15
ISBN (Electronic)9781450381765
Publication statusPublished - 2020


  • generic programming
  • gradual types
  • strategy
  • type preserving

Cite this