Matrix Multiplication in Haskell

As I mentioned in a previous post, I’m trying to learn Haskell.  I’m not progressing super quickly because it’s not a terribly high priority, but it’s sort of fun to think about programming problems in a totally different way.  While Haskell (being a functional language) definitely fits this niche, the book that I’m following does not include any exercises — you can sort of work the examples ahead of time and compare your solution to the book’s, but that’s a poor substitute.

I was helping a friend of mine (a sophomore in computer science) with an assignment he was working on recently, when it struck me that the straightforward, simple assignments he’s doing might make good projects to tackle in Haskell.  The course he’s in is a data structures course, so a lot of the projects have fairly simple input / output specifications, and somewhat complex backend requirements.  I chose to ignore the data structure parts (I’ll save implementing stacks / linked lists / etc. in Haskell for another day) and tried to tackle just the functionality.  The first (and so far, only) project I worked on reads in two matrices and either multiplies them or informs the user that the matrices’ sizes are incompatible.  The multiplication is straightforward — I’m not using the Strassen algorithm — and the input / output formats are easy as well.

The project turned out to be both more difficult and more instructive than I had planned.  Some observations I made while writing my program:

  • Parsing in a functional language is totally foreign to me.  The math wasn’t all that hard to grasp (though it wasn’t exactly straightforward either) but doing simple things like splitting a line into chunks (“tokens”) based on some delimiter is a completely new experience in a functional language.
  • Nearly all my methods have essentially one line of functionality.  I’m not sure if this is how Haskell is “supposed” to be written, or if it shows that I’m doing something wrong.  Either way, the length of functions is something I’m definitely going to pay more attention to when I look at examples in the future.
  • I’m not very good at list comprehensions.  Below are two ways of multiplying matrices: First, my way:

    Second, the way it’s implemented on rosettacode.org:

All in all, I learned a lot.  It’s some pretty ugly code, and I may rewrite it further, or tackle a different project from the same class and try to go about it in a better way.  If you’d like to look at my code or compile / run it (with the understanding this is just sort of doodling-type-code and isn’t documented or optimized or very good) feel free to download it.

Haskell and exercises

The Haskell logo, from haskell.orgIn fall 2011 I took a course that covered, among other things, proving program correctness with some software called Coq.  There's a lot to it, and I won't go into that here, but one important part of Galina, the language used in Coq, that I had been unexposed to previously was functional programming.  Functional programming is a style of programming (a paradigm, in the parlance of our times) that a lot of computer science students learn as undergraduates.  I didn't, though, so this course – which used but did not teach functional programming – was quite challenging.

I ended up slugging my way through the class, and learning lots.  I  wasn't satisfied with my understanding of functional programming, though, so I decided to learn Haskell on my own.  Haskell is a pretty modern functional programming language that I'd heard lots about as an undergrad from a friend named Alan Mock (it doesn't look like he updates his blog, which is a bummer, since he's super smart and has lots of interesting opinions).  Not wanting to learn from some old, crusty, book full of greek symbols (since I get enough of that at school), I found the least-crusty programming language book ever: Learn You a Haskell for Great Good!, by Miran Lipovača.An octopus, as drawn by Miran Lipovača.

It seems to me like a somewhat narrowly targeted book – it assumes some knowledge of imperative programming, pop culture (from the time I was a child – teenage mutant ninja turtles, etc.), and a sense of humor.  That's not to say that any of these things are required, but I think you'll miss quite a bit of the joy in the book without them.  Since I'm mostly in the target audience, though, I really like the book.  I'm only a few chapters in, but it does an excellent job of explaining (what seem to me to be) pretty tough concepts.  My one complaint about the book, though, is that it doesn't have any exercises.  Without a way to test yourself at the end of a chapter or section, it's hard to tell if you've actually learned anything – I find myself playing around with the given examples / trying to figure out why they work or don't work.  That definitely helps, but it's not as direct as just working through exercises.

As an example of just how valuable exercises are even for short technical descriptions, here's a program called Logitext: it's an "educational proof assistant for first-order classical logic using the sequent calculus."  The author has an excellent tutorial, with examples throughout and some interesting problems at the end.  After just reading through the tutorial you may have some trouble with the exercises (I know I did) but after completing them, the knowledge seemed to "gel" a lot better.

The Haskell logo is from haskell.org, and the octopus playing guitar hero is from Learn You a Haskell for Great Good! by Miran Lipovača.

Papers, papers… some more papers

So, looking at my blog, I realized I hadn’t ever actually made a post about finishing my thesis.  I defended successfully at the end of November, made the committee’s corrections, and now have a final version of my master’s thesis.  If you’d like, you can find a copy here.

I’m continuing on at K-State, and now working on my PhD.  I’m currently working mostly on my classes / breadth exams, though since I did my MS here, I have an opportunity to finish pretty quickly.  I’ve also begun some work on my doctoral research, which is pretty closely related to the stuff I worked on for my masters: I’m looking at applications that run on K-State’s MDCF.  Eventually I’ll work on application development (process, tool support, etc.) specifically but for now everything’s just getting started.  One nice thing about this project is that it was already underway, so things are moving quickly.  In fact, our group has a paper accepted to the Software Engineering in Health Care (SEHC) workshop at the 2012 International Conference on Software Engineering (ICSE).

You can read the full paper here, if you’d like.  It looks at requirements specifications for applications that run on MDCF-like platforms (so-called “Medical Application Platforms”).

Pretty-Printing XML with XSL

One of the things I really enjoy about my job is that as the only developer on my project (formerly known as λ, now officially named Kinerja), I get to tackle a bunch of different types of programming jobs.  Working on the model checking core is pretty different from working on the web interface, and neither of those are at all similar to tuning the database backend.  Though the (vast) majority of my work is in Java, other layers are written in their own language (PHP, SQL, etc.).  One of the most exciting parts of my job, then, is to learn a new technology to handle a new aspect of the project.

Since Kinerja's input files are in the XML format produced by YAWL's user-interface, we don't have a lot of flexibility with making those look the way we'd prefer.  Though my adviser and I have talked about coming up with our own domain-specific language, it's hard to imagine one that would be less bulky than YAWL's XML that would still support all of its features.  That said, we still wanted a way to look at a workflow without firing up the user-interface and manually inspecting the intricacies of each workflow-task.  We decided, then, to write a simple formatter.  Since we were modifiying an XML file, I decided to learn and use XSL (eXtensible Stylesheet Language) — specifically XSLT (the T stands for transformations, in my case from XML to HTML).

XSLT is a declarative language (or a language where the control-flow is not explicitly stated) and it's the first time I've used such a language.  It took a little while to get used to (and plenty of example-reading) but I think I'm pretty much up to speed now.  So far, I've created a number of small examples (in XSLT) and a full-scale mockup (in hard-coded HTML).  My project for the coming week is to make the actual pretty-printer, and I'm interested to see how it will turn out.  It uses a number of different XML files (with values in one referencing values in the other) so it should be quite the task.

I didn't choose to use XSL simply because it was a new technology, however, but also because it has a number of really beneficial qualities.  The first is that it's usable (nearly) anywhere.  Not only can it be rendered server-side (via another language, like PHP's XML package, or Java's XALAN) but it's also one of the (relatively) few technologies that can be used client-side as well.  In fact, you can have web-page visitors do a great deal of formatting work themselves by giving them XML and and XSL stylesheet.  Indeed, this was my original plan, however some less full-featured browsers (e.g.: those running on mobile phones) aren't as reliable as the major computer-based browsers.  Still, the fact that this formatter won't have to be re-written even if the rest of the server code would be (if it gets re-based to Java, for example) is an interesting (and somewhat comforting) thought.

Cold Weather Grilling

Our two grills, shortly after lighting.Well, it’s officially winter break: it’s sleeting outside, I’m putting off wrapping gifts, and I’m at my parents house with very little to do.  I had a pretty decent semester, and my one class (Advanced WWW Technologies) is now complete, so I can focus full time on my master’s work.  In a sort of neat twist, however, my course-long project was to build a graphical front-end for my the software I’m building (currently named λ (lambda) — discussed in the preceding post as well).  That user-interface is now complete, and at some point I’ll post up a link to the server I have which runs λ.  That day is not today, however.  Today is a day for discussing winter grilling.

I know a lot of people aren’t big fans of winter, which bums me out, because it’s my second favorite season (the top slot goes to Fall).  I understand a lot of the complaints — being cold is lame, you’re not on summer vacation, and it’s not very pleasant outside so your ability to do fun stuff is restricted.  While all of these are valid, one particular fun activity, grilling, has not ceased just because it’s below freezing outside.

During the summer, my roommate(s) and I got into the habit of grilling every week on Sunday.  We’ve continued this tradition as the months progressed, and are planning on trucking through the winter.  We have a cookbook on simple grilling recipes, and they’re really pretty good — a recent weekend’s menu was chipotle-peach glazed chicken and buttered new potatoes, for example.  Grilling in inclemency takes a bit more effort than your standard Memorial Day weenie roast; there are in fact several unique factors to consider.

First, there’s wind / rain / snow which can slow down your fire when it’s first getting lit.  Second, there’s the fact that it’s considerably colder outside — note that both this and the first factor can be remedied by adding more charcoal briquettes (propane is lame) to get stuff up to the appropriate temperature.  Third, you have to wear more clothing while lighting the fire and tending the grill, and this clothing gets smoky.  This happens during the summer, too, but I have a lot more t-shirts than I have hoodies and coats.

There is one definite advantage to grilling in the winter, however, and that’s that no one else is using their equipment.  When our friends retired their grills for the season, they donated / loaned some of their equipment to us, so we now have a smaller, secondary grill we use for heating up our side dish while the proverbial “big meat” roasts on the main grill.

I reviewed a paper!

The Springer logoSo, I just reviewed my first academic paper.  I'm not sure how much I'm allowed to say about it (since it's both pre-release and not my own work) and I can't link to it, but I will say that it was fascinating.  It also was one of those unique experiences where you know you'll be repeating it countless times over the remainder of your life — but as this time is identifiably the first, there is considerable wracking of nerves.

I wasn't given a ton of guidance from the professor who gave the paper to me, which wasn't a problem but did leave some basic formatting questions, e.g.: Should my review be a typeset pdf or a plain text email?  Was there any standard format to be used?  I got most of this ironed out and submitted my second draft earlier today.  I'm not sure how much of my review will be used / submitted back to the paper's authors.  I've been lead to think all of it, but I haven't heard for certain.

Reading a non-peer reviewed (or at least not previously reviewed) paper was itself an odd experience.  I'm so used to reading published papers (indeed, I think this is the first non-published paper I've read, save for those internal to my office) that the format itself lends quite a bit of credence to the subject, and at first I found the idea of criticizing the paper somewhat daunting.  Here was a manuscript, identical at first glance to those I had read before, with all the requisite figures and formulas, and I was supposed to go poking holes in the arguments and thoughts of its authors.  I had plenty of feedback eventually, but it certainly took a while to get going.

The image to the right is the logo of Springer Science+Business Media (the publisher of a number of academic journals) and was retrieved from http://www.nanonets.org/.