Menu
I've been looking at Haskell and I'd quite like to write a compiler in it (as a learning exercise), since a lot of its innate features can be readily applied to a compiler (particularly a recursive descent compiler).
What I can't quite get my head around is how to represent a language's grammar in a Haskell-ian way. My first thought was to use recursive data type definitions, but I can't see how I use them to match against keywords in the language ("if") for example.
Thoughts and suggestions greatly appreciated,
Pete
776
Haskell's design is centered around pure functions and immutable data. Over and over, these features have proven essential for writing correct software. Managing global state, mutable data, and side effects is error-prone, and Haskell gives the programmer all the tools to avoid or minimize these sources of complexity.
There are lists of companies that use Haskell on the Haskell web site and on Quora. A few highlights are Facebook, IBM, Twitter, AT&T, Bank of America, Barclays Capital, NVIDIA and Microsoft. Some interesting links are: Facebook uses Haskell in several projects, for example Fighting spam with Haskell.
Haskell (/ˈhæskəl/) is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation.
Getting started. Like some languages Haskell can be both compiled and interpreted. The most widely used implementation of Haskell currently is GHC, which provides both an optimising native code compiler, and an interactive bytecode interpreter.
Functional programming is based on mathematical functions. Besides Haskell, some of the other popular languages that follow Functional Programming paradigm include: Lisp, Python, Erlang, Racket, F#, Clojure, etc. Haskell is more intelligent than other popular programming languages such as Java, C, C++, PHP, etc.
Every expression in Haskell has a type which is determined at compile time. All the types composed together by function application have to match up. If they don't, the program will be rejected by the compiler. Types become not only a form of guarantee, but a language for expressing the construction of programs.
GHC which is the main Haskell compiler is a masterpiece that can generate incredibly performant code. This is due to the LLVM and a native run back-end present in the GHC. If properly optimized, Haskell can run with code fairly close to C code. The IO manager and runtime is able to handle thousands of threads with minimal effort.
Haskell is a functional language, as mentioned before, while Python is a mixture of procedural, object-oriented, and functional programming styles. Haskell has procedural programming support, but the side-effects in the language do not make it easy. Python and Haskell have a strong type system, which means explicit conversions have to be done.
You represent programs using mutually recursive algebraic data types, and to parse programs you use parsing combinators. There are a million flavors; you will find three helpful tutorial papers on the schedule for my class for Monday, March 23, 2009. They are
The Hutton and Meijer paper is the shortest and simplest, but it uses monads, which are not obvious to the amateur. However they have a very nice grammar of and parser for expressions. If you don't grok monads yet, Fokker's tutorial is the one.
68
A recursive data type is fine for this. For example, given the language:
expr ::= var | "true" | "false" | "if" expr "then" expr "else" expr | "(" expr ")" an example expression in this language would be:
if true then x else (if false then y else true) Your Haskell data type would look something like this:
data Expr = Var String | Lit Bool | If Expr Expr Expr Your parser then takes care to translate, e.g., x into Var "x", and true into Lit True, etc. I.e.:
parse "if x then false else true" == If (Var "x") (Lit False) (Lit True) For writing parsers you can roll your own using the techniques mentioned in Norman's answer, or using Parsec or use parser generators like Happy.
23
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
