Implementing Abstract Binding Trees (in Scala, ...)
While this might grow into more (say, a usable library), currently this is a playground for me to learn about Abstract Binding Trees.
I started off from the code in http://semantic-domain.blogspot.de/2015/03/abstract-binding-trees.html.
Scala-specific goodies:
Lam("x", Var("x"))
instead of the underlyingTermInt(Set(),_Tm(_Lam(TermInt(Set(),__Abs(x,TermInt(Set(x),_Var(x)))))))
..toString
, and calls for anThere are many possible TODOs:
Usually, when implementing languages with binding, you have lots of language-specific boilerplate, of size proportional to the size of the language's grammar and to the number of languages. This becomes worse when a project contains multiple languages with binding.
Abstract Binding Trees promise to minimize the language-specific overhead; in particular, one needs only to take the language's syntax, remove binding information, turn the algebraic data types into a pattern functor and implement an instance of Foldable for this functor; the latter step is mechanical enough that it can even be automated (and it is in many languages).