<p>I'll have a go at the answer, though I do not have a concrete program for you to try. In one Eelco Visser <a href="http://blog.eelcovisser.net/index.php?/archives/149-Lambdas-in-Spoofax.html" rel="nofollow">blog entry</a> 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. </p>

<p>If you are interested in a more specific notion of expressiveness, then I suggest that you rephrase your question.</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-15T20:35:51.903Z
2010-09-16T06:56:45.860Z
2010-09-16T06:56:45.860Z
Dave Clarke
<p><a href="http://en.wikipedia.org/wiki/Stratego/XT" rel="nofollow">Stratego</a> is a programming transformation language/Rewriting DSL. </p>

<p>Anthony Sloane has <a href="http://hal.archives-ouvertes.fr/docs/00/35/02/69/PDF/7.pdf" rel="nofollow">done some work</a> doing an <a href="http://www.labri.fr/perso/reveille/DSPD/2008/papers/7.pdf" rel="nofollow">implementation that runs on Scala</a>. </p>

<p>What are the theoretical limits of Stratego as a functional language? (regardless of implementation). Could one write an applicative order ycombinator in Stratego?</p>

CC BY-SA 2.5
2010-09-15T08:26:28.733Z
A very interesting question.
Dave Clarke
CC BY-SA 2.5
2010-09-15T17:09:46.050Z
Did you really mean to link to two trivial variants of the same paper?
Randall Schulz
CC BY-SA 2.5
2010-09-16T15:50:46.273Z
A refinement of this question: What advantages & disadvantages are there of extending a programming language by this means, as opposed to with macro technology?
Charles Stewart
<functional-programming>
What are the theoretical limits of the Stratego Programming Language?
hawkeye
# What are the theoretical limits of the Stratego Programming Language?

(Asked by: username_0 on 2010-09-15)

[Stratego](http://en.wikipedia.org/wiki/Stratego/XT) is a programming transformation language/Rewriting DSL.

Anthony Sloane has [done some work](http://hal.archives-ouvertes.fr/docs/00/35/02/69/PDF/7.pdf) doing an [implementation that runs on Scala](http://www.labri.fr/perso/reveille/DSPD/2008/papers/7.pdf).

What are the theoretical limits of Stratego as a functional language? (regardless of implementation). Could one write an applicative order ycombinator in Stratego?

**Tags:** functional-programming
> **Comments:**
> **username_1**: A very interesting question.  
> **username_2**: Did you really mean to link to two trivial variants of the same paper?  
> **username_3**: A refinement of this question: What advantages & disadvantages are there of extending a programming language by this means, as opposed to with macro technology?  

---

## 1 answers

### Answer by username_1 on 2010-09-15. Score: 6 | Accepted answer

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](http://blog.eelcovisser.net/index.php?/archives/149-Lambdas-in-Spoofax.html) 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.


---

