RE: How to Design (Declarative) Programming Languages

["Anton van Straaten" <address@hidden>]

Steven Jenkins wrote:
> I have a friend who is struggling to develop a DSL, and I've been giving
> him advice.  However, I'm getting a bit tired of basically teaching him
> how to design a language, so I started to point him to Essentials of
> Programming Languages.
>
> After reviewing the TOC, though, I'm not convinced it's the right book
> to hand him.  Are there any recommendations as for a reference for
> designing a language?  I'd leaning toward Watt's Programming Language
> Syntax and Semantics, except that he's designing a declarative language,
> so perhaps Watt's Concepts and Paradigms book would be a better choice?

EOPL may not be such a bad fit.  You don't mention what language your friend
is planning to use to build this DSL, but I would definitely advise him to
use Scheme: building languages is one of the things it does best.  Even if
there's some reason that Scheme can't be used for the final implementation,
for prototyping languages, its only serious competition in this area is
other Lisp family languages.

There are some big advantages of using Lisp family languages for this
purpose, for example:

(a) you don't have worry about the surface syntax, at least until you've got
the more important semantic stuff nailed down;
(b) you have macros to help you very quickly prototype & build the language
you need;
(c) you learn important things about language semantics when learning and
working with Scheme;
(d) you avoid spending time dealing with low-level details of language
implementation;
(e) expanding on the prior point, it's not unusual to find that the language
you need is actually a very thin layer on top of Scheme and you can be done
much quicker than you expected, by embedding the language in Scheme and
taking advantage of its powerful semantic core.

One reference that covers the subject of DSLs in Lisp (not Scheme) is Paul
Graham's "On Lisp"[1].  For more specific coverage of how to build Lisp-like
languages (not DSLs particularly) using Scheme, Queinnec's Lisp in Small
Pieces[3] is very thorough, covering "11 interpreters and two compilers".

Re the declarative aspect, depending on the details, you may find there are
already similar languages implemented in Scheme or other Lisps.  For
example, Schelog[2] is a Prolog embedded in Scheme, and there are plenty of
examples of constraint-based or dataflow languages floating around.  If you
provide some more info about the kind of language being developed, perhaps
some more specific examples can be suggested.

Anton

[1] http://www.paulgraham.com/onlisp.html
[2] http://www.ccs.neu.edu/home/dorai/schelog/schelog.html
[3]
http://search.barnesandnoble.com/booksearch/isbnInquiry.asp?isbn=0521562473