Code and Bugs

Coding things

GCC Array

While doing one homework I’ve observed one little known fact about gcc: declaring dynamic arrays as normal arays (like int a[n])

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).

A non von Neumann Style of Programming

I’ve read an ACM Turing Award article these days. It belongs to John Backus and it is called «Can Programming be Liberated from the von Neumann Style?»

Though some perceive this paper as an apology for creating FORTRAN, a read of the article will show several aspects which transcends this opinion. We know that programming languages tend to grow more and more in complexity and constructs trying to become more powerful – I will not take the NKS road in this article. However, the growth rate of the complexity is far superior to that of power, something which is discouraging. Moreover, combining two programs to make a powerful one is not straightforward and easy as one would expect. In fact, this is because common language programs bear a close resemblance to a machine: they are similar constructs of a von Neumann architecture.

Starting from this idea and trying to be able to compose programs in a simple way, John Bakus presents a new kind of programming: the functional one. Don’t think of Haskell, Scheme, Lisp right now. He even proves that a version of Lisp is not useful. He then creates a simple (not so really) programming language which considers everything to be a function with no named parameters involved. Read the article for more information.

A new Programming Language (APL) was created after his language. For the most curious of you, here we have a Conway’s Game of Life implementation in one single line of code. Mind blowing language, isn’t it?

For more informations, one can read Conal’s article here. In fact, it was his blog which directed me to Bakus’ work. A single article upon which I stumbled when looking for Functional Reactive Programming articles.

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 »

Writing a Compiler for Verilog – part 2

As previously stated, I am working on a Verilog Compiler in Python using PLY. The last article talked in a generic way about the project, from now on we will talk about specific parts of the compiler.

Today, we begain with the first part of any compiler: the lexing part.

Read the rest of this entry »

Writing a Compiler for Verilog – part 1

This year, I took a class named Numerical Computers II (I had Numerical Computers I last year). The course was about Computer Architecture and things like this. However, I ended up with a very fascinating homework: to write a compiler for Verilog in a team of 2 to 4 people. The deadline is coming soon (I have to finish it by Friday) but I need a break so I’ll post here my story.

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.

Follow

Get every new post delivered to your Inbox.