[antlr-interest] object oriented compiler implementation

Mark Wright markwright at internode.on.net
Mon Jun 13 07:33:52 PDT 2011


On Fri, 10 Jun 2011 17:43:49 -0500, "Edwards, Waverly" <Waverly.Edwards at genesys.com> wrote:
> This is not directly ANTLR related but have any of you come across a guide,
> tutorial or book (preferably) for implementing an compiler for an object
> oriented language.  I don't mean the compiler is created using an object
> oriented languages, though that would be good.  I mean what goes into
> implementing subclassing, method overriding, hybrid language type safety
> such as objective-c (static and dynamic type) enforcement.  Also things like
> implementing exceptions and polymorphic variables.  I've used them in
> languages but I haven't read how you might go about go about implementing
> them.  I have a few compiler books but interestingly enough, they all deal
> with procedural languages like C or Pascal.  None of them talk about the
> innards of making compilers for object oriented languages.  I do own
> "Language Implementation Patterns", which helped me understand scopes for
> object languages.

Hi Waverly,

There is lots of information using type theory, functional programming,
and proof assistants.  The book to start with using this approach is
free:

http://www.seas.upenn.edu/~cis500/current/sf/html/index.html

The 2 main proof assistants for this sort of stuff are Coq and Isabelle.
There seems to be more tutorial info on Coq.  A useful tool that can generate
some Coq and Isabelle code is Ott:

http://www.cl.cam.ac.uk/~pes20/ott/

The chapter TypeChecking:

http://www.seas.upenn.edu/~cis500/current/sf/html/Typechecking.html

describes how to prove that a Coq fixpoint function for the type checker
is equivalent to the Coq propositions that are more convenient to work
with in the proof assistant.  Ott can generate the propositions, looking
at those can help with writing the fixpoints, and then Haskell or Ocaml
code can be extracted from the fixpoints.  Or you could just look
at the fixpoints as a guide and write the type checker in a functional
programming language

Lots of very useful type theory/Coq videos here:

http://vimeo.com/user5565394/videos/page:1/sort:newest

The Software Foundations book does not cover object orientented languages,
but the theory is required to understand books that do.  There are different
types of subtyping in type theory.

The standard text on type theory does have some discussion on object
oriented languages:

Types and Programming Languages, by Benjamin C. Pierce. MIT Press, 2002.

There are 2 obscure books on type theory and object oriented langauges:

(1) Foundations of Object-Oriented Languages by Kim Bruce

The first half is an easy discussion on object oriented type systems
that you would probably find useful even if you don't use the type theory
approach.

The second half uses type theory, proof sketches, which is useful if
you wanted to use type theory.

(2) A Theory of Objects (Monographs in Computer Science) by Martin Abadi and
Luca Cardelli

its an expensive book, I have not read it.  It develops its own object
calculus which I guess would make it hard to understand this book.

There are other references in the postscript:

http://www.seas.upenn.edu/~cis500/current/sf/html/Postscript.html

If you write the compiler using a functional programming language, then
I think the standard approach is use continuations, that is described
in this book:

Compiling with Continuations by Andrew W. Appel 

and 2 chapters in this book (seems to be more on interpreters than
compilers though):

Essentials of Programming Languages by Daniel P. Friedman and Mitchell Wand

Regards, Mark

> I'm hoping to start with a book that lets you know what to do, what not to
> do and why you don't want to do it that way.  I'd like to start with making
> fresh mistakes versus ones that have been made over and over again.

> Thank you kindly,
> 
> Waverly
> 
> 
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address


More information about the antlr-interest mailing list