Unifying Events and Threads in Haskell

[ Update: 3 May 2006: Source is now available ]

Lambda the Ultimate points to a great paper, A Language-based Approach to Unifying Events and Threads, by Peng Li and Steve Zdancewic.

This paper presents a language based technique to unify two seemingly opposite programming models for building massively concurrent network services: the event driven model and the multithreaded model. The result is a unified concurrency model providing both thread abstractions and event abstractions.

The paper is about the implementation of the unified concurrency model in Haskell. The threads are 'lightweight' threads and according to the paper scale to 10 million threads. The scheduler outperforms NPTL in I/O benchmarks.

• Monads provide the thread abstraction by defining an imperative sub-language of Haskell with system calls and thread control primitives.
• Higher-order functions provide the internal representation of threads in continuation passing style.
• Lazy data structures provide the event abstraction, which is a lazy tree that represents the trace of system calls generated by threads.

Some interesting benchmark results too. One benchmark test they did involved launching 10 million threads that just yield within a loop. This was running on a machine with 1GB set aside for the GHC heap. The per thread cost was only 48 bytes!

Their multiprocessor benchmark, yielded a 3.65 times speedup over a non-MP version version on a 4CPU machine (The library is able to take advantage of SMP machines).

Other interesting things in the paper are a web server they built using this framework and an application level TCP stack written entirely in Haskell.

I hope the source for the things mention in this paper becomes available. In the meantime, you can read it here.

Categories: haskell

Handling X-Forwarded-For in Yaws

I run a Yaws webserver behind a Pound proxy. This works really well but all the IP addresses logged by Yaws appear as the localhost (127.0.0.1). This is due to Yaws picking up the IP address of the proxy as it forwards the request.

Pound sends the original IP address as a header in the HTTP request called X-Forwarded-For. This finally bugged me enough to modify Yaws to display the X-Forwarded-For IP address if the header was there, otherwise display the normal IP address.

The 'quick hack' change was quite simple. I modified the 'include/yaws_api.hrl' file to add 'x_fowarded_for' to the 'headers' record:

-record(headers, {
   connection,
   accept,
   host,
   if_modified_since,
   if_match,
   if_none_match,
   if_range,
   if_unmodified_since,
   range,
   referer,
   user_agent,
   accept_ranges,
   cookie = [],
   keep_alive,
   location,
   content_length,
   content_type,
   content_encoding,
   authorization,
   transfer_encoding,
   x_forwarded_for,
   other = []   %% misc other headers
  }).

The idea being that this value will be set by Yaws when it first parses the HTTP request headers. This is done by modifying the http_collect_headers function in 'src/yaws.erl' to contain the following code:

{ok, {http_header, _Num, 'X-Forwarded-For',_, X}} ->
     http_collect_headers(CliSock, Req, H#headers{x_forwarded_for = X},SSL)

This was basically a copy and paste of the way the other headers are handled. In the code that handles the logging I just check for the header and output the IP address if it is there, otherwise use the IP address from the request itself. This is done by a helper function I added to 'src/yaws_server.erl':

x_forwarded_for_or_ip(Ip, Item)->
    case Item of
        undefined -> Ip;
        Item -> yaws:parse_ip(Item)
    end.

The 'Item' passed to this function is the 'x_forwarded_for' element of the 'headers' record. If the 'X-Forwarded-For' header exists I parse the string into an IP address using yaws:parse_ip/1.

All that remains is to change the maybe_access_log/3 in 'src/yaws_server.erl' to call this helper function:

     TrueIp = x_forwarded_for_or_ip(Ip, H#headers.x_forwarded_for),
     yaws_log:accesslog(SC#sconf.servername, TrueIp, User,
          [Meth, $\s, Path, $\s, Ver], 
          Status, Len, Referrer, UserAgent);

Now all my IP's appear correctly forwarded from Pound in the Yaws server.

Categories: erlang, yaws

Building wxFruit and Yampa with GHC 6.4.x

wxFruit is a Haskell GUI library based on Functional Reactive Programming concepts. It uses wxWindows as its underlying GUI framework. For FRP it uses the Haskell FRP framework Yampa.

Both libraries are relatively old and seem to have suffered bitrot as I couldn't get them to compile using a recent GHC build (GHC 6.4.x). A bit of searching came across this post to the haskell-jp list which had some patches to enable these to build. I've extracted the relevant patches here:

• afrp.diff
• wxfruit.diff

These can be applied by using 'patch' from within the original wxFruit and Yampa distributions:

cd afrp-0.4
patch -p1 <afrp.diff
cd ../wxfruit-0.1
patch -p1 <wxfruit.diff

Alternatively you can download the already patched versions I've made here:

• afrp-0.4-patched.tar.bz2
• wxfruit-0.1-patched.tar.bz2

To build and install the patched Yampa, the following should work:

cd afrp-0.4
runhaskell Setup.hs configure
runhaskell Setup.hs build
sudo runhaskell Setup.hs install

Once this is done the wxFruit paddle example builds with:

cd ../wxfruit-0.1
ghc --make -farrows -o paddle paddle.hs

Categories: haskell

Haskell Gameboy Emulator

OmegaGB is a Nintendo Gameboy Emulator written in Haskell. The author has a devlog where they are posting information about the implementation along with screen shots and source code.

Categories: haskell

jhc - Optimizing Haskell Compiler

jhc looks interesting. It's an optimizing Haskell compiler "...that aims to produce very efficient code as well as explore novel compilation techniques in an attempt to make them practical."

Two things from the site that interested me were:

• Produces 100% portable ISO C. The same C file can compile on machines of different byte order or bit-width without trouble.
• No pre-written runtime. other than 20 lines of boilerplate all code is generated from the Grin intermediate code and subject to all code simplifying and dead code elimination transformations. As a result, jhc currently produces the smallest binaries of any Haskell compiler. (main = putStrLn "Hello, World!" compiles to 6,568 bytes vs 177,120 bytes for GHC 6.4)

Categories: haskell

Jack Dempsey

Jack Dempsey was a famous boxer early in the 20th century. Today I got in the mail a DVD on Jack Dempsey's style of boxing made available by Kirk Lawson on rec.martial-arts.

The DVD is a garage training session led by Ken Pfrenger, a western martial arts instructor. Ken's 'western martial arts' interest covers early bare knuckle boxing, Irish Collar and Elbow wrestling and stickplay and Cornish Close Hugg wrestling amongst other things. Based on his knowledge of Dempsey and Dempsey's book and fights he led a session on some of his techniques and tactics. This is what appears on the DVD.

Some interesting stuff covered, including:

• Stance
• Center line theory and parrying
• The Jolt
• Trigger Step
• Shoulder Whirl
• The Surge, upper cut and shovel hook
• Feinting and drawing the punch
• The Double Shift
• The Corkscrew
• The Cross
• The Inside Triple
• The Outside Triple

As you can see early boxing had its own vernicular seperate from modern boxing. Even 'The Cross' is a different punch being much more like an overhand right.

The DVD is about 45 minutes of material - raw and relatively unpolished - but containing very interesting and useful content to the enthusiast of boxing's history and great fighters. Well worth the low price Kirk is selling them for.

It is interesting to compare the differences style of the early 20th century of boxing versus modern boxing. Dempsey advocated punching with the bottom three knuckles of the fist (vs modern boxing's top two) and many punches are done with a vertical fist.

The Jolt is a lead hand punch different from the modern Jab. The fist is vertical and the power is obtained from a drop step into the opponent.

Many of the punches derive power by rapidly rotating the shoulders, concentrating on bringing back fast the non punching shoulder and thrusting forward the punching shoulder - creating a rotational torque which pushes out the punching hand. This movement being called the 'shoulder whirl'. Described in Dempsey's book, Championship Fighting, as:

One shoulder whips forward while the other whips back. Muscles of the shoulders, back, stomach, legs co-operate in achieving the whirl. Also, the process is assisted by shifting the weight from one leg to the other. You need concern yourself only with the shoulder motions. Nature will supervise the assisting muscles and movements.

...

MAKE CERTAIN THAT YOUR SHOULDERS ARE DRIVING THE PUNCHES; THAT THE PUNCHES ARE NOT PULLING THE SHOULDERS.

According to the DVD Dempsey advocated a open hand position. Rather than keeping the hands in close to the head, protecting the chin. creating a shield like say Peek-a-boo boxing style or Rodney King's Crazy Monkey, they were kept more apart to create a target for the opponent and thus draw his punches to a known point. Parrying the punch then being as simple as a downward parry motion to bat the punch away or a stop-catch with the rear hand followed by a lead hand punch or jolt.

There's some nice coverage of the shovel hook to the body and the upper cut. The delivery style for the shovel hook being to keep the drop down from the knees, keep the elbow of the hooking hand close (or attached to) the hip and torquing with the hips to drive the punch. No movement of the hand or arm away from the hip.

Some nice links to Dempsey in action:

• Dempsey vs Bill Tate (Youtube)
• Jack Dempsey Highlight (Google Video)
• Jack Dempsey vs Jess Willard (125MB .mpg file, big download but great fight, originally from here)
• Web archive of some of Dempsey's book, Championship Fighting. If anyone has a copy of this book they'd be willing to part with or lend out let me know.

The video of Dempsey vs Willard linked above shows some obvious differences in rules compared to modern boxing. When a boxer is knocked down they get a ten count but the opponent can stand right over them and immediately hit them when they get up. There is no neutral corner rule. In this fight Willard is knocked down seven times in the first round.

Categories: martialarts

Playing with HAppS

I downloaded HAppS, the Haskell Application Server, I mentioned previously to try it out.

I already had GHC installed so I could build darcs but I needed a few additional packages to install HAppS. Most of these I obtained via apt-get but I had to manually install the following two:

• fps
• HaXml

Once they were installed compiling and building HAppS is done using the Cabal based setup file:

runhaskell Setup.hs configure
runhaskell Setup.hs build
sudo runhaskell Setup.hs install

Once that's out of the way I tried out the 'hello' example. This is located in the 'examples' subdirectory of 'HAppS' and needs to be built and run:

make
./hello

This starts up an application server listening on port 8000. Where to go from there in terms of building apps I'm not sure as there doesn't seem to be much 'how to' style documentation. Digging through the source and examples looks to be the next thing to try.

Categories: haskell

SISCweb v0.33 announced

Alessandro Colomba has announced the release of version 0.33 of SISCweb.

SISCweb is a continuation based web server written in SISC, a Scheme implementation that runs on the JVM.

New features mentioned in the release announcement include:

• A new module siscweb/image provides procedures to send images from java.awt.image.RenderedImage objects or from files.
• A new API wraps and "scheme-ifies" all methods on the Request, Response, Session and ServletContext objects. This makes it easier to access POST data through a scheme input port, or to set the response buffer size, or set Java or Scheme session attributes, for example.
• A new procedure forward/dynenv/store! can be used in place of the @href-p attributes or plain forward/store! when one desires to capture the dynamic environment of a closure, e.g. SRFI-39 parameters. Because SISC 1.13 solves a few serialization bugs, it is now possible to use SRFI-39 parameters in place of session attributes for tracking state. This is particularly useful in event-based programming (e.g. AJAX). See the Counter example code (no pun intended).
• Improvements to response writing improve performance for markup, graphviz, images.
• Improvements to XML/XHTML output.
• A new (backwards-compatible) API for siscweb/config.
• Updated documentation throughout.
• Some internal refactoring.

Categories: scheme

ZoomIn - NZ Mapping Web Application

I stumbled across ZoomIn today which is a New Zealand map site with lots of interesting features.

You can search with street addresses and get maps of pretty much all of New Zealand and explore via a Google Maps like interface. Included are optional aerial photographs of many of the regions. I like the way it uses Ajax to narrow down a search for an address as you type.

ZoomIn also provides the ability for users to comment on places, upload photo's and annotate in other interesting ways. A nice idea!

For developers they have a REST style API that allows searching for addresses programatically and retrieving the lattitude and longitude of the address found. Other API's seem to allow integrating map data into your own web apps.

Categories: misc

Haskell Application Server - HAppS

Haskell gets more interesting every day. In the Haskell Weekly News was an announcement of HAppS, a Haskell Application Server. A nice list of features:

HTTP Application Server

Performs better than Apache/PHP in our informal benchmarks (thanks to FastPackedString), handles serving both large (video) files and lazy (javascript) streaming, supports HTTP-Auth, and more.

Mail delivery agent with integrated DNS resolver

Stop worrying about making sure a separate local mail server or DNS is up and running to delivery your mail. HAppS takes care of making sure your mail is delivered as long as your application itself is running and makes sure no outbound mail is lost even with unplanned restarts.

XML and XSLT

Separate application logic from presentation using XML/XSLT. With HAppS, you can have your application output XML (via HTTP or SMTP) and handle style/presentation via separate XSLT files at runtime. HAppS takes care of doing server side XSLT for outbound mail and HTTP user-agents that don't support it client side.

SMTP Server

Handle incoming email in your application without worrying about .procmail or other user level inbound mail configuration hackery. Just have the HAppS.SMTP listen on port 25 or have the system mail server SMTP forward mail for your app to some internal port.

Monadic ACID transaction service

Write apps as a set of simple state transformers. MACID write-ahead logging and checkpointing make it easy for you to guarantee application integrity in the face of unplanned outages. MACID even guarantees that your side effects will be executed at-least-once if they can complete within a timelimit you define.

Session Service

Define bits of per-user application state that automatically expire after time limits you define. No more manual housekeeping of session data!

(Experimental) Table and Index

Do relational operations safely on in memory Haskell Data.Set(s) rather than dealing with an external SQL relational database. Define custom indices for your Haskell datatypes (e.g. geographic/geometric types). Use in combination with MACID for a robust relational DBMS customized for your application.

Categories: haskell

Haskell Filesystem

Isaac Jones writes about the release of Hafs, a Linux filesystem written in Haskell.

In the course of developing a web server for an embedded operating system, Galois Connections had need of a filesystem which was small enough to alter to our needs and written in a high-level language so that we could show certain high assurance properties about its behavior. Since we had already ported the Haskell runtime to this operating system, Haskell was the obvious language of choice. Halfs is a port of our filesystem to Linux.

Categories: haskell

Pushing events from the server to the browser

I've written in the past about the ways of pushing events from the server to the web browser. Recently a this model of usage has had a term defined for it called 'Comet'.

My plan was to have a library that modelled a web page as an asynchronous Erlang process. Other Erlang processes can send it messages using the standard Erlang constructs and the clients browser would process these messages. I put a proof of concept here.

This model of usage is becoming more and more popular evidenced by the number of Ajax based chat applications as well as the new 'Comet' term. The latest release of the Java based DWR library has added functoinality similar to the message passing example mentioned above.

DWR 2.0 allows what they are calling 'reverse ajax'. A simple to use API that enables the web server to call javascript functions on the browser.

The big new feature is Reverse Ajax: DWR 1.x allowed you to asynchronously call Java code from Javascript. DWR 2.0 builds on this to allow you to asynchronously call Javascript code from Java. Reverse Ajax makes writing interactive applications much easier. Reverse Ajax makes writing interactive applications much easier. It can use polling or Comet (long-lived HTTP) queries.

Categories: ajax, javascript

ICFP Programming Contest 2006

Information on the ICFP Programming contest for 2006 are up. It's being held on July 21-24, 2006 and run by Carnegie Mellon University.

Categories: misc

Factor and The Computer Language Shootout

I implemented one of the Computer Language Shootout benchmarks in Factor to see how it would compare. I wanted to get a gauge of the comparative performance of compiled Factor as well as seeing how the Factor implementations of the algorithms looked.

I started with the recursion benchmark. A darcs repository containing the Factor code and the C code for this can be obtained from the following command:

darcs get http://www.bluishcoder.co.nz/repos/computer-language-shootout

The Factor implementation is an almost direct translation of the C code.

To run the Factor code I created an image with the recursive.factor loaded and compiled:

./f factor.image -shell=tty
"recursive.factor" run-file
"recursive" words [ try-compile ] each
save

I then ran 'run-recursive.factor' which just calls the 'run' word in the recursive vocabulary and used the Unix 'time' command:

time ./f factor.image-shell=tty run-recursive.factor

The C code runs in 2.7 seconds with an argument of '11'. The Factor code runs in 31.8 seconds (it is hardcoded to use 11 as the argument). This is on my machine.

In the online recursive benchmarks the C code ran at 3.33 seconds. Assuming the speeds are relative this would mean that Factor would slot in at the benchmark at about 39.2 seconds ranking it slightly slower than GForth on the list.

The timing includes the starting up and relocating of the Factor image. Running the test within an already started image gives a 30.5 second runtime meaning the image startup takes about 1.3 seconds.

The code is written very much like the existing C code and I'll play around with it to see what a more concatenative style produces. Manfred Von Thun wrote an article on Nested Recursion for Joy that implemented Ackermann using a 'condnestrec' combinator. Trying a style like this in Factor to see the performance hit would be interesting.

Categories: factor