Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Stratego is a programming transformation language/Rewriting DSL.
Anthony Sloane has done some work doing an implementation that runs on Scala.
What are the theoretical limits of Stratego as a functional language? (regardless of implementation). Could one write an applicative order ycombinator in Stratego?
I'll have a go at the answer, though I do not have a concrete program for you to try. In one Eelco Visser blog entry you can see a screen shot containing essentially the lambda calculus encoded in Stratego (I'm sure this code is available elsewhere). He presents an interpreter for the lambda calculus in Stratego. Presumably, this is sufficient to show that Stratego is Turing-complete.
If you are interested in a more specific notion of expressiveness, then I suggest that you rephrase your question.
In terms of practical usage, I found Stratego's main limitation that it operated over only one data structure, namely, the tree being transformed. Using other data structures such as a table of symbols was unnatural (at least in Stratego from 5+ years ago). Even though Stratego is ideal for transformations on a single tree, performing operations on two trees simultaneously is not easy.
