Haskell for defining a programming language

Question

I have googled about trying to find a simple example of Haskell being used to define a simple language but to no avail.

I did find this post on stackoverflow giving a similar example, but when i implemented it, it didn't appear to work:

Haskell - How to best to represent a programming language's grammar?

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

however, when i entered if true then x else (if false then y else true) into the console as input, it complained about "x" not being interpretable. It also didn't like true and false.

EDIT: I did derive "show" also, at the end

Answer 1

There are a couple of common steps to creating a programming language (there are others, of course):

• parse the program text into a syntax tree
• walk the syntax tree, doing something with it (interpreting, compiling, collecting statistics)

The data Expr you've shown would be part of a syntax tree. The if true then ... is program text. You need some way to get from text to tree: you need a parser.

Or, you can use Haskell as your parser, and write the syntax tree as Haskell code:

If True "it's true!" (If False "uh-oh" "it's false")

Answer 2

Parsec has extensive programming-language-focused tools. So that's a great place to get started.

It may take some time to wrap your head around the distinction between two things:

• Your programming language as text saved in a file.

• The representation, in Haskell, of that language.

That's why you need the Lit True and not just true. true is the text in your programming language. Lit True is the Haskell representation. Linking the two is what a parser is for.

To answer another of your questions in comments, a basic solution of the "chair desk" problem is this:

import Text.Parsec

data ProgrammableFurniture = ChairDesk 
                           | CouchCoffeeTable

--a parser for the text "chair desk"
chairDesk = do string "chair"
               char ' '
               string "desk" <?> "Chair must be followed by desk!"
               return ChairDesk

Answer 3

If you want to represent if true then x else (if false then y else true) in your little language, you need to use the following expression:

If (Lit True) (Var "x") (If (Lit False) (Var "y") (Lit True))

If, as you say, you derived Show this will also show exactly as entered.

I'm not sure what more you want to do! Possible further things to try are:

• Writing an evaluation function.
• Writing your own Show instance to get the printed representation to look nicer.
• Writing a parser for this little language.

Answer 4

Along the same vein as yatima2975's answer, you can simply derive Read.

data Expr = Var String
          | Lit Bool
          | If Expr Expr Expr
          deriving (Read, Show)

Then if you use the read function on a String with the same format as yatima illustrated, it can produce an Expr. Notice I had to escape the " around the inner strings.

ghci> read "If (Lit True) (Var \"x\") (If (Lit False) (Var \"y\") (Lit True))" :: Expr
If (Lit True) (Var "x") (If (Lit False) (Var "y") (Lit True))

This is simpler than defining your own Read instance, but you could do that, too.

Answer 5

Unfortunately, language syntax and parsing do not rise to the level of defining a programming language. Defining the semantics of the language is the most important part and if well-defined (which it must be by definition to settle conformance issues of implementations of a language) goes the distance to improve implementation whether via interpreter or compiler.

While Haskell is a purely functional language there are criticisms regarding its lazy evaluation which introduces problems regarding reasoning about its performance.

Regarding Haskell's suitability for what you intend (a simple language) - perhaps it is more important to delineate your intentions first, and then attempt to validate whether Haskell or some other language fits your criteria as the best candidate in which to define your programming language.

While you are at it, you might want to checkout Dana Scott's Denotational Semantics and take a look at Lambda Calculus as a potential language in which to define your programming language (if you are up to the challenge). Even simple languages, in order to be useful, should be well-defined semantically.

Answer 6

Design And Implementations Of Languages Of

W.Pratt is good book to read , after that it is better to read aho compiler book.

But after all of this ; you need some algorithms for compilers and some principals that you should follow.

For example you should write a scanner , Which checks errors in variable names for exmaple.

For example a C++ scanner will find error in below code :

int 32xy=0;

Because the c++ variables cannot start with a digit.

So far a scanner has a symbol table that holds the errors . the scanner will send the symbol table to parser now.

Now we will write a parser .

notice that my answer is pervasive.