Translate Haskell into English Manually, Part II

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

I really hate to spoil the tone of such a nice tutorial with opinionated commentary, but the exceedingly careful reader may have noticed that the C version is shorter than the Haskell version! In fact, by my count, there are 106 useful lines of code in the C version and 146 lines of useful code in the Haskell version. What happened? This is the type of thing that can make a budding article writer lose sleep at night!

Notice a few things. The C version is using static memory allocation. It pre-allocates space for 100 tokens, each of which can be up to 64 characters long. Modern C applications must usually manage memory dynamically, and it's a painful, error-prone chore. Nor does the example do any error handling. Haskell's exception system went completely unused. Last of all, the example didn't make use of any abstractions. Haskell's high-level, functional nature means that libraries, in general, can be higher level in Haskell than in C, but this is meaningless if you don't even use a parsing library.

Note, however, that the Haskell version already has some benefits over the C version. For instance, being able to print a ParseContext for free was really nice. Theoretically, because all parsing state is contained in a ParseContext, you can pass off the ParseContext to another machine and let it continue the computation. If, during parsing, for some reason it was necessary to undo what you had done and go back to some previous parsing state, it's absolutely possible to throw away your current ParseContext and continue with some previous ParseContext.

Consider the task of removing a bolt. You have your choice of a crescent wrench (say, C), a socket set (say, Java) or an impact wrench (say, Haskell). An impact wrench is incredibly powerful and can make difficult tasks easy. However, what we've seen is that sometimes it takes longer to retrieve the compressor from the garage in order to use an impact wrench than it takes to simply get the job done with a crescent wrench.

If Haskell is so powerful, why isn't it more popular? I think it's because the authors and many of the users are just too dang intelligent! I've heard Guido van Rossum, the author of Python, say something like, “ML is a great language--it's just too bad you have to have an IQ higher than 150 to use it.”

Consider that in Paul Hudak's book, The Haskell School of Expression, Hudak drags the user through writing code to calculate the area of a concave polygon [exercise 2.5 on page 33] before he even shows the user the canonical “Hello world” example [page 37], and I still haven't gotten to the part in the book that explains how to use Hugs. [Note: I'm being facetious. I don't think it's covered in the book at all. Hugs is an implementation of Haskell, and the book is about the language itself, not any particular implementation. However, my point stands that unless you actually get an interpreter or compiler running so that you can actually write some code, you can't truly claim to know a language. I spent hours trying to figure out why the Hugs shell wouldn't let me define a function before I found out that you have to store them in a file and load them as a library.]

Furthermore, as much as I love Haskell's type system, I think there's a real misconception. Hudak writes:

The best news is that Haskell's type system will tell you if your program is well-typed before you run it. This is a big advantage because most programming errors are manifested as typing errors [p. 8].

I don't agree. Although I would agree that most bugs are caused by programmers typing the wrong code, I would not agree that most bugs are manifested as typing errors! In fact, I find that most of my bugs are caused by subtly misunderstanding the fine details of a difficult problem, and I've heard other well-respected programmers say the same thing. Personally, being a fan of duck typing, I find that most of the time, types are almost a nuisance! [Note: Lest Java programmers send me hate mail, this is a topic covered repeatedly by Bruce Eckel, author of Thinking in Java, on his blog (mindview.net/WebLog/ArticleIndex). For instance, this post: mindview.net/WebLog/log-0025. If you consider tools like QuickCheck (www.cs.chalmers.se/~rjmh/QuickCheck), which can use Haskell's type system to generate test cases automatically, you'll see that a whole article could be written debating whether Bruce Eckel's ideas apply to Haskell. Nonetheless, I think it's fair to say that Haskell's type system gives you “more bang for the buck” than Java's.]

I spent a lot of time wondering why Haskell programmers seemed to be so successful. I've come to the following conclusion:

It's not that good programmers are necessarily drawn to Haskell--as Google has shown, there are a lot of extremely talented programmers who are content to code in Java. Rather, it's that you have to be a smart, patient, disciplined and dedicated programmer to code in Haskell at all.

The truth of the matter is you can be a bad programmer and make a living coding in Java. The same cannot be said of Haskell.

In summary: I think that it's fair to say that Haskell has some flaws (for instance, you have to be smart to use it), and it might not ever be as popular as Java, PHP or Ruby. However, languages are like friends; you take the good with the bad and enjoy them as a whole (with the exception of C++; almost no one uses all of C++).

Haskell is like a brilliant kernel programmer I once worked with. Asking him anything outside his areas of expertise was like trying to dereference a random location in memory. I use to joke that his user interface was about as friendly as a Commodore 64--“syntax error”. Nonetheless, you just couldn't beat him if you needed a new device driver for some random piece of hardware. Likewise, if I had to reimplement Pascal or write Perl 6, Haskell would be my first choice--although I'd definitely use a powerful parsing library. In fact, I'm pleased to say that Haskell is a welcome addition to my programmer's toolbox!

______________________

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