Translate Haskell into English Manually, Part II

Write a program in Haskell that translates C type declarations into English.

This is part two of a two-part series [see linuxjournal.com/article/9096 for part one]. In this article, I build upon the concept of a parse pipeline with the State monad. Then, with all the pieces in place, I show the complete Haskell program. I also take a step back and consider why Haskell isn't as popular as some other languages and whether it deserves a place in your programmer's toolbox.

The State Monad

In part one of this series, I showed parse pipelines that looked like:

c $ b $ a ctx

Now, there are two problems with basing the whole program around this construct. The first is that everything is written backwards. It's not too hard to work around that by creating an operator that reads left to right, unlike $. However, it's also a pain to pass the ParseContext explicitly to and from every function that acts as a ParseContext transformer. [Note: 1. In an early version of my program, I wrote the following:

-- |> is like a UNIX pipe.
infixl 9 |>
x |> f = f x

Hence, c $ b $ a ctx could be written ctx |> a |> b |> c. I originally wrote the whole program around this construct instead of the State monad, but I like the State monad better because of Haskell's syntactic sugar for monads.]

Purely functional means you have to pass everything to the function (that is, no globals) and you have to return everything from the function (that is, no side effects allowed, not even printing a message to the user). Passing everything explicitly can get tedious, but that's something Haskell has an answer for—monads. Instead of having to piece a pipeline together using $, the do syntax can transform the above into:

do a
   b
   c

Not only does the do syntax “read the right way”, but (and this is a key point) it's also syntactic sugar for saying, “the result of 'a' will be needed to call 'b', and the result of 'b' will be needed to call 'c'.” It's still a pipeline, but now it's syntactically convenient.

The State monad is a monad that comes with Haskell, which is perfectly suited for the current situation. The State monad is a simple monad that simply encapsulates a bit of state. Looking at the example above, a, b and c are all functions that take and modify this implicit state. Because each might modify that state, they must be run in order, which, of course, isn't necessarily the norm in Haskell.

The notion of a ParseContext transformer dovetails perfectly with how the State monad works. Each ParseContext transformer will now have the following signature:

f :: State ParseContext ()

This translates into:

"f" is a function that has type "State ParseContext ()", which is to say
that "f" operates within the "State" monad where the "State" monad is
encapsulating a "ParseContext" object.

In summary, what does the monad buy us?

  1. It allows us to use the do syntactic sugar in order to tie statements together into a chain that must be executed in order.

  2. It takes care of implicitly passing around ParseContext objects.

Lest my reader get bleary eyed, let's see some code! I've updated the makeCool.hs program to use the State monad, thus creating a true Rube Goldberg (en.wikipedia.org/wiki/Rube_Goldberg#Rube_Goldberg_machines) program:


import Control.Monad.State

data TokenType = Identifier | Qualifier | Type | Symbol Char
  deriving (Show, Eq)

data Token = Token {
  tokenType :: TokenType,
  tokenValue :: String
} deriving Show

data ParseContext = ParseContext {
  input :: String,    -- The input that has not been parsed yet.
  output :: String,   -- The output generated so far.
  currTok :: Token,   -- The current token, if defined.
  stack :: [Token]    -- A stack of tokens we haven't dealt with yet.
} deriving Show

makeCool :: State ParseContext ()
makeCool = do
  ParseContext {input = s} <- get
  put (ParseContext {input = "", output = s ++ " is cool!\n"})
  return ()

main = do
  s <- getContents
  let ctx = ParseContext {input = s, output = ""} in
    putStrLn $ output $ execState makeCool $ ctx

Running it:

$ echo -n "Haskell" | runhugs -98 makeCoolState.hs
Haskell is cool!

A few things deserve note. First, in order to use the State monad, you must pass -98 to runhugs, which enables special Hugs extensions. Next, what used to be:

putStrLn $ output $ makeCool ctx

is now:

putStrLn $ output $ execState makeCool $ ctx

The execState function is used to get into and out of the “State monad world”. Occasionally, it's easy to get confused by higher order functions like execState; however, it's easy enough to apply a cookie-cutter approach. That is, execState makeCool $ ctx takes ctx as an initial state and returns a final state. makeCool operates within “the context” of the State monad. Easy enough. If you really want to know the nitty-gritty details of how the State monad works, there's a really fun explanation on Wikipedia (en.wikibooks.org/wiki/Programming:Haskell_monads#The_State_monad).

Notice that makeCool uses the do syntax to tie multiple statements together. First it uses the get function to get the current state. Then it uses the put function to put back an updated state. Then it returns (), which is to say nothing useful. Looking at get and put, at it's heart, the makeCool function is still a ParseContext transformer.

Another thing deserves note. As usual, there are a few convenience functions for interacting with the State monad. For instance, instead of using get and put explicitly, it's also possible to use the modify function, combining the two activities. Hence, the makeCool function could have been written:

makeCool :: State ParseContext ()
makeCool = modify (\ctx ->
  ctx {input = "", output = input ctx ++ " is cool!"})

The modify function takes a callback that takes the state as input and returns state as output. Instead of passing a named function to modify, I'm passing an anonymous function, hence the \ syntax. Translating:

"makeCool" is a "ParseContext transformer".  Modify the "ctx" by setting
"input" to "" and setting "output" to the original input plus the string
" is cool!".

As in other languages, anonymous functions can be either ultra-convenient or ultra-inscrutable, depending on both the author and the reader. Nonetheless, I'll use the convenience functions where, uh, convenient.

______________________

Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Good static typing does make a gidfference.

Curt Sampson's picture

As background: my first five years of full-time programming were Java, the next five years after that, Ruby, and over the last year or so I've moved to nearly-full-time Haskell.

Types in Haskell do often feel like a nuisance when you come from a Ruby background, especially when you're doing quick-and-dirty hacks where you're not so concerned about correctness because you're going to throw out the code after a few uses.

However, these days I just as often find the lack of types in Ruby to be more of a nuisance because I have to work fairly hard to keep silly bugs from creeping into my programs (oops, that was supposed to be an array of arrays, not an array) whereas in Haskell the type checker deals with all of this for me. In Haskell I find myself using far fewer unit tests and doing both small and large refactorings with more confidence. I also find I no longer need to use error checking code as I did on occasion in Ruby, where I'd look at a situation and say to myself, "if the wrong class of object gets out of here, it's going to appear half-way across the program and I'll spend ages debugging it."

Not to mention which, when you really start using monads and combinators, you'll find them extremely powerful.

cjs@cynic.net

it's unfair to blindly translate algorithms

Shannon -jj Behrens's picture

Brandon Moore has sent me an alternate version of the code that is both simple and yet still shorter than the C version. His findings suggest that an algorithm in C may not translate easily or naturally into Haskell; which, of course, is not surprising. I purposely made the Haskell program as close to the C program as possible to aid the reader in understanding it, but perhaps this was an unfair handicap to Haskell.

Alternate solution

Brandon Moore's picture

I wrote some alternate code which makes a simple parser monad, rather than the simple state monad used in the article. It's like a recursive descent parser, but with all the recursion wrapped up inside the monad. This doesn't quite handle quantifiers like const and static at the beginning of the declaration correctly, but the C and Haskell code are already both wrong in different ways, and the full syntax is really complicated so I don't care. I count 62 lines of code.

Many thanks for a very clear

Jim B's picture

Many thanks for a very clear tutorial. I'm some way from grokking monads but this should help...As you say, introductory articles on monads are usually a bit deep (The subtitle of the Programmers Guide to Monads, 'Don't Panic', sounds promising but 2 or 3 pages later sure enough I was panicking!) so congratulations on not mentioning Category Theory :-)

Your link to the syntax tour is broken. I suppose it's meant to be http://www.cs.uu.nl/~afie/haskell/tourofsyntax.html but that gives a 404 - another place is http://cs.anu.edu.au/Student/comp1100/haskell/tourofsyntax.html but I don't know if this is it's home.

thanks

Shannon -jj Behrens's picture

Thanks for your comment as well as mentioning the broken link.

White Paper
Linux Management with Red Hat Satellite: Measuring Business Impact and ROI

Linux has become a key foundation for supporting today's rapidly growing IT environments. Linux is being used to deploy business applications and databases, trading on its reputation as a low-cost operating environment. For many IT organizations, Linux is a mainstay for deploying Web servers and has evolved from handling basic file, print, and utility workloads to running mission-critical applications and databases, physically, virtually, and in the cloud. As Linux grows in importance in terms of value to the business, managing Linux environments to high standards of service quality — availability, security, and performance — becomes an essential requirement for business success.

Learn More

Sponsored by Red Hat

White Paper
Private PaaS for the Agile Enterprise

If you already use virtualized infrastructure, you are well on your way to leveraging the power of the cloud. Virtualization offers the promise of limitless resources, but how do you manage that scalability when your DevOps team doesn’t scale? In today’s hypercompetitive markets, fast results can make a difference between leading the pack vs. obsolescence. Organizations need more benefits from cloud computing than just raw resources. They need agility, flexibility, convenience, ROI, and control.

Stackato private Platform-as-a-Service technology from ActiveState extends your private cloud infrastructure by creating a private PaaS to provide on-demand availability, flexibility, control, and ultimately, faster time-to-market for your enterprise.

Learn More

Sponsored by ActiveState