Explaining the Prompt monad with a clearer representation

The MonadPrompt package is tricky to understand, as it uses a continuation-based representation. This post explains the Prompt monad with a clearer (though less efficient) representation.

Introduction to Prompt

When programming in Haskell, you want to keep code as pure as possible. This may be dogmatic, but it's valuable, and doesn't come automatically. Consider a simple chat server, where the code to handle a client has type:

serve :: ServerEnv -> ClientInfo -> IO ()

Implementing serve, and using it correctly, can be quite daunting, as several factors come into play:

• Concurrency - When the client sends us a message, we have to notify all the other server threads. When someone else sends us a message, we have to be notified.

• Exception safety - When the connection dies, we have to remember to remove our client's entry from the server's list of clients. If another thread might kill this one (e.g. a user connects from somewhere else), we have to make sure that we are prepared to receive an exception at any point.

• Windows - GHC currently does not have good IO support on Windows. If our server is running on Windows, and a client connection hangs, using killThread on the thread blocked on IO will not kill it. Quite the opposite: the thread calling killThread will block, too!

All of these problems are IO-related. Now consider a simpler example, a web server whose main function is:

serve :: Request -> Response

This is much easier to deal with. When implementing serve, we don't have to worry about concurrency, exception safety, or Windows. When calling serve, we don't have to worry about it hanging due to a bad network connection ¹.

But what if serve needs to read a file from disk?

The idea behind the Prompt monad is to have a pure function return an action it would like the caller to perform. To illustrate the concept, let's extend serve so it can ask to download a file:

serve :: Request -> Prompt

data Prompt = ReadFile FilePath (String -> Prompt)
            | Answer Response

Now serve is allowed to "perform" a carefully-chosen set of IO actions, and the caller has full control over how it happens.

The Prompt monad

A Prompt monad is described in The Monad.Reader Issue 15, and implemented in the MonadPrompt package. It handles the plumbing for us, and lets us define a type for requests. Each request may have a different return type, so we'll want to define our request type as a GADT:

data Request a where
    GetLine  :: Request String
    GetChar  :: Request Char
    PutStrLn :: String -> Request ()
    Print    :: Show a => a -> Request ()

If you are not familiar with GADTs, see the Monad.Reader article for more information.

Here's one possible implementation of the Prompt monad:

data Prompt p r
    = forall a. Ask (p a) (a -> Prompt p r)
    | Answer r

instance Monad (Prompt p) where
    return              = Answer
    Ask req cont >>= k  = Ask req (\ans -> cont ans >>= k)
    Answer x >>= k      = k x

prompt :: p a -> Prompt p a
prompt req = Ask req Answer

runPromptM :: Monad m => (forall a. p a -> m a) -> Prompt p r -> m r
runPromptM perform (Ask req cont) = perform req
                                >>= runPromptM perform . cont
runPromptM _       (Answer r)     = return r

A Prompt p r computation either has a value r, or needs some action p a to be performed before it can continue:

This is in fact the original formulation of Prompt. Unfortunately, left recursion of >>= takes quadratic time to evaluate (thanks for pointing this out, ryani).

Let's compare the formulation above to MonadPrompt's runPromptC function, and see how we'd implement it in terms of Ask and Answer:

runPromptC :: (r -> b)
           -> (forall a . p a -> (a -> b) -> b)
           -> Prompt p r
           -> b
runPromptC onAnswer onAsk p =
    case p of
        Ask req cont -> onAsk req $ runPromptC onAnswer onAsk . cont
        Answer r     -> onAnswer r

The interesting wrinkle is that we embed a recursive call inside of the continuation passed to onAsk. Thus, the caller does not have to do its own recursion. This simplifies the implementation of runPromptM, for example:

runPromptM :: Monad m => (forall a . p a -> m a) -> Prompt p r -> m r
runPromptM prm = runPromptC return (\p cont -> prm p >>= cont)

So while MonadPrompt's continuation-based representation may be harder to understand at first, it is more efficient, and perhaps even easier to use.

Takeaways:

• MonadPrompt uses a continuation-based representation to avoid a performance issue. The Ask/Answer formulation, however, may be easier to understand.

• A library implementing a network protocol should export a pure API (perhaps in addition to impure convenience functions), so the user can deal with concurrency, exception safety, and Windows on their own terms.

---

1. Actually, evaluating serve :: Request -> Response might hang if the Request contains lazy IO. In this case, it's not serve's fault, but the fault of whatever is producing the data.↩

Alien computer system

Abduction

Suppose you are abducted by aliens at a surprisingly convenient time, and they show you their alien computer (which they have localized for humans) and how they use it. Fascinated, you see that "files" and "directories" as you know them simply don't exist on the alien system. Perhaps they're working with "lists", "collections", and "cells" instead. Instead of creating documents in applications, they're putting together machines from interchangeable parts.

Most importantly, you notice that the aliens automate just about everything they do. They build mini-programs to do things rather than just doing them. Why? Well, this layer of abstraction means they never have to "undo"; they just tack on more machinery to short-circuit what they had before, and if they want to "redo", they just short-circuit the short-circuit. As you watch, you ponder the distinction between a "user" and a "programmer", wondering if it even exists on the alien homeworld.

On day two (after having eaten the best replicated chicken teryaki dinner orbiting earth and well-rested from zero-gravity sleep), you continue watching them play around with their on-screen contraptions, and you find that certain things show up over and over again. Sort of like how Earth computers have windows, icons, menus, and the pointer, you see a lot of the same things over and over again on the alien system, but they seem to have much more to do with semantics than with presentation.

By the end of the week, you've been using the alien computer and have gotten the hang of it. You learn to do some really advanced things, and the aliens are astounded by your progress. Moreover, some of the things you're doing on the alien system in minutes would be month-long projects on Earth computers.

However, you still can't do the vast majority of things you could do on your Earth computer, such as browsing the web, writing documents, managing files, etc.. Also, if other humans saw you working on the alien computer, they'd be just as clueless as when you looked over the aliens' shoulders the first day. Practically speaking, these alien computers would be completely useless to most humans.

Back on Earth

You are returned to Earth (with some cash and leftover teryaki chicken for compensation) and go back to your daily activities. However, you can't shake the feeling that there might be a radically better way to do computing that only takes a week to learn (if you're a fast learner). But, bringing "computer programming" into the user experience just seems like the wrong way to go in terms of making something both user friendly and easy to learn. Then again, you cannot deny the fact that computers are really hard to learn anyway.

I believe that learning how to become a computer "user" isn't easier than learning a programming language, but actually much harder (granted, you'll want to learn how to use a text editor and web browser before learning how to program).

Why, then, don't we teach grandma Python? I think it's because (most) users don't use Python to send and receive e-mail and browse the web. However, even grandma might find Python's interactive command line to be a handy desktop calculator... that is, until she tries to divide integers. The thing is, programming languages (well, except maybe the shell) typically don't make it easy to automate the day-to-day tasks of people who haven't devoted their lives to computing.

Higher-level programming-ish facilities integrated into operating systems would be useful to a lot of people, in my opinion. However, it would involve a learning curve, but users have to learn how to use computers anyway. Something can be simpler, yet harder to learn than something that is familiar.

Guppy: trying to make parsing simple, fun, and powerful

I've been working on designing a parser definition language called Guppy. I have not implemented it yet, as the syntax and semantics of it are a moving target subject to my whims.

The mission statement of Guppy is to make parsing simple, fun, and powerful. You give Guppy a grammar definition and an input string, and Guppy gives you an AST whose nodes are named after production rule symbols. Want to write a calculator? Define a simple, 20-line grammar to get started, and test it out with Guppy. Want to make your own extension to the C programming language? Import the "c" grammar (like you would import a library in scripting languages), and write only the parts that make your language different.

Here are a few examples of Guppy as I currently have it. The first example is the beginnings of a "standard library" for Guppy; a collection of rules that can be used without having to define them by hand:

alnum:    alpha | digit
alpha:    [A-Za-z]
ascii:    [\x00-\x7F]
digit:    [0-9]
extended: [\x80-\xFF]
lower:    [a-z]
space:    [\t\n\v\f\r ]
upper:    [A-Z]
xdigit:   [0-9A-Fa-f]

identifier:  (alpha | '_') (alnum | '_')*

number:  int | float
    int:
        dec:  [1-9] [0-9]*
        hex:  '0' [Xx] xdigit*
        oct:  '0' [0-7]*
    float:  dec | hex
        e:  [Ee] ('+'|'-')? [0-9]+
        p:  [Pp] ('+'|'-')? [0-9]+
        suffix:  [FLfl]?
        
        dec:
            [0-9]* '.' [0-9]+ e? suffix
            [0-9]+ '.' e? suffix
            [0-9]+ e suffix
        hex:
            '0' [Xx] xdigit* '.' xdigit+ p suffix
            '0' [Xx] xdigit+ '.' p suffix
            '0' [Xx] xdigit+ p suffix

The key features to note here are the use of nested production rules and lexical scope. If a series of rules are listed indented under a parent rule, the names of rules become available to the definition of the actual parent (as in the case of number: int | float). If the parent rule's definition is empty, it automatically defaults to |-ing its child rules (as in the case of dec:). Note that in Guppy (unlike other grammar definition languages like Yacc), empty strings must be explicit (as in, '').

Two more candidate rules to add to Guppy's standard library are:

//C-style string literal
string(start_quote = '"', end_quote = start_quote)
        : start_quote char..end_quote
    char:
        literal: .
        escape:
            hex: '\\' [Xx] xdigit{1,2}
            oct:
                '\\' [0-3][0-7][0-7]
                '\\' [0-7][0-7]
                '\\' [0-7]
            unicode: '\\u' xdigit{4}
            backslash: '\\' .

//infix-delimited list with at least one item
list(item, delimiter = ','):
    item (delimiter item)*

This introduces functions. In this case, they're just used as templates for common tasks. However, using functions recursively makes it possible to define non-context-free grammars (perhaps even Turing-complete ones). Whether Guppy will ultimately allow that or not, I'm not sure.

Isolated production rules

I've also been thinking about how the traditional notions of lexer and parser can be united under one grammar formalism. I thought about how a formal grammar defines a program that outputs valid strings in a language, rather than defining the steps needed to parse that grammar. Taking that further, if you wanted to write a program to output code in a programming language like C, you'd first emit the start symbol, then apply grammar rules. After that (as in, you'd stop applying rules from the grammar), you'd apply lexical rules to convert things like IDENTIFIER to complete strings.

What I came up with involves enabling the user to isolate production rules. The syntax is rather ad hoc, but it lets you take a symbol or string and apply production rules wrapped in parenthesis to it by saying text -> ( rules... ).

expr -> (
    expr: add_expr
    
    primary_expr:
        number
        identifier
        ( expr )
    
    multiply_expr:
        primary_expr
        multiply_expr '*' primary_expr
        multiply_expr '/' primary_expr
    
    add_expr:
        multiply_expr
        add_expr '+' multiply_expr
        add_expr '-' multiply_expr
    
    /* Note that number, and identifier aren't defined
     * in this scope, so they are "quasi-terminals".
     * Once we expand them using the production rules
     * below, there's no turning back. */
) -> (
    '': white
) -> (
    number:
        [0-9]+
        [0-9]+ '.' [0-9]*
        [0-9]* '.' [0-9]+
    
    identifier:
        [A-Za-z_][0-9A-Za-z_]*
    
    white:
        [\t\n ]
)

Ambiguity

There are a number of things I'm having trouble deciding on or understanding. For one, should ambiguity be allowed? Consider this much easier way of defining expr:

expr:
    number
    identifier
    ( expr )
    expr '*' expr
    expr '/' expr
    expr '+' expr
    expr '-' expr

The issue here isn't just that the order of operations isn't defined. Even if it could be indicated with a hint (as is done in Bison with %left, %right, etc.), the grammar here just isn't correct. If you say "1+2*3+4", you could follow the expr '*' expr expansion first, but it would yield an incorrect derivation. Another case is the ambiguity of + versus ++ in languages with that pre/postincrement operator:

(A|B)* -> (
    '' -> ' '
) -> (
    A: '+'
    B: '++'
)

The ambiguity is typically resolved by making the lexer greedy; "+++" means "++ +". However, this grammar allows us to derive "+++" as "+ ++", which is incorrect. Making this grammar unambiguous isn't exactly simple, so requiring the user to do so goes against Guppy's mission statement.

Indentation-based syntax

Another issue is: should Guppy use an indentation-based syntax or not? Should Guppy offer a non-indentation-based alternative? Consider nice and simple code like this:

number:  int | float
    int:
        dec:  [1-9] [0-9]*
        hex:  '0' [Xx] xdigit*
        oct:  '0' [0-7]*
    ...

If we had to do without indentation-based syntax, it might look like this:

number: { (int | float);
    int: {
        dec:  [1-9] [0-9]* ;
        hex:  '0' [Xx] xdigit* ;
        oct:  '0' [0-7]* ;
    };
    ...

Although indentation-based syntax makes the code look nice, it has a number of drawbacks. One major drawback is that the grammar of Guppy would not be context-free (I think), complicating the matter of defining Guppy in Guppy. Note that indentation can be invoked in Guppy using a recursive function:

node(indent = ''):
    indent value '\n'
    indent key ':' value? '\n' node(indent [\t ]+)

Again, whether or not this will be allowed, I'm not sure.

Idea: Centralized minimal effort bug reporting

Suppose you are running Ubuntu, and for some strange reason, the cursor disappears intermittently. You don't know why, and you don't really feel like quitting what you're doing to probe into it.

If you were a Good, community-loving person, you might do this for every bug you encounter:

• Search for an existing bug report similar to your own
• Create an account on the project's bug tracking website (if they have one, otherwise, sign up with the project's mailing list)
• Go to your e-mail and click the confirmation
• Navigate through the bug reporting interface
• Find a way to consistently reproduce your bug
• Describe, in detail, what your bug is and how to reproduce it.
• Wait for a response
• Attach more information
• Recompile the program in question with a patch you receive
• Describe more details

In short, reporting bugs is a painstaking process. That's why I, for one, rarely ever do it.

Wouldn't it be great if you could simply go to one website and fill out a form like this? :

Project(s): Ubuntu, GNOME, Xorg, Compiz
Description: Cursor disappears intermittently. It's kind of annoying. Someone else borrowing my computer noticed it, and it's kind of an embarrassment. Pls fix kthx.

That's all you really care to say (you don't even need to say that much). Just click submit, and go back to what you were doing. If you really feel like following it, you can bookmark the link to the bug ID (e.g. example.com/1gaf35 ). Less lazy people might search through the bug reports and mark yours as an instance of theirs, giving it more weight. Developers might respond on the website so you (and other victims) can see how progress is coming along.

Comments?

What is the worst feature of C?

This was a question on the Google Summer of Code application template for the CCAN (Comprehensive C Archive Network) organization.

C's problem is not a "feature" per se. To understand what is wrong with C, you have to ask why it takes six lines or more to do simple things like retrieve a single line from the console and convert it to an integer:

char buffer[32];
printf("prompt> ");
fgets(buffer, sizeof(buffer), stdin);
if (*buffer==0 || *buffer=='\n')
    break;
num = atoi(buffer);

By comparison, in Perl it'd be:

num = int(<>);

C suffers from stagnancy. If one wants to create a directory, he/she or he\she has to worry about conflicting standards. Functions for creating and traversing through directories are not standardized across the major platforms. Unix doesn't even have a function call for copying a file (if you do it the manual way with fread/fwrite, that still doesn't compensate for sparse files). Even the language itself has similar issues. Can I use typeof or not? Is long 32 or 64 bits? Is long long even available? I need not discuss creating a window or displaying an Open dialog.

How do programmers deal with this? Most flock to Java, Python, and other low-performance languages. Others rely on toolkits such as Qt to abstract those details while sacrificing the portability of C. Few put up with it by learning the details, and even when they do, they end up with messy (and likely still incorrect) code.

Nevertheless, C has crucial benefits. It is the lingua franca of compiled programming languages. If you write a library in C, it can easily be adapted for use in C++, D, eC, etc.. Most importantly, C and its compile-to-machine-code brethren are fast. If you want an operating system package manager to be quick, you write it in C, not Python.

The reason it is so hard to program in C is because C has an inadequate, obsolete standard library. I believe CCAN, by providing a standard repository for C libraries (analogous to CPAN for Perl and Boost for C++), will soundly overcome this obstacle.

First!

I probably should have started a blog long ago. I've oft wanted to rant about random stuff, and I tended to dump my ideas into IRC and forums. Now that I have some necessity for a blog, a better understanding of what a blog is, and have noticed that many of my Google searches for help land me on blogs, I too have a blog that I hope will be useful to many.

I will probably talk mostly about programming (mainly C) and Linux, though other topics may come to mind. I will never ever cuss on this blog, nor do I plan to say anything worse than "crap" or "drugs". Feel free to let your mother, grandmother, kids, and teacher/boss who's standing right behind you read this blog (if they're interested).

To round up this post and to round up some hits, here's a simple routine in C for randomly scrambling an array:

void scramble(void *base, size_t nmemb, size_t size) {
    char *i = base;
    char *o;
    size_t sd;
    for (;nmemb>1;nmemb--) {
        o = i + size*(random()%nmemb);
        for (sd=size;sd--;) {
            char tmp = *o;
            *o++ = *i;
            *i++ = tmp;
        }
    }
}

Note that it has horrendous cache performance for large arrays.