<p>You can turn every programming language $L$ into a homoiconic language $L_{hom}$ by adding a suitable representation of programs, such as ASTs (abstract syntax trees) or quasi-quoted programs, together with some operations that mediate between $L$ and the representation of $L$-syntax (e.g. evaluation or splicing instructions). The details of this depend on your precise rendering of homoiconicity (e.g. compile-time as in Template Haskell vs run-time as in the MetaML family of languages or Javascript). </p>

<p>One extreme example is the empty language $L^{\emptyset}$ that has no programs. Clearly its  homoiconic variant $L^{\emptyset}_{hom}$ isn't Turing complete. For more interesting examples, you can take any of the usual type theories such as the simply typed $\lambda$-calculus, System F or the Calculus of Constructions. Of course one would have to prove that the homoiconified version of such type-theories doesn't allow us to encode recursion somehow. I doubt that this has been done. Cody's comment below suggests that this might not be possible. </p>

CC BY-SA 3.0
2016-03-23T20:21:31.233Z
I don't believe that the claimed result holds, or at least that "reasonable" definitions are less trivial than expected. For example, imagine that your language contains a `Syntax` type and an `eval` construct that returns the "un-quoted" version of a quoted term, if it is well-typed of type `Syntax -> Syntax`, as well as a `quote` term. Then one can define `loop x = (eval x) x` and finally call `loop (quote loop)`. Connor McBride explains this perfectly here: https://mail.haskell.org/pipermail/haskell-cafe/2003-May/004343.html
cody
CC BY-SA 3.0
2016-03-24T15:44:02.807Z
I'm confused: are you agreeing that the result you claim in your last sentence is false?
cody
CC BY-SA 3.0
2016-03-24T16:12:42.563Z
@cody Sorry, I misunderstood what you meant. I should have re-read the second part of my answer. I've edited it accordingly.
Martin Berger
CC BY-SA 3.0
2014-02-12T13:38:19.127Z
2016-03-24T16:12:18.407Z
2016-03-24T16:12:18.407Z
Martin Berger
<p>Does there exist a programming language which is homoiconic (in the sense that any code can be represented as a data structure, can be altered, and can be run after being altered) but not Turing complete?</p>

<p>For instance, one may avoid "for loops" by preventing data (which could represent code) from being copied.</p>

CC BY-SA 3.0
2016-03-22T14:55:28.753Z
For a more informal discussion of why "homoiconic" isn't a terribly interesting category of languages (and what it often really means: that the tree structure of a language can be observed without complete parsing), see Dave Herman's essay: http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-point/
Paul Stansifer
<pl.programming-languages>
Homoiconic languages which are not Turing complete
Bruno Le Floch
# Homoiconic languages which are not Turing complete

(Asked by: username_0 on 2014-02-12)

Does there exist a programming language which is homoiconic (in the sense that any code can be represented as a data structure, can be altered, and can be run after being altered) but not Turing complete?

For instance, one may avoid "for loops" by preventing data (which could represent code) from being copied.

**Tags:** pl.programming-languages
> **Comments:**
> **username_1**: For a more informal discussion of why "homoiconic" isn't a terribly interesting category of languages (and what it often really means: that the tree structure of a language can be observed without complete parsing), see Dave Herman's essay: http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-point/  

---

## 1 answers

### Answer by username_2 on 2014-02-12. Score: 9 | Accepted answer

You can turn every programming language $L$ into a homoiconic language $L\_{hom}$ by adding a suitable representation of programs, such as ASTs (abstract syntax trees) or quasi-quoted programs, together with some operations that mediate between $L$ and the representation of $L$-syntax (e.g. evaluation or splicing instructions). The details of this depend on your precise rendering of homoiconicity (e.g. compile-time as in Template Haskell vs run-time as in the MetaML family of languages or Javascript).

One extreme example is the empty language $L^{\emptyset}$ that has no programs. Clearly its homoiconic variant $L^{\emptyset}\_{hom}$ isn't Turing complete. For more interesting examples, you can take any of the usual type theories such as the simply typed $\lambda$-calculus, System F or the Calculus of Constructions. Of course one would have to prove that the homoiconified version of such type-theories doesn't allow us to encode recursion somehow. I doubt that this has been done. Cody's comment below suggests that this might not be possible.

> **Comments:**
> **username_3**: I don't believe that the claimed result holds, or at least that "reasonable" definitions are less trivial than expected. For example, imagine that your language contains a `Syntax` type and an `eval` construct that returns the "un-quoted" version of a quoted term, if it is well-typed of type `Syntax -> Syntax`, as well as a `quote` term. Then one can define `loop x = (eval x) x` and finally call `loop (quote loop)`. Connor McBride explains this perfectly here: https://mail.haskell.org/pipermail/haskell-cafe/2003-May/004343.html  
> **username_3**: I'm confused: are you agreeing that the result you claim in your last sentence is false?  
> **username_2**: @cody Sorry, I misunderstood what you meant. I should have re-read the second part of my answer. I've edited it accordingly.  

---

