2009/5/6 Rouan van Dalen :

Hi everyone.

I am designing my own programming language.

I would like to know what is the best way to go about writing my compiler in haskell. What are the tools available in haskell that can help with compiler construction?

I know about Happy. Is that a good tool to use?

The compiler is intended for serious use and I would like it to be very efficient, maybe competing with compilers written in C. It should also be very easy to extend as the languoge grows.

Hi, This seems an interesting project. Can you tell us a bit more about your language (functional, dynamic, lazy, does it support call/cc, ...) ? What about the target language (C, C--, x86 assembly, some virtual machine) ? What about the syntax ? Depending of the kind of answers you might provide, specific directions can probably be given. Also, you say "maybe competing with compilers written in C", do you really talk about compiler performance or about generated code performance ? Once those questions are resolved, you can go to hackage, see a list of packages. http://hackage.haskell.org/packages/archive/pkg-list.html For x86 machine code: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/harpy For LLVM: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/llvm For C: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/language-c Cheers, Thu

On Tue, May 5, 2009 at 11:07 PM, Rouan van Dalen wrote:

Hi everyone.

I am designing my own programming language.

I would like to know what is the best way to go about writing my compiler in haskell. What are the tools available in haskell that can help with compiler construction?

I think GHC itself uses Alex and Happy for tokenizing and parsing respectively. Parsec is a nice parser combinator library. Another tool you could employ is Higher Order Abstract Syntax (more of an idiom), and there are papers about it if you google for them. It's a way of representing the program you want to compile and doing transformations on it.

I know about Happy.  Is that a good tool to use?

My understanding is that GHC uses it. I think they are happy with happy, but maybe a GHC dev could comment.

The compiler is intended for serious use and I would like it to be very efficient, maybe competing with compilers written in C.  It should also be very easy to extend as the languoge grows.

I think one of the biggest slow downs for compilers is the complexity of parsing and the complexity of the compilation. For example, If you pick a grammar that parses efficiently and do less sophisticated analyses involving a single pass and so on it will be fast to compile. The draw back is that the compiled programs may execute more slowly than if you did lots of analysis or optimization. As an example of what not to do, C++ has a notoriously complex to parse grammar along with some other issues that make it a slow compiling language :)

Are there any good books that you can recommend on compiler construction in general and specific to haskell?

I like "Modern Compiler Design" myself: http://www.amazon.com/Modern-Compiler-Design-D-Grune/dp/0471976970 I would also recommend reading the haskell report to get an idea of what a friendly language specification looks like: http://www.haskell.org/onlinereport/ One point of advice I would give is defining your language as an embedded language in Haskell first. You can start with the data type that holds your intermediate representation or abstract syntax. Then you can work on either code generation or evaluation. As you start to settle on your data structures and the language primitives you can begin working on a parser. In a sense, the parser is the last part you need to finish. I've found this approach to be quite accommodating and to also save me a lot of time. If you google for it, there is a fair bit of literature about domain specific and embedded domain specific languages in Haskell. It's quite a good language for prototyping this way. Once you write some code you'll discover that some things are taking too long. In that case, you'll want to learn how to make proper use of the GHC profiler, assuming you use GHC as your haskell compiler. It's quite powerful and by using it correctly you can zoom in on the slow spots and dramatically improve the performance of your compiler. I found this paper to be a nice way to get started: http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf One of the brilliant bits in that paper is that it teaches you to use an existing compiler (gcc) to generate code and then learn how to implement things by example! I highly recommend reading it. It's written about a scheme compiler, but it applies equally well to other languages. Good luck! Jason

2009/5/6 Rouan van Dalen

I know about Happy.  Is that a good tool to use?

Alex and Happy are used in (at least) these two packages:    http://hackage.haskell.org/cgi-bin/hackage-scripts/package/language-python    http://hackage.haskell.org/cgi-bin/hackage-scripts/package/language-c You should be able to find lots of useful code to start with in both of those. You can get good performance out of Alex and Happy. Of course there are more considerations than just performance, and you will get different opinions about those other aspects. I wrote the python parser above and I was quite pleased with Alex and Happy from a usability perspective. LLVM is a nice framework for building the backend of a compiler, and the Haskell bindings are quite useful:    http://hackage.haskell.org/cgi-bin/hackage-scripts/package/llvm The amount of work you have to do depends on your runtime system (GC, threads, exceptions etc). If your language has fairly conventional semantics (a typical imperative language) then you can reuse a lot of the existing infrastructure that LLVM provides.

On another note, how is the operator + implemented in haskell?

It is good to differentiate Haskell "the language specification" from compilers (and other tools) which implement it. The language specification does not say exactly how the primitive operations should be implemented; that is a detail which is up to the compiler writer to decide. GHC's implementation is the best documented, and there are many research papers which describe aspects of it (some outdated). For numerical primitives, you could start by looking at this paper:    "Unboxed values as first class citizens in a non-strict functional language" Peyton Jones and Launchbury.    http://research.microsoft.com/en-us/um/people/simonpj/papers/unboxed-values.... Cheers, Bernie.

Dear Rouan, on http://www.cs.uu.nl/wiki/HUT/WebHome you will find a collection of tools which may help you to construct a compiler. As an example you will find a Tiger compiler constructed with the uulib tools and the uuagc attribute grammar system. Tiger is the language used in the book series by Andrew Apple. Not that Tiger is a great language, but the compiler contains an instance of all the things that have to be done when writing a compiler. Once you like these tools you may take a look at the UHC compiler, which actually is a series of compilers, starting from a small language, which is than gradually extended, both with new language concepts and with new aspects, such as code generation, new forms of types etc. Here you will also see that writing a compiler for a language like Haskell is not a small endeavour. You said you wanted to write a compiler in Haskell, but you did not say what language you want to compile? This sounds a bit strange: I have chosen my tool, but now I am going to decide what to use it for? With respect to your question about the + operator. There are many answers to this question; but it depends on what language you are compiling, with which goal in mind etc. It makes a big difference whether you are compiling a language like Perl into some byte-code language which is to be interpreted in which case your aproach looks reasaonable, or a special purpose language describing finite state machines into code for an embedded system in which case your approach does not work out. Doaitse Swierstra On 6 mei 2009, at 08:07, Rouan van Dalen wrote:

Hi everyone.

I am designing my own programming language.

I would like to know what is the best way to go about writing my compiler in haskell. What are the tools available in haskell that can help with compiler construction?

I know about Happy. Is that a good tool to use?

The compiler is intended for serious use and I would like it to be very efficient, maybe competing with compilers written in C. It should also be very easy to extend as the languoge grows.

Are there any good books that you can recommend on compiler construction in general and specific to haskell?

On another note, how is the operator + implemented in haskell?

is there a primitve (say #+) that is wrapped by the haskell operator +? Maybe something like:

(+) :: a -> a -> a v1 + v2 = #+ v1 v2

Thanks in advance

Rouan.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe