Javascript syntax highlighting for Haskell code

Lots of time passed since my last post. I've been busy but this week I got sick and had some time to hack a bit.

As I said in my last post, I was sick of Blogger's way of indenting my Haskell code. I was on the verge to move to wordpress.com, which provides seamless support for the excellent syntaxhighlighter. Too bad, syntaxhighlighter doesn't provide Haskell support out-of-the-box.

Hence, I decided to write one myself. Go get it! Then, follow these instructions to get it to work with Blogger.

Here's an example of what it can do:

{-dfhc: by jAS 000807-}

module Import (importOne) where

import IO
import PackedString(PackedString,packString,unpackPS)
import Flags
import OsOnly(fixImportNames,isPrelude)
import Extra
import Syntax(Module,ImpDecl,Type,Decls,Decl,FixId,InfixClass(..),Simple,
  Context,Constr)
import Lex(Lex)
import TokenId(TokenId(..),tPrelude,rpsPrelude,extractV)
import ParseCore(Parser(..),ParseBad(..),ParseError(..),ParseGood(..),
  ParseResult(..),parseit)
import ParseI
import Lexical(PosToken(..),PosTokenPre(..),LexState(..),lexical)
import State
import Error
import IExtract
import ImportState(ImportState,putModid2IS)
import IntState(dummyIntState)
import PPSyntax(ppModule,ppDecl,ppDecls,ppImpDecls,ppInterface,ppFun,ppClassCodes)

#if !defined(__HASKELL98__)
#define ioError fail
#endif

openImport:: Flags -> PackedString -> IO (String,String,String)
openImport flags mrps =
 catch
  (do
   (fstr,finput) <- readFirst filenames
   if sImport flags
    then hPutStr stderr
      ("Importing module "++mstr++" from "++fstr++".\n")
    else return ()
   return (mstr,fstr,finput))
  (\err -> ioError (userError (can'tOpenStr mstr filenames err)))
 where
 isUnix = sUnix flags
 preludes = sPreludes flags
 includes = sIncludes flags ++ preludes
 mstr = (reverse . unpackPS)  mrps
 filenames =
  fixImportNames isUnix mstr
   (if isPrelude mstr then preludes else includes)

readFirst:: [String] -> IO (String,String)
readFirst [] = hPutStr stderr "Fail no filenames, probably no -I or -P" >> exit
readFirst [x] = do
 finput <- readFile x
 return (x,finput)

Of course, you can help improve it! While waiting for me to setup a page for this (which could take foerever), patches and comments are very welcomed!

Sick of Blogger

And yes! I'm sick of Blogger... going to change that really soon...

More on Python 2.5's generators

The implementation I proposed is actually flawed. No sooner than I wrote it, I noticed that the value returned after a send call doesn't depend on the value passed to send itself.

Why? Let me explain the situation. First, let's call the "sender" the function calling send, and "recipient" the function calling the yield.

The recipient's yield call is:

y <- yield x

Conversely, the sender's call is:

x <- send y

Can you see the point? x depends only on what happened in the receiver's past, so it can't depend on y, which is actually in the receiver's future. The same happens to the sender. So:

bar = do x <- yield 1
         yield $ x+5

foo = do y1 <- send 1999
         y2 <- send 100
         return [y1,y2] 

returns [1,2004]. That's not the way a Python 2.5's iterator works. Actually, such an iterator can't work at all!

If you can't believe this, try and run the equivalent piece of code in a Python 2.5 interpreter:

def bar():
  x = (yield 1)
  yield x+5

def foo():
  it = bar()

  y1 = it.send(1999)
  y2 = it.send(100)

  return [y1,y2]

You'll get the following error:


TypeError: can't send non-None value to a just-started generator


That simply means that you can't call send() if haven't previously called next(). That's exactly the same reason why my implementation was wrong: the semantics of send() says that the value returned by it must depend on the value passed to it. But, in the first yield() this semantics can't be fulfilled because the value passed to the yield depends only on the past in which, for the first call, can't include the value passed to send().

On subsequent calls, how can Python assure the semantics of send()? The answer is both easy and surprising: the value returned by send() depends on the next yield(), for which that value is actually in its past!

The solution I come up with is rewriting the send function and writing a next in this way:

next = do (RP (y,_)) <- get
          return y

send x = do (RP (_,f)) <- get
            let rp@(RP (y',f')) = f x
            put rp
            return y'

Now it works as expected. Notice that, surprisingly, the semantics of send/next depends only on send and next implementation: the yield function is completely apart from it.

Python 2.5's iterators in Haskell (sort of)

DISCLAIMER! The code I present here is likely to be far from perfect and in fact I ask for comments from the community, specifically on how to get rid of the "RecPair" user data type.

Is it possible to mimic Python 2.5's iterators in Haskell? If you don't
know what iterators are (or you're used to 2.4's ones), have a look to PEP343.
By and large, iterators are Python's way to surrogate continuations, which
represent a more general concept usually found in FP languages.

Basically, I want to be able to write something like:


bar = do y <- yield 1
yield (y+2)


and have bar return immediately the argument in a yield call to the caller. Yet, the caller should look like:


foo k = do x <- send undefined -- this will be ignored
y <- send k
return $ [x,y]


First two considerations:

• It natural to use the Cont monad when implementing the yield function.


• As two successive calls to send may have different outcomes, some sort of state must be involved. For the basic implementation we resort to State monad.

When trying to solve the puzzle, I stumbled upon a beautiful and straightforward implementation of Python 2.4's iterators by David Menendez. The problem of extending his approach to 2.5 iterators turned out to be a bit more difficult. First, I'll show you the code:


module Main where

import Control.Monad.Cont
import Control.Monad.State

data RecPair a b = Nil RP (b,a -> RecPair a b)

yield x = Cont $ \k -> RP (x,k)

send x = do (RP (y,f)) <- get
put $ f x
return y

runYield it cl = evalState cl $ runCont it $ \_ -> Nil


Let's discuss the yield funtion's implementation. First, as we're working
in the Cont monad, we must return a Cont value which is basically a
function taking a continuation (what to do next) and build a pair (x,k).

x is the value passed to the yield function and then returned to the
caller.

What about k? In my mind, k is a function taking an argument (the
receiving variable of a '<-' statement in a do-block) and returning another pair (x',k'), which is the result of the next small step of the Cont computation, till the next yield call. In this way, a computation can't go on after a yield statement until you feed it with a value through a send call, which is the semantics of iterators. Naively, at start I wrote: yield x = Cont $ \k -> (x,k)

But ghc promptly issued the following error:


Occurs check: cannot construct the infinite type t = a -> (t1,t)


What's going on? Let's try and do some type analysis:

1. The type of "\k -> (x,k)" is "t -> (b,t)" which is perfectly right, as long as "x" is in the scope of that definition and is of type "b".


2. But, the argument of "Cont" must have type "(a -> r) -> r".


3. Let's do the bindings: "t = a -> r" and "r = (b,t)".


4. Substituting the latter in the former we obtain "t = a -> (b,t)".

This equation is clearly impossible to solve (no types exist to make the
equation true) and the Haskell's type system did his job.

How to escape the problem? The real point here is that the above type
equation can be expanded infinitely. There must be a way to stop the
expansion. What if "r" would be masked by an opaque type?

Enter RecPair. We turn the above equation into:


t = a -> RecPair a b


which is perfectly solvable provided there are instances of the type
"RecPair a b". In the above snippet you can find a convenient definition of
RecPair which is suitable to our goal. There are other, like:


data RecPair a b = Nil RP (a -> (b,RecPair a b))


which turns out to be less elegant when you modify yield and send
accordingly.

The other part of the code is just plain Haskell code. Notice that solution
I proposed doesn't mimic completely Python 2.5's iterators: for example,
send can't deal with more than one iterator at the time due to the use of the State monad.

But these are only technicalities which can be easily overcome, for instance,
using the IO Monad and a couple of IORef here and there.

syb-with-class 0.4 for HAppS

While I was trying to compile HAppS, I needed version 0.4 the syb-with-class package, which is not in the HackageDB (yet, I hope). I had to grab it from:

darcs get http://happs.org/HAppS/syb-with-class

Hope this will help anyone trying to compile HAppS.

Xmonad side bye side KDE

As you may know, I recently switched to ArchLinux... those guys are doing an excellent work and, after some months, I got completely addicted to that kdemod thing... I missed Xmonad though, which jumped from 0.2 to 0.5 in the meanwhile and I badly wanted to give it a try and test out the new features...

What to do? Well, it's indeed possible to run xmonad and kde side-by-side on the same PC. You could fire up a new Xserver on a different display but switching between them may not be fast enough.

Instead, my solution relies on Xnest, an X server running in a window of another X server.

Here's the command line I use:

kstart --desktop 2 --fullscreen -- xinit ~/.xinitrc.xmonad -- /usr/bin/Xnest :10 -geometry 1600x1200 -ac

where .xinit.xmond simply contains:

/usr/bin/xmonad

The command will open a new full-screen Xnest window, with no window decoration, on virtual desktop number 2. Now, you can use the usual shortcuts to switch between virtual desktops to go back and forth KDE and Xmonad.

Best of the two worlds!

UPDATE! Too bad, cut&paste doesn't work between Xnset and the real X server beneath. Any hints?

More on Point-Free Programming Style

I discovered that programming in Point-Free Style can be addictive! Today, I wrote two perverse functions using PFS before discovering I had spent almost two hours just two add two lines to my code!!!

Here's the one of the two:

foo = uncurry (.) . (map . second . drop . length &&& (filter . (flip $ flip isPrefixOf . snd)))

Sorry if it didn't fit in your screen. I used the name foo purposedly: can you imagine what this function does?

If you can't come up with a solution in less than 1 minute, the above code is a failure as it means nothing to you (i.e. its meaning is not apparent).

Try with the following version:

foo p [] = []
foo p ( (k,l):os ) | p `isPrefixOf` l = (k,take (length p) l) : foo p os
| otherwise = foo p os

Sorry for the bad layout.

It took two hours to me to figure out how and where to put all those . and $ in the first version but it was fun, just like winning a game.

On the other hand, I wrote the second version as I was writing this post. I think the reason why I write PFS code much much slower lies both in my lack of knowledge of PFS programming and my way of reasoning about programs.

Nevertheless, PFS is appealing to me because I'm used to write shell scripts to automate things on the systems I manage: PFS is all about composing and piping functions, mostly like you compose and pipe shell programs.

I wonder if I'll be able to guess the meaning of the PFS functions I wrote after some months: we'll see.

As a side note, I noticed that the following pattern is coming up rather often when coding in FPS:

goo = uncurry g . (foo &&& bar)

which means:

goo i = foo i `g` bar i

So, I wonder whether the following combinator would help to making FPS code more readable:

f `interspersedBy` g = uncurry g . f

So, the above snippet would become:

goo = (foo &&& bar) `interspersedBy` g