In both, the JFP & APLAS paper, the authors note that no fancy type extension are needed for this approach. But in almost every (Haskell) example that is a bit more involved the authors do make use of functional dependencies and / or type families. GADTs are also being used, although *not* in the syntax definition...
Just to dispel the doubts, here is the Haskell98 version of the previously posted code CB.hs (tagless final interpreter for call-by-name, call-by-value and call-by-need lambda-calculus with integers and constants) http://okmij.org/ftp/Haskell/CB98.hs It may appear somewhat less convenient. How less convenient -- well, you decide. The code can be easily re-written in OCaml, which has no typeclasses, type families and other bleeding edge features. Talking about it here is probably not appropriate. (I wonder if someone has ever cross-posted to the Haskell and Caml lists). P.S.
I'm still digesting the "Finally Tagless" approach from Oleg, Jacques and Chen. You probably mean Chung-chieh Shan, whose last name is Shan and the first name is Chung-chieh. http://en.wikipedia.org/wiki/Chinese_name