Fun in the Caribbean Windwards

Thanks to the generous invitation of Marc Hachey to me and my sister, Katy, we arranged to spend two weeks in the Windward Islands of the Caribbean with Marc and his Peterson 44 Sea Angel. I know Marc from hiking with him in the Sierras by Lake Tahoe. He’s an amazing hiker, we did a 26 mile day hike in fall 2009.

After meeting over dinner in November we arranged to fly into St. Vincent the evening of Wednesday, December 31st and to fly back to the states Monday, January 11th.

After flying into St. Vincent and getting picked up by Marc we had our first sail the next day over to Bequia, our first experience sailing in the Caribbean was wonderful. We couldn’t have asked for better conditions the winds were ~20knots and sunny skies. What a difference compared to the states where it had been gloomy and rainy in California.

After anchoring in Bequia we relaxed and I went for a short run on the island.

Bequia Harbor

That evening Marc’s friend Art invited us over to his boat the Jo Na Li to spend new years with him, his wife, daughter and a few others. We had fun chatting and eventually went over to the island and saw the new years fireworks over the harbor.

After picking up another crew member, Laura Tonello, our next destination was the Tobago Cays which according to Marc have decent snorkelling. Our sail down was again very enjoyable. Marc’s GPS with the arrow pointing to the way points made the navigating dead simple. After sailing down and anchoring I took a few photos; there were a lot of people it practically looked like a busy harbor!

Laura Tonello in the Tobago Cays

The next day we went snorkelling which I sucked very badly at. I might have set a world record for sucking in sea water every possible way in a snorkel. After finishing up snorkeling or in my case trying to snorkel we checked out the beach on one of the islands and spotted the large number of conch shells from times past when the area had more plentiful sea life.

After all our fun in the Cays we sailed back up to Bequia and spent a little more time there. But I was looking forward to climbing the Petit Piton in St. Lucia. To sail up to St. Lucia Marc decided to sail on the windward side of St. Vincent. This was a great decision with ~25 knot winds and a ~1-2 knot current in our favor. While sailing on the windward side of St. Vincent we had a few instants that we broke 10 knots and we had a steady 8+ knots for a few hours!

We got into the harbor between the Pitons in the afternoon and I took a few photos of the Petit Piton which Marc had talked about climbing way back in November when we discussed the trip over dinner. It looked like a fun climb!

Petit Piton

The trail to the top is on the other side which is a tiny bit less steep but still requires ropes in a few spots. The next day we sailed over to Soufriere and Marc checked in with his very good friends at the SMMA including one very funny lady, Baby! They had one of the customs officials drive us to lunch for roti’s. It was my first time getting chauffeured by a custom official!

A couple days later Marc and I made it up the Piton and what a climb. Marc has done it twice in one day! I was happy with getting to the top, it’s a fun climb and I highly recommend it.

Marc on the Petit Piton

My sister Katy and Laura didn’t climb to the top of the Piton but the next day we all went to the the rainforest. Sadly my batteries died before I could take photos of the rainforest but it was very beautiful and untouched compared to the rest of the island.

I’ve only touched on a very few of the highlights of our trip. I want to again thank Marc, and everyone else for making it a wonderful experience. I still think of your dinners, Marc, and your banana crepes, Laura.

We flew back to the states from Rodney Bay.

Playing with Alex (Compiler Series Part II)

We’re going to use Alex to write the scanner for NewL. Alex is the Haskell equivalent of Lex. The Alex manual is reasonably thorough and has several excellent examples of simple scanners written using it.

The basic idea for Alex is to pass it your Haskell code written up in the special Alex syntax and it spits out a plain Haskell source code file. There are several wrapper options available for using Alex as (1) a standalone scanner or (2) a module that gets compiled in with your parser. For this post we’ll be using Alex as a standalone scanner that takes input from standard in and outputs a list of tokens.

Alex like all other scanner generators uses regular expressions for specifying tokens. The basic format of an Alex file is

regexp { haskell-code }  

where haskell-code is an anonymous function that takes a string (the string that matched the regexp) and returns a token. A typically example is

 [0-9]+ { \s -> TIntLiteral s }

The \s is Haskell’s way of defining an anonymous function with one parameter named s. The “->” signals the start of the function body. Thus “\s -> TIntLiteral s” is a function that takes a String s as the argument and returns TIntLiteral s.

To define our tokens we make a new data type called Token with a list of the possible tokens.

 data Token = TIntLiteral String |
              TIdentifier String 

The above code defines two token types one is a literal int such as “10” and the other is an identifier such as “myVariable”.

Alex has a nice option %wrapper "basic" that defines the function alexScanTokens which takes a string and returns the list of tokens. Using this we define our main function as

main = do 
           s <- getContents
           print (alexScanTokens s) 

The main function gets the string from the standard input and puts it in s and then uses print (alexScanTokens s) to generate the list of tokens and print them out.
To test the scanner run

echo "10 \"StringLiteral\"" | ./a.out

the above command echos 10 “StringLiteral” to the standard output and then pipes it into the scanner, a.out (I assume a.out is the scanner executable). The output should be [TIntLiteral 10, TStringLiteral “StringLiteral”].

I’ve included a listing of the NewL Alex scanner below. I strongly recommend reading the Alex manual introduction. For compiling the listing use “alex Scanner.x” to generate the Haskell code and then run “ghc Scanner.hs” to generate the executable.

module Main (main) where

%wrapper "basic"

$digit = 0-9			-- digits
$alpha = [a-zA-Z]		-- alphabetic characters
$graphic    = $printable # $white

@string     = \" ($graphic # \")* \"

tokens :-

  $white+				;
  "class"				{ \s -> TClass }
  "new"				    { \s -> TNew }
  "String"				{ \s -> TString }
  "static"				{ \s -> TStatic }
  "void"				{ \s -> TVoid }
  "main"				{ \s -> TMain }
  "return"              { \s -> TReturn }
  "public"				{ \s -> TPublic }
  "extends"				{ \s -> TExtend }
  "int"					{ \s -> TInt }
  "boolean"				{ \s -> TBool }
  "if"					{ \s -> TIf }
  "else"				{ \s -> TElse }
  "true"				{ \s -> TTrue }
  "false"				{ \s -> TFalse }
  "this"				{ \s -> TThis }
  "length"				{ \s -> TLength }
  "while"				{ \s -> TWhile }
  $digit+				{ \s -> TIntLiteral (read s) }
  "."                   { \s -> TPeriod }
  "&&"				    { \s -> TOp (head s) }
  "!"					{ \s -> TNot }
  [\+\-\*\/]            { \s -> TOp (head s) }
  "<"                   { \s -> TComOp (head s) }
  "="					{ \s -> TEquals }
  ";" 					{ \s -> TSemiColon }
  "("					{ \s -> TLeftParen }
  ")"					{ \s -> TRightParen }
  $alpha[$alpha $digit \_ \']*	{ \s -> TIdent s }
  @string 	       	  		{ \s -> TStringLiteral (init (tail s)) -- remove the leading " and trailing " }
  "{"	 	 	   		{ \s -> TLeftBrace }
  "}"					{ \s -> TRightBrace }
  ","					{ \s -> TComma }
  "["					{ \s -> TLeftBrack }
  "]"					{ \s -> TRightBrack }
  "System.out.println"  { \s -> TPrint }
-- Each action has type :: String -> Token

-- The token type:
data Token =
    TLeftBrace  |
	TRightBrace |
	TComma |
	TLeftBrack |
	TRightBrack |
	TClass |
	TPublic |
	TString |
	TStatic |
	TVoid |
	TMain	 |
	TExtend |
	TInt |
	TBool |
	TIf |
	TElse |
	TTrue |
	TFalse |
	TThis |
	TLength |
	TWhile |
	TNew |
	TOp Char |
	TComOp Char |
    TNot |
	TEquals |
	TPeriod |
	TSemiColon |
	TLeftParen |
	TRightParen |
	TIdent String |
    TPrint |
	TIntLiteral Int |
	TStringLiteral String |
	deriving (Eq,Show)

main = do
  s <- getContents
  print (alexScanTokens s)


Writing A Compiler In Haskell (Compiler Series Part I)

My goal is to write a series of posts on creating a compiler for a restricted subset, NewL, of the Java language in Haskell. My tools are Haskell, Alex for scanning, and Happy for parsing.

Alex and Happy are basically the Haskell equivalent of Lex and Yacc. I know most of my compiler theory and practices from the Dragon book so I’ll be making references to it for the techniques used in semantic analysis and code generation. I’ve learned everything I know about Haskell from the really good book “Real World Haskell“, I cannot recommend it highly enough.

I plan to cover the following topics with Haskell source code and make files included.

1. Go over the grammar of NewL (this post).
2. Scanner for NewL using Alex.
3. Parser for NewL using Happy.
4. Error recover and reporting for the scanner and parser (I’m keeping it simple and abort on the first error and print the line and column number)
5. Symbol table and how it’s used in semantic analysis and code generation.
6. Revised NewL language and more symbol tables.
7. Type checking.
8. Intermediate code generation.
9. Machine code generation.
10. Garbage collection.

As you can see that’s a lot of stuff to cover. I’m warning you ahead of time that I’m very much a newbie when it comes to writing Haskell. I don’t even understand monads, so be forewarned the code get ugly compared to a true Haskell programmer.

With the above out of the way I’d like to go over the grammar of NewL. Please note that the semantics of NewL are similar to Java so if there’s any question about what some operation should do, we follow what Java does.

Terminal symbols are bolded and single character ones are in double quotes.

NewL Grammar

1. Program ::= MainClass { ClassDecl }
2. MainClass :== class Ident “{public static void main “(” String “[” “]” Ident “)” “{” Statement “}” “}
3. ClassDecl ::= class Ident “{” {VarDecl} {MethodDecl} “}
4. VarDecl ::= Type Ident “;
5. MethodDecl ::= public Type Ident “(” FormalList “)” “{” {VarDecl} {Statement} return Exp “;” “}
6. FormalList :== Type Ident { FormalRest } | ε
7. FormalRest :== “,” Type Ident
8. Type :== int “[” “]” | boolean | int | String | Ident
9. Statement :== “{” { Statement } “}” | if “(“ Exp “)” Statement else Statement | while(” Exp “)” Statement | System.out.println(” Exp “)” “;” | Ident = Exp “;” | Ident “[” Exp “]” “=” Exp “;
10. Exp ::= Exp Op Exp | Exp “[” Exp “]” | Exp “.length | Exp “.” Ident “(” ExpList “)” |
Integer_Literal | String_Literal | true | false | Ident | this | new int[” Exp “]” | new Ident “(” “)” | “!” Exp | “(” Exp “)
11. ExpList :== Exp { ExpRest } | ε
12. ExpRest ::= “,” Exp
13. Ident ::= Letter { Letter | Digit | “_” }
14. Integer_Literal ::= Digit { Digit }
15. String_Literal ::= “” { Character } “
16. Op ::= && | < | +| | *

The classic Hello World for NewL

class HelloWorld {
    public static void main(String[] a) {
        System.out.println(new Hello().World());
class Hello {
    public String World() {
        return "Hello World";