I come from Java and want to know what monads are in Haskell

This is an introduction to monads. There are many of these. My goal today is to show how a simple class written in Java could be translated into equivalent functionality in Haskell using some monads, without getting into any of the theory stuff.

Hopefully some people coming from a non-Haskell background will get something out of this, though the Haskell syntax is likely to be very WTF-inducing for those who haven’t seen it before.

I should begin with a few things that this guide is not about:

  • Categories. The etymology of the word “monad” is a red herring. Trust me. Knowing a lot about category theory will make you a better programmer in the same way that playing a lot of checkers will make you better at chess: there’s probably some benefit, but it’s not a good way to get up and running with the basics.

    We will be treating monads as a design pattern instead of monoids in the category of endofunctors. The latter perspective is interesting to the people who like to design languages; the former perspective is interesting to people who like to write code.

  • The full generality of monads in programming. Lots of things are monads, and I will be ignoring most of them. I’m going to focus on how monads can be used to translate a particular Java class into Haskell, and what it looks like as we add functionality to both versions of the code.
  • Haskell evangelism. I’ve already written about the things in Haskell that I love. I love Haskell, and I use it to make my dreams come true. On the other hand, I’m not at all invested in whether or not you like Haskell.

    Though if you want to learn more about this language, I’d like to help you along your journey.

What I am going to talk about is how to use monads to do something in Haskell that is easy to do in Java.

(more…)

Advertisements

Haskell features I’d like to see in other languages

When I read Ben Hutchison‘s OO/Imperative programmers: ‘Study Functional Programming or Be Ignorant’ I knew I had too much to say for the comments, so I figured I’d put in my 2 cents here.

Haskell is my go-to language, both for scripting, and for getting work done. This is not because of any particular allegiance to the language. Haskell and I have an open relationship, and the moment I find a language that out-Haskells Haskell, you can be sure I’ll move on.

Here I want to describe my favorite things about Haskell. You’ll note that they are all about the type-system. I don’t feel too strongly one way or the other about laziness, or about monads (though I won’t give them up without first finding something to take their place). I don’t even particularly care that it’s a functional language, in as much as I can have these features in a non-functional environment.

Some of these features are already available elsewhere. This is wonderful! If you know of any examples of this, please tell me in the comments.

This is a list of my favorite things:

(more…)

Syntactic support for Kaminsky’s Interpolique in Haskell

When I recently wrote about my first impressions of Kaminsky’s Interpolique, I mentioned that the only thing I didn’t like is that PHP doesn’t offer any way to protect against syntactic mistakes, such as where the programmer mistakenly uses a $ instead of a ^^.

Today we’ll look at how Interpolique can be implemented in Haskell in such a way that we force the developer to use Interpolique when creating a SQL query, precluding the possibility of the $/^^ mixup bug. In doing so we’ll see that we don’t need anything like PHP’s eval to get the job done.

All of the code for this post is on github: InterpoliqueQQ.

(more…)

First impressions: Serving statically with Snap

(This post refers to Snap 0.2.6.)

There’s been a lot of buzz about the Snap framework, so I thought I’d give it a look. My personal website doesn’t have anything dynamic going on, so arguably Snap is “overkill,” but then again so is Apache, so what the heck. Snap is entirely experimental at this time: in their own words, “it is early-stage software,” so every single critique given here should be read with an implied expiration date.

So the question is: how does one host a static site on Snap? At present time there’s no tutorial for this, so I fumbled around until I got something working. Here’s my code:

main = do
    putStrLn "ninj4net online"
    quickServer config site

site :: Snap ()
site =
    route [ ("kinetic", static "kinetic")
          , ("math1010", static "math1010")
          , ("math1030", static "math1030")
          , ("math1100", static "math1100")
          , ("math1210", static "math1210")
          , ("", static "")
          ] 
    (writeBS "general error")

static d = do
    let html_file = "static/" ++ d ++ "/index.html"
        xml_file  = "static/" ++ d ++ "/index.xml"
    html <- liftIO $ doesFileExist html_file
    xml  <- liftIO $ doesFileExist xml_file
    ( (ifTop (fileServeSingle $ if html then html_file else xml_file)) 
      (fileServe $ "static/" ++ d) )

Discussion

Some of my directories use an index.html file, while others use an index.xml file. I need to use System.Directory.doesFileExist function to determine whether or not these files exist — trying ifTop (fileServeSingle "something that doesn't exist") will not switch to the alternative using <|>, so an explicit check is needed (it will whine about an exception being thrown, completely undermining the choice operator!). This is presumably a bug (I submitted it to their github).

I’m sure there is a much more elegant approach, but this was the best I could muster during lunch.

A thing Snap is missing

I came across a design decision that makes me nervous. As with any web framework, there are facilities for getting strings from the user. Unfortunately, Snap does not use types to distinguish between user-provided strings (dirty) and programmer-provided strings (clean).

Why does this matter? Segregating user input into its own type is a formidable defense against (say) SQL injection, since it obviates that "select * from myData where foo='" ++ userInput ++ "'" isn’t well-typed (presumably SQL code should be its own type, say, SQLString, and the function UserString -> SQLString should be some kind of escape routine). It would be nice to see framework support for this types-based defense.

The most obvious example of this is in getParam, which simply returns a Maybe ByteString.

Another example is provided by getSafePath and fileServeSingle. The former returns a FilePath provided by the user (a “safe” path, which — looking at the source — means that the “/../”‘s get removed), and the latter takes a FilePath and opens the corresponding local file. I suppose the idea is that the code

do p <- getSafePath
   fileServeSingle p


shouldn’t escape the implied sandbox of the file system. Of course, if the application has tighter requirements than this, the type system isn’t there to help out. (For instance, perhaps a path is considered “safe” if it excludes certain keywords in addition to the constraints imposed by getSafePath).

A natural work-around is to build an application-specific wrapper around Snap, and perhaps this is the better approach; I’m not yet sure.

Conclusions

I’m glad that Snap has been announced, as it has proven interesting to look at. Of course, Haskell already has (at least) two other web frameworks (yesod and happstack) and it’s not clear which will win-out in mindshare, nor is it obvious (to me, anyway) which one would be the best choice for someone wanting to sit down and make a site. Of course, it’s possible that some mix-and-match might be the best approach: the web server of one project, the HTML generation of another, and the persistent storage of the third. (This possibility deserves some consideration, especially as projects like BlazeHTML really take off.) Hopefully in the coming months we’ll see more high-powered applications of these frameworks, giving us a fountain of lessons we can capitalize on, and providing some compelling show cases of Haskell’s power as a web development language.

Still solving string injection: first impressions of Kaminsky’s Interpolique

This past week Dan Kaminsky announced Interpolique, a technology for dealing with string injection problems in web applications. The basic idea is pretty sharp: instead of writing (say) PHP code like

$conn->query('insert into posts values($_POST[author] , $_POST[content] );');


we write

$conn->query(eval(b('insert into posts values(^^_POST[author] , ^^_POST[content] );')));


The b function is provided by interpolique. It essentially translates the input string into some PHP code (which is then reified using eval) that base64 encodes the user-input and wraps that encoding up in a call to the MySQL function for base64 decoding.

The idea is that the resulting query is given to MySQL in a format where the user input is base64 encoded. As Dan points out, there aren’t any known injection techniques that can escape the MySQL base64 decoder, and the decoder won’t try to evaluate the resulting string as a SQL expression, so no injection is possible.

I have mixed feelings about this approach. On the one hand, it’s really just another form of escaping (instead of inserting a bunch of \‘s into the string, we’re base64 encoding it), and escaping is an error-prone thing. After all, there’s nothing preventing a tired developer from accidentally mixing some $ in with their ^^, nor could there be — if the developer writes $ instead of ^^, PHP will interpolate the string before passing it off to the b function, so no run-time check will be able to save the day.

(I’m not elated about the use of eval, but (a) I see no way around it if the plan is to use a syntactic approach, as is currently the case, and (b) the only vector I can see for attacking it requires a programmer to leave out the call to b, which is something they’d likely catch during development unless they also used $ instead of ^^, and that double-accident seems unlikely, barring a stupid refactoring snafu.)

On the other hand, if this technique is applied correctly, it seems likely to be robust (peer review should weigh in on this pretty quickly).

When I look at interpolique, I see the next generation of escaping: if you forget to do it you’re screwed, but if you do it correctly you’re safe. interpolique’s contribution is that its style of escaping is much simpler than trying to scan strings for dangerous characters, hence less likely to contain silly errors and edge cases, and that it is cross-language ready, in that base64 encoding isn’t target-language-specific (unlike escaping, which certainly is).

interpolique does not improve upon escaping biggest failure, though: if you’ve got 50,000 lines of PHP, the only way to know that interpolique (or escaping) is being used throughout is to look through the code. This is a PHP shortcoming, of course. We could certainly produce some static analysis tool to check for this design pattern, but then again, if writing tools that understand strings in PHP were easy we wouldn’t have the code injection mess in the first place.

Future direction

interpolique does provide a novel improvement for how to move data across the language barrier. This makes the core idea useful even in situations where programmers aren’t using PHP (or other half-brained-but-common-anyway languages).

In the long term, however, we still need to address the fact that we’re abusing the String type. User-input should be its own distinct type. The fact that this isn’t the case in .Net and Java completely explains why those type-safe languages don’t fare any better than PHP in terms of code injection.

Following the interpolique idea, the only function from UserString to String could be a base64 encoder. Languages could provide syntactic sugar to allow things like

$conn->query('insert into posts values($_POST[author] , $_POST[content] );');


to implicitly denote the interpolique style, thereby preserving type-safety (in this case, separation of user-input from SQL code) without compromising string interpolation style.

(Of course, both of these ideas are already possible in Haskell using algebraic data types and Template Haskell, but this is of little comfort to the vast majority of programmers since (a) most haven’t heard of Haskell and (b) Haskell is still in its web-development-language infancy.)

Moving forward I am interested in seeing whether interpolique passes peer review (probably will), becomes a common practice and reduces the incidence of code injection. Regardless of how these questions fare, the core idea is elegant, doesn’t seem to have a performance penalty, and can likely be carried forward fruitfully in future technologies.

Optional class constraints in Haskell

Work on my Haskell EDSL is moving ever onward. Today I want to talk about a trick I found while working on it. (Along the way I’ll make some allusions to the EDSL, but I want to forestall announcing the EDSL for another week or so, in the interest of ensuring it’s fully baked.)

(more…)

Polymorphic first class labels

(This post uses GHC 6.12.1)

The expression “first class labels” refers to the idea that, for record data types, one should be able to pass around the labels just as they would any other type. For instance, if I have a record like

data Foo a b = { biz :: a, baz :: b }


the value biz shouldn’t just denote the function biz :: Foo a b -> a, but should also be usable as a way of updating records, that is, a function like biz' :: Foo a b -> a' -> Foo a' b.

The Mythical Haskell’ includes some proposals for updating the records system with features aimed at supporting this idea, but for the time being, many people prefer to use fclabels, which achieves much of this magic using Template Haskell.

Recently, while working on an EDSL, I found myself wishing I had first class labels. I ran into a problem, though, which (along with solution) I’ll now describe.

Consider the following code:

module Label where

data Foo a b = Foo a b deriving Show

updatea :: a' -> Foo a b -> Foo a' b
updatea a (Foo _ b) = Foo a b

updateb :: b' -> Foo a b -> Foo a b'
updateb b (Foo a _) = Foo a b

worksFine foo0 = let foo1 = updatea 'a' foo0
                     foo2 = updatea "a" foo1
                 in foo2

Here I’ve defined a data structure Foo with two fields, along with a pair of functions for updating these fields. Then I defined a function worksFine which uses updatea to modify a Foo.

Obviously I could also write the following function:

worksFine' foo0 = let foo1 = updateb 'a' foo0
                      foo2 = updateb "a" foo1
                  in foo2


which is exactly the same, except that it uses updateb instead, thereby modifying the other field in Foo.

So now we have an obvious place to generalize: instead of having both worksFine and worksFine', why not have a single function which takes the updater as a parameter?

If we try it out, the first attempt looks like this:

trouble u foo0 = let foo1 = u 'a' foo0
                     foo2 = u "a" foo1
                 in foo2


Only trouble is that this fails to type check:

    Couldn't match expected type `[Char]' against inferred type `Char'
      Expected type: [Char] -> t1 -> t
      Inferred type: Char -> t2 -> t1
    In the expression: u "a" foo1
    In the definition of `foo2': foo2 = u "a" foo1

The problem is that trouble doesn’t believe that the argument u is polymorphic enough. This is a typical rank-2 issue: we don’t want trouble to bind the type variables in the signature for u.

Using rank-2 types, we can get very close to a solution. We can write the functions

alsoWorksFinea :: (forall a a' . a' -> Foo a b -> Foo a' b)
               -> Foo a b -> Foo [Char] b
alsoWorksFinea u foo0 = let foo1 = u 'a' foo0
                            foo2 = u "a" foo1
                        in foo2

alsoWorksFineb :: (forall b b' . b' -> Foo a b -> Foo a b')
               -> Foo a b -> Foo a [Char]
alsoWorksFineb u foo0 = let foo1 = u 'a' foo0
                            foo2 = u "a" foo1
                        in foo2

but neither is able to accept both of our update functions, even though each function has exactly the same body. Worse, I wasn’t able to find a sufficiently general type signature that would allow me to have one function which would be able to accept both update functions.

Luckily, where rank-2 types have failed me, type families have saved me. Any time you need more flexibility in your type signatures than the syntax will allow, you might be in a box where type families are the way to go. Here’s what it looked like in my case.

First I defined some typed to represent the two fields of my Foo structure:

data A = A
data B = B


Obviously I can pass around these values in a first-class manner, no trouble at all.

Then I defined a class for describing updating and getting:

class Field f x y where
  type Updated f x y
  update :: f -> x -> y -> Updated f x y
  type Gotten f y
  get :: f -> y -> Gotten f y

Now there are two instances to give, one for each field in Foo:

instance Field A a' (Foo a b) where
  type Updated A a' (Foo a b) = Foo a' b
  update A a' (Foo a b) = Foo a' b
  type Gotten A (Foo a b) = a
  get A (Foo a b) = a

instance Field B b' (Foo a b) where
  type Updated B b' (Foo a b) = Foo a b'
  update B b' (Foo a b) = Foo a b'
  type Gotten B (Foo a b) = b
  get B (Foo a b) = b 

And we’re basically done. We can now write the function that started this whole mess:

shouldWorkFine f foo0 = let foo1 = update f 'a' foo0
                            foo2 = update f "a" foo1
                        in foo2

GHCi is able to give us a very promising type signature for it:

> :t shouldWorkFine 
shouldWorkFine
  :: (Field f [Char] (Updated f Char y), Field f Char y) =>
     f -> y -> Updated f [Char] (Updated f Char y)

While this technique introduces type classes and type families into our program (something which can make typing troublesome in other areas), it delivers something I don’t know how to otherwise get: polymorphic first class labels.

Clearly the next step is to implement a library like fclabels which uses Template Haskell to define instances of the Field class.

Some weird interactions between Monomorphism Restriction and Template Haskell

Today I’m going to look at a weird issue I encountered this past weekend while working on a DSL in Haskell.

I’ll start with the code. As this example uses Template Haskell, we need to have the source broken up into two files:

Testa.hs:

{-# LANGUAGE
        TemplateHaskell #-}
module Testa where

import Language.Haskell.TH

someth = [| () |]

unit = ()

mrIssue :: (Monad m) => b -> m b
mrIssue = return

Testb.hs:

{-# LANGUAGE
        NoMonomorphismRestriction,
        TemplateHaskell #-}
module Testb where

import Testa

g = $(someth)
foo1 = mrIssue $(someth)

f = ()
foo2 = mrIssue ()

h = unit
foo3 = mrIssue unit

Now, if we fire up ghci Testb.hs, we get the following:

$ ghci Testb.hs 
GHCi, version 6.10.4: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
[1 of 2] Compiling Testa            ( Testa.hs, interpreted )
[2 of 2] Compiling Testb            ( Testb.hs, interpreted )
Loading package syb ... linking ... done.
Loading package array-0.2.0.0 ... linking ... done.
Loading package packedstring-0.1.0.1 ... linking ... done.
Loading package containers-0.2.0.1 ... linking ... done.
Loading package pretty-1.0.1.0 ... linking ... done.
Loading package template-haskell ... linking ... done.
Ok, modules loaded: Testb, Testa.
*Testb> :t foo1
foo1 :: (Monad m) => m ()
*Testb> :t g

:1:0:
    Ambiguous type variable `m' in the constraint:
      `Monad m' arising from a use of `g' at :1:0
    Probable fix: add a type signature that fixes these type variable(s)
*Testb>

Notice that, while we’re able to get the type for foo1, for some reason g is ill-typed with an ambiguous type variable in the constraint Monad m. The only problem, of course, is that when we look at our source we don’t see any way in which the type for g should have this constraint!

So maybe the problem is that g needs a type signature. But if we go in and modify Testb.hs, giving it

g :: ()
g = $(someth)

then we get the following from ghci:

Testb.hs:10:7:
    Could not deduce (Monad m) from the context ()
      arising from a use of `mrIssue' at Testb.hs:10:7-23
    Possible fix:
      add (Monad m) to the context of the type signature for `g'
    In the expression: mrIssue ($someth)
    In the definition of `foo1': foo1 = mrIssue ($someth)
Failed, modules loaded: Testa.
*Testa>

So now it's upset about the type for foo1. Fine. Let's give it a signature as well:

g :: ()
g = $(someth)
foo1 :: (Monad m) => m ()
foo1 = mrIssue $(someth)

Now we get a new error from ghci:

Testb.hs:11:0:
    Contexts differ in length
      (Use -XRelaxedPolyRec to allow this)
    When matching the contexts of the signatures for
      g :: ()
      foo1 :: forall (m :: * -> *). (Monad m) => m ()
    The signature contexts in a mutually recursive group should all be identical
    When generalising the type(s) for g, foo1
Failed, modules loaded: Testa.

If we add RelaxedPolyRec to our list of LANGUAGE extensions, the problem does, indeed, go away. In this case, we can even remove our type signature for g or for foo1, but not both -- we need to have at least one of them present.

Lastly, if we go back to our original source given above, but replace the signature for mrIssue with

mrIssue :: b -> IO b
mrIssue = return


then we can remove the NoMonomorphismRestriction, and everything works just fine (we can :t g and :t foo1 without any problems).

I'm entirely unsure of what's going on here. Any theories?

Kinetic source release

I’ve received a request to release the source for Kinetic, a project I worked on in Haskell around the winter of 2006 (iirc). There are two reasons why I’ve put this off:

  1. This was one of the first projects I worked on in Haskell, and the source shows that. My experience has been Haskell is often criticized based on the quality of code produced by its n00bs. This is an unreasonable thing to do (imagine judging a unicycle based on how well someone can ride it on their first go!) but I see it often none the less. I hope that this release does not lead to more of this nonsense.
  2. The project had ambitious goals that I never had the time to pursue (I’m sure many hackers know that feeling…) I’m really not interested in hearing about how I didn’t deliver on that. It’s just something I was working on when I was in college, you dig?

I’ve uploaded a snapshot of my development directory here. The build process attempts to download the source to ghc-6.6 and build it locally for use in the construction of the kernel. It will also try to find (using very basic means) the object files for many non-system C routines used to support the GHC runtime.

The Makefile should be able to produce a bootable CD ISO that can be used with VMWare. The operating system includes a driver for the VMWare graphics adapter, which it will assume is what the host system provides (so it probably won’t get very far in Bochs or qemu).

Of course, when I tried building it on my current machine, the build failed in ghc-6.6. I know that I was working on replacing the GUI with a console-based shell at some point; it’s possible that the source I posted is somewhere in the middle of that, and won’t build as a result. I’ll investigate this more when I get a chance.

I’d be happy to answer any questions about the system as best as I can. Happy hacking!

GHC as the basis for an operating system

Today’s post is more of a “thinking out loud.”

A few years back I started working on an “operating system written in Haskell. The code drew on some C++ that I had already written for dealing with CPU-level data structures, together with some new Haskell code I had written for interfacing with it. I wound up leaving the project to rest soon after that, more or less because I didn’t like the way the code was turning out. I’d later look back and realize that my haskell-foo just wasn’t up to the task of writing the code in good style (I’m planning to release the source this weekend, so you’ll get a chance to see what I mean).

Recently I learned that House, a Haskell-based OS project that preceded my own, is once more in active development. This is good news for two distinct reasons:

  1. It was an interesting project that accomplished much more than I managed to, and
  2. If I ever find the time to work on an operating system again, there’s a project to contribute to rather than re-invent.

All of this made me wonder, though: what would it take to make GHC itself bootable? It’s already the standard compiler; more or less everything works with it. Every day Hackage grows with more software that works in it. At some point, doesn’t it make sense to just boot to GHC?

How would it be done? Perhaps in much the same way as I made Kinetic bootable: create a stripped down POSIX environment, include whatever standard libraries are needed to support the thing, and run Bochs until the kinks get worked out.

What do you think?