[wheels]

Even not as a real lisp guy that's one of the things that I appreciate about lisp and the only time that I've done anything particularly powerful with it: the fact that it's basically a parse tree makes it really interesting for genetic programming.

[gruseom]

It seems that the fact that Lisp is a parse tree is what makes it a limiting case. That is, if there's only one canonical structure for representing programs, and Lisp makes it explicit, then any other language that makes it explicit is going to be isomorphic to Lisp.

I'd like to know, though: is that true? Is an abstract syntax tree the only good way to represent programs as data? Has any other expressive way to do this been invented, or do programs always boil down to an AST after the syntax has been stripped away?

I say "expressive" because I can think of at least one other code-as-data representation: binary. But that isn't suitable for programming. If there is another representation that is suitable, but isn't isomorphic to a parse tree, then presumably one could derive from it an analog to Lisp that doesn't simply reduce to Lisp. Until then, though, I think the point that PG made semi-jokingly in the essay, that any language as powerful as Lisp will be a variant of Lisp, has to hold true.

Some day I'd like to research this question (or better, someone on HN could just tell me the answer). If other meaningful representations are possible, surely some must have been invented by now. And if they aren't, then the AST is a considerably more remarkable discovery than people realize.

[wheels]

I don't think that a parse tree is intrinsic -- it's just something that maps well to the languages that we actually use: of course you could translate everything to a turing machine's tape, but that wouldn't be particularly useful.

What would really interest me would be exploring that if human logic fundamentally reduces to a parse tree because of something to do with the language faculty of the mind, and the programming languages that we create tend towards that just because programming languages are built out of the same logical faculty.

[gruseom]

Yeah, that's the point. Other representations are possible (binary), but only one has proven suitable for programming. This is presumably because of the way the human mind works. It would be remarkable if it were the only good representation for this. It would also be the reason why Lisp is the limiting case among programming languages, at least when it comes to metaprogramming. But I repeat myself :)

[jacquesm]

> Has any other expressive way to do this been invented, or do programs always boil down to an AST after the syntax has been stripped away?

That is actually an excellent question.

[gruseom]

I was thinking Rebol might be a good place to look.

http://news.ycombinator.com/item?id=780853