Haskell

Various projects of mine using the Haskell programming language.


  Old - Some content is 10+ years old, not representing my current thoughts  

Index


Machine Learning

Gopher
Image Recognition

Some of my code is available on my GitHub Account


The Glorious Haskell Debugger


I've been looking into writing debugging and profiling tools for Haskell, and as a first step I wrote a document detailing the inner workings of GHC's stack (both the STG and the CCS one). If you have to debug a segfault in a GHC Haskell program, there's a full tutorial on how to do so using gdb. The document also describes how to write a debugger using the ptrace and Mach kernel APIs. Finally, I wrote a basic stack trace debugging tool. This is still very much work-in-progress.

Have a look at the project's GitHub repository.

Look at this awesome ghd-produced stack trace from my Game of Life program.

LRU Bounded Map


I wrote several Haskell implementations of associative containers (maps / dictionaries) which retire elements in least recently used (LRU) order when growing past a specified limit (bounded). Great exercise in pure functional data structure design, and the container is useful for implementing all kinds of caches. The implementations featured are a linked-list hash map, a double map, a 16-way Hash Array Mapped Trie (HAMT) and a Bitwise Trie / Hash Tree.

Source code and benchmarks / analysis are available on GitHub.

Benchmark results comparing all different implementations, measured using the Criterion library. It can generate HTML reports with nice looking charts like these.

Neskell


Neskell is my Haskell 6502 CPU emulator. The goal of the project was to learn more about Haskell, the 6502 and CPU emulation as well as developing an important piece of a future Nintendo Entertainment System (NES) emulator. So far, only the emulation of the NMOS 6502 / 2A03 is largely complete, no work on the PPU / APU has been attempted yet. Having comprehensive and easy to run tests is key for developing any emulator. Neskell features a test suite comprised of a number of custom and well-established tests from the community. Neskell aspires to emulate an NMOS 6502 or 2A03 (NES CPU) as accurately as possible. Every difference between the real hardware and the emulation observable by the program (or the user, once it is more than a CPU emulator) is considered a bug to be fixed. Currently, Neskell emulates all official and unofficial instructions with bit and cycle accuracy, including all known bugs and BCD behaviors. The emulator itself runs inside the ST monad and provides a very small load/store interface for manipulation of CPU / RAM state from the emulation code. The final goal would be extending the CPU emulator to a full system, most likely the NES.

The program is open source, see Neskell's GitHub page for more details and some interesting notes on Haskell emulator development and 6502 emulation.

The emulator has a comprehensive test suite which can run in parallel. The screenshot shows the console UI reporting testing progress.

Game of Life


The purpose of this project was to learn more about writing fast Haskell code working with arrays and displaying the results using OpenGL. Three versions of this program exist. A first version using Data.Array and GLUT, an improved one with Data.Vector and GLFW-b, and a third parallel version written with Async and Repa (stencils, partitioned arrays, traverse, convolve) using GHC's LLVM backend and containing a C++ & pthread reference implementation.

The code for all three versions is available on GitHub.

Third iteration of my Haskell Game of Life program using Repa partitioned arrays to efficiently work with the torus array data structure on multiple cores.

Jacky


Work-in-progress Haskell Twitter Newsreader. Features a very robust system for parallel downloading, decompressing and disk / memory caching of images with LRU semantics, including packing them efficiently into OpenGL textures and drawing them. Has a custom FreeType 2 integration with a basic text layout engine on top. Glyph and kern caching, full Unicode support and efficient OpenGL rendering implemented. Work-in-progress UI combinator library, including bin packing code for automatic tile layout. Fully-featured logging and tracing framework for debugging and performance measurement. Uses conduit and aeson for processing messages from the Twitter streaming and REST APIs.

The program is open source, see Jacky's GitHub page for more details.

Some debug displays with tiles of Twitter avatars, FreeType 2 font rendering, UI layout code, etc.
Unicode glyphs packed tightly into an OpenGL texture for rendering.
Debug mode for dumping rendered glyphs / strings to the console. Unicode block elements are a useful debugging aid for quickly visualizing things in a terminal.
kD tree for finding a tight layout for rectangles inside a larger bounding one (bin packing). Useful for packing textures (fonts, lightmaps), UI elements, etc. Supports online bin packing, uses a special optimization to keep kD trees from degenerating (see code).
Support for multiple typefaces and Unicode glyphs can be seen in this image.

Maximal Rectangle


The Maximal Rectangle problem is easy to explain, but tricky to solve efficiently. The task is finding the largest rectangular area in a plane filled with obstacles. The naive solution has unacceptable O(n^4) complexity, but clever use of dynamic programming can bring it down to O(n). I implemented the solution presented in this Dr. Dobb's article in Haskell.

Found it! I like using Unicode characters for quickly visualizing something using only a terminal.

Hackage Diff


I developed a tool to compare the public API of different versions of a Hackage library. It's open source, see the hackage-diff GitHub page for more details.

Showing a Diff between two versions of mtl. ANSI colors are supported to make everything a little quicker to interpret.

Julia Set


The Julia Set is a fractal related to the Mandelbrot Set, commonly visualised by plotting pixels with a brightness proportional to the number of iterations needed to estimate if a given coordinate is unbounded or not. I mostly coded this up as a starting point for some more complex work with fractals.

The source code for this project is available on GitHub.

The OpenGL application visualizes an animation over the different starting points of the Julia Set. It is easy to split up the computation over multiple cores.
A couple of stills from the animated version which the applications displays. To avoid banding, a smoothed iteration count is being used.
The widely-known Mandelbrot Set for good measure.

Ray Marching Distance Fields


This rendering technique has been becoming more popular in recent years, especially in the demo scene and with the two-triangle, all-shader approach to rendering popularized by fantastic sites like Shadertoy. I highly recommend these slides and this GTC presentation (just wget / curl if it doesn't play in the browser) by Inigo Quilez. 3D Distance Fields: A Survey of Techniques and Applications predates the current distance field boom, but is still worth a read. Also see this fantastic eight part series on ray marching distance estimated fractals. The rendering is all done with OpenGL 3.3+ / GLSL in a Haskell rendering framework and viewing application.

The source code for this project is available on GitHub.

A simple scene lit by a few light sources, created by combining basic shapes.
Using a smooth minimum function, distance fields can be combined without having hard edges at their interrsection points.
With distance fields it is very easy to distort the rendered shapes with various perturbations or transformations. Here a few sine waves are creating bumps in the surfaces.
With a triangle distance function scenes like the well-known Cornell Box can be rendered. The ambient occlusion is efficiently computed from the distance field. With an edge distance function, wireframe renderings can be produced. Notes on triangle distance estimation can be found here. A lossless, GPU friendly acceleration structure is described in A Complete Distance Field Representation.
See the Generalized Distance Functions paper and the Raymarching Toolbox Thread on Pouet.net for the distance functions used to render this scene.
The Haskell viewing application doing the pre-processing, functioning as a development and debugging aid, allowing different shaders to be explored. It automatically reloads and recompiles shaders when they change, showing an overlay displaying any errors. There's a flexible frame buffer system, supporting under and super sampling and saving of screenshots. Tiled rendering avoids shader timeouts and unresponsive UI.
An optimized I dubbed approach spheres. The scene is first rendered at a lower resolution with a higher distance threshold, and the last DE sphere is saved into a texture. The second full resolution pass then intersects with those spheres to start marching closer to the surface. Unfortunately, this does only help a little in most situations. Also see the Major Raymarching Optimization thread on Fractal Forums.

Prefiltered Environment Maps


Offline convolution of an environment map with a filter kernel to enable fast lighting of diffuse and glossy surfaces is a standard technique in computer graphics. I implemented a Haskell pipeline for this. The environment maps are loaded as HDR files in latitude / longitude format, convolved with a cosine lobe in a brute-force O(n^4) operation, cached to disk, converted into a cube map and uploaded to the GPU as half-floats for rendering. It's a rather slow process, but the low-pass nature of the convolution allows even high specular exponents like 1024 to be represented by low resolution 256x128 environment maps, making the pre-processing time acceptable. Some care has to be taken due to the area distortion of the latitude / longitude parameterization as well as potential artifacts from downscaling, cube map re-projection and cube map edge seams. It's still all fairly straightforward, though. An existing tool for this kind of prefiltering is AMD's CubeMapGen. Also see this excellent article for an improved version of the tool and some very helpful notes. Another option is to do the convolution at runtime using Spherical Harmonics.

The source code for this project is available on GitHub.

Various environment maps starting with their downsampled version on the left, then being pre-convolved with smaller and smaller exponent cosine lobes, down to a power one / diffuse lobe on the right.
Pure diffuse and specular reflection in the top row, varying degree of glossiness in the bottom row.
A selection of materials with all kinds of diffuse, glossy and specular reflection components under different illumination conditions. Rendered with a simple normalized Phong lighting model plus a Fresnel term.

Mandelbulb


The Mandelbulb is probably the most popular 3D fractal and best analog to the Mandelbrot Set we've got so far. While there exist number systems of one, two, four and eight dimensions, the three dimensional one ideally required to formulate a 3D version of the Mandebrot iteration formula, was missing. The key component to building one turns out to be a three dimensional version of the power operation, ingeniously implemented as rotating and scaling the point in spherical coordinates (there are several different formulas in use). The last missing piece was a distance estimator, allowing efficient visualisation. The Mandelbulb pages of Daniel White and Paul Nylander (both considered its inventors) are a perfect introduction and history lesson on this remarkable fractal. Also see the True 3D mandelbrot type fractal thread on Fractal Forums. Continuing with my previous work on ray marching distance fields and prefiltered environment maps, I decided to implement the Mandelbulb myself. Mikael Hvidtfeldt Christensen's fantastic eight part series on Distance Estimated 3D Fractals (1 2 3 4 5 6 7 8) was the perfect tutorial to get started. I also found Inigo Quilez' mandelbulb article, distance field work and his Julia Bulb entry on Shadertoy to be helpful. Most of the images below are rendered with ambient occlusion and IBL from my prior projects mentioned above. The same viewing application as for my other ray marching experiments is used, all actual rendering happens on the GPU through GLSL.

The source code for this project is available on GitHub.

The power 8 Mandelbulb. It is probably the most commonly used one. Integer powers also enjoy a more efficient implementation as the computation can be done without transcendental functions. The shading is an ambient occlusion glitch, which I thought looked rather neat.
Various renders of fractional powers between 2 and 6. The lower powers are less symmetric and show a more chaotic behavior. There's tremendous variety in the shapes the object can take.
Six more renders like above, simply because they look so nice. All images are super sampled with 64 samples per pixel. At lower quality, interactive frame rates can be achieved even on older GPUs, like the one in my 2009 MacBook Pro.
The lower powers often exhibit a whipped cream look reminiscent of Quaternion Julia Fractals. This early image still has a lot of artifacts.
Comparing ambient occlusion methods. The left side uses a cone occlusion test by checking sphere penetration along the normal with the DE, the right side is using the ray marching iteration count as a measure of occlusion.
Looks like a snowy mountain floating in space. Image inspired by a post on Fractal Forums. The ray marching iteration count is a surprisingly useful input for all kinds of creative effects.
A chrome power 8 Mandelbulb illuminated by the Dining Room HDR environment map from this collection.
A collection of twelve deep zooms into the surface of the Mandelbulb. There truly is no end to the amount of detail hidden inside the depths of this fractal. Be sure to view the image in full resolution (it is fairly big). All individual zooms have been rendered at 4096 * 4096 resolution and are downscaled to 512 * 512 here.
Another set of zooms to showcase the variety and beauty. I find the mixture of detailed and smooth regions very visually appealing.
Choosing pixels for super sampling by looking at the image contrast through the screen-space derivatives of the surface color. This unfortunately does not perform well in practice due to the divergence it introduces in the shader. The compaction and scatter passes required to avoid this would be difficult to implement with plain fragment shaders. A failed experiment, for now.
A collection of Mandelbulb images in different HDR environments (sources for the environment maps: 1 2 3 4). Very high resolution image, be sure to zoom in to see all the detail.

Hue Dashboard


This is a web application / web interface for controlling Philips Hue lights from any device with a browser. Hue is Philips' product range of "smart" light bulbs and switches. Hue devices use ZigBee Light Link mesh networking to communicate. Part of the Hue system is a bridge which connects the Hue devices to the network. The bridge offers both an integration into Apple's HomeKit framework and its own REST / HTTP / JSON API. There's a growing number of apps, home automation systems and 3rd party ZigBee devices working with Hue. Hue Dashboard aims to be an ideal control panel for daily operation of Hue lights. It works with any modern browser. Adjusting individual lights or the automatically created groups is comfortable both with a mouse or touch based input. Light groups can be shown / hidden, preferences are stored on a per-browser basis. Existing scenes are fetched from the bridge. Scene creation interface allows easy building of scenes from the current light state, also editing and updating of scenes is supported. Scenes are displayed with a preview of the lights they are going to change, and which groups they touch. All official Philips Hue lights are recognized and displayed with the appropriate graphics. Clicking a light / group caption makes the lamps blink (can be used as a crude form of communication!). The UI is done with vector graphics and looks crisp on retina displays. On-screen light status responds in real-time to changes with smooth animations and transitions. Schedule system allows automatic triggering of scenes at specified times, supports special actions like turning a scene off, having it slowly fade in or making the lights blink, can be scheduled only on certain weekdays, checks for differences between client & server time to avoid surprises, schedules can be deactivated as well. Server has been tested on OS X and Ubuntu, needs very little system resources to run. Can be deployed on a Raspberry Pi, even features a server control panel for shutdown / reboot and monitoring CPU / RAM usage. Implemented in Haskell, we're talking to the Hue bridge through its REST API using http-conduit. The web interface is done using threepenny-gui. Bootstrap and jQuery are used client-side.

More information, better screenshots and source code is available on GitHub.

Screenshot of the interface running on an iPhone 6. The icons are resolution independent SVG, provided by Philips for Hue developers.
Same thing, just this time on OS X. Can access an entire house worth of lights from a single screen. Hue Dashboard's backend is running on a Raspberry Pi, the server administration tile with the raspberry logo can be seen at the bottom.
The UI for the light color picker. There's also the option to put lights into a special color loop mode or assign them a random color.

 © 2002 - 2017 Tim C. Schröder Disclaimer