Of course if you are a believer in higher-order abstract syntax (the idea that one should use constructs such as lambda abstractions as part of your syntax tree), Scheme is a better fit, as ML's type system doesn't allow for such wildly typed syntax trees, nor does it allow data-as-code. (I think HOAS is hogwash, but then I'm a firm believer in well-typed code and against data-as-code.)
Of course, if your AST is more a graph than a tree, you're better with a logic language such as Mercury or Prolog. I've had very good experiences writing compilers and interpreters in Mercury.
But what of actually parsing a program in HOAS? The idea of HOAS is to translate the text "\x -> x + 5" into the expression Lam (\x -> Op("+", Var x, Const 5)). But how does one translate the string "x" into the variable name x short of data-as-code (or a similar meta-facility)?
The best Google turns up for this problem is here: http://books.google.com/books?id=OxeBw-sH4SUC&lpg=PA50&#... which seems to address the problem using a meta-facility of lambda-Prolog.
import scala.util.parsing.combinator.syntactical.StandardTokenParsers
import scala.util.parsing.input._
import scala.util.parsing.syntax._
object HoasTest extends StandardTokenParsers {
lexical.delimiters ++= List("(", ")", "\\", ".", ":", "=", "->", "+", "{", "}", ",", "*")
lexical.reserved ++= List("Bool", "Nat", "true", "false", "if", "then", "else", "succ",
"pred", "iszero", "let", "in", "fst", "snd")
import lexical.NumericLit
import lexical.Identifier
def Term(base: Parser[Term]): Parser[Term] = positioned(
SimpleTerm(base) ~ SimpleTerm(base) ^^ { case fun~arg => Apply(fun,arg) } // should be left-assoc
| SimpleTerm(base) ~ ("+" ~> SimpleTerm(base)) ^^ { case a~b => Plus(a,b) } // should be left-assoc
| SimpleTerm(base)
| failure("illegal start of term"))
def SimpleTerm(base: Parser[Term]): Parser[Term] = positioned(
(("\\" ~> ident <~ ".") into (x => Parser { in =>
def body(arg: Term): ParseResult[Term] = Term(Identifier(x) ^^^ arg | base)(in)
body(new Term {}) match {
case Success(_,rest) => Success(Lambda(x, (arg) => body(arg).get), rest)
case f => f
}
}))
| "(" ~> Term(base) <~ ")"
| base
| failure("illegal start of simple term"))
def BaseTerm: Parser[Term] = positioned(
numericLit ^^ { case n => Num(n.toInt) }
| failure("unrecognized base term"))
abstract class Term extends Positional
case class Num(n: Int) extends Term
case class Plus(a: Term, b: Term) extends Term
case class Lambda(x: String, body: Term=>Term) extends Term {
override def toString = "\\"+x+".("+body(new Term { override def toString = x }).toString+")"
}
case class Apply(fun: Term, arg: Term) extends Term
}:- pred asg_nodes(asg, node).
:- mode asg_nodes(in, out) is nondet.
:- mode asg_nodes(in, in) is semidet.
:- pred asg_edges(asg, node, node).
:- mode asg_edges(in, out, out) is nondet.
:- mode asg_edges(in, in, in) is semidet.
Underlying are traditional sets or what-have-you but you never have to deal with these at high levels of coding. You could then do fancy stuff like defining ancestry as:
:- pred asg_ancestor(asg, node, node).
:- mode asg_ancestor(in, out, out) is nondet.
:- mode asg_ancestor(in, in, in) is semidet.
asg_ancestor(ASG, A, A).
asg_ancestor(ASG, A, B) :- asg_edge(A, C), asg_ancestor(C, B).
Of course you'd want to wrap this stuff up in a typeclass or some such and give them useful names.
Also (unfortunately, IMHO), this talks a lot about speed, which was a big problem in the Pentium 200 days with minimal RAM, cache, etc. Nowadays, any old poorly written, garbage-collected program runs speedy as hell. Seems like lost is the golden days of optimization.