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?

  • $\begingroup$ A very interesting question. $\endgroup$ Sep 15, 2010 at 8:26
  • $\begingroup$ Did you really mean to link to two trivial variants of the same paper? $\endgroup$ Sep 15, 2010 at 17:09
  • $\begingroup$ A refinement of this question: What advantages & disadvantages are there of extending a programming language by this means, as opposed to with macro technology? $\endgroup$ Sep 16, 2010 at 15:50

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.