3 ms·

ASTs are trees of nodes. At each level, a node will typically be one out of a range of choices. In OO languages this turns into a class hierarchy of nodes, and

ASTs are trees of nodes. At each level, a node will typically be one out of a range of choices. In OO languages this turns into a class hierarchy of nodes, and you'd use the visitor pattern to manipulate them. This approach is awful: it generates large amount of boilerplate code in your program, which, if you're not careful, becomes so large that it obscures the actual logic. Functional languages provide a better abstraction, in the form of discriminated unions for data structures, and pattern matching in place of the visitor pattern. I recommend one of the ML family of languages: this is likely to be OCaml, Haskell or F#. I recommend Andrew W Appel's books on "Modern Compiler Implementation": he wrote three books, aimed at Java, C and ML, and the ML book is wonderfully clear.

rch 16y ago
Thanks for the excellent answer, and I am certainly considering Haskell (even though I didn't mention it). I'll grab the book as well. I'd still like to make the best case for the AST side though, since my first goal is to compare the two approaches directly. I'd hate to relay what you've listed to a bunch of Perl programmers just to have someone stand up and ask about Lua0x, or some such. It might be worth noting that this project is only on the table because the Python generator just plain works... Anyway, thanks again.
- GregBuchholz 16y ago
  You'll also want to investigate Prolog. That's the grandfather of pattern-matching tree-manipulation languages. Also, it is dynamically typed if that floats your boat more than Haskell or ML. ML always forces you to deal with incomplete patterns, but you need to specifically ask your Haskell compiler to warn you about incomplete patterns. It is hard to beat Prolog for quickly whipping up prototype language interpreters. Besides pattern matching, there are easy to use symbols (just start a word with a lower case letter), declarative semantics, definite clause grammars (for parsing), user definable infix, prefix, and postfix operators, etc
  - rch 16y ago
    Thanks very much! That is exactly the kind of answer I was looking for.

rch 16y ago

Thanks for the excellent answer, and I am certainly considering Haskell (even though I didn't mention it). I'll grab the book as well. I'd still like to make the best case for the AST side though, since my first goal is to compare the two approaches directly. I'd hate to relay what you've listed to a bunch of Perl programmers just to have someone stand up and ask about Lua0x, or some such. It might be worth noting that this project is only on the table because the Python generator just plain works... Anyway, thanks again.

GregBuchholz 16y ago
You'll also want to investigate Prolog. That's the grandfather of pattern-matching tree-manipulation languages. Also, it is dynamically typed if that floats your boat more than Haskell or ML. ML always forces you to deal with incomplete patterns, but you need to specifically ask your Haskell compiler to warn you about incomplete patterns. It is hard to beat Prolog for quickly whipping up prototype language interpreters. Besides pattern matching, there are easy to use symbols (just start a word with a lower case letter), declarative semantics, definite clause grammars (for parsing), user definable infix, prefix, and postfix operators, etc
- rch 16y ago
  Thanks very much! That is exactly the kind of answer I was looking for.