Code and Bugs

Coding things

Tag: Haskell

Enter Bucharest-fp group

A few days ago a new group was founded in Bucharest: Bucharest-fp group [0]. It is a place where people with a passion for functional programming can get together and discuss technical details and more.

The first meeting took place two days ago and it was a startup meeting. Te next meeting should be more interesting and I eagerly await it.

[0]: Right now, the content is little and in Romanian but this will not be a problem in the future when we will add more English content

Raptors

All xkcd‘s fans know the raptor problem: suppose you are standing at the centre of an equilateral triangle with three raptors in the corners, one of them injured (thus going with a slower speed). Knowing the speeds of all entities and the edge of the triangle determine the direction in which you will have to run to maximize your life time.

Read the rest of this entry »

Ships

Let’s say we have two ships arranged on a line. Both ships are sailing with the same speed. However, while the first one is always going in a perpendicular direction to the line initially connecting the ships, the second one will always try to go towards the first.

We are asked to determine the distance between the ships after enough time has passed.

Read the rest of this entry »

Visual Haskell Debugger (part 2)

The idea from the previous article received a lot of feedback both in the form of comments to the article or on reddit or on Haskell-Cafe (though, not on a dedicated topic).

For another proof of the idea, I will draw some diagrams by hand for the following suggested pieces of code. As you will see in this article, the drawing will evolve as I will tackle with more complex examples (and there are still pieces of code that I cannot render right now).

Read the rest of this entry »

Haskell Project Idea

Since a few days ago a little idea is bugging me: what if debugging Haskell programs would be reduced to a graphical interface and some clicks here and there to spot the problem?

What I have in mind is a new debugger very much GUI oriented. It will parse the code and interpret it and then it will offer a picture to the user in the GUI program.

For now, I will consider only the case of functions with no side effects. Suppose our user has, at some moment in the debugging phase, observed that one particular function gives wrong results. The only method of debugging that I know as of now is to use Debug.Trace and the trace function. However, this method involves changes to the code, none of which will really solve the bug. Cannot we do better?

I think that we can. Suppose that the code debugged is the following (simple demonstrative example) and that the user is debugging f.

f :: Int -> Int -> Int
f x y  = y + g x
 
g :: Int -> Int
g = (-1)

and the user observes that it gives output 7 instead of 8 when applied to 3 and 5. How the users reaches these values is beyond the scope of this article. He might have used quickcheck or he might have manually tested the code, it doesn’t matter. What does matter is what the proposed tool will show to the user:

Yes, a simple image describing only the inputs and the outputs of the function. What cannot be seen from the figure is that, although what he sees is a very abstract representation of his function, by clicking on the f name the tool will display the internals of the function, for the case taken.

The meaning of the rounded decorator around the + function is that that function’s implementation was not written by the user and it shouldn’t be debugged. However, the g function can be debugged and, by clicking on it, the GUI will open a new image, as if the user was really debugging function g right now.

Because this function doesn’t involve other user defined functions, the GUI will redirect any click on the function name to the actual implementation. The user would then be able to see what went wrong and correct the function (g was supposed to be id).

This was a simple example and the bug could be seen with naked eyes. However, this is not always the case and I think that this tool can help in debugging.

To be more helpful, I intend to extend this tool such that it can run a quickcheck test suite over one function using the informations that the user provide via the GUI. I intend to make the program to be capable of displaying informations at the type level and, maybe, allow the user to drag the boxes representing the functions and try to match them like some jigsaw puzzle. If there would be a missing link, the project might search on hoogle or hayoo for any function that matches that signature and offer a suggestion to the user.

I still have to think what should be done for functions returning other functions. I will not give up on handling curried functions but I haven’t decided yet how this would be represented graphically

Finally, maybe this tool can be also integrated with hlint, providing a visual feedback on common warnings issued by this tool (for example, runing hlint over one piece of my code showed 4 similar warnings concerning it)

Now, I don’t usually speak about my ideas in front of the public (or even remotely like blogging about it). I did this right now because this would be my first Haskell based project which could affect the community if all things are going well. But, before starting it, I want to see some feedback of whether this is needed, whether this is doable in one summer and whether this hasn’t been done before (I did a short search but found only tools remotely related to this project – either not debugging or not graphically displaying the code).

Thus, I finish this article by inviting every reader to give a feedback related to this project in the next few days. Depending on your feedback I may start working on a useful project or realise that my idea is not really such a brilliant one.

Haskell Compiler with LLVM backend

We know that GHC (The Glorious Haskell Compiler) can output it’s machine code via assembly or via C. Someone once asked on Haskell-cafe if LLVM couldn’t be used, taking into account that once you get your code to LLVM it will be very easy to deploy it to several platforms. Though, a year ago, the answer was discouraging, a BSC Thesis by David Therei contradicted this. Right now, we can write very fast code in Haskell using the LLVM backend. If you need a benchmark, see here an example.

Now, a short review on the thesis. Starting with a few details on compiler design and quickly dwelling into GHC, David presents his work on implemententing the LLVM backend for GHC. His thesis ends with some short evaluations but I enjoyed the above example more.

His paper has enough code examples to make everything clearer to any begginer into the topic of compilers and I recommend reading it while it is still open to anyone wanting to work on this area.

To me, reading this paper was like descovering a hidden treasury. Had I read it sooner I wouldn’t make several mistakes in my Verilog compiler (the third article will be written shortly after this post).

Raytracing

Yet another puzzle solved in Haskell. This time we have a raytracing problem. A simplified version but, nonetheless, hard to do in a functional way. At least in a non-monadic fashion.

Enough talk. Let’s see the problem: suppose we have a box with size n by m. Inside the box we have some light sensors – some cells which are initially black and which will turn to another colour as soon as one light ray comes very close to them. The sensors are placed at all integer coordinates in the box (assuming that the maximum allowed coordinates are n and m). Their sensitivity is chosen such that a cell is active only if the ray passes the point where the sensor is placed. Filling the box with sensors, we would like to obtain a picture of their state after several light sources are placed in the box.

Read the rest of this entry »

Segmented Sieve Of Eratosthenes

Today’s Programming Praxis problem describes an algorithm which may be used to find the prime numbers in a large interval, so large that it cannot be kept in memory at once. See their description there, I’ll only give the code in Haskell.

First, some utility functions:

firstQ :: Int -> Int -> Int
firstQ l pk = (-(1+l+pk) `div` 2) `mod` pk
 
nextQ :: Int -> Int -> Int -> Int
nextQ b pk qk = (qk - b) `mod` pk

Then we sieve one block and convert the values to the primes:

sieveBlock :: [Int] -> [Int] -> [Int] -> [Int]
sieveBlock [] [] blk = blk
sieveBlock (p:ps) (o:ofs) blk = filter f (sieveBlock ps ofs blk)
  where
    f x = (x < o) || ((x - o) `mod` p /= 0)
 
getValsfromBlock :: Int -> [Int] -> [Int]
getValsfromBlock l bl = map (\x->l+1+2*x) bl

Now, it’s time to obtain all the numbers. This post will make use of the until function which is very similar to what some will use for the `for` construct in C.

sieve :: Int -> Int -> Int -> [Int] -> [Int]
sieve l r b primes = middle $ until stop incr start
  where
    middle (_, v, _) = v
    stop (sb, _, _) = sb == r
    start = (l, [], map (firstQ l) primes)
    incr (startblock, primessofar, q) = (nextblock, nextprimes, nextq)
      where
        array = [0 .. b-1]
        nextblock = startblock + 2 * b
        nextprimes = primessofar ++ (getValsfromBlock startblock bl)
        nextq = zipWith (nextQ b) primes q
        bl = sieveBlock primes q array

The main is very simple after we know about the print function and that it is a monadic one

main = print $ sieve 100 20000 10 [3, 5, 7, 11, 13]

That’s all for now.

A Strange Machine

Another Haskell puzzle. This time, we have a 2D square matrix. Each cell can contain a number. We have a cursor which always resides in one cell of the matrix. Let s be the sum of values contained in the 8 neighbouring cells and the cursor’s cell. At each update step, we will modify the cell under cursor by using a bijective function of s. After this, we change the cursor location by moving it to a neighbouring cell or leaving it as it is, depending on the value of its cell.

We have to simulate such a machine, assuming that the matrix wraps at the boundary.

Read the rest of this entry »

The Monad Reader – Issue 15

Today, Brent Yorgey announced a new issue of «The Monad Reader». The waiting of 10 days since submission deadline and today was worth it: a project from Google Summer of Code (Gergely Patai – a new profiler for Haskell), 3 useful monads (Edward Z. Yang – Logic, Prompt and Failure) – of which the Prompt Monad will be used in a personal project, hopefully before April -, a new way to write monads (Heinrich Apfelmus – an operational view of monads) and a nice implementation of STM in pure Haskell (Andrew Coppin).

I’ll be back shortly.

Follow

Get every new post delivered to your Inbox.